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

Answer:

See proof below

Step-by-step explanation:

An equivalence relation R satisfies

• Reflexivity: for all x on the underlying set in which R is defined, (x,x)∈R, or xRx.
• Symmetry: For all x,y, if xRy then yRx.
• Transitivity: For all x,y,z, If xRy and yRz then xRz.

Let's check these properties: Let x,y,z be bit strings of length three or more

The first 3 bits of x are, of course, the same 3 bits of x, hence xRx.

If xRy, then then the 1st, 2nd and 3rd bits of x are the 1st, 2nd and 3rd bits of y respectively. Then y agrees with x on its first third bits (by symmetry of equality), hence yRx.

If xRy and yRz, x agrees with y on its first 3 bits and y agrees with z in its first 3 bits. Therefore x agrees with z in its first 3 bits (by transitivity of equality), hence xRz.