Can somebody explain to me Cantor's diagonalization argument? [duplicate]

This question already has an answer here:

Like..can somebody explain this to me as if I was a 5 year old or something? Every explanation I read repeats the same exact thing that I simply do not understand. This is what my book says:

"The real numbers between 0 and 1 can be listed in some order, say, $r_1, r_2, r_3, ...$Let the decimal representation of these real numbers be

$r_1 = 0.d_{11}$$d_{12}$$d_{13}$$d_{14}... r_2 = 0.d_{21}$$d_{22}$$d_{23}$$d_{24}$... $r_3 = 0.d_{31}$$d_{32}$$d_{33}$$d_{34}... r_4 = 0.d_{41}$$d_{42}$$d_{43}$$d_{44}$...

Where $d_{ij}$ is an element of {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}. Then for a new real number with decimal expansion r = $d_{1}$$d_{2}$$d_{3}$$d_{4}... where the decimal digits are determined by the following rule: d_{i} = {4 if d_{ii} does not equal 4, 5 if d_{ii} = 4}. And I'm sorry but..what? What in the world is any of this trying to get at? What is the whole r1, r2, r3 thing even mean? Why do we have to create a "new real number"? What is the point? Why? Why are we doing any of this? I don't understand any of the process behind it and I don't understand how it all leads to the conclusion that the real numbers are uncountable. I have absolutely no idea what is going on here. marked as duplicate by Asaf Karagila♦, user61527, Hanul Jeon, Thomas, Dan RustOct 7 '13 at 1:39 This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question. • Sorry, that's what I meant, I'll edit it right away – FrostyStraw Oct 6 '13 at 23:15 • By "explain this to me as if I was a 5 year old" do you mean that we should start by explaining what the words "countable" and "uncountable" mean, or do you already understand the meaning of those words? If you do, it might help if you explained your understanding of the terms in your question, that would give us a starting point. – bof Oct 6 '13 at 23:26 • What book are your reading? If the discussion of Cantor's theorem begins with the flat statement that "The real numbers between 0 and 1 can be listed . . .", you need to throw it away and get another book. Cantor's point is that the real numbers cannot be so listed. One way to arrange the proof is to assume that such a list can be given, and derive from that a contradiction by showing that the list does not really list all the numbers. This is done by exhibiting some number that was omitted from the given list. – bof Oct 6 '13 at 23:32 • @bof . It explains beforehand for example that the set of odd positive is infinitely countable because it has a one to one correspondence with the natural numbers, which makes sense. Then it explains why the positive rational numbers are countable, which is slightly more confusing but still makes sense. But then the way the real numbers uncountability is explained just seems so much more difficult than the other explanations. Also, it starts by saying "to show that the set of real numbers is uncountable, we suppose the the set of real numbers is countable and arrive at a contradiction" – FrostyStraw Oct 6 '13 at 23:40 • I wish people would get over that silly idea that you can explain everything to a five year old. Math is hard and requires maturity. – Asaf Karagila Oct 7 '13 at 0:08 2 Answers Every argument is argument for something. Cantor diagonal argument is an argument to prove that set of real numbers is uncountable. What is a countable set? Let's say a set is countable if we can start ordering the elements of a set like the first, the second and so on. Formally we have to find a bijection with natural numbers. To prove that reals are uncountable we first assume the contrary, namely that set of reals is countable. Then we have to find a contradiction, rendering the assumption false. To do that we find a real number which is not counted. Cantor diagonal argument construct such a real number which is not counted. So here are the steps: Goal: Set of real numbers is uncountable. Step 1: Assume that the set is countable. This means that the set of real numbers can be written as a set with first element, second element and so on, which is \{r_1,r_2,r_3,\dots\}. Step 2: One way to show that the assumption of step 2 is not possible is to find a real number which is not counted there. How? By Cantor diagonal argument. Suppose that we are going to consider only numbers between 0 and 1. Then the new number is such that it is different from the first number at the first digit, from the second element at the second digit and so on. For instance look at the following:$$ \begin{matrix} 0.& \color{red}9 & 7& 0& 6& \dots\\ 0.& 8 & \color{red}2& 4& 3& \dots\\ 0.& 4 & 5& \color{red}2& 8& \dots\\ 0.& 1 & 2& 5& \color{red}3& \dots\\ \vdots & \vdots & \vdots& \vdots& \vdots& \dots\\ \hline\\ 0.& 8 & 1& 1& 4& \dots\\ \end{matrix}$$You can see that the number is different from all counted numbers and also you can see that it is constructed by using the diagonal elements of counted numbers written as above, hence the nominalization of Diagonal argument. • You don't really need to structure this as a proof by contradiction, and that might be a distraction for the OP. You're essentially proving that given any countable set of real numbers, there is a real number not in that set. No contradiction. – Jack M Oct 6 '13 at 23:47 • @Arash How are you determining what digits each of those numbers are? It just seems like you chose random numbers to put on that little table you made. So are you saying that the number 0.8114 is NOT in the set of real numbers between 0 and 1? – FrostyStraw Oct 6 '13 at 23:59 • I believe he just chose those numbers as examples. His point is that for any set of real numbers, if you go down and across in a diagonal method to select one digit from each of the numbers (the red digits), and then subtract$1$from each of those digits, you will have created a number not in your set, because it differs from every number in the set at at least$1$digit. – user71641 Oct 7 '13 at 0:03 • No, he is NOT saying that the number$0.8114\dots$is not in the set of real numbers between$0$and$1$. That number sure IS in the set of real numbers between$0$and$1$, but it is NOT on the LIST which ALLEGEDLY contained all of those real numbers. That's what he ACTUALLY SAID. What makes you think he's saying that$0.8114\dots$isn't a real number between$0$and$1$? WHERE DID HE SAY THAT? – bof Oct 7 '13 at 0:27 • @bof One little word put in capitals, for emphasis, is not anything like half of the comment being in capitals, bolded, in an aggressive tone. – Jack M Oct 7 '13 at 7:19 The argument is often presented as a proof by contradiction, but it can be presented more directly, which I think makes it a bit clearer: Theorem. Let$f$be any function$\mathbb{N} \to \mathbb{R}$. Then there is some real number not in the image of$f$; that is,$f$is not surjective. Proof. Given$f : \mathbb{N} \to \mathbb{R}$, construct a real number$x$via its infinite decimal expansion; take its$n$th digit$x_n$to be 4 if the$n$th digit of the standard decimal expansion of$f(n)$is 5, and take$x_n$to be 5 otherwise. Now for any$n$, we get that$x$differs from$f(n)$in the$n$th digit of their decimal expansions; so$x \neq f(n)$. So$x$cannot be in the image of$f$.$\square$So there is no surjection$\mathbb{N} \to \mathbb{R}\$; so there’s certainly no bijection, so the reals aren’t countable.

• I was a bit sceptical about the If it's countable, we can "count" it, i.e. make a list of Rs proof, because it seemed to me we could have just build the list the wrong way, and did not find the new number 'r' by chance, which is why I came here. Your use of the surjection aspect of the bijection clears the formal issues of the "make a list" argument. Thank you! – Al.G. Feb 7 at 20:56