Relation-Types and Properties of Relation

Relation- Types and Properties of relation. In this article, we will study the types of relation and their properties.  Also, we will study the equivalence relation, partially ordered relation, and closures of relation. Let us start the topic and understand the topic.

The only way to learn mathematics is to do mathematics-Paul Halmos

 Introduction

The concept of the term ‘relation’ in mathematics has been drawn from the meaning of relation in the English language, according to which two objects or quantities are related if there is a recognisable connection or link between the two objects or quantities. In this article, we will study the different types of relation, Inverse relation, composition of relations, closure properties of relations, and partition of a set.

 

Types of Relation

In this section, we would like to study different types of relations. We know that a relation in a set P is a subset of P × P. Thus, the empty set φ and P × P are two extreme relations. These two extreme examples lead us to the following definitions.

Definition 1. A relation R in a set P is called empty relation, if no element of P is related to any element of P, i.e., R = φ ⊂ P × P.

Definition 2. A relation R in a set P is called universal relation, if each element of P is related to every element of P, i.e., R = P × P.

Both the empty relation and the universal relation are some times called trivial relations.

 

Properties of Relation

Definition 3. A relation R in a set P is called

1.    Reflexive, if (a, a) ∈ R, for every a ∈ P. In other words, if R is not reflexive, then there exist at least one element a ∈ A such that (a, a) /∈ R.

2.    Symmetric, if (a₁, a₂) ∈ R implies that (a₂, a₁) ∈ R, for all a₁, a₂ ∈ P. For example, A = {1, 2}. Then R = {(1, 1), (1, 2), (2, 1)} defined on A × A.

     3.    Transitive, if (a₁, a₂) ∈ R and (a₂, a₃) ∈ R implies that (a₁, a₃) ∈ R, for all a₁, a₂, a₃ ∈ P.

4.    Anti-symmetric, if for any two elements a, b ∈ P, (a, b) ∈ R, (b, a) ∈ R =⇒ a = b. In other words, a relation R in a set is anti-symmetric if there (a, b), (b, a) /∈ R whenever a /= b.

Example 4. Let P = {2, 4, 6} defined by (a, b) ∈ R if a ≥ b, ∀ a, b, ∈ P. Then R = {(2, 2), (2, 4), (2, 6), (4, 4), (4, 6), (6,6)}

Determine whether the given relation is transitive, reflexive, symmetric or antisymmetric.

Solution: The given relation is reflexive as (a, a) ∈ R, for each a ∈ A, such that 2, 4, 6 ∈ A and (2, 2), (4, 4), (6, 6) ∈ R thus R is reflexive.

The given relation is not symmetric as (2, 4) ∈ R  but  (4, 2) /∈ R. The given relation is transitive as (a,b), (b, c) ∈ R then (a, c) ∈ R.

Relation R is anti-symmetrric if there (a, b), (b, a) /∈ R whenever a /= b.

 

Equivalence Relation

Definition 5. A relation R in a set P is said to be an equivalence relation if R is reflexive, symmetric, and transitive.

Example 6. If R be a relation in the set of integer Z, defined by R = {(x, y) : x ∈ Z, y ∈ Z, (x −y) is divisible by 6}. Then prove that R is an equivalence relation.

Solution: Let x ∈ Z, then x − x = 0 and 0 is divisible by 6. Therefore, xRx∀x ∈ Z. Hence, R is reflexive. Again, xRy

 

⇒ (x − y) is divisible by 6

⇒ −(x − y) is divisible by 6

⇒ (y − x) is divisible by 6

⇒ yRx

 

Hence, R is symmetric.

 

xRy and yRz ⇒ (x − y) is divisible by 6and (y − z) is divisible by 6

⇒ [(x − y) + (y − z)] is divisible by 6

⇒ (x − z) is divisible by 6

⇒ xRz

 

Hence, R is transitive.

Partial Order Relation

Definition 7. A relation R in a set P is said to be a partial order relation if R is reflexive, anti-symmetric, and transitive.

Example 8. Check whether the relation of divisibility on the set N of positive integers is an equivalence relation or not? Justify your answer.

Solution: Given a ∈ N, a is divisor of a, ie, aRa. Therefore R is reflexive.

If a is a divisor of b then b cannot be a divisor of a unless a = b. Thus aRb and bRa =⇒ a = b. Therefore

R is not symmetric, it is anti-symmetric.

Finally, a is the divisor of b and b is the divisor of c implies a is the divisor of c. Therefore, R is transitive. Since, R is reflexive, anti-symmetric, and transitive, therefore R is not an equivalence relation it is the partial order relation on N.

Note: Two elements a, b in a partially ordered set (P, ≤) are said to be comparable if either a ≤ b or b ≤ a.

If they do not hold then it is known as uncomparable.

 

Inverse Relation

Let R be a relation from set P to set Q, then the inverse of R, denoted by R⁻¹ is the relation from set Q to

P and is defined as

 

R⁻¹ = {(q, p) : q ∈ Q, p ∈ P, (p, q) ∈ R}

Also Domain of R⁻¹ = Range of R and Range of R⁻¹ = Domain of R.

 

Closure Properties of Relation

Let R be a relation on a set P, it is quite possible that this may lack some of the important relation properties discussed earlier, that is, reflexivity, symmetry, and transitivity. There may occur a situation where R does not have a particular property but with the addition of certain pairs of R we get a relation with the property. With the addition of the minimum number of ordered pairs, we can find the smallest relation R₁ on P that contains R and possesses the property we desired. But a relation of the type R₁ does not always exist. If there exists a relation such as R₁ then we call it the closure of R with respect to the property in question.

 

Reflexive Closure

The reflexive closure R_R of a relation R is the smallest reflexive relation that contains R as a subset.

To find the reflexive closure, has to know what pairs have to be added to the relation to make it reflexive.

Given a relation R on a set P, the reflexive closure of R can be formed by adding to R all pairs of the form

(a, a) ∈ R with a ∈ P, not already in R. Thus

 

R_R = R ∪ I_P

where I_P = {(a, a) : a ∈ P}.

 

Symmetric Closure

The symmetric relation R_S is the smallest symmetric relation that contains R as a subset. A symmetric relation contains (p, q). Since the inverse relation R⁻¹ contains (q, p) if (p, q) is in R, the symmetric closure of a relation can be constructed by taking the union of R and R⁻¹ that is, R ∪ R⁻¹ is the symmetric closure of R, where R⁻¹ = {(q, p) : (p, q) ∈ R}

 

Transitive Closure

A relation R is the transitive closure of R if R is the smallest relation containing R which is transitive. The transitive closure is usually denoted by R_T .

Example 9. Let R be the relation on a set A = {1, 2, 3, 4} defined by R = {(1, 2), (2, 3), (1, 3), (3, 4)}. Find reflexive closure and symmetric closure.

Solution: Given A = {1, 2, 3, 4} and R = {(1, 2), (2, 3), (1, 3), (3, 4)}.

Let S = {(1, 1), (2, 2), (3, 3), (4, 4)}.

Thus R_R = R ∪ S = {1, 1), (2, 2), (3, 3), (1, 2), (2, 3), (1, 3), (3, 4)(4, 4)}.

Now, R⁻¹ = {(2, 1), (3, 2), (3, 1), (4, 3)}.

Therefore, R_S = R ∪ R⁻¹ = {(1, 2), (2, 3), (1, 3), (3, 4), (2, 1), (3, 2), (3, 1), (4, 3)}

 

Composition of Relations

Let A, B, and C be sets, let R be a relation from A to B, and let S be a relation from B to C. Let R be a subset of A × B and S be a subset of B ×C. Then R and S give rise to a relation from A ×C denoted by RoS. Thus, RoS = {(a, c) : (a, b) ∈ R, (b, c) ∈ S}. Relation RoS is known as the composition of R and S. Suppose R is a relation on a set A, that is R is a relation from a set A to itself. Then RoR, the composition of R with itself is always defined and RoR is sometimes denoted by R².

Example 10. If R and S be the following relations on A = {1, 2, 3}, R = {(1, 1), (1, 2), (2, 3), (3, 1), (3, 3)}

and S = {(1, 2), (1, 3), (2, 1), (3, 3)}. Find Ros and S² = SoS.

Solution: Given relations are R = {(1, 1), (1, 2), (2, 3), (3, 1), (3, 3)} and S = {(1, 2), (1, 3), (2, 1), (3, 3)}.

Let us understand by arrow diagram.

Thus RoS = {(1, 2), (1, 3), (1, 1), (2, 3), (3, 2), (3, 3)}.

Here, SoS = {(1, 1), (1, 3), (2, 2), (2, 3), (3, 3)}.

Example 11. If R be a relation on A = {1, 2, 3, 4} defined by R = {(1, 2), (2, 3), (1, 3), (3, 4)}. Find R² = RoR.

Solution:

Thus RoS = {(1, 3), (1, 4), (2, 4)}.

                                                                                                    Partitions of a Set

Consider a non-empty set A and let P = {A₁, A₂, · · · , A_n}, where A₁, A₂, · · · , A_n are non-empty subsets of  A. Then the P is called the partition of A, if the following two conditions are satisfied:

1.    The set A is the union of subsets A₁, A₂, · · · , A_n ie, A₁ ∪ A₂ ∪ · · · ∪ A_n = A.

2.    The intersection of every pair of distinct subsets of A, is the null set, that is, if A₁ and A₂ ∈ P then either A₁ = A₂ or A₁ ∩ A₂ = φ .

References

[1]    B. S. Grewal, Higher Engineering Mathematics, Khanna Publishers, 40^th Edition.

 

[2]    H. Rosen Kenneth, Discrete Mathematics and its Applications, McGraw-Hill.

You can download the pdf from here.

You can watch these videos for more understanding about the topic.