Let $\mathscr X$ be the set of all nonempty sub sets of the set $\{1,2,3,...,10\}. $Define the relation $\mathscr R$ on $\mathscr X$ by: for all $A,B \in \mathscr X, A\mathscr RB$ if and only if the smallest element of $A$ is equal to the smallest element of $B$.

(a) find the number of equivalence classes of $\mathbb R$.

(b) find the number of elements in the equivalence class $[\{2,6,7\}]$.

I am thinking this would be the number of subsets containing the element 2 of the set $\{1,3,4,...,10\}$ so it would be $2^9$?

(c) find the number of four-element sets which are elements of the equivalence class $[\{2,6,7\}]$.

Also this would be like choosing a 3-element subset from the set $\{1,3,4,...,10\}$ so ${9 \choose 3}$?

  • $\begingroup$ Is the relation defined if the smallest element of A is equal to the smallest element of B? "The smaller element" doesn't quite make sense to my mind for one. Secondly, is there anything about the size of A and B for the relation? IOW, would {10} be its own equivalence class since it doesn't have any smaller elements than the largest element of X? $\endgroup$
    – JB King
    Apr 10, 2013 at 3:49
  • $\begingroup$ Yes, sorry...fixed it, and nothing regarding the size is mentioned. $\endgroup$
    – user60334
    Apr 10, 2013 at 3:50
  • 2
    $\begingroup$ Your answers to (b) and (c) are almost correct, as is the reasoning behind them, but since the equivalence classes are determined by smallest element, you need to make sure that you exclude $1$. That reduces your $9$’s to $8$’s. $\endgroup$ Apr 10, 2013 at 3:51
  • 1
    $\begingroup$ @BrianM.Scott: Can $1$ be in a set in $[\{2,6,7\}]$? I don't think so. $\endgroup$ Apr 10, 2013 at 3:54
  • 1
    $\begingroup$ The exchange between Brian M. Scott and me should be a big hint for (a). How many possibilities are there for a smallest member? $\endgroup$ Apr 10, 2013 at 4:01

1 Answer 1


Hints to each:

a) Consider looking at the single element subsets and notice how these compare to multi-element subsets in terms of using the equivalence. I suspect it is the cardinality of X that is the answer here but I'll leave it to you to prove that.

b) Would {1,2,3} be in the same class? In this case, 1 is the smallest element while the given set has 2 as its smallest element so it isn't quite that simple.

c) If you fix the error in the previous case this should be relatively easy to see that you are close but not quite right.


You must log in to answer this question.

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