Answer to Question #267868 in Discrete Mathematics for Jaishree

Question

Show that the relation R consisting of all pairs(x, y) such that x and y are bit

strings of length three or more that agree in their first three bits is an

equivalence relation on the set of all bit strings of length three or more.

Answer 1

Recall that a relation R on a set A is

(i) Reflexive if (a, a)∈ R for all a ∈ A

(ii) Symmetric if (a, b) ∈ R implies that (b,a) ∈ R

(iii) Transitive if (a,b),(b,c) ∈ R implies that (a, c) ∈ R

(iv)An equivalence relation if it is reflexive, symmetric and transitive. 

 Suppose A is the set of all bit strings of length three or more. Define a relation R on A as R = {(x,y)|x and y agree in their first three bits}

Clearly (x,x)∈ R for all x ∈ A. 

Suppose x, y ∈ A, (x,y)∈ R

x and y agree in their first three bits.

y and x agree in their first three bits.

(y,x) ∈ R 

Suppose x, y,z ∈ A,(x, y),(y,z) ∈ R

x and y agree in their first three bits.

And y and z agree in their first three bits.

x and z agree in their first three bits.

(x, z) ∈ R 

Hence, R is reflexive symmetric and transitive on A and therefore, R is an equivalence relation on A.