In the set $\mathcal{P}(\mathbb{N})\setminus \{\emptyset\}$ we define an equivalence relation as: $$X \equiv Y \iff \left( \forall n \in X \ \exists m \in Y \ (m \ge n) \ \land \forall k \in Y \ \exists l \in X \ (l \ge k)\right)$$ I want to consider the cardinality of two equivalence classes: $[\{2\}]_\equiv$ and $[\mathbb{N}]_\equiv$, and the cardinality of the quotient set $(\mathcal{P}(\mathbb{N})\setminus \{\emptyset\})\ / \equiv$. This is a relatively new topic for me. How may I approach this problem?

  • $\begingroup$ first you have to understand when are two elements of power set (or subset of natural numbers) equivalent. If you get a hold of that, you are there. $\endgroup$ – HumbleStudent Jan 10 '17 at 22:10


As HumbleStudent pointed out in the comment, the key is to understand the condition given for equivalence. Here is the hint:

For $X=\{2\}$, the possible $Y$'s can be only $\{1,2\}$ and $\{2\}$. The reason for that is: if $a \in Y$ is such that $a>2$, then it will violate the criterion for equivalence as there is no element in $X$ that will be greater than or equal to $a \in Y$.

This shows that $|[\{2\}]_{\equiv}|=2$.

Can you now deal with $X=\mathbb{N}$?

  • $\begingroup$ So, for $X=\mathbb{N}$, the set of possible $Y$'s is $\mathcal{P}(\mathbb{N})$ and $\lvert [\mathbb{N}]_\equiv \rvert = \mathfrak{c}$? At the same time, the quotient set would have $\lvert (\mathcal{P}(\mathbb{N})\setminus \{\emptyset\})\ / \equiv \rvert = \lvert \mathbb{N} \rvert$. Is this correct? $\endgroup$ – Zelazny Jan 11 '17 at 8:23
  • $\begingroup$ @Zelazny I made a mistake in my comment. The equivalence class of $\mathbb{N}$ will contain every "infinite" subset of $\mathbb{N}$. For example, $\mathbb{N} \equiv \{10, 20, 30, \ldots\} \equiv \{1,23,56,987,\ldots\}$. So the size of this equivalence class will not be $1$ as I indicated in my previous comment. $\endgroup$ – Anurag A Jan 13 '17 at 8:08

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.