I Are Some Real Numbers Countable and Others Uncountable?

[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!

 

[jbriggs444]

Banal is not the word I would use!

You minimalist!

 

[sysprog]

Hey, please wait @PeroK, @jbriggs444 used the nonal form "banality", not simply the adjective "banal".

 

[sysprog]

Hey , when we were asked "are real numbers countable", why didn't we just say "well, some of them are, but not all of them are", and leave it at that? -- perhaps that would have been underinformative . . .

 

[phyti]

jbriggs;

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.

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.

Things were looking good up to the red statement.

Always searching for simplicity, here is another graphic.
The sequences remain defined as before and 12 are randomly selected and identified with a line number. Make a copy of a randomly selected sequence from the sample, say 9, and compare to L.
1. If L is complete, result is S9 will differ from all S in L except itself.
2. If L is incomplete, result is S9 will differ from all remaining S in L.
Cantor declares the transformed diagonal p as new, based on (2).
If any 1 of the 12 was removed from L and compared, the result would be (2.).
Thus (2) is not a criterion for a new sequence, since all 12 are members of L. The result in (2) is a property of any set of unique elements. Extending that property to L, p is not new, it is a missing sequence. The verification that p is a new sequence would require a comparison of all its positions, which is not possible. 'All remaining' does not equal 'all'. His interpretation of p as new excludes it from L, and prevents the one comparison that makes L complete. The subtle difference of the one comparison of 0 difference depends on inclusion or exclusion of the sequence used in the comparison.

 

[Hornbein]

Hey , when we were asked "are real numbers countable", why didn't we just say "well, some of them are, but not all of them are", and leave it at that? -- perhaps that would have been underinformative . . .

Very underinformative.

 

[SSequence]

Hey , when we were asked "are real numbers countable", why didn't we just say "well, some of them are, but not all of them are", and leave it at that? -- perhaps that would have been underinformative . . .

I don't quite understand, what do you mean by this specifically? In case you meant to say that some real numbers can labeled as "countable" and others can labeled as "uncountable", then there are some (additional) implicit assumptions involved in it.

For example, specifically think of a model where CH is false and cardinality of real numbers is $\aleph_2$ . Then the statement you wrote makes sense "after" we assume some "reasonable" bijection between the reals and $\omega_2$. Then, in some sense, one could say those reals that are associated with ordinals less than $\omega_1$ are countable while others are uncountable. But I don't know what would be the criteria of assigning the word "reasonable" in that case.

In some cases, there can definitely be some agreement on it. For example, in constructibility, CH is true and the reals have $\aleph_1$ cardinality. In that case, there would usually be only a few candidates for what would constitute a "reasonable" bijection. Usually every computable real (or even every arithmetic real) will be associated with a very very small ordinal in that case [think something like $<\omega^3$ or $<\omega^4$]. But of course the exact specific ordinal depends on fixing a single bijection. There are few more things that can be said on this topic but it will get a bit lengthy (so I have skipped that).

P.S.
It seems that there is one other point that kind of arises from this discussion. Perhaps you had something similar in mind. There should be some reals which would be common to every model of set theory. I wonder whether this notion can be fully formalized in some sense (I don't have enough knowledge/understanding to be certain of the subtleties that could be involved here).

 

[sysprog]

Hey , when we were asked "are real numbers countable", why didn't we just say "well, some of them are, but not all of them are", and leave it at that? -- perhaps that would have been underinformative . . .

I don't quite understand, what do you mean by this specifically? In case you meant to say that some real numbers can labeled as "countable" and others can labeled as "uncountable", then there are some (additional) implicit assumptions involved in it.

For example, specifically think of a model where CH is false and cardinality of real numbers is $\aleph_2$ . Then the statement you wrote makes sense "after" we assume some "reasonable" bijection between the reals and $\omega_2$. Then, in some sense, one could say those reals that are associated with ordinals less than $\omega_1$ are countable while others are uncountable. But I don't know what would be the criteria of assigning the word "reasonable" in that case.

In some cases, there can definitely be some agreement on it. For example, in constructibility, CH is true and the reals have $\aleph_1$ cardinality. In that case, there would usually be only a few candidates for what would constitute a "reasonable" bijection. Usually every computable real (or even every arithmetic real) will be associated with a very very small ordinal in that case [think something like $<\omega^3$ or $<\omega^4$]. But of course the exact specific ordinal depends on fixing a single bijection. There are few more things that can be said on this topic but it will get a bit lengthy (so I have skipped that).

P.S.
It seems that there is one other point that kind of arises from this discussion. Perhaps you had something similar in mind. There should be some reals which would be common to every model of set theory. I wonder whether this notion can be fully formalized in some sense (I don't have enough knowledge/understanding to be certain of the subtleties that could be involved here).

Thanks for all of that elucidative work; I was trying to make a joke, but I think that I'm not especially good at being funny . . .