Another Cantor Crank: Representation vs. Enumeration

I don't think any mathematicians would call Cantor's diagonal a "constructive" proof. It only constructs something if there were already the list of real numbers to work with, and the whole point is to prove that that list doesn't exist.

Mark, you forgot to put 0 below each node in the tree.

If you do, another problem in his proof appears: there are an infinite number of equivalent representations of any value that DOES show up in his tree: 0.5, 0.50, 0.500, etc.

Ignore the decimal point for a minute, so that nodes represent naturals. He can't even show the identity isomorphism in the naturals using this approach as he's introduced an infinite number of representations of each member!

In fact he's showed that the decimal representations of the naturals have a higher cardinality than the naturals themselves, which directly contradicts his point. Whoops!

Typo:

"...there's a one-to-one correspondence between nodes of the infi To see the..."

Third last paragraph.

@1 John Armstrong:

Cantor's diagonalization proof is definitely a constructive proof. It explicitely constructs a counter-example for any given supposed bijection between the naturals and the reals.

Constructive proofs just require that the law of the excluded middle isn't used. Cantor's proof doesn't use the law of the excluded middle. A non-constructive proof would demonstrate that a counter-example must exist because if one didn't exist, some other law would be violated. Diagonalization, however, explicitely constructs the counter-example, making it a constructive proof.

Nate, try running it past an intuitionist and see if they're willing to accept it. I don't think they are.

Thinking deeper, there's something interesting going on here. We all know that if d is the cardinality of the natural numbers, and c is that of the continuum, then c=2^d. So -- in a sense -- the authors have packed "exponentially more" things into a tree than into a list, and then not realized that a list can't hold it all.

I wonder if there's a strong parallel to the way that data structures like binary search trees are "exponentially more efficient" at tasks than lists are.

You're incorrect about the tree being uncountable. The tree is countable, because you can enumerate all the nodes. That's part of the 'but that sounds correct!' appeal of the proof.

The tree doesn't work for the other reason you mentioned: it doesn't contain any of the non-terminating-in-base-10 reals. All of its nodes point to a terminating real. To make this obvious, consider: every node, except 0, has a parent node. What is the parent node of pi?

To be honest, I wouldn't call Cantor's diagonalisation really a proof by contradiction, since you never use the bijective property of f. Given any f : N -> R one can construct an x in R which is not in the image of f. Therefor no bijections from N to R exist.

Although I know very little about intuitionism, I think an intuitionist will accept an explicitly constructed counterexample such as this.

He doesn't understand proof by contradiction.

From the knol "Wrong. Proofs by contradiction are valid if the assumption is known to be false."

So any further discussion is wasted.

@6:

The tree, extended to infinity, is uncountable.

In some ways, the construction reminds me of surreal numbers. Just like in the surreals, In the tree construction, you can assign each number a "birthday" which is the ordinal of the construction step in which it was first possible to represent it.

The tree doesn't contain all of the reals until the ωth birthday - that is, until after an infinite number of steps. At that point, just like the surreals, it will contain all of the real numbers, but it will no longer be countable.

Before the ωth birthday, the tree is finite, and will always have a countable number of nodes. After ω construction steps - that is, when the tree is extended to infinity, in has an uncountably infinite number of nodes.

But be careful, Robert, about exactly what is being proven.

Okay, to be more explicit: this is an explicit construction which takes a function f:N->R and gives a number r which cannot be in the image of f. That's as far as "explicit construction" goes.

The overall theorem is that an object having certain properties does not exist, and you cannot give a construct something that doesn't exist.

Last line should have cut out "give a". Would edit myself if I could.

It appears this crank does not know the distinction between nodes and paths. There are countably many nodes but uncountably many paths!

The tree, extended to infinity, is uncountable.

The tree, as you seem to have defined it, is already infinite and has a countable number of nodes. What do you mean by extended to infinity?

This same author (John Gabriel) has a few other nuggets of poor math perception:

- http://knol.google.com/k/john-gabriel/there-are-no-infinitesimals/nz742…
- http://knol.google.com/k/understanding-vectors#

Basically, he contends that he and he alone truly understand how math works and that most mathematicians are completely wrong.

@ #10
> (The overall theorem is that an object having certain properties does not exist, and you cannot give a construct something that doesn't exist.

Mappings from N to R exist. Cantor does not assume that bijective mappings exist, his proof merely shows that no valid mapping from N to R can possibly be surjective. He constructs a counterexample to any *claim* of a surjection and shows that it is merely an injection. So what he has constructed is very much real, and it is based on something that itself is real.

Wow! This particular Cantor crackpot not only fails to understand the nature of proof and of the real numbers (though my adviser, a topologist, quipped to the department chair, an analyst, that "theorems" in analysis were merely conjectures, counterexamples for which had yet to be found), but he exhibits the paranoia of the 9/11 truthers and the birthers.

The the interesting cranky objections to Cantor's argument are the "well I'll just tack the Cantor constructed number on to the list." I sometimes when teaching students ask them why this doesn't work. It does give them a better feeling for the proof (especially in regard to the constructive nature of the proof).

An objection I've seen only once was someone who created what amounted to a strawman of Cantor's argument by looking at it in base 2 and then noting how it breaks down there. I was unable to persuade the individual that any other base would work and it only needed to work in a single base.

The try-to-list-them-all is I think the most common and by far least interesting approach by cranks.

I did once see a website where a guy claimed that Cantor's work was part of a plot against God by atheists. He apparently also thought that measuring different infinities was akin to building the Tower of Babel. Unfortunately, a quick google search doesn't turn up the website in question.

I have to agree with Strilanc, extended to infinity, the nodes are countably infinite. They can be enumerated breadth first. In fact, I would be somewhat confident to say that any thing that can be put into a tree is countably infinite. Only problem here is that the reals cannot be put into a tree.

John, to elaborate on B-Con's comment: The statement "There is no onto function f: N -> R" is, as you note, proved by contradiction. That's actually okay, because the statement is explicitly negative. It's proofs-by-contradiction for positive existence statements that give intuitionists the jibblies. In general, "not A" is interpreted by constructivists as "there is a procedure for transforming proofs of A into proofs of contradictions", and that certainly exists here, given a proof of the statement "For every f: N -> R, there is an x in R which is apart from f(n) for every n in N".

Jorde @ 17:

any thing that can be put into a tree is countably infinite

Not quite. A node of a tree could have uncountably many branches, for instance.

But I agree with you that Mark's putative tree with uncountably many nodes does not exist.

"Cantor's argument is a classic proof by contradiction."

I don't think so. In a "classic" proof by contradiction, the negation of the conclusions should be assumed to be true, and a contradiction derived.

In Cantor's proof, he does not assume that there is a bijection from N to R. He just shows that any function from N to R is not a bijection. This is more a "classic" example of "universal generalization" or using sufficiently arbitrary assumptions.

This makes Cantor's proof constructive because it shows how to find the element of R missed by a function from N to R.

If Cantor used a proof by contradiction and assumed that there was a bijection from N to R, you would not be able to use it (directly) to construct the counterexample because the construction would only apply to functions that ARE bijections. In order to find the counterexample you would have to restate the proof (or the construction) in a "sufficiently arbitrary" way to allow it to apply to a given (or any) function. This sufficiently arbitrary way is exactly the classic universal generalization proof.

@10 - You can look at Cantor's proof as showing that something does not exist. But it can also be understood as showing that a certain type of thing does not have a certain property (functions from N to R are not bijective). And you can take it to mean that a certain type of thing HAS a certain property (function from N to R have the property of missing an element of R).

It's actually cool that the tree has countable number of nodes but uncountable number of paths from top down.

Intuitionists and other constructivists accept diagonalization proofs that the real numbers are uncountable.

I know I'm asking for trouble by posting this, but:

Naturals go off to infinity in two directions. Reals go off to an infinite of infinities (at both ends, but also between each number). Looking only at the positive half, the question can possibly be rephrased as "can you find a reliable complete traversal through an infinite number of infinite sets". My first guess was no, but once I thought about it for a while I realized that you can always, at each iteration, force a finite pass through a growing number of infinite paths. That is, if at each iteration, you traverse a finite number of finite sets (limited arbitrarily), then adding an infinite number of them slowly for infinity effectively "serializes" the traversal (it will eventually visit all of the elements). Or in simpler terms, I think that an infinite number of infinities, is mappable to a single infinity from a traversal perspective. This showed up when I was playing with prime numbers:

http://theprogrammersparadox.blogspot.com/2009/11/prime-perspectives.ht…

Of course, not wanting to get added to the list of Internet crazies (yet), I'm perfectly willing to admit that this is wrong (are there different types of multiple infinity sets?). If it is, I'd really like to know why because this has a wider range of implications then just Cantor and primes.

Paul.

interesting stuff. entertaining quackery.

My question: why were the easier phrases "one-to-one" and "onto" replaced by the bourbaki-isms "injection" and "surjection"? Are we better off with the uglier words?

With respect to my earlier comment:

http://theprogrammersparadox.blogspot.com/2009/12/quickie-infinite-sets…

shows a simple mapping, why isn't this usable for R -> N?

@Paul: The algorithm described there works for mapping the union of a countable number of countable sets to a single countable set.

@Anonymous: So the question is, whether or not reals are just an infinite number of infinite sets. I see them, that way, but I could be wrong. I see it as for any two member of the real numbers, A and B, there are an infinite number of other numbers between them. Which can be expressed as:

..., A, ..., B, ...

And the "in between infinities" can all be tied back to the number on the left (particularly if we only tackle half the space at a time). That (to me) sets it as the set I described in my post. Wrong?

Paul.

Paul: There's more to the reals than infinities "at both ends, but also between each number". We can do that with the set of rational numbers (which is countable). However, the rational numbers still have gaps. Those gaps have zero width, but they're still gaps.

Consider the rationals "less than sqrt(2)" and the rationals "more than sqrt(2)". That is, let L be the set of rationals q where either q < 0 or q2 < 2; and let R be the set of rationals q where q > 0 and q2 > 2. Every rational number falls into one of L or R (since no rational q has q2 exactly equal to 2), and every member of L is less than every element of R. So we've split the rational line into two pieces, but there's no rational number which corresponds to the exact position of the split. That's a gap in the rationals. As it turns out, there are more gaps than numbers.

The defining property of the real numbers, as determined by Dedekind, is that every cutâevery partition of the reals into nonempty sets L and R where L lies entirely to the left of Râcorresponds to an actual real number x, which is either the greatest element of L or the least element of R. As noted above, this goes a lot further than ensuring that numbers get arbitrarily close. Something much deeper and more powerful is going on.

You seem to read "infinite set" as {a_1, a_2, a_3, â¦}, implicitly assuming that every element of the set is a_n for some natural number n. The whole point of Cantor's theorem is that this intuition is vastly, mind-bogglingly wrong for most infinite sets.

This is getting a bit heavy, so I'll repeat Mark's advice: specify the function that you think will work, and apply the diagonal argument to it. You'll see what you missed.

@Mark The problem isn't that the nodes of the tree aren't countable: They are! The problem is that the tree doesn't have a node for each real. What is the node for pi? Doesn't exist. Same for 1/3.

@Nate If you "flip" the tree and generate the natural numbers, the tree is countable AND includes a node for each number. The tree does provide a mapping for the naturals. Including leading zeros isn't a problem. (Excluding them isn't hard either...)

As for the tree we've been discussing, it depends on what you count. That decimal tree has a countable number of nodes, and an uncountable number of branches. Since it's the branches that correspond to real numbers (more or less), organizing the nodes into a list doesn't really accomplish anything.

Since I've already disgraced myself for today, I little bit more can't hurt :-)

Consider a 16bit version of IEEE floating point numbers. It is a finite small subset of numbers in R. A 32bit version is also finite, although it contains more elements than than the 16bit version. In fact, if we keep adding bits to the 'precision', at each iteration we get a new finite set of additional numbers represented. Each step includes a new set of growing, but finite elements.

Now, if we talk about this growing set of numbers, as the limit of the precision P (bits) approaches infinity, then I have an interesting question to ask: is Pi contained in our infinity-bit representation? It's really a question about whether or not we ever "get to" infinity.

If Pi is there, then R can be mapped to only one infinity (based on precision). If Pi is not considered to be there, then we have some weird concept of "post infinity". Such that we could write a set of numbers approaching Pi as:

{ 3, 3.1, 3.14, 3.141, ... , Pi }

and it is this 'post' infinity that makes my earlier mapping invalid. In this second case, I do suspect that we could round up all of the "post infinity" representations (an infinite group of them) and put them into our set first.

Continuing, although I can't claim to really understand Cantor's diagonalization argument (or at least how it seems to be mapping back to Reals), if there is a problem, then it might be that the argument applies to code, not data. By that I mean those "mathematical" objects that are changing via time. I know, it's weird to map a mathematical formal system onto a programming one, but ultimately they are related. Thus perhaps a run-time infinity (for lack of a better term) creates something outside of the formal system, and thus defies counting (because you must "count" relative to some point in time).

If that works, then we have a concept of data infinities that are different from code infinities (like the halting problem). Reals could be defined as code, but they are fully representable as just data (at infinity). And as such, might be mappable back to N (based on either earlier case).

Just a (weird) thought.

Paul.

I agree with the other commenters that the node of the tree are countable: given the I node of the Lth level it corresponds to (10^(L-1) - 1)/9 + I (where L starts from 0). This is used in data structures to represent a tree with an array. Problem is a *node* for every irrational number like sqrt(2) or Pi does not exist.

sorry, looks like mattiast already pointed that out

@32 and others:

You're missing what I'm saying. I'm trying to be as generous towards the bozo as possible. So I'm interpreting his description in the way that gets closest to what he's trying to say. And there is a valid infinite description of the tree - that's what I was trying to get at with my
surreal numbers post.

The surreals are a brilliant extension of the real numbers that grew out of John Conway's exploration of a particular branch of game theory. It's a step-wise construction, where in each step, you can create a new generation of numbers.

Roughly, a surreal number is defined by two sets - a left-set which contains numbers smaller, and a right-set wich contains numbers larger.

So you start with zero - defined as the pair (empty, empty). In generation 1, you can define two new numbers: 1 and -1, where 1 is ( { 0 }, empty), and -1 is ( { 0 }, empty ). In generation 2, you can define more numbers: 1/2 is ( {0}, {1} ), 2 is ( {1}, empty). And so on. In each generation, you add a finite number of numbers.

You can get an approximation of any real number to any finite accuracy in a finite number of steps. But there are lots of numbers that you can't create after a finite number of steps. The cases where the surreals can't do a finite representation of numbers
are similar to the cases where bozo's construction can't do a finite representation; the difference is that the set where the surreals can't do a finite representation is based on binary, and the set where bozos construction can't do a finite representation is based on decimal. In both cases, there is no finite representation of 1/3; and there is no finite representation of an irrational number like π.

But Conway shows how in the surreal construction, after an infinite number of steps, you get precise representations of every real number - plus a bunch of unreal numbers, like ω, and 1/ω.

If you take the decimal tree representation and extend it an infinite number of steps, you'll get all of the real numbers between 0 and 1.

I don't think that's actually what the bozo meant - reading his stuff, he's got a profound dislike of any kind of reasoning that involves infinity. He rejects the entire concept of an irrational number, because a number without a finite representation can't exist. He rejects the idea of limits, because limits involve reasoning towards infinity.

So from his reasoning, he's almost correct. According to him, numbers like
π don't matter - they just don't exist. There is no square root of two. There are some numbers that are very, very close to it - but according to him, there is
no real number n such that n*n=2, because such a number would require an infinite
notation. If you accept that, then the set of real numbers is the set of rationals, and his argument is correct.

But since it's just insane to say that things like π and e and limits don't exist, the only way to rescue his construction is to pull the surreal trick, and extend the construction out to infinity. Then you do end up with all of the real numbers, but the nodes of the tree
are uncountable.

Paul, it really depends on what you mean by "the infinity-bit representation". If we think of the n-bit precision numbers as embedded in the (n+1)-bit precision numbers, for all natural numbers n, and take their union, then we get a countably infinite collection of representations, but one which cannot precisely represent Ï or indeed most of the reals. (This is often called a "direct limit".) If instead we think of the (n+1)-bit precision numbers as projecting onto the n-bit precision numbers, and take the collection of branches, then we get an uncountably infinite collection which can represent all of the reals. (This is often called the "inverse limit".)

I do suspect that we could round up all of the "post infinity" representations (an infinite group of them) and put them into our set first.

You can't. If you think you've found a way, slap it with the diagonal argument and you'll see why it doesn't work.

I can't claim to really understand Cantor's diagonalization argument (or at least how it seems to be mapping back to Reals)

Wikipedia's page on the subject is okay, but the author insists on using ternary expansions, which might not be the easiest to grasp.

Do some research. Make sure you understand the diagonal argument, as it applies to the reals, before you speculate any further. It will save you a lot of time and wasted effort.

Incidentally, you really need to stop talking about "infinity" as if it's a well-defined concept. It isn't. The adjectives "finite" and "infinite" are well-defined as descriptions of sets, but two arbitrary infinite sets are no more equivalent than two arbitrary finite sets are.

Mark:

If you take the decimal tree representation and extend it an infinite number of steps, you'll get all of the real numbers between 0 and 1.

You still haven't said what precisely you mean by this. If you mean that the resulting tree T (obtained I'm not sure how) has a node corresponding to each real number between 0 and 1, then I dispute this claim. Let v be a node of T corresponding to an irrational number. What are the neighbors of v (the nodes directly connected to it)?

The surreal numbers are all fine and good; I just don't see any sensible way to put them in a tree, and you haven't told us how to do it.

@Chad, thanks for responding. Somehow I can't ever consider "thinking" as a waste of effort, even when I'm wrong :-)If more people would try, it would be a better world. Thanks for indulging my foolishness.

I've tried to wrap my head around the diagonalization argument (I've read at least four versions so far), but I keep getting stuck on the basics. The "list" that is created appears to be finite, or at very least our searching for the missing element is a search over a finite set of elements (because it halts). Many examples have the list un-ordered, which I find even more confusing.

If you take a list of finite elements, and apply the diagonalization construction, than depending on how the list was constructed, the element is there or not. If you add any missing elements, and then do the diagonalization again and again, eventually there won't be any new elements to add. There are a finite number of permutations at each finite number of elements. If we now allow each number to grow by one digit, and then start regenerating new elements, that too will terminate at some point.

When I think of infinity, I tend to see it in the same way people use "west" in a phrase like "the sun setting in the west". That is, to my naive way of thinking, it is a direction, not a place. In that sense, as our finite lists get larger, or the precision of the floating point numbers grows, we get closer and closer to the list being infinite (and the distance between our finite list and our infinite one gets infinitely smaller).

At this point, if we've build up our list as described above, our next generated element is either in the list (because of the last iteration) or about to be in the list because of the next iteration. The only elements missing from the list are those that are of "infinite" length. But if we can't get to "infinity", then we can't be sure that the element is missing. If we can get to "infinity" (in some magical universe), then the element is not missing. Either way, I am confused.

Paul.

@Mark: "If you take the decimal tree representation and extend it an infinite number of steps, you'll get all of the real numbers between 0 and 1."

You're being imprecise here, and I think it can cause confusion.

There is a PATH through the tree for every real number, but there is not a NODE in the tree for every real number. Alternatively, every real number has a path through this tree, some of the paths are finite (and can equivalently represented with their terminating node), and some of the paths are infinite (and don't have a terminating node).

The nodes (and finite paths) in the tree are countable, the infinite paths are not.

@Chad: You're right if you take "branch" to mean "path" and not "edge". There is an infinitely countable number of nodes in the tree, and an infinitely countable number of edges. The number of paths in the tree is NOT countable.

Heh.... Replace "infinitely countable" with "countably infinite" in my last post...

Paul, the list in Cantor's diagonal argument is actually infinite - countably infinite. You can think of the entries in the list as 'numbered' after the naturals.
Also, infinity in this context refers to the size of a set. If you find it useful to think of it as a direction, you might be confusing it with the meaning it has in the context of calculus (as in a function 'diverges to infinity', or gets 'infinitely close' to a number).

@dete: I assume that you're using the path as representing a variant on a Cauchy sequence for your reals. I'm going with Mark on the nodes, though - they are uncountably infinite.

Consider: At each level, n, of the tree, there are 10^n nodes. This means that at a "countably-infinite" (called hereafter c.i.), you will have 10^(c.i.) nodes. That's an uncountable amount, isomorphic to an "enumeration" of the number of functions from the naturals to the set { 0..9 }.

@Mark: Just a quibble, but in comment 34, did you mean to write:
"-1 is ( empty, { 0 } )"

@boris: Yes, it precisely because the list is infinite that I am having trouble. Functions diverge to infinity, limits approach it, and (I've always thought) sets just grew larger and larger. Since it's not a thing, it must be an action (verb, direction, etc.). Countability just seems like a nice way of saying something maps to N (thus allowing us to count it).

Can you ever really be sure that an element is not in an infinite list? Every finite element is in the list (by construction), so it's only the infinite ones that are "not there yet". Also, you're using an infinite element that you don't have yet either (or you would have matched an already existing finite element).

Maybe it's just Thursday. :-)

Paul.

@Walt:

The tree of all finite decimal expansions has countably many levels AND countably many nodes. (Each level has finitely many nodes, and the union of countably many finite (or countable) sets is countable.) So your intuitive argument unfortunately doesn't work.

We can add in all the infinite decimal expansions, but there's no sensible place to attach any of them. You could make each one a disconnected node by itself, and that's a perfectly valid thing to do, but it doesn't give you an object that's very useful. You might as well talk about sets rather than trees.

@Paul:

I'd guess that some of your confusion stems from thinking of limits and sets in active terms. Limits don't approach anything, and sets don't grow. They simply exist. A limit is equal to a definite value (when the limit exists) and a set (or list) has a definite collection of members.

@Mark I think this tree has been mentioned on your blog before.

I agree with Ivan and dete in 36 and 38. I thought too that the misunderstanding lies with the 'node' and 'branch' distinction. If the function does not map to the nodes then what is the definition of this function? Maybe that is a better question for the bozo and you are giving him the benefit of doubt ascribing a definition akin surreal numbers.

If the function does map to nodes, then I think that even when 'extended to infinity' the nodes are only countably infinite.

But, then again, I think we have a different interpretation of 'extended to infinity'. Mark you write,
"But Conway shows how in the surreal construction, after an infinite number of steps, you get precise representations of every real number..."
I think you mean "uncountably infinite number of steps" to describe the nodes. So, for example, there would be a 'pi' node at the end of a branch and an 'e' node at the end of another. Whereas I interpret 'extend to infinity' as letting the tree grow on an on forever in the manner described, which turns out to be countably infinite because the union of a countably infinite number of countably infinite sets is again countably infinite.

Paul: I think I see the issue. In set theory, one doesn't think of a set as changing with time. Sets are static and have definite membership; they really are "nouns", not "verbs". Given an object a and a set X, either a is an element of X or it isn't. If it isn't, then adding a to X produces an entirely different set. That static nature makes it a bit unnatural to model functions and time evolution (though it's possible, of course!); category theory is a more natural setting for such questions.

Anyway, since sets don't change, they don't grow larger and larger. A set like N or R doesn't literally grow toward infinity; it just contains arbitrarily large elements. I'll admit it's a bit unnatural to consider an infinite collection as completed. It wasn't until mathematicians put calculus on a firm footing in the 19th century that we saw the need for infinite sets, so they're a pretty recent development; but they really are necessary.

What exactly do you mean by "X maps to N"? That there is a function, that it's 1-1, or that it's onto? It's a bit more natural to think in terms of maps from N to X, and whether an onto map exists.

"Can you ever really be sure that an element is not in an infinite list?" That depends on how you've defined the infinite list. Regardless, the element either is or is not in the list; it's considered a well-defined predicate even when there isn't a "procedure" to determine membership. For example, the set H of all pairs of natural numbers (e,n) where machine e halts on input n is a well-defined set with a well-defined membership, even though (famously) there is no algorithm to decide whether a given pair (e,n) is an element of H.

@Walt

The notation 2^(infinite cardinal) has nothing to do with exponents of finite numbers. When speaking about infinite cardinals, "2^a" only means "an infinite number greater than a." The '2' does not refer to the number 2. Furthermore, "greater than" even has a separate definition when talking about infinite cardinals.
Thus it is meaningless to write "10^(c.i.)" as you did in 41. If you wish to consider the size of the number you were trying to describe then you will have to take a union of sets, which is, as Ivan described, countably infinite because you are talking about a countable number of countable sets.

@Mark

"If you take the decimal tree representation and extend it an infinite number of steps, you'll get all of the real numbers between 0 and 1."

Ok, after reading Ivan and dete, I thought of a simple argument against this statement. The number of nodes in the tree can only be infinite if a single node has an uncountably infinite number of branches extending from it, otherwise we have a countably infinite number of countably infinite sets, which is again countably infinite. This particular tree, as described, does not have nodes with so many branches, each node extends to only 10 more branches. Therefore no matter how far we extend the tree or in what manner we extend the tree we will never have an uncountable number of nodes.

@mike:

(talking to Mark) I think you mean "uncountably infinite number of steps" to describe the nodes. So, for example, there would be a 'pi' node at the end of a branch and an 'e' node at the end of another.

Not quite. You could construct the tree level-by-level, indexing the levels by ordinal numbers (which is what I think Mark was going for), and then level Ï would contain the infinite decimal expansions (uncountably many of them, of course). I'm not claiming this makes a lot of sense, because, um... what should go in level Ï+1 if we continue the construction? (Decimal expansions aren't really what we want to work with if we're trying to end up with surreal numbers.)

As I mentioned earlier, you'd pretty much have to add the nodes in level Ï (your 'pi' node and 'e' node) without connecting them to anything else, so it's a pretty dumb construction. But it's countably many steps, and the resulting tree has uncountably many nodes (although its only interesting part, the main connected component, is countable).

Pedantic note:

I just checked the definition of tree (I'm not a graph theorist), and connectedness is one of the requirements. So in some of my previous comments, tree should be replaced with forest.

@mike:

The number of nodes in the tree can only be uncountably infinite if there exists a node with an uncountably infinite number of branches extending from it, otherwise we have a countably infinite number of countably infinite sets, which is again countably infinite.

(quote altered to say what I'm sure you meant)

Yes. If each vertex of a tree has countable degree, then the set of vertices is countable. This follows from the connectedness requirement: if we fix a root of the tree, then any other vertex is necessarily a finite distance away from that root vertex. Each sphere of radius n about the root is countable, and the union of all such spheres is countable (and equal to the entire tree by the previous statement).

If I remember my graph theory - the only way you can have an infinite graph is to have either at least one infinite node (infinitely many paths leading from it) or infinitely many nodes - because if neither of these are true you can enumerate all the paths (it might be a large number - O(exp(n)) sort of thing - but still finite).

The "intuitive" argument seems to be something along the lines of 1) we can enumerate all finite decimals of order M, 2) since this is complete (it is a finite set that is closed) then there is no diagonalization that can move outside of the closed set, 3) we then increase M and apply the same argument. QED (not).

Outside of the snide remark that this reminds me of my high school pre-calculus teacher ;-), it shows a slick mis-application of induction. It is sort of like the "proofs" we software engineering sort of people see about sorts that are O(N) (since you can add an element to a sorted list with O(N) (really O(lgN)) comparisons, you just build a sorted list one element at a time so its O(N) - and you conveniently forget that you have to do this N times).

Thanks, Ivan. That is exactly what I meant.
In 45 I was trying to describe how one could imagine a decimal tree with uncountably infinite number of nodes, and I think it occurs in some imaginations because of the phrase "extend to infinity," (or maybe there was a misunderstanding of the 2^x notation). But after writing 48 I'm convinced that such a tree is an invalid concept.

OK, there appears to be a lot of confusion about this whole tree business, so let's set it up carefully. We are constructing what is called an n-ary rooted tree (n at least 2): it has a 'top' node (at level 0), called the root, and each node at the ith level is connected to a single node at the (i-1)th level, and to n nodes at the (i+1)th level. This extends to infinity, in the sense that for every natural number i there is an ith level of the tree, containing ni nodes. The number of nodes is countable.

Define an end to be a path containing exactly one node from each level for every single level. (Of course, any two nodes in this end should be connected by a path travelling only along nodes in the end.) This might be thought of as a branch, but it extends off to infinity. The boundary of the tree is the set of ends. The boundary is an uncountable set, because it contains (a set that is in one-to-one correspondence with) the power set of the naturals. To see this, assume n=2, and for a given level i, if the end (i.e., the branch) veers to the left then we allow i to be an element of the set, and if the end veers to the right then we do not allow i to be an element of the set. This constructs a bijection.

In order to find non-terminating decimals (or n-ary representations of the reals), one needs infinite strings, which can be thought of (i.e., easily in one-to-one correspondence with) as the ends of the n-ary rooted tree. Hence the reals with terminating decimals (i.e., those rationals of the form a/10b for some a,b) are countable, but all reals are in bijection with the power set of the rationals, which is uncountable.

@Chad: Yes, I agree. My intuitive definition derives itself from my experience with computers. If you remove the growth (time), then each part of Cantor's diagonalization makes perfect sense. The element you construct is not in the set, and can't be.

Maybe it's faulty intuition or too much of a Computer Science bias, but the timelessness of sets seems off (setting itself up for problems like Russell's paradox). With time included in Cantor's proof I can see a race condition between the construction of the element in the set, and the construction of the set itself. The set is always a day late and a dollar short, so to speak. It feels like the infinite-size of the elements is a different type than the one in the set (one is structural, the other is dynamic). But I guess if the definition of sets bypasses this, then it's already been consigned to the trivia bin.

We never got category theory in school, but it seems like an interesting branch to explore. If I get a chance, I'll dig around. Thanks again for responding :-)

Perhaps this can clear up some of the node/tree/path confusion:

* The author attempts to build a tree to show how each real number can be enumerated.
* This tree (pictured above in the post) is constructed such that the nth level/layer/depth of the tree corresponds to the nth decimal digit.
* The nth digit has an edge leading to the next possible digit for every possible digit coming from that node.
* In order to find a number x in this tree you must start at the root node and traverse down the tree following the edges corresponding to the digits in x until you have found the last digit of x. The path that you took down this tree is what corresponds to x. If the digits in x do not terminate, the tree is considered to be infinitely deep.
* The author claims that the number of nodes and edges in the (infinitely deep) tree is countably infinite, namely, of size |N|. He is correct. If you start numbering at the root node and move down one depth at a time, from left to right, you can enumerate every node and every edge. (Namely, for every node or edge in the tree, you will count it at a finite point in time.)
* However, this tree was meant to represent numbers by paths through the tree, not by nodes in the tree.
* Since there are 10 possible choices at each of the nodes and there are |N| nodes, the number of paths available is 10^|N|.
* The size of the real numbers is 2^|N|. If you don't believe this, then read on:
* To make it easier, think in terms of binary. We can use base 2 instead of base 10 since the size of the sets that they can represent are equal, namely we can write the all of the reals in base 2 or base 10. Now each node simply leads a 0 or 1. Then there are exactly 2^|N| nodes.
* Use Cantor's diagonalization proof on infinite binary strings and realize that you cannot have a surjection from N to the set of infinitely long binary strings. The author never showed that Cantor's proof was flawed.
* Realize that the number of paths in the tree is greater than the number of nodes or edges in it. Consequentially, there are more real numbers than integers.
* QED.

I think there's some confusion here about the meaning of "constructive proof". I hesitate to bring this up in comments, but it seems worth a try. Cantor's proof is constructively valid. The statement of the theorem is "there is no bijection between N and R", a negated proposition. Of course, the way to prove a negative is to refute it by showing that assuming it would result in a contradiction. Such a proof always ends with "therefore not something", that is it is a proof of a negation of something.

This is _not_ a "proof by contradiction" in the sense criticized by constructivists! What is criticized by constructivists is to prove a positive statement by assuming its negation and deriving a contradiction. To reiterate, this is _not_ what the Cantor argument does: it proves not P by assuming P and deriving a contradiction. A proof by contradiction in the sense criticized by constructivists is one that proves Q by assuming not Q and deriving a contradiction. Constructively you have proved that the statement Q cannot be refuted, which is not the considered to be the same thing as affirming it. For example, any open problem in mathematics is one what cannot be refuted (it might be true for all we know) nor can it be proved (that's why it's open). For this reason the constructivist denies that "not refutable" is the same as "affirmed".

(1) I enjoyed Mark CC channeling Conway: "Before the Ïth birthday, the tree is finite, and will always have a countable number of nodes. After Ï construction steps - that is, when the tree is extended to infinity, in has an uncountably infinite number of nodes."

(2) Not everyone here is clear on "Intuitionist."
See what I link to from my related entry in The On-Line Encyclopedia of Integer Sequences
http://www.research.att.com/~njas/sequences/A140861

(3) By "related" I mean, not just the link from there to Mark van Atten, The Development of Intuitionistic Logic, Stanford Encyclopedia of Philosophy, July 10, 2008; but also my explicit use of strings of decimal digits as a representation of something that seems very different.

I think this might be relevant:

http://www.broadstuff.com/archives/1194-The-game-theory-of-Google-Knol-…

(1) I enjoyed Mark CC channeling Conway: "Before the Ïth birthday, the tree is finite, and will always have a countable number of nodes. After Ï construction steps - that is, when the tree is extended to infinity, in has an uncountably infinite number of nodes."

Unfortunately, Mark was not channeling Conway's rigor. It's impossible to construct a tree with uncountably many nodes unless at least one node has uncountably many branches, as shown above in #51.

@mike:

When speaking about infinite cardinals, "2^a" only means "an infinite number greater than a."

No, 2a is the cardinality of the power set (of a set with cardinality a).

@Ivan

You're right, but I just wanted to emphasize that the '2' is just notation when talking about infinite cardinals in response to 41.

B-Con in 56 also made the mistake I was writing about saying:
"* Since there are 10 possible choices at each of the nodes and there are |N| nodes, the number of paths available is 10^|N|.
* The size of the real numbers is 2^|N|..."
There is no such thing as 10^|N| or |N|+8.
B-Con used bad reasoning to get a right conclusion, but Walt use this bad reasoning to get a bad conclusion.

Forgot to sign that last post^^ I wrote 62.

@B-Con:

Then there are exactly 2^|N| nodes.

Well, their cardinality is 2|N|, or 2âµ0. The word exactly is a bit weird when applied to infinite cardinals.

@mike #62:

Actually, no. Ten is a cardinal number just like two is, and cardinals can be added, multiplied, and exponentiated. So 10|N| is a perfectly valid cardinal expression (and is equal, of course, to 2|N|).

@B-Con again:

Oops, I got caught up by the word exactly and missed the larger error: the nodes are countable, so their cardinality is not 2|N|, but simply |N|.

@Paul: I'm glad that we're understanding each other more clearly.

Your intuition about "race conditions" is actually pretty good. Most of the paradoxes found in the early days of set theory amount to self-reference problems, and a great deal of effort was expended to avoid them. For example, assume the existence of a set V which contains all mathematical objects (or even all sets) as elements. The collection of all its subsets, denoted P(V), is a subcollection of V. Thus there is an onto function p from V to P(V): if x is a set, then p(x) = x, and if x is not a set, then p(x) is the empty set. But by Cantor's argument, there is no such onto function. What makes this especially interesting is that the flipped-diagonal set that Cantor's argument produces is exactly the Russell set (check!). I think this was actually how Russell found the set in the first place.

There are only two coherent ways to resolve this paradox: either deny the existence of the function p above (as Russell did, on what I think are very dodgy ideas inspired by type theory), or deny that all of mathematics can be bound up in a single set (as Cantor and eventually most of the mathematical community did).

What's beautiful to me about modern set theories (such as ZF) is that they let us examine systems like N or Rn as completed, bounded, but still infinite structures, while allowing for the unbounded, absolutely infinite universe of all mathematics.

Best of luck in your studies :-)

@Chad: Yes, our discussion absolutely crystallized my understanding. Yesterday I started trying to list out my initial viewpoint of sets (because I thought it might be fun), but I think that lead to a dream which woke me up in the middle of the night (a habit that comes from coding, I think). I doubt if it is correct, but I in the wee hours of the evening I could envision another way around the problem, so I put together a post that (maybe) shows that R can map (one-to-one, onto) to N.

@Mark: if you have some time, I'd appreciate you trying to tear it to shreds. As you suggested I attempted to address Cantor's argument as well as creating an enumeration. Shred away ...

http://theprogrammersparadox.blogspot.com/2009/12/infinite-node-tree.ht…

Paul.

The tree, ipso facto, doesn't get you anywhere towards proving that there's a bijection between the naturals and the reals. Say we construct the tree. Now, in order to associate each natural with a real, you need to label each path through the tree (representing a real) with a natural number. The tree thus generates a list in which each natural corresponds to a real. Cantor's argument applies to this list. Game over.

To Paul at post 68: I just looked at your argument and the flaw shows up when you say this:

"So we traverse the above as follows:

a1, b1, a2, c1, b2, a3, d1, c2, b3, a4, ...

We can see that eventually we will get through all elements of S.

Then:

a = a1, b = b1, c = a2, d = c1, e = b2, f = a3, ....

Thus there appears to be a simple mapping between a single infinite set and an infinite set of infinite sets."

This claim is only true _if_ you're comparing infinite sets _with the same cardinality_. If not, then no, you won't eventually get through all elements of your S. At the start of your proof you talk about constructing your tree as follows:

"We can define an 'infinite node tree' as a tree similar to an N-ary tree, except that at each and every node, there are an infinite number of children."

Did you mean a countably infinite number of children, or an uncountably infinite number of children? :)

You've shown that a countably-infinite-node tree has a countable infinity of nodes- I think! - but an uncountably-infinite-node tree has an uncountable infinite of nodes- I'm sure :)

Ah, f--k me. Trees in the sense of set theory are more general than trees in the sense of graph theory. Also see Aronszajn tree.

The lemma that I proved in comment #51 only holds for graph-theoretic trees, where paths with two endpoints are necessarily finite. For set-theoretic trees, such paths are allowed to be infinite, and Mark's construction makes sense.

Mark, I retract my comment #60.

I need to amend my post #56, where I said:
> * To make it easier, think in terms of binary. We can use base 2 instead of base 10 since the size of the sets that they can represent are equal, namely we can write the all of the reals in base 2 or base 10. Now each node simply leads a 0 or 1. Then there are exactly 2^|N| nodes.

I meant to say that there are 2^|N| PATHS, not nodes. This was obviously a typo, considering the context. I'm not sure why others didn't see this.

@ mike, #62
> There is no such thing as 10^|N| or |N|+8. B-Con used bad reasoning to get a right conclusion, but Walt use this bad reasoning to get a bad conclusion.

Barring the typo, my reasoning is sound. Using the same reasoning that leads to the notation of 2^|N| to represent the powerset also leads to the motivation to use 10^|N| in this similar case. If you are familiar with powerset notation, surely this should be none more confusing. Perhaps it was my usage of the word "exactly" that confused you. Regardless, reducing the problem to the binary powerset mapping (in the next step) should have been a dead giveaway.

@ Ivan, #64
> Well, their cardinality is 2|N|, or 2âµ0. The word exactly is a bit weird when applied to infinite cardinals.

I agree. "Exactly" is a word better left for measuring finite quantities. I shouldn't have used it, I think it caused confusion.

And to clarify my previous post, "binary powerset mapping" means "the binary string mapping used to construct the powerset".

I wonder if some of the objection to Cantor's proof comes from how it's presented as coming up with a single, special-looking number that doesn't fit in the list, and it feels like a cheap trick, and that it ought to be possible to "fix" the list by adding it in.

Maybe it would be more intuitively convincing to generate a whole load of numbers that aren't in list - eg, given a supposed list of all real numbers, for (almost) every infinite sequence of digits from 1-9, you can generate a number not in the list by altering the nth digit of the nth number by the amount in nth place of the sequence. That way, instead of one missing number that looks like it could be tacked onto the start of the list, there's an infinity of new numbers, and no particularly obvious way to "fix" the list.

(It might be better to get rid of the "(almost)" there with some slightly more complex scheme that accounts for numbers with two decimal representations)

@Stephen,

Those are good points, we can discuss them here if you want (but I almost missed you comment).

Running the numbers down the tree is doomed, I agree. That's why I stuck them (in their totality) in the nodes. That way I don't have to 'get' to infinity, and thanks to set theory, they just exist.

If there aren't different infinite cardinalities, then my comparison is fine. Any two infinite sets (with singular or multiple embedded infinities) are the same cardinality, because there is no object larger than the one I've created (in set theory), and this object (likely) maps back to N.

In fact, if it turns out I'm right, then there are no 'uncountable sets' either. R is countable, and every crazy construction of sets possible is 'traversable'.

So, I definitely mean a countable infinite number of children (since there are no uncountable sets anymore).

The tree is not diagonalizable, but it is travserable and thus countable. I think (so far).

Paul.

@Paul:yes, _if_ every infinity were countable then every infinity would be countable. But you can't assume that when you make your object! Otherwise we could stipulate that the square root of 2 is rational by stipulating that all numbers are rational :)

Whatever object you build, if you claim it generates a one-to-one mapping between the naturals and the reals, it doesn't matter how we get there; we can always run the diagonal argument over the claimed mapping and generate a real that doesn't correspond to any natural.

@Stephan, which is why I had to find a way around the diagonal argument. Mark's right, a mapping is no good unless I can get past Cantor.

I think I did that by sticking in multiple infinities. If you can't get to the end of the construction, you can't create the diagonal, and thus it can't NOT be found.

Cantor assumes that there is only a single infinite set of elements in the original sequence. As far as I know (but I could be wrong, and would like to know why) I could also start with a sequence that contains a 'number' of different infinities. There doesn't seem to be a mechanism to prevent this (at least not in the Wikipedia description).

Independent of everything else, is this an allowable sequence to start with:

{ a1, a2, ..., b1, b2, ... }

The first ... extends the aNs out to infinity, and the second ... extends the bNs out to infinity. The two ... cannot be joined because they apply to different elements.

Is this allowed?

Paul.

@76: whatever construction you're building, _if_ it's generating a bijection between the reals and the naturals, it must be generating a list which maps 1 to a real, 2 to a real.... etc. and we can do Cantor on that list. If your tree generates such a list then it's vulnerable to Cantor, and if it doesn't then you have no bijection.

If your tree construction doesn't allow you to "get to the end of the construction" doesn't that mean it's not countable?

@Stephen, sorry about all of the typos in my last comment. :-)

Consider the sub-sequence produced by a mapping:

0.00001000...
0.00001100...
0.00001110...
...
0.00010000...
0.00011000...
0.00011100...
...

This sub-sequence will prevent Cantor's argument from working. More importantly, if we ever were to find a one-to-one and onto mapping R -> N, this sub-sequence would HAVE to be part of that mapping.

However, I can assign 1 to the first item in the first part of the sub-sequence, 2 to the first item in the second part of the sub-sequence, and keep switching back and forth between them. Thus this sub-sequence is countable.

This shows that Cantor's diagonalization argument does NOT prove that R can never be mapped to N, but it proves that the mapping itself will NEVER be a sequence with a single infinity. A simple list will never work. Which of course, to some degree, we all know, and all except.

This seems to be a hole. The only way to close it is to say that sequences can only have one and only one infinity (even bi-infinite sequences are dangerous).

The nodes in a tree are countable. Even if that tree has multiple infinities. We can always construct a traversal, that will eventually get through all of the infinite nodes (as we approach infinity), and we can assign a number to each step in the traversal. There are a number of ways to show this. Thus we can always find a one-to-one and onto map from the nodes in the tree to N.

I'm going to jump back over to my blog now. Chad had an interesting question that I didn't answer well. Head down into the comments, since that is where all of the meat is now (a mess and getting worse, but I promise I'll rewrite it when I've reach a conclusion (one way or the other)).

Paul.

How exactly does any subsequence prevent the argument from working? I don't get what you mean.

Given a sequence, we have to create a new element by picking a different nth digit, for all n elements.

http://mathpages.com/home/kmath371.htm

So we start by working down the diagonal, and picking the nth digit for the nth number:

[2]. 0 0 0 0 1 0 0 0 ...
0 .[2]0 0 0 1 1 0 0 ...
0 . 0[2]0 0 1 1 1 0 ...
0 . 0 0[2]0 1 1 1 1 ...
...
0 . 0 0 0 1 0 0 0 0 ...
0 . 0 0 0 1 1 0 0 0 ...
0 . 0 0 0 1 1 1 0 0 ...
...

The problem is that we go 'into' the first infinity, so there is no nth diagonal element to pick after we come out (because it has gone to infinity already).

I am unable to apply Cantor's diagonalization argument to my subsequence. I can get an element, but it was only constructed using some limited number of the sequence elements.

So we don't know for sure that the element is not in the sequence. Maybe it is, maybe it isn't. To know for sure, we have to use all of the elements, but we can't do that. Either we don't finish the construction, or we create a element for which we can't say anything meaningful.

Paul.

If you can't enumerate part of your sequence this is a problem for your construction, no? - you have a bunch of real numbers starting with 0.0001... which your construction _does not associate to any natural number_ because you never get out of your first sequence. But your claim is that you can associate every real one-to-one with a natural- so you're showing us a construction which fails to do what it should for your claim to be true.

And if we do associate both your subsequences to naturals- easily done say be using the odd numbers for the first set and the evens for the second- then Cantor works on the list.

No, because as I said in my earlier comment, I can enumerate my sequence. I just keep jumping back and forth between the two different infinite pieces. They are countable, but not diagonalizable.

This of course brings up the reason why I stumbled onto all of this in the first place. When I was putting together an earlier post on primes I realized that for every structure (I could imagine), no matter how many infinities it contained, there was always a way to eventually (as we approach the calculus infinity) visit every element in the structure. That is, no matter how many infinities went off from each other, at different times, I could still traverse them.

The idea is actually simple. If we have an infinite number of infinite branches hanging off the structure, we impose an arbitrary finite limitation on all but one of them. Then we just increment through the finite limitations. Thus, I think, there is no collection of infinities that can't be traversed in this manner.

When I read the above post, I realized that Cantor was claiming that R was preciously a mathematical object with a few infinities, that was not traversal. Without really understanding set theory, that started my line of questioning to Chad, which lead me here.

Now that I have an object (binary infinite node tree), I'm just intrigued to see if it fits into set theory. If it does, then R -> N. If it doesn't, then there is an "extended set theory" where it does fit.

Paul.

Paul,

You're going about constructing the diagonal in the wrong way. Here's how to construct the diagonal element given your enumeration: the first digit is the first digit of the first entry on the first sub-list; the second digit is the second digit of the first entry on the second sub-list; the third digit is the third digit of the second entry on the first sub-list; etc. Point being, to construct the diagonal, you simply have to order the elements on the list by their enumeration.

@jdkbrown,

Yes, you are correct. That will work for my example. That should work for any sequence where there are two different types of infinities. Fortunately, for me, the actual structure itself has three different types of infinities. One for each infinite element, one for the depth, and because it is an infinite node tree, one for the breadth.

It's that third type of infinity that 'eats' the diagonal argument. Two is managable.

The reason it doesn't also eat the 'countable' argument is because we're basically ignoring the element infinity when we are counting.

Two is doable, three gets lost. But there are three going into the diagonal argument, and only two going into the counting.

Paul.

Paul, if your counting includes all the reals and is counted by the naturals, then we apply the diagonal argument _to your counting_ and it fails. If, on the other hand, your construction of the reals includes more elements that aren't counted by the naturals, you've failed to establish that the naturals count the reals.

IOW, you can't make the diagonal argument _not_ work on your counting by proving that it doesn't work on _something other than your counting_. _However_ you construct your counting, it generates a list of naturals corresponding one-to-one to reals, and we can apply the diagonal argument to it. Whether or not you can apply the diagonal argument to something else isn't relevant.

@Stephen,

Give me about an hour, and then check back at my site for the lastest post. The post should hopefully explain it all (as Fermat says "it too large for the margin").

Paul.

@Paul W Homer:

It's always nice to see people interested in set theory and associated concepts (in perhaps the same way that it's pleasing to see young animals leaping to and fro with such vigour and enthusiasm) but I have to caution you that the contents of what you're saying mark you out as being "just another Cantor crank".

I see that you yourself are aware of this possibility and do not embrace it, which is good. Hence, I recommend that you Read More. Carry on writing if you wish, but at least intersperse it with reading. One idea would be to google for some lecture notes on set theory, but actually working through university-level courses on one's own can take quite a lot of time/discipline/commitment.

Alternatively, you could try reading Paul Halmos's excellent book "Naive set theory" (don't be put off by the title!)

@Neil,

Wasn't Cantor originally considered a Cantor Crank? :-)

The difference hopefully between me and "just another Cantor Crank" is that what I am saying is bounded by rational formal systems. Sometimes I realize that I stray outside of set theory, but only in that I've moved over into Computer Science. I have to think of it in that system, and then map that back to set theory. If I am getting into problems it is because I am thinking in one formal system (that I know well), but trying to describe it in another (that I don't know very well). Translation problems don't necessary invalid the argument (although they may make it harder to understand and ultimately they may invalidate it).

I've had a look at your post, Paul, and you're committing the same error you commit in comment 80.

In your post, you try to construct the diagonal element this way: the first digit is picked off the first digit of first element of the first sub-list; the second digit is picked off the second digit of the first element of the second sub-list; the third digit is picked off the third digit of the first element of the third list; and so on.

You are correct that this procedure won't provide the diagonal element.

But that's not the proper construction. Here's what will work: the first digit of the diagonal element is picked off the first digit of *the first element in the enumeration*; the second digit is picked off the second digit of the second element in the enumeration (i.e, given your enumeration, the second element in the first sub-list); the third digit is picked off the third digit of the third element in the enumeration (i.e., the first element of the second sub-list); and so on.

Lesson: construct the diagonal from the *enumeration*, not from how you happen to have graphically represented your list.

@jdkbrown,

In the enumeration, we cannot write "..." to terminate it, so we cannot map the remaining diagonals to the remaining elements. If you start writing it out, and put in a "..." then it is not the enumeration that I have specified.

The one I have specified is the one in the graphical representation, which can't be diagonalized because of the double ellipse at the end.

Paul.

funny, i had a test when i was in university where i had to prove that the branches of an infinite binary tree were innumerable. it was as easy as showing that the tree represented the binary representation of all real numbers between 0 an 1.

@vila, even funnier because a binary tree is easily countable, just mark 1 for root, 2 for left, 3 for right, etc. descending level by level.

And, Mark's post above shows that neither the irrationals, nor the repeating rationals are in the tree if you base the tree on the representation. The tree never gets to infinity, so the elements are never in the tree.

Paul.

As usual, Mark CC clams up once proven wrong. The tree obviously has countably many vertices, and equally obviously has uncountably many paths.

@Observer,

Actually what I've been discussing has nothing to do with Mark's post, as far as I know everything he has said is correct (or believed to be correct).

If you can count the nodes in a tree, then you can also count the paths. Just name them after their nodes. In a binary tree, call them L1, R1, L11, L12, R11, R12, level by level in the same way you count the nodes.

The problem is in trying to get the irrationals and the repeating rationals into the tree.

Another point: so far, I have done nothing more than just showed that there is a way around Cantor's argument. That it is not entirely fail-safe. As of yet, I have not shown anything more significant than that.

Paul.

@Observer
Mark wrote another post and he has a life, which includes a career. He never mentioned nodes or branches and this is all beside his point anyway.

@Ivan
This is what I mean: P(N):=2^(N). The cardinality of the set of the functions of a set with ten elements to the natural numbers is valid, whereas the number 10 raised to the power of No is not valid. I see that the cardinality of A^N, where the cardinality of A is 2, equals the cardinality of the powerset of N, but I don't see that the cardinality of the powerset of an infinite cardinal implies the number 2. Rather, I believe "2^No" just notation coming from the cardinality of finite powersets.

@93:

One of the things that I'm proud of about this blog is that I have always admitted when I'm wrong.

In this case, I'm not wrong, but I'm tired of repeating myself, and as someone else said: I've got a job and a life, and frankly they take priority.

There aren't more paths than there are nodes: every path is a path to a node; without the nodes, there's no path. The problem is that you're not understanding the infinite construction, and the best I can do is to repeat what I've already said, and suggest that you read Conway, which is always a good thing to do.

In the infinite construction, you can talk about the leaves of the constructed tree - that is, the nodes that only exist when the length of the path through the digit tree to the node is ω. Obviously, you can't ever construct those nodes, by the very definition of ω. But you can talk about them - and with that set of nodes included, there is a one-to-one correspondence between paths and nodes. And with that, you've got an uncountable set of nodes in the infinite construction.

Here is a computer verified formulation of Cantor's diagonal argument, using Agda 2 (although you could construct a similar fomalization in Coq, or any number of other theorem provers if you have more confidence in them).

Now there's no excuse for not agreeing, right? :)

Note also that it is in fact a constructive proof (if there remained any doubt; I've only skimmed most of the comments), since that's the only kind you get in Agda without explicitly assuming classical postulates (which, obviously, I haven't done).

Mike, the number 2 in the 2^(No) cardinality for the power set corresponds to the fact that given a subset S (i.e an element of the power set) then each natural number is either in S ("1") or not in S ("0"). Thus, there is a NATURAL correspondence between the power set of N and the set of functions from N to {0,1}, or equivalently, the set of functions from N to any TWO element set. This function from N to {0,1} corresponding to a subset S of N is called the "characteristic function" of S.

The cardinal 10^No denotes either the set, or the cardinality of the set, of functions from N to a 10 element set, which, as a cardinal, is the same cardinal as 2^No, that is, as cardinals, 10^No = 2^No and similarly for any other finite base-- in fact, No^No = 2^No by (where LE means "less or equal"):

2^No LE No^No LE ( 2^No)^No = 2^(No x No) = 2^No

Since k^No = 2^No for k = 2, 3, 4, ....., No, there is, for each k, a 1-1 correspondence between the power set of N and the set of functions from N to k. but when k=2, the correspondence is natural (by characteristic function). The cardinality of P(N) or R is conventionally denoted 2^No, even though k^No is the exactly the same cardinal as 2^No for all k from 2 through No.

@Paul W. Homer

I wasn't talking about nodes. What i meant with branches are all the (infinite) paths starting from the root and infinitely going down. in this case zero is the path that always descends along the left descendant (0.00000000...). if you also want to include finite paths, well, that's just even more elements to count.

@Paul

"If you can count the nodes in a tree, then you can also count the paths. Just name them after their nodes. In a binary tree, call them L1, R1, L11, L12, R11, R12, level by level in the same way you count the nodes."

but in a tree that allows for infinitely long paths, you'll get infinitely long names. can you count these infinitely long names? no. how do we know this? because we can apply cantor's diagonalization proof on them. there's no sidestepping cantor's argument, you always run back into it.

Mark C. Chu-Carroll: You are not only wrong, you are completely fooled to believe that Cantor's diagonal argument makes any sense whatsoever. Cantor is the father of all cranks. That would make you his relative?

You call me a crank and yet when I read your webpage, all I can think about is: only an idiot can believe in such nonsense.

@vila, I think Mark showed quite well that if you base a tree on representation, then it will never contain the infinitely long elements such as Pi.

"there's no sidestepping cantor's"

Yes there is, I've shown that there is a way around it, but we don't need that here.

@Everybody,

I believe Mark when he says that through a long set of axioms he can prove that binary trees are uncountable. However, consider this:

{ r, l1, r2, l11, r11, l12, r12, l21, r21, l22, r22, ... }

This is a binary tree simply placed in a set, left to right, top to infinity. If for each one of these element I replace it with a number, I get:

{ 1, 2, 3, 4, 5, ... }

Which is the set of N, which is countable. The number of paths in the tree is 1 less than the number of nodes.

So what does this mean? If Mark shows that a binary tree is uncountable based on a set of axioms, and I've shown using first-principles that it is not, then there is at least one axiom in ZFC set theory that is invalid.

Before anyone gets completely panicked, based on my last post in The Programmer's Paradox, there was a previously unknown mathematical object that could easily account for some of these problems. The extra type of magic sequence could be the cause.

I'm going to reply to Chad, over on my site now.

Paul.

@101:

Gosh John, that's just such a devastating critique that I don't know how I'll be able to go on living after it.

Seriously - yeah, I called you a crackpot (if the shoe fits...); but I also took the time to explain why. There's a detailed critique of your construction up there, which you just completely ignored, preferring to focus exclusively on name-calling. I wonder why that is?

@Paul

Why are you ignoring infinite paths? an infinite path is not the same as "as long as you want it". it literally means "no last node". so your enumeration could never name these infinite paths because the naming itself is based on the last node of the path.

And the tree that i'm talking about (the one described in my test, with infinitely long paths) does contain infinitely long elements, it contains all real numbers between 0 an 1, including rationals, irrationals, even the non describable, non computable ones.

@vila,

Actually, I'm not ignoring infinite paths. A binary tree extends out to infinity. N extends out to infinity. They both go out in the same direction, so we can map one to the other.

However, as Chad warned me long ago, while we can talk about going to infinity, we can't ever assume that we are going to get there. Pi doesn't "go to infinity", it is already at infinity. The number itself is infinitely long, by definition. It just is. Because it is already there, a tree that is gradually getting there, will never contain it. But the tree is still countable, because we can map it's single infinity to the one in N.

So, back in my post about Infinite Node Trees, you'll see that I had to be creative. One 'type' of infinity is countable. Cantor's sequences have two types, one for the elements and one for the sequence. Two types is countable and diagonalizable. However a magic sequence has three 'types'. At three, things are still countable, but the diagonalization has dropped out.

Cantor was right about there being multiple 'types' of infinity. He just was unable to find an example that contained more than two, so that is how he constructed his proof. I guessed at three, and then just started back-peddling until I found a way to create something 'like' a sequence that contained 'three', thus my "magic sequences". They don't fit into sequences because of the extra 'type' of infinity.

Paul.

@Paul.

"Actually, I'm not ignoring infinite paths. A binary tree extends out to infinity. N extends out to infinity. They both go out in the same direction, so we can map one to the other."

No, the fact that both extend to infinity does not imply that you can map one into the other. That's the whole point of the different types of infinities.

I'm not sure what you're trying to say in general, all I gather is that you're trying to prove that you can find a 1-1 mapping between N and R.

So, of the following statements, which one do you think is wrong:

- If N maps 1-1 to R, then R must be enumerable.
- If R is enumerable, it means that you can list all the elements of R, and even though this will be an infinite list, any real number will eventually appear in this list.
- Given this infinite list, cantor's diagonalization shows how you can build a number that is not in the list.
- Therefore any listing of real numbers is bound to leave a real number out.
- Therefore you can't list all the elements of R.
- therefore R cannot be mapped 1-1 with N.

You must think one of these is wrong. If you don't, then I just can't see how you can think that R maps to N. Please tell me which step do you think is wrong.

@vila,

"No, the fact that both extend to infinity does not imply that you can map one into the other. That's the whole point of the different types of infinities."

Well, it's the number of them you are dealing with that makes them different 'types'. It's roughly analogous to 1D, 2D and 3D, where anything going off to one infinity can be mapped to any other thing going off to one infinity. Any thing going off to two infinities, can be mapped to any other thing going off to two infinities. Etc.

Still, there is one hitch in the perspective, reals are already at infinity. In a binary tree that means we never get there, so I can't map one to the other. But in Cantor's diagonalization it turns out the element we are creating is already at infinity too, so we can map the nth digit from the nth infinite element properly.

As for what I am saying, right now I'm just pointing out that binary trees are countable. At my blog site I am saying that there exists a magic sequence that is countable, but not diagonalizable. Earlier today I suggested that that new object may be responsible for the flawed assertion that binary trees are NOT countable.

As for R and N, well, last night I was preparing my second post and I found that there was still one last technical hurdle that I needed to pass, and as of right now I don't know how to do that. I plan to think about it for a few days, and then I will post the results. It's entirely possible that what I will post will be a first principles proof (independent of sequences) that decisively shows that the irrationals are NOT countable. Or not. I'm still working through my understanding.

Paul.

If there is a magic sequence that is countable, but not diagonalizable, perhaps you could write it down, and then feed it into my computer program, which will magically fail to produce a new real/subset-of-the-naturals, along with a proof that it isn't in your list. :)

Also, the different infinities are not related to dimensions. If you have a plane with two countably infinite dimensions, you can put its points into correspondence with a single countably infinite dimension (the product of two countably infinite sets is countably infinite). And in fact, you can prove that for any finite number of countably infinite sets, their product is countably infinite (though not for a countably infinite number of countable sets; that'd give you a set of infinite strings with a countable alphabet).

@Dan,

Change your program to allow it to take a magic sequence as input, not just a sequence, then use the subset in my post:

http://theprogrammersparadox.blogspot.com/2009/12/magic-sequence.html

But be careful, if you do it correctly, your program will NEVER halt.

If you have two infinite dimensions, when counting them, the traversal will zigzag back and forth between them extending out into it's OWN dimension. If you want a visual example goto my post called "Prime Perspectives" and look at the first graph. It won't be exactly the same, but it will probably look very similar (since it must extend out in two directions at once without missing anything in either axis). The x axis goes to infinity, the y axis goes to infinity and the traversal itself also goes to infinity.

Paul.
Paul.

@paul

"Well, it's the number of them you are dealing with that makes them different 'types'. It's roughly analogous to 1D, 2D and 3D, where anything going off to one infinity can be mapped to any other thing going off to one infinity. Any thing going off to two infinities, can be mapped to any other thing going off to two infinities. Etc."

I don't see the rough analogy. You can easily map naturals in 1D to the naturals in 2D, 3D, 4D or whatever.

"reals are already at infinity"

I don't understand this at all. in what sense are reals already "at infinity". are naturals not already "at infinity". could you please elaborate?

@vila,

N is { 1, 2, 3, 4, ...} which is basically one axis.

Pi is 3.14156..., where the ... implies ALL of the digits of Pi. All of them, right now, right there buried in my symbol for Pi. It's a different usage for "..." then the one in N.

A sequence of R has two different types of "..." symbols. The one in the set, and the one on the reals themselves.

A magic sequence (if writable) has three different "..." symbols. The one on the reals, the one for the sub-sequences and ANOTHER one to repeat the sub-sequences themselves. The double ellipse.

If you start with two axises, and you apply a function it is really an independent line that is winding it's way through the 2D space. The line itself stretches out infinitely to some point independent of either axis.

In counting, we want a line to cover "everywhere" as it gradually goes out to it's own infinity. Thus we know how big "everywhere" really is. It's way easier to think of it as a "traversal" of all possible elements on both axises, and we don't want to miss any elements.

Getting back to Pi, it is infinity long. If you truncate it at it's 206 digit, the number you have is slightly less than Pi. So you can't ever truncate it (ever). A simple rational like 3.0 is finite in length, but we can also represent it infinitely: 3.0000000....

So, the "..." symbols in the set represent axises and the "..." symbols attached to reals represent a number that is already at infinity.

Paul.

What is the type of a magic sequence? And once I have a type of magic sequences, how do I write a program that encodes your specific magic sequence?

Your diagram:

0.10000...
0.11000...
0.11100...
...
0.01000...
0.01100...
0.01110...
...
...

appears to be a countable union of countable sets, which is indeed countable (roughly, your sequence is similar to the countable ordinal Ï*Ï). However, it has a problem: all the elements you show have finitely many zeros, followed by finitely many ones, followed by infinitely many zeroes. The inner ellipses represent adding ones, and the outer ellipses represent adding leading zeroes (I assume). But, that means, for instance, that there is no '0.101000...' in your magic sequence, off the top of my head. Also, no '0.10101010...'.

To answer my initial question for myself, I'd posit that your magic sequences have type â â â â (â â Bool). That is, you need to give a natural for one of the infinite subsequences, and then you need to identify an element of that sequence, and it will give you a subset of the naturals. But, one can come up with a scheme for turning that into a â â (â â Bool) (zig-zagging through a table of pairs, for instance), and then my diagonalization function can be applied to that to yield something that isn't in the magic sequence.

So, I'm afraid this construction does not work. I'll see if I can construct a demonstration in Agda.

Also, incidentally, your illustration of diagonalization uses '2' as a digit. This is used in diagonalization proofs of reals because they're represented in trinary. With reals, you need to be careful because, in binary '0.011111...' is the same as '0.1000...', and the diagonalization may well produce the former, while the latter may be in the list or vice versa. With trinary numbers, one can always pick either a 0 or 1 for the new digit, avoiding '0.0222...' = '0.1000...' and such. But if the numbers are written in trinary, then a magic sequence containing reals with only 0s and 1s as digits misses quite a lot of numbers containing 2 as a digit, as well.

I think your terminology is terminally confusing. what about N x N? its got two axis and its still enumerable.

how about all the rational numbers between 0 and 1, you can list them in decimal notation in an infinite list with the same two dimensions, infinite going down and infinite going left, but they are ALSO enumerable.

@Dan,

"What is the type of a magic sequence?"

The type is "magic sequence". That's why I had to create a new mathematical object.

"So, I'm afraid this construction does not work."

The numbers are all R in base 10, that's why I used 2 later, just to emphasis that point. The first type of ellipse adds another 1. The second type pushed down the first sequence by 0. And of course, there is a third one on each real itself.

"how do I write a program that encodes your specific magic sequence?"

It's a halting problem, I don't think you can.

What is happening? The magic sequence itself is a larger object than you can represent in your formal system (computer or Turing machine if you prefer). It defies validation checking with a program.

Paul.

@vila,

Any two axises will always be enumerable. In fact I think any number of "goes to" axises will always be enumerable (it's this possibility that started all of this). I haven't yet given much consideration to infinities on the reals themselves, and how they interact with the "goes to" axises.

Magic sequences are an example of what Hofstadter called "strange loops" in GEB. Basically they are horribly confusing. Given that, this one appears to have been unnoticed for 139 years or so, so it's bound to be one of the more confusing ones.

Paul.

@Dan,

OK, I'm wrong about something. You can fit the sequence I gave you into a known structure (I should have guessed this).

Open up a spreadsheet and in each cell add in the complete R.

Now, before you leap to the conclusion that just because the cells are enumerable, the thing is diagonlizable, start tracing out the enumeration one cell at a time.

In a simple algorithm we start with 0,0 then goto 0,1 then 1,0, then 0,2 1,1, and 2,0. We've been traversing at a diagonal, one diagonal at a time.

We've covered 6 elements, but only moved 2 positions on either axis. Now we are tired, and we want to just match our line's "..." up with something, but which axis? If we map the line's "..." to x, then we miss all of the values on Y, and vice versa. So we can start the diagonalization, but we can't finish it, and the farther we go, the more elements we fall behind. We're no longer getting the nth digit from the nth element, we getting it from the sqrt(n) element. Can't stop and losing elements.

Paul.

If the numbers are decimal, then the magic sequence (trivially) misses all the reals with the digits 2-9.

I'm afraid I don't believe that your magic sequences aren't encodable in my type theory, and that the one you've written down is uncomputable. For instance, see here. I have a proposed type 'Magic', and a value 'magic' that appears to me to be the sequence on your blog. I then show how to turn it into a function that works for my 'cantor' function.

So, what's wrong with my formalization? You yourself even have a mapping from natural numbers to reals in the magic sequence (although it's different than mine). Why is it impossible to compute the element of the sequence corresponding to the natural you've labeled it with?

And if my formal system isn't powerful enough to describe magic sequences, what is a formal system that is? And can you show how to describe magic sequences in that system? And can you show where the diagonal argument fails on that formal representation? I'm afraid I'm not going to believe you've found a counter-example to Cantor's (quite simple) proof based only on a drawing and hand-waving description. If you're right, it can be made more rigorous, and if you're wrong, attempting to make it rigorous will help identify where you are wrong.

now you're invoking hofstadter's strange loops? "goes to"? good luck with the magic.

@Dan,

Yes, sorry, as I said in my last comment, it fits into your formal system. It fits into a spreadsheet.

Which if you have been following what I've said about infinities makes perfect sense. The spreadsheet heads off to two different infinities (the rows, and the columns), and each cell holds an infinite real. So we have the three infinities necessary to match the ellipses in my example.

Of course, all along I've said that this is countable. So you can zig-zag through all of the cells in the spreadsheet and assign each one an incrementing number, thus counting them.

For Cantor's diagonalization argument to work, the element constructed MUST be made up of exactly one digit from every member of the sequence. If you miss ANY members, then you cannot say conclusively that your newly constructed element is not one of them. This is a huge point in his argument. And to enforce this, he explicitly requires that the nth digit of the new number comes from the nth element in the sequence. They have to match, all the way towards infinity, or you can't guarantee that you haven't missed something.

So, we have this spreadsheet, full of cells of infinite numbers, and we want to pick the nth digit of each number for our construction. The only way to do this is to head down a single row or column. That is, you must take the nth digit from the nth cell, in a straight line. That guarantees that you cover exactly n elements. If you try to weave you will be adding in digits faster than then you will be headed towards infinity. As your construction heads to infinity, the actual number of elements will be headed there N^2 faster.

Basically you will construct an element from a single row in the spreadsheet, and then claim that because the element is not in that row, it must also not be in the table either, which would be a false conclusion. That's why Cantor specifies that the nth digit come from exactly the nth element.

Another point: If you apply your computer program to any regular sequence in an attempt to prove that it is missing something, your program is inherently incorrect. Since you can't wait for your program to construct an element of infinite length, somewhere in your code, you stop and apply an approximation. Because of that, and because you haven't checked all of the elements in the sequence your code can't actually prove anything. Not conclusively.

We can do so in set theory because we can manipulate the symbolic "..." in a way to essentially cancel them out. That is, I don't actually need to construct the element, I just need to know that I can. And I can with a regular sequence because the nth digit is guarantee to come from the nth element, so I can prove that I didn't miss anything. A computer can't show that, it has to approximate, which is invalid. You're simply showing that some part of the sequence does not contain the element, not that all of it doesn't.

A counter-example is rigorous. I provided a really short and simple one. The hand-waving is only because everyone is having a really hard time understanding what I am saying. Well, to be precise, everyone is having a really hard time with the idea that there could actually be something wrong with Cantor's argument that has gone unnoticed for such a long time.

Paul.

It doesn't matter that the spreadsheet is two dimensional. I can create a surjective mapping from the naturals â to the product of the naturals with itself â^2. For every (i,j) in â^2, there will be a natural n such that my mapping sends n to (i,j). My program does this. And that product set is obviously in correspondence with the cells of the spreadsheet. So, composing the two correspondences together, I have a mapping from the naturals â to cells in the spreadsheet, such that every cell is covered.

It doesn't matter that cells in a single row or column are covered 'faster' if you only go down that single row or column. My mapping covers all the cells. I could prove that my 'zig-zag : Stream (â Ã â)' really contains all pairs of natural numbers if necessary. I just didn't because it seemed like it would be tedious.

Once we have a mapping from â to every cell in the spreadsheet, we can use the diagonalization argument. It does not construct a diagonal of a single row or column. It constructs a diagonal using the entire spreadsheet; the diagonal of the zig-zag path. The 0th bit of the diagonal is the negation of the 0th bit of the (0,0) cell. The 1st bit of the diagonal is the negation of the first bit of the (1,0) cell. The second bit is the negation of the second bit of the (0,1) cell. And so on.

This is not an approximation. We don't have to wait to see the entire output of the diagonal construction to know that it isn't in the mapping from â to â -> Bool. The language I'm using allows you to encode theorems about programs in the type system, and if the program type checks, those theorems have been verified, unless the logic is unsound, or there's a bug in the type checker. So what I'm presenting is about as good as having a computer verified proof of Cantor's argument in set theory, with the side benefit that one can fiddle with having the computer show (bits of) the specific Cantor diagonal of candidate bijections.

A counter-example would be rigorous. I showed that what you proposed could be diagonalized, as far as I understood it. I even gave you a couple specific numbers that didn't appear to be in your sequence, and you never explained where they were. I have what I think is a pretty good formal model of a spreadsheet-of-infinite-extent with my â -> â -> T (for a spreadsheet with cells holding Ts). But I've shown how to perform the diagonal construction on that. So if that isn't satisfactory, then what is an appropriate formal model for a spreadsheet, and let's see a formal proof that you can both fill it with every real number, and put the cells in correspondence with the natural numbers, but not perform Cantor's argument once you do that.

People are having a hard time with the idea that Cantor was wrong because there are relatively simple, machine checkable formalizations of his argument, and your sequences are pretty clearly still subject to it.

@93, 96:

Observer said:

As usual, Mark CC clams up once proven wrong. The tree obviously has countably many vertices, and equally obviously has uncountably many paths.

I, too, initially thought that Mark was wrong about this. But then I discovered that there's a set-theoretic notion of tree that's quite a bit more general than the graph-theoretic notion, and this is the kind of tree that Conway works with for the surreal numbers. See my comment #70.

Mark C. Chu-Carroll said:

Obviously, you can't ever construct those nodes, by the very definition of Ï.

They can't be constructed if your tree is only graph-theoretic, because there's no natural edge relationship for the new nodes. However, a set-theoretic tree allows exactly this type of construction.

I smell a good topic for a new post, since it seems that no one was fully aware of all the nuances involved here. You were quite correct about the Conway-type construction, but a lot of confusion came of the fact that we all seemed to be stuck with the idea of graph-theoretic trees, and the Conway construction doesn't fit into that framework.

@Paul W Homer:

You're talking complete nonsense.

Look, this isn't a conspiracy. These people who are responding to you, here and in your blog, are disagreeing not because they don't "get it" but because what you're saying is hopelessly confused and wrong.

Their understanding of logic, computability and set theory far surpasses yours, whether you admit it to yourself or not.

Consider that 'magic sequence' of yours. You yourself have shown that the sequence is countable, because you were able to assign natural numbers to the left hand column in such a way that every natural number was used and no two rows had the same number.

OK, so for natural numbers n, let's define x_n to be the sequence of 1's and 0's in the unique row to which you assigned the number n. With me so far?

Now let's define a sequence of 1's and 0's called y, as follows: The n-th entry of y is 1 if the n-th entry of x_n is 0, or else 0 if the n-th entry of x_n is 1.

Then y does not belong to the magic sequence.

I've annotated my code here with a revised copy that contains a proof that zig-zag in fact contains all pairs of integers (I fiddled with some of the previous definitions, too, to make it easier to prove things about them). So, magic is a spreadsheet of infinite extent, zig-zag is a stream enumerating all pairs of integers, and flat-magic takes an integer n, uses zig-zag to find a pair corresponding to that number, and returns the value of the spreadsheet cell corresponding to that pair. So flat-magic enumerates everything in the spreadsheet, but it can be used in the cantor function to construct a value that does not appear in the spreadsheet.

@Neil,

I understand your frustration. I do. But, to go back to my debugging metaphor, this is not my program. I didn't write the source, all I am doing is telling you want your problem is.

"Their understanding of logic, computability and set theory far surpasses yours, whether you admit it to yourself or not."

Mathematics is an abstract formal system. It is what it is regardless of how much I personally know about it. It's entirely possible that some person buried deep in the Amazon jungle knows as much, if not more about set theory, then any living person. I'm not saying it's true, but just that it is a possibility you can not discount.

As a side-point, I often end up helping other programmers debug their code too. In those cases, I don't need to fully understand the purpose or all of the code, in order to provide assistance. I just need to know enough to help them trace down the bug.

@Dan,

"It doesn't matter that the spreadsheet is two dimensional."

Yes it does. It's exactly that point that you've missed! Again: Cantor picks the nth digit from the nth element because if he didn't there is no way to *guarantee* that the constructed element is not "somewhere else" in the sequence.

If you only use an infinitesimally small part of the sequence to generate the element, it invalidates the argument.

If you only generate the element from one single row or column of the two-dimensional sequence, then you have absolutely no idea as to whether or not that element exists in the other rows and columns of the table.

If you try to use all of the elements, the construction will NOT halt.

That's not a guess, that's not magic, that is a basic mathematical fact.

OK, lets try again. I've provided two perspectives of this so far, maybe three is the charm:

Lets start with a 10x10 square. This cube contains 100 elements. If we enumerate the first 10 elements, then there are 90 elements we have NOT yet enumerated.

Lets double our x and y axis to a 20x20 square. We enumerate the next 20 elements, and we now how 380 non-enumerated elements. Lets call this a tick (like the tick of a clock).

Each time we tick, we add 10 more elements to X, and 10 more elements to Y. Each time we tick, we enumerate 10 more elements.

Our cube is growing at N^2, our enumeration is growing at N. As we approach infinity, our cube is growing soooo much faster than our enumeration. If at any point in the approach, we "declare" that we've constructed the element, our element has enumerated only N elements, while the cube has grown to N^2.

Precisely that means that we can either "never declare" success, or we've only created the element out of one single row or column of the table. Either way, the diagonalization fails.

Paul.

:)

@Dan,

"I even gave you a couple specific numbers that didn't appear to be in your sequence, and you never explained where they were."

My example only shows that magic sequences exist, and that Cantor's dagonalization argument can't be applied to them.

The example I gave was trivially NOT a mapping from R->N, it's only purpose is to show that it can NOT be represented as a sequence, but it can still be counted.

It exists to show that:

a) there are magic sequneces != normal sequences
b) countable != diagonalizable
c) you can't apply Cantor's argument to a magic sequence, only to the normal ones.

That is all. (so don't think that by accepting the existence of magic sequences that I am somehow tricking you into saying R->N, they are completely different issues.)

Paul.

Paul: Neil's comments are right on. Let me be more clear: you don't know what the fuck you're talking about.

Now run along. Anyone who's interested in your magical shite can visit your blog. Don't worry, I'm sure your mathematical genius will be recognized someday.

No, I'm afraid you are wrong. There is nothing non-halting about using every element of an infinite, 2D spreadsheet. At least, nothing more non-halting than using a single, 1-dimensional list of numbers. I can be precise about this, even.

First, let's talk about what our reals/subsets are. They're functions (â -> Bool). In Agda, that means that given a natural number, they produce boolean in a finite amount of time (this constraint would be relaxed in set theory). The language ensures this when doing type checking.

Now, a spreadsheet of infinite extent is a function with type â -> â -> T for values of type T. This means that given two integers i and j, it produces an element of T within a finite amount of time.

Now, I also wrote a function with type â -> â*â in the language. This is a terminating function from the naturals to the pairs of naturals. I also proved that the range of the function contains every pair of naturals. So, if you started enumerating the pairs, you'd reach every pair in a finite amount of time, just like you'd reach every integer in a finite amount of time.

By combining these two, we can construct a function with type â -> (â -> Bool). This function takes a natural, and in a finite amount of time produces a subset/real. It also, because the zig-zag function above produces every pair of reals, produces every element in the spreadsheet. If you started enumerating all the results of the function, you'd get to each one in a finite amount of time (you can't print real numbers to the screen, though, because each one potentially takes an infinite amount of time to print; but that doesn't actually matter).

The cantor diagonal function takes a function like the last one, and produces a new subset/real. It does this by asking for the nth digit of the nth element of the sequence, and using some other digit for its nth element. But, this fits the profile for a subset above. Given n, it takes a finite amount of time to produce (i,j), and then it takes a finite amount of time to find the value at spreadsheet cell (i,j), and then it takes a finite amount of time to find the nth digit of that cell, and then we choose some other digit and return it, all in a finite amount of time.

So there you have it. There's nothing non-terminating about this diagonalization beyond a normal one. And if we generalize to non-computable reals (as in classical set theory; or even non-computable spreadsheets), then the zig-zagging part remains the same, it's just the real numbers (and spreadsheet) that become unable to be represented on a Turing machine (we still have a computable method for enumerating the spreadsheet linearly).

So, I'm afraid you are incorrect. 100*100 is bigger than 100. But |â|*|â| = |â|. It's one of the oddities about infinite cardinals. You could create a system where that wasn't true, but, as I explained above, the current situation is a pretty good match for even aspects of computation. There's also the ordinals, where there are many different countable infinities, but those do not describe the sizes of sets, and all the different countable ordinals (as typically defined as sets) have the same number of elements (the same number as the naturals).

You may disagree with the conclusions of set theory. But you have not found a counter example within set theory. You have found an informal "I don't think this should be allowed" objection to the system, and will have to come up with a new system with new axioms that don't allow your objection if you want to work in a mathematical framework that matches your intuitions.

I believe my nomenclature was different from yours.

Clearly there are a countable number of nodes: here is a perfect scheme for counting them. Left to right, followed by a 'carriage return'. thus, node 1 is the top. Nodes 2 through 11 are in the first row. Nodes 12 through 111 are in the second. Etc. No node will ever be missed.

However, by 'path' I did not mean 'segment connecting two nodes'. I meant 'infinitly long series of segments starting at the top'. There are clearly uncountably many 'paths', as they each are a representation of a number of (0,1), and fill that space.

I suppose for rigor's sake (not that I've been rigorous in any way) I should have said 'sequence', not 'series'.

@Dan,

Jim is right. This discussion has run its course here.

If you want to continue discussing this (and I hope you do), then please re-post your comment at my site.

Thanks,

Paul.

Just saw 121.

Yes, I'm doing graph theoretic trees, and the original tree in this discussion clearly is one. Each node is connected to eleven segments, the one descending into it, and the ten descending from it.

Thus, the cardinality of the NODES is the same as the cardinality of all finite strings of natural numbers, which is countable. The cardinality of the paths is equal to c.

@129, 130:

You're still ignoring the key thing - the extension to path-length ω. When you do that, you get a "tree" in which the leaves are the real numbers. The length of the path to those nodes is ω - so your enumeration will never reach them. You'll never output 1/3 in your enumeration - As you keep going, you'll enumerate closer and closer approximations of it, but you'll never actually reach it. But in the infinite construction, where you have nodes with path-length ω, you've got a one-to-one correspondence between paths and nodes - a 1:1 correspondence between
paths from the root to the nodes and nodes. But you have nodes whose path has length ω.

The set-theoretic infinite construction doesn't have paths which don't terminate in nodes. It's counter-intuitive, but playing with infinities is pretty much always counterintuitive. In the infinite construction, you can talk about the termination of an infinite path.

Like I keep saying: go read some Conway. He explains much better than I do, and for anyone interested in this kind of stuff, he's so much fun to read that you should do it just for the pleasure.

Obviously the enumeration is going to miss some 'numbers'. I don't claim to enumerate the reals! I claim to enumerate the nodes of this tree, which correspond to finite strings of the digits {0,9}.

The enumeration of the rationals is similar to this.

Yes, the extension to (omega) (I don't know how to do the symbol) changes everything. Once dealing in ordinals enumerations go all wonky.

That comment about the rationals should have been deleted along with the stuff to which it was meant to refer.

Incidentally, Cantor's argument doesn't necessarily demonstrate that there are more reals than naturals. It all depends on what sort of theory you're working in.

Agda, for instance, is a constructive type theory. Every Agda function must be given by an algorithm for computing that function, and algorithms are represented by finite character strings. If we do analysis on Agda inside some meta theory, we can clearly see that there are countably many Agda functions, because finite character strings can be put into correspondence with the naturals. But, subsets of the naturals have been represented by functions â -> Bool, so there must be countably many subsets of the naturals in Agda. (You can translate all this stuff to set theory by tacking "computable" onto whatever you want to talk about. There are countably many computable reals, for instance.)

But, inside Agda, Cantor's argument still works. Given any Agda function â -> (â -> Bool), there is a â -> Bool that is missing, and one can compute an example. Does this mean that our meta theoretic analysis is wrong? No, because we're not using Cantor's argument on meta-theoretic functions, we're using it on Agda (computable) functions. What it means is that any computable mapping from the naturals into the computable subsets of the naturals misses some computable subsets. But this can be attributed to restrictions on the behavior of computable functions, rather than the idea that there are "more" of one thing than another.

Functions in classical set theory are a lot less restricted than (computable) functions in intuitionistic theories, so it makes more sense to interpret Cantor's argument as showing a size difference there.

@133:

The set-theoretic infinite construction doesn't have paths which don't terminate in nodes. It's counter-intuitive, but playing with infinities is pretty much always counterintuitive.

Hmm. I actually think it's fairly intuitive. It's just that it's not the way that graph-theoretic trees work, which is what everyone is thinking of when you say tree.

So I don't think you can blame those of us who were claiming you were wrong and asking for clarification. You were wrong in the sense that you didn't realize (as far as I can tell) that you were using a different kind of tree.

@133, Just a small nit:

Strictly speaking, a branch of length omega with a node at the end of it constitutes a branch of length omega+1.

Here is what Cantor's "constructive proof" looks like, applied to the tree. I've briefly skimmed over the comments above and it didn't look like it was given before.

Any two numberings of the tree are equivalent up to a unique isomorphism. That means, we can start counting where ever we want. Any numbering someone else comes up with can be mapped to the one given below by just stating a (countable) one-to-one mapping.

So, let's take the number

0.11111111111111...

with infinitely many 1s. This number is in R, and hence it must be in the tree. Let's assign this number 0.

Let's take another number, that one:

0.21111111111111....

the number with a 2 at the first decimal place followed by infinitely many 1s and assign it number 1.

We continue like that, assigning number n of N to the number of R where the n-th decimal place is a two, and all other, up to inifnity, are 1s.

Here is the mapping:

0 = 0.111111111111111...
1 = 0.211111111111111...
2 = 0.121111111111111...
3 = 0.112111111111111...
.
.
.

If we continue this for all n in N, we will have used up all natural numbers just to count the nodes of the tree matching the schema above. There is no natural number left to assign the number (node of the tree)

0.2222222222222222....

to. Hence, we've constructed a counterexample, hence there cannot be any numbering of the tree. Hence the tree contains uncountably many nodes.

Okay, forget what I wrote above, it doesn't work that way. It must be more like:

The set of all infinite binary sequences is uncountable.
The tree contains all infinite binary sequences.

@139 The problem is that you are constructing your own mapping here, instead of using a given one. Furthermore, you cannot "use up all natural number's" The infinite hotel paradox gives a nice example of this:
http://en.wikipedia.org/wiki/Hilbert%27s_paradox_of_the_Grand_Hotel

If you skip numbers in the diagonalisation, you have to make certain that the counterexample you have created is not one of the skipped numbers.

I'm interested in how 'tree' is defined Mark's way.

@141: but if numbers are "skipped" in that some reals are not associated to naturals, then we don't have a bijection to begin with.

@142:

I already linked to wikipedia on this topic, but here ya go:

What most people mean by "tree"

Set-theoretic trees, which allow Mark's construction with heights greater than Ï.

By the way, you're still wrong about cardinal expressions, but I don't see a way to explain it better than I already have.

@142:

I already linked to wikipedia on this topic, but here ya go:

What most people mean by "tree"

Set-theoretic trees, which allow Mark's construction with heights greater than Ï.

@mike:

By the way, you might read wikipedia on cardinal expressions and tell me if you still think that 10a isn't a valid expression or that 2a is "just notation" (where a is any cardinal number).

As I do not claim to understand these arguments, is it the opinion of people here that Gabriel is a total crank, or do any of his other articles make more sense? [I posted a comment on his What Is An Average to see what kind of response, if any, I get.]

Well, what do you know, my comments and question got deleted without response. Basically I suggested that (besides being useless) the way to average rainfall over three cities was to weight based on area. This apparently did not please Mr Gabriel.
[And name today is name rather than some url, at least in preview.]

Cantor was a crank? Some people need to be cranked upside the head. Guy went literally "where no man has gone before." Cost him his reputation and his sanity, so ease up on the legend that opened the curtains on this beautiful vista... is what I'm saying. ;)

No one shall remove Cantor's fools from the fools paradise he created for them.

@133 (Mark):

The length of the path to those nodes is Ï - so your enumeration will never reach them.

As one of the resident Cantor crackpots, I was wondering if I may inquire on a few points.

The flaw in Cantor's argument is the same as I see in your quote IF I'm interpreting your comment correctly. Do I understand correctly that because the path is |N| in length, then we must have enumerated at least that many nodes to get to it and because we know there are other nodes, then it cannot be reached? Or at the very least, we cannot enumerate any other nodes that are not along the path.

If this is incorrect, could someone clarify?

If it is correct, why is it not possible for the cardinality of the path to be different than the cardinality of the nodes? We know this is possible since Dedekind's theorem says that a proper subset of an infinite set can map to said infinite set. Being a proper subset, this means that |A|<|B| until they are remapped one to one.

Failure to take into account Dedekind's theorem is what I see as the flaw in Cantor's diagonal argument.

If you have countably infinite digits on one axis, then each digit (assuming 0-1) will double the number of representations possible. So what Cantor is trying to prove is that the the horizontal axis (digits) is not a proper subset of the vertical axis (reals). However, at no point during his "proof" do I see him attempt to remap the two axis to each other one to one. In fact, no matter what list I give you, you insist on using the original mapping where |H|<|V|.

I fully accept Cantor's diagonal argument in that |H|<|V| as long as the enumeration is related to the digits. But this says nothing about being able to remap the two axis as per Dedekind's theorem. The diagonal is the very flaw in Cantor's argument.

The only difference I see between reals and naturals are if you don't allow naturals to be represented by infinite digits or other indeterminate forms such as i/|N| or i>>|N| (shift, both forms are equivalent). This would allow things such as the "middle" natural. This is indeterminate. But if Cantor sees sets as "complete", then such notions should be possible, no?

I guess the true question is how many digits do you need to represent all naturals? And does this extend to any single natural?

(Corrected less than sign. Sorry for double post)

@133 (Mark):

The length of the path to those nodes is Ï - so your enumeration will never reach them.

As one of the resident Cantor crackpots, I was wondering if I may inquire on a few points.

The flaw in Cantor's argument is the same as I see in your quote IF I'm interpreting your comment correctly. Do I understand correctly that because the path is |N| in length, then we must have enumerated at least that many nodes to get to it and because we know there are other nodes, then it cannot be reached? Or at the very least, we cannot enumerate any other nodes that are not along the path.

If this is incorrect, could someone clarify?

If it is correct, why is it not possible for the cardinality of the path to be different than the cardinality of the nodes? We know this is possible since Dedekind's theorem says that a proper subset of an infinite set can map to said infinite set. Being a proper subset, this means that |A|<|B| until they are remapped one to one.

Failure to take into account Dedekind's theorem is what I see as the flaw in Cantor's diagonal argument.

If you have countably infinite digits on one axis, then each digit (assuming 0-1) will double the number of representations possible. So what Cantor is trying to prove is that the the horizontal axis (digits) is not a proper subset of the vertical axis (reals). However, at no point during his "proof" do I see him attempt to remap the two axis to each other one to one. In fact, no matter what list I give you, you insist on using the original mapping where |H|<|V|.

I fully accept Cantor's diagonal argument in that |H|<|V| as long as the enumeration is related to the digits. But this says nothing about being able to remap the two axis as per Dedekind's theorem. The diagonal is the very flaw in Cantor's argument.

The only difference I see between reals and naturals are if you don't allow naturals to be represented by infinite digits or other indeterminate forms such as i/|N| or i>>|N| (shift, both forms are equivalent). This would allow things such as the "middle" natural. This is indeterminate. But if Cantor sees sets as "complete", then such notions should be possible, no?

I guess the true question is how many digits do you need to represent all naturals? And does this extend to any single natural?

(Can't get less than sign to work. Sorry for triple post)

@133 (Mark):

The length of the path to those nodes is Ï - so your enumeration will never reach them.

As one of the resident Cantor crackpots, I was wondering if I may inquire on a few points.

The flaw in Cantor's argument is the same as I see in your quote IF I'm interpreting your comment correctly. Do I understand correctly that because the path is |N| in length, then we must have enumerated at least that many nodes to get to it and because we know there are other nodes, then it cannot be reached? Or at the very least, we cannot enumerate any other nodes that are not along the path.

If this is incorrect, could someone clarify?

If it is correct, why is it not possible for the cardinality of the path to be different than the cardinality of the nodes? We know this is possible since Dedekind's theorem says that a proper subset of an infinite set can map to said infinite set. Being a proper subset, this means that |A| less than |B| until they are remapped one to one.

Failure to take into account Dedekind's theorem is what I see as the flaw in Cantor's diagonal argument.

If you have countably infinite digits on one axis, then each digit (assuming 0-1) will double the number of representations possible. So what Cantor is trying to prove is that the the horizontal axis (digits) is not a proper subset of the vertical axis (reals). However, at no point during his "proof" do I see him attempt to remap the two axis to each other one to one. In fact, no matter what list I give you, you insist on using the original mapping where |H| less than |V|.

I fully accept Cantor's diagonal argument in that |H| less than |V| as long as the enumeration is related to the digits. But this says nothing about being able to remap the two axis as per Dedekind's theorem. The diagonal is the very flaw in Cantor's argument.

The only difference I see between reals and naturals are if you don't allow naturals to be represented by infinite digits or other indeterminate forms such as i/|N| or i>>|N| (shift, both forms are equivalent). This would allow things such as the "middle" natural. This is indeterminate. But if Cantor sees sets as "complete", then such notions should be possible, no?

I guess the true question is how many digits do you need to represent all naturals? And does this extend to any single natural?

Too bad Cantor's diagonalization produces just one counterexample for each mapping. Happily, one can create an infinty of counterexamples without too much more work. We first take our list of sequences which we have in base 2 and produce a counterexample. We then convert each member of that list into base 3. Then instead of taking 1-d for each digit in the counterexample (swapping 1 to 0 and vice versa) we take (d+1)(mod 3) for another POSSIBLE counterexample and (d+2)(mod 3) for another possbile counterexample. Then we convert each member into base 4 and take (d+1)(mod 4), (d+2)(mod 4), and (d+3)(mod 4) for three more possible counterexamples, and so on with the general form as for base n we take (d+1)(mod n), ..., (d+(n-1))(mod n) for n-1 counterexamples.

Of course one will object that this really shouldn't work. However, since we only use approximations to begin with, when switching bases we end up using different numbers, so not all of the counterexamples end up the same, and we should "end up" with an infinity of different counterexamples. Or at least that's my take... it's not quite so easy to prove.

"I guess the true question is how many digits do you need to represent all naturals?" Volrath

We can't represent all naturals. Either we have a representation system of digits which allows for an infinite creation of new digits for each distinct natural number, or we have a finite number of digits in base n which for any sequence of digits hkfi, with hkfih as a natural number unrepresented.

"The only difference I see between reals and naturals are if you don't allow naturals to be represented by infinite digits or other indeterminate forms such as i/|N| or i>>|N| (shift, both forms are equivalent)."

The actual value of a natural number (given that we can write it) can get communicated purely by truncating any digits after the decimal point, as all natural numbers have nothing but 0s after the decimal point. Non-natural, non-rational real numbers do not have this property. Additionally, for any natural number k one can produce an interval of length j, with j<1, where each member of the interval J comes as a real number that approximates the value of k. Thus we have an infinty of real numbers r_1, r_2, ... which approximates any given natural number n where abs(r_n-k)<1. If we start with a real number r, we can only find two natural numbers k_l and k_u which approximate r such that abs(k_l-r)<1 and abs(k_u-r)<1. On top of all this, any real number can get approximated by a DISTINCT real number within any given length j, where j does not equal 0. It does not hold that any natural number can get approximated by a distinct natural number within any given length j, where j does not equal 0.

The above should read

""The only difference I see between reals and naturals are if you don't allow naturals to be represented by infinite digits or other indeterminate forms such as i/|N| or i>>|N| (shift, both forms are equivalent)."

The actual value of a natural number (given that we can write it) can get communicated purely by truncating any digits after the decimal point, as all natural numbers have nothing but 0s after the decimal point. Non-natural, non-rational real numbers do not have this property. Additionally, for any natural number k one can produce an interval of length j, with j less than 1, which has an infinty of real members r such that abs(k-r) is less than 1. For any given real number r, one can only produce two naturals k_l and k_u such that abs(r-k_l) is less than 1 and abs(r-k_u) is less than 1. Additionally, for any desired interval of precision j, where j does not equal 0, for any real number r_1, we can approximate it by some r_2 such that abs(r_1-r_2) is less than j. For any desired interval of precision j, where j does not equal 0, for any natural number n_2, we CANNOT aproximate it by some n_2 such that abs(n_1-n_2) is lss than j.

Doug, your entire reply is shaky at best. Please keep the crackpottery to the pros. You don't quite have the hang of it yet though you're off to a good start.

We can't represent all naturals.

So you're saying you can't identify all the countable digits in Cantor's diagonal argument? That they don't map one to one with N? How does that work?

The actual value of a natural number (given that we can write it) can get communicated purely by truncating any digits after the decimal point, as all natural numbers have nothing but 0s after the decimal point.

You have it backwards. i is the natural. i/|N| is the real it maps to.

@154 (Doug),

Wanted to add that your last scenario is only true if you don't allow indeterminate forms for naturals (or their intervals) exactly as I said before. If you do allow indeterminate forms to represent naturals, then your argument falls apart.

"Doug, your entire reply is shaky at best." -Volrath

You certainly haven't shown such, and notice that I've presented certain difference which do exist. Please show which parts you consider "shaky" and explain why.

"We can't represent all naturals."

"So you're saying you can't identify all the countable digits in Cantor's diagonal argument?"

If we use base 2, then we can identify all the digits in Cantor's diagonal argumnet as 1 and 0. We still can't represent all naturals. For any proposed set of representations of all natural number there exists some other natural number which we haven't represented. Suppose our set ends with some extremely long sequence of digits which physically we can't even construct in the real universe in a finite base system with x digits, where x has more symbols for digits than physically unconstructable in our universe also. Since we have a finite base system, we can still plop the same sequence of digits on the end of that first sequence and have a distinct natural number which we didn't represent.

If you mean to ask if we can't identify *the sequence from the diagonal* of digits in Cantor's counterexample in the diagonal argument, you do speak correctly. We can only pair the concept of such a diagonal sequence with the infinite set of sequences which we used to create the idea of such a concept. We likewise cannot identify an infinite set of sequences which represents all natural numbers, as we really haven't created/discovered them all, and we've known we can't do such for millenia now.

"That they don't map one to one with N?"

They still map one to one with N.

"You have it backwards. i is the natural. i/|N| is the real it maps to."

Either I don't understand what you mean by 'i' or you mean the number sqrt(-1), in which case you've changed definitions by allowing sqrt(-1) to mean a natural number.

"Wanted to add that your last scenario is only true if you don't allow indeterminate forms for naturals (or their intervals) exactly as I said before. If you do allow indeterminate forms to represent naturals, then your argument falls apart."

No, and you haven't shown such.

Doug, your statements are so ridden with "tinfoil hattery" that I don't know where to begin. Take the last part. All you say is "No, and you haven't shown such." I explained it. It should be clear that using indeterminate forms for naturals counters your argument. There's not much else to add. However, it's not surprising that you don't understand because your statements are a complete waste of time. Take this beauty.

We likewise cannot identify an infinite set of sequences which represents all natural numbers, as we really haven't created/discovered them all, and we've known we can't do such for millenia now.

So you disagree with Cantor's diagonal? I want someone who agrees with it to answer my original questions in post 152.

I just have to quote another beauty of yours.

If we use base 2, then we can identify all the digits in Cantor's diagonal argumnet as 1 and 0. We still can't represent all naturals.

That one cracks me up. BTW, it's clear that you don't understand anything about Cantor's diagonal argument because this quote of yours demonstrates that you have no concept of enumerations.

Doug, you're completely bonkers.

"All you say is "No, and you haven't shown such." I explained it. It should be clear that using indeterminate forms for naturals counters your argument."

It doesn't work out as clear, and I see no reason why it should. Additionally, even if it should, that doesn't mean it does work out as clear. Without adding more you don't have an effective argument.

" We likewise cannot identify an infinite set of sequences which represents all natural numbers, as we really haven't created/discovered them all, and we've known we can't do such for millenia now.

So you disagree with Cantor's diagonal?"

No, I don't disagree with it, and I simply don't see how you infer that I do from the truism I stated above. Look, we may recognize a pattern which theoretically go on intermiably and thus produce a representation of all natural numbers, such as 0, 1, 10, 11, 100, 101, ... We may even specify a procedure which produces such a pattern and recognize it. However, we cannot identify the set of infinite objects, which comes as what the pattern would produce were it to go on infinitely.

"If we use base 2, then we can identify all the digits in Cantor's diagonal argumnet as 1 and 0. We still can't represent all naturals.

That one cracks me up."

If you think I've misspoken, then produce your represntation of ALL nautral numbers. Again, I don't want a pattern or a procedure which if carried on infinitely produces all natural numbers, I want an actual representation of all natural numbers. Without that, I haven't misspoke.

"BTW, it's clear that you don't understand anything about Cantor's diagonal argument because this quote of yours demonstrates that you have no concept of enumerations."

Just an attack here lacking substance. I didn't mention enumerations in the quoted part either. Additionally, using Mark's notion of enumeration "In an enumeration of a set, there will be some finite point in time at which any member of the set will be emitted by the enumeration. " We can't enumerate the set of natural numbers N, because there exists no finite point in time at which we can safely say that a random selection from N will match what has gotten emitted by the enumeration procedure. In fact, at any finite point in time, there exist infinitely more natural numbers in N than have gotten emitted by the enumeration procedure.

Mark,
I don't understand how you can say the tree does not contain all the rational numbers or any irrational numbers.

The top-down finite traversals produce every rational number - there is no exception here.

The left-right infinite traversals along a given path produce all the irrational numbers and also rational numbers that are not finitely represented in decimal notation.

Using Cantor's recipe, one is able to produce an imaginary list of real numbers in the interval (0,1).

Your arguments as I have seen so far are sheer nonsense.

The article has been revised since you last checked. I have added a section at the end which deals with Cantor's first uncountability theorem.

"The only difference I see between reals and naturals are if you don't allow naturals to be represented by infinite digits or other indeterminate forms such as i/|N| or i>>|N| (shift, both forms are equivalent)." -Volrath

If we allow naturals to get represented by indeterminate forms (like 0/0 in calculus, if that's what you mean by 'indeterminate form', if you mean something else, you need to clarify what you mean), then for some natural number r we have {r}={r}. But r can get said to equal floor(r) in one case and ceiling(r) in another, similar to how the indeterminate form 0/0 can get said to equal 1 when talking about lim x->0 (x/x), and 0/0 can get said to equal 0 when talking about lim x->0 (x^2/x). Consequently {r}={r} does not necessarily hold (thus the axiom of extension fails), even though they have the same members. So, if you use (crisp) set theory, then you it comes as untenable to use indeterminate forms to analyze a problem.

Just a side comment here to Doug Spoonwood. I know you are not addressing me but wanted to make the comment anyway.

There is no such thing as a 0/0 form, not in calculus or any mathematics. Newton's finite difference is a kludge. See my knol called Who discovered the derviative?

http://knol.google.com/k/who-discovered-the-derivative#

You may want to skip all the way down to the paragraph called:

So how did we get the form of the derivative that we have today?

MChu: The catch - and it's a huge catch - is that the tree defines a representation, not an enumeration or mapping.

JohnGabriel: The catch is that you are an idiot. What is the difference between Cantor's rational pairs and the representations in my tree? Dimwit!

MChu: As a representation, taken to infinity, it includes every possible real number.

JohnGabriel: Correct. And every one of those representations can be counted using?...that's right - natural numbers!!!! Moron.

MChu: But that doesn't mean that there's a one-to-one correspondence between the natural numbers and the real numbers.
JohnGabriel: Yes, it does.

MChu: There's no one-to-one correspondence between the natural numbers and the nodes of this infinite tree.
JohnGabriel: Yes, there is. You admitted this by agreeing that every representation to infinity includes every real number in[0,1).

MChu: It doesn't escape Cantor's diagonalization. It just replaces "real number" with "node of this infinite tree.

JohnGabriel: Really? You can produce an imaginary list of all the representations and then consider the diagonal. Changing any of the digits along the diagonal results in a representation that is in the tree.

See my knol called How we got radix systems

http://knol.google.com/k/john-gabriel/how-we-got-radix-systems/nz742dpk…

to understand how every radix representation is indeed unique.

John,

You just don't get it. I'm telling you this because you think you get it, which isn't the same as actually getting it. Get it?

Your tree either has countably many nodes and finite decimal representations, or uncountably many nodes and infinite decimal representations.

Either way, you failed.

By the way, I am a college math student who has just shown your knols to his professors. There remark was, "I thought google was limiting it to people can only write on professions they are in?" and "Well, if nonsense like this appears it should be deleted. Look at the format, it looks correct, but it's not."

Who are you fool?

"Your tree either has countably many nodes and finite decimal representations, or uncountably many nodes and infinite decimal representations."

That sentence alone tells me you won't ever get it. You contradicted yourself twice you f..k..g moron!!!

Mark Chu: I guess the laugh's on me. All you really care about is traffic to your worthless site - even if it means calling someone else a crank.

Nice Mark. Very nice. I would expect nothing less from a fool.

John:

First, my name is Mark Chu-Carroll. I'll never understand why people look at my name, and just drop the last part of it as if it wasn't there.

Second: My comment policy is pretty simple. You're welcome to insult me as much as you want. But you don't get to throw insults at other commenters. You get one warning, and this is it. Throw pointless insults at other commenters one more time, and you get to join the very small list of people who I've banned from commenting on here.

Third: If I were actually concerned about traffic, there are *much* better ways of drawing hits to my blog than making fun of twits like you. But the simple fact is, I don't care. It's nice when my blog gets hits, but that's not why I do it. I don't do it for money, or for fame, or for anything like that. I write this blog for *fun*. I enjoy studying math and explaining it to other people. And I enjoy mocking crackpots like you.

John,

How was that a contradiction? I told you either one of the two scenarios is true. You have to pick one. If it is the former than your tree only counts numbers with finite representation. If it is the latter, than you cannot count what you enumerated.

I stand by my assessment you think you get it which isn't the same as actually getting it. Get it?

MarkCC,

I see in your info, you work for google. I have to ask given the amount of incorrect ideas on knol, would you consider it a failed project? or do you believe there is a possibility to save it? For example, limiting areas like mathematics, physics, etc. to experts in those fields.

First of all: I couldn't care a stuff what your name is fool.

Second: You and your policies can take a flying leap for all I care. I shall insult whoever I please. And I begin with you - moron!

Third: You do it for fun? He, he. Calling others cranks is your idea of fun? Well, what can one expect from an ass like you anyway yeah?

Truth is you can't refute my arguments so you resort to flaming. Nothing surprising.

John:

I *did* refute your argument. That's what this post is about. You've refused to actually *address* my critique in any way - just constantly coming back here and throwing insults.

See, you're not willing to address the fact that your construction *doesn't work*.

Ultimately, it comes down to two possibilities: either your tree contains a countable set of nodes, or an uncountable set of nodes.

In the first case - the nodes are countable (that is, they can be put in 1:1 correspondance
with the naturals), then your tree doesn't contain all of the reals. It's simple to show that:
to be countable, it can only contain finite representations. So in a countable version of your construction, where does 1/3 appear? Where does *any* non-terminating decimal appear? The answer is, they don't appear.

If you extend your tree to allow infinite representations, then it's uncountable. And it's trivially provable - via exactly the argument it claims to refute - that it can't be put into 1:1 correspondence with the naturals.

But you won't address those problems. You *can't* address those problems. But cranks like you can never admit something like that. So you'll just make excuses about how I'm not worth your time, or I'm too stupid to understand, or whatever. But you'll keep coming back here to shout about how I'm an idiot, and all of the other people who say you're wrong are idiots. But you'll never actually address any of the problems that I, or any of the other commenters here, have pointed out. You'll just keep playing the juvenile game of "I know you are but what am I".

Calling other people cranks isn't my idea of fun. Finding cranks, showing what's wrong with their cranky arguments, and mocking them for it - *that's* fun. Watching you flail around, desparately hunting for excuses for why you don't need to address the problems with your cranky rubbish? That's entertainment.

MChu: I *did* refute your argument.

Gabriel: Only in your imagination.

MChu: It's simple to show that: to be countable, it can only contain finite representations.

Gabriel: According to who? You? Countability does not require finite representation of anything. The representations in Cantor's diagonal argument not finite representations.
Not all the real numbers can be represented finitely. So if your argument is even remotely true, then one cannot begin to talk about the countability of real numbers. It becomes irrelevant.

MChu: So in a countable version of your construction, where does 1/3 appear?

Gabriel: "a countable version" - oh please, don't make me laugh. You are so pathetic. There is no such thing as a countable version - twit! Now as for 1/3. All I have to do is tell you where it starts and you can follow the path. Go to the first digit which is a 3 and follow the path that contains only digits which are 3s. Question answered.

MChu: But you won't address those problems. You *can't* address those problems. But cranks like you can never admit something like that.

Gabriel: But I do answer these questions dimwit! You just don't get it! I just answered your questions. Now don't you even begin to complain about me verbally abusing you when you called me a crank. You pathetic scumbag!
Who do you think you are?! What makes you think you have the right to call anyone a crank? You are the crank!!!

One more thing: I am not the only one who knows the Diagonal Argument is a bunch of baloney. Cantor's *ideas* (they were stolen from Dedekind)
began with his countability theorem which essentially says nothing except to reformulate Dedekind's definition of real number.

The Diagonal Argument was Cantor's failed attempt to add credibility to his theorem which was immediately rejected by his peers. Once the diagonal argument was presented to the world, there was no doubt left in anyone's mind that Cantor was a fool. That makes you an even bigger fool for accepting this rot.

See, you're still just flinging insults instead of actually addressing criticisms.

I didn't say that your tree is finite. I said that there are two possible cases for how your tree works. In one of them, you can only ever have nodes for numbers with *finite* decimal representations. In the other, you can have all of the real numbers.

There's no way around that: either your tree contains only finite representations, or
it contains infinite representations.

The problem for you is that if you allow the tree to contain infinite representations - that is, you're using "tree" in a sense which allows you to talk about "nodes" of the tree that have infinitely long path-lengths leading to the node - then there's no way to create a 1:1 correspondence between those nodes and the natural numbers.

And you still will not do anything to address that point. You'll shout, and you'll call me names. You'll ignore the substance of the critique. But you'll never actually address the problems in your argument.

Just to give you an example; I didn't say that your tree was only the finite representations. I said that you've got two choices: either the tree only contains finite representations (in which case it has one kind of problem), or it has infinite representations (in which case it has a *different* problem). You can't actually address the problem with your argument - so you go for the strawman: you pretend that I only mentioned the finite case, and then address something I said about the finite case as if it was about the infinite case.

You can't have it both ways. The set of nodes of a branching tree with infinitely long paths is not countable. You cannot put the nodes of the infinite tree into a 1:1 correspondence with the natural numbers. The fact that you can identify the path for a particular number is irrelevant: that's really nothing more than an alternative way of saying that you can specify a particular real number - of course you can. But you can't
assign it a 1:1 mapping with the natural numbers.

But I'm sure you'll pick out some sentence fragments from that, construct a nice little strawman, and then use it as an excuse for calling me names again, without ever actually addressing anything real.

You hurled the first insult by calling me a crank. Let's drop the insults and start again. I shall prove to you step by step that my argument is correct. However, in order to do this, I need you to respond to each of my questions. Let me begin with the first question:

Do you agree that every real number in the interval (0,1) can be represented in decimal?

YES or NO

I do not want you to say anything else. Just YES or NO. I am waiting for your response before I continue my proof. I will ask you a few more questions and then I will show you my proof. Deal?

You can send your answers to my email address and I will respond here on your web page.

john underscore gabriel at yahoo dot com

1. Do you agree that every real number in the interval (0,1) can be represented in decimal?
YES or NO

2. Do you agree that my tree contains every real number in the interval (0,1)? Don't concern yourself about finite/infinite numbers at this time. We don't care about enumerating the numbers at this stage, only that if we know a number, we can find it in the tree.

YES or NO.

3. Do you agree that if we traverse the tree in each level from top to bottom that we can be sure to enumerate all the finitely (not the repeating decimals or irrational numbers) represented numbers in decimal? I know there are duplicates but we shall not worry about this right now.

YES or NO.

4. Do you agree that if we only perform left to right (infinite) traversals, that we can enumerate all the irrational numbers and some of the rational numbers?

YES or NO.

Once you answer these questions, I shall proceed. I am expecting a YES answer on all of them. Nothing secretive here. Besides, I think you will agree that these assumptions are reasonable.

@177:

I'm not interested in playing games. I've read your "proof". I've told you what's I think is wrong with it. You've refused to address that. And I've seen how you respond to criticism - both from me, and from other people who disagree with you.

(A) This is a blog. There are lots of readers. If you want to have this discussion, it's not just with me: it's with all of the people who read the blog.

(B) Why on earth would I believe that if I start playing your game that you're going to say
anything different from your Knol article?

(C) If it's just going to be the same as your Knol piece, why should I believe that if I continue to disagree with it, that you're going to respond any differently?

You've demonstrated that you're a juvenile who throws tantrums whenever anyone dares to disagree with your obvious brilliance. Even this "offer" of yours is just more of that: yeah, you'll explain why I'm wrong - provided I'm willing to do exactly what you want, when you want, how you want. The moment I do or say anything you don't like, you'll just start up your tantrums again.

One thing that I'm proud of on this blog is that I've got a history of admitting my errors. Just go back and look at the history of the blog. I've made my share of mistakes. And I've always done my best to admit them, and correct them. And I've done it without trying to hide it: I've always made the correction, and inserted extra text to explain that the original post contained an error.

If you're really interested in defending your proof, go ahead and do it here, in the open, in the comments. If you want, I'll even set up a new top-level post specifically for your arguments. But I won't play games with sending you private mails between each step, and I won't tolerate you throwing insults at readers who point out problems with your argument.

See what I mean? I started to prove this to you but look how you responded. I am not playing games with you. I am not prepared to continue unless you answer my questions. The reason for this is obvious: if you do not answer satisfactorily then I cannot continue the proof because you can always waver later on.

The reason I asked you to email me is because this page takes forever to load. But it's okay. Just place your responses here and I shall continue to respond whenever I can.

So once again, I offer to prove it but only on condition you answer my questions. It's up to you.

Before you accuse me, take a good long hard look in the mirror. You are guilty of everything you have accused me of. You can say whatever you dislike about me but I despise anyone who calls my intelligence into question. So, want to move ahead? Answer my questions. They're easy. YES or NO. We shall address every issue you have as we go along.

John, *this is a blog*, not private email. I don't track stats that closely - but each comment thread is followed by *at least* several dozen users. You're *not* just talking to me; you're talking to *all of the people reading the thread*. I'm not the only one who can respond, disagree, and criticize: anyone who reads this blog can.

Playing this little game of "you have to do it my way, and answer my questions, or I'll take my crayons and go home" is bullshit. It's just an excuse.

Are you going to throw more of your hissy-fits when some commenter who *didn't* send you per-comment answers points out a problem?

But fine, I'll give you your answers.

(1) Yes, I'll agree that all real numbers are *representable* using infinite decimal
notation.

(2) I'll also agree that taken to infinity, your tree contains all real numbers between
zero and 1.

(3) Yes, I'll agree that all finitely representable numbers can be enumerated from
your tree using a breadth-first traversal.

(4) NO, I do *not* agree that you can do a "left to right" traversal of the infinitely-long
representations. This is the problem with your whole damned argument: you're mixing together notions from finite representations with infinite representations. You cannot do an ordered traversal of the leaves of an infinite tree. It's *meaningless*. What's the left-neighbor of 1/3 in your tree? You cannot specify it - it doesn't really exist: there simply is no real number which is "closest" to 1/3 without being 1/3. But a left-to-right traversal supposes that there *is*. And that's the problem. You're trying to get a result using a property of a finite tree, when that property doesn't exist on a tree extended to infinity.

Very good. Now let's address your issue with question number 4 so that we can move on.

"This is the problem with your whole damned argument: you're mixing together notions from finite representations with infinite representations. You cannot do an ordered traversal of the leaves of an infinite tree. It's *meaningless*."

Well, if you can't do this, then I do not see how you agreed with 2? Let me clarify it for you: at this time we do not care about ordered traversals, only that the traversals are possible. Cantor's original argument says nothing about order of numbers, only that these have to be placed into a one to one correspondence.

That last sentence should have read:
Cantor's original argument says nothing about order of numbers, only that these have to be placed into a one to one correspondence with the natural numbers.

If I cease to respond today, it is because I am in a different time zone. So I'll continue to respond tomorrow.

I will not respond to anyone else but you.

Re 184: Fine, but I will still welcome comments from anyone who has anything to say, and I will *not* tolerate any abusive behavior towards them.

Re 182: You can enumerate things in a breadth-first fashion easily. (0, 0.1, 0.2, 0.3, 0.4, 0.5, ..., 0.9, 0.11, 0.12, 0.13, ...). There are an infinite number of values - but the number of steps that it takes to get to any one of them in the traversal is finite. That's *exactly* what it means to be countable: it's an infinite set, so you'll never stop enumerating them; but you can pick out any particular value, and it will be enumerated after a finite amount of time.

But in the case of the infinite tree, traversing the "leafs" makes no sense. It's not something that you can meaningfully do.

John,

I will give you point number 4 if and only if you acknowledge you are using infinite axiom of choice. Still you cannot enumerate your list so it doesn't matter.

MChu: Looks like we have to first agree on definitions. You claim:

"That's *exactly* what it means to be countable: it's an infinite set, so you'll never stop enumerating them; but you can pick out any particular value, and it will be enumerated after a finite amount of time."

This is not true. An infinite set is *countable* if and only if its members can be placed into a one-to-one correspondence with the natural numbers.

Where do you see anything in that definition that implies finite time? It's not there.

You claim the number of steps in a top-down traversal can be found in finite time.

*Finite time* has nothing to do with enumeration. 1/3 can be found in a finite number of steps as I demonstrated. Naturally,
one is not going to follow the full path for
the traversal because this is physically impossible. But it does not matter because you
agree that 0.3333..... is the decimal representation of 1/3 in base 10.

One does not care too much *where* in the tree/list the numbers are as much as one cares that these numbers are *in* the tree.

You also claim:

"But in the case of the infinite tree, traversing the "leafs" makes no sense. It's not something that you can meaningfully do."

If this is the case, then you can throw Cantor's diagonal argument out the window and we are done. Cantor's diagonal argument works on the premise that any list provided will not contain every real number. Now if we know that 1/3 is in our list (hey, it's just 0.333...), then what you are claiming is the same as Cantor telling us "But you can't meaningfully write down 1/3!"

Nonsense! If 1/3 can't be in our list, then there is no use taking up Cantor in his challenge, is there? I can't think of a more ridiculous excuse than this.

So now we know that the number 0.333... can be in out list. It cannot be written down or enumerated in a finite time - well, not in base 10 at any rate.

Another way of stating Countability is by saying, "A set is countable if one can write out its members".

Well, to this with the rational numbers, it can be done in finite time because they are well defined - N x N plus 0 defines the rational numbers. Since we cannot apply this product to all real numbers (as you know most real numbers cannot be represented as ratios), we need to find another way to represent real numbers. This other way is my tree.

In fact, if we cannot find a way to represent all real numbers, then it is not true that every real number can be represented using decimals.

So, do you now agree that one can perform a left-to right infinite traversal? Hey, let me put it to you this way: I can perform an infinite left-to-right traversal of 1/3 in finite time. How? I find the path that starts with a digit 3 and then I stop! Why? I know that every possible *permutation* is in my tree. I don't need to continue any further.
I could apply this same process to pi or e or sqrt(2) or any other irrational number I like, provided I know the first few significant digits.

So, in order to proceed, I must have your acknowledgement that it is possible to perform left-to-right finite traversals.

BTW: How do I know you are Mark Chu and you know I am John Gabriel? This was another reason I wanted to confirm via email. I had another scheme but I would have to tell you in an email how we could know who the real poster is. Otherwise I'll proceed here as I have been.

Sorry, I need your acknowledgement to:

So, in order to proceed, I must have your acknowledgement that it is possible to perform left-to-right infinite traversals.

That last comment was too long. Let me summarize it.

One can perform an infinite left to right traversal as follows:

Find the first digit of the decimal representation and stop.

That's it. I can rest assured that number is in my tree because the tree contains every possible *permutation* of the digits 0-9 in the decimal system.

As simple as that. So now we have taken care of your finite time issue. YES? May I continue?

@187:

How do you know I'm Mark Chu? You don't, because I'm *not* Mark Chu. I'm Mark Chu-Carroll. And what the hell difference does it make whether I send you email? I could *still* be sending from a newly created fake email address.

More importantly, it doesn't matter. You don't seem to understand that this is a blog. This is not a private conversation between two people. This is a public forum where anyone who wants to participate can participate.

On to substance: we clearly disagree about what "traversal" means. Traversing a tree means visiting its nodes in some sequence. A left-to-right traversal means visiting every node on a level in left to right order.

Traversal of a node doesn't mean saying "It's down there somewhere". It means visiting the node. You can't touch a parent of a node in a tree, say "I know the child is down there somewhere, so I've traversed it".

So no, you haven't taken care of anything. You're just redefining "traversal" in a non-sensical way in order to make your "proof" work.

Nonsense. You have a PhD? From where did you get your degree? Must be somewhere in the US. Allow me to educate you: A tree traversal does not say anything about visiting nodes in any order or sequence except that the nodes are visited exactly *once*.

That different ways of visiting the nodes exactly once are called traversals and can be accomplished in systematic ways. This however is irrelevant because I visit each node in my tree exactly once and this process is called a traversal. Rather than call it a pre-order or post-order or b-tree traversal, I call it top-down or left-right. See, this is one of the reasons I wanted to verify you are who you say you are. You evidently know very little about computer science.

Now read carefully: Don't you dare address me ever again as you have in your previous comment!

You DO NOT tell me what to do and you DO NOT get to say how things are done where I am concerned. Do I make myself clear?

Now let's proceed again:

You say:

Traversal of a node doesn't mean saying "It's down there somewhere". It means visiting the node. You can't touch a parent of a node in a tree, say "I know the child is down there somewhere, so I've traversed it".

As I just explained to you. I have a systematic way of visiting each node once. As for saying "I can't touch the parent node in a tree and say the child is down there somewhere" - OH, YES I CAN. This is part of the beauty in computer science algorithms - they are predictable. Tree structures are designed the way we want them to be. I wrote complicated balanced tree algorithms in Assembly x86 way back in 1980. Trust me, if I could not say the "child" is down there somewhere, I would have had major issues. Do you know anything about algorithms and optimisation? Probably not much.

So, don't spew out any more nonsense at me. I am infinitely more intelligent than you can ever hope to be. Yes, I know it's arrogant. Do you know what? F..k the lot of you at Google. You are the biggest morons I have ever come across in my entire life. The sad thing is you don't realize it because your ego is way out of proportion with your intelligence.

Ok, stupidicus? Now, may I continue? Abuse me one more time verbally and piss on you!!!!

In order to complete my proof, it is imperative that you agree with point number 4 (it does not require the axiom of choice - I don't believe in the axiom of choice).

After this, I have one more question and then I shall complete the proof. Once the proof is completed, you shall apologize for calling me a crank and update your webpages to reflect the fact that you have been wrong yet again!

YES or NO to question number 4? Spare me any other shit talk. I don't want to discuss anything else.

Just a point of clarification:

In a infinite left-right traversal, I am referring to a traversal that results in only one real number. By stepping down the tree, the next real number and so forth.

I am not completing the infinite traversals - there is no sense in even thinking about such an absurdity.

@191:

See, this is exactly what I predicted. You just regurgitate the same nonsense, and throw insults the moment I disagree with you.

Let me explain something to you again. This is a blog. This is not a private conversation. This is a public forum. You don't get to make up your own rules about how the forum works. If you don't like it, tough.

And it's really quite amusing to see you throwing tantrums because you think I didn't address you correctly. I'm honestly not even sure about exactly what set off that tantrum: but you want to be addressed in some particular way, but you can't even be bothered to get my name right. I'm supposed to be properly respectful and deferential towards you, to the point of rewriting the rules of how I handle comments on my blog; but you can't have the simple, trivial decency of getting my name right.

I still fail to understand your obsession with identity. How would my sending you private email prove who I am? It takes 30 seconds to set up a new gmail address. I could set up a dozen variants on Mark Chu-Carroll on gmail. I could set up a gmail address claiming that I was John Gabriel, and send you email from that. What would it prove? Email can't prove identity. It can't prove that I have a PhD. It can't prove that I don't have a PhD. It can't prove that this is my real name, and it can't prove that it's not. And as I keep trying to explain, this isn't a private conversation. This is taking place on a public forum, with somewhere between a couple of dozen and a couple of hundred readers, any of whom are welcome to participate. So even if there were some way for you to verify my credentials, what difference would it make?

More importantly, this is an argument about math. If you're wrong about a piece of math, the identity of the person who points out that error is entirely irrelevant. It's math: a critique of a proof doesn't become correct because the person who wrote it has a particular degree. Greg Chaitin, who I admire greatly, wrote his first major mathematical critique of Kolmogorov when he was in high school. Is that original critique less correct than the exact same criticism written down after he got his PhD?

Tell me, John. How exactly is touching the parent node of an infinite subtree equivalent to visiting every child of that subtree exactly once? What does "left to right" mean if not, well, left to right?

Yet another thought: If you are thinking that I would not be able to complete the left-right traversals, well, you would not be able to complete pairing the natural numbers either.

So if there isn't anything else, I think you are ready to agree with point 4.

A infinite left-right traversal is starting off at any one of the top nodes and visiting only one node from each level.

A top-down traversal on the other hand is finite and remains within one level with the first digit being the parent node in that level.

Left-right:

0.1 - 4 - 5 - ......

Top-down:

0.1
0.2
0.3
.....

You do realize that to accomplish all the left-right traversals means starting off at a top node. But this is okay because we can leave a marker at the last node we forked off somewhere.

Although nodes are revisited this way, it does not matter because each traversal is for a different number. What I am saying is that for one traversal, each node is visited *exactly once* - this is in order. Think of a formula parsing tree that contains many different formulas. We could do one traversal to calculate one function and start another traversal to calculate another function.

One need not be concerned about not being able to move from one node to the next. One can think of infinitely many parallel traversals all taking place at the same time.

This may not have been a mental block for you but I just thought I'd address it to make sure we covered every possibility.

@200:

In one message, you say:

4. Do you agree that if we only perform left to right (infinite) traversals, that we can enumerate all the irrational numbers and some of the rational numbers?

In another, you say:

n a infinite left-right traversal, I am referring to a traversal that results in only one real number. By stepping down the tree, the next real number and so forth.

I am not completing the infinite traversals - there is no sense in even thinking about such an absurdity.

How can you claim to "enumerate" the irrational numbers, without being able to complete traversals? Or are you claiming that you can enumerate the digits of any particular irrational number? If the latter, than what on earth does "left to right" traversal
have to do with it? If you're enumerating the digits of a specific number, then you're traversing a single path - no "left-to-right". If you're enumerating multiple numbers, then your traversal is not ever visiting the nodes corresponding to the numbers with infinite representations.

1. One enumerates an irrational number by a given left-right traversal. The completion is imaginary for one does not write down all the digits of pi say, this would be absurd because it is impossible. However, the imagined completion is the number pi.
2. Yes, if you are enumerating (writing down) the digits of a specific number, then you are traversing a single path.
3. Left-to-right is just what I call the traversal where one visits exactly one node in each top-down level and it results in one real number either rational or irrational. If one does not like the name left-right, you can change it to whatever you like. Itâs immaterial.
4.Enumerating multiple numbers: This requires parallel traversals that all take place at the same time.

"If you're enumerating multiple numbers, then your traversal is not ever visiting the nodes corresponding to the numbers with infinite representations."

Yes, it will visit the nodes - we just won't wait around for it to finish. See what I mean?
Once the number's digits are on the path, we bid it adieu. Take the simple example of 1/3. We start at the digit 3 and we know there is an infinite string containing only the digit 3.

This is the imaginary completion. It is absurd to think you can find the last node because there *is no last node*. However, you cannot disqualify the argument for this reason. Cantor's challenge to provide an imaginary list includes numbers that are infinitely represented.

No, it *won't* visit the nodes. It will never reach them.

It comes back to exactly where we started: I said that your problem is that you can represent nodes, but not actually enumerate them.

What you're doing now is playing games with terminology. You're trying to redefine
the meanings of "enumeration" and "traversal".

You're claiming that you can do a "left-right traversal" which isn't actually a traversal. It involves "visiting" nodes without ever actually visiting them. And it involves "enumerating" nodes that will never actually get enumerated, by using an infinite number of processes which will never actually finish reaching the nodes that they supposedly enumerate.

And none of that has anything to do with Cantor. Cantor doesn't generate an enumeration. Cantor says "Given a supposed enumeration of the real numbers, I can show you a real number which isn't in that enumeration".

You've got a representation which includes all of the real numbers. But you can't enumerate the values in it. As I said at the very beginning, representation is not enumeration. You still can't enumerate the real numbers. You can represent them, but you can't enumerate your representations.

The nodes *are* visited, but you are not able to see it. So this is why we are having this discussion.

Enumerate means to count off one by one.

I *do not* want to write out or count the digits of any traversal. The digits only have meaning as a *collective*, that means taken to infinity, they represent the decimal number. Again, take the example of 1/3. Can you enumerate the digits of the decimal representation 0.333... ? No. Suppose now that each digit 3 is contained in a node. One left-right traversal is an *enumeration* of 1/3. It's that simple.

MChu: You're claiming that you can do a "left-right traversal" which isn't actually a traversal. It involves "visiting" nodes without ever actually visiting them.

Not so. It is exactly a traversal. As I explained, one does not have to wait around for ever to be convinced that every node is visited exactly once for each real number represented by a given left-right traversal.

MChu: And it involves "enumerating" nodes that will never actually get enumerated,

No. You are not enumerating *nodes*, you are enumerating decimal numbers. Big difference. The nodes are the building blocks of each decimal number.

MChu: ...by using an infinite number of processes which will never actually finish reaching the nodes that they supposedly enumerate."

Tell me, what node is one supposed to reach in the case of 1/3? Do you realize how ridiculous this last statement of yours is? There is no last node.

MChu: You still can't enumerate the real numbers. You can represent them, but you can't enumerate your representations.

If I can represent them, I can enumerate them. Representation <=> Enumeration.

In mathematics and theoretical computer science, the broadest and most abstract definition of an enumeration of a set is an exact listing of all of its elements (perhaps with repetition). Wikipedia.

Hate quoting from Wikipedia but this definition is correct.

@205:

Tell me, what node is one supposed to reach in the case of 1/3? Do you realize how ridiculous this last statement of yours is? There is no last node.

That's exactly the point. Your mechanism will never produce 1/3 in its enumeration. It will produce an infinite succession of closer and closer approximations to 1/3 - but it will never produce the real number 1/3.

Your enumeration will only ever really generate finite length numbers. Anything which requires an infinitely long representation cannot be generated by an enumeration from your tree. None of the numbers with infinitely long representations are reachable by traversal.

Like I keep saying: You're redefining "enumeration", "traversal", and "visit". You can't enumerate the real numbers with your tree, because you can't traverse the tree to visit any number with an infinite representation.

If you're allowed to change the meaning of visit to "not really visit, but be able to sorta point in the direction of", and traverse as "sorta point in the direction of all of the parts of the tree", then sure, you can traverseJG the tree in a way where you visitJG all of the nodes, and thus you can enumerateJG all of the nodes by sorta pointing in their direction.

But back in the real world, visitJG != visit, traverseJG != traverse, and enumerateJG!=enumerate.

the real numbers without actually enumerating them", then you can

Yes John, an enumeration is a complete listing of all of its elements. Which is really just begging the question: what is a listing?

You're essentially claiming that a "listing" is in some sense equivalent to a predicate. That is, if you can define a predicate describing a set of numbers, then you can enumerate those
numbers.

Meanwhile, the rest of the world of computer science and math gives enumeration a rather different meaning: an enumeration of a set is a 1:1 mapping from a subset of the natural numbers to members of the set. In the case of an infinite set, it's generally
a mapping from the complete set of natural numbers to the members of the infinite set.
(Hell, it's even implicit in the word "enumeration"!)

If you have an enumeration of a set, one of the properties of it is that you can describe what natural number will be mapped to what element of the set. If you
really have an enumeration, then finding the natural number associated with a particular
member of your set is trivially computable.

But numbers with infinitely long representations aren't enumerable in
your representation. If you search for them, you'll never find them. They'll never show up in the list. There's a theoretical representation of every real number - but it's not a
representation that will ever appear in an enumeration. In your system, there is no natural number N such that 1/3rd is the Nth element of the list. So in what sense is 1/3 actually
a member of your list?

MChu:"That's exactly the point. Your mechanism will never produce 1/3 in its enumeration. It will produce an infinite succession of closer and closer approximations to 1/3 - but it will never produce the real number 1/3."

In other words, 0.333... is not equal to 1/3 in your opinion? No. You agreed in Point 1 that all real numbers can be represented in decimal. So we are not going back to that one. Each time I explain to you, you keep going back and forth.

You've already agreed to this. And now you don't agree with it any more? So, if you don't agree with point number 1, you may as well discard Cantor's diagonal argument because it is about an imaginary list that can contain infinitely represented numbers.

MChu:"But numbers with infinitely long representations aren't enumerable in
your representation. If you search for them, you'll never find them. They'll never show up in the list. There's a theoretical representation of every real number - but it's not a
representation that will ever appear in an enumeration."

The fact that I have imagined these representations means they are very *real*. And of course they appear in a list but I haven't got there yet because you still can't see that point number 4 is true. In fact, you are now disputing that you agreed with point number 1!

See why I must have you answer these questions first? If you don't see that these four statements are true, we cannot proceed with the next question and finally the proof.

As I see it now, you are disagreeing for the sake of disagreeing. I think you know you are wrong. Well, for one thing you are contradicting yourself.

By the way, I have never redefined anything. Please don't go down that road. You are smarter than this, I think.

Just stay with the argument. If you do not understand I will try to explain. Just ask.

MChu: Meanwhile, the rest of the world of computer science and math gives enumeration a rather different meaning: an enumeration of a set is a 1:1 mapping from a subset of the natural numbers to members of the set. In the case of an infinite set, it's generally
a mapping from the complete set of natural numbers to the members of the infinite set.
(Hell, it's even implicit in the word "enumeration"!)

Once we agree on all four points, the above statement is what I shall proceed to prove.

I'm not disputing that you can represent 1/3 as an infinitely long decimal string 0.333.....

What I'm disputing is that you can produce an enumeration of the nodes of your tree which will ever include that string. The fact that you've got a representation for the real numbers does not imply that you've got an enumeration
of the real numbers. Your representation is not enumerable.

You can whine and complain all you like - but it's not going to change anything. If you claim that 1/3 appears in an enumeration of the nodes of your tree, then either you're lying, or you don't actually understand what an enumeration is, or you have some other meaning of enumeration that's different from the rest of us.

If you have an enumeration, then specifying what natural number maps to 1/3 must be possible. By the definition of an enumeration, there must be exactly one natural number that maps to 1/3 in your enumeration.

In one of the canonical ways of enumerating the rationals, 1/3 corresponds to 5: {0, 1, 2, 1/2, 3, 1/3, 2/3, 4, 1/4, 3/4, ...}. Given any rational number, I can find its position in that
enumeration. It might take me a while to do it - if you give me a number like 623784/98237421, it'll take me a long time to find it - but I can.

In your system, you can't specify the natural number that corresponds to 1/3 in your "enumeration" - because 1/3 will never be enumerated by your "traversal".

The fact that you can represent the members of an infinite set does not imply that you can enumerate them.

MChu: "You can whine and complain all you like - but it's not going to change anything."

Taking cheap shots at me does not help. In fact it makes you look stupid.

MChu: "What I'm disputing is that you can produce an enumeration of the nodes of your tree which will ever include that string. The fact that you've got a representation for the real numbers does not imply that you've got an enumeration of the real numbers."

Oh yes, it does. Suppose I represent the first six natural numbers of my set by a, r, b, w, e, t. Now, I create a bijection: f(1)=a, f(2)=r, f(6)=t. I have enumerated my set. In fact, the it is *required* that one can represent the members of a set. What you have written is the dumbest thing I ever heard! How on earth can you enumerate anything when you don't even know what it is?! Get real!

MChu:"Your representation is not enumerable."

Well, you are not able to comprehend even the most basic concepts. I still have to show that [0,1) is enumerable but I cannot do this unless you *understand* that the representations in my tree diagram represent every real number. In fact, you have already admitted this in your introduction. See paragraph 10:

MChu: "His enumeration is based on trees. You can create an infinite tree of the decimal representation of the numbers between zero and one."

My, oh my, but you have such a short memory, don't you?

Please be frank with me: do you really have a PhD in computer science? I am even doubtful that you are who you claim to be. You are contradicting yourself over and over again.

Now, you have to answer YES to question 4 and understand why the answer is correct otherwise I am wasting my time with you.

So you see why I did not bother engaging you even over a year ago? I imagines these would be the dumb, thoughtless responses I would receive.
My problem is I often give others the benefit of the doubt when it comes to believing they are of reasonable intelligence.

In fact you have not realized it, but by stating what you have in Paragraph 10, you have essentially agreed to all 4 points already. The reason I brought up these points is because I wanted to make sure you understood what you were putting your head on the block for. Evidently, you did not know what you were agreeing with.

1. Do you agree that every real number in the interval (0,1) can be represented in decimal?
YES or NO
2. Do you agree that my tree contains every real number in the interval (0,1)? Don't concern yourself about finite/infinite numbers at this time. We don't care about *enumerating* the numbers at this stage, only that if we know a number, we can find it in the tree.
YES or NO.
3. Do you agree that if we traverse the tree in each level from top to bottom that we can be sure to enumerate all the finitely (not the repeating decimals or irrational numbers) represented numbers in decimal? I know there are duplicates but we shall not worry about this right now.
YES or NO.

4. Do you agree that if we only perform left to right (infinite) traversals, that we can enumerate all the irrational numbers and some of the rational numbers?
YES or NO.

Paragraph 10 confirms all these questions with a YES. Now, I need to know that you know your admission in par. 10 is equivalent to all these 4 points.

Truthfully, the only reason I bothered engaging you is because I took the time to read your introduction and realized you were almost *there* in terms of understanding.

I now am beginning to see I was mistaken.

Oh yes, it does. Suppose I represent the first six natural numbers of my set by a, r, b, w, e, t. Now, I create a bijection: f(1)=a, f(2)=r, f(6)=t. I have enumerated my set. In fact, the it is *required* that one can represent the members of a set. What you have written is the dumbest thing I ever heard! How on earth can you enumerate anything when you don't even know what it is?! Get real!

I did not say that you cannot represent an enumerable set. I said that the fact that a sent is representable does not imply that it is enumerable.

As I originally predicted, you're not addressing the substantial criticisms of your construction. You're picking out bits and pieces, mis-representing them, and then using them as a basis for flinging insults.

You have a representation for all of the real numbers. I have never claimed or implied otherwise. From the start, from the original post, I have continually said that you have a representation of the real numbers, but your representation is
not enumerable.

You keep responding to tiny pieces of my criticism that you can misrepresent, while ignoring the substantial parts.

So let me repeat: By the definition of an enumeration of a set, given any element of the set S, it's possible - it's easy to discover what natural number corresponds to that element in the enumeration. If you have an enumeration, then specifying what natural number maps to 1/3 must be possible. By the definition of an enumeration, there must be exactly one natural number that maps to 1/3 in your enumeration.

So, John, what number is it? At what natural-number position will 1/3 appear in your enumeration? In fact, go ahead and pick any number you want that has an infinite representation as a decimal, and tell me where it will appear in your enumeration. If you've really got an enumeration, then it must be possible to say where some number with an infinite representation appears in the enumeration.

So come on, put up or shut up. Where does 1/3, or 1/9, or 1/π, or 1/27th, or 1/11th appear in your enumeration? What natural number maps to any number with an infinite representation? If you can't answer that, you don't have an enumeration.

I am not surprised at your outburst and false accusations.

I have informed you that in order for me to proceed, you have to consent with the 4 statements I put to you.

Look at you: Come on John! Tell me, what number corresponds to 1/3, or pi or e!

Let me ask you: Come on Mark, tell me, what number corresponds to the smallest rational number greater than pi?

Would you be able to answer? NO. Yet you have the audacity to tell me that you are able to enumerate all rational numbers. So tell me then, where is this rational number in your list and tell me which natural number it is mapped to?

Unlike like you, I know that this smallest rational number greater than pi will be in your list and that some natural number will *eventually* be assigned to it.

Do I tell you that the rational numbers are not denumerable because you cannot provide this information to me? No, because I understand that it can be in your list.

Your arguments are lame.

Let me correct you: I do not have to provide a natural number that corresponds to any of the reals in my tree. All I have to do is show you that it is possible to assign a natural number to every real in my tree and then I am done.

This is what enumeration is all about. Just another gaping hole in your understanding!

John:

You can "inform" me of anything you want. It doesn't change reality.

You want me to agree with you that your tree is traversable in a particular way - but it isn't. And as usual, you ignore the point, throw insults, and whine.

I'm giving you the freedom to pick any number with an infinite representation in your tree, and tell me where it appears in your enumeration. I'm doing that, because you and I both know that you can't do it, and that the reason you can't do it is because you don't have an enumeration.

In return, you come back with something that by definition, doesn't exist, and ask me to show it to you. There is no rational number closest to π. It doesn't exist. And you know that.

But you're asking for the impossible, because you can't do what I asked. If you had an enumeration, you could specify where things occur in it. By definition, if you had an enumeration, you could specify where things occur in it. But you don't.

You keep wanting me to admit to agreeing with you that you can enumerate these things. But you can't. They're not enumerable. This is the crux of your argument, which is why you demand that I accept it. But it's not true. You cannot enumerate any numbers with infinite representations by traversing your tree - unless, of course, you redefine the words "traverse" and "enumerate".

And all that you can do is constantly play games like this - throw insults, shout, whine, and ignore the point of anyone who disagrees with you. You're a crank all right - and in typical crankish fashion, you demand respect that you haven't earned, and throw tantrums anytime anyone points out that you are wrong.

John, you are wrong. Your representation is not enumerable. A "left to right" traversal - or in fact any traversal of your tree will never reach a single number with an infinite representation.

Nonsense. I do not have to provide a particular natural number that corresponds to any of the real numbers in my tree.

All I have to do is show that it is possible to assign a natural number to every real in my tree and then I am done. Then the real numbers in (0,1] are denumerable.

No where in the definition of countability is there a requirement to produce a particular natural number for any of the rational numbers.

I could denumerate my rational numbers by placing them into a one-to-one correspondence with the even natural numbers or the prime numbers. There is *no* requirement to produce a particular value. If you knew any mathematics, well then you would know this fact.

Alas, you do not.

MChu:John, you are wrong. Your representation is not enumerable. A "left to right" traversal - or in fact any traversal of your tree will never reach a single number with an infinite representation.

Evidently not according to your paragraph 10!

MChu: There is no rational number closest to Ï. It doesn't exist. And you know that.

Oh yes there is. But don't worry, you can't find it. You can't do a lot of things in mathematics, but that does not prevent you from producing useful results and theorems.

MChu: There is no rational number closest to Ï. It doesn't exist. And you know that

In fact at some or other position in your enumeration of rational numbers, it must appear. For if it does not, then your rational numbers are also not denumerable!!

Quite possibly the dumbest thing I have ever read:

MarkCC: There is no rational number closest to Ï. It doesn't exist. And you know that.

JG: Oh yes there is. But don't worry, you can't find it. You can't do a lot of things in mathematics, but that does not prevent you from producing useful results and theorems.

okay, really Gabriel?

We shall show, John Gabriel is wrong, and there is no rational closest to pi.

Proof: We shall prove by contradiction and assume r is in Q, such that r is the first rational after pi.
Consider the interval (pi...r), then by Archimedes principal there exists a rational s in the interval, thus pi < s < r. Contradiction.

Really? Try not to make it that easy...

thus pi less than s less than r, contradiction.*

MChu: Let me put it to you another way: Suppose that you could enumerate the real numbers. Just "suppose". Now, if I were to ask you what natural number corresponds to pi, would you be able to tell me? NO.

Now, let's see if we can approach this in another way because your mental faculties are obviously limited. From my tree it is evident there are two distinct *infinities* (hate to use this word but anyway): the one infinity describes the top-down traversals and the other, the left-right traversals.

Try to imagine two bottomless wells: The one well is a reservoir for the top-down numbers. In other words, each time we visit one of these numbers, it goes into the reservoir. The other well is also a reservoir that stores all the numbers from the left-right traversals in a first-in-first-out fashion. The left-right reservoir is populated with infinitely many left-right traversals taking place at the same time.

So, at any given time, one can get a number from either of the reservoirs. Now, from the top-down reservoir one can produce a one-to-one correspondence with the even natural numbers. From the other reservoir, one can produce a one-to-one correspondence with the odd natural numbers. Result: A list of all the real numbers in [0,1). However, job is still not done. We go through the list removing the duplicates and what is left is exactly all the numbers in [0,1). And we have produced a bijection. Therefore the real number interval according to Cantor is *countable*.

There is an undergrad student here who is one of the biggest fools I have ever had the misfortune of meeting - Scully. Since he has started to comment here, this is my last comment to you.

MChu: You do not call anyone a crank for any reason whatsoever. You can call me a Cantor disputer or even better refuter. However, you have no right to call me a crank because you are unable to understand my arguments. Just so you are aware, there are mathematics professors who agree with me. My knol had a very high rating before it was voted down by fools the likes of Scully. This insignificant worm does not posses even 1/100 of my intelligence. You probably have less.

In fact the word crank comes from a German word meaning sick. Let me assure you, I have only met one person in my almost 1/2 century of existence who was intellectually on par with me.

As I mentioned earlier and have proved from this dialogue, you are not only incapable of engaging me, you are rude, arrogant and insulting. MChu, be prepared for insults when you call anyone a crank. You are the real crank!

@226:

So this ends exactly as I predicted: you can't address criticisms of your "proof", so you throw tantrums and call names.

And I'll just note for humors sake the irony of posting a comment in which you bitterly complain about how awful it is to call anyone a crank, while flinging equivalent insults in the very same sentence.

John, you're a crank. A pathetic crank.

I'm not much on maths but this is psychologically fascinating. The mental representation of infinites must be coded or truncated. It looks like John has pulled them out of his head with the branches cut off, as if the numbers and the mental coding are the same thing.

There is no rational number closest to Ï . The basic reason is that the rational numbers are a dense set, and there are an infinite number of them between any two points on the line, rational or irrational.

However, to make it clearer, I'll give a proof by contradiction, just like the famous reductio ad absurdum proof of the irrationality of â2, where for any rational number x, I construct a closer number y:

Suppose you have x â  Ï , which is the rational number closes to Ï. Then δ = Ïâx â  0 is the distance to pi. Let δ = s·ε, where s=±1 is the sign and ε=|δ|>0 is the magnitude.

For any natural number N > 1/ε, y=x+s/N is a rational number between x and Ï. If you want a specific one take N = â2/εâ, which will produce a y approximately "halfway between" x and Ï.

y is rational because x is rational and s/N is rational, and so their sum is rational.

And yet |Ïây| = |Ïâx|â2/N < |Ïâx|, so y is closer to Ï than x.

Thus, our assumption is false, and no such number x exists.

(With a bit more effort, I could find a number y' on the other side of pi that's also closer than x. But that requires a longer proof that treats the case of N=1 specially.)

If you need a totally formal proof of the uncountability of the reals, see http://us.metamath.org/mpeuni/ruc.html, That's a machine-verified proof showing every derivation step directly from the axioms of ZF set theory. (Without, in this case, the axiom of choice.)

I realize it's an awfully big chain of logic to wade through, but it is finite, and doesn't skip any steps, so if there's a flaw, it's explicitly written out somewhere. All you have to do is find it.

It's also interesting because it's not Cantor's proof; it avoids the whole issue of decimal representations. But it is similar in that given any countable list of real numbers, it constructs a real number not on the list.

I should have written this earlier, but better late than never.

@98 Ned Rosen
Thank you for taking the time to write that.

@144,145 Ivan
I saw the definition you posted of the set theory tree. It explains everything. I too find it very interesting, especially that a single definition discrepancy could cause so much confusion and discord.

About 10^a:
I believe my problem was with the difference between cardinal numbers and regular numbers. Specifically that |10x10x...| is not equal to |10^N|.

a/b=Sqr(2), Let a=Sqr(2).(1000...omega...) and b=1000...omega...
omega integers a/b=2
Are omega integers possible?