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.

  • $\begingroup$ Please note, for further reference, the $\LaTeX$ editing I did to your question. $\endgroup$ – Andreas Caranti Apr 28 '15 at 7:26

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

  • 1
    $\begingroup$ Thank you, I'm trying to see the pattern, could you please help me walk through the thought process? I think maybe that's what my problem is. From what I thought, the number of elements in the class was 2^(total -1) like [{271}] = 2^270 $\endgroup$ – AVC Apr 28 '15 at 7:45
  • $\begingroup$ You are correct, this is the right formula !! Excellent :) $\endgroup$ – alkabary Apr 28 '15 at 7:51
  • $\begingroup$ Thank you! Is that always the formula then? $\endgroup$ – AVC Apr 28 '15 at 7:56
  • $\begingroup$ yes It is the right formula, You are very welcome $\endgroup$ – alkabary Apr 28 '15 at 7:56
  • $\begingroup$ Sorry I meant like, if I were to try to find any equivalence class of any relation, the formula would always be 2^(class element -1)? $\endgroup$ – AVC Apr 28 '15 at 7:58

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 \}$.

  • $\begingroup$ So for b) Let's say I have {1,3} {2,3} {1,2,3} {3} thus there are 4 equivalence classes? and for) then 2^2014? Am I on the right teack? $\endgroup$ – AVC Apr 28 '15 at 7:26
  • $\begingroup$ To be precise, the equivalence class of $\{ 3 \}$ has $4$ elements. $\endgroup$ – Andreas Caranti Apr 28 '15 at 7:27
  • $\begingroup$ It's like in question (d), the elements of the equivalence class of $\{ 3 \}$ are of the form $\{ 3 \} \cup B$, where $B$ is a subset of $\{1, 2 \}$. $\endgroup$ – Andreas Caranti Apr 28 '15 at 7:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.