# Transitive relation

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

## properties

- 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 .

## Examples

### Order of real numbers

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 .

### Subset

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

- Transitivity . In: Michiel Hazewinkel (Ed.): Encyclopaedia of Mathematics . Springer-Verlag , Berlin 2002, ISBN 978-1-55608-010-4 (English, online ).