Question

Let S be the set of bit strings of length no larger than 6, and define an equivalence relation R on S as follows: (x, y) ϵ R if and only if x and y are of the same length. Specify the partition P of S that arises from R.

Answer 1

Denote by $|x|$ the length of a string $x$. Therefore, $(x, y) \in R$ if and only if $|x|=|y|$. Then $|x|\in\{1,2,3,4,5,6\}$ for each $x\in S$. The equivalence class $[x]$ of a bit string $x$ is defined as $[x]=\{v\in S\ :\ (v,x)\in R\}=\{v\in S\ :\ |v|=|x|\}$. Therefore, there are 6 equivalence classes. The partiton $P=\{A_1,A_2,A_3,A_4,A_5,A_6\}$ consist of 6 sets. The set $A_i$ contains all bit string of length $i$ for $i\in\{1,2,3,4,5,6\}.$