[Math] Show that the set of all infinite subsets of $\mathbb{N}$ has cardinality greater than $\mathbb{N}$

discrete mathematicselementary-set-theorynumber theory

Is there any way to solve this problem using the diagonalization method? I know there's the proof that uses $\mathcal{P}(\mathbb{N})$ = set of all finite subsets $\cup$ set of all infinite subsets, but I'm trying to solve it using the diagonalization method specifically. I was thinking that we can assume the two have the same cardinality and arrive at a contradiction, but I don't know how to get there. How can we show there has to be some infinite set in the set of all infinite subsets that cannot match 1-1 with a natural number?

Best Answer

Suppose that the set of all infinite subsets (and thus all are countable) of $\mathbb N$ was countable. Suppose thus that $\{A_n\}_{n\in \mathbb N}$ is a list of all the countable subsets of $\mathbb N$, and write $A_n=\{a_{n,1},\cdots, a_{n,k},\cdots \}$. Now diagonalize by defining $b_n$ to be some integer different than $\{b_j\}_{1\le j < n}$ and also $b_n\ne a_{n,n}$ and show that $\{b_n\}_{n\in \mathbb N}$ is not on your list, but it is an infinite subset of $\mathbb N$.