# How can I identify how many equivalence classes are there?

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.

• In part (a), the equivalence classes are $[11], [01] = [10], [00]$ since elements of the equivalence classes have $0$, $1$, and $2$ zeros, respectively. Mar 12, 2020 at 21:41

a) On $$S_2$$, where $$aRb$$ if and only if the digit $$0$$ appears the same number of times in $$a$$ as in $$b$$.

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]$$ .

b) On $$S_3$$, where $$aRb$$ if and only if $$a$$ is either $$b$$ written in forwards order or $$b$$ written in reverse order.

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.

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$$.

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.

• Palindromes are words (or sentences, strings, etc.) that are spelled the same forwards and backwards. Mar 13, 2020 at 2:33

$$S_n$$ has $$2^n$$ elements.
An equivalence class is a subset of the set of given elements.

Two elements belong to the same equivalence class iff they are in the given relation.

So, for part a), the equivalence classes are $$\{00\},\ \{01,\,10\},\ \{11\}$$.

For part b), they are $$\{000\},\ \{001,\,100\},\ \{010\},\ \{011,\,110\},\ \{101\},\ \{111\}$$.