How do you show that $R$ is an equivalence relation and enumerate one bit string from each of the different equivalence classes of $R$?

Question

If $A$ is the set of all bit strings of length $12$. Let $R$ be the relation define on $A$ where two bit strings are related if the first $2$ bits, the $4^{\text{th}}$ bit and the $7^{\text{th}}$ bit are the same.

Answer 1

You show that $R$ is an equivalence relation on $A$ by showing that it is reflexive, symmetric, and transitive. Each of those properties is very straightforward to show. For symmetry, for instance, let $a=a_1a_2\dots a_{12},b=b_1b_2\dots b_{12}\in A$, and suppose that $aRb$. This means that

$$a_1=b_1,a_2=b_2,a_4=b_4,\text{ and }a_7=b_7\tag{1}\;.$$ You want to show that $bRa$, which means that

$$b_1=a_1,b_2=a_2,b_4=a_4,\text{ and }b_7=a_7\tag{2}\;.$$

Does $(1)$ imply $(2)$?

Reflexivity is even easier, and transitivity isn’t much harder; I’ll leave them to you.

There is one equivalence class for each possible set of values of the first, second, fourth, and seventh bits. For instance, one equivalence class of $R$ consists of all of the $12$-bet strings of the form

$$01b_30b_5b_61b_8b_9b_{10}b_{11}b_{12}\;,\tag{3}$$

the bit strings $b_1\dots b_{12}$ that have $b_1=0,b_2=1,b_4=0$, and $b_7=1$. These are all $R$-equivalent. (Why?) And a bit string that doesn’t fit that pattern is not equivalent to any of them. (Again, why?) Those two facts make this collection of bit strings an $R$-equivalence class. To get a representative of that class, fill in the bits $b_3,b_5,b_6,b_8,b_9,b_{10},b_{11}$, and $b_{12}$ arbitrarily; I’d simply set them all to $0$ and take $010000100000$ as my representative of the class described in $(3)$.

Since each equivalence class is determined by the settings of the four bits $b_1,b_2,b_4$, and $b_7$, and each of these bits can be set either to $0$ or to $1$, there are $2^4$ ways to set these four bits and therefore $2^4$ equivalence classes. Bear that in mind when you’re choosing one bit string from each: you should end up with $2^4$ different bit strings.

Answer 2

So $A=\left\{a_1a_2a_3a_4a_5a_6a_7a_8a_9a_{10}a_{11}a_{12}:\forall i\in[12\textbf{]}\left(a_i\in\{0,1\}\right)\right\}$, where $[12\textbf{]}=\{1,2,3,4,5,6,7,8,9,10,11,12\}$.

What you wish to prove is that given $\color{red}{a_1a_2a_3a_4a_5a_6a_7a_8a_9a_{10}a_{11}a_{12}},\,\color{green}{b_1b_2b_3b_4b_5b_6b_7b_8b_9b_{10}b_{11}b_{12}}, \,\color{blue}{c_1c_2c_3c_4c_5c_6c_7c_8c_9c_{10}c_{11}c_{12}}\in A$ you have:

1. Reflexivity: $\color{red}{a_1a_2a_3a_4a_5a_6a_7a_8a_9a_{10}a_{11}a_{12}}$ has its first, second, fourth and seventh bit equal to the same bits in $\color{red}{a_1a_2a_3a_4a_5a_6a_7a_8a_9a_{10}a_{11}a_{12}}$.
2. Symmetry: If $\color{red}{a_1a_2a_3a_4a_5a_6a_7a_8a_9a_{10}a_{11}a_{12}}$ has its first, second, fourth and seventh bit equal to $\color{green}{b_1b_2b_3b_4b_5b_6b_7b_8b_9b_{10}b_{11}b_{12}}$, then $\color{green}{b_1b_2b_3b_4b_5b_6b_7b_8b_9b_{10}b_{11}b_{12}}$ will have its first, second, fourth and seventh bit equal to the same bits in $\color{red}{a_1a_2a_3a_4a_5a_6a_7a_8a_9a_{10}a_{11}a_{12}}$.
3. Transitivity: If $\color{red}{a_1a_2a_3a_4a_5a_6a_7a_8a_9a_{10}a_{11}a_{12}}$ has its first, second, fourth and seventh bit equal to the same bits in $\color{green}{b_1b_2b_3b_4b_5b_6b_7b_8b_9b_{10}b_{11}b_{12}}$ and $\color{green}{b_1b_2b_3b_4b_5b_6b_7b_8b_9b_{10}b_{11}b_{12}}$ has its first, second, fourth and seventh bit equal to the same bits in $\color{blue}{c_1c_2c_3c_4c_5c_6c_7c_8c_9c_{10}c_{11}c_{12}}$, then $\color{red}{a_1a_2a_3a_4a_5a_6a_7a_8a_9a_{10}a_{11}a_{12}}$ will have its first, second, fourth and seventh bit equal to the same bits in $\color{blue}{c_1c_2c_3c_4c_5c_6c_7c_8c_9c_{10}c_{11}c_{12}}$

Can you now do this?