Can someone explain how to find the number of equivalence classes and elements?

Question

I am struggling so much with this topic. Trying to do some practice questions but I don't seem to get it. What I'm working on is

Let $A = \{ 1, 2, 3, \dots, 2014 \} = \{ x \mid 1 \le x \le 2014 \}$. Let $P$ be the set of all non-empty subsets of $A$. Define the relation R on P by: for any $X, Y$ element of $P$, $XRY$ if and only if the largest element of $X$ equals the largest element of $Y$.

(b) List all the elements of the equivalence class $[\{3\}]$ (the equivalence class of $\{3\}$).

(c) How many equivalence classes does $R$ have? Explain.

(d) How many elements does the equivalence class $[\{271\}]$ (the equivalence class of $\{271\}$) have? Explain.

Answer 1

for $[\{3 \}]$ You are looking for all the sets that are subsets of $A$ that have $3$ as their largest element and so

$$[\{3\}] = \{\{1,2,3\},\{1,3\},\{2,3\},\{3\}\}$$

Notice that we don't include the empty set

How many equivalence classes does $R$ have ?

$R$ has $2014$ different equivalence classes, because we have $2014$ different numbers . And actually all these equivalence classes are distinct and they all partition the set $P$

I will let you think about (c) and ask me if you couldn't get it

Just look at the equivalence class of ${3}$ and try to make connections

To make it easier for you consider $$[\{4\}] = \{\{1,2,3,4\},\{2,3,4\},\{1,2,4\},\{1,3,4\},\{2,4\},\{3,4\},\{1,4\},\{4\}\}$$

Now count the elements in the equivalence class of {3} and {4} and try to drive a formula for 271

Answer 2

For (b), you must find all non-empty subsets of $A$ whose largest element is $3$

For (c), consider the function $\max : P \mapsto A$, which takes a subset to its maximum. By definition $X R Y$ iff $\max(X) = \max(Y)$. So every equivalence class corresponds to an element of $A$.

For (d), how may subsets are there that have $271$ as their maximum? If $A$ is such a set, then $A$ is the disjoint union of $\{ 271 \}$ and $B$, where $B$ is an arbitrary subset of $\{1, \dots, 270 \}$.