Transitive relation

from Wikipedia, the free encyclopedia
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 .

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 ):

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.

See also

Web links