Equivalence of Relations MCQ Quiz - Objective Question with Answer for Equivalence of Relations - Download Free PDF

The Correct Answer is 15

Key Points

• An equivalence relation is a relation that satisfies three properties: reflexive, symmetric, and transitive.
• Equivalence relations partition a set into disjoint subsets called equivalence classes.
• The number of equivalence relations on a set of size n corresponds to the number of ways to partition the set into non-empty subsets.

Detailed Solution

We are tasked with finding the number of equivalence relations for the set {1, 2, 3, 4}. The number of equivalence relations is equivalent to the number of partitions of the set, which is given by the Bell number.

The Bell number for a set of size n = 4 is:

• B(4) = 15

Explanation of Partitions:

The partitions of the set {1, 2, 3, 4} are as follows:

• 1 subset: {1, 2, 3, 4} (1 way)
• 2 subsets:
  • {1}, {2, 3, 4}
  • {2}, {1, 3, 4}
  • {3}, {1, 2, 4}
  • {4}, {1, 2, 3}
  • {1, 2}, {3, 4}
  • {1, 3}, {2, 4}
  • {1, 4}, {2, 3}
  • {1, 2, 3}, {4}
  • {1, 2, 4}, {3}
  • {1, 3, 4}, {2}
  • {2, 3, 4}, {1}
  • (11 ways)
• 3 subsets:
  • {1}, {2}, {3, 4}
  • {1}, {3}, {2, 4}
  • {1}, {4}, {2, 3}
  • {2}, {3}, {1, 4}
  • {2}, {4}, {1, 3}
  • {3}, {4}, {1, 2}
  • (6 ways)
• 4 subsets: {1}, {2}, {3}, {4} (1 way)

Total: 1 + 11 + 6 + 1 = 15

Conclusion:

The number of equivalence relations for the set {1, 2, 3, 4} is 15. Additional Information

• The Bell number, denoted as B(n), is a sequence that counts the number of partitions of a set with n elements.
• For small values of n, Bell numbers can be calculated directly, but for larger values, they are computed using recursion or other advanced mathematical methods.
• The Bell numbers for sets of size 1 to 4 are as follows:
  • B(1) = 1
  • B(2) = 2
  • B(3) = 5
  • B(4) = 15

The correct answer is option 4) 7

Key Points

• Given: R = {(1, 2), (2, 3)}
• Goal: Make R reflexive, symmetric, and transitive.
• Reflexive Closure: Add (1,1), (2,2), and (3,3)
• Symmetric Closure: Add (2,1) and (3,2)
• Transitive Closure: Since (1,2) and (2,3) exist, we must add (1,3); and since (3,2) and (2,1) are added, we also require (3,1) and (1,1) (already added).
• By carefully checking, the final set contains: {(1,1), (1,2), (1,3), (2,1), (2,2), (2,3), (3,1), (3,2), (3,3)} → 9 elements. Original had 2, so we added 7.

Additional Information

• Reflexive Relation: Must include (a,a) for all a ∈ A. Here A = {1,2,3}
• Symmetric Relation: If (a,b) exists, then (b,a) must also exist.
• Transitive Relation: If (a,b) and (b,c) exist, then (a,c) must also exist.

Hence, the correct answer is: option 4) 7

Calculation: 

a R a ⇒ 5a is multiple it 5

So reflexive

⇒ a R b ⇒ 2a + 3b = 5α,

Now b R a

⇒ 

= 

= 

= 5(a + b – α)

Hence symmetric

⇒ a R b ⇒ 2a + 3b = 5α.

⇒ b R c ⇒ 2b + 3c = 5β

Now 2a + 5b + 3c = 5(α + β)

⇒ 2a + 5b + 3c = 5(α + β)

⇒ 2a + 3c = 5(α + β – b)

⇒ a R c

∴  relation is an equivalence relation. 

Hence, the correct answer is Option 4. 

Calculation

Let S = {1, 2, 3, ........, 10}

R = {A, B) ∶ A ∩ B ≠ ϕ; A, B ∈ M}

For Reflexive,

M is set of all the subset of 'S'

So ϕ ∈ M

for ϕ ∩ ϕ = ϕ
⇒ but relation is A ∩ B ≠ ϕ

So it is not reflexive.

For symmetric,

ARB  ⇒  A ∩ B ≠ ϕ,

⇒ B ∩ A ≠ ϕ ⇒ BRA 

So it is symmetric.

For transitive,

If A = {(1, 2), (2, 3)}

B = {(2, 3), (3, 4)}

C = {(3, 4), (5, 6)}

ARB & BRC but A does not relate to C

So it not transitive

Hence option 4 is correct

Calculation

R = {(x, y), x + y is even x, y ∈ z}

reflexive x + x = 2x even

symmetric of x + y is even, then (y + x) is also even

transitive of x + y is even & y + z is even then x + z is also even

So, relation is an equivalence relation.

Hence option 3 is correct

Concept:

Reflexive: Each element is related to itself.

• R is reflexive if for all x ∈ A, xRx.

Symmetric: If any one element is related to any other element, then the second element is related to the first.

• R is symmetric if for all x, y ∈ A, if xRy, then yRx.

Transitive: If any one element is related to a second and that second element is related to a third, then the first element is related to the third.

• R is transitive if for all x, y, z ∈ A, if xRy and yRz, then xRz.

R is an equivalence relation if A is nonempty and R is reflexive, symmetric and transitive.

Calculation:

Here,  R = {(a, b): a, b ϵ N and a2 = b}

1. Relation R is not reflexive since, 2 ≠ 2²

2. Since, 2² = 4 so,  (2, 4) belong to R

But,  4 ≠ 2 and so, R is not symmetric

3. Since, 4² = 16, so (4, 16) belong to R

Also, 16² = 256,  so (16, 256) belong to R

But, 4² ≠ 256  so R is not transitive.

So, R satisfies none of the reflexivity, symmetry and transitivity.

Hence, option (4) is correct. 

Concept:

Let R be a binary relation on a set A.

1. Reflexive: Each element is related to itself.

• R is reflexive if for all x ∈ A, xRx.

2. Symmetric: If any one element is related to any other element, then the second element is related to the first.

• R is symmetric if for all x, y ∈ A, if xRy, then yRx.

3. Transitive: If any one element is related to a second and that second element is related to a third, then the first element is related to the third.

• R is transitive if for all x, y, z ∈ A, if xRy and yRz, then xRz.

4. R is an equivalence relation if A is nonempty and R is reflexive, symmetric and transitive.

Calculation:

Given: x

⇒ y ≥ x + 5

For Reflexive: (x, x) should ∈R for all x ∈ X

Now, x cannot be 5 years older than himself. So the relation is not reflexive.

For Symmetric: If (x, y) ∈ R ⇒(y, x) ∈ R

(x, y) ∈ R ⇒ y is at least 5 years older than x.

(y, x) ∈ R ⇒ x is at least 5 years older than y. This contradicts the above statement. Hence the relation is not symmetric

For Transitive: If (x, y) ∈ R and (y, z) ∈ R ⇒ (x, z) ∈ R.

(x, y) ∈ R ⇒ y is at least 5 years older than x.

(y, z) ∈ R ⇒ z is at least 5 years older than y.

Then, (x, z) ∈ R ⇒ z is at least 5 years older than x.

Since, z is at least 10 years older than x. The relation is transitive.

Concept:

Let R be a binary relation on a set A.

1. Reflexive: Each element is related to itself.

• R is reflexive if for all x ∈ A, xRx.

2. Symmetric: If any one element is related to any other element, then the second element is related to the first.

• R is symmetric if for all x, y ∈ A, if xRy, then yRx.

3. Transitive: If any one element is related to a second and that second element is related to a third, then the first element is related to the third.

• R is transitive if for all x, y, z ∈ A, if xRy and yRz, then xRz.

4. R is an equivalence relation if A is nonempty and R is reflexive, symmetric and transitive.

Calculation:

A relation is defined on Z such that aRb ⇒ (a − b) is divisible by 5,

For Reflexive: (a, a) ∈ R.

Since, (a − a) = 0 is divisible by 5. 

Therefore, the relation is reflexive.

For symmetric: If (a, b) ∈ R ⇒ (b, a) ∈ R.

(a, b)∈ R ⇒ (a − b) is divisible by 5.

Now, (b − a) = − (a − b) is also divisible by 5.

Therefore, (b, a) ∈ R

Hence, the relation is symmetric.

For Transitive: If (a, b) ∈ R and (b, a) ∈ R ⇒ (a, c) ∈ R.

(a, b) ∈ R ⇒ (a − b) is divisible by 5.

(b, c) ∈ R ⇒ (b − c) is divisible by 5.

Then,

(a − c) = (a – b + b −c)

(a − c)  = (a − b) + (b − c)

We know that (a − b) is divisible by 5 and (b − c) is divisible by 5 then (a − c) is also divisible by 5.  Therefore, (a, c) ∈ R.

Hence, the relation is transitive.

∴ the relation is equivalent.

Now, depending upon the remainder obtained when dividing (a−b) by 5 we can divide the set Z into 5 equivalent classes and they are disjoint i.e., there are no common elements between any two classes.

Concept: 

Reflexive relation: Relation is reflexive If (a, a) ∈ R ∀ a ∈ A.

Symmetric relation: Relation is symmetric, If (a, b) ∈ R, then (b, a) ∈ R.

Transitive relation: Relation is transitive, If (a, b) ∈ R & (b, c) ∈ R, then (a, c) ∈ R,

If the relation is reflexive, symmetric, and transitive, it is known as an equivalence relation.

Explanation:

Given that, A= {1, 2, 3}.

∴ Possible equivalence relations:

• R1 = {(1, 1), (2, 2), (3, 3)}
• R2= {(1, 1), (2, 2), (3, 3), (1, 2), (2, 1)}
• R3 = {(1, 1), (2, 2), (3, 3), (1, 3), (3, 1)}
• R4= ((1, 1), (2, 2), (3, 3), (2, 3), (3, 2)}
• R5 = {(1,1), (2,2), (3,3), (1,2), (1,3),(2,1),(2,3) (3,1),(3,2)}

∴ A maximum number of an equivalence relation is '5'.

Concept:

Let R be a binary relation on a set A.

1. Reflexive: Each element is related to itself.

R is reflexive if for all x ∈ A, xRx.

2. Symmetric: If any one element is related to any other element, then the second element is related to the first.

R is symmetric if for all x, y ∈ A, if xRy, then yRx.

3. Transitive: If any one element is related to a second and that second element is related to a third, then the first element is related to the third.

R is transitive if for all x, y, z ∈ A, if xRy and yRz, then xRz.

Calculation:

For reflexive:

mRm = m – m = 0 and nRn = n – n = 0 which is not odd

thus, it is not reflexive.

For symmetric:

mRn = m – n is odd then nRm = n – m is also odd

∴ This relation is symmetric.

For transitive:

Let m = 5, n = 2 and third number (p) = 1

mRn = 5 – 2 = 3 (odd), nRp = 2 -1 = 1 (odd) and mRp = 5 – 1 = 4 (even)

i.e., mRn and nRp ≠ mRp

∴ This relation is not transitive.

Hence, option (1) is correct.

Concept:

Reflexive: Each element is related to itself.

• R is reflexive if for all x ∈ A, xRx.

Symmetric: If any one element is related to any other element, then the second element is related to the first.

• R is symmetric if for all x, y ∈ A, if xRy, then yRx.

Transitive: If any one element is related to a second and that second element is related to a third, then the first element is related to the third.

• R is transitive if for all x, y, z ∈ A, if xRy and yRz, then xRz.

R is an equivalence relation if A is nonempty and R is reflexive, symmetric and transitive.

Calculation:

Here, R = {(a, b): a,b ϵ Z and (a + b) is even}

1. Since,a + a = 2a, ,which is even, so R is reflexive.

2. If a + b is even then b + a will also be even. So, R is symmetric.

3. Let, a = 3, b = 5, and c = 7.

a + b = 3 + 5 = 8 (which is even), b + c = 5 + 7 = 12 (which is again even) and a + c = 3 + 7 = 10 (which is also even)

Therefore, R is an equivalence relation on Z.

Hence, option (2) is correct.

Concept:

1. Reflexive: Each element is related to itself.

R is reflexive if for all x ∈ A, xRx.

2. Symmetric: If any one element is related to any other element, then the second element is related to the first.

R is symmetric if for all x, y ∈ A, if xRy, then yRx.

3. Transitive: If any one element is related to a second and that second element is related to a third, then the first element is related to the third.

R is transitive if for all x, y, z ∈ A, if xRy and yRz, then xRz.

4. R is an equivalence relation if A is nonempty and R is reflexive, symmetric and transitive.

Calculation:

For reflexive:

(a, a) = a – a = 0 is divisible by 3.

For symmetric:

If (a - b) is divisible by 3, then (b – a) = - (a - b) is also divisible by 3.

Thus relation is symmetric.

For transitive:

If (a - b) and (b - c) is divisible by 3

Then (a - c) is also divisible by 3

Thus relation is transitive.

∴ R is an equivalence relation

Hence, option (4) is correct.

Explanation:

Equivalence Relation: A relation R on a set A is said to be an equivalence relation if and only if the relation R is reflexive, symmetric, and transitive.

Ex. The relation R in the set {1, 2, 3} given by

R = {(1,1), (1,2), (1,3), (2,1), (2,2), (2,3), (3,1), (3,2), (3,3)} is equivalence.

Reflexive: A relation is said to be reflexive if (a, a) ∈ R, for every a ∈ A.

Ex. The relation R in the set {1, 2, 3} given by 

R = {(1,1), (2,2), (3,3)} is reflexive.

Symmetric: A relation is said to be symmetric, if (a, b) ∈ R, then (b, a) ∈ R.

Ex. The relation R in the set {a, b, c} given by

R = {(a,b), (b,a), (b,c), (c,b)} is symmetric.

Transitive: A relation is said to be transitive if (a, b) ∈ R and (b, c) ∈ R, then (a, c) ∈ R.

Ex. The relation R in the set {1, 2, 3} given by

R = {(1,2), (2,3), (1,3)}

Concept:

1. Reflexive: Each element is related to itself.

R is reflexive if for all x ∈ A, xRx.

2. Symmetric: If any one element is related to any other element, then the second element is related to the first.

R is symmetric if for all x, y ∈ A, if xRy, then yRx.

3. Transitive: If any one element is related to a second and that second element is related to a third, then the first element is related to the third.

R is transitive if for all x, y, z ∈ A, if xRy and yRz, then xRz.

4. R is an equivalence relation if A is nonempty and R is reflexive, symmetric and transitive.

Calculation:

Here, xRy → x - y = 5 years Where x,y ∈  X (citizen of India)

For Reflexive:

xRx → x - x ≠ 5, So its not reflexive

For symmetric:

xRy → x - y = 5 and yRx → y - x = 5, difference will be 5 years only

So its symmetric

For transitive:

Let, x = 25, y = 20, and z = 15

x - y = 5, y - z = 5, but x - z ≠ 5

If xRy and yRz, then not necessarily, xRz.

So, its not transitive.

Hence, option (2) is correct. 

Concept:

1. Reflexive: Each element is related to itself.

• R is reflexive if for all x ∈ A, xRx.

2. Symmetric: If any one element is related to any other element, then the second element is related to the first.

• R is symmetric if for all x, y ∈ A, if xRy, then yRx.

3. Transitive: If any one element is related to a second and that second element is related to a third, then the first element is related to the third.

• R is transitive if for all x, y, z ∈ A, if xRy and yRz, then xRz.

4. R is an equivalence relation if A is nonempty and R is reflexive, symmetric and transitive.

Calculation:

S = Set of all integers and R = {(a, b), a, b ϵ  S and ab  0}

For reflexive:

aRa = a.a = a² ≥ 0, so it's reflexive.

For symmetric:

aRb = ab ≥ 0 and bRa = ba ≥  0, So relation is symmetric

For transitive:

For all integers, if ab ≥ 0, bc ≥  0, then for all the cases ac ≥ 0 is not true.

For example,

If a = -1, b = 0, and c =1

Then,  ab ≥ 0, bc ≥  0 but for ac = -1 which is not satisfying ac ≥ 0 so R is not transitive.

So, Relation Is reflexive, symmetric but not transitive. 

Hence, option (2) is correct.