August 14th, 2016, 03:03 PM  #1 
Senior Member Joined: May 2016 From: USA Posts: 427 Thanks: 171  Question about Cantor's Diagonal Proof
I have recently been given a new and different perspective about Cantor's diagonal proof using bit strings. The new perspective does make much more intuitive, in my opinion, the proof that there is at least one transfinite number greater then the number of natural numbers. First to establish a basic notation. Let T be the set of all possible bit strings of infinite length. Let M be any subset of T. If M can be put into 11 correspondence with the set of natural numbers, the antidiagonal cannot be in M but must be in T. Thus, if M can be put into 11 correspondence with the set of natural numbers, M is not T. But T is a subset of T. Thus, if M is T, T cannot be put into 11 correspondence with the set of natural numbers and so is "larger" than the set of natural numbers. Thus there is at least one transfinite number larger than the number of natural numbers. Fine. Nice and simple and elegant. I hope I managed to get through that without any awful blunder. But it does nothing to show that the real numbers cannot be put into 11 correspondence with the natural numbers. It would not satisfy Zylo for example, or the guy who wanted to represent all real numbers with just one symbol. So the next intuitive step SEEMS to be to prove that the real numbers between (0, 1) can be put into 11 correspondence with T. Based on a different thread, however, I gather that is not how things proceed. Or rather I gather that is not how things must proceed. And I can see how the approach of putting the bit strings into correspondence with the reals gets tricky due to the dual representation problem. You can't just exclude one out of each pair of dual representations because then you are not dealing with T anymore, and we certainly did not prove that no subset of T can be put into 11 correspondence with the set of natural numbers. Please understand: this is not an attempt to say that Cantor is wrong. I am trying to see whether the next step of this of the bit string approach is or is not simpler and more intuitive. Where my mind goes, but maybe I am wrong, is to define T differently so that it is the set of all bit strings of infinite length without infinite repetitions, but I may be sliding a finite thought in there. So the transition to real numbers would actually be to the irrationals. Am I thinking straight? 
August 14th, 2016, 03:54 PM  #2 
Senior Member Joined: Aug 2012 Posts: 832 Thanks: 146 
Yes your proof is clear and correct. You're also right (or at least in agreement with me ) about the pedagogy. It's easier to prove the result for bitstrings and then transfer to reals than to do the proof for the reals first. Most students have a very tenuous notion of the real numbers and "infinite decimals" whatever those are. Then you add the dualrepresentation problem and it's a mess. As you note, the next step is to equivalence the bitstrings to the reals and deal with the dualrep problem. I admit I've always simply accepted the explanation, "The dualreps are countable so it doesn't matter." It might be fun to nail this down once and for all. One technical point. We can formalize "infinite bitstrings" as functions that input a positive integer $1, 2, 3, \dots$ and output $0$ or $1$. That is, an infinite bitstring is a function $b : \mathbb Z^+ \rightarrow \{0,1\}$. For example the string $0101...$ of alternating $0$'s and $1$'s is just a function $b$ with $b(1) = 0$, $b(2) = 1$, $b(3) = 0$, etc. In proofs we'd designate the values of $b$ as $b_1$, $b_2$, etc. The same remarks apply to "infinite decimal" expressions. Everything to the right of the decimal point is just a bit function or bitstring. The formalism is handy when we want to prove things about bitstrings. Last edited by Maschke; August 14th, 2016 at 04:04 PM. 
August 14th, 2016, 05:24 PM  #3 
Math Team Joined: Dec 2013 From: Colombia Posts: 6,354 Thanks: 2085 Math Focus: Mainly analysis and algebra 
The proof is remarkably easy with some supporting results. Let us define $Q'$ to be the terminating bitstrings (or those ending with a string of zeros) and $R'$ the nonterminating bitstrings (or those not ending with a string of zeros). Then there is a 11 mapping between $R'$ and $\mathbb R$, and a 11 mapping between $Q'$ and a subset of the rationals and $$T = R' \cup Q' \qquad \text{and} \qquad R' \cap Q' = \emptyset$$ Now. If $R'$ were countable, $T$ would be the union of two distinct countably infinite sets which would make it countably infinite. But $T$ is uncountably infinite and $Q'$ is countably infinite, so $R'$ must be uncountably infinite. And thus $\mathbb R$ is also uncountably infinite. Last edited by v8archie; August 14th, 2016 at 05:44 PM. 
August 14th, 2016, 06:21 PM  #4  
Senior Member Joined: May 2016 From: USA Posts: 427 Thanks: 171 
Archie Quote:
Quote:
Quote:
Quote:
In fact, it is crucial to the entire argument. So the essence of the argument may be to show that correspondence. Alternatively, you could try to repeat the diagonal argument with set K selected from R'. Quote:
Quote:
Quote:
But thank you sincerely. I am not trying to pick a quarrel here. I am just trying to see how to close the loop. Last edited by skipjack; August 14th, 2016 at 10:15 PM.  
August 14th, 2016, 07:45 PM  #5 
Math Team Joined: Dec 2013 From: Colombia Posts: 6,354 Thanks: 2085 Math Focus: Mainly analysis and algebra  Because only fractions of the form $k \over 2^n$ are terminating strings in the binary representation. Just as only fractions of the form $k \over 10^n$ are terminating decimals. For example: $0.637952385={637952385 \over 10^9}$. It is only numbers that have a terminating representation that have a second, nonterminating representation (decrement the last digit by 1 and add a string of 1s in binary or 9s in decimal). It's another assertion, but hopefully one you can accept. I've been asserting rather than proving for brevity. The 11 mapping between $R'$ and $\mathbb R$ is then guaranteed by the fact (assertion) that every string of digits $(a_1a_2\ldots a_n\ldots)$ following a decimal point is a decimal representation of a real number meaning $\sum \limits_{n=1}^\infty {a_n \over 10^n}$ and (another assertion) that every real number has at least one such representation. Please note the edit of my original sketch of the proof. Last edited by skipjack; August 14th, 2016 at 10:34 PM. 
August 15th, 2016, 12:35 PM  #6  
Senior Member Joined: May 2016 From: USA Posts: 427 Thanks: 171 
Archie I truly am not trying to be an argumentative pain in the ass. I am trying to get my head fully around something that I have long known in a loose fashion. Your followup was quite helpful in that regard, but does not fully satisfy me. (I am not pulling a Zylo.) Quote:
But I can now see that I was being an idiot. You were placing one of the pair from each dual representation into Qprime (not Q) and placing all the rest of the strings in R prime (not R). And it is a snap to put subset Q prime into 11 correspondence with the natural numbers. Quote:
We showed that T, originally defined as the set of all infinite bit strings, has a greater cardinality than the set of natural numbers. You then showed how to interpret T as the set of all real numbers that are (a) in the interval (0, 1) and (b) "representable" by such an infinite bit string. You then proceeded to divide set T into mutually exclusive subsets A and B, where A contains one of the dual representations from each pair of dual representations and B contains all the other bit strings. Great. (I have changed your notation from Q prime and R prime to avoid any psychological hiccups about their relation to Q, the set of rationals, and R, the set of reals.) You now say that there is a 11 correspondence between A (your R') and R. My original question was, in essence, how do we know that. So an assertion cannot satisfy me. But I now think I asked a dumb question. You showed that A has the cardinality of T, which is greater than the cardinality of the natural numbers. And quite obviously A is a subset of R. So R has a cardinality greater than the cardinality of natural numbers. There is absolutely no need to show a 11 correspondence between A and R. This should please Maschke because it leaves open the possibility that there are real numbers that are not "representable" by infinite strings. There is no need to deny or affirm that to prove that the cardinality of the reals exceeds that of the natural numbers. Please feel free to critique. Last edited by JeffM1; August 15th, 2016 at 12:43 PM.  
August 15th, 2016, 01:39 PM  #7 
Math Team Joined: Dec 2013 From: Colombia Posts: 6,354 Thanks: 2085 Math Focus: Mainly analysis and algebra 
That seems OK to me except that I don't think Maschke wants to show that there are any reals that are not representable by infinite binary sequences. $\mathbb R$ can be defined as the completion of $\mathbb Q$ with respect to the metric $xy$. This just means that the limit of any Cauchy (convergent) sequence of rational numbers is in $\mathbb R$. And the infinite binary sequences $\{b_n\}$ have a 11 mapping to sequences $\sum \limits_{n=1}^\infty {b_n \over 2^n}$. So all infinite binary sequences represent real numbers. All real numbers are represented by sequences of the form $\sum \limits_{n=1}^\infty {b_n \over 2^n}$, although I'm not sure how exactly to prove it right now. It seems pretty obvious by the construction of the binary representation. That's clearly not a proof, but it is the sort of "obvious" thing that can be hard to prove  a bit like "1+1=2". Construction of the real numbers Last edited by v8archie; August 15th, 2016 at 02:16 PM. 
August 15th, 2016, 01:45 PM  #8  
Senior Member Joined: Aug 2012 Posts: 832 Thanks: 146  Quote:
In fact JeffJo provided the proof sketch a while back with his X(0) idea. You keep track of which halfinterval a given real number is in; then which half of that interval, and so forth. You end up with a sequence of L's and R's which you can replace by 0's and 1's to get the binary representation of a number. That is a finitelydescribable procedure, but it doesn't count as an algorithm since you have to carry out infinitely many steps. But every real number is the intersection of a countable set of downward telescoping nested closed intervals. If you do the intervals as halves, you get binary. If you do the intervals as tenths, you get decimal. And you always end up with a countable set of pesky dual representations. Last edited by Maschke; August 15th, 2016 at 01:56 PM.  
August 15th, 2016, 02:06 PM  #9  
Senior Member Joined: May 2016 From: USA Posts: 427 Thanks: 171  Quote:
There may well be one; Archie believes that there is. I am certainly not asserting the contrary because I have seen no proof either way. Furthermore, as I think I showed, the assertion is unnecessary to demonstrate that the cardinality of the reals exceeds the cardinality of the natural numbers. I think that is a neat result. If, as Archie thought possible, the proof about capturing all the reals in (0, 1) with bit strings is difficult, skipping that proposition leads to a very simple proof about the cardinality of the reals. You work in bit strings and diagonalize as you and JeffJo suggested. You reinterpret the set of bit strings as binary representations of real numbers in (0, 1) and then dichotomize the set as Archie did. You then show that one of those two sets both has a greater cardinality than that of the natural numbers and is a subset of the real numbers. Done. EDIT: Thanks again for the help getting my mind straight. Last edited by JeffM1; August 15th, 2016 at 02:17 PM.  
August 15th, 2016, 02:15 PM  #10  
Senior Member Joined: May 2016 From: USA Posts: 427 Thanks: 171  Quote:
Quote:
Quote:
In any case, it is not needed for what was to be proved. Oh and thanks again for the help getting my mind straight.  

Tags 
cantor, diagonal, proof, question 
Thread Tools  
Display Modes  

Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Cantor's diagonal proof and the real numbers  zylo  Topology  8  March 31st, 2016 02:00 PM 
Help! Cantor's Diagonal Argument  mjcguest  Applied Math  9  July 25th, 2013 07:22 AM 
Cantor´s diagonal argument  netzweltler  Applied Math  191  November 7th, 2010 02:39 PM 
Counting the reals: Cantor's Diagonal Proof  ch00blet  Applied Math  3  January 12th, 2010 12:50 PM 
Cantor diagonal functions  Barbarel  Number Theory  2  April 10th, 2009 02:59 PM 