I Cantor's diagonal number

FactChecker

Science Advisor
Gold Member
2018 Award
4,868
1,673
First aside: let me reiterate that Cantor's intent was to use Diagonalization on strings, and specifically not on numbers.
Of course, it is also trivial to have the list include both representations of the listed number, both 0.1 and 0.099999.... Then his method would avoid both of those with no trouble.
 
110
15
Of course, it is also trivial to have the list include both representations of the listed number, both 0.1 and 0.099999.... Then his method would avoid both of those with no trouble.
Which is exactly what is accomplished by using strings, instead of numbers, in the first place. :)

But it points out another improperly-taught simplification of the proof. There are several - "strings" v. "numbers" is another - that I claim cause more harm than good.

When presented as a proof by contradiction:
  • It starts by assuming a bijection between ##N## and the example set ##T##.
  • It then uses diagonalization to find an element of ##T## that is not mapped by this bijection.
  • The alleged contradiction is that there can't be an element that is not mapped by a bijection, so the assumption must be false.
  • But this is not the outline of a valid proof by contradition. It doesn't actually use the part of that assumption that says you have a surjection; it just claims that it is contradicted.
  • So, it is actually a direct proof that you can't have a surjection.
The harm that I claim, is that many people will correctly object to assuming the thing that gets contradicted this way. So they feel the proof must be wrong, when all that really happened was that it was explained poorly.
A similar fact that you use, is that diagonalization does not need to assume an injection, either. What it proves is "If ##f(n)## is a function whose range is ##N## and whose co-domain is the set of all binary strings ##T##, then there is a binary string in ##T## that is not mapped by ##f(n)##." This proves that ##T## is uncountable.
 
Last edited:

PeroK

Science Advisor
Homework Helper
Insights Author
Gold Member
2018 Award
9,402
3,431
Which is exactly what is accomplished by using strings, instead of numbers, in the first place.
There's no sense in which "numbers" and "strings" are fundamentally different things. That's a bit like saying "using n-tuples instead of vectors".
 
110
15
There's no sense in which "numbers" and "strings" are fundamentally different things. That's a bit like saying "using n-tuples instead of vectors".
I suggest you look up the definition of numbers. Strings represent numbers, but are mathematically different objects.

Trivial example: "0.4999..." and "0.5000..." are quite different - in the same sense that Cantor uses - strings, but represent the same number in decimal.
 

PeroK

Science Advisor
Homework Helper
Insights Author
Gold Member
2018 Award
9,402
3,431
I suggest you look up the definition of numbers. Strings represent numbers, but are mathematically different objects.

Trivial example: "0.4999..." and "0.5000..." are quite different - in the same sense that Cantor uses - strings, but represent the same number in decimal.
And ##1/2## and ##2/4## represent the same number. But, you don't say: let's use vulgar fractions instead of numbers!
 
110
15
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.
 
Last edited:
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?
 
Last edited by a moderator:
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.
 
Last edited by a moderator:

stevendaryl

Staff Emeritus
Science Advisor
Insights Author
8,400
2,569
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

Staff Emeritus
Science Advisor
Insights Author
8,400
2,569
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.
 
Last edited by a moderator:

stevendaryl

Staff Emeritus
Science Advisor
Insights Author
8,400
2,569
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.
 
Last edited:

Demystifier

Science Advisor
Insights Author
2018 Award
9,861
2,862
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.
 
306
36
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?
 
Last edited:
110
15
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.
 
110
15
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##.
 
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]##.
 
110
15
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

Science Advisor
Gold Member
2018 Award
4,868
1,673
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
 
\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^*## .
 
110
15
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

Science Advisor
Gold Member
1,344
729
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.
 
110
15
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

Staff Emeritus
Science Advisor
Insights Author
8,400
2,569
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.
 

FactChecker

Science Advisor
Gold Member
2018 Award
4,868
1,673
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?
 

Want to reply to this thread?

"Cantor's diagonal number" You must log in or register to reply here.

Physics Forums Values

We Value Quality
• Topics based on mainstream science
• Proper English grammar and spelling
We Value Civility
• Positive and compassionate attitudes
• Patience while debating
We Value Productivity
• Disciplined to remain on-topic
• Recognition of own weaknesses
• Solo and co-op problem solving
Top