Let $S_n=\{d_1d_2\cdots d_n\mid d_i∈\{0,1\}\text{ for }\,i= 1,2, \dots , n\}$, i.e., the set of binary strings of length $n$. List (in full) the equivalence classes for each of the following equivalence relations on the given
set.
a) On $S_2$, where $aRb$ if and only if the digit $0$ appears the same number of times in $a$ as in $b$.
b) On $S_3$, where $aRb$ if and only if $a$ is either $b$ written in forwards order or $b$ written in reverse order.
c) On $S_4$, where $aRb$ if and only if the sum of the last three digits in $a$ equals the sum of the last three digits in $b$.
For case a) I wrote four equivalence classes the $[00] ,[01], [10], [11]$. But I am not sure if having both $[01]$ and $[10]$ makes sense because their elements will be the same and I know equivalence classes can not have the same elements.
Can someone guide me through this question and how to form equivalence classes? For example in case b) do i have to form 8 equivalence classes? We did not go really in depth in class and I am trying to understand how it works and how can I identify how many equivalence classes are there.
Best Answer
The number of $0$ in the string may be zero, one, or two. Therefore there are three equivalence classes. $${[11]=\{11\}\\ [10]=\{01, 10\}\\ [00]=\{00\}}$$ And indeed, $[01]=[10]$ .
There are $2^3$ strings in $S_3$, of which some begin and end in the same digit, and the remainder do not. The former are palindromes, so are partitioned into equivalence classes of one element (eg $\{010\}$), while the later are partitioned into equivalence classes of two elements (eg $\{011,110\}$).
So count the amount of palindromes, and add half the count of non-palindromes.
Since the digits may only be $0$ or $1$, therefore the sum of the last three digits equals the count of $1$ among those digits.