0
$\begingroup$

I don't really understand Cantor's diagonal argument, so this proof is pretty hard for me. I know this question has been asked multiple times on here and i've gone through several of them and some of them don't use Cantor's diagonal argument and I don't really understand the ones that use it. I know i'm supposed to assume that A is countable and then find the contradiction to state that it is uncountable. I just don't know how to get there. Also, there's a part B.

Here's part B if you can help:

Prove that P(N) = {X : X ⊆ N}, the power set of the natural numbers, is uncountable by establishing a bijection between P(N) and the set A from part (a).

(HINT: Given X ⊆ N, we can ask whether 1 ∈ X, 2 ∈ X, etc. Based on the true/false results, can you think of a way to define a unique binary sequence to go with each subset of N?)

$\endgroup$
  • $\begingroup$ Where exactly do you get stuck in the diagonal argument? If you can pin down the first step that doesn't make sense, it will be easier for us to help you. $\endgroup$ – Noah Schweber Feb 14 '17 at 20:06
  • $\begingroup$ Okay. The way we did it in class was proving that |$N$| < |(0,1)|, or in other words there does not exist a bijective function between the natural numbers and (0,1). We supposed towards a contradiction that there existed a bijective function f: $N$ --> (0,1) and let f(1)=$x_1$, f(2)=$x_2$, ... Then we listed the elements in (0,1) as follows.... $x_1$ =.$x_11$$x_12$$x_13$... $x_2$ =.$x_21$$x_22$$x_23$... ... and then we said every element of $R$ is on this list exactly once. Next, we supposed the list started like $x_1$=.102536, then $x_2$=.087513 and then $x_3$=.009010 and so on. $\endgroup$ – user21 Feb 14 '17 at 20:12
  • $\begingroup$ Ran out of characters. I got lost around this point. Next, we define the real number y by its decimal expansion as y=.$b_1$$b_2$$b_3$ where each $b_i$ = $x_ii + 1$ if x<8, 7 if $x_ii$ = 8, and 0 if $x_ii$ = 9. This contradicted our assumption. I don't know how though. $\endgroup$ – user21 Feb 14 '17 at 20:16
  • $\begingroup$ Based on your comments, I've tried to address your issue in my answer. $\endgroup$ – Noah Schweber Feb 14 '17 at 20:41
1
$\begingroup$

Suppose $A$ is countable. Then, we will have a bijection:

$1 \to \phi(1)=a= \{a_1, a_2, a_3, a_4,...\}$

$2 \to \phi(2)=b=\{b_1, b_2, b_3, b_4,...\}$

$3 \to \phi(3)=c=\{c_1,c_2,c_3,c_4...\}$

$4 \to \phi(4)=d=\{d_1,d_2,d_3,d_4...\}$

and so on. Now, we're going to build a sequence that is in $A$ and it's not in the list, arriving to contradiction.

Our sequence $x=\{x_1,x_2,x_3,x_4...\}$ is defined this way:

  • $x_1\neq a_1$. That is, if $a_1=1$, then $x_1=0$, and if $a_1=0$, then $x_1=1$.
  • $x_2\neq b_2$.
  • In general, $x_n\neq \phi(n)_n$.

Now, we see that $x\neq a$, because their first terms are different. Now, $x\neq b$ because their second terms are diferent. In general, $x$ cannot be the $n$-th element of the list $\phi(n)$, because its $n$-th term is different from the $n$-th term of $\phi(n)$.

Now, note that there is a biyection between $A$ and $\mathcal P(\mathbb N)$. For each $A\subset \mathbb N$, let us consider the sequence $x$ that satisfies $x_n=1$ if $n\in A$ and $x_n=0$ if $x\notin A$. For example:

  • if $A=\{1,3,5,7,...\}$ then $x=(1,0,1,0,...)$.
  • if $A=\{1,2,3\}$, then $x=(1,1,1,0,0,0,0,0,...)$.

It is clear that this is a bijection between $A$ and $\mathcal P(\mathbb N)$, but $A$ is uncountable, as we proved before.

$\endgroup$
  • $\begingroup$ Why do your elements $a$, $b$, $c$, and $d$ all start off with 0? My professor gave us an example of an element of A which was 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, . . .and so on. So is there any reason all of yours start off with zero, even the $x$? I understand the reasoning behind the proof. $x$$\ne$$a$, $x$$\ne$$b$, $x$$\ne$$c$, and so on. Therefore x isn't on the list. Correct? $\endgroup$ – user21 Feb 14 '17 at 20:36
  • $\begingroup$ Sorry, I misread the question. Let me fix the notation. $\endgroup$ – A. Salguero-Alarcón Feb 14 '17 at 20:39
  • $\begingroup$ Yeah, your proof makes sense and helps me understand Cantor's Diagonal Argument. How does this help me with proving the power set of natural numbers is also uncountable? $\endgroup$ – user21 Feb 14 '17 at 20:48
  • $\begingroup$ I'm going to add it to the answer in a few minutes. $\endgroup$ – A. Salguero-Alarcón Feb 14 '17 at 20:54
  • $\begingroup$ Thanks a lot. I really appreciate the help. $\endgroup$ – user21 Feb 14 '17 at 20:55
1
$\begingroup$

In the comments to your question, you indicate that your professor began by showing that $(0, 1)$ is uncountable. I actually think this is a bad way to start; it will be easier to understand the proof of the uncountability of set of infinite sequences of natural numbers, $\mathbb{N}^\mathbb{N}$.

Why? Well,there is a slight issue in the uncountability of the interval $(0, 1)$ - namely the fact that some reals have two decimal expansions (like $0.1000000...=0.0999999....$) - which forces us to be a little weird (this is the whole "if $x_i(i)<8$ . . ." business).

So let me explain why $\mathbb{N}^\mathbb{N}$ is uncountable. Suppose I have a "counting" of some infinite sequences - that is, a map $f: \mathbb{N}\rightarrow \mathbb{N}^\mathbb{N}$. (I think of $f$ as a list: the first element on the list is $f(1)$, the second is $f(2)$, etc.)

Now I want to build a "missing sequence" - that is, an infinite sequence of natural numbers which is "not on the list" (that is, not in the range of $f$). To do this, it will be enough to build a sequence $s\in \mathbb{N}^\mathbb{N}$ satisfying the following property:

For each $n$, there is some place where $s$ differs from $f(n)$: that is, some $i$ such that the $i$th term of $s$ is different from the $i$th term of $f(n)$. (Remember that $f(n)$ is a sequence.)

Why? Well, if $s=f(n)$ for some $n$, then each of the terms of $s$ and $f(n)$ had better be the same: if the $57$th term of $s$ is $0$, but the $57$th term of $f(n)$ is $5$, they're clearly different sequences!

So how can I do this? Well, I'll define $s$ so that the $n$th term of $s$ is different from the $n$th term of $f(n)$, for each $n$. This will be enough to make $s$ different from each $f(n)$, that is, not on the list.

And this isn't hard to do - just add $1$! For instance, if the first four sequences on my list look like

  • $f(1) = (4, 2, 5, 1, . . .)$,

  • $f(2) = (1, 52, 2, 8, . . .)$,

  • $f(3) = (0, 0, 0, 0, . . . )$,

  • $f(4) = (5, 10, 15, 20, . . .)$,

then my $s$ will begin as follows: $$s = (5, 53, 1, 21, . . .)$$

This $s$ isn't $f(1)$, since the first term of $s$ is different from the first term of $f(1)$. It's not $f(2)$, since the second term is different from the second term of $f(2)$. And so on.

Formally, here's how we define $s$:

$$s(n)=f(n)(n)+1$$

(here "$f(i)(j)$" means "the $j$th term of $f(i)$," so e.g. in my example above $f(1)(3)=5$).

It's clear that for each $n$, the $n$th term of $s$ is different from the $n$th term of $f(n)$; so $s\not=f(n)$ for any $n$. In particular, $s$ is not on the list.

This shows that any listing of infinite sequences of naturals is incomplete - that is, there is no bijection from $\mathbb{N}$ to $\mathbb{N}^\mathbb{N}$.


Now, do you see how to adapt this idea to infinite binary sequences? Note that adding $1$ to each term doesn't work anymore, since if you do that you don't get a binary sequence ($2\not\in \{0, 1\}$). But there's something else you can do . . .

$\endgroup$
  • $\begingroup$ to be completely honest, i think this is above where we are in the class right now lol $\endgroup$ – user21 Feb 14 '17 at 20:43
  • $\begingroup$ @johnie4usc What particularly is above the class? $\endgroup$ – Noah Schweber Feb 14 '17 at 20:43
  • $\begingroup$ We haven't used or defined what $N^N$ is. $\endgroup$ – user21 Feb 14 '17 at 20:44
  • $\begingroup$ @johnie4usc I did that in my answer - it's just the set of infinite sequences of natural numbers. Like $(1, 2, 3, . . . )$. I wanted to use something similar to, but not quite the same as, infinite binary sequences. $\endgroup$ – Noah Schweber Feb 14 '17 at 20:48

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.