How many infinite subsets of N are there anyway?

Question

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?

Answer 1

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

Answer 2

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.