My Math Forum Question about Cantor's Diagonal Proof

 Topology Topology Math Forum

 August 14th, 2016, 03:03 PM #1 Senior Member   Joined: May 2016 From: USA Posts: 997 Thanks: 410 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 1-1 correspondence with the set of natural numbers, the anti-diagonal cannot be in M but must be in T. Thus, if M can be put into 1-1 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 1-1 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 1-1 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 1-1 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 1-1 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? Thanks from Joppy
 August 14th, 2016, 03:54 PM #2 Senior Member   Joined: Aug 2012 Posts: 1,852 Thanks: 511 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 dual-representation problem and it's a mess. As you note, the next step is to equivalence the bitstrings to the reals and deal with the dual-rep problem. I admit I've always simply accepted the explanation, "The dual-reps 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. Thanks from Joppy and JeffM1 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: 7,276 Thanks: 2437 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 non-terminating bitstrings (or those not ending with a string of zeros). Then there is a 1-1 mapping between $R'$ and $\mathbb R$, and a 1-1 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. Thanks from JeffM1 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: 997
Thanks: 410

Archie

Quote:
 Let's say that Tâ€² is all infinite bitstrings with a prepended decimal point.
Not lost yet.

Quote:
 That is, all binary representations of real numbers between zero and one.
That seems plausible although it is not a proof. It would have to be a weird number if it could not be represented by an infinite number of digits. I'd be willing to accept this assertion as an axiom. And I'd be ecstatic if there is a proof (but I probably would not grasp it). I'll take your word for it if there is a proof.

Quote:
 Let us also define Qâ€² to be the terminating binary representations of numbers between zero and one (or those ending with a string of zeros) and Râ€² the non-terminating representations (or those not ending with a string of zeros).
All good so far.

Quote:
 Then there is a 1-1 mapping between Râ€² and $\mathbb R$
This is an assertion rather than a proof. Again it seems plausible. I am not doubting it, but I doubt it should be accepted as an axiom.
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:
 and a 1-1 mapping between Qâ€² and a subset of the rationals
Now I am nit picking. Why "subset of the" rather than the "set of"?

Quote:
 Tâ€²=Râ€² $\bigcup$ Qâ€² and\ Râ€² $\bigcap$ Qâ€²=âˆ… Now. If Râ€² were countable, Tâ€² would be the union of two distinct countably infinite sets which would make it countably infinite.
Yes indeed.

Quote:
 But Tâ€² is uncountably infinite and Qâ€² is countably infinite, so Râ€² must be uncountably infinite.
Again, yes indeed. So my difficulties come down to one or two points, which may just be a result of my ignorance.

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: 7,276
Thanks: 2437

Math Focus: Mainly analysis and algebra
Quote:
 Originally Posted by JeffM1 Why "subset of the" rather than the "set of"?
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, non-terminating 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 1-1 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: 997
Thanks: 410

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 follow-up was quite helpful in that regard, but does not fully satisfy me. (I am not pulling a Zylo.)

Quote:
 Originally Posted by v8archie 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, non-terminating representation (decrement the last digit by 1 and add a string of 1s in binary or 9s in decimal).
Thanks. I should have got that. I think my brain slipped a few cogs because I thought you were trying to place the rationals and irrationals in distinct subsets, Q and R. So I misread "terminating," which made no sense to me in the context of non-terminating strings, as "non-terminating but repeating sequences."

But I can now see that I was being an idiot. You were placing one of the pair from each dual representation into Q-prime (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 1-1 correspondence with the natural numbers.

Quote:
 It's another assertion, but hopefully one you can accept. I've been asserting rather than proving for brevity. The 1-1 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.
I cannot just accept an assertion when it is the crux of a proof. HOWEVER, I now believe that we can show the assertion to be unnecessary. I seem to have just tripped over a variant of the continuum problem. So let me give it a go.

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

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: 7,276 Thanks: 2437 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 $|x-y|$. 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 1-1 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 Thanks from JeffM1 Last edited by v8archie; August 15th, 2016 at 02:16 PM.
August 15th, 2016, 01:45 PM   #8
Senior Member

Joined: Aug 2012

Posts: 1,852
Thanks: 511

Quote:
 Originally Posted by JeffM1 This should please Maschke because it leaves open the possibility that there are real numbers that are not "representable" by infinite strings.
I never asserted any such thing. On the contrary, every real number is representable as as a bitstring (defined as a function from the positive integers to a two-element set).

In fact JeffJo provided the proof sketch a while back with his X(0) idea. You keep track of which half-interval 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 finitely-describable 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: 997
Thanks: 410

Quote:
 Originally Posted by Maschke Every real number is representable as as a bitstring (defined as a function from the positive integers to a two-element set).
Do you have a proof for that assertion?

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 re-interpret 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: 997
Thanks: 410

Quote:
 Originally Posted by v8archie 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.
I was just teasing.

Quote:
 $\mathbb R$ can be defined as the completion of $\mathbb Q$ with respect to the metric $|x-y|$. 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 1-1 mapping to sequences $\sum \limits_{n=1}^\infty {b_n \over 2^n}$. So all infinite binary sequences represent real numbers.
Now I was the one electing brevity. That is what I meant by "And quite obviously A is a subset of R."

Quote:
 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".
I have learned to be suspicious of the "obvious" when it comes to real numbers and the infinite. I agree that it is very hard to conceive how that proposition can be false, but absent citation to a proof, I shall continue to be agnostic.

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 Linear Mode

 Similar Threads Thread Thread Starter Forum Replies Last Post zylo Topology 8 March 31st, 2016 02:00 PM mjcguest Applied Math 9 July 25th, 2013 07:22 AM netzweltler Applied Math 191 November 7th, 2010 01:39 PM ch00blet Applied Math 3 January 12th, 2010 11:50 AM Barbarel Number Theory 2 April 10th, 2009 02:59 PM

 Contact - Home - Forums - Cryptocurrency Forum - Top