Binary Relation Transitive Continuous and Monotone Implies Complete Proof

In set theory, a relation is defined as a way of showing a connection between any two sets. A relation in mathematics defines the link between two distinct sets of information. Relations and their theories are one of the primary topics of set theory. Sets, relations and functions are interlinked with one another. Sets indicate the collection of ordered elements or components on the other hand relations and functions illustrate the operations performed on sets.

During the morning assembly at schools, students are thought to be standing in a queue in the rising order of their heights. This illustrates an ordered relation between the students and their heights. With this article on transitive relations, we will aim to learn about the definition, transitive property with examples and more.

Transitive Relation Definition

Transitive relations are binary relations in discrete mathematics represented on a set such that if the first element is linked to the second element, and the second component is associated with the third element of the given set, then the first element must be correlated to the third element.

For example, if for three elements x, y and z in set A, if x = y and y = z, then x = z. Here, equality '=' denotes a transitive relation. There are mainly eight types of relations in discrete mathematics, namely empty relation, identity relation, universal relation, symmetric relation, transitive type of relation, equivalence relation, inverse relation and reflexive relation.

Also, read about Statistics here.

Condition for Transitive Relations

Mathematically, we can address it as a relation R marked on a set A is a transitive relation:

If (a, b) ∈ R and (b, c) ∈ R, then (a, c) ∈ R.

for all a, b, c ∈ A.

This is read as a binary relation R specified on a set A is supposed to be a transitive relation for all a, b, c in A if aRb and bRc, then aRc. That is if a is linked to b and b is linked to c, then a must be linked to c.

Let us consider set A as given below.

A = {p, q, r}

Let R be a transitive relation defined on set A.

Then,

R = { (p, q), (q, r), (p, r)}

That is,

If "p" is linked to "q" and "q" is associated with "r", then "p" must be related to "r".

In easy terms;

pRq, qRr -> pRr

Check out this article on Sets.

Transitive Relation Example

Transitive relations as read in the definition are binary relations in set theory that are defined on a set X such that component 'p' must be associated to element 'r', if 'p' is related to 'q' and 'q' is related to 'r', for p, q, r in X. To understand this, let us analyse an example of transitive relations.

Specify a relation R on the set of integers Z such that xRy if and only if x> y. Now, assume for integers x, y, z in Z, xRy and yRz ⇒ x > y and y > z. We know that for integers, whenever x > y and y > z, we have x > z which implies x is related to z, that is, xRz. Hence, R is a transitive type of relation.

Below are some mathematical and non-mathematical transitive examples of transitive relations for more practice.

• 'Is a subset of' denotes a transitive relation specified on a power set of sets. If X is a subset of Y and Y is a subset of Z, then X is a subset of Z.
• 'Is less than' also implies a transitive relation established on a set of numbers. If l < m and m < n, then l < n.
• 'Is equal to (denoted by the symbol '=')' is a transitive relation specified on a set of numbers. If p = q and q = r, then p = r.
• 'Is a biological sibling' also implies a transitive relation as if one character E is a biological sibling of another character F, and F is a biological sibling of G, then E is a biological sibling of G.
• 'Is congruent to' also means a transitive relation specified on the set of triangles. If triangle 'A' is congruent to triangle 'B' and triangle 'B' is congruent to triangle 'C', then triangle 'A' is congruent to triangle 'C'.

Example 1: Verify if 'is parallel to' specified on a set of lines is a transitive relation.

Solution: We know that if a line denoted by 'one' is parallel to line second line 'two' and if line 'two' is parallel to line 'three', then line 'one' is also parallel to line 'three' as lines parallel to the same line are parallel to one another.

Hence 'Is parallel to' is a transitive type of relation.

Example 2: Let A = { 3, 4, 5 } and R be a relation defined on set A as "is less than" and R = {(3, 4), (4, 5), (3, 5)}. Verify that R is transitive in nature.

Solution :

From the given set A, let:

a = 3

b = 4

c = 5

Here, we have;

(a, b) = (3, 4) -> this implies 3 is less than 4.

(b, c) = (4, 5) -> this implies 4 is less than 5.

(a, c) = (3, 5) -> this implies 3 is less than 5.

That is, if 3 is less than 4 and 4 is less than 5, then 3 is less than 5.

More precisely in terms of mathematical notation,

3R4, 4R5 -> 3R5

The above explanation proves that R is transitive.

Check out this article on Sequences and Series.

Properties of Transitive Relations

As of now, we know the transitive meaning and mathematical notation plus have also seen relevant examples, let us now learn some of the transitive properties.

• The inverse of a transitive relation is again a transitive one. For instance, as we reviewed above 'is less than' implies a transitive relation, then the opposite 'is greater than' is likewise a transitive relation.
• The union of two transitive relations may or may not be a transitive one. For example, assume P and Q are transitive relations so that (a,b) is in P, and (b,c) is in Q, but (a,c) is in neither.
• The junction of two transitive relations is again a transitive one. For instance, 'is greater than or equal to' and 'is equal to' are transitive in nature and their intersection relation is 'is equal to' which is also a transitive one.

Check more topics of Mathematics here.

The various types of relations we study in discrete mathematics are empty relation, identity relation, universal relation, symmetric relation, transitive relation, equivalence relation, inverse relation and reflexive relation. Here is a brief summary about the various types of relations along with their mathematical condition:

Types of Relations	Condition	Definition
Empty Relation	R = ∅ ⊂ A × A	A relation R in a set A is termed to be an empty relation if none of the elements of A is associated with any component of A.
Universal Relation	R = A × A	A relation is universal if every component of any given set is mapped to all the components of another set or the set itself.
Identity Relation	I or \(I_{A}\)= {(a, a), a ∈ A}	A relationship is supposed to be an identity relation if all the components of the given set are related to itself.
Inverse Relation	\(R^{-1}\) = {(b, a): (a, b) ∈ R}	If a set with elements holds the inverse pairs of another set, then the relation is termed inverse relation.
Reflexive Relation	(a, a) ∈ R	A relation specified on a set is a reflexive relation if and only if every component of the set is linked to itself.
Symmetric Relation	aRb ⇒ bRa, ∀ a, b ∈ A	A relation is supposed to be a symmetric one, in which the ordered pair of a given set plus the reverse ordered pair are present in the relation.
Transitive Relation	aRb and bRc ⇒ aRc ∀ a, b, c ∈ A	The relation R is said to be a transitive relation if it follows (a, b) ∈ R and (b, c) ∈ R ⇒ (a, c) ∈ R, ∀ a, b, c ∈ A.
Equivalence Relation	Reflexive: (a, a) ∈ R Symmetric: (a, b) ∈ R ⇒ (b, a) ∈ R ∀ a, b ∈ A Transitive: (a, b) ∈ R and (b, c) ∈ R ⇒ (a, c) ∈ R, ∀ a, b, c ∈ A	The relation R is said to be the equivalence relation if R is reflexive, symmetric, and transitive.
Asymmetric Relations	If (a, b) ∈ R, then (b, a) ∉ R, for all a, b ∈ A.	Asymmetric relation is the inverse of a symmetric type of relation.
Antisymmetric relation	(a, b) ∉ R and (b, a) ∉ R if a ≠ b.	A relation R on a set A is supposed to be antisymmetric, if aRb and bRa exist when a = b.

Learn more about Probability with this article.

Key Takeaways

A relation described on an empty set is always a transitive type of relation. Also, there is no set-up formula to determine the number of transitive relations on a given set.

The complement of a transitive relation may or may not be a transitive one.

• The mathematical notation of the transitive type of relation is:
• (a, b) ∈ R and (b, a) ∈ R ⇒ (a, c) ∈ R,
• That is aRb and bRc ⇒ aRc where a, b, c ∈ A.
• The relation is supposed to be non-transitive, if
• (a, b) ∈ R and (b, c) ∈ R do not indicate (a, c ) ∈ R.
• Also for a particular ordered pair in R, if we hold (a, b) and we don't possess (b, c), then we need not check transitive for that obtained pair.
• That is, we must check transitive, only if we observe both (a, b) and (b, c) in the given relation R.
• A binary relation R specified on a set P is an anti-transitive type of relation for a, b, c in P if (a, b) ∈ R plus (b, c) ∈ R, then this always signifies that (a, c) ∈ R does not exist.
• A binary relation R specified on a set P is an intransitive type of relation for some a, b, c in P if (a, b) ∈ R and (b, c) ∈ R however (a, c) ∉ R.
• Transitive relation examples:
• Whenever X > Y and Y > Z, then also X > Z.
• Whenever X ≥ Y and Y ≥ Z, then also X ≥ Z.
• Whenever X = Y and Y = Z, then also X = Z.

We hope that the above article on Transitive Relations is helpful for your understanding and exam preparations. Stay tuned to the Testbook App for more updates on related topics from Mathematics, and various such subjects. Also, reach out to the test series available to examine your knowledge regarding several exams.

Transitive Relation FAQs

Q.1 How do we define relation in maths?

Ans.1 In mathematics, a relation describes the relationship between sets of values of ordered pairs. The set of components in the first set are termed as a domain that is related to the set of the component in another set, which is designated as the range.

Q.2 What is the domain of a relation?

Ans.2 Let R express any relation from set A to set B. Then, the set of all the first components of the ordered pair relating to relation R makes the domain of the relation R.

Q.3 What are transitive relations?

Ans.3 Transitive relations are binary relations in set theory that are defined on a set X such that component 'p' must be associated to element 'r', if 'p' is related to 'q' and 'q' is related to 'r', for p, q, r in X.

Q.4  How do you know if a relationship is transitive?

Ans.4 If the first element of a given set is linked to the second element, and the second component is associated with the third element of the given set, then the first element must be correlated to the third element as per the transitive rule.

Q.5  What are Reflexive, Symmetric and Transitive Relations?

Ans.5 The condition for Reflexive, Symmetric and Transitive Relations are:
Reflexive: (a, a) ∈ R.
Symmetric: (a, b) ∈ R ⇒ (b, a) ∈ R ∀ a, b ∈ A.
Transitive: (a, b) ∈ R and (b, c) ∈ R ⇒ (a, c) ∈ R, ∀ a, b, c ∈ A.

Continue Reading in App

• 0

lovebutes1943.blogspot.com

Source: https://testbook.com/learn/maths-transitive-relations/

Share this post