I was reading 2 proofs

  • one that the powerset of $ N$ has a higher cardinality than $N$

  • two a proof that the cardinality of the set of all finite subsets of $N$ has the same cardinality than $N$

That made me wonder the difference between these two sets is the set of Infinite subsets of $N$ so how many are there of these, and how do they look?

  • $\begingroup$ Well, you've answered it: the set of finite subsets is countable; the power set is uncountable; therefore the set of infinite subsets is uncountable (with the same cardinality as the power set). $\endgroup$ – mjqxxxx Feb 2 '15 at 1:21
  • $\begingroup$ (Note that the duplicate answers your question on two accounts: the first being the fact that subsets of $\Bbb N$ with the same cardinality are in fact infinite; the second is that every infinite subset of $\Bbb N$ in fact has the same cardinality as $\Bbb N$ so this is actually the same question. Hence my vote to close it as a duplicate.) $\endgroup$ – Asaf Karagila Feb 2 '15 at 5:08
  • $\begingroup$ (I somehow feel that I close a lot of your questions as duplicates. I hope you are not offended, or take it personally. I really have nothing against you!) $\endgroup$ – Asaf Karagila Feb 2 '15 at 6:07
  • $\begingroup$ @AsafKaragila sorry my fault forgot to check for duplicates $\endgroup$ – Willemien Feb 2 '15 at 10:54

$P(N)$ has higher cardinality than $N$. Let $I(N)$ be the set of all infinite subsets of $N$, and $F(N)$ the set of all finite subsets of $N$.

We have $P(N)=I(N) \cup F(N)$.

Let $A,B$ two infinite set, we have $card(A \cup B)= \max(card(A), card(B))$.

So, if $I(N)<P(N)$, as $F(N)=N$ and $N<P(N)$, $P(N)=\max (F(N), I(N))=\max(N,I(N))=I(N)<P(N)$.

There is a contradiction. So $I(N) \geq P(N)$. But, $I(N) \subset P(N) \implies I(N)\leq P(N)$.

So $I(N)=P(N)$

  • $\begingroup$ is P(N) = $\aleph_1$? $\endgroup$ – Daschin Jun 7 '17 at 4:31

Exactly as @mjqxxxx says, you've already practically answered it. The proof is simple. Let $\mathcal{F}=\{E\in\mathcal{P}(\mathbb{N}):|E|<\infty\}$ and $\mathcal{I}=\mathcal{P}(\mathbb{N})\backslash \mathcal{F}$. Suppose to the contrary that $\mathcal{I}$ is countable. Then $\mathcal{I}\cup\mathcal{F}=\mathcal{P}(\mathbb{N})$ is a countable union of countable sets and therefore countable. But, as you mention, $\mathcal{P}(\mathbb{N})$ is uncountable, leading to a contradiction. Therefore $\mathcal{I}$ is uncountable.

What do sets in $\mathcal{I}$ look like? Well, since it is uncountable there is no way to write them all down, but there are several notable examples. It contains for example all co-finite sets, sets of the form $\mathbb{N}\backslash E$ where $|E|<\infty$, but even these are only countable in number. It also includes sets such as the set of all prime numbers. The set of all numbers with a 5 somewhere in their decimal representation, and anything else you can come up with where it is unbounded above.


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