I Are Some Real Numbers Countable and Others Uncountable?

[sysprog]

Oh and, despite $\mathbb {C}$ having that second dimension, the number of numbers in $\mathbb{C}$ is exactly the same as the number of numbers in $\mathbb {R}$.

It's perhaps startling to some persons that the number of even-numbered integers, or, for example, of integers evenly divisible by 100, is exactly the same as the number of the entirety of integers.

 

[jbriggs444]

Don't we have to sum uncountably infinite numbers of infinitesimals to get away with doing integral calculus?

It's not a sum. It is (in the Riemann definition, roughly) a countable limit of a finite sum divided by a finite count.

 

[sysprog]

It's not a sum. It is (in the Riemann definition) a countable limit of a finite sum divided by a finite count.

Nice.

 

[jbriggs444]

That would beg the question, not whether the measure of an interval (say 3) is a real number, but whether the continuous interval itself (between 5 and 2, but I don't mean "the set of reals between 5 and 2", which is something else).

If you speak of a continuous interval between 5 and 2 and do not mean the set of reals between 5 and 2 then you should say what it is that you do mean.

That would seem to indicate a 1:1 correspondence between a line and a plane, so I'm guessing you mean something else ?

as @sysprog has pointed out, the cardinality of the real line and that of the complex plane are identical. One approach to showing this is to take a point on the complex plane, represent it with coordinates (e.g. a+bi), express the coordinates a and b as decimal expansions, interleave the digits in the expansions to get a new decimal expansion and interpret that new expansion as a real number on the real number line. And vice versa. There are some minor tweaks needed to deal with the multiple representation problem (i.e. the .100... versus .099... problem), but that only crops up countably many times and can be dealt with easily in a Hilbert Hotel fashion. Understanding the proof in outline is easy. Dotting the i's and crossing the t's can be tedious.

 

[S.G. Janssens]

Given the initial post, it bewilders me that a thread like this can run for four pages. I suppose I will start working on a post asking for my flat Earth hypothesis to be scrutinized.

 

[phyti]

forum;,
By persevering on and off for some years, we can now slay the 'diagonal dragon'.

 

[BWV]

forum;,
By persevering on and off for some years, we can now slay the 'diagonal dragon'.

But you cite Wikipedia as a source but fail to actually deal with the construction of the set in the article:

Next, a sequence s is constructed by choosing the 1st digit as complementary to the 1st digit of s1 (swapping 0s for 1s and vice versa), the 2nd digit as complementary to the 2nd digit of s2, the 3rd digit as complementary to the 3rd digit of s3, and generally for every n, the nth digit as complementary to the nth digit of sn. For the example above, this yields:

s1	=	(0,	0,	0,	0,	0,	0,	0,	...)
s2	=	(1,	1,	1,	1,	1,	1,	1,	...)
s3	=	(0,	1,	0,	1,	0,	1,	0,	...)
s4	=	(1,	0,	1,	0,	1,	0,	1,	...)
s5	=	(1,	1,	0,	1,	0,	1,	1,	...)
s6	=	(0,	0,	1,	1,	0,	1,	1,	...)
s7	=	(1,	0,	0,	0,	1,	0,	0,	...)
...
s	=	(1,	0,	1,	1,	1,	0,	1,	...)

By construction, s differs from each sn, since their nth digits differ (highlighted in the example). Hence, s cannot occur in the enumeration.

Based on this theorem, Cantor then uses a proof by contradiction to show that:

The set T is uncountable.
The proof starts by assuming that T is countable. Then all its elements can be written as an enumeration s1, s2, ... , sn, ... . Applying the previous theorem to this enumeration produces a sequence s not belonging to the enumeration. However, this contradicts s being an element of Tand therefore belonging to the enumeration. This contradiction implies that the original assumption is false. Therefore, T is uncountable.

As to your argument relating to a set of random infinite sequences the probability that the infinite diagonal would be equal to any other number in the set is zero - just as the odds would be of drawing any two equal real numbers from some interval

 

[PeroK]

forum;,
By persevering on and off for some years, we can now slay the 'diagonal dragon'.

https://www.math.cmu.edu/~wgunther/127m12/notes/CSB.pdf

 

[Mark44]

forum;,
By persevering on and off for some years, we can now slay the 'diagonal dragon'.

Nope. You didn't perserere quite long enough...

 

[phyti]

But you cite Wikipedia as a source but fail to actually deal with the construction of the set in the article:

As to your argument relating to a set of random infinite sequences the probability that the infinite diagonal would be equal to any other number in the set is zero - just as the odds would be of drawing any two equal real numbers from some interval

The citation is for people who may not be familiar with the subject. A second source is http://uk.geocities.com/frege@btinternet.com/index.htm Copyright © E.D.Buckner 2005, a translation of Cantor's 1891 paper.

As to your argument relating to a set of random infinite sequences the probability that the infinite diagonal would be equal to any other number in the set is zero - just as the odds would be of drawing any two equal real numbers from some interval

Here is a counter example showing probability doesn't constitute a proof.

11111...
01111...
00111...
00011...
00001...

d=11111...
p=00000...

The diagonal d and sequence S1 are both unlimited 1's, which exist in the binary tree, with the complementary sequence of 0's.
If you don't accept the binary tree as containing all possible sequences of 0 and 1, then show me a counterexample, with just the first 4 positions.

 

[jbriggs444]

Here is a counter example showing probability doesn't constitute a proof.

Cantor's proof does not use probability.

If you don't accept the binary tree as containing all possible sequences of 0 and 1, then show me a counterexample, with just the first 4 positions.

You have asserted that the binary tree is "equivalent" to a particular hypothetical complete sequential list of sequences of zeroes and ones. But you have not identified a sense in which it is equivalent.

One sense in which it is inequivalent is that a completed infinite binary tree has no second row.

 

[BWV]

The citation is for people who may not be familiar with the subject. A second source is http://uk.geocities.com/frege@btinternet.com/index.htm Copyright © E.D.Buckner 2005, a translation of Cantor's 1891 paper.
Here is a counter example showing probability doesn't constitute a proof.

11111...
01111...
00111...
00011...
00001...

d=11111...
p=00000...

The diagonal d and sequence S1 are both unlimited 1's, which exist in the binary tree, with the complementary sequence of 0's.
If you don't accept the binary tree as containing all possible sequences of 0 and 1, then show me a counterexample, with just the first 4 positions.

But you claimed in the the paper:

Assume a complete list L of random infinite sequences. Each sequence S is a unique infinite pattern of symbols from the set {0, 1}.

your example is not a random sequence, nor is it a complete list of possible sequences. And the complement of the diagonal (per Cantor) is not in the set

 

[Mark44]

By persevering on and off for some years, we can now slay the 'diagonal dragon'.

@phyti, your attempt in this thread is no better than your earlier attempt in 2007 in this thread -- https://www.physicsforums.com/threads/cantor-diagonal-argument.170316/

 

[phyti]

But you claimed in the the paper:your example is not a random sequence, nor is it a complete list of possible sequences. And the complement of the diagonal (per Cantor) is not in the set

If the sequences are not ordered by any specified pattern, then they are random.
Cantor, nor anyone else can show you a complete infinite list. It's an abstraction that cannot be made manifest for viewing. The ellipsis (...) is supposed to inform you that the data extends without limit.

 

[phyti]

BWV;

p and d are from the pdf example.
The graphic shows how p, the sequence formed from the diagonal d is actually an element of L, yet goes undetected.
Sequence d is a simple alternating symbol beginning with 0.
The complement p is therefore an alternating symbol beginning with 1.
The arrows show the correspondence forward and backward.
Sr can be anywhere in L.
The position x is 1 for d and 0 for p. Sr is truly different from d at x but would have to be compared in all positions to reveal itself as the complement of d.

Cantor ignores the fact that d, being a linear sequence, is also a member of L, and would have to be compared in all positions to reveal itself as such. Also definition of sequences is independent of spatial orientation.
Using the symmetry properties of the binary tree, if p is an element of L, its complement d must also be an element of L.

Cantor interprets p as he constructs it as an additional S missing from L, based on the one position difference with all the remaining S.
For a set of unique sequences, by definition, each must differ from the others by at least one position.
With p excluded from L per his interpretation, it will differ from all S in L, whereas in a complete L with p included, it will differ from all S except one, itself.

An interesting quote from his paper:
"However, there is a proof of this proposition that is much simpler,"

It seems the simplicity became an obstacle, and his focus on differences obscured his vision.
The binary tree representing L, includes all S, thus nothing is missing.
You can follow Cantor's construction in the binary tree to prove d and p are duplicates.

 

[Mark44]

Cantor, nor anyone else can show you a complete infinite list. It's an abstraction that cannot be made manifest for viewing.

Obviously no one can show a complete infinite list, but so what? The assumption is that such a list exists. And for any finite index n, each digit on the diagonal can be changed to generate a new number that is not included in the preceding n elements on the list. Since this process can be performed for any index n, that's sufficient to prove that the "complete" list cannot possibly be complete.

 

[jbriggs444]

If the sequences are not ordered by any specified pattern, then they are random.
Cantor, nor anyone else can show you a complete infinite list. It's an abstraction that cannot be made manifest for viewing. The ellipsis (...) is supposed to inform you that the data extends without limit.

The word you should be groping for is "arbitrary", not "random". There is a very basic proof technique that you seem not to grasp:

If one can prove a statement about arbitrary x without making any assumptions about x then it follows that the statement holds for all x.

Cantor does not have to supply a list. That's your job. His job is to demonstrate that no matter what list of lists you proffer, it will necessarily be incomplete.

 

[BWV]

If the sequences are not ordered by any specified pattern, then they are random.
Cantor, nor anyone else can show you a complete infinite list. It's an abstraction that cannot be made manifest for viewing. The ellipsis (...) is supposed to inform you that the data extends without limit.

and this is a specified pattern that is guaranteed to be incomplete (where is 0101... for example?):

Here is a counter example showing probability doesn't constitute a proof.

11111...
01111...
00111...
00011...
00001...

 

[BWV]

Using the symmetry properties of the binary tree, if p is an element of L, its complement d must also be an element of L.

If 5 (0101) is a member of a set, why should 10 (1010) by default be considered its complement and a member of the set?

 

[PeroK]

If the sequences are not ordered by any specified pattern, then they are random.
Cantor, nor anyone else can show you a complete infinite list. It's an abstraction that cannot be made manifest for viewing. The ellipsis (...) is supposed to inform you that the data extends without limit.

Rather than slaying a dragon, I think you are flailing your sword at fresh air here.

 

[jbriggs444]

If 5 (0101) is a member of a set, why should 10 (1010) by default be considered its complement and a member of the set?

As I understand the "proof", @phyti asserts (without proof) that the proffered list of rows is "equivalent" to the completed infinite binary tree.

By construction, for every left to right path within the binary tree there is a corresponding complementary left to right path within the binary tree such that each symbol along the respective paths are the complements of each other. That is, if you take the path: down, up, down, up, you'll land on 0101 and if you take the path: up, down, up, down, you'll land on 1010.

Possibly I was reading too much sense into the "proof", but I got the impression that the plan was to do a series of 180 degree flips of various sub-trees around their horizontal mid-points, so as to manipulate the tree so that an in-order tree traversal would match the sequence of rows in the sequential list.

The "proof" never reached a point where the question of whether a countable sequence of flips could be adequate for this purpose would arise.

However, since an in-order traversal yields no second path, the plan was always a non-starter. If you go for a pre-order traversal, you have the problem of never finishing the first subtree and, accordingly, never starting the second. If you do a top down traversal, you'll never hit the paths that do not terminate on a node.

No way are you going to be able to traverse a binary tree that contains an uncountable number of paths so as to end up with a countable list of paths. The common thought that leads to the assumption that one can do a countable traversal is the fact that the complete binary tree with an uncountable number of paths has a only a countable number of nodes. So it feels like it should be countably traversable. "I mean, there can only be at most twice as many paths as nodes, right?"

 

[BWV]

Getting above my pay grade, but looks like phyti tried the same question on stack exchange and got this answer:
https://math.stackexchange.com/questions/2277858/representing-real-numbers-in-0-1-with-a-binary-tree

The real numbers in this tree do not correspond to nodes, they correspond to infinite chains starting at the root. There are uncountably many of those.

To prove that, you can mimic Cantor's diagonal argument. If the number of chains were countable you could list them

C1,C2,…C1,C2,…
Now build a chain DD that goes left at level ii (choice 00) when CiCi goes right there (choice 11) and vice versa. Then DD is a chain that's not in the list.There really are more chains than nodes.

(Clever idea, that didn't quite work, as you suspected.)

 

[BWV]

Also from the Wikipedia entry on binary trees, every real number would be a path on the tree

• In the infinite complete binary tree, every node has two children (and so the set of levels is countably infinite). The set of all nodes is countably infinite, but the set of all infinite paths from the root is uncountable, having the cardinality of the continuum. That's because these paths correspond by an order-preserving bijection to the points of the Cantor set, or (using the example of a Stern–Brocot tree) to the set of positive irrational numbers.

 

[Jarvis323]

The binary tree representing L, includes all S, thus nothing is missing.

If you construct a number through diagonalization, you're constructing that from a fictional object. Essentially you're showing that taking this objects existence as an axiom leads to an inconsistent axiomatic system.

The infinite binary tree does include all of the binary sequences, $\{0,1\}^*$. $L$ is a representation of the $\{0,1\}^*$ by assumption for the purposes of contradiction. The existence of the diagonalization constructed number in the binary tree doesn't mean much. Of course it is, because we assumed that. It's that the constructed number isn't in $L$ that matters, which shows $L$ is not a representation of the binary tree. If you want you could try to assign unique indices to the paths in the infinite binary tree, but it won't turn out to be possible.

But actually, I am thinking this might be the essence though of your argument.

You can simply include the compliment of the diagonal of L to L. For example, just reserve a special index 0 to put it in, and start the rest of the list from 1. The problem with this is that you've assumed $L$ exists before diagonalization. Your assumption wasn't that $L\cup d(L)^{\mathsf{c}} =\{0,1\}^*$ And anyway, suppose it were, then you could add the diagonal of that again, and so forth on to infinity. Maybe you could try to define a relation $L_{n+1}=L_n \cup d(L_n)^{\mathsf{c}}$ where $L_0$ equals something, and define an $L_{\infty}$. But what does that even mean, because we already run into a contradiction in constructing $L_1$ if $L_0=\{0,1\}^*$, so anything we do after that exists only in an inconsistent mathematical universe where everything can be shown to be both true and false.

Maybe you could try defining this kind of procedure where you start with an $L_0$ that does exist, and see if that can lead to a list of $\{0,1\}^*$ but you won't be able to do it.

 

[phyti]

forum;

part 1

The set N of natural (counting) numbers enables an ordering by size (cardinality) of finite sets.

Cantor's concept is a set of transfinite numbers that enable a similar ordering by size of infinite sets. He sees this as an extension of the number system, and considers a transfinite set as existing complete at any time, within the abstract world of pure mathematics.

Definition at end of translation:

"[By a "set" we understand any gathering-together M of determined well-distinguished objects m of our intuition or of our thought, into a whole] (Cantor, Beitrage 1895b GG p. 112)"

Ewald, W., From Kant to Hilbert, Oxford 1996.

____________________________________

This explains his goal.

 

[phyti]

forum;
part 2
translation of Cantor's diagonal argument:
From the proposition proved in § 2 there follows another, that e.g. the totality (Gesamtheit) of all real numbers of an arbitrary interval (a ... b) cannot be arranged in the series

w1 w2, …, wv, …

However, there is a proof of this proposition that is much simpler, and which does not depend on considering the irrational numbers.

Namely, let m and n be two different characters, and consider a set [Inbegriff] M of elements

E = (x1, x2, … , xv, …)

which depend on infinitely many coordinates x1, x2, … , xv, …, and where each of the coordinates is either m or w. Let M be the totality [Gesamtheit] of all elements E.

To the elements of M belong e.g. the following three:

EI = (m, m, m, m, … ),
EII = (w, w, w, w, … ),
EIII = (m, w, m, w, … ).

I maintain now that such a manifold [Mannigfaltigkeit] M does not have the power of the series 1, 2, 3, …, v, ….

This follows from the following proposition:

"If E1, E2, …, Ev, … is any simply infinite [einfach unendliche] series of elements of the manifold M, then there always exists an element E0 of M, which cannot be connected with any element Ev."

For proof, let there be

E1 = (a1.1, a1.2, … , a1,v, …)
E2 = (a2.1, a2.2, … , a2,v, …)
Eu = (au.1, au.2, … , au,v, …)
………………………….

where the characters au,v are either m or w. Then there is a series b1, b2, … bv,…, defined so that bv is also equal to m or w but is different from av,v.

Thus, if av,v = m, then bv = w.

Then consider the element

E0 = (b1, b2, b3, …)

of M, then one sees straight away, that the equation

E0 = Eu

cannot be satisfied by any positive integer u, otherwise for that u and for all values of v.

bv = au,v

and so we would in particular have

bu = au,u

which through the definition of bv is impossible. From this proposition it follows immediately that the totality of all elements of M cannot be put into the sequence [Reihenform]: E1, E2, …, Ev, … otherwise we would have the contradiction, that a thing [Ding] E0 would be both an element of M, but also not an element of M.

http://uk.geocities.com/frege@btinternet.com/index.htm Copyright © E.D.Buckner 2005
____________________________________
The red denotes:
My argument is not about any number system, but the diagonal method itself
and the elements can be anything, as noted in part 1 as
"well-distinguished objects m of our intuition or of our thought,"

comments to me:

"your example is not a random sequence, nor is it a complete list of possible sequences."

It is as random and complete as Cantor's example above.
Cantor wants to compare an infinite set N to a transfinite set. The list is a prop.

 

[phyti]

forum;

part 3

comments to me:

"One sense in which it is inequivalent is that a completed infinite binary tree has no second row."

This is an abstract 'tree' showing connectivity of its elements according to some form of order. It has no leaves and bears no fruit.
L begins in position 0 with no selection made. L contains itself in an endless loop. At each branch, the selection is from L, 0 or 1. Cantor's method is not unique. The tree is also a history of coin tosses. Rotation 180° of the binary tree is only to show the symmetry of the sequences with a symbol exchange and is not part of the process.
There were no computers in 1890, thus Cantor would not have thought in terms of a binary tree.
My challenge is still, form a sequence of a few positions not in the binary tree.

"Each sequence S is a unique infinite pattern of symbols from the set {0, 1}."

There seemed to be some confusion with this notation, so a revision to (0 or 1).

"your example is not a random sequence, nor is it a complete list"

Cantor wants to show there are more elements in a transfinite set than the set N.
He thinks if he can construct an additional element for his infinite list assumed to be complete, then it is not countable using the infinite set N, and requires a transfinite set.
The diagonal method is in question.

"The word you should be groping for is "arbitrary", not "random"."

random:
statistics equally likely: relating or belonging to a set in which all the members have the same probability of occurrence
synonym:
chance, accidental, haphazard, arbitrary, casual, unsystematic, hit and miss, indiscriminate, unplanned, unintentional
Computer programming and spreadsheets have a random function to generate random numbers.

 

[phyti]

forum;

Thanks for the Q&A session. It was valuable constructive criticism.
As the author, you can't know if the reader interprets the contents as intended.
Feedback is needed to correct errors, clarify, simplify, add detail, etc.
In Cantor's diagonal argument, the difference in interpretation is so subtle, it's the most difficult part to explain. Hopefully the revised pdf does this in section 3. the error.
The explanation of the binary tree to BWV by jbriggs was almost correct, and maybe he will see the difference.

 

[jbriggs444]

forum;

Thanks for the Q&A session. It was valuable constructive criticism.
As the author, you can't know if the reader interprets the contents as intended.
Feedback is needed to correct errors, clarify, simplify, add detail, etc.
In Cantor's diagonal argument, the difference in interpretation is so subtle, it's the most difficult part to explain. Hopefully the revised pdf does this in section 3. the error.
The explanation of the binary tree to BWV by jbriggs was almost correct, and maybe he will see the difference.

Oh no. I get it. I am gobsmacked by the banality of it all.

The proof structure itself is the guaranteed fail. Let me try to summarize the proof in a more mathematically understandable fashion.

The document begins with an outline of Cantor's diagonal proof in proof by contradiction form.

Cantor wants to prove: "No countable list of countably infinite binary sequences can be complete"

Proof:

Assume the opposite. That is, assume the hypothetical: "some countable list of countably infinite binary sequences is complete.
Let L be such a complete list.
Construct a sequence by taking the complement of a diagonal through L
Make the trivial observation that this sequence cannot match any of the sequences in L
Conclude that L was incomplete.
But this contradicts the supposition that L was a complete list. We have a contradiction.
Complete the proof by contradiction. The negation of the hypothetical has been proven. No list of countably infinite binary sequences is complete.

@phyti attempts to argue with this proof. He does so by attempting to show that the conclusion arrived at within the context of the proof by contradiction is contradicted.

You know what happens when you arrive at a contradiction within the scope of a proof by contradiction, right?

If we examine the guts of the attempted disproof, everything turns out to be justifiable, albeit overly complicated.

The demonstration that the sequence L is "equivalent" to the binary tree goes through just fine. The binary tree contains all infinite sequences by construction. L contains all infinite sequences by the hypothetical. So the set of sequences in L does indeed match the set of paths through the binary tree. The two are "equivalent" in this sense.

For every path in the binary tree, the complement of that path is in the binary tree. Yep, that's true enough.

The sequence d taken from the diagonal of L is present in the tree. Yes. The sequence p which is the complement of that is also present in the tree. Yes. That means that the sequence p is present in L. Even though Cantor's construction guarantees that the sequence p is not present in L.

All of this follows correctly -- from the hypothetical that a complete list L even exists.

So at this point we have correctly concluded both that p is present in L and that p is not present in L.

But wait. That hypothetical. It was a hypothetical. In a proof by contradiction. We've arrived at a contradiction. Which means that the hypothetical is disproven.

So @phyti has come up with a needlessly complex proof of Cantor's theorem.

Edit: Cantor also has a direct version of his proof. Instead of starting with an assumption that L is a complete list, one just let's L be an arbitrary list and then demonstrates that it is incomplete.

In this case, the assertion that the binary tree is "equivalent" to the list L does not go through. It cannot be proven and can, in fact, be disproven.

 

[PeroK]

Banal is not the word I would use!