# Transitive relation

Transitive two and a non-transitive relation (bottom right) as directed graphs shown

A transitive relation is in mathematics a double-digit relation to a quantity that for three elements that has the property , , the amount of and always follows. Examples of transitive relations are the direct and the less-relations to the real numbers , because for three real numbers , and with and applies always , and out and followed . ${\ displaystyle R}$${\ displaystyle x}$${\ displaystyle y}$${\ displaystyle z}$${\ displaystyle xRy}$${\ displaystyle yRz}$${\ displaystyle xRz}$${\ displaystyle x}$${\ displaystyle y}$${\ displaystyle z}$${\ displaystyle x = y}$${\ displaystyle y = z}$${\ displaystyle x = z}$${\ displaystyle x ${\ displaystyle y ${\ displaystyle x

A non-transitive relation is called intransitive (not to be confused with negative transitivity ). Transitivity is one of the prerequisites for an equivalence relation or an order relation .

## Formal definition

If there is a set and a two-digit relation , then is said to be transitive if (using the infix notation ): ${\ displaystyle M}$${\ displaystyle R \ subseteq M \ times M}$${\ displaystyle M}$${\ displaystyle R}$

${\ displaystyle \ forall x, y, z \ in M: xRy \ land yRz \ Rightarrow xRz.}$

## Representation as a directed graph

Any relation on a set can be interpreted as a directed graph (see example above). The nodes of the graph are the elements of . A directed edge (an arrow ) is drawn from node to node if and only if applies. ${\ displaystyle R}$${\ displaystyle M}$${\ displaystyle M}$${\ displaystyle a}$${\ displaystyle b}$${\ displaystyle a \ longrightarrow b}$${\ displaystyle aRb}$

The transitivity of can now be characterized in the graph as follows: Whenever two arrows follow one another ( ), there is also an arrow that directly connects the start and end nodes ( ) (also in the Hasse diagram ). ${\ displaystyle R}$${\ displaystyle a \ longrightarrow b \ longrightarrow c}$${\ displaystyle a \ longrightarrow c}$

## properties

• The transitivity of a relation also allows conclusions to be drawn across several steps (as can easily be shown by complete induction ): ${\ displaystyle R}$
${\ displaystyle a \, R \, b_ {1} \, R \, b_ {2} \, R \, \ dots \, R \, b_ {n} \, R \, c \ implies a \, R \, c}$
• With the help of the chaining of relations, transitivity can also be characterized by the following condition: ${\ displaystyle \ circ}$
${\ displaystyle R \ circ R \ subseteq R}$
• If the relation is transitive, then this also applies to the converse relation . Examples: the relation is too converse, the relation is too converse .${\ displaystyle R}$ ${\ displaystyle R ^ {- 1}}$${\ displaystyle \ leq}$${\ displaystyle \ geq}$${\ displaystyle <\}$${\ displaystyle> \}$
• If the relations and are transitive, then this also applies to their intersection . This statement can be generalized from two relations to the intersection of any family of transitive relations.${\ displaystyle R}$${\ displaystyle S}$ ${\ displaystyle R \ cap S}$${\ displaystyle \ cap _ {i \ in I} R_ {i}}$
• For every relation there is a smallest transitive relation that contains, the so-called transitive envelope of . Example: let the predecessor relation be on the set of natural numbers, so it applies . The relation itself is not transitive. The smaller relation results as the transitive envelope of .${\ displaystyle R}$${\ displaystyle S}$${\ displaystyle R}$${\ displaystyle R}$
${\ displaystyle R}$${\ displaystyle a \, R \, b: \ Longleftrightarrow a = b-1}$${\ displaystyle R}$${\ displaystyle R}$${\ displaystyle <\}$

## Examples

### Order of real numbers

From a> b and b> c follows a> c.

The smaller relation on the real numbers is transitive, because it follows from and . It is also a strict total order . ${\ displaystyle <\}$${\ displaystyle x ${\ displaystyle y ${\ displaystyle x

Likewise, the relations , and are transitive. ${\ displaystyle> \}$${\ displaystyle \ leq \}$${\ displaystyle \ geq \}$

### Equality of real numbers

Ordinary equality on real numbers is transitive, because it follows from and . It is also an equivalence relation . ${\ displaystyle = \}$${\ displaystyle x = y}$${\ displaystyle y = z}$${\ displaystyle x = z}$

The inequality relation on the real numbers, however, is not transitive: and , but of course does not hold. ${\ displaystyle \ neq}$${\ displaystyle 3 \ neq 5}$${\ displaystyle 5 \ neq 3}$${\ displaystyle 3 \ neq 3}$

### Divisibility of the whole numbers

The divisibility relation for integers is transitive, because it follows from and . It is also a quasi-order . If you restrict to the set of natural numbers , you get a partial order . ${\ displaystyle |}$${\ displaystyle a | b}$${\ displaystyle b | c}$${\ displaystyle a | c}$

Not, for example, is transitive the coprimality . So and are coprime, just as and , but have and the common factor . ${\ displaystyle 12}$${\ displaystyle 5}$${\ displaystyle 5}$${\ displaystyle 9}$${\ displaystyle 12}$${\ displaystyle 9}$ ${\ displaystyle 3}$

### Subset

The subset relationship between sets is transitive, because it follows from and . In addition, is a partial order. ${\ displaystyle \ subseteq}$${\ displaystyle A \ subseteq B}$${\ displaystyle B \ subseteq C}$${\ displaystyle A \ subseteq C}$${\ displaystyle \ subseteq}$

For example, the disjointness of sets is not transitive . The sets and are disjoint, as are and , but not and (since they have the element 1 in common). ${\ displaystyle \ lbrace 1,2 \ rbrace}$${\ displaystyle \ lbrace 3 \ rbrace}$${\ displaystyle \ lbrace 3 \ rbrace}$${\ displaystyle \ lbrace 1,4 \ rbrace}$${\ displaystyle \ lbrace 1,2 \ rbrace}$${\ displaystyle \ lbrace 1,4 \ rbrace}$

### Parallel straight lines

In the geometry that is parallelism of straight transitive: If both the straight and parallel and the straight lines and then also and in parallel. In addition, the parallelism is an equivalence relation. ${\ displaystyle g_ {1}}$${\ displaystyle g_ {2}}$${\ displaystyle g_ {2}}$${\ displaystyle g_ {3}}$${\ displaystyle g_ {1}}$${\ displaystyle g_ {3}}$

### Implication in logic

In logic , transitivity applies to the implication , although this is also known as modus barbara in predicate logic :

From and follows (compare also: rule of intersection ). ${\ displaystyle A \ Rightarrow B}$${\ displaystyle B \ Rightarrow C}$${\ displaystyle A \ Rightarrow C}$

The implication defines a quasi-order on the formulas of the logic under consideration.