1
$\begingroup$

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.

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

2 Answers 2

0
$\begingroup$

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.

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

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

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .