Show that the set of all infinite subsets of $\mathbb{N}$ has cardinality greater than $\mathbb{N}$ 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?
 A: 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$.
A: Suppose that $\mathcal{P}(\mathbb{N})$ has a cardinality equal to $\mathbb{N}$. 
That means we can put each set $ \: S_i \in \mathcal{P}(\mathbb{N}) $ in a one to one correspondence with a natural number $\: i $ . Now consider $ J \subset \mathbb{N} $ defined as $ J = \{\: i \in \mathbb{N} \:| \: i \notin S_i \}$ . By construction, $  \forall \: i, \: J \neq S_i$ because comparing with any $S_i \:$, $i$ is in $J$ (by definition) only if it is NOT in $S_i$. Thus, the one to one correspondence is not possible. 
A: Let $\mathcal{I}$ be the set of all infinite subsets of $\mathbb{N}$, i.e. $$\mathcal{I} = \Big\{ A \subseteq \mathbb{N}\  \Big|\  |A| = |\mathbb{N}| \Big\}.$$
Suppose, that $\mathcal{I}$ is countable, i.e. $|\mathcal{I}| = |\mathbb{N}|$, and so, there exist a bijection $f : \mathbb{N} \to \mathcal{I}$. 
Denote by $g_n(S)$ the $n$-th smallest number of $S$ for any set $S \in  \mathcal{I}$ (such number always exists, because $\langle\mathbb{N},\leq\rangle$ is well-founded and $S$ is infinite):
$$ g_n(S) = k \iff \Big|S \cap \{0,1,\ldots,k\}\Big| = n.$$
Now define a non-decreasing sequence $x_n$ and set $X$ of its elements
\begin{align}
x_n &= 1 + \max_{k \leq n} g_n\big(f(k)\big) & \text{ for } n \in \mathbb{N},\\
X &= \{x_n \mid n \in \mathbb{N}\},
\end{align}
and observe, that set by definition of $\mathcal{I}$ we have $X \in\mathcal{I}$. 
Let $\chi = f^{-1}(X)$ and consider
$$
\color{red}{g_\chi(X)} \stackrel{(1)}\geq x_\chi \stackrel{(2)}= 1+\max_{k \leq \chi} g_\chi(f(k)) \stackrel{(3)}\geq 1+g_\chi(f(\chi)) \stackrel{(4)}= \color{red}{1+g_\chi(X)}
$$
where


*

*$x_n$ is non-decreasing, hence $g_k(X) \geq x_k$ for any $k \in \mathbb{N}$,

*definition of $x_n$,

*property of $\max$ for $k = \chi$,

*$f$ is a bijection,


which leads to $\color{red}{g_\chi(X)} \geq \color{red}{1+g_\chi(X)}$, that is, contradiction.
I hope this helps $\ddot\smile$
