1
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ Please note, for further reference, the $\LaTeX$ editing I did to your question. $\endgroup$ Apr 28, 2015 at 7:26

2 Answers 2

1
$\begingroup$

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

$\endgroup$
6
  • 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, 2015 at 7:45
  • $\begingroup$ You are correct, this is the right formula !! Excellent :) $\endgroup$
    – alkabary
    Apr 28, 2015 at 7:51
  • $\begingroup$ Thank you! Is that always the formula then? $\endgroup$
    – AVC
    Apr 28, 2015 at 7:56
  • $\begingroup$ yes It is the right formula, You are very welcome $\endgroup$
    – alkabary
    Apr 28, 2015 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, 2015 at 7:58
1
$\begingroup$

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

$\endgroup$
3
  • $\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, 2015 at 7:26
  • $\begingroup$ To be precise, the equivalence class of $\{ 3 \}$ has $4$ elements. $\endgroup$ Apr 28, 2015 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$ Apr 28, 2015 at 7:28

You must log in to answer this question.

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