Of all of the work in the history of mathematics, nothing seems to attract so much controversy, or even outright hatred as Cantor’s diagonalization. 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. As a result, countless people bothered by this have tried to come up with all sorts of arguments about why Cantor was wrong, and there’s only one infinity.
Today’s post is another example of that. This one is sort of special. Unless I’m very much mistaken, the author of this sent me his argument by email last year, and I actually exchanged several messages with him, before he concluded, roughly “We’ll just have to agree to disagree.” (I didn’t keep the email, so I’m not certain, but it’s exactly the same argument, and the authors name is vaguely familiar. If I’m wrong, I apologize.)
Anyway, this author actually went ahead and wrote the argument up as a full technical paper, and submitted it to arXiv, where you can download it in all it’s glory. I’ll be honest, and admit that I’m a little bit impressed by this. The proof is still completely wrong, and the arguments that surround it range from wrong to, well, not even wrong. But at least the author has the Chutzpah to treat his work seriously, and submit it to a place where it can actually be reviewed, instead of ranting about conspiracies.
For those who aren’t familiar with the work of Cantor, you can read my article on it here. A short summary is that Cantor invented set theory, and then used it to study the construction of finite and infinite sets, and their relationships with numbers. One of the very surprising conclusions was that you can compare the size of infinite sets: two sets have the same size if there’s a way to create a one-to-one mapping between their members. 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. Using that idea, Cantor showed that if you try to create a mapping from the integers to the real numbers, for any possible mapping, you can generate a real number that isn’t included in that mapping – and therefore, the set of reals is larger than the set of integers, even though both are infinite.
This really bothers people, including our intrepid author. In his introduction, he gives his motivation:
Cantor’s theory mentioned in fact that there were several dimensions for infinity. This, however, is questionable. Infinity can be thought as an absolute concept and there should not exist several dimensions for the infinite.
Philosophically, the idea of multiple infinities is uncomfortable. Our intuitive notion of infinity is of an absolute, transcendent concept, and the idea of being able to differentiate – or worse, to be able to compare the sizes of different infinities seems wrong.
Of course, what seems wrong isn’t necessarily wrong. It seems wrong that the mass of something can change depending on how fast it’s moving. It seems even more wrong that looked at from different viewpoints, the same object can have different masses. But that doesn’t change the fact that it’s true. Reality – and even worse, abstract mathematics – isn’t constrained by what makes us comfortable.
Back to the paper. In the very next sentence, he goes completely off the rails.
As a matter of fact, if the set N is an infinite set it should be of same power as the set R. This has not been proven so far. We knew by several arguments, and in particular by the argument of Cantor’s diagonal, 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. I show that the set R is countable and that there is only one dimension for infinite sets, ℵ.
(In this quote, N and R are the set of natural numbers, and the set of real numbers, respectively.) “This has not been proven so far” is a classic line. In fact, not only has in “not been proven so far”, it’s been disproven, as he admits in the next sentence. So, he goes on to say that Cantor proved that there is no possible bijection (total, onto, one-to-one mapping) between the natural numbers and the reals; and that he’s going to show us one.
If someone wanted to show that one of the most well-known, respected, widely analyzed and accepted proofs in all of mathematics is wrong, you’d think that they’d show just why the proof is wrong. In particular, Cantor’s proof shows you that given any purported mapping between the integers and the reals, you can create a member of the reals that isn’t included in the mapping. It doesn’t show you that for one particular mapping; it shows a procedure that can defeat any possible mapping. So you’d think that the author of the paper would show why Cantor’s proof wouldn’t apply to his proposed mapping. But he doesn’t. He just ignores Cantor’s proof, because his mapping is, apparently, so obviously correct that it doesn’t need to address Cantor.
So what’s his argument?
Basically that he can construct a mapping based on trees. He starts by defining a tree over the set of all possible natural numbers (he says “integers”, but his construction doesn’t include negatives.) The basic structure is what we CS people call a Trie. The root of the tree is “0”. “0” has ten children: 00, 01, 02, 03, 04, 05, 06, 07, 08, 09. Each of those has ten children. And so on, forever.
In this tree, every possible number is associated with one node of the tree. For any possible number n in N, there is exactly one path in the tree that leads to n. What he neglects to notice is that for any possible member n of N, the path from the root of the tree to n is finite.
The set of finite length paths in this number-trie corresponds exactly with the set of natural numbers – it’s a perfect bijection between nodes of the tree, and members of N.
Next, he goes on to show that the cardinality of N is supposedly equal to 10ℵ0. The argument really doesn’t make a lot of sense:
Proof :Each integer is a node of the tree. The set of the nodes in the tree is bijective with the set of integers. When N is large, counting the number of nodes is the same as counting the number of paths (to infinity) in the tree. The cardinality of the set of the nodes of this infinite tree is 10 ℵ0 counted 9 times. Indeed, we see in Figures 1 and 2 that the set N is of cardinality (0, 1, 2, 3, 4, 5, 6, 7, 8, 9) N counted 9 times. This implies that the cardinality of the set N is 10ℵ0 As ℵ0 represents the cardinal of N, which is by definition the cardinal of the set of the nodes in the tree (bijective with N), we get 10ℵ0 = ℵ0. Note already that this implies that 2ℵ0. This proposition shows that the cardinality of N, ℵ0 , is equal to 10ℵ0. In the next proposition, I compute the cardinality of the powerset of N.
The nonsensical part (or rather, the most obvious nonsensical part) is that he talks about “When N is large”, even though N is the set of all integers… The set of all integers doesn’t get large.
The basic error, though, is the same as above: he’s got an enumeration of all finite length paths. Everything that he says is talking about the set of finite-length paths. Because natural numbers are all finite-length. An infinite-length string of digits isn’t a natural number, or an integer. And so everything else in that “proof” breaks down.
You can probably guess where he’s going next.
For the real numbers, he also constructs a tree. It’s sufficient to show that there is a bijective mapping between the set of real numbers between 0 and 1 and the set of natural numbers – because the size of the set of reals between 0 and 1 is the same as the size of the set of all positive reals, and the set of all positive reals is the same size as the set of all reals.
So, he constructs another tree. This time, instead of the tree starting with “01”, “02”, “03”, …, it starts with “0.1”, “0.2”, “0.3”, … . This tree will, he asserts, eventually include all possible real numbers. There’s obviously a bijection between the nodes of this tree, and the nodes of the integer tree – and therefore, a bijection between the integers and the reals.
The key question to seeing the error here is to ask: what’s the member of the natural numbers tree that corresponds to π?
And the answer is: there isn’t one.
The integers are all, necessarily, represented by finite length paths in the tree. But π isn’t finite-length. Any natural number from the natural numbers tree will correspond to a finite prefix of π, but no integer will ever correspond to π. In fact, you can only ever see the node representing the value of π after you’ve build ω levels to the tree – that is, after you’ve built a tree whose depth is the same as the cardinality of the set of integers, and you’re on the step after that – that is, you’re on the ω+1th step of tree construction. But if you’re on the ω+1th step, then you’ve got an infinity which is strictly larger than ω!
After that, he uses it to show that there’s only one infinity, and that’s it! He’s done! Not a mention of Cantor’s diagonalization, or why his construction is immune to it. Even if the finite/infinite length path issue wasn’t so glaringly obvious, the fact remains that Cantor’s diagonalization shows how to produce a counterexample to any possible mapping from the naturals to the reals. If Cantor’s proof is correct, then even if he showed a compelling looking construction, it wouldn’t matter – because without showing an error in Cantor’s proof, without showing how his construction escapes from Cantor’s trap, the diagonalization shows that his construction is invalid. But he never addresses that at all. He just pretends that it’s not there, that there’s no problem.
And so, we’re forced to conclude, we’re looking at just another crackpot who’s convinced that he must be right, because it’s obvious that there can’t be anything larger than infinity.
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!
you are funny!
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.
It drove me crazy, so I decided that infinity was not a place I wanted to go. Life’s too short.
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:
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.
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
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:
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
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.
Pingback: Yet Another Cantor Crank | Good Math, Bad Math
Erm…one teensy quibble (I’ve only read this after you linked from “Yet Another Cantor Crank,” right after I got done editing a textbook chapter on special relativity).
Saying that mass increases with velocity in special relativity is, nowadays, to borrow a term from the IT field, “deprecated.”
To be sure, it is an attractive interpretation at first glance, and might seem like a more convenient formulation than leaving mass alone and putting the interesting (or weird, if you prefer) relativistic effects into the definitions of momentum and energy. You can probably even come up with an accurate and consistent model based on mass change as the method of describing the interesting effects of special relativity. However, such a model will probably have somewhat greater complexity in some of the derivations (kinetic energy comes to mind) than one with the interesting effects in momentum and energy, and be more pedagogically challenging.
So nowadays (this is a recent development) we prefer a model where mass is a fixed quantity, measurable only at rest, and the relativistic effects are in the definitions of momentum and energy. Which gets into the philosophical point that we only measure things in mass, length, and time instead of energy and momentum for the simple reason that the former are much easier to construct measuring devices for.
All numbers from 0-3 can be mapped to 0-1 if we compare x/3 but if we compare x-2 then only points from 2-3 are mapped to 0-1.
This is totally absurd. It depends on how you map the points. Things like these result in something like
http://en.wikipedia.org/wiki/Bertrand_paradox_(probability)