4
$\begingroup$

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?

$\endgroup$

3 Answers 3

3
$\begingroup$

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

$\endgroup$
7
  • 1
    $\begingroup$ Can you spell out what $a_{n,1}, a_{n,k}$ are? $\endgroup$ Feb 26, 2014 at 9:18
  • 1
    $\begingroup$ What is $b_{n,j}$, then? And $b_n$? Sorry, the notation is somewhat confusing. $\endgroup$ Feb 26, 2014 at 9:36
  • 1
    $\begingroup$ 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}$? $\endgroup$ Feb 26, 2014 at 17:53
  • 1
    $\begingroup$ 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? $\endgroup$ Feb 26, 2014 at 18:57
  • 1
    $\begingroup$ 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. $\endgroup$ Feb 26, 2014 at 19:05
0
$\begingroup$

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.

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

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$

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .