# 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?

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

• Can you spell out what $a_{n,1}, a_{n,k}$ are? Feb 26 '14 at 9:18
• What is $b_{n,j}$, then? And $b_n$? Sorry, the notation is somewhat confusing. Feb 26 '14 at 9:36
• That helps, but it's still not entirely clear. I'm mainly lost at the part that says "Now diagonalize by defining $b_n$..." What is $\{b_j\}_{i \leq j < n}$? Feb 26 '14 at 17:53
• If I understand correctly, take any infinite subset $A_i$ of $\mathbb{N}$ and construct a new infinite set $B_i$ such that no two elements in $A_i$ and $B_i$ that are in the same position are equal to each other, and no two elements are the same in $B_i$. How do we know that $B_i$ is not part of the original infinite subsets? Feb 26 '14 at 18:57
• Or is your argument: make a new set $B_i$ that is different from every infinite subset in an assumed 1-1 matching in exactly one position. So if we assume a 1-1 matching, but $B_i$ is different, then there must be more infinite subsets than there are natural numbers. Feb 26 '14 at 19:05

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.

• OP wanted a diagonal argument for the infinite subsets of $\mathbb N$, not so much the proof of Cantor's Theorem for $\mathbb N$. Feb 26 '14 at 9:34

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

1. $x_n$ is non-decreasing, hence $g_k(X) \geq x_k$ for any $k \in \mathbb{N}$,
2. definition of $x_n$,
3. property of $\max$ for $k = \chi$,
4. $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$