For a relation to be equivalent, it needs to be reflexive, symmetric and transitive. We are given some relations on the set of alphabets over {a, b}.
R1 = {(u, v) | |uv| is prime}
- Reflexive: Let u = a. For R1 to be reflexive, all (u, u) should belong to R1. But it can be shown the |uu| = 2|u| = an even number ∉ Prime numbers → (u, u) ∉ R1. ∴ R1 is not reflexive and thus not equivalent.
R2 = {(u, v) | v is permutation of u}
- Reflexive: It can be shown that (u, u) ∈ R2 ∀ u since u is a permutation of itself.
- Symmetric: If (u, v) ∈ R2, then (v, u) ∈ R2. Let u = ab, v = ba. Then both (ab, ba) and (ba, ab) ∈ R2. Hence, symmetric.
- Transitive: If (u, v) ∈ R2 and (v, w) ∈ R2, then (u, w) ∈ R2. If v is a permutation of u and w is a permutation of v, then all u, v and w are permutations of each other. Hence R2 is transitive.
So, R2 is an equivalent relation.
R3 = {(u, v) | |uv| is even}
- Reflexive: It can be shown that (u, u) ∈ R3 ∀ u since |uu| = |u| + |u| = 2|u| = an even number.
- Symmetric: If (u, v) ∈ R3, then (v, u) ∈ R3. If |uv| = |u| + |v| = an even number = |v| + |u| = |vu| → (u, v) and (v, u) ∈ R3. Hence, symmetric.
- Transitive: If (u, v) ∈ R3 and (v, w) ∈ R3, then (u, w) ∈ R3. If |uv| is even, then either both |u| and |v| are even or both |u| and |v| are odd. Accordingly, if |vw| is even, then either both |v| and |w| are even or both |v| and |w| are odd. Hence all u, v and w are of the same parity (either all are even or all are odd). So, |uw| will also be even. Hence R3 is transitive.
So, R3 is an equivalent relation.
The answer will be B and C.
