Transitive two and a non-transitive relation (bottom right) as directed graphs
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 .
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 .
If there is a set and a two-digit relation , then is said to be transitive if (using the infix notation ):
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.
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 ).
- The transitivity of a relation also allows conclusions to be drawn across several steps (as can easily be shown by complete induction ):
- With the help of the chaining of relations, transitivity can also be characterized by the following condition:
- If the relation is transitive, then this also applies to the converse relation . Examples: the relation is too converse, the relation is too converse .
- 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.
- 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 .
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 .
Likewise, the relations , and are transitive.
Equality of real numbers
Ordinary equality on real numbers is transitive, because it follows from and . It is also an equivalence relation .
The inequality relation on the real numbers, however, is not transitive:
and , but of course does not hold.
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 .
Not, for example, is transitive the coprimality . So and are coprime, just as and , but have and the common factor .
The subset relationship between sets is transitive, because it follows from and . In addition, is a partial order.
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).
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.
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 ).
The implication defines a quasi-order on the formulas of the logic under consideration.