Test: Equivalence Relations - Computer Science Engineering (CSE) MCQ

Given:

Relation R is defined by function R = {(a, b) | (a - b) = km for some fixed integer m and a, b, k ∈ z}.

1. For the same number a, R = a - a = 0 × m, where m is a fixed integer and 0 є z, hence the relation R is reflexive.
2. For two numbers (a, b) if R = a - b = km, where m is a fixed integer and k є z, then for (b, a), R = b - a = -(a - b) = -km, where -k є z. Hence relation R is symmetric.
3. Consider three numbers a, b, and c. If, for (a, b), R = a - b = km and for (b, c), R = b - c = lm, where m is a fixed integer and k, l є z, then for (a, c), R = a - c = a - b + b - c = km + lm = m(k + l), where (k + l) є z, since k, l є z. Hence relation R is transitive.

Hence, relation R is an equivalence relation.
Hence, the correct answer is option 4.

Let us check all the conditions:

Reflexivity:
Let x be an arbitrary element of R. For Reflexive, let y + x
i.e. for any x ∈ R
⇒ 2x + x = 41

Thus, it is NOT reflexive.

Symmetry:
Let (x, y) ∈ R. Then,
2x + y = 41 Which is not equal to 2y + x = 41
i.e. (y , x) ∉ R
So, R is NOT symmetric.

Transitivity:
Let (x, y) and (y, z) ∈ R
⇒ 2x + y = 41 and 2y + z = 41
which is not equal to 2x + z = 41
i.e. (x , z) ∉ R
Thus, R is NOT transitive.

Let's start with Option 3;

Option 3:if a relation S is reflexive and circular, then S is an equivalence relation.
It is correct.
- S is reflexive and circular; see that if are able to derive Symmetric and transitive property from these given properties.
aRa ∈ S and aRb ∈ S => bRa ∈ S   //Using Reflexive and circular 
aRb and bRa both exist then the relation is Symmetric.
- Now 
aRb and bRc together => cRa and according to symmetricity ≡  aRc 
aRb and bRc together => aRc
Hence Transitivity satisfied.
Hence S is an Equivalence Relation.
Example : S = { {a,a) (b.b) (c,c) } (diagonal relation)

Option 1: If a relation S is transitive and circular, then S is an equivalence relation.
It is not correct.
Consider a example of empty relation or S = {(a,b)}; it is transitive and circular but its not Equivalence Relation.
Hence S is not an equivalence Relation.

Option 2: If a relation S is reflexive and symmetric, then S is an equivalence relation.
It is not correct. For a Relation S to be Equivalence Reflexive, Symmetric and Transitive are required.

Option 4: if a relation S is circular and symmetric, then S is an equivalence relation.
It is not correct.
Consider a example of empty relation or S = {(a,b) , (b,a), (a,a)}; It is circular and symmetric but its not Equivalence relation.
Hence S is not an equivalence Relation.

Given: a R_mb if and only if a ≡  b mod.
Since m|(a-a) = 0, we have a ≡ a mod m
So  R_m is reflexive.
if m|(a-b), then
​⇒ m|(-1)(a-b).
⇒ m|(b-a).
​⇒ So, if a ≡  b mod m​​ ⇒ b ≡  a mod m.

• Therefore, Rm is symmetric.
• If aRmb and bRmc 

​⇒ m|(a-b) and m|(b - c).
​⇒ m|[(a-b) + (b-c)] 
⇒ m|(a-c) ⇒  a Rmc

Therefore R_m is transitive.
Hence the relation is an equivalence relation.
Therefore option 4 is correct.

Option D is wrong as transitivity may break on taking the union of two equivalence relations
For two equivalence relation R and S

• The largest equivalence relation in R and S is R∩S
• The smallest equivalence relation which contains R and S is (R∪S)∞ {transitive closure}

So option A is correct.
Option C is trivially false as option A is correct.

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

• Since,a + a = 2a, ,which is even, so R is reflexive.
• If a + b is even then b + a will also be even. So, R is symmetric.
• 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.

(1) { (f, g) | f (x) − g (x) = 1 x ϵ  Z }
It is not reflexive. As f(x) – f(x) = 0 it is not 1. It is also not transitive. So, it cannot be an equivalence relation.

(2) {(f, g) | f (0) = g (0) or f (1) = g (1) }
This relation is not transitive. Suppose f(x) = 0, g(x) = x and h(x) = 1. Here f is not related to h. Only we have a relation given between f and g, g and h. but not between f and h. So, it cannot be an equivalence relation.

(3) {(f, g) | f (0) = g (1) and f (1) = g (0) }
It is not always true f(0) = f(1) for reflexive case. So, it is not reflexive. Hence, no equivalence relation.

(4) { (f, g) | f (x) − g (x) = k for some k ϵ  Z }
It is reflexive relation, consider constant as 0. It is also symmetric because the difference will be equal to a constant value. It is also transitive. So, it is an equivalence relation.

Here,  R = {(a, b): a, b ϵ N and a² = b}
1. Relation R is not reflexive since, 2 ≠ 2²
2. Since, 22 = 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. 

A = {p, q} ∴ n = 4
R = {(p, p), (p, q), (q, p), (q, q)}
∴ Reflexive
The largest equivalence relation is n² = 2² = 4
Diagraph of this relation will have only one connected component, hence this relation has rank 1.

Let two lines ℓ₁, ℓ₂ ∈ L
Now (ℓ₁, ℓ₂) ∈ R
Only when ℓ₁ ⊥ ℓ₂
1. For reflexivity:
Let ℓ₁ ∈ L
But (ℓ₁, ℓ₁) ∉ R
Since no line is perpendicular to itself
R is not reflexive

2. For symmetric:
Let, (ℓ₁, ℓ₂) ∈ L
Now, if ℓ₁ ⊥ ℓ₂ then this implies that ℓ₂ is also perpendicular to ℓ₁
Hence, (ℓ₁, ℓ₁) ∈ L
R is symmetric.

3. For Transitive:
Let (ℓ₁, ℓ₂) ∈ L and (ℓ₂, ℓ₃) ∈ L
ℓ1 ⊥ ℓ₂ and ℓ₂ ⊥ ℓ₃

ℓ1 is not perpendicular to ℓ₃
(ℓ­₁, ℓ₃) ∉ R
∴ Not transitive