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
$\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 '14 at 9:18
  • 1
    $\begingroup$ What is $b_{n,j}$, then? And $b_n$? Sorry, the notation is somewhat confusing. $\endgroup$ Feb 26 '14 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 '14 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 '14 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 '14 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 '14 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$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.