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.
