Need help counting equivalence classes.

Question

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.

Answer 1

(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?

Answer 2

An equivalence relation is a different kind of "equality". In this case, two subsets are "equal" if they share the same smallest element. That's analogous to saying two people are equal if they share the same mother.

Every equivalence relation induces equivalence classes. An equivalence class is a set of objects that are all equivalent to each other. In the people case, all my mother's children are equal, and all your mother's children are equal, etc. In the example you were given, $\{8\}, \{8,10\}, \{8,9\}, \{8,9,10\}$ are all equivalent to each other. Together, they form an equivalence class, because no other subset of $X$ is equivalent to any of them. The equivalence classes for this relation are determined by the smallest elements; hence there are ten equivalence classes.

The number of elements in the equivalence class $\{2,6,7\}$ is the number of subsets of $X$ that: first, contain $2$; and second, all their other elements (if any) are from $\{3,4,5,6,7,8,9,10\}$. The combinatorial tools you've been studying should help you answer that question, and the next one. If it helps, consider the smaller equivalence class above, with four elements: $\{\{8\}, \{8,10\}, \{8,9\}, \{8,9,10\}\}$.