# How many infinite subsets does $\mathbb N$ have?

I attempted to write a derivation of the answer, but was told my mathematics was wrong; please correct me.

The cardinality of $\mathbb N$ is $\aleph_0$.
From this set, we can generate another infinite subset by excluding $1$ element.
There are $\aleph_0$ such possible subsets that can be generated like this.
We can generate an infinite subset by excluding $2$ elements from $\mathbb N$.
There are $\aleph_0 \choose 2$ possible subsets that can be generated like this.

In general, for any $i$ from $0$ to $\aleph_0$ we can generate $\aleph_0 \choose i$ such possible subsets by excluding $i$. To find the total number of possible subsets, we simply sum all the combinations.
$$\sum_{i = 0}^{n} {n \choose i} = 2^n$$

Based on the above: $$\sum_{i = 0}^{\aleph_0} {\aleph_0 \choose i} = 2^{\aleph_0}$$

$2^{\aleph_0} = \aleph_1$
$\therefore$  the number of infinite subsets of $\mathbb N$ is $\aleph_1$.

I realise that I excluded the number of infinite subsets who have infinite complements.

To account for this, merely combine any $k$ $i$ used in the selection above, and exclude all multiples of the products of $i_1*i_2*i_3*...*i_k$.
We have $\aleph_0$ such sets of $i$ with numbers increasing from $0$ to $\aleph_o$.

I didn't consider this when I first wrote it out, and only realised it after. I haven't yet updated my proof to include it. However, this wasn't the problem with my proof; I was told I did "bad mathematics".

• They were right. I think it is possible (and also necessary, if you want to use it) to define binomial coefficients for infinite cardinals, and to prove a generalization of the binomial theorem for them. But it's hardly worth your time. The result follows immediately from the obvious observation that the set of finite subsets is countable. – user436658 Jun 6 '17 at 7:43
• You can't suppose $2^{\aleph_0} = \aleph_1$. – Martín-Blas Pérez Pinilla Jun 6 '17 at 7:47
• Your explanation for infinite subsets that have infinite complements looks strange. Could you maybe explain why you think you can get all subsets this way? E.g. the set of all prime numbers, the set of all numbers with porperty P for any property (for which we know that there are infinitely many such numbers, even if we can't enumerate them),...? – Dirk Jun 6 '17 at 8:43
• I was going to count prime numbers and non prime numbers as two subsets, then work with that. But your argument for Property P (e.g the numbers in the Fibonacci sequence breaks my argument). – Tobi Alafin Jun 6 '17 at 17:17
• @Dog_69, AC is almost universally accepted. CH isn't. – Martín-Blas Pérez Pinilla Feb 3 '18 at 19:34

$\Bbb N$ has $2^{\aleph_0}$ subsets. The number of subsets of size $n$ for any $n$ finite is countable. The union of a countable number of countable sets is countable, so $\Bbb N$ has a countable number of finite sets...
Some of the math you did (plugging cardinalities into the combination function for instance) isn't valid. The function $(n,k)\mapsto {n\choose k}$ takes nonnegative integers as arguments; the expression ${\aleph_0 \choose n}$ is meaningless (if such a thing has been defined and is useful, it's probably the case that you haven't learned about it in your class).
Let $X$ be the set of infinite subsets of $\mathbb{N}$. To prove the claim, note that $\vert \mathscr{P}(\mathbb N)\vert =\mathfrak{c}$. Further, there are $\aleph_0$ finite subsets of $\mathbb N$ (since the set of all finite subsets of $\mathbb N$ is a countable union of countable sets). Therefore, $$\aleph_0+\vert X\vert = \mathfrak c$$ Since $\aleph_0+\alpha=\alpha$ for any infinite cardinal $\alpha$, we have $\vert X \vert = \mathfrak c$.
• The number of finite subsets of $\mathbb R$ should be $\mathfrak{c}$ at least, shouldn't it? – Hyperplane Jun 6 '17 at 7:54
• @Hyperplane: Obviously yes, since already $|\{\{x\}~:~x\in \mathbb{R}\}|=\mathfrak{c}$. – Mundron Schmidt Jun 6 '17 at 8:00