The Continuum Hypothesis Solved: All Infinities are the Same? Nope.

Nitpick: An infinite set A is larger than another infinite set B if every possible mapping from members of B to members of A will exclude at least one member of A.

IIRC, that's only true in systems with the axiom of choice.

I thought I had it until "An infinite-length string of digits isn't a natural number, or an integer".

Why is this the case? Why is an infinitely-long sequence of digits not an integer?

OK, so not only can he not construct pi, but he can't even construct 1/3 in his [0,1] construction since his trees never reach a length of infinity. (It took me a couple minutes to come up with a mapping from [0,1] to (-inf, inf) - tangent shift, duh.) Mind you, the distinction between continuing infinitely and reaching infinity can be hard to grasp, especially for one with such problems with the concept of infinity to start. Still, if you think you've disproved a famous proof, wouldn't you want to make sure your proof can withstand the other before publishing your paper?

There are concepts that I don't understand completely, but my lack of understanding is in no way proof of the contrary. Concepts doesn't get to become a scientific theory without sufficient evidence. I may never understand relativity or certain parts of quantum physics - fortunately, most of my interests focus on objects larger and slower than a photon and smaller than a black hole.

So how, exactly, did this paper make into Arvix?

I disagree with your assessment that his proof cannot be correct while Cantor's argument still holds. There is another option: there's a contradiction in our axiomatic system. Luckily for mathematicians this isn't what is happening in this case.

Actually, if you would *read* the paper, you can see he infact *can* represent Ï in his tree. Indeed, it is explicitly done on page 4 of the paper:

"In fact, we can define any node in this infinite tree by he decimal number characterizing the path of the tree to each a node. For example, the node (3,1,4,1,5,9,2,6) can be defined by the decimal number (3,1415926) which is the number Ï."

So there!

Knowbuddy:

Any given natural number n is finite, pretty much as part of the definition of natural numbers.

Let's define a function l(n) = depth of n in the trie described above, or in other words, one more than the number of digits in the decimal expansion of n. I assert that l(n) < n, for all n $gt; 2.

Proof (by induction):
Base case n=3: By computation, l(3) = 2 < 3.
Induction Case (n>3):
If n &neq; 9 mod 10, then l(n+1) = l(n) < n < n+1.
Otherwise n = 9 mod 10, and l(n+1) = l(n)+1 < n + 1.
Either way, l(n+1) < n + 1.

Since the length in decimal notation of any sufficiently large natural number n is less than n, and since n is finite, the length of n must also be finite, for all n > 2.

Therefore, no integer corresponds to a decimal digit string of infinite length. Or, in terms of this paper, the path from the root of his trie to the node corresponding to any integer is finite.

Re #6:

I can't tell if you're joking or not. So I'll just pretend for the sake of amusement that you're not.

As I implied in the original post, in the discussion about what correspond to parts of π, his tree includes every finite prefix of π. But π goes on forever - no finite prefix of π is π, and π cannot be represented by a finite sequence of digits. So no node of his tree at any level less than ω can possibly include π. And if the tree doesn't include π before it reaches level ω, then that implies that there is something after ω.

OK, so he says he can find a node for Ï in his trie. What's the integer corresponding to that node?

I want to know the integer corresponding to the node for 11/90 (which, in decimal is 0.21111111.....) It isn't 1, since that node is for 0.1, so it differs from 11/90 in the first digit. It isn't 2, since that node is for 0.2, so it differs from 11/90 in the second digit. It isn't node 3 (0.3) which differs in the 3rd digit.....

Well, unless I misunderstand my own reply to the paper, here's my off-the-cuff proof of different infinities:

Q1: How many 0 dimensional points are in a unit circle?
A1: An infinite amount
Q2: How many 0 dimensional points are in two unit circles?
A2: Twice as ... er, infinite...uh..
Q3: 2x infinity, no?
A3: ...

Re #10:

That one doesn't quite work...

Two counterexamples: How many even integers are there? How many odd integers are there? How many integers are there? All three are equal.

The really interesting one is the Banach-Tarski paradox. Take a sphere. Slice it into some very strange pieces. Put those pieces back together, without changing them at all - and you'll get two spheres exactly the same size as the original. The same number of points, but now they form two spheres, instead of one.

Why are they equal? Why wouldn't the total number of integers be twice (plus or minus one) the amount of odd or even integers? Also, how could you biject the entire integer series onto only the odd or even integer series?

As far as the Banach-Tarski paradox - I seem to recall that's not precisely true. The short form of which being, you can get the same volume and surface area with many different amounts of material, but the total amount of material won't change. They just use a very subtle form of stretching.

Ketil (#6) is, sadly, not kidding. Check the PDF from arXiv, right there middle of page 4. Wow.

Also, how could you biject the entire integer series onto only the odd or even integer series?Consider f(n) = 2n. This function is a bijection between the integers and the even integers. Since there's a bijection between them, the two sets are the same size.

Twice a given infinity is the same infinity. Adding one to a given size of infinity also results in the same size of infinity. To get larger infinities, you need to take more exotic action.

And the Banach-Tarski paradox uses no stretching. The sphere is cut up, then the pieces are moved without stretching, and the result is 2 spheres.

Dreiken, Banach-Tarski does not require any stretching but it does require the Axiom of Choice. The pieces used in Banach-Tarski are very strange looking. Banach-Tarski says more that you can't consistently assign volume to all of R^3 if you want volume to satisfy the basic properties we expect it to, especially being unchanged under translation. In 1 or 2 dimensions the situation is slightly better but only marginally so.

Speaking as a mathematical n00b: didn't Paul Cohen prove in, like 1962, that the Continuum Hypothesis is undecidable?

And if someone doesn't like the results of Cantorian set theory, can't they just say that that demonstrates that the Axion of Choice is incorrect, and roll their own set theory without it? Isn't disproving Cantor with it a mug's game? Color me confused.

The idea of comparing the sizes of different infinities - and worse, of actually concluding that there are different infinities, where some infinities are larger than others - drives some people absolutely crazy.

It drove me crazy, so I decided that infinity was not a place I wanted to go. Life's too short.

So how, exactly, did this paper make into Arvix?

He just submitted it. ArXiv is a pre-print repository, so anything can be sent there. It doesn't mean it'll get published, just that he threw it into the system.

@16: Cantor's proof in no way requires the Axiom of Choice.

Surely the existence of different-sized infinities is intuitively obvious?

There are an infinite number of integers.
There are an infinite number of numbers with two fractional places -- but there are a hundred times as many of them as there are integers.
QED.

What am I missing here?

"Infinity can be thought as an absolute concept and there should not exist several dimensions for the infinite."

Anyone think that using the words "there should not exist. . ." in an argument about mathematics might be a sign of terminal crankdom?

#2: Actually, the definition of an irrational number is two-fold: first, it's a number that cannot be expressed as the ratio of two integers, m, n, where n is not equal to 0. Second, an irrational number is a non-terminating, non-repeating decimal. The "non-repeating" part gives some folks difficulty. What it means is that for any finite group of consecutive digits in its representation, that group does not repeat for the remainder of the representation.

For a very sweet introduction to Cantor's ideas, check out WELCOME TO THE HOTEL INFINITY: http://tinyurl.com/ddkesc

As MPGoldenberg said, the author seems not to realize that the set of finite decimal representations, no matter how finitely long, only captures the rationals.

I'm almost convinced that the "3.1415926, which is pi" part was put in there to indicate that the whole thing is a joke. I'd like to think that, anyway.

Re #19:

Surely the existence of different-sized infinities is intuitively obvious?
There are an infinite number of integers.
There are an infinite number of numbers with two fractional places -- but there are a hundred times as many of them as there are integers.
QED.
What am I missing here?

It's not that easy. In fact, the set of numbers with two fractional places is exactly the same size as the set of integers. There's a simple bijection between them:
"b(int) = int/100".

Infinite sets are very counter-intuitive. A lot of things that seems like they should make sense don't. The set of even numbers is the same size as the set of integers - even though it seems as if it should be smaller. The set of rational numbers is the same size as the integers - even though it seems like it should be larger.

The only way to compare infinite sets is by looking for bijections. There is a bijection between the rationals and the naturals - so they're the same size. There's a bijection between all naturals and even naturals (b(n) = n×2) - so they're the same size. But there isn't a bijection between the integers or the reals - so they're not the same size; and in every attempt at a bijection, you can cover all of the integers, but you'll always miss some reals - so the set of the reals is larger than the set of the integers.

Re #16:

My admittedly limited understanding is that the continuum hypothesis wasn't shown to be undecidable, but rather that it was shown to be independent.

The difference is that undecidable means, in some sense, impossible. You can't create a valid system in which an undecidable problem has a solution. But the continuum hypothesis is indepedent of the axioms we use for math - so you can create two different valid systems - one where it's true, and one where it's false. Neither one is incorrect - because the validity of the continuum is independent.

A good metaphor is geometry. You can take the basic axioms of geometry, omitting the parallel axiom. Then you've got the basic structure of a geometry. The parallel axiom in indepedent of the other basic axioms of geometry. So you can create a valid geometry by accepting it; or you can create other valid geometries by rejecting it and using something else.

Infinite sets are very counter-intuitive. A lot of things that seems like they should make sense don't. The set of even numbers is the same size as the set of integers - even though it seems as if it should be smaller. The set of rational numbers is the same size as the integers - even though it seems like it should be larger.

In fact, a definition of an infinite set is that it can be put in 1-to-1 correspondence with a proper subset of itself. So a set being infinite actually forces such nonintuitive things to happen!

#19:
It may seem intuitively obvious that there are different-sized infinities, but a little digging shows that the "intuitively obvious" examples don't actually work to show there are different sized infinities.

Cantor studied the question of what does it mean to say two sets are the same size, infinite or not. What he argued (and no one has come up with a better way since) is that two sets A and B are the same size if you can match each element of A with an element of B such that once you are done there are none of A and B left. You count the sides of a cube by matching them with the numbers 1, 2, 3, 4, 5, 6. We say there's a 1-1 correspondence between the numbers 1-6 and the sides of a cube, and that there's the same number of them.

This works intuitively well for finite sets, but for infinite sets you get what seems like confusing results. For one, a "modern", post-Cantor definition of an infinite set is a set which can be put into a 1-1 correspondence with a proper subset of itself.

An example of this are the positive integers. It's trivial to see that there's a 1-1 correspondence between positive integers and positive even integers, since you can pair integer n with even integer 2n. So the number of positive integers is the same as the number of positive even integers. It also means that the set of positive integers is infinite.

You can also come up with 1-1 correspondences of positive integers to positive odd integers (pair n with 2n-1), to all integers (pair 2n with n-1 and 2n-1 with -n), etc. So the various sets of odd, even, positive, and negative integers all have the same infinite size as the integers.

In your example, it's easy to come up with a 1-1 correspondence between integers and "numbers with two fractional places" (which I assume means numbers with two decimal places, like 3.14). Simply pair n with n/100. So there's the same number of integers and numbers with two fractional places.

What about fractions (rationals)? Certainly they are more complicated than integers. They are dense (given any two rationals a < b, there's a rational c such that a < c < b), which the integers aren't. surely there are more rationals than integers, right? Well.... Take the pairing of the rational m/n (in lowest terms) to the integer 2^m*3^n (so that 4/3 would be paired with 2^4*3^3 = 16*27 = 432). That's not a 1-1 correspondence because while every rational is paired with an integer, there are a lot of unpaired integers. But it's suggestive. There are better formulated 1-1 correspondences which work.

So there are the same number of integers as rationals.

The trick is showing that there are infinite sets which can't be put into 1-1 correspondences with the integers.

Mark, independent and undecidable are essentially the same thing. For a fixed axiomatic system S saying a statement A is undecidable means I can assume A or I can assume ~A along with S and neither will lead to any contradictions. So as an axiomatic system the system S + A has A independent of the other axioms as does the system S + ~A.

To use your example, if I take the axioms of geometry without the parallel postulate then the parallel postulate is undecidable in that context.

"We knew by several arguments [...] that the set R and N do not have the same cardinality and that there is no bijection between these two sets. In this paper, I show that there is a bijection between the set of integers and the set of real numbers."

And that didn't look, er, somewhat fishy? Well, he'll have a hard time getting that published. Maybe in some proceedings of some WSEAS conference, maybe.

And just to add to the series of counterintuitive infinity statements: there are just as many real numbers than continuous mappings from R to R.

Of course, everything Mark says is true. But I do think he misses out an important fact: the multiple infinities of set theory are consequences of our axioms of set theory.

There's no reason we have to have these axioms. A lot of mathematics is about finding interesting frameworks. But there's no grand metaphysics that says we have to use the set theory we do. Lots of smart people have done their best to make it match intuition and correspond to real-world considerations as well as possibleâbut that doesn't mean it's the only approach you can have.

It's entirely possible to come up with your own mathematics that only has one infinity. Ultimately, infinity isn't a physical concept at all.

Re #29:

That's true - but there's also a reason why pretty much all of modern mathematics relies on ZFC set theory to provide the basic axioms. It's hard to find a realistic, credible alternative to ZFC where everything that we expect to work, works.

You can create an axiomatization where Cantor's diagonalization won't work. But a lot of other things won't work either - which is why we tend to stick with ZFC.

The proof that for any set X, the cardinality of X is strictly less than its power set P(X) is quite elementary.

One would need axioms that, given a function f:X -> P(X), would prevent creating the set
Y = {x in X : x is not a member of f(x)}

(Because now if f is supposed to be surjective, then there is a y in X with f(y) = Y. But then we note that if y is an element of Y = f(y), then by definition y is not an element of Y; and likewise if y is not an element of Y, then by definition y is an element of Y.)

So your new set theory axioms force you to either have no infinite sets at all, or they force you to be unable to construct, given a set X and a formula, the subset of those elements of X that satisfy the formula.

What a horrid place to do mathematics!

Freak @ 18 & Mark @ 24:

Thanks for your replies. As I said, IANAM, but I had always read that Ernst Zermelo formulated the Axiom of Choice to address what he regarded as a hidden assumption in Cantorian set theory, and that it was possible to formulate set theories without it, which some people had done.

That's what I meant in my clumsy way: as Mark said, the Axiom of Choice is independent of the others, just like the Parallel Postulate, and you could take or leave it as you liked. I assume non-Cantorian set theory is a pretty bleak discipline, though.

And in my original post: the Axion of Choice is whatever you think the best Dark Matter candidate is. Spell-check is your friend!

In his book On the Hights of Despair, E.M. Cioran says the following in his short fragment, "The Cult of Infinity:" "Infinity leads to nothing for it is totally provisional. 'Everything' is too little when compared to infinity [...] The penchant for form comes from love of finitude, the seduction of boundaries which will never engender metaphysical revelations [...] Let us live in the ecstasy of infinity, let us love that which is boundless, let us destroy forms and institute the only cult without forms: the cult of infinity." Sometimes it may be worth not only remembering, but also considering what the poets have to say. Thanks for great posts.

#29: That the multiple infinities of set theory are consequences of our axioms of set theory is of course true. But you do not need anything as strong as ZFC to prove Cantor's theorem (in particular you do not need the axiom of choice - don't remember the name of that proof right away). All you need is basically the powerset axiom and the axiom of infinity. I am not sure a set theory that rejects the powerset axiom is worthy of the name (#31 puts it nicely). (Of course, the continuum hypothesis is another matter which cannot be proved even with ZFC (You need e.g. an axiom of constructibility to do that)).

"It's entirely possible to come up with your own mathematics that only has one infinity"

Well, based on the extremely limited resources needed to prove Cantor's theorem, it seems like you'd need something like a finitist approach to do that, and to come up with a finitist approach that could reasonably be called mathematics is far from trivial (no one has to my knowledge been even close yet).

Think the basic upshot is that if the arXiv guy's got it right, it'll basically be the end of mathematics as we know it. Fortunately he's not even close.

I'm beginning to think there are different types of infinity, as far as pedagogy is concerned. One of the ones I'm familiar with is infinity as a rate - ie, that something that is infinite is something that increases/decreases without bound. Under that, it's quite possible to have different infinities just by comparing rates of increase/decrease.

But keeping with the bijection definition - the only one I've seen offered (unless I missed one/some) to my question of mapping odd or even integers onto all integers is "f(n) = 2n" to map even to all. It seems rather trivial to me to point out that that only maps either odd or even onto even..

For the Banach paradox, stretching wasn't meant like a balloon. What I meant is that it seems like it creates the same volume and surface, but with less than the total mass, and if you added the mass of the two spheres together, they would only equal the original sphere in mass.

(btw, just pointing me at a resource on the net that addresses this is fine)

Re #35, with respect to Banach-Tarski:

It's meaningless to talk about mass with B-T. The B-T construction requires a very strange infinite deconstruction with indeterminate volume. It's not something that you can come close to actually creating in the real world.

If real-world matter were infinitely decomposable, and you had the capability to do the infinite subdivisions necessary to create the BT-sphere deconstructions, then you'd wind up with two spheres, and the density of the two spheres would be equal to the original sphere - because when you do the BT construction, you're not breaking the matter, you're not stretching it, and you're not leaving any gaps. So the density of it can't change.

Re #35 WRT bijections:

But keeping with the bijection definition - the only one I've seen offered (unless I missed one/some) to my question of mapping odd or even integers onto all integers is "f(n) = 2n" to map even to all. It seems rather trivial to me to point out that that only maps either odd or even onto even..

Why would f(n)=2n only map either odd or even onto even? Represented set form, that's the set of pairs { (0,0), (1,2), (2,4), (3,6), (4,8), (5,10), ... } - it maps every integer, whether odd or even, onto an even integer.

Re Banach-Tarski - I'll have to look more into that.

Re Bijections - Ah, misread the directionality (I was thinking f(n) was 'supposed' to result in the set of all integer, not all even integers). I had a response to this, but immediately realized it relates in a .. peculiar way to one of my earlier (unstated) ones, so I'll have to puzzle those two out.

Thanks, btw :-)

Re #27: Actually, there is a subtle difference between undecidable and independent. An independent statement is one such that either it or its negation may be added; either is consistent with the original axioms. However, an undecidable statement may in fact have a truth value, it is just impossible to prove. For example, the tradition Godel proof uses (roughly) the statement

S: This statement has no proof.

Now, it is not independent, for if we add (Not S), then there must exist a proof of S, which cannot happen, since if our original axiom system was consistent, you cannot prove false statements.

So, the way I would put it is this: Independent Statements are ones that we can arbitrarily decide are true or false, whereas Undecidable Statements may already be true or false, but we can never find proof of them (or their negation).

Re #27: Actually, there is a subtle difference between undecidable and independent. An independent statement is one such that either it or its negation may be added; either is consistent with the original axioms. However, an undecidable statement may in fact have a truth value, it is just impossible to prove. For example, the tradition Godel proof uses (roughly) the statement

S: This statement has no proof.

Now, it is not independent, for if we add (Not S), then there must exists proof of S, which cannot happen, since if our original axiom system was consistent, you cannot prove false statements.

So, the way I would put it is this: Independent Statements are ones that we can arbitrarily decide are true or false, whereas Undecidable Statements may already be true or false, but we can never find proof of them (or their negation).

Ah, it figures my first post here would be a double post.

Anyways, I should add that I really like your blog Mark. As I am a math grad student and someone who is passionate about math, it is great to see other people share this passion.

Buffdan at 40, yeah this gets into the whole issue of consistency v. omega inconsistency and into philosophical issues of the nature of truth.

GD at 34. You need much less than even that to get Cantor's results. You can instead of the powerset axiom have as an axiom that for any two sets A and B the cartesian product of A and B exists. If you have just that and the axiom that P(N) exists then you can get most of it right there.

Buffdan, undecidable and independent do mean the same thing. A very standard result is that for any collection of axioms A and any sentence S, if A ⪠{S} is inconsistent, then A proves ¬ S.

Concerning Gödel's proof, recall that he was using integers to code proofs, as logical sentences can't directly reference themselves. Adding S can result in a system that's still consistent if that coding breaks down. Specifically, in a nonstandard model of arithmetic.

So the cranks are posting to the arxiv now. Jeez.

I don't think it's possible to respond to shite like that without looking silly yourself. It's just like the problem of giving creationists credibility by debating them, except worse, because this guy is just flat-out mental.

Ok, I did some more reading and I see what you guys are saying about independent vs. undecidable, and omega consistency and all that jazz. Yes, of course there are non-standard models of arithmetic, and the whole point of being undecidable means it is independent of the standard axioms and it can be true in one of those. Thank you for correcting me (I really should know better).

I was thinking of it more from a naive philosophical viewpoint, which I think is where I went astray.

Just a side question: Is there a pair of infinite sets that differ in mapping by exactly one member?

Argon: Short answer: no. You can rig up a quick proof from the fact that every infinite set has a countable subset and that the natural numbers can be put in bijection with (the natural numbers plus and extra element).
Actually if you have a map f:A->B between infinite sets, and B has larger cardinality than A then the set of elements of B which are not in the image of f can always be put in bijection with B (in ZFC cardinality in ZF is messy).

Bob O'H@17: ArXiv does have some screening of papers; that's why it takes a couple of days for preprints to appear. I think they usually just shuffle maths-cranks to "general mathematics" but I'm pretty sure if someone persistently submits papers of no merit they take them down.

me: punctuation fail, sorry. Should be
"(in ZFC; cardinality in ZF is messy)."

I am just wondering. Given a System of axioms that include the powerset axiom. If I remember right, then a bijective mapping from X -> P(X) does not exist, if P(X) is the powerset of X. Basically this means: You cannot enumerate the Set of Sets of Natural numbers. But what happens if I construct the sequence a_n = P(a_(n-1)) and a_1 = X?

I cannot create a mapping from a_n to a_n+1, because a_n = Y and a_n+1 = P(Y), and thus a_n+1 has a greater cardinality than a_n. if X is infinite in the first place (for example the set of natural numbers), then this would show that there are (countably) infinite many infinities, wouldn't it?

I am just confused where my error is, because it looks way too easy, given the assumptions (Powerset axiom, |P(X)| > |X| in sloppy terms).

Tetha: Why do you think you made an error?

You've just constructed the Beth numbers.

Ah. I remembered the Continuum Hypothesis wrong and though I sorta solved it. However, looking at the simplicity of the construction, I though I had made an error, because someone would have to think of this before :)

Ok, now I see what you were thinking. The title of the post is somewhat misleading if you forget what the CH is. The only reason to mention CH is that the crank paper implies a trivial solution to CH. (Of course, being a false and contumelious paper, it trivially proves all hypotheses!)

Yeah, so the Continuum Hypothesis says there's no cardinal between beth-0 and beth-1 (equivalently, beth-1 equals aleph-1). Not being a set theorist myself, I always forget whether it's aleph-1 or beth-1 that's the cardinality of the real numbers (it's beth-1).

btw, MarkCC: Since your comments stick out in bold colors, it might be nice if you corrected your comment #24.

Re #20

The "non-repeating" part gives some folks difficulty. What it means is that for any finite group of consecutive digits in its representation, that group does not repeat for the remainder of the representation.

That is not what "non-repeating" means. In fact, it is provably impossible for any irrational number to comply with that definition. Suppose we're looking at groups of 5 digits. There are only 10^5 combinations of 5 digits. It is therefore guaranteed for any sequence of more than 100,000 digits to have at least one non-unique 5 digit sequence. As a concrete example, the first five digits of pi after the decimal place, 14159, are repeated within the first million digits.

In fact, if pi is normal, as it is believed to be, then it contains every finite sequence of digits. This means that at some point, it contains a sequence of 8 billion zeroes.

"Non-repeating" simply means that the digits are not an infinitely repeating pattern, of any size, no matter where you start looking.

I've seen this arguement before (or atleast a variation of it) by a mathematics professor from Russia named Alexander Zenkin (I believe he has a doctorate in mathematics).

It is also my understanding that each branch of the tree is infinite so the pi is represented by one (and only one) branch of this tree. Likewise, the Natural numbers are also each represented by one (and only one) branch of the tree and NOT as Mark asserts as a finite length of the tree. In other words the finite number .32 would be the branch in the tree containing .32000..., i.e. followed by an infinite number of zeros. This is also how 1/3 is represented and why .9999... is the same 1. I'm not saying that the guy's arguement is correct but only that Mark is misrepresenting it.

Actually the person made the binary tree arguemnt was Jailton C. Ferreira and his paper is here - http://arxiv.org/vc/math/papers/0108/0108119v1.pdf
Abstract
Each real number of the interval [0, 1] can be represented by an infinite path in a given binary tree. The binary tree is projected on a grid NÃN and shown that the set of the infinite paths corresponds one-to-one to the set of natural numbers.

However, Zenkin is fairly well known for his views on Cantor and Zenkin's paper is referrenced all over the internet. His paper can be found on the website -
http://alexzen.by.ru/list%20of%20papers.html
then search for
Logic of Actual Infinity and G.Cantorâs Diagonal Proof of the Uncountability of the Continuum
Unfortunately, I can't link directly to it.

Well, the path you give for 0.32 is a very special path -- one which goes all the way in the same direction after a while. This is the direction given by the sequence of 0's you append after the last nonzero digit.

Actually, not every infinite path can represent a decimal number 0.something finite: in fact, in order to represent one the path *must*, after a finite number of variations, go all the way in the same direction as the one for 0.32.

A real number by definition corresponds to *any* choice of path, no matter how erratic or complicated. Therefore there are 'more', in a loose sense. Cantor's diagonal argument shows that there are 'more' in a precise sense.

For integers, you can, of course, represent them by an infinite path if you like, but, as Mark says, you can *also* use a finite path. For real numbers you *cannot* use a finite path, no matter how astutely you proceed.

By the way, since you obviously disagree with Mark's argument (and, seemingly, with Cantor's), could you point out where you think it is wrong, or at least unclear?

Fair enough, Toybox. However, to do so will take a little thought on my part so give me a day or so. BTW, I don't think Cantor is wrong -- I just don't think all the cranks are wrong either.

Of course, take your time :-)

It also depends what you mean by 'crank' -- if someone comes up with a result flatly contradicting Cantor's, then he or she has to be wrong. But even in that case, it may happens that the mistake is very subtle, and trying to identify it can then be instructive as well.

All right here is my response --
http://www.1001books.com/cantor.aspx

At the website I will use a binary tree to place all the numbers of the continuum into a list, and then apply the same reasoning used by Cantor to create a new number not found in the list. This is followed by an anti-Cantor viewpoint, labeled "Another View --"

This is a great post!
I want to emphasize something that Mark wrote: "The only way to compare infinite sets is by looking for bijections."
Mark is explaining this well. I just want to add that addition, subtraction multiplication between infinite and finite numbers is meaningless. For example, the prase "infinity plus one" does not make sense; if we think of "infinity plus one" as the cardinality of the union of an infinite set and a disjoint set with cardinality one (like the amount of Natural numbers together with a single extra thing), then "infinity plus one" has the same cardinality as "infinity" because a bijective mapping can be found between the two sets.

Also, the Continuum Hypothesis (CH) has nothing to do with Cantor's diagonalization argument. Mark and Germain mention the CH because if Germain proof were right, the CH would describe a world that didn't exist. But there are different sizes of infinity, assuming CH or not.
Or what I mean is: if we do not assume the CH, there are still different sizes of infinity because of Cantor's diagnolization argument. CH just talks about something different.

@45
1. Mark does not look silly writing about this stuff. Mark explains the subject matter well to many people who are unexposed or interested. When Mark responds to specific papers he is motivated by the broader topic.
2. Everything respectful Mark said about the author of the bad proof is true.

@56 Reading the document, Mark did not misrepresent the argument. The paper does not map from branches to real numbers, and sadly, it does map one particular node to pi.
(Also, knowing what natural number maps to .32000..., what maps to .3333... ?)

Cantor's diagonal argument for an uncountable set is a joke. It's using the fact that a sequence with 2n digits has more combinations than a sequence with n digits. Sorry, but this is a FAIL of epic proportions. IOW, it's using properties of finite sequences and applying them to infinite sequences.

WOW, I can't count to 2n if I can only use n numbers. Well, DUH! There's no contradiction here folks.

.010101... maps to .333...

Daithhi,
.010101... is not a natural number. If we are mapping from the natural numbers to the real numbers then you must have a single natural number map to .3333...

Vorlath,
2^n does not have the same definition as when n is finite, so we are not using any properties from finite numbers. 2^n is defined as the cardinality of the powerset of a set with n elements. It is easy to show that the powerset has a larger cardinality than the original set.

Mike,

Your missing the point. I can create a binary tree in which every path in that tree represents represents a number. The first path is 0.000..., the 2nd path is whatever number comes after 0.000..., and so on up to 0.999... which is the last path. The number 0.0101... has one path in that tree, as does the number that represents the binary expansion of pi, and in fact every number in the continuum has a path. If you are asking me what is the cardinal number of the path of for 0.0101... well, I have no idea. Then again, I'd ask you what number comes after 0.000...?

My bottom line is that I think you can approach math from the traditional perspective of Cantor's diagonal arguement, but I also believe you can approach math from the perspective that Cantor's Diagonal arguement is meaningless. I also think the second approach may lead to some interesting math, but anyone that doesn't swallow the party line on Cantor is labeled a 'crank' which leads to areas of mathematics not being persued.

Daithi,
You say that you can have every branch correspond to a natural number.
1 corresponds to 0.000...
2 corresponds to what? You wrote "the number after 0.000...". But that to me is not clear. What exactly is "the number after 0.000...? Is it pi? Is it the square root of 2? .00100..? .00010...?

Finally, what natural number corresponds to 0.333...? That is, what natural number corresponds to the branch .0101...?
Those are legitimate questions because you claim the branching method describes a mapping from the naturals to the reals.

0.000... is not 1.
0.000... is 0 and is the first path in the tree.
Just like you don't know what number comes after 0.000... neither do I. I just know that there 'is' a number that comes after 0.000... and it is the 2nd path in the tree. Likewise, I don't know the number of the path that corresponds to pi or any other number in the tree, but I do know that each and every number has a path in the tree.

Take a look at the website I provided in #61 as it provides a nice pretty picture and detailed explanation.

Re #69:

No, there isn't a number that comes after 0.0000.. And that's the point that you're missing.

You're talking about taking an infinite construction, and treating it as if it's finite.

In this binary tree construction, which real number is the right sibling of 0?

In this binary construction, for any real value, what's its immediate right-sibling?

That may seem like a silly question - but one of the fundamental properties of the natural numbers; one of the properties that pretty much define the natural
numbers is "successor". For any natural number, there is exactly one natural number
that is its successor.

For the rationals, I can answer questions like that. Using the mapping of naturals to rationals, I can answer questions about the successors. What's the successor of 1/2 in the natural to rational mapping? 3. What's the successor of 3? 1/3. What's the successor of 1/3? 4. What's the successor of 4? 3/2. And so on.

(I'm using the classic table construction for the mapping. I should probably do a post on it, since it's interesting and appropriate. The beginning of the mapping is: (0,0),
(1,1), (2,2), (3, 1/2), (4, 1/3), (5,4), (6, 3/2), (7, 2/3), (8, 1/4), ....)

You're claiming to be able to create a perfect one-to-one mapping between the reals and the naturals - but you can't identify any part of it. You can't describe any of the properties of that mapping - because it's a non-existent mapping. The "leaves" of the infinite binary tree aren't countable - and that's the fundamental reason that you can't answer questions about things like the successor relationship.

Worse, you don't even both to address Cantor's construction. This is one of things that drives me batty about anti-Cantor crankery. What Cantor showed was that given any putative mapping between the natural numbers and the reals, that it was possible to construct a member of the reals that isn't included in the mapping. He didn't show that there was a flaw in a mapping - he showed that there was a flaw in every possible mapping. If you can't show the error in Cantor's proof, then no amount of babbling about how perfect your construction is is worth a damn thing. If there's no error in Cantor's proof, then it shows how to construct a counterexample to your claim that your construction is a complete mapping. Period.

Your argument that you've got a mapping basically comes down to a claim that Cantor's proof is flawed. But you don't show hom.

You don't need to specifically find the flaw in Cantor - but you do need to explain why Cantor's diagonalization won't construct a counterexample to your claim. If you can't do that, you've got nothing.

Actually, Mark, if we accept the Axiom of Choice then there does exist a total ordering on the Real numbers, meaning there is a single number that directly follows 0.000...
You can prove this using Zorn's Lemma on the set of partial well-orders of the Reals.

But, Daithi, if you claim there is a mapping from the Naturals to the Reals then you must define it, and when you do Mark is right that the diagonalization argument will construct a number not included in the mapping.
So far, if your mapping can't tell me what 1 maps to then I don't believe it maps to anything, which is silly because naturals to the Reals is the easy direction. I mean, there is not much else to say. How can we analyze a mapping if we don't know what the mapping is, what maps to what and how?
Sure, you might talk about branches to the Reals, but what about from natural numbers to branches? I guess that assuming a mapping from Naturals to the branches is equivalent to assuming a mapping between the Naturals and Reals, which is what you are trying to show.

Apparently I am far worse at explaining my position than I envision it in my head. I think I am being clear, but obviously that is not the case. I don't know if I'll do much better with this post, but I'll try.

First of all, I am not arguing that I can "create a perfect one-to-one mapping between the reals and the naturals." Nor am I arguing that Cantor is even wrong.

What I am arguing is that the results of Cantor's Diagonal argument can be interpreted in more than one way. Cantor's argument in a nutshell is, "Start with the assumption that you can place all the Real numbers into a list. Then a new Real number can be produced that is not in the list but yet must be in the list." The traditional view of this result is that it means the Real numbers cannot be counted. I am arguing that an even simpler view of Cantor's argument is possible -- "the concept of arranging all the Real numbers into a list is meaningless."

Mark, you chastise me for treating the Real numbers as if they were finite. Yet, this is exactly what Cantor's Diagonal argument does. You also claim that there isn't 'a' next number after 0.000... but according to Cantor there is 'a' next number. It is only if you accept 2nd interpretation of Cantor's argument that the concept of the number that follows 0.000... becomes moot. It is the 2nd interpretation that says it is meaningless to refer to the number that follows 0.000... because you would need to treat an infinite concept as though it were finite.

My use of the binary tree was not an attempt to show that Cantor was wrong. It was simply a restating of Cantor's diagonal argument. I thought that the binary tree was an excellent way to show Cantor's argument because unlike the original diagonal argument the binary tree places the list of numbers in order. This made Cantor's argument clear in my mind and I thought it would do so in the mind's of others -- apparently not.

"Start with the assumption that you can place all the Real numbers into a list. Then a new Real number can be produced that is not in the list but yet must be in the list."

Daithi,

First, in order for there to be the same number of Naturals as the Reals there must exist a perfect one-to-one mapping between the Reals and the Naturals, as you put it.

Second, Cantor's diagnolization argument does not require the assumption that the Real numbers can be put into a list. One must only assume that there is a one-to-one mapping of the Naturals onto the Reals. That is all it takes to construct a contradiction.

Also, Daithi, in your last post you use the word "finite" when you really meant "countable."

First, I am NOT arguing that there are THE SAME NUMBER OF NATURALS AS REALS!!!!
I am sorry for yelling but I don't know how to be any clearer.

Second, if your position is that the Cantor Diagonal argument does not require the assumption that the Real numbers can be put into a list then clearly you do not understand the Cantor diagonal argument.

Finally, I said "finite" when I meant "finite".

After rereading my post I saw that I used the term "finite" in response to Mark chastising me for "taking an infinite construction, and treating it as if it's finite." However, you were right, I actually did mean "countable".

Is there any difference between 'putting (something) in a list' and finding a bijection with the natural numbers? (Yes yes, provided this something not a finite set).

Actually the tree proof works fine, just as well as Cantor's apparently -- except it should be made clear that the sequences s1,s2,... need not be (and, indeed, can not be) in order. Here, "in order" is by means of the usual order of real numbers.

Of course you can find other orderings of real numbers. This includes a well ordering (every subset has a minimal element), but this would be a very messy order which cannot be compared to the one we know and use routinely.

Daithi,

I understand the diagonalization argument.
Existence of a bijective mapping between the Naturals and the Reals implies that the Reals can be listed, but one does not need the list to execute the argument. Here it is without the list:

Assume f:N->R bijective
Define g:N->{0,1} by g(i) = 0 if the ith decimal value of f(i) =/= 0 and g(i) = 1 if the ith decimal value of f(i) = 0.
Describe a real number, r, with ith decimal value being g(i).
Function f does not map to r because for all i in N, f(i) differs from r in the ith decmial place, and f is thus not bijective.

Now, Diathi, I see that you don't disagree with Cantor, but the cranks are indeed nothing but wrong if they cannot reconcile the simple diagonalization argument.

this might be trivial, because this argument seems clearly fallacious if by no other reason then that cantors proof is sound. but what if instead of refering to different cardonalities as larger than each other we said that one was denser than another; would that cause less discomfort?

just a thought, by the way i am new to this site and i am really enjoying it.

Step 1. Map natural number 0 to real number 0.
Step 2. Map real number not already listed to a natural number not already listed.

Why does induction not work in this case?

BTW, I'm afraid Cantor's theory actually *IS* flawed. It's comparing two different bases. Listing of elements is analogous to base 1 while the representation of digits is usually done in another base. Take the example on wikipedia, we know that you can only produce 'base' number of new entries. So just take that many extra natural numbers for each N digits and you have a one to one mapping.

if the sets m = x * n are mapped one to one, then so is Cantor's theory. Compare the same base and you'll have a really hard time proving anything with Cantor's theory. Until that mistake is fixed, you're comparing two different representations. It's like assuming that 10 base 2 = 10 base 10 and then showing a contradiction proving that 10 != 10 for all bases even if they have the same base. I know contradictions are supposed to show the absurd, but this is ridiculous.

USE THE SAME BASE!!!

Sorry, that should be base^(N-1) more entries where N is the number of digits.

BTW, the following is what Cantor's theory is saying.

You can use base 10. I can use base 2. But each one of us can only use digits 0 and 1. Since base 10 can always come up with numbers not found in base 2 using the same number of digits, then base 10 is uncountable.

It's not an analogy. It's an EXACT definition of what Cantor's theory is.

I know most people believe Cantor's theory, but I'm laughing my head off.

Mark, you are incorrect about finite numbers. A finite number is simply one which is not infinity. So just because a representation has infinite digits, this has no significance at all as to whether or not a number is finite. A representation is completely arbitrary. It's a personal choice in how you identify each element.

BTW, comparing different representations is also Cantor's mistake.

Apologies for posting again, but I thought this was an important point.

I may be going completely off the rails (cf. "A little knowledge is a bad thing") but, consider any infinite set X and a model M of the type used in nonstandard analysis (for instance, X could be the reals, M a superstructure). Then, by the downward LöwenheimâSkolem theorem, M has a countable submodel (the bijection showing countability being external), and in this submodel, X itself must be (externally) countable.

In this way, all sets can be considered countable.