1
$\begingroup$

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?

$\endgroup$
  • $\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
0
$\begingroup$

$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)$

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

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.

$\endgroup$

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