# Yet Another Cantor Crank

I get a fair bit of mail from crackpots. The category that I find most annoying is the Cantor cranks. Over and over and over again, these losers send me their "proofs".

What Cantor did was remarkably elegant. He showed that given anything that is claimed to be a one-to-one mapping between the set of integers and the set of real numbers (also sometimes described as an enumeration of the real numbers - the two terms are functionally equivalent), then here's a simple procedure which will produce a real number that isn't in included in that mapping - which shows that the mapping isn't one-to-one.

The problem with the run-of-the-mill Cantor crank is that they never even try to actually address Cantor's proof. They just say "look, here's a mapping that works!"

So the entire disproof of their "refutation" of Cantor's proof is... Cantor's proof. They completely ignore the thing that they're claiming to disprove.

I got another one of these this morning. It's particularly annoying because he makes the same mistake as just about every other Cantor crank - but he also specifically points to one of my old posts where I rant about people who make exactly the same mistake as him.

To add insult to injury, the twit insisted on sending me PDF - and not just a PDF, but a bitmapped PDF - meaning that I can't even copy text out of it. So I can't give you a link; I'm not going to waste Scientopia's bandwidth by putting it here for download; and I'm not going to re-type his complete text. But I'll explain, in my own compact form, what he did.

It's an old trick; for example, it's ultimately not that different from what John Gabriel did. The only real novelty is that he does it in binary - which isn't much of a novelty. This author calls it the "mirror method". The idea is, in one column, write a list of the integers greater than 0. In the opposite column, write the mirror of that number, with the decimal (or, technically, binary) point in front of it:

Integer Real
0 0.0
1 0.1
10 0.01
11 0.11
100 0.001
101 0.101
110 0.011
111 0.111
1000 0.0001
... ...

Extend that out to infinity, and, according to the author, the second column it's a sequence of every possible real number, and the table is a complete mapping.

The problem is, it doesn't work, for a remarkably simple reason.

There is no such thing as an integer whose representation requires an infinite number of digits. For every possible integer, its representation in binary has a fixed number of bits: for any integer N, it's representation is no longer that . That's always a finite integer.

But... we know that the set of real numbers includes numbers whose representation is infinitely long. so this enumeration won't include them. Where does the square root of two fall in this list? It doesn't: it can't be written as a finite string in binary. Where is π? It's nowhere; there's no finite representation of π in binary.

The author claims that the novel property of his method is:

Cantor proved the impossibility of both our enumerations as follows: for any given enumeration like ours Cantor proposed his famous diagonal method to build the contra-sample, i.e., an element which is quasi omitted in this enumeration. Before now, everyone agreed that this element was really omitted as he couldn't tell the ordinal number of this element in the give enumeration: now he can. So Cantor's contra-sample doesn't work.

This is, to put it mildly, bullshit.

First of all - he pretends that he's actually addressing Cantor's proof - only he really isn't. Remember - what Cantor's proof did was show you that, given any purported enumeration of the real numbers, that you could construct a real number that isn't in that enumeration. So what our intrepid author did was say "Yeah, so, if you do Cantor's procedure, and produce a number which isn't in my enumeration, then I'll tell you where that number actually occurred in our mapping. So Cantor is wrong."

But that doesn't actually address Cantor. Cantor's construction specifically shows that the number it constructs can't be in the enumeration - because the procedure specifically guarantees that it differs from every number in the enumeration in at least one digit. So it can't be in the enumeration. If you can't show a logical problem with Cantor's construction, then any argument like the authors is, simply, a priori rubbish. It's just handwaving.

But as I mentioned earlier, there's an even deeper problem. Cantor's method produces a number which has an infinitely long representation. So the earlier problem - that all integers have a finite representation - means that you don't even need to resort to anything as complicated as Cantor to defeat this. If your enumeration doesn't include any infinitely long fractional values, then it's absolutely trivial to produce values that aren't included: 1/3, 1/7, 1/9.

In short: stupid, dull, pointless; absolutely typical Cantor crankery.

• Joel says:

Why did it need to be in binary? It seems to me that this would attempt, and fail, just as well using a decimal representation.

• Engineer says:

I remember reading in a textbook that Cantor's proof is tricker to do in binary because 0.00...0011111.... = 0.00..010000..., and since your only option to construct a new real number is by flipping bits, you have to show that you don't get into this pathological case with your new member. The book said the same thing about avoiding 0.00..009999... and 0.00..01000... in decimal notation.

If you agree that the countable union of countable sets is countable then Cantors diagonal scheme generates only a countable set and never proved the existence of a nondenumerable set. In fact, no one has ever constructed a nondenumerable set. What Cantor accomplished is: he generated a countable subset of the real numbers.

• Andrew says:

Joel: That's because some people think that proof by obscurity is a valid technique (not to say that I think binary is obscure, but they probably do).

I'm going to repost my blurb about constructive mathematics and Cantor's proof that I posted to another blog...

It’s worth noting that while, yes, the real numbers are uncountable in ZFC, some of us think ZFC is a bunch of hogwash. I prefer a foundation more like constructive type theory, but Constructive ZF is okay I guess.

These theories essentially exploit the fact you mention, “every consistent first-order logic has a model with a countable universe”, to say “well, fine, then we don’t need uncountable sets — let’s design a theory without them”. Here, Cantor’s proof is still valid, but it says that there is no *total* surjection from the natural numbers onto the reals; but it is consistent to assert that there is a *partial* surjection (see http://en.wikipedia.org/wiki/Subcountability ), which we can interpret as saying “there is at most as many real numbers as there are naturals”. And constructively, we cannot turn a partial surjection into a total surjection the same way we can in classical mathematics.

The intuition here is that we are actually dealing with the “computable reals”, of which there is certainly at most countably many, since there are only countably many computer programs (with which to compute real numbers). The partial surjection can be implemented by de-Godeling the natural number to a program which we interpret as a real number. It’s necessarily partial because not all programs can be (constructively) interpreted as real numbers (the halting problem means we don’t know if a program is going to eventually give us another digit, or if it’s just going to loop forever).

So while there are uncountably many reals in ZFC, I take that to mean “Let’s throw out ZFC”.

I’ll follow that up by suggesting that maybe the Counts are just constructivists who don’t realize they’re constructivists.

• MarkCC says:

Personally, I think that that's a remarkably strange point of view for a mathematician. What it comes down to is: I can't say why it's wrong, but I'm sure it is, so I'm going to throw away the entire theory behind it.

*If* you could show why it's wrong, that's one thing. But you can't do that. You just don't like the result, and so you're saying that because it offends your aesthetic sense, that it must be wrong and so you're going to throw it out.

• Andrew says:

It's not so much about it offending my aesthetic taste, and it's certainly not *only* because of the uncountability of the reals that I have a constructivist bent. It's more of a question of whether what we "gain" from ZF over, say, constructive type theory, is worth what we "lose". How do you feel about the Banach–Tarski paradox or results like "every set can be well-ordered" (even the real numbers)? For many these results cast some doubt on whether the axiom of choice is "worthwhile".

In classical ZF we "gain" the ability to prove results with excluded middle, which from my perspective is a "lazy man's shortcut" for proving that a property is decidable (and some just aren't -- we live with it).

We lose "tangibility"; there are more real numbers than we can ever "get our hands on". Enumerability is in some sense the "only way" we can get our hands on infinity in the "real world". And we lose the property that existence proofs actually demonstrate witnesses (they can just refute the non-existence of one).

We lose the ability to interpret proofs as programs (this actually really deep and cool and has been influencing programming language design in really cool ways for a few decades now). Believe it or not, but I find constructive proofs more intuitive because there's less choice when proving a result -- I know that if I'm expected to prove the existence of a real number, I *must* exhibit a Cauchy sequence (either directly, or by appeal to a lemma that exhibited one) -- importantly, I don't have the choice to reason by contradiction ("well, there's not not one...")

Also I need to point out that many mathematicians have the wrong idea about what constitutes a "proof by contradiction". The proof that sqrt(2) is irrational is still valid constructively. It's a proof of negation: "it is not the case that sqrt(2) is rational ", *not* a proof by contradiction.

Basically, by working in a constructive framework, I feel that we stay closer to the realm of "what we can get our hands on", instead of working far off in "imaginary land". The problem with "imaginary land" is that it's *arbitrary*. Axiom of choice or axiom of determinacy? They're incompatible, and the choice has deep impacts on weird fields like classical model theory. More real numbers than we can point our fingers at? No thanks. Let's stay closer to what is "tangible" to us and not worry about this stuff.

FYI, I don't identify myself as a mathematician. Certainly I study math, but not the kind that the people who label themselves as "mathematicians" do. I prefer computer scientist or logician.

• John Fringe says:

The fact that you enclose almost all your arguments in quotation marks makes me thing it's effectively an aesthetic decision XD

Not being "tangible", not being able to "get our hands on" them, being "the lazy man's shortcut", not of the "real world", but of an "imaginary land"... Can't not you say the same for imaginary numbers? I don't expect to see an imaginary height. But, as people studied them, we know complex numbers are useful.

You may believe that we can not "point" to noncomputable numbers, so we should discard them. But, what's then the probability for an arbitrary program to stop? Chaitin's omega may not be computable, but we can "point" to it, in a certain sense. If you discard these numbers, how do we talk about that probability? If it's not a number, then what? Because if it's another concept, we could rename that concept "number", probably.

Having said all that, I don't see any problem in you restricting yourself to computable numbers and constructive proofs. You can develop an interesting and rich theory there. But just be aware of your choice and the fact that there is a whole world out there.

You're making arbitrary choices, too 🙂

• Andrew says:

Yes, many of my reasons are aesthetic. One very important one is not: I can view proofs and programs as the same thing, and make use of a great exchange of ideas between proof theory and programming. Do this long enough, and you'll probably start to question why you ever bothered with excluded middle in the first place; it never really did anything for you.

Imaginary numbers are "imaginary" in a different sense, of course. I may not be able to point to something with an imaginary height, but I can point to an object rotating and scaling in 2D space and say that it's described by a complex number.

As for Chaitin's constant: It's plainly not a well-defined concept in constructive settings. There, you cannot point to it, because in order to define it you need to use the assumption that every program either halts or does not. So we simply don't talk about it. Because who cares?

> But just be aware of your choice and the fact that there is a whole world out there.

I'm fully aware of the classical world. It's hard not to be. I'm more concerned about all the classical mathematicians who don't know they're making a very unnecessary and controversial choice or that there's another world out there with beautiful properties and which stays more down to earth.

• Andrew says:

And even though Chaitin's constant is not computable and not definable constructively, it is definable classically. And once again there are only countably many definable numbers -- they are always expressed in a fixed logical system, in which there are only countably many possible definitions. You plainly can't convey an uncountable set as well as you can convey enumerable sets.

• John Fringe says:

> "I'm more concerned about all the classical mathematicians who don't know they're making a very unnecessary and controversial choice or that there's another world out there with beautiful properties and which stays more down to earth."

Well, those mathematics may not be useful for you. You don't need them, so you call them unnecessary. "Who cares?".

Some crazy people cares. The problem here is that there is people from other planets. With other interests.

Good example: You can use imaginary numbers in your programs precisely because people have studied them. If they were driven by "tangibility", no one would ever know. Now it's easy to say "but they're useful!". But how did we learn that? Imaginary numbers were not useful for programming when discovered XD

To me, your saying "I'm only interested in numbers x who verify A(x), so numbers not verifying A(x) should be discarded. If you don't discard them, you don't have the beautiful property that for every x, A(x)". That's not a reason for everybody else to discard them.

• Andrew says:

Let me know when a physicist or a computer scientist or a biologist thanks you for studying non-computable numbers and uncountable sets because it made his life easier.

• John Fringe says:

OK, but be patient. Euler studies about number theory took a whole 250 years to be useful to a programmer so he can include RSA in his programs. It's probably one of the first practical uses of primes, those entities studied by the ancient Greeks. These things take time. So be patient.

Now, I'm writing a genetic algorithm which takes a program and mutates it... I would love to know which is the probability for a mutated program to halt so I can skip its.........

• Andrew says:

I *may* even be persuaded to tolerate the existence of a few weirdos who study non-computable numbers and uncountable sets, but it's deeply disturbing to me that this is the *default state of affairs* in mathematics.

• Andrew says:

> I would love to know which is the probability for a mutated program to halt so I can skip its....

Sure you would. But it's been proven that you will never know.

• John Fringe says:

> "Sure you would. But it's been proven that you will never know."

Yes, by people who studied those numbers you want to discard.

Those weirdos you can tolerate only a few are called mathematicians. By contrast, people who use existent mathematical knowledge are usually called engineers, or physicists, or whatever.

Mathematicians seem to be happy investigating things the rest of people do not find immediately useful.

Also, those people do not seem to care about what you tolerate, sincerely. They simply advance knowledge.

• Andrew says:

> Yes, by people who studied those numbers you want to discard.

Non-computability can be studied without postulating the existence of non-computable things. To say that a property, such whether a program halts, is non-computable is a negative statement which we have no problem proving constructively. To say that Chaitin's constant exists is a positive statement.

They advance the collection of strings that the game called ZFC says "OK" to.

Note that I am in no way attacking all of mathematics or all mathematicians. The vast, vast majority can happily live in a constructive framework. It's stuff like the deep results in classical model theory (e.g. Morley's categoricity theorem) and the uncountability of the reals that I take issue with. Very little work in mathematics is directly affected by the uncountability of the reals.

• william e emba says:

Let me know when a physicist or a computer scientist or a biologist thanks you for studying non-computable numbers and uncountable sets because it made his life easier.

Another very important example is the Robertson-Seymour graph minor theorem, probably the deepest and most important theorem in all of combinatorics.

Graphs have associated with them subgraphs, and then these subgraphs have edge contractions, i. e., smash certain edges into points. A graph minor of a given graph is a graph obtained this way. R-S proved that given any infinite sequence G1, G2, ... of finite graphs, one of them is a graph minor of the other. It doesn't look like much, but it both extremely deep and difficult and leads to significant consequences.

The first interesting bit is that the theorem is highly nonconstructive, and cannot be proved without going well past Peano Arithmetic. The other well-known PA independence results are just barely past PA in strength.

The second interesting bit is that the theorem says there exist algorithms, without giving a clue as to how to find them. Even more humiliating (from the finitistic point of view), the algorithms are usually quadratic-time in complexity!

A simple example is the problem of recognizing planarity of a graph. A famous theorem says that a graph is planar iff it does not contain a K5 or a K33 graph minor (K5=complete graph on 5 points, K33=complete bipartite graph on 3 and 3 points). How about recognizing when a graph can be embedded on a torus? On a projective plane? Etc. The R-S theorem implies that any given surface has associated with it a finite set of excluded minors that characterize graphs that can be embedded in the surface. R-S does not given a clue as to how to find the characterizing set, and in general this is noncomputable!

A minimal set for the projective plane is known, and has over 100 members. No set for the torus is known, but any such set been shown to have over 10000 members. But the algorithm for testing a given graph for embedding in a given surface is fairly simple: check if its graph minors are excluded or not. We normally have no idea what the algorithm actually is.

So, while we can't say R-S have made the lives of computer scientists easier, they have made their lives a lot more interesting.

• Andrew says:

Also, this: "I can't say why it's wrong, but I'm sure it is, so I'm going to throw away the entire theory behind it." assumes a mathematical realist philosophy, which I fervently deny in favor of a formalist philosophy. I am not claiming "the result is objectively wrong so I'm going to throw it out". I am claiming "this underlying theory (ZF) is too far removed from the realm I find worth thinking about".

• Andrew says:

Here's another kicker:

The axiom of choice is actually *provable* in certain constructive type theories, and it's a trivial (let's say "2 line") proof. In a form that I think captures the mathematician's intuition of "Well, if all the sets are non-empty, you should be able to take an element from each". The trick is that in constructive logics, in order to prove non-emptiness, you actually have to exhibit an element (you cannot reason by contradiction)! So you already have one!

• Andrew says:

And it doesn't result in any of the weirdness that it does in ZFC

• lily says:

But none of that even really matters. It's sufficient to say: "Here are the axioms I'm using and here's what follows from them". You can just pick some axioms that work, it's perfectly fine and a good idea for applications.

We should be going the other way and saying "well these things are true in this axiomatic model and these things are true in this other one, and how are these models related", not "this is the right model and this is the wrong one". there's no reason for everyone to use the same axioms, its like Euclid's fifth postulate, even useless geometries cost nothing to think about.

• Andrew says:

> You can just pick some axioms that work, it's perfectly fine and a good idea for applications.

Actually, what you take as your basis matters when you assign computational behaviour to proofs (which is a damn useful thing -- see Coq). Certain choices of axioms make it very difficult if not impossible to assign computational behaviour.

> even useless geometries cost nothing to think about.

They cost the time and energy of bright people who could be thinking about other things.

• lily says:

>Actually, what you take as your basis matters when you assign computational behaviour to proofs (which is a damn useful thing -- see Coq). Certain choices of axioms make it very difficult if not impossible to assign computational behaviour.

That makes sense but it agrees with what I'm saying, you'd everyone to be able to pick the most useful axioms, for their particular application. And it makes sense to be adaptable and impersonal and let people choose their axioms, instead of being rigid.
To disagree with that, is to say that the axioms for metric spaces and the axioms for fields being different is somehow bad, because one or the other has more applications or is more intuitive.

>They cost the time and energy of bright people who could be thinking about other things.

Surely abstraction would be helpful, its always been helpful. Its the same vein of reasoning that united so many things under abstract algebra. Even though most examples of groups are useless, the connections that group theory made apparent (eg. homotopy groups) were invaluable. Since giving all things with something like addition the same name was so useful, doing the same thing with axiomatic systems seems very natural and reasonable. (In the sense of looking for similarities in the structures of seemingly unrelated axiomatic systems).

• lily says:

Sorry about the repetitious phrasing, it's the sleep deprivation talking.

• Andrew says:

> you'd [like] everyone to be able to pick the most useful axioms, for their particular application

I agree, and I encourage this. But I think most don't do this. They take ZFC as god given and don't consider that there might be better alternatives. Then they espouse accidental features like "the reals are uncountable" as if that's an essential feature of mathematics.

Forget excluded middle for now. In set theory you can write down a predicate which holds of a group G, but does not hold of an isomorphic group H. A simple example is $emptyset in G$. This holds when G uses the empty set to represent its identity, but if we swap it out with a different representation, it no longer holds. How strange is that? In contrast, in type theory, you cannot even write down such things. Vladimir Voevodsky is using this to argue for a type theoretic foundation for mathematics, where reasoning up to isomorphism is perfectly safe.

As for excluded middle, I think constructive mathematics serves as a damn good heuristic to distinguish "math worth doing" from "math not worth doing". If your results are constructive, as almost everyone's are, there's a decent chance that your work can be applied to make someone's life easier in the future. If your results are highly non-constructive, like "the reals are uncountable" or Morley's categoricity theorem, then it's guaranteed that the only people who will ever care are the other mathematicians who are just as perverse as you are.

• John Fringe says:

What is the warranty? Who guarantees it? Can we see it?

• Andrew says:

Also, I object to your claim that these cranks need to explain why Cantor's proof is wrong. In fact, Cantor's proof could conceivably be valid, *and* there could be a bijection between N and R. What would this mean? It would mean that ZFC is inconsistent. All experimental evidence is to the contrary, but oh well. I prefer the phrasing "No one has yet demonstrated that ZFC is inconsistent" anyways.

• Eric says:

I guess the thing about that view that fails to convince me is that no amount of cleverness in the (supposed) bijection will be sufficient to evade Cantor's trap, because the argument does not depend in any way on the details of the map, beyond the fact that it goes from N to R. Therefore modifying the details of the map cannot alter the result of applying Cantor's diagonalization to it.

Now I don't actually know anything about different axiomatic systems or the relationship between their consistency and the existence of large cardinals (other than that such a relationship exists), so this is certainly a naive view. If I'm making a typical newbie mistake I'd be grateful to hear about it.

• Andrew says:

This is the nature of inconsistency. An extremely clever bijection which exploits an inconsistency in ZFC would *not* evade Cantor's trap. Cantor's trap would show that there exists a real number not in the image of the map. The clever existence of the bijection shows that there is no such real number. *Both* are there. There both is and is not a real number outside the image of the map. Every statement is provable. That is the nature of inconsistency.

• Andrew says:

Sorry, "*Both* are there" should say "*Both* are true".

• Matthew Cline says:

I really don't understand why people like this don't just reject the concept of real numbers.

• Eric says:

Because that way they don't get the glory of having single-handedly overturned centuries of slavishly defended establishment dogma.

• Vicki says:

That was tried more than two thousand years ago, but it means throwing away too much geometry: if they reject the real numbers, they reject the existence of isoceles right triangles. (I don't think the irrationality of π had been demonstrated in Pythagoras' time, but it has now, so they'd also lose the area of circles, volume of spheres and cylinders…)

• Andrew says:

Not true. Reject the real numbers, keep the computable real numbers. Keep your algebraic numbers, keep pi and e, throw out Chaitin's constant.

• william e emba says:

Andrew: It has in fact been explained to Mark previously that cranks are not required in any way shape or form to "address Cantor's proof". They are obligated to show there exists a bijection between N and R, which they fail to do and which they fail to notice that they have not done. It is always nice when giving a counterexample to an already published (alleged) theorem to identify the mistake in existing proofs, but it is completely unnecessary.

In the course of responding in that earlier thread, I identified two examples of limited set theories where Cantor's theorem fails: fine structure of the constructible universe, and certain non-Boolean topoi. I gave an explicit reference for the latter (comment 101), pointing out that the author in the reference did exactly what Mark says is the cranks' Big Mistake: giving a counterexample to Cantor's theorem without addressing Cantor's proof. In short, Mark is provably incorrect.

For Mark to continue to give this erroneous assertion is pure crackpottery on his own part.

This is rubbish.

The point behind "addressing Cantor's proof" is that if someone is claiming to have disproven Cantor, they need to actually disprove Cantor's proof. By addressing some unrelated problem (and doing so incorrectly), you're not disproving Cantor. It's just blind handwaving.

Anyone could claim, for instance, "Hey, look, if I take the lengths of this right triangle, [3, 4, 5], and write them in binary, [11, 100, and 101], notice that 11^2 + 100^2 = 10121 which is not equal to 101^2 = 10201! Pythagoras disproved!"

You'd obviously look at that and think it was the stupidest argument ever. It doesn't disprove the Pythagorean Theorem because it doesn't actually address the theorem in a valid way. It's using invalid logic and addressing something completely silly and unrelated to the original concept.

Similarly, here, the author Mark refers to isn't addressing Cantor's proof. Cantor's proof is a sort of logical framework that says we can construct a list of real numbers S and, from those numbers, create a number s0 that isn't found in S -- by logical necessity. The author is addressing something that is an invalid refutation of Cantor's proof -- it's just silliness that suggests he doesn't really understand how Cantor's proof works.

• Andy M says:

Well, no, what emba is saying is nowhere near that bad since what you wrote just boils down to "getting arithmetic wrong". I believe he's saying that since Cantor's proof states "there does not exist a bijection between N and R" then if you can write down such a bijection (you can't) then you'll have refuted his proof. Personally I think it's largely a pedantic semantic argument and it's perfectly correct the way Mark discusses it: the interesting bit would come next when you figured out *why* Cantor's construction wouldn't work for your bijection.

Apologies, but I believe you misunderstood my point. I agree that writing down a bijection between N and R would be a refutation of Cantor's proof, but the point is that you can't do it. I agree that Mark's refutation is just fine as-is.

Emba said that cranks are not required to "address Cantor's proof" but they must simply show there there "exists a bijection between N and R." My point is that this is nonsense to phrase it this way. If you can show such a bijection, it also needs to make sense with respect to Cantor's proof... otherwise you're not addressing Cantor's proof at all, and this entire thing becomes meaningless.

That's what the author in the original post did. He made some odd binary analogy and claimed it refuted Cantor. This is hogwash because *he isn't refuting Cantor's proof*.

• william e emba says:

Emba said that cranks are not required to "address Cantor's proof" but they must simply show there there "exists a bijection between N and R." My point is that this is nonsense to phrase it this way.

No, it's not nonsense. Cantor proved there is no such bijection. You refute (strongly) Cantor by showing there is such a bijection, you refute (weakly) Cantor by showing Cantor made a mistake in his argument.

If you can show such a bijection, it also needs to make sense with respect to Cantor's proof... otherwise you're not addressing Cantor's proof at all, and this entire thing becomes meaningless.

SO WHAT if you're not addressing Cantor's proof? If you show there is such a bijection, then Cantor goofed and his proof is clever gibberish.

That's what the author in the original post did. He made some odd binary analogy and claimed it refuted Cantor. This is hogwash because *he isn't refuting Cantor's proof*.

No, it's hogwash for the reason Mark stated: it is obviously not a bijection. End of counterexample. The crackpot then went on and did exactly what Mark claims crackpots are supposed to do: he attempted to explain where Cantor allegedly went wrong. Like his bijection, the explanation was an utter failure.

The only thing that matters, mathematically, is whether there is a bijection N->R. The crackpot gave a bijection between N and a proper subset of R, the unit interval dyadics. Had he given an actual bijection, and then went on and tried to be helpful and explain where Cantor made a mistake but unfortunately the crackpot made no sense here, we'd all be very very interested in his bijection just the same. "Addressing Cantor's proof" is a social nicety. It would, were it possible, be an enhancement to the mathematics of the imagined bijection.

• Mark C. Chu-Carroll says:

You can explain things all you want, but that doesn't mean I have to agree with your explanation.

When it comes to Cantor, my point is that Cantor did something very deep. He showed that given any supposed enumeration of the real numbers, you can generate a real number which isn't in the enumeration.

If you claim that you can defeat Cantor's proof by showing an enumeration, I maintain that you absolutely must show why Cantor's procedure won't generate a counterexample. If you can't do that, then Cantor's proof shows that your enumeration is incomplete - i.e., that you're wrong.

So you either need to show that there's something wrong with Cantor's proof in the abstract; or you need to show in your specific case why Cantor's proof doesn't generate a counterexample to your claim. If you don't do that, then your claim to have defeated Cantor is bullshit.

• Robert says:

In general it is indeed sufficient to have a counterexample to disprove a theorem, often a counterexample will already show how a proof went wrong, if you dont show so explicitly. However, if you claim to have created a bijection between the naturals and the reals, you need to show that every real number, including the one created by the Cantor diagonal, is in your list. As such, a correct counterexample to Cantor must include an argument why the diagonal is in the enumeration.

• william e emba says:

The "correct" counterexample's argument that an alleged N->R is a bijection only has to refer to the diagonal implicitly, merely by showing all reals are enumerated. There is absolutely no mathematical need to single out Cantor diagonals for special treatment in such a proof. Claiming such a need exists is crackpot nonsense.

You are confused because Cantor's proof is so simple, and the crackpots are so simple-minded.

• Andrew says:

Imagine we are in the days before Cantor was even born. Someone comes to you and exhibits a bijection between N and R.

Do they have a proof? Answer: Yes.

Did they have to refute Cantor's argument in their proof? Answer: Who is Cantor?

You are suggesting that the notion of what constitutes a proof changes as we learn more theorems. Bullocks.

• Carl Witty says:

In practice, "proof" refers to a piece of text (in a mixture of a human language and mathematical notation) that is sufficient to convince other mathematicians that a theorem is true. In this sense, "what constitutes a proof" certainly does change over time; and it's not surprising that it does, given the subjective nature of the concept.

• william e emba says:

You can explain things all you want, but that doesn't mean I have to agree with your explanation.

Of course not. You can choose to be your own brand of crackpot all you want.

When it comes to Cantor, my point is that Cantor did something very deep. He showed that given any supposed enumeration of the real numbers, you can generate a real number which isn't in the enumeration.

Yes. He did do that.

If you claim that you can defeat Cantor's proof by showing an enumeration, I maintain that you absolutely must show why Cantor's procedure won't generate a counterexample.

You can maintain that all you want. It's complete crackpot nonsense.

It would be nice for the proposer of an alleged N->R bijection to do that, but if he doesn't, SO WHAT? You can huff and puff about how helpful it is, you can rant and rave about how it leads to self-awareness, but that still does not add up to an obligation.

Were the alleged bijection to be a genuine bijection, it would mean that there was a surprising and obviously very subtle error that has been overlooked all these decades, and hordes of mathematicians would jump in to identify what exactly went wrong. Why, exactly, is the burden on the proposer to beat the rush?

For example, not once have you ever asserted that the crackpot is supposed to explain where Cantor's First Proof, involving descending closed intervals, goes wrong. Why not?

If you can't do that, then Cantor's proof shows that your enumeration is incomplete - i.e., that you're wrong.

Cantor's proof, since it really is correct, shows anyway that the crackpot is mistaken. This is the typical professional mathematician's complete response to a Cantor crackpot. Very, very, very rarely do any of them do what you propose is supposedly obligatory: examine the claim deemed erroneous to the point of identifying the actual error. They simply rely on the claim deemed correct and move on.

And as I've explicitly referenced, restricted set theories and logics where Cantor is mistaken do exist, wherein there exist bijections N->R. And where the mathematician in question gave the bijection but did not bother to explain where Cantor fails to work. The reader of Johnstone's book who thinks that is an interesting question has to (a) ask the question himself, and (b) figure out the answer himself.

Try reading corrections/retractions in the professional journals. Sometimes the exact bit of faulty reasoning is identified. Sometimes no faulty reasoning is identified, but a key lemma is shown to contradict something else, so at the least the faulty reasoning is localized. But sometimes nothing other than the final result itself is shown to be in contradiction with other results, and no hint where the mistake occurs is given. An extreme version of this last is where the "other results" are not even identified! The author merely thanks so-and-so for sharing his unpublished work, with no clue to what that work states and how it refutes the original publication.

Obviously, the first style is the most helpful, and the last version is the least helpful. You are claiming, contrary to fact, that the first style is obligatory, and someone who engages in the 2nd, 3rd, or 4th has not really corrected/retracted his work.

Complete piffle.

Where a Cantor crackpot goes wrong is quite simple: they have failed to give a bijection N->R. (Or at least show, non-constructively, that such a bijection exists.) Such a construction--if the crackpot gets that far--is usually so trivial that in fact we can all identify missing values almost instantly. Game over. Of course, as I stated above, most mathematicians consider it "game over before it was even begun".

• Benson says:

Good work. In my experience you are totally right that many people are confused on this issue. Opponents of "cantor crackpots" should first and foremost show that the alleged map from N onto R is not actually onto. They should not just point at Cantor's theorem. (Going too far to call these folks "crackpots" themselves though, and as overzealous defenders of orthodoxy perhaps there is an even better term for them?)

In addition, the thing is that Cantor's theorem is so simple and so obvious is it really hard to keep in mind this fact. Are you aware of any examples where a very simple and long established "theorem" has had a genuine counterexample to it shown?

Lakatos's example with the Euler Characteristic don't count because the problem there was the definition of the terms and not the theorem itself.

• william e emba says:

In addition, the thing is that Cantor's theorem is so simple and so obvious is it really hard to keep in mind this fact. Are you aware of any examples where a very simple and long established "theorem" has had a genuine counterexample to it shown?

The most extreme is Vann McGee "A Counterexample to Modus Ponens" J Phil, 82(9), pp462-471 (1985). Some may question how "genuine" the counterexample is--nevertheless, the paper is still mind-twisting. You can't help but flipflop between being deeply wowed to feeling horribly swindled.

• william e emba says:

Perhaps the classic example is the following, quoting from Wikipedia:

Augustin Louis Cauchy in 1821 published a faulty proof of the false statement that the pointwise limit of a sequence of continuous functions is always continuous. Joseph Fourier and Niels Henrik Abel found counter examples in the context of Fourier series. Dirichlet then analyzed Cauchy's proof and found the mistake: the notion of pointwise convergence had to be replaced by uniform convergence.

Note that, contra Mark, neither Fourier nor Abel identified Cauchy's mistake.

• Benson says:

I don't think McGee's case is a counterexample to any theorem, it is a deeper and more philosophical argument and the nature of the logical connectives. And Cauchy's "proof" is not the best example either since the standard of rigor was comparatively very low in his day. In fact the various notions of continuity had not even been established. I am going to look up his "proof" since I find it hard to imagine what it could have been (the statement proved being so obviously false).

• David Starner says:

If there is a proffered proof of A and a proffered proof of ~A, then in theory one of the proofs should be demonstrated to be incorrect before the other can be accepted as true. In practice, one might be able to offer a counter-excepted to Fermat's Last Theorem that would get accepted before anyone could find the error in Wiley's voluminous complex proof. On the other hand, if you can not demonstrate the error in something as simple as Cantor's proof, the most generous thing the mathematical community could do is admit that the status of both proofs is unclear.

• Forget about pi and square root of 2 as not being on the list: his list doesn't even have 1/3 .

• Thinkeye says:

I don't understand people who do not understand Cantor.
For any two finite natural numbers A<B, I can tell exactly how many natural numbers are between them - this number is always finite. For any two (finite) real numbers a<b, there are infinitely many real numbers between them.
So for any potential mapping, put A=a and B=b, and your natural trousers are too short for your real legs.

• Snarkyxanf says:

But that "infinitely many in between" property also holds for the rationals, and the rationals are countable.

• david says:

OK. Here's my disproof: There seems to be an infinity of crackpots who claim to have disproven Cantor's theorem. The Cantor crackpots are a subset of the integers, and therefore are countable. However, none of them are rational. Also, they keep up correspondence with math bloggers (really stretching the puns, here, ....). Therefore there is a correspondence between irrationals and the countable set of Cantor crackpots.

• lily says:

boooooooo
=p

• Snarkyxanf says:

It's nice of these people to keep providing proofs that various sets of numbers can approximate reals to arbitrary precision. Too bad that they think they proved something else completely different, and can't write worth a damn.

• william e emba says:

Andrew wrote:

Let me know when a physicist or a computer scientist or a biologist thanks you for studying non-computable numbers and uncountable sets because it made his life easier.

Nonconstructive mathematics and uncountable sets and even forcing have been used by physicists. One such application provides a clever way to bypass the Bell inequality, which severely limits the kinds of "hidden variable" interpretations of quantum mechanics are possible. Another provides a radical rewriting of many-worlds. Forcing has been used to make progress on the AdS/CFT correspondence. Noncommutative geometry is highly nonconstructive.

Theoretical computer science and theoretical biology include the study of chaotic systems, and the question of how effective these actually are is of great interest. As an historical note, the widespread use of Kripke semantics inspired models of computation ultimately owes a big-thank you to Paul Cohen. His original forcing followed intuitionistic logic (he thus proved the independence of "not not CH"). Scott showed how to put the double-negation business inside the definition of forcing, so that it would follow classical logic. But Kripke realized the original Cohen notion could be adapted to directly model intuitionistic logic.

• Andrew says:

Nonconstructive mathematics and uncountable sets and even forcing have been used by physicists.

Interesting. Do you have references I can look at?

• william e emba says:

You can find the following papers free on-line if you search around enough. These aren't the only papers/books with modern physics and modern metamathematics mixed together--these were just the ones I could remember off the top of my head.

Geroch and Hartle propose that, because 4-manifolds are, for most purposes, non-computable, quantum gravity may ultimately be non-computable (and hence, a Turing oracle). Pitowsky uses non-measurable sets and more. Król and van Wesep use forcing. Note that Król also uses topos theory and higher category theory! Van Wesep's work was published as three papers, consecutive in the journal they appeared in.

Robert Geroch and James B. Hartle, "Computability and physical theories",Found. Phys., 16 (6), 533-550.

Itamar Pitowsky "Deterministic Model of Spin and Statistics", Phys. Rev. D27, 2316-2326 (1983).

Jerzy Król "Background independence in quantum gravity and forcing constructions" Found. Phys., 34, (2004), 361–403. (see also his 2003 and 2004 papers on the arXiv relating model theory and forcing to the AdS/CFT correspondence).

Robert van Wesep, "Hidden variables in quantum mechanics: Generic models, set-theoretic forcing, and the appearance of probability I, II, III", Ann. Phys., 321 (10) (2006) 2438--2452, 2453--2475, 2476--2490.

Gudder's book is not available on-line, but Amazon lets you peek at the table of contents and the index. You'll see transfinite induction mentioned in the table of contents, and the axiom of choice and the continuum hypothesis in the index. (And looking at the prices, I'm glad I bought my copy when it was new.)

Stanley Gudder Quantum Probability, 1988.

• Andrew says:

Thanks!

• william e emba says:

Having looked at my Gudder again, I have the impression that he is giving a textbook presentation of an improvement of Pitowsky's work. The Geroch and Hartle paper was published in 1986.

• John Fringe says:

So, things can be useful despite not being useful for oneself inmediately without much thinking? O_o

We should spend less time looking at our own navel, then XD

In any case, I think this is the incorrect way to address this issue. If someone claim "it's guaranteed that non constructive proofs are useless", I expect some justification. It's surprising how much people accept that assertions are true until someone can immediately prove they're false.

Will we ever learn the lesson?

• Andrew says:

My justification is perhaps appears a bit circular, but essentially, if these non-computable phenomenon show up in physics, then in fact they are a resource we can exploit in computation, and hence they expand our definition of computable, and hence are constructive for an expanded, but still satisfactory, notion of constructive.

Perhaps down in the bowels of physics lies an oracle for the halting problem for the traditional notion of computability. Fine, but then the halting problem for "machines with an oracle for the original halting problem" is undecidable by those machines. Continue ad nauseam.

So never will all propositions become decidable (see http://en.wikipedia.org/wiki/Turing_degree#Basic_properties_of_the_Turing_degrees -- there is no maximal Turing degree). But classical logic asserts "P or not P", which can never be given a constructive interpretation for that reason.

So sure, it's conceivable that the Church-Turing thesis is wrong, and that there are stronger notions of computability built into physics. But they're never going to include excluded middle.

• Andrew says:

So yes, essentially I am arguing that "physical" and "computational" mean the more or less the same thing, and so my assertion that "constructiveness is the only useful notion for physics" is basically just tautological.

• John Fringe says:

I believe I understand what you're thinking, but I still believe it's wrong. Concepts not realizable physically can be very very useful.

Take infinite as an example. There is probably no physical realization of infinite, I don't know. Assume there isn't, as a possibility.

Would you say infinite is not a useful concept?

It may be a bad example (I didn't though about it too much), but I feel it reflects your argument. If there is no physical realization of something noncomputable (we don't actually know), then the concept is useless. I think this is false.

• Andrew says:

There is a physical realization of the infinite in the sense that we can describe and execute procedures which enumerate an infinitude of things. We can't hold all of them, but we can have "as many as we want".

• Andrew says:

And I often find that "as many as you want" is often enough.

• Andrew says:

Anyways, at a minimum, I would be happier if mathematicians stopped espousing the uncountability of the reals as if it's an essential feature of mathematics, and treated it more like the optional (or as I see it, "accidental") feature of a choice to use ZFC it is.

I would be even happier if they recognized that constructive logic is actually *more* expressive, not more restrictive, than classical logic. Because classical logic can be embedded in constructive logic via a double negation translation and various other techniques.

• John Fringe says:

No, I can "guarantee" you can not execute as many iterations as you can of a procedure in the physical real universe. Maybe you're speaking about _theory_, not realizable.

About describing a procedure which could theoretically be executed so much times, well, Chaitin's omega can also be described, and you don't like it. Invalid argument, I must say.

So, if you believe nature is finally deterministic, you believe that, as there would not be true physical realizations of randomness, we shouldn't study random models. (Despite they being very useful even in deterministic models).

On the contrary, if you believe nature to be random in essence (like in quantum mechanics), you believe, as there would not be true physical realizations of determinism, we shouldn't study deterministic models. (Despite they being incredibly useful).

• John Fringe says:

I meant you can not execute as many iterations as you want of a procedure in the physical universe, of course. I typed too fast.

There may be a lot of limitations. I don't believe I need to list them. You can think of them, too.

• John Fringe says:

Now, about your last comment, and seeing you like constructive proofs, how would you enumerate your reals?

I don't see how you can give an useful enumeration of reals. Maybe that's the reason why it's so easy to assume they are not enumerable. (Remember, for me, pi and e and e^pi are very important. I would love to know their indexes). But I'm open to new ideas.

I could work on my computer with your codification, if it's useful.

• william e emba says:

Keep in mind that integer-based computation and real-based computation are different things. Integer-based computation just means Turing machines and the like. Processes and values are discrete. Real-based computation refers to Blum-Shub-Smale models. Computations are really dynamical systems.

In general, real-based computation is algorithmically more difficult than integer-based computation. One can also do simple tricks like put noncomputable numbers as weights to a neural net. In classical mechanics, these are all physical!

Note that most versions of string theory put a bound on arbitrary precision. I'm not sure if it's clear what quantum mechanics does in this context.

Even more remarkable: rotating Kerr black holes or more generally, Malament-Hogarth spacetimes allow for hypercomputation, that is, infinitely many steps done in a finite time. (I think Pitowsky first suggested this line of research, by the way.)

So not only is it getting harder and harder to believe "physical" means "Turing computable", something you conceded above, there's more. With hypertasks, classic Brouwer style failures of the law of excluded middle, "π as a decimal has 1000000 0s in a row or π as a decimal does not have 1000000 0s in a row" become physically constructive.

• John Fringe says:

> "I would be even happier if they recognized that constructive logic is actually *more* expressive, not more restrictive, than classical logic. Because classical logic can be embedded in constructive logic via a double negation translation and various other techniques."

I thought any "constructive logic" construction is valid "classically", so I don't understand how it can be more expressive.

Can you express something with "constructive logic" that you can't express in "classical logic", so I can understand your assertion, please?

• william e emba says:

Classical logic embeds into intuitionistic logic by using double-negation. That is, if P has a classical proof, then not-not-P has an intuitionistic proof. This is easy: the classical proof of P becomes, in essence, an explicit witness to our inability to prove not-P.

So what this means is that having an intuitionistic proof of P is more information about P.

• John Fringe says:

Excuse my ignorance, Emba, but I still don't get it. But it's very interesting.

Well, of course I understand that a proof of P in constructive logic has additional information about P that a classical proof of P. This is trivial: as constructive logic only accepts a subset of the valid classical proofs, a constructive proof of P carries this additional information: P can be proved with that subset of valid proofs.

But that additional information can be expressed in classical logic, too. Isn't it?

If I have a constructive proof of P, I can prove classically that I can prove P with only those restricted methods valid in intuitionistic logic.

So, I still don't understand why constructive logic is more expressible. Can I express something I can not express classically?

• Andrew says:

> If I have a constructive proof of P, I can prove classically that I can prove P with only those restricted methods valid in intuitionistic logic

True, but this embedding is quite cumbersome. I mean "more expressive" in the sense that statements about constructibility can be expressed more directly. Yes, it's an aesthetic thing, but one that makes a difference in practice.

> how would you enumerate your reals?

I outlined this in my first post, but the idea is: take your favourite enumeration of all finite ASCII strings. If the string constitutes a valid Fortran program, which just so happens to print out a Cauchy sequence of rationals, then it denotes that real number. If not, meh. It's only a *partial* surjective map from N -> R.

Finding the index of pi is easy: Write down your favorite Fortran program which prints out a Cauchy sequence for pi. Apply the bijection between N and ASCII strings in reverse.

• Andrew says:

Of course that's a terrible bijection from a theoretical point of view (it's impossible to work with), but there are much nicer ones inspired by proof theory and lambda calculus, say.

• John Fringe says:

I'm not sure that's a valid enumeration.

You say: take a string (which you can enumerate), and see if it is a program which generates a number. The problem I'm thinking is: how can you know if the program generates a string? Can you? Because you can't even automatically know if it will halt.

And, if you can't know if it generates a real, is it a valid enumeration? I'm not sure. Tomorrow I'll think about it (it's a bit late here, hehe)

• Andrew says:

Yes, we should hesitate to call it an enumeration. We can call it a partial surjection though.

• william e emba says:

Regarding the greater expressibility of intuitionistic logic versus classical logic: yes, you can interpret back-and-forth. The "expressibility" referred to here is more human. Technically speaking one never needs to refer to intuitionistic logic in the same sense that one never needs to refer to hyperbolic geometry: both can be embedded inside the classical version. But when the natural sense of a problem is distorted by using such embeddings, something will be lost--to the human, not to the mathematics.

• John Fringe says:

Andrew> "I outlined this in my first post, but the idea is: take your favourite enumeration of all finite ASCII strings. If the string constitutes a valid Fortran program, which just so happens to print out a Cauchy sequence of rationals, then it denotes that real number. If not, meh. It's only a *partial* surjective map from N -> R."

But your giving me a noncomputable surjection to defend that we should only consider computable functions!!! Aren't you?

You can enumerate programs. But, given a program, you can not decide if it will halt, and you can not decide what number it will generate, if any.

You say "if the program prints a Cauchy sequence of rationals, then it denotes a real number". But it is not decidible if it generates a Cauchy sequence. For example, a program that generates a Cauchy sequence for PI will never stop, and you can not decide running it if it generates a Cauchy sequence or if it will hang itself during its execution. Rice's theorem guarantees you that you can not computably decide what real will it generate. So, if I'm right, given a program you can not decide if it generates a real.

Do you accept a noncomputable partial surjection as an enumeration of computable reals?

• Andrew says:

> So, if I'm right, given a program you can not decide if it generates a real.

Yes, this is correct.

But this partial surjection is computable (we don't normally talk about the computability of partial maps, but here I am using "computable" to mean simply that if it has a value, you can compute it)

• Andrew says:

Hmm maybe I should be more careful about how I state that. Doesn't seem quite right. But I think you see what I mean. Yes, the map lacks some nice properties, but it is still effective in a sense, and certainly can be considered a witness of the fact that there are "at most as many computable reals as there are naturals".

• John Fringe says:

> "and certainly can be considered a witness of the fact that there are "at most as many computable reals as there are naturals"."

Yes, you're right, that's obvious. I just could not think of a good enumeration.

I still doubt about the uselessness of the non-computable reals. But maybe now you aren't neither, after Emba's references. (I'll like to take a look at those references, too, just to learn a couple of things).

In any case, I believe we can agree in the basics: You have the freedom to choose your axioms and see if they're useful to your field of study, but this is applied math. I add that almost any set of axioms will lead you to an interest system :p There is not a privileged set of axioms in mathematics.

So you're in your right to use your computable reals, and other people is in their right to study (and use) the traditional reals. Which was my first comment.

In any case, we already deviated a lot from the topic of this thread ^^;

• Andrew says:

Sure. I just think that it's about time that mainstream mathematics seriously considers constructive logic. I would argue that the current state of affairs effectively treats classical logic and set theory as a "privileged set of axioms".

Computability aside, intuitionistic logic is also the "natural logic of topology". See, e.g.

Martın Escardó. Topology via higher-order intuitionistic logic

And all the work on topos theory and homotopy type theory.

• william e emba says:

Let me point out that many standard set-theoretic assumptions are ultimately finite statements. The consistency of "ZFC+there exists a measurable cardinal" is, in the end, just a combinatorial assertion that certain kinds of finite strings from a finite alphabet (known as "proofs") never end in "0=1". By the Matiyasevich theorem, this can be realized as the assertion that a certain mildly complicated Diaphontine equation has no solutions.

In principle, this could have a direct impact on computation and computational complexity. It's entirely conceivable to have an algorithm that involves one nasty subcase. The subcase could very well be coding a large cardinal, in such a way that the set-theoretic assumption that such a large cardinal is consistent allows one to bypass the subcase. This could give a proof that a certain function's computability depends on the large cardinal. Or it could give a function that can be computed rapidly, if you know you can ignore the subcase, but otherwise, you're doomed to extremely slow behavior.

• lily says:

>Anyways, at a minimum, I would be happier if mathematicians stopped espousing the uncountability of the reals as if it's an essential feature of mathematics, and treated it more like the optional (or as I see it, "accidental") feature of a choice to use ZFC it is.

But it is an essential feature of mathematics, because it's a consequence of the way they are constructed so whenever you talk about them, that will be a fact, and if it isn't (for example: if you tried to construct them outside of ZFC or w/o classical logic) then what you constructed isn't the reals. It's some other number system.

• Andrew says:

Fine, true. But for most purposes, mathematicians take a high level abstract view of the real numbers, and often don't use features that come from the classic definition.

I think it's safe to say they use "real numbers" informally to mean "any concept which satisfies the properties I need in this context" and not necessarily "the real numbers as they are constructed in ZFC". I'm arguing that the computable real numbers are often sufficient, and in some ways better.

• william e emba says:

I am responding to a posting by Shadonis that mistakenly appeared in the following "Facts vs Beliefs" thread. I've blockquoted all of Shadonis' post, whether I'm commenting on it or not.

Cantor indeed showed that such a bijection doesn't exist. But you don't refute Cantor by using some cranky method with questionable assumptions and then asserting that you don't need to explain your result in terms of Cantor's process. All you're doing here is trying to bypass the burden of proof.

"SO WHAT if you're not addressing Cantor's proof? If you show there is such a bijection, then Cantor goofed and his proof is clever gibberish."

You're assuming that by "showing that there is such a bijection," you've actually showed it. If your method is valid, you should be able to show beyond a shadow of a doubt why Cantor's process fails and that he indeed goofed. But if you can't do it, then your method is probably wrong.

Well, yes, I assume that if someone shows there is such a bijection, someone has actually shown there is such a bijection. And yes, you should be able to go beyond writing down your alleged bijection and extract from it a mistake in Cantor's argument. And yes, if you can't figure out where the mistake in Cantor's proof is, it's probably because you're too stupid to realize where the mistake is in your proof in the first place. Such is the life and mind of a crackpot.

But note that many crackpots do go on and identify what they claim to be errors in Cantor. Unlike their alleged bijections, which sometimes are readable to the point that we can all figure out how the map N->R fails to be surjective, their claims about Cantor's errors never make any sense.

But whether they take that next step or not is irrelevant. The failure of their N->R to be surjective is definitive in itself.

It's why I brought up the Pythagoras example. Any idiot can say they've disproved the Theorem by converting the sides to binary first and then treating those numbers as decimal. But at some point you have to actually show WHY it's a sensible idea, how its results are consistent with everything else out there, how the current version of the theory can't account for your results, and so on. Similarly, if you're going to disprove Cantor, you need to show how Cantor's proof fails and why.

No, you do not. All this would be nice, but if you've got your valid counterexample to Pythagoras or Cantor or the like, you've struck gold right there. Given such a valid counterexample, it's a fine mathematical research effort to extend your result to explaining what went wrong, what to do next, and all that. Maybe you'll do that, maybe somebody else will. Maybe nobody will care at that point and the old proof will simply be forgotten. All these possibilities have in fact occurred in the history of mathematics.

The most striking example was Weierstrass' construction of a continuous nowhere differentiable function. There were claims around that alleged all continuous functions were somewhere differentiable, but mathematicians of the day were just coming to grips with these questions, and doing a bad job of it. Weierstrass gave them a kick in the head that could not be ignored, in addition to developing his own delta-epsilon level of rigor. He did not bother to explain where the previous "proofs" went wrong, and I'm not sure if anyone else did either. They all just sobered up fast.

You don't get to just handwave it away.

It's not being handwaved away. It's being ignored.

Besides, nobody is going to be able to do it because Cantor's proof is logically watertight, and it makes sense to everyone except those who continue to misunderstand how infinity works. There is no bijection between the naturals and the reals. Anyone with a fully-functioning brain can intuit this, and yet some people apparently lack the functionality.

That's a different issue. The extreme simplicity of Cantor's proof makes it easy for us to identify who the crackpot is. It also makes it easy for you and Mark to confuse the fact that it is so trivial to apply Cantor's proof--it seems to be as simple as putting a period on at the end of a sentence--that you both go on expecting this to be done.

Anyway, because of the difficulty of talking about counterfactual mathematics, I've referenced specifically the following. Let me requote it:
======================================================
Look up Peter Johnstone Sketches of an Elephant, volume 2. (Unfortunately, only volume 1 is available online for free.) Theorem D4.1.8 is a proof that in a Boolean topos, Cantor's theorem holds. Example D4.1.9 is a non-Boolean topos in which Cantor's theorem fails. Johnstone does not address the question of why diagonalization actually fails here. It is left as an implicit exercise for the interested reader.
======================================================
Something simpler can be done with spherical geometry. On a sphere, form a triple right triangle, consisting of three 90 degree arcs, say two half-meridians from the North Pole to the Equator, with 90 degrees between the half-meridians, and the portion of the Equator between the half-meridians. Tada, πR/2 by πR/2 by πR/2, yet (πR/2)^2+(πR/2)^2=(πR/2)^2 fails. Have I explained where Pythagoras went wrong? No. Is there something wrong with my example? No. The mathematician does have to come to grips with what's going on here, but if he doesn't, the example is still valid.

emba:

We'll just have to agree to disagree. If someone claims to find a bijection between N and R (which they obviously can't), they should be able to relate it back to Cantor's process. There's no reason NOT to do so is if Cantor's process shows that your supposed "proof" of a bijection is complete bunk. What you call "ignoring" I call "handwaving" -- they're the same thing in this case. It's a complete dismissal of Cantor's proof for the sake of upholding an assertion. If you've "got your valid counterexample to Pythagoras or Cantor or the like," you should also be able to talk about it in terms of the actual proofs/theories you're falsifying. It's a necessary rigor, especially if you're trying to convince people.

Anyways, your last example doesn't apply here in the same way because the Pythagorean Theorem is derived from the postulates of Euclidean geometry. If you're going to talk about non-Euclidean geometry, then we use different systems that make consistent sense. Similarly, if we're going to talk about bijections between N and R, we need another system to allow for that sort of thing. However, I'm not sure what kind of system that would be, because it sure as hell doesn't make sense in any reality I can think of.

• william e emba says:

We'll just have to agree to disagree. If someone claims to find a bijection between N and R (which they obviously can't), they should be able to relate it back to Cantor's process.

Of course they can't do the former, and of course they should be able to do the latter. More to the point, they should be able to understand Cantor's theorem in the first place and not waste their time with their nonsense. I mean, I comprehend that there are people who can't understand the proofs regarding the impossibility of trisecting angles or squaring circles, but how on earth there are people who are able to read and cross a street without killing themselves yet fail to comprehend Cantor's argument--it defies understanding.

There's no reason NOT to do so is if Cantor's process shows that your supposed "proof" of a bijection is complete bunk.

But if you've presumably written down a bijection N->R, then you conclude Cantor's process will fail. Why bother?

The answer, of course, is all about the social/human side of mathematics. It's good to have a thorough understanding of your subject. It's good to immunize yourself against flawed arguments that fooled everybody. It's good to convince skeptical readers that there will be lots of payoff. And so on.

Someone who successfully coughs up a bijection N->R can rest on his laurels right there. Other people will fill in the social/human side.

What you call "ignoring" I call "handwaving" -- they're the same thing in this case. It's a complete dismissal of Cantor's proof for the sake of upholding an assertion.

No, they are not the same thing in this context (although perhaps you meant it to be). "Handwaving" means bypassing a delicate step in an argument, knowing full well that it's delicate. "Ignoring" means leaving something out, not even acknowledging there's an issue. The dumbest crackpots ignore the question of showing N->R a bijection. The smarter crackpots handwave here. Either way, they've failed to give a bijection N->R, as we all knew they'd not do.

At which point, who cares what they say afterwards? They can say "Mission Accomplished" all they want. They are still an idiot either way.

And yes, some of them do go on to explain why Cantor is "wrong"--the crackpot Mark is responding to in this post, for example--and of course it's all gibberish.

If you've "got your valid counterexample to Pythagoras or Cantor or the like," you should also be able to talk about it in terms of the actual proofs/theories you're falsifying. It's a necessary rigor, especially if you're trying to convince people.

At this point, you're vociferously agreeing with me: it's a social necessity only. More to the point, you should be able to understand and talk about Pythagoras and Cantor, period.

Really, the crackpot's error happens as soon as they completely fail to get something so trivial. It's just too simple a proof! Given that this is their real error, it seems kind of silly to home in on later details. But from a narrow, strictly mathematical point of view, they're not cooked until the first time they write down a falsehood. And that occurs as soon as they claim they have a bijection N->R. (Some of them simply fail by not even stating a claim.)

Anyways, your last example doesn't apply here in the same way because the Pythagorean Theorem is derived from the postulates of Euclidean geometry. If you're going to talk about non-Euclidean geometry, then we use different systems that make consistent sense. Similarly, if we're going to talk about bijections between N and R, we need another system to allow for that sort of thing. However, I'm not sure what kind of system that would be, because it sure as hell doesn't make sense in any reality I can think of.

It makes sense in the non-Boolean topos Johnstone constructed in his book. See the reference I've made repeatedly. I specifically gave this reference because it is very very difficult to talk sense in the counterfactual world of the crackpot. To reiterate: Johnstone defined what amounts to a "fuzzy" set theory in which there exists an explicit bijection from N->R. Johnstone did not, however, go on to even mention the fact that Cantor's proof has to fail in this context, let alone explain how it fails. The interested reader has to ask this question and answer it himself.

I consider this to be an irrefutable counterexample to Mark's claim. If I wanted to be jerk, I'd call Mark a hypocrite at this point--why doesn't he go and "refute" Johnstone, now that he's claiming Johnstone is erroneous? No, Mark is simply in error.

Of course, this example is, unfortunately, too difficult for most readers here. Johnstone's book is a highly advanced treatise on topos theory. Even though this example is mostly elementary, it would take a lot of work to de-Johnstone-ize the description and make it accessible at a beginning category theory level.

So, I switched to the non-Euclidean Pythagoras "counterexample" simply to invite you and everyone else to disagree with me on something we can all handle mathematically. So imagine some Pythagoras crackpot--back in the days before people knew the Earth was round!--who maps out a large non-Pythagorean triangle on the Earth's surface and claims it's a counterexample to the Pythagoras theorem. Do you berate him for not identifying the "flaw" in Euclid's proof?

Yes, this is conceptually different: the triangle is physical, not mathematical. But in this case, the crackpot is actually correct! Failure to deconstruct Euclid on his part is simply not relevant. It is not, as Mark claims, an error on his part. Once the cat is out of the bag, people will verify the correctness of the original claim. And over time, someone will figure out that real-world triangles follow the spherical law (cos c=cos a cos b), and voila!, prove the Earth is round.

So when we're being asked to imagine the crackpot's world where he really really has come up with a counterexample to Cantor, I imagine something like the Johnstone example, and I consider the Pythagoras example to be in the same spirit. And I find the claims that there's some mathematical requirement to identify the original flaw that fooled people all along don't work here. The only issue is the validity of the contested claim.

It's never been good. As someone pointed out early on, the correct response to a valid counterexample, that is, a mathematically correct bijection N->R, will be to rethink our foundations.

• TUNAPOLOCS says:

My god!!!! How can you guys screw up something as obvious as the diagonal argument? It is nothing but the pigeon whole principle writ large, arbitrarily that is...

Mathematics, in case you have forgotten, is about "proving" the correctness of your claims. I guess we need a new discipline with a nice bullshit sounding name like, politika-mathematica.

• william e emba says:

Let me give a summary of my position.

Cantor crackpots are the rank dumbest (mathematical) crackpots in the world. Angle trisectors and circle squarers are too dumb to understand the proof that their quest is impossible, but to their credit, the proofs are certainly nontrivial. Fermat theorem provers using high-school algebra are incompetent at high-school algebra, which is sad but not completely trivial. In contrast, Cantor's proof is so simple minded, only someone so stupid that it's pretty iffy whether they could win a mental wrestling match with an immature blowfish, two falls out of three, can fail to understand it.

So as far as I'm concerned, the real "error" made by a Cantor crackpot is his extreme stupidity. Trying to call something his "error" is the moral equivalent of feeding an Internet troll. He's not playing the same game the rest of us are playing, and splitting hairs as if he were playing the same game is so much foolishness.

But if I'm going to dive into the foolishness, then I'm going to do so as literally-minded as possible: his writings are to be treated as neutral mathematical texts, and I will read until I find an error. Anything else is giving him credit which he absolutely has not earned. And his error is always the same (assuming he gets so far as to present something readable as mathematics): he writes down a map N->R, and fails to prove that it's a bijection, or worse, simply fails to understand that he's expected to provide a bijection.

At that point, we have a bona fide mathematical error. I simply cannot understand bypassing the first (unfixable) error and saying something later is his "real" error, unless you are simply saying his real error is being a Cantormaniacal moron. Either you are reading the crackpot mathematically, meaning that once the error has been made, what follows is irrelevant, taking part in some counterfactual never-never-land, or you are diagnosing the crackpot's stupidity, which is his wretched inability to diagonalize, in the abstract or in a particular case. But that comes before he writes down one word, not after he's written down his miserable little non-bijection and fails to actually diagonalize.

• The argument goes:

Cantor: There is no surjective mapping from N to R. For any claimed mapping, I can construct a diagonalization number in R which is not in the mapping.

Crank: You're wrong. To prove it, here's a mapping from N to R.

Mark: That's not a valid counterexample. You didn't even try to disprove Cantor.

Comments: Lots of arguing about whether it's necessary to formally disprove Cantor in order to provide a counterexample.

My response: A minimum requirement for a counterexample is that it shows that the diagonalization number is contained in the mapping. If this can be demonstrated, it constitutes a disproof of Cantor by example. Any claimed mapping which does not attempt to deal with the diagonalization number does not even challenge Cantor and therefore cannot be a disproof of Cantor.

A counterexample to Cantor doesn't need to disprove Cantor in the sense of revealing a flaw in his argument. But it does need to at least contradict Cantor. That contradiction would be a disproof.

"A minimum requirement for a counterexample is that it shows that the diagonalization number is contained in the mapping. If this can be demonstrated, it constitutes a disproof of Cantor by example. Any claimed mapping which does not attempt to deal with the diagonalization number does not even challenge Cantor and therefore cannot be a disproof of Cantor."

Agreed.

• william e emba says:

A minimum requirement for a counterexample is that it shows that the diagonalization number is contained in the mapping. If this can be demonstrated, it constitutes a disproof of Cantor by example. Any claimed mapping which does not attempt to deal with the diagonalization number does not even challenge Cantor and therefore cannot be a disproof of Cantor.

Agreed.

Note, though, this "agreement" is completely irrelevant to my criticism of Mark.

There is no requirement that the alleged counterexample be constructive, or even if it is, that in the course of allegedly proving that it really is a bijection N->R that the alleged prover explains how the function works for any particular value.

Were someone ever to get that far--proving that there exists a bijection N->R--he would be an instant mathematical celebrity. He could let someone else unravel the blatant contradiction with Cantor, and still be just as famous.

• Matthew Morse says:

Okay, another way:

Crank: I have a surjection from N to R.

Cantor: Okay prove it. By the way, I can prove this number is not in your mapping.

Crank: Wait, what?

If the crank were to attempt a demonstration that the mapping is onto, then the crank could claim that R includes the diagonalization number, regardless of its exact value. But Cantor disproofs don't even try to demonstrate it. They just assume it.

• william e emba says:

Exactly. They have absolutely no idea of what they are supposed to be putting together by way of proof. Some of them get so far as to exhibit an actual map N->R. Of those, none of them seem to even try to prove that the map is onto. From a mathematical point of view, that is their mistake.

The business about "failing to account for Cantor's proof" is extraneous. Mark focuses on that, and is a crackpot himself when he goes further and states that is their mistake. In fact, many of them think they've accounted for Cantor's proof, with crank gibberish explaining why it doesn't apply, in general or to their example, or something just as incompetent.

I've come to the conclusion that Mark makes things much worse by concentrating on the inessential part. Simply hammer them with a request for a proof that their map N->R is onto. Usually the maps are so pathetic that there is no need to invoke Cantor to find missing values. Pretty much any infinite decimal is missing. But why bother to go that far? Just hammer them with a request for a proof that their map N->R is onto. No matter what they say, repeat the request. Failure on their part to prove there exists an onto map N->R is their mistake. Everything else is pretty much irrelevant.

We're dealing with people too stupid to understand something as trivial as Cantor's proof. So what does Mark do? Jump right into Cantor's proof. Unnecessarily. Sheesh.

I don't think you understand what it means for someone to be a crank.

A crank is someone who holds a really screwed up view of things and absolutely refuses to admit when they're wrong, even in the face of evidence, because they typically ignore vital counterpoints, fail to understand the opposing position, and assume a lot of things without justification. No amount of rational argument will cause a crank to change his/her mind because their position is not founded on sensible arguments to begin with.

The entire point here is that you can't just claim to have found a mapping that disproves Cantor unless you're capable of showing that it does indeed disprove Cantor. If you can't show that your mapping disproves Cantor, then you can't claim to have found the mapping! It's really that simple.

Then again, there's no mapping to be found because Cantor's proof is so incredibly obvious to anyone with a brain, which is why people who try to "refute" Cantor come across as equally nutty as the guys who think pi is 4 or that real numbers don't exist. There's nothing "cranky" about calling people out on their nonsense when they claim to refute X without refuting X.

• william e emba says:

It's not clear from the nesting who you are responding to. Personally, I have no idea what on earth gives you the impression that people here don't understand the crank mentality.

The entire point here is that you can't just claim to have found a mapping that disproves Cantor unless you're capable of showing that it does indeed disprove Cantor. If you can't show that your mapping disproves Cantor, then you can't claim to have found the mapping! It's really that simple.

Which is what I've been saying all along. You disprove the Cantor assertion "for all maps f:N->R, f is not a bijection" by proving "there exists a bijection f:N->R". In every case, of course, any putative f is not a bijection, which means they have failed to accomplish their self-proclaimed task.

Mark has repeatedly insisted that this is not "their error". He's claimed that it's failing to go beyond and showing how Cantor allegedly made a mistake, and that the crank fails to show how f makes some clever runaround on Cantor's proof. And this remains complete nonsense on Mark's part.

The source of Mark's error is easy to identify: there is something pathetic about the crank not understanding Cantor's proof in the first place, and Mark has the delusion that the crank could somehow be led to comprehension by walking through the proof every so carefully, with his own f in hand to give the proof a concrete heft. In short, if Mark simply said the crank's error is his gross stupidity in not understanding Cantor in the first place, I'd agree. But he doesn't say that, instead he treats the crank as playing by the rules of mathematical proof, and then Mark jumps over the factual error of the crank not proving his claim to something utterly irrelevant to the rules of mathematical proof.

• Dumbledore says:

Perhaps another source of confusion is the formulation of the theorem. Of course, the wording one should use is something along the lines of "for all maps f : N -> R, f is not a bijection", making william's criticism entirely valid. But I think, since Cantor's proof is so canonical, some people assume a formulation like "for all maps f : N -> R, the Cantor Number C_f is not in the image of f (and hence f is not a bijection)". If the theorem was worded this way (and was preceded by a definition of C_f), a counterexample would have to show that C_f actually *is* in the image of f, and Mark would have a point.

I think it's clear that Cantor cranks are pretty stupid, but ultimately I think that's what we're all arguing, here.

• william e emba says:

One thing I find a bit freaky is that over on math.stackexchange.com, you find math majors (apparently) who do not understand Cantor's diagonal argument (search on "cantor diagonal"). They're not cranks--they know they are missing something--but it still strikes me as unbelievable. The responses are certainly of very high quality, and it seems the ending is always happy.

• Vorlath says:

I have a few "crank" questions if someone is willing to indulge me.

The definition of the powerset is the set of all subsets of X. So consider if I built a set Y that maps one to one with 2^X. And for each element m in Y that is mapped to each element n in 2^X, we define m(i) = 1 if i is in n and m(i) = 0 if i is not in n.

IOW, set Y is 2^X, but with ordered tuples that have values of 0 or 1 indicating if the element is in the set or not.

Example:
So if X = { 0, 1 }, then 2^X = { {}, {0}, {1}, {0,1} }
and Y = { (0,0), (1,0), (0,1), (1,1) }

Those are finite sets, but it's just to visually see what I'm getting at in case my description wasn't clear.

Do we agree that 2^X and Y are equivalent? That they both represent the powerset of X?

We see that there is a one to one mapping between the elements of X and each element of the tuples of Y. While this mapping exists, then X and 2^X cannot be one to one because each element of X doubles the amount of tuples in Y. This is not a one to one ratio.

When you assume that there is a function f that is one to one... and you build S so that x is not in S if x is in f(x), and x is in S if x is not in f(x), asking if x is in f(x) is exactly replicating the way set Y was built if we did this for all i in f(j) for all j, no? If x is in f(x), that's TRUE/1, and if x is not in f(x), that's FALSE/0, so we can easily map 0 to FALSE and 1 to TRUE.

If we instead ask if there is a function f that maps from N to Y, we could build S as an ordered tuple where S(i) = !f(i)(i), correct? The problem I see is that f's range is supposed to be Y. But then when you subscript again, each of those elements causes f(i), the first subscript, to be twice as large according to the process used to build a powerset. According to the definition of Y, in f(a)(b) we know A and B to not be one to one. Every element b doubles the amount of elements a as per the definition of a powerset.

So if you try and map A to B one to one when constructing S, you will be forced to only reach a proper subset of Y no matter what f you use. Now, granted, this is the result that Cantor and Cantor believers seek. But is this really a valid proof? We've not traversed the entire list of f, only a proper subset because the proof revisits the original non one to one mapping between X and 2^X.

I do not see how Cantor's proof can hold up. How is comparing against a mapping that is not one to one and only using a proper subset supposed to prove anything?

• Matthew Morse says:

Vorlath,

I don't understand everything you've written, but I'm going to respond to parts of it anyway.

Given a countable set X (so it can be ordered), constructing its power set Y as a set of tuples should work. The number of terms in the tuple is the size of X, so if X is (countably) infinite then each tuple has an infinite number of terms, but that isn't a problem.

If X is infinite, it is not correct that each additional "element of X doubles the amount of tuples in Y." Adding another member to X does not change its size. If X is infinite, then Y is also infinite. Adding a member to X also does not change the size of Y. Since X and Y are both infinite, it is not obvious that they are different sizes.

I don't follow your discussion of f(x) and the construction of S. I think you are starting with a function f(x) which maps members of the set A to the set B, so if a is a member of A then f(a)=b, where b is a member of B. I think you are then defining S as a subset of B. If b is a member of B such that there does not exist a member a of A such that f(a)=b, then b is a member of S. It's not clear to me whether you intend both A and B to be the same set, but they can be the same set or two different sets and these definitions of f(x) and S hold up, as long as S is a subset of B if the two sets are different.

If f(x) is one-to-one, then S is the empty set by definition, so I'm not sure what you mean when you say that f(x) is one-to-one.

I may have your intended definition of S backwards, so b is a member of S if there exists a member a such that f(a)=b. The first definition is the complement of the second, but it would be good if you clarify which you mean.

In your next paragraph, you use the notations S(i) and f(i)(i), and I'm not sure what either of those notations are intended to mean. If you can clarify this it would be helpful.

The meaning of the last two paragraphs escapes me. I think your argument is that if you map N to a proper subset of R, then Cantor proves that the mapping is a proper subset of R. Therefore Cantor is assuming what he's proving.

But Cantor starts with the assumption that the mapping is onto, and then demonstrates a contradiction. He does not assume what he sets out to prove. In fact, he assumes the opposite.

• Vorlath says:

I didn't see your message until now. Probably too late, but I thought I'd respond anyhow.

Given a countable set X (so it can be ordered), constructing its power set Y as a set of tuples should work. The number of terms in the tuple is the size of X [...]

Absolutely! But Cantor's proof itself proves that Y (2^X) is not one to one with X. You may think this sounds odd as I'm using Cantor's proof. But I've always said that if Cantor's proof is valid, then it disproves itself.

Adding a member to X also does not change the size of Y. Since X and Y are both infinite, it is not obvious that they are different sizes.

In Cantor's proof, he assumes a one to one relationship between the digits (same size as X) and the rows Y, correct? This is done so as to show a contradiction to said assumption. In this case, I absolutely agree that Cantor proved that in this particular relationship, the diagonal will NOT traverse all rows of Y. But Cantor's proof only speaks about that ONE relationship. It does not speak about ALL possible relationships. The digits of R define the rows of R. As such, that is a very specific mapping. This is a mapping that is known to not be one to one. Comparing all mappings to this non one to one mapping proves nothing.

For example. It can be proven that the digits of N (call this S) are a proper subset of N. And both sets are infinite (just look at Cantor's diagonal as proof producing an infinite identity matrix if you wrote 1's along the diagonal. The digits and rows map one to one. In other bases, they do not map one to one, but are still infinite). The digits being a proper subset, it means that some elements of S do not map to N. However, outside of the "grid" where the digits of N dictate what rows of N are possible, you can indeed remap S to N one to one. We know this since proper subsets of N have already been mapped to N. But with R, the situation is different.

What I'm saying is that Cantor's proof is nothing more than proving the definition of a proper subset. It is NOT about cardinality. Outside the relationship that defined the proper subset, that proper subset can be remapped one to one with the original set. Since Cantor never leaves behind the definition/mapping that created the proper subset, he will always find a contradiction.

For example, suppose I have a set of even numbers, call this E, and the set N. I then map all even numbers of N to each element in E according to their binary representations. So all elements of N that end with a 1 are not mapped. If I then remap one to one E to N, I must leave behind the mapping I originally had. If I compare these two mappings, they are different and I will have a contradiction. Cantor does exactly that. He never leaves behind the original mapping that defines the proper subset. He would map via digits and show that E does not contain any numbers that end with a 1.

So for any infinite set A, its set of digits B will be a proper subset of A. Within that definition, there will always be elements of B not mapped to A. This does not imply a difference in cardinality since if we discard that mapping and remap the sets, they can indeed be mapped one to one. But Cantor does not allow this. He always discards any mapping I give him and remaps it to the digits of the set I gave him, thus reusing the original non one to one mapping.

• Matt says:

Maybe I'm a stupid cantor crank, but I see two problems with the blog author's rantings. Problem number one. He asserts that all integers have a finite number of digits. If this is true then he is asserting that integers are not an infinite set as if you take any finite number , raise ten to that power, you still have a finite number. Raising ten to a power does not get you from finite to infinite. So this is basically a bogus definition of integers, unless you're making up your own finite set of integers. .... just choose your favorite power of ten which is finite, and supposedly that's the end of the integers. That's B.S.

Fundamentally, the problem here is that cantor got himself lost in infinity. He assumed the un-assumable namely, you could get to the end of an infinite list. There is no end to an infinite list, so you can never say OK, now I'm done counting through the list, and this number isn't on the list. What happens when you have an infinite mapping of R-N take your pick how you want to do it... go look at those mappings. go five or six lines down the mapping and build your cantor number. Now look at your number and examine the mapping. You will shortly discover that your cantor number is simply further down the list than you counted. All cantor proved was that his cantor number doesn't belong to any given subset of an infinite listing. He didn't prove that it doesn't belong to the entire infinite listing because there is no end to that infinite listing, therefore you can never stop your cantor number. It never gets done, therefore you can not create such a number. The cantor number of an infinite R->N mapping doesn't exist.

• Matt says:

That's what infinity means is you can't get to the end of the list by enumerating it one element at a time, so cantor's proof breaks because it assumes you can come to the end of the list which defies the nature of an infinite list.

• Matt says:

What remains is you get to decide on a criteria for an infinite set being larger than another infinite set. Then you get to compare infinite sets based on that criteria. In my opinion, the real numbers is still a larger set of numbers than the integers, but not because of cantors so called proof of supposedly nonexistent mappings which exist. Rather because of the nature of the required mappings. Cantors proof is not allowing the mind to capture the system. It views infinity from the viewpoint of the finite, which can never view infinity. The deal is that there will be different classifications of mappings, and you can pick and choose between them as you like in order to make your favorite definition of a bigger or smaller infinite set. There may be an infinite number of classes of mappings (not claiming that), meaning that it would be an infinite amount of work just to make the definitions as to which ones implied bigger infinities and which ones didn't. It requires a very extreme mapping to map from N->R. One might argue as to whether a particular mapping is legitimate. The argument can't be closed because it will ultimately come down to personal opinion as to whether the mapping is legitimate or not because it winds up being a damned definition that is called into question, and definitions are not universal truthes. They are just a way that we think about things and use words. Use the words this way, use the words that way, it doesn't change reality, but it can change how we think about it. On the other hand, thinking about reality in multiple different ways exposes multiple different facets of reality to consciousness. Therefore, the proper approach is probably to identify the facets of reality that are best exposed (as well as possible) by the different models of thought. Eventually we have to accept that some components of reality will never expose themselves to our minds no matter what model we use.

A trained mathematician pops onto the scene with a specified set of definitions in his head. Those definitions are supposedly some kind of consistent. The last thing this accomplishes is any kind of proof that there is not another consistent set of definitions. Mathematics is as much history as fact. Here's the words we use, here are our favorite operators, methods of proof, semantics, etc. To genuinely prove someone wrong, you have to work inside their own system and show that their own system is inconsistent with itself. You can't just say ... no, this is the system that we have been using. You can complain that they are not using your favorite standard system of thought, but this is not proof of error. So I say that you can map integers to reals. For example, you just take every odd numbered digit of the integers and swing it around the decimal point like an infinitely long stick and collapse each list of digits on each side of the decimal point. Unlike the blog authors assertion that integers can only have a finite number of digits which is obvious b.s. You can take two infinitely long lists of digits out of one infinitely long list of digits. Now, this is a very wild mapping, but it won't matter what real number you choose. It won't matter what cantor number you choose. You can map it back to an integer by undoing the afore-mentioned operation. Can you make up some definitions and use them to claim that that's an illegitimate mapping? Of course you can, but they are just definitions, not universal truthes. It's just a case of you deciding how you want to use words. If you define integers or naturals and say they are not infinite numbers, or they don't have an infinite number of digits (same claim), then you are asserting that there is only a finite number of them. Of course you can not map a finite number of numbers 1:1 to an infinite set of numbers. .. But claiming only a finite number of digits is pretty pathetic because its the same as claiming that it's not an infinite set, which is pathetic and uninteresting.

• Matt says:

Cantor's proof brings up the problematic of doing a proof that requires an infinite number of steps. Normally, we assume that a proof with an infinite number of steps can be valid, but look at it this way. if the probability of an error for each step of the proof is 0, then for any finite number of steps, the probability of the proof being in error will also be 0, but if your proof requires a number of steps that is infinite, then the probability of an error in the proof becomes something like infinity times 0, which is an undefined number. What that means is that for an infinitely long proof. Just having an infinite number of steps puts the proof into question, and the question has to be answered by another means other than the proof its self. The strategy of the proof has to be put under the microscope for any flaws that could show up in an infinite sequence of steps. Normally, we feel satisfied that there are no flaws. Take for example, the addition of an infinite number of continually decreasing numbers like 1 + 1/2 + 1/4 + 1/8 etc. We can see that as we approach infinity, the significance of the information continually decreases. And, that by the time we are at infinity, the significance of the information is 0. Therefore, a mistake in a proof of infinite steps in this case would not even upset the proof, so it doesn't matter that infinity times 0 is undefined in this case.

However, we readily accept that we can not take the sin function of infinity because infinity is not a number, and because the crucial information lies at the end or the final value of the infinity, which doesn't exist. Cantor has the same problem. He is taking the function at or his proof is the function of the end of an infinite list, which doesn't exist. He is pretending that infinity is a number. The crucial information is actually always past any designated end of an infinite list, so the proof is incapable of capturing that crucial information therefore defunct, and discardable. Another way to see it is You're riding a bicycle at 10 mile an hour and looking backwards. Your friend is riding at 20 miles an hour. You both start riding at the same time, but he is ahead of you. After an infinity of time you conclude that you have been everywhere and you never saw your friend, so he doesn't exist. Well, if your friend was always looking forwards, then he just might assert that he has been all over, and he didn't see you, so you don't exist, but both assertions are flawed. Cantor simply created a number that is always ahead of and out of view of his proof, not one that doesn't exist. It proves nothing about a mapping, but it does have some interesting things to say about the nature of infinity.

• Matt says:

So you might say that the interval [0,1] represents an infinite list of real numbers and the final number on the list is 1 as an attempted counterexample. My response is that [0,1] is a reductionistic view of an infinite list, not the infinite list itself. You can't enumerate your way from one end of it to the other end and ever get there because it's infinite. Furthermore, you can always add 0 to 1 and get another element of the list, which is still on the list. From your distorted reductionistic perspective, it appears that adding 0 to 1 does not generate a new element of the list. But that's because when we look at it from a distorted perspective, it does not appear to be infinite. But when your mind accepts that it is an infinite list, you realize that you have to accept adding 0 to 1 as adding a new member to the list. There are in fact an infinite number of 1's in the list, indistinguishable from each other from this distorted perspective of the list, rather only distinguishable by using a microscope with infinite magnifying power, which is the only genuine means of viewing this list in its entirety.

• Matt says:

Another view angle of this is to go back to the concept of meta-levels of proofs as discussed by Hofstadter in GEB. In reality, no proof ever really proves anything because before there is certainty of the proof, there must be certainty in the system used to accomplish the proof, but this can only be accomplished by using a more generic proof system, which then additionally requires proving by a more generic proof system ad-infinitum. Logic systems have flaws, and to deal with those flaws, we have to jump to proof meta-levels. In reality, Cantor has exploited a flaw in proof theory. It's not much of a surprise to believe that proof theory could have flaws in cases of infinite systems. After all, one of the most common assertions for example is that Goedels statement 'G' (This proof system can't prove this statement.) might be provable using a proof of infinite number of steps.

So, I'm going to assert on a proof meta-level that in order to prove something, all information relevant to the question must be acquired into the proof system before the proof is done. I am pretty **** confident that you will be unable to get your mind to disagree with that one. Now, can you see how this requirement might fall into question in cases that require an infinite amount of information to be gathered from an infinitely large space in order to make a proof?

The moment Cantor reduced an infinite list down to something he could come to an end of (so that you can have a number C), he imposed an act of reductionism on his work. Reductionism always loses information. So, the only question remaining is whether or not the lost information is relevant. In the case of Cantor's proof, it turns out that it's easy to see that the lost information is relevant by noting that every time you stop and build a C for a finite R-N mapping, if you were to continue the mapping, you can find that C further down the map. So cantor's proof is explicitly locking critical information to the proof outside of its self. Cantor sneakily reduced infinity down to finite terms, lost information in the act, and blew your brain away because you were too stupid to realise that methods of proof have their limits, and he stepped out onto turf where a tactic you might normally trust was a flawed tactic. His proof fails because it explicitly never obtains all information relevant to the proof. Now I don't give a **** what your professor said. You knuckleheads, it's time to grow up and realise that Cantor has a problem. Cantors proof can be reduced to a very interesting flaw in proof theory, highly similar to Goedels "this proof system can't prove this statement". Cantors proof reduces down to something like: "there is a valid proof of this statement which explicitly excludes information that exists that disproves this statement" So, this kind of statement might pass through a proof system, especially in the case of infinity and reductionism where information can be lost, but on a proof meta-level, it crashes. The method of proof is unsatisfactory by definition.

• Matt says:

This statement, and information relevent to its truth value are separated by an unbreachable barrier.

• Scientopia Blogs