Transitive Relations

Transitive relations are binary relations defined on a set such that if the first element is related to the second element, and the second element is related to the third element of the set, then the first element must be related to the third element. For example, if for three elements a, b, c in set A, if a = b and b = c, then a = c. Here, equality '=' is a transitive relation. There are mainly three types of relations in discrete mathematics, namely reflexive, symmetric and transitive relations among many others.

In this article, we will explore the concept of transitive relations, its definition, properties of transitive relations with the help of some examples for a better understanding of the concept.

Transitive relations are binary relations in set theory that are defined on a set A such that if a is related to b and b is related to c, then element a must be related to element c, for a, b, c in set A. To understand this, let us consider an example of transitive relations. Define a relation R on the set of integers Z as aRb if and only if a > b. Now, assume for integers a, b, c in Z, aRb and bRc ⇒ a > b and b > c. We know that for integers, whenever a > b and b > c, we have a > c which implies a is related to c, that is, aRc. Hence, R is a transitive relation.

Transitive Relations Definition

A binary relation R defined on a set A is said to be a transitive relation for all a, b, c in A if a R b and b R c, then a R c, that is, if a is related to b and b is related to c, then a must be related to c. Mathematically, we can write it as: a relation R defined on a set A is a transitive relation for all a, b, c ∈ A, if (a, b) ∈ R and (b, c) ∈ R, then (a, c) ∈ R.

Let us see some definitions of relations that are related to transitive relations:

• Anti-transitive Relation - A binary relation R defined on a set A is an anti-transitive relation for a, b, c in A if (a, b) ∈ R and (b, c) ∈ R, then this always implies that (a, c) ∈ R does not hold.
• Intransitive Relation - A binary relation R defined on a set A is an intransitive relation for some a, b, c in A if (a, b) ∈ R and (b, c) ∈ R but (a, c) ∉ R.

Now, that we have studied the definition of transitive relations, let us go through some mathematical as well non-mathematical examples of transitive relations for a better understanding.

• 'is a subset of' is a transitive relation defined on a power set of sets. If A is a subset of B and B is a subset of C, then A is a subset of C.
• 'Is a biological sibling' is a transitive relation as if one person A is a biological sibling of another person B, and B is a biological sibling of C, then A is a biological sibling of C.
• 'Is less than' is a transitive relation defined on a set of numbers. If a < b and b < c, then a < c.
• 'Is equal to (=)' is a transitive relation defined on a set of numbers. If a = b and b = c, then a = c.
• 'is congruent to' is a transitive relation defined on the set of triangles. If triangle 1 is congruent to triangle 2 and triangle 2 is congruent to triangle 3, then triangle 1 is congruent to triangle 3.

Let us explore some properties of transitive relations:

• The inverse of a transitive relation is a transitive relation. For example, as we discussed above 'is less than' is a transitive relation, then the converse 'is greater than' is also a transitive relation.
• The union of two transitive relations need not be transitive. For example, Suppose R and S are transitive relations such that (x,y) is in R, and (y,z) is in S, but (x,z) is in neither.
• The intersection of two transitive relations is a transitive relation. For example, 'is greater than or equal to' and 'is equal to' are transitive relations and their intersection relation is 'is equal to' which is a transitive relation.
• A transitive relation is an asymmetric relation if and only if it is irreflexive.

Important Notes on Transitive Relations

• A relation defined on an empty set is always a transitive relation.
• There is no fixed formula to determine the number of transitive relations on a set.
• The complement of a transitive relation need not be transitive.

Related Topics on Transitive Relations

• Symmetric Relations
• Reflexive Relations
• Equivalence Relations

What are Transitive Relations in Set Theory?

Transitive relations are binary relations in set theory that are defined on a set B such that element a must be related to element c, if a is related to b and b is related to c, for a, b, c in B.

What are Reflexive, Symmetric and Transitive Relations?

• A binary relation R defined on a set A is said to be reflexive if, for every element a ∈ A, we have aRa, that is, (a, a) ∈ R.
• A binary relation R defined on a set A is said to be symmetric iff, for elements a, b ∈ A, we have aRb, that is, (a, b) ∈ R, then we must have bRa, that is, (b, a) ∈ R.
• A binary relation R defined on a set A is said to be a transitive relation for all a, b, c in A if a R b and b R c, then a R c,

How to Find the Number of Transitive Relations?

There is no fixed formula to determine the number of transitive relations on a set.

What the Other Relations Similar To Transitive Relations?

The other type of relations similar to transitive relations are the reflexive and symmetric relation. The reflexive relation is relating the element of set A and set B in the reverse order from set B to set A. And the symmetric relation is when the domain and range of the two relations are the same.

Is the Intersection of Two Transitive Relations Transitive?

Yes, the intersection of two transitive relations is a transitive relation.

Is the Union of Two Transitive Relations Transitive?

No, the union of two transitive relations need not be transitive.