Transitive Relation

A transitive relation is in mathematics, a binary relation on a set that has the property that for from three elements, this amount and always follows. A non- transitive relation is called intransitive. The transitivity is one of the prerequisites for an equivalence relation or an order relation.

Formal definition

Is a set and a binary relation on, then called transitive if and only if (using infix notation ):

Representation as a directed graph

Any relation on a set can be regarded as a directed graph (see example above). The nodes of the graph are the elements of. From node to node is a directed edge if and only pulled (an arrow ) if the following applies.

The transitivity of the graph can now be characterized as follows: Whenever two consecutive arrows (), there is also an arrow, the start and end node connects directly ().

Properties

• The transitivity of a relation also permits conclusions about several steps away (as one easily shows by induction ):
• Using the chain of relationships can also be represented by the following transitivity condition characterized:
• The relation is transitive, this also applies to the converse relation. EXAMPLES The converse relationship is to be, to be converse.
• Are the relations and transitive, then this also applies to their intersection. This statement can be generalized from two relations on the intersection of any family of transitive relations.
• There is a smallest transitive relation that contains the so-called transitive closure of any relation to. Example: is the predecessor relation on the set of natural numbers, so it is true. The relation itself is not transitive. As a transitive closure of results in the less-than relation.

Examples

Order of the real numbers

The less-than relation on the real numbers is transitive, because then follows. She is also a strict total order.

Similarly, the relations, and transitive.

Equality of real numbers

The usual equality on the reals is transitive, because then follows. She is also an equivalence relation.

The inequality relation on the real numbers, however, is not transitive: and, but of course does not apply.

Divisibility of integers

The divisibility of integers is transitive, because then follows. She is also a quasi-ordering. When restricting to the set of natural numbers we obtain a partial order.

Non- transitive, for example, the coprimality. Thus, and prime, and well, however, and have the common divisor.

Subset

The subset relation between sets is transitive, because then follows. Furthermore, a partial order.

Non- transitive, for example, the disjointness of sets. Thus, the quantities and disjoint, and also, but not, and ( as they the element 1 in common).

Parallel lines

In geometry the parallelism of lines is transitive: If both the straight and parallel as well as the lines and then are also parallel. Moreover, the parallelism is an equivalence relation.

Implication in the logic

In the logic of transitivity with respect to the implication holds, where this is known in the predicate logic as a mode barbara:

Off and follows (see also: cut rule ).

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