[Math] Need help counting equivalence classes.

combinatoricsequivalence-relations

I am having trouble wrapping my head around the concept of equivalence classes. Here is the question:

Let $X$ be the set of all nonempty subsets of the set $\{1,2,3,…,10\}$. Define the
relation $R$ on $X$ by: for all $A, B \in X$ , $ARB$ if and only if the smallest element of $A$ is equal to the smallest element of $B$. For example $\{1,2,3\}R\{1,3,5,8\}$ because the smallest element of each set is $1$.

a) Find and simplify the number of equivalence classes of $R$. Explain.

b) Find and simplify the number of elements in the equivalence class $\{2,6,7\}$. Explain

c) Find and simplify the number of four-element sets which are elements of the equivalence
class $\{2,6,7\}$. Explain.

Thanks.

Best Answer

(a) If $A$ and $B$ are in the same equivalence class $[A]$, the $A$ is related to $B$. That is, $A$ and $B$ have the same smallest element. How many possible smallest elements are there? That is, how many elements are there in $\{1, 2, ... , 10\}$?

(b) Any set which contains $2$ but does not contain $1$ is related to $\{2, 6, 7\}$. How many nonempty subsets can you construct which contain $2$ but do not contain $1$?

(c) How many of the sets from (b) have 4 elements?

Related Question