Undergrad Can Cantor's diagonal number solve the issue of infinite lists?

[JeffJo]

And $1/2$ and $2/4$ represent the same number. But, you don't say: let's use vulgar fractions instead of numbers!

Hey, it's much easier to enumerate vulgar fractions. It's even how I choose to do it in an antagonistic "discussion," because there's a simple formula for it. But I call them pairs of integers (m,n) instead of "vulgar fractions." That sounds so, well, vulgar. And while I wouldn't use them in an engineering paper, they can be useful when using a tape measure that is marked off in sixteenths of an inch.

The point is, we can use whatever objects work for the specific purpose at hand. And we can even choose what works more easily, if we want. In diagonalization, it is important to be able to prove that two elements of the candidate set are different. It is a lot easier to show this with strings, and it prevents the use of certain irrelevant arguments.

 

[Flo Tur]

Um, yeah? The result you describe is the reason the proof works?

First aside: let me reiterate that Cantor's intent was to use Diagonalization on strings, and specifically not on numbers. His first proof of the proposition that there are uncountable sets did use numbers. But it made some debatable assumptions about sets of numbers. So he devised a second proof, because (and this is a direct quote from that link) "there is a proof of this proposition that is much simpler, and which does not depend on considering the irrational numbers."​

If used on strings, your question is irrelevant; a string is not "rational" or "irrational." The argument can be used on numbers, but only with the additional step of converting them to strings.

Second aside: "0.25" is not a number. It is a string used to represent a number; in this case, the number we name "one fourth". I know it sounds pedantic to point out the difference, but the property of numbers that you are trying to utilize depends on it. Some rational numbers have two such representations. And I'll point out that since you are relying on two such representations, and only rational numbers have two, the answer to your question should already be obvious.​

To get a "diagonal number" as you call it, there are steps that Cantor didn't need that become necessary. There technically is no such thing - diagonlaization applies to strings. So you mean the number associated with the diagonal string. And to get it, we need to guarantee that any number, rational or irrational, has only one valid string. So we need these requirements in any base B:

• If the number to be converted is rational with a denominator whose prime factors are all prime factors of the base B, then express it as terminating string and append an infinite string of "0"s to it.
• If there is a prime factor of the denominator that is not a prime factor of B, then the representation eventually becomes a repeating string of characters that are not all "B-1".
• If the number is irrational, there is no repetition.

Now we need to make sure that diagonalization will produce a string meeting the same requirements (i.e., not ending with repeating "B-1")s:

• One way (there are many) is to replace each character "C", that isn't an "B-1", with "C+1". And replace "B-1" with "0".
• None of the many similar methods works in binary, so you need a more complicated scheme like stevendaryl's. He was a little terse in explaining the string for every number, even the ones he seemed to skip over, are included in his list. It's not that I think you don't, but I need to ask you if you understand why.

So now the proof you asked for is:

• Let $Q$ be the set of rational numbers in [0,1). It can be put into a list. Assume we have an arbitrary one.
  
• Let $S$ be the set of strings that represent the elements of $Q$. It can be put into a parallel list.
  
• Apply the valid diagonlaization technique to the list of $S$. Call the result a "diagonal string", and name it $d$.
• Trivially, $d$ is not in $S$.
• But $d$ does fulfill the restrictions for our strings. So it can be converted back to a number, $r$.
  
• Since each number has exactly one representation, and $d$ is not in $S$, we know that $r$ is not in $Q$.
• But all rational numbers are in $Q$. So $r$ is not a rational number.

In your logic, replace Q with R. Then, r is not in R?

 

[Flo Tur]

In my opinion, the flaw is here: "Trivially, $d$ is not in $S$". Cantor proved only that for every digit n, the diagonal number is not yet on the list. This is an excelent algoritm to create new numbers, but has noting to do with count-ability. If you count the ordered natural numbers, for every n you reached I can prove that n+1 is not on your list. And I can do this forever, not because N is uncountable, but because is infinite.

 

[stevendaryl]

In your logic, replace Q with R. Then, r is not in R?

The argument starts off: "Let Q be the set of rational numbers in. It can be put into a list."

If you replace Q by R, then the second sentence isn't true, so the rest doesn't follow. Cantor's proof shows that the second sentence isn't true with Q replaced by R.

 

[stevendaryl]

In my opinion, the flaw is here: "Trivially, $d$ is not in $S$". Cantor proved only that for every digit n, the diagonal number is not yet on the list. This is an excelent algoritm to create new numbers, but has noting to do with count-ability.

It is the definition of countability. A set is countable if there is a list that contains every element.

If you count the ordered natural numbers, for every n you reached I can prove that n+1 is not on your list. And I can do this forever, not because N is uncountable, but because is infinite.

The claim is this: If $L$ is a function from natural numbers to reals (that is, for every $n$, $L(n)$ returns a real number), then there is a real number $r$ that is not on the list. Mathematically, that is formalized as follows:

$\forall L\ \exists r\ \forall n\ : r \neq L(n)$

(the quantifiers should actually be restricted quantifiers: forall L of type list of reals, exists r of type real, forall n of type natural, ...)

Your claim about natural numbers is completely different. You're saying for every list of natural numbers, and for every natural number $n$, there exists another natural number, $n'$ such that $n'$ is unequal to every natural number up to index $n$. That's a much more complex statement, which can be formalized as follows:

$\forall L\ \forall i\ \exists n'\ \forall j \leq i : n' \neq L(j)$

These are very different statements.

Here's a way to understand logical statements with alternations of quantifiers. In terms of a two-player game. We have a logical statement of the form:

$\forall L\ \exists r\ \forall n\ : r \neq L(n)$

(The general form is: some number of $\forall$ quantifiers, then some number of $\exists$ quantifiers, then more $\forall$ quantifiers, etc, until you get to the statement at the end, which has no quantifiers)

The first player is trying to make the statement false. We'll call him the falsifier. The second player is trying to make it true. We'll call him the verifier. They take turns playing.

The falsifier picks some list $L$. The verifier gets to inspect $L$ and picks, based on $L$, a real number $r$. The falsifier then picks a number $n$. Then we evaluate the expression $r \neq L(n)$. If it's true, then the verifier wins. If it's false, then the falsifier wins.

We say that a formula is "valid" if there is a strategy such that the verifier can always win, following this strategy. If there is no such strategy, then the formula is invalid.

A simplest case is "For every number, there is a larger number". That can be formalized as:

$\forall n\ \exists n' : n' > n$

Here's the winning strategy: Whatever number $n$ the falsifier picks, the verifier picks a number one higher: $n' = n+1$.

The verifier always wins with this strategy. So it's a valid formula. Similarly, the verifier always wins Cantor's formula:

$\forall L\ \exists r\ \forall n\ : r \neq L(n)$

If you want to show that Cantor's formula is invalid, then you have to play the falsifier, and show that you have a strategy, a way of playing, such that you can beat Cantor's verifier strategy.

 

[stevendaryl]

So in terms of games, the winning strategy for the verifier that "Every list of real numbers omits at least one real number" is Cantor's diagonal strategy.

The statement is $\forall L\ \exists r\ \forall n\ : r \neq L(n)$
(where $L$ is restricted to a function from naturals to reals, $r$ is restricted to be a real, $n$ is restricted to be a natural)
The game plays out by the falsifier picking $L$, the verifier picking $r$, the falsifier picking $n$, then checking whether $r \neq L(n)$.

• The falsifier picks any list $L$. Let $L(m)[n]$ be the $n^{th}$ decimal in the expansion of real number $m$ in the list $L$.
• The verifier picks a number $r$ such that the decimal expansion of $r$ has as its $n^{th}$ decimal: $r[n] = L(n)[n] +1$ (unless $L(n)[n] = 9$, in which case $r[n] = 0$)
• Then whatever natural number $n$ is chosen by the falsifier, the verifier shows that $r[n] \neq L(n)[n]$. That shows that $r \neq L(n)$.

In contrast, how would the game "Every list of natural numbers omits at least one natural number" play out?

The statement is $\forall L\ \exists n\ \forall n'\ : n \neq L(n')$
(where $L$ is restricted to a function from naturals to naturals, $n$ and $n'$ are restricted to be naturals)

The game plays out by the falsifier picking $L$, then the verifier picks $n$, then the falsifier picks $n'$ then checking whether $n \neq L(n')$.

• The falsifier picks the list $L$ where $L(n) = n$.
• The verifier picks a natural number $n$.
• The falsifier picks $n' = n$
• We check if $n \neq L(n')$. That's false. So verifier loses.

 

[Demystifier]

Let me consider the reals between [0;1] and work in binary numeration system.
I order the list like this: first number is 1, second is 0.0, third is 0.10. For the next numbers, the rule is that all the diagonal decimal digits are 0's.

In this way you produce only rational numbers. Your list does not have any single irrational number. The numbers like $\pi$ and $e$ are not on your list.

Cantor's diagonal number will then be 0.111111...=0.(1)=1. So, he failed to produce a number which is not on my list.

Congratulations, you just proved that the set of rational numbers is countable! But this says nothing about the set of real numbers.

 

[SSequence]

Yes, that's a good idea. If we just add one further initial step in the construction (which would basically be modifying the original list L to make a list L' so that L' is guaranteed to contain every rational number) ... then in that case every "digit diagonalisation" would always be guaranteed to work.

=================

Though there are some further subtleties one can consider. Given a certain amount of basic assumptions, the argument certainly shows that we somehow can't "squeeze" ℝ to make a 1-1 correspondence function from ℕ to ℝ.

But if some collection C is too big to be "squeezed" to make a 1-1 correspondence function from ℕ to C, then it does raise the question that shouldn't we distinguish between "surveyable" and "non-surveyable" collections?

 

[JeffJo]

So now the proof you asked for is:

• Let $Q$ be the set of rational numbers in [0,1). It can be put into a list. Assume we have an arbitrary one.
  
• Let $S$ be the set of strings that represent the elements of $Q$. It can be put into a parallel list.
  
• Apply the valid diagonlaization technique to the list of $S$. Call the result a "diagonal string", and name it $d$.
• Trivially, $d$ is not in $S$.
• But $d$ does fulfill the restrictions for our strings. So it can be converted back to a number, $r$.
  
• Since each number has exactly one representation, and $d$ is not in $S$, we know that $r$ is not in $Q$.
• But all rational numbers are in $Q$. So $r$ is not a rational number.

In your logic, replace Q with R. Then, r is not in R?

It doesn't further your point when you ignore some steps. It only suggests that you have already reached a conclusion, and are trying to twist the logic to support it. But recall that my "valid strings" use, for example, 0.5000... instead of 0.4999... . And my "valid diagonalization technique" will never use the digit "9":

• Let $R1$ be the set of rational numbers in [0,1). We don't know if it can, or can't, be put into a list. So assume we have an arbitrary list that may or may not be complete. Call the set that is listed $T$.
  
• Let $S$ be the set of strings that represent the elements of $T$. It can be put into a parallel list.
  
• Apply the valid diagonlaization technique to the list of $S$. Call the result a "diagonal string", and name it $d$.
• Trivially, $d$ is not in $S$.
• But $d$ does fulfill the restrictions for our strings. So it can be converted back to a number, $r$, that is in $R1$.
  
• Since each number has exactly one representation, and $d$ is not in $S$, we know that $r$ is not in $T$.
• But all real numbers are in $T$. So $T$ is not all of $R$.

In my opinion, the flaw is here: "Trivially, $d$ is not in $S$". Cantor proved only that for every digit n, the diagonal number is not yet on the list

You are falling into the trap favored by all Cantor doubters. The trap of confusing how a 9th-grade teacher will demonstrate the comparison on the blackboard for beginning students, with the comparison process that is being demonstrated.

The comparison process is not a sequential one. Since any element of $T$ corresponds to an $n$ in the FULL list (not $n$'s taken in sequence), it necessarily differs from $d$ in position $n$. There are no elements of $TT$ that this statement does not apply to.

This is an excelent algoritm to create new numbers, but has noting to do with count-ability.

Directly? Of course not. That is just one line of the proof.

But look at the first and list lines of that proof. They say "If we have a list of members of $R1$ ... then that list does not include all of $R1$." Since by definition, "countability" means "the entire set can be put into a list," and this proof demonstrates unequivocally that $R1$ can't, it is uncountable.

If you count the ordered natural numbers, for every n you reached I can prove that n+1 is not on your list. And I can do this forever, not because N is uncountable, but because is infinite.

And if the dog hadn't stopped to pee, he'd have caught the rabbit. In other words, inserting a step that is not in the proof (stopping after you "reach" a finite-numbered line in the list) says nothing about the proof itself.

 

[JeffJo]

There was a typo in my last reply, that I can't correct. The part in blue is the correction.

• Let $R1$ be the set of rational numbers in [0,1). We don't know if it can, or can't, be put into a list. So assume we have an arbitrary list that may or may not be complete. Call the set that is listed $T$.
  
• Let $S$ be the set of strings that represent the elements of $T$. It can be put into a parallel list.
  
• Apply the valid diagonlaization technique to the list of $S$. Call the result a "diagonal string", and name it $d$.
• Trivially, $d$ is not in $S$.
• But $d$ does fulfill the restrictions for our strings. So it can be converted back to a number, $r$, that is in $R1$.
  
• Since each number has exactly one representation, and $d$ is not in $S$, we know that $r$ is not in $T$.
• But all real numbers are in $R$. So $T$ is not all of $R$.

 

[Periwinkle]

If I understood what was said, it was agreed that Cantor's diagonal argument would not work if the real numbers were expressed as dual (or also called binary) fractions. However, I looked at Abraham A. Fraenkel's Abstract set theory, North-Holland Pub. Co., 1961, p. 54, writes A. Fraenkel that the method can be applied to the base 2 with minor modifications. The method itself is not described, but at the end of the section, exercise 2 contains this question with a hint.
.................................

Each real number in the interval $(0,1]$ can be on way written as an infinite dual fraction of type $0, c_1c_2c_3…,$ which cannot be such that after some $c_i$ digit only 0 follows. So it can't end with an infinite number of 0s. (The correct way to write the real number.)

We omit $0$ because it cannot be written in this form.

Thus, the finite dual fraction $0.1011$ is represented as an infinite fraction of $0.10101111….$ And here are the other infinite fractions that cannot be written in a finite form. This theorem is explained by mathematical analysis.
.................................

It must be proved that the numbers of the interval $(0,1]$ cannot be listed in a countable sequence. Suppose that it is possible.

$$r_\rm{1} = 0.a_\rm{1,1}, a_\rm{1,2}, a_\rm{1,3}, a_\rm{1,4},…
\\r_\rm{2} = 0.a_\rm{2,1}, a_\rm{2,2}, a_\rm{2,3}, a_\rm{2,4},…
\\r_\rm{3} = 0.a_\rm{3,1}, a_\rm{3,2}, a_\rm{3,3}, a_\rm{3,4}, ...
\\r_\rm{4} = 0.a_\rm{4,1}, a_\rm{4,2}, a_\rm{4,3}, a_\rm{4,4},…
\\......$$
All dual fraction digits in the table are $0$ or $1$. With the diagonal method we take the opposite of the numbers $a_\rm{1,1}, a_\rm{2,2}, a_\rm{3,3},…$. $1$ instead of $0$, but $0$ instead of $1$. In this diagonal number $d$,

$$d = 0.a_\rm{1,1}'a_\rm{2,2}'a_\rm{3,3}'a_\rm{4,4} '...$$
the digits will be different from at least one place (at the diagonal location) of each of the $r_1, r_2, r_3,…$ numbers listed.
.................................

However, it has not yet been shown that the number $d$ is different from each of the numbers $r_1, r_2, r_3,….$ There is no guarantee that this $d$ diagonal number would be represented in the correct way of writing. In this case, despite that, it differs in at least one binary digit from every $r_1, r_2, r_3,…$ number, it would be the same.

The number $d$ would not be written correctly if it would appear as $0, 1011000 ...$ with infinite number $0$ at the end. If this is avoided, the proof is ready.

Let's take the $n_1, n_2, n_3,…,$ infinitely growing sequence of natural numbers. Let's look at the diagonal element of $r_{n_1}$. If the diagonal element of $r_{n_1}$ is $0$, then nothing has to be done with $n_1$, because it is secured on its part the $1$ digit in the diagonal fraction $d$. However, if $r_{n_1}$ has a diagonal element of $1$, then we proceed as follows:

The assumption is that the $r_1, r_2, r_3,…$ sequence contains all the numbers in the interval $(0,1]$. It should therefore also include the number $r$ which is precisely the same as $r_{n_1}$, except that the $n_1$ digit in the fraction is not $1$ but $0$. Therefore, in the above table, the $n_1$ digit of $r_{n_1}$ is replaced by $0$, while $n_1$ of $r$ is replaced by $1$. This secures that the $n_1$ digit of the $d$ diagonal number is $1$.

The above steps are continued for the infinitely growing sequence of $n_1, n_2, n_3,...$ It is achieved that the $d$ diagonal number should not of $0.110100000…$ type, with infinite number $0$ at the end. So it is correctly written, but differs from all the numbers in the table, so we have contradicted the assumption that we would have listed all real numbers in the interval $(0, 1]$.

 

[JeffJo]

If I understood what was said, it was agreed that Cantor's diagonal argument would not work if the real numbers were expressed as dual (or also called binary) fractions.

This diagonalization method:

1. Express every real number in [0,1) as a binary string, with the single restriction that all rational numbers whose denominator is a power of two are represented by your choice of either a terminating string followed by infinite 0's, or as a non-terminating string ending with infinite 1's.
2. Make a list s1, s2, s3, ... of these strings.
3. Extract the diagonal string d.
4. Create a new string by switching 1's for 0's, and vice-versa.

... will not work in Cantor's Diagonalization method. The reason being that you can't prove that the new string satisfies the restriction. But it is entirely possible that one could devise a second restriction that allows such a proof, and I never said otherwise.

I didn't look closely at it, but that appears to be what Fraenkel suggests. Whether or not that is so, it is entirely irrelevant. The elegance of Cantor's Argument is that such machinations are not needed when it is applied to strings, and not numbers.

 

[FactChecker]

The elegance of Cantor's Argument is that such machinations are not needed when it is applied to strings, and not numbers.

I agree. And although different representations of the real numbers might present some technical problems, they are all solvable. The fact remains that, given a reasonable representation of the reals, the proof can be made solid.
"The reals by any other representation would be as numerous." -- Shakespeare

 

[Periwinkle]

\begin{array}{|c|c|c|c|c|c|c|c|}
\hline & a & b & c & d & e & f & g & h & i & .\\
\hline a & \mathbf {*} & & & &X & X & X & & X &. \\
\hline b & & \mathbf {X} & & & & & X & &. \\
\hline c & & & \mathbf {X} & X & & & & & X &. \\
\hline d & & & & \mathbf {X} & & & & & &. \\
\hline e & & &X &X & \mathbf {X} &X & & & &. \\
\hline f & &X & X &X & & \mathbf {*} & & & &. \\
\hline g & & & X &X & X & & \mathbf {*} & & &. \\
\hline h &X & & & & & X &X &\mathbf {*} & &. \\
\hline i & &X &X &X & & & & & \mathbf {X} &. \\
\hline . & . & . & . & . & . & . & . & . & . & .\\
\hline
\end{array}

The diagonal argument in its general form.​

We want to prove that if $A = {a, b, c, d, ...}$ is an infinite set, then it has more subset than the number of elements. Suppose that this is not the case so we would be able to equate $a, b, c, d, ...$ with all its subset exhaustively (illustrated in the rows of the above table, each subset would occur). However, take the elements $A = {a, b, c, d, ...}$ that are not included in the subset corresponding to it. This is the $A^*$ set. (Illustrated where there is no $X$ in the diagonal of the above table.)

..................................
This is definitely a subset of the set $A$, at most the empty set.

The question is, is this $A^*$ set assigned to one of $a, b, c, ...$?

• If it were assigned to an $x^*$ element that is not in the assigned subset, then we get a contradiction because we chose the elements of $A^*$ by taking the elements that are not in the subset that is associated with it. (In the table, if there was no $X$ in the diagonal, we had the item.) However, the assignment shows that $x^*$ should be in $A^*$.
• If $A^*$ were assigned to an $x^*$ element that is included in the assigned subset, then we also get a contradiction because we chose the elements of $A^*$ to exclude the elements that are in the subset assigned to it. (In the table, if the diagonal was a letter $X$, we didn't need the item.) However, due to the assignment, $x^*$ could not be in $A^*$ .

 

[JeffJo]

I'm not sure if the OP is even following this anymore, but the points people want to make seem to be becoming muddled and not addressing the question.

Here is an outline of how Cantor's Diagonal Argument works. Note that only addresses how there must be a cardinality greater than Aleph0. Cantor's Theorem, which seems to be what Periwinkle addressed, is more general.

1. For an appropriate, infinite set T.
2. Let S be any subset, proper or improper, of T that can be put into an infinite sequence S1, S2, S3, ...
3. Define a "diagonalizing algorithm" on set T to be an algortihm such that:
   • The object produced, d, is a member of T.
   • Guarantees that d is different from Sn for every n.
4. If we can define T and a diagonalizing algorithm on T, then T cannot be put into a sequence.
   • Because every possible sequence S necessarily omits a member of T.

Here is the original question:

Let me consider the reals between [0;1] and work in binary numeration system.
I order the list like this: first number is 1, second is 0.0, third is 0.10. For the next numbers, the rule is that all the diagonal decimal digits are 0's. Cantor's diagonal number will then be 0.111111...=0.(1)=1. So, he failed to produce a number which is not on my list.

Like most treatments, this inserts steps into the argument, that the author thinks are trivial and/or transparent. The set T in this passage is not the set of reals in [0,1], which I call R1. It is a set of strings that can be interpreted as members of R1. But numbers are not the same mathematical objects, and the translation between the two sets is not as transparent as some would believe. And it is the translation process that causes the "error" that FLO TUR alleges.

All this accomplishes, is obfuscation of the proof. FLO TUR showed only that inappropriate choices for T and/or the diagonalizing algorithm may not prove the result. That doesn't mean that there aren't appropriate choices that do. They are easiest to show using the choices Cantor actually used: T is teh set of all possible, infinite-length, binary strings. The algorithm selects the diagonal character in each string of the sequence, and inverts it.

 

[TeethWhitener]

Why not start with binary, but subtly do your operations in base 4? Just change two bits at a time such that they don't get changed to 11. So break up
$$a = 0.01110100101011 $$
into pairs of bits, like so
$$a = 0.\text{ } 01\text{ } 11\text{ } 01\text{ } 00 \text{ }10\text{ } 10\text{ } 11$$
and change each pair of bits for a pair from the set $\{00, 01, 10\}$, such that if $a$ is in the first position on your list, you get (e.g.,)
$$a_1 = 0.\text{ } \color{red}{\mathbf{10}}\text{ } 11\text{ } 01\text{ } 00\text{ } 10\text{ } 10\text{ } 11$$
If $a$ is in the second position, you get (e.g.,)
$$a_2 = 0. \text{ } 01\text{ } \color{red}{\mathbf{00}}\text{ } 01\text{ } 00\text{ } 10\text{ } 10\text{ } 11$$
etc. You're still in a binary representation, but you're basically doing operations as if you were in base 4.

 

[JeffJo]

Why not start with binary, but subtly do your operations in base 4?

Why apply it to real numbers at all? Cantor didn't.

It's an elegant proof. Burdening it with unnecessary details diminishes that.

 

[stevendaryl]

Why apply it to real numbers at all? Cantor didn't.

It's an elegant proof. Burdening it with unnecessary details diminishes that.

Well, the point is that the set that people are most interested in is the reals, not the infinite binary strings. They are only interested in the latter because they can be used to represent reals.

But of course, it's pretty simple to see that the cardinality of the reals is equal to that of the infinite binary strings.

 

[TeethWhitener]

Why apply it to real numbers at all? Cantor didn't.

Because that’s what the OP asked about?

 

[FactChecker]

But of course, it's pretty simple to see that the cardinality of the reals is equal to that of the infinite binary strings.

But isn't it critical to show that the example which the diagonal process comes up with is a real number which is not on the list in another form?

 

[stevendaryl]

But isn't it critical to show that the example which the diagonal process comes up with is a real number which is not on the list in another form?

No, my argument is this:

1. Cantor's diagonal argument proves that there are uncountably many infinite binary strings. The binary string "0.01111.." is a different string than "0.1000..."
2. The cardinality of the reals in $[0,1]$ is the same as the cardinality of the infinite binary strings.
3. Therefore, there are uncountably many reals in $[0,1]$

 

[TeethWhitener]

But of course, it's pretty simple to see that the cardinality of the reals is equal to that of the infinite binary strings.

Echoing @FactChecker , it's simple to see that the cardinality of the infinite binary strings is equal to the cardinality of the powerset of the natural numbers. I'm not sure it's so easy to see that the cardinality of the reals is equal to this as well.

 

[stevendaryl]

Echoing @FactChecker , it's simple to see that the cardinality of the infinite binary strings is equal to the cardinality of the powerset of the natural numbers. I'm not sure it's so easy to see that the cardinality of the reals is equal to this as well.

Well, we can split up the infinite binary strings into three sets:

1. $A$ = Those with only finitely many 0s
2. $B$ = Those with only finitely many 1s
3. $C$ = Those with infinitely many 0s and infinitely many 1s

Since sets $A$ and $B$ are countable, and the union $A \cup B \cup C$ is uncountable, it follows that $C$ must be uncountable. But $C$ has a one-to-one correspondence with a subset of the reals in $[0,1]$. So that subset must be uncountable, as well.

 

[jbriggs444]

Or go with Schroeder-Bernstein.

There is an injection⁽¹⁾ from the reals in [0,1) to the binary strings. Just take the canonical decimal expansion of each real.

There is an injection from the binary strings to the reals. Rewrite each 0 as 01, each 1 as 10 and interpret the resulting string as a binary decimal expansion of a real number. By construction, it cannot end in all zeroes or in all ones.

By the Schroeder-Bernstein theorem, it follows that there is a bijection between the reals and the binary strings. QED.

(1): An injection or a "one to one" function maps distinct elements in the domain to distinct elements in the range. No element in the range is re-used.

 

[JeffJo]

Because that’s what the OP asked about?

Oh? Where? The start of the thread was not a question. It was the claim to have found a counterexample to the proof. A counterexample that was based on a misunderstanding that can exist only when the proof is applied to the real numbers.

So, a good reason to not use the real numbers is that these misunderstanding would not arise. I still see no reason to use them. Not even...

Well, the point is that the set that people are most interested in is the reals, not the infinite binary strings. They are only interested in the latter because they can be used to represent reals.

Which came first, the chicken or the egg?

Similarly, which came first, the interest in whether the reals were uncountable, or applying the proof to them because they seem to be a more recognizable set?

Cantor's interest was never about what sets had what cardinalities, it was that he could order the cardinalities of infinite sets.

 

[TeethWhitener]

Well, we can split up the infinite binary strings into three sets:

1. $A$ = Those with only finitely many 0s
2. $B$ = Those with only finitely many 1s
3. $C$ = Those with infinitely many 0s and infinitely many 1s

Since sets $A$ and $B$ are countable, and the union $A \cup B \cup C$ is uncountable, it follows that $C$ must be uncountable. But $C$ has a one-to-one correspondence with a subset of the reals in $[0,1]$. So that subset must be uncountable, as well.

Minor point: this says that the cardinality of the reals is greater than or equal to the cardinality of $C$, not strictly equal. If you're concerned about showing that the cardinality of the reals is greater than the cardinality of the naturals, it's sufficient.

I still see no reason to use them.

Given post #46, I see no reason not to use them.

 

[FactChecker]

The cardinality of the reals in $[0,1]$ is the same as the cardinality of the infinite binary strings.

I agree, but since there are multiple binary strings for some reals, something more must be said to rigorously conclude this. There are simple ways to avoid this issue.

 

[JeffJo]

Circular logic, applied to excepts, doesn't help:

Why apply it to real numbers at all? Cantor didn't.

Given post #46, I see no reason not to use them.

Post #46:

Why not start with binary, but subtly do your operations in base 4? ...[valid demonstration omitted]...

Post #47:

Why apply it to real numbers at all? Cantor didn't.

It's an elegant proof. Burdening it with unnecessary details diminishes that.

[Emphasis added.]

So let me repeat:

1. Cantor's second proof, which is the subject of this thread, was intended to be a proof of "the proposition that there is an infinite manifold, which cannot be put into a one-one correlation with the totality of all finite whole numbers." That's a quote.
   1. All that is needed to prove this is an example set.
   2. Cantor specifically chose to use an example set that wasn't the real numbers. He chose strings.
   3. It is a remarkably elegant proof.
2. It can be applied to the reals in [0,1].
   1. To do so requires transforming the reals into strings, and the strings into reals.
   2. There are complications in doing so that are often not recognized.
   3. So it is less elegant.
3. Nearly every attempt to "disprove" the proof involves those complications.
   1. Using strings as the example invalidates those attempts.
   2. Continuing to use the real numbers allows the authors of those attempts to believe they are right.
   3. AND THIS THREAD IS AN EXAMPLE OF EXACTLY THAT.
4. Still, the complications are surmountable.
   1. Doing so as the initial presentation of the proof adds unnecessary steps that add to the confusion of beginning students (and sometimes students who think they are quite advanced).
   2. But it can done as an addendum once the proof is understood.
   3. As an addendum, it on;ly needs to be done once. It is both more understandable, and easier, to do it in base 10. The students will recognize the applicability, and the diagonalization method is straight forward.

Do you disagree with any of this? Which part?

 

[FactChecker]

I think that there are benefits to using the set of real numbers as an example. The application of the proof to such a familiar object as the real numbers has some appeal. By using the decimal representation of the reals, it is also possible to point out that there are unimaginably more reals than there are natural numbers (and rational, if one wants to show how to count them). It makes it very natural to anticipate the rational numbers having Lebesgue measure zero while the reals have measure 1.

 

[JeffJo]

I think that there are benefits to using the set of real numbers as an example. The application of the proof to such a familiar object as the real numbers has some appeal.

And that application can be pointed out after the proof is understood (see point #4.2). Until then, it gets in the way (see point #3). Evidence: search the internet for people who claim to have disproved it. Start with post #1 of this thread. How many of these claims are based on the parts added to the proof to make it apply to real numbers?

All I am asking, is that you you compare the benefits and detriments.

By using the decimal representation of the reals, it is also possible to point out that there are unimaginably more reals than there are natural numbers (and rational, if one wants to show how to count them). It makes it very natural to anticipate the rational numbers having Lebesgue measure zero while the reals have measure 1.

I really do think this is a chicken v. egg point you make. Experienced people want to see it applied to real numbers because it was first presented to them that way. Not because it helps the inexperienced to understand it. And as I keep pointing out, it gets in the way.