Good Math, Bad Math

Grandiose Crankery: Cantor, Godel, Church, Turing, … Morons!

Posted by Mark C. Chu-Carroll on March 9, 2010
(71)
More »

A bunch of people have been asking me to take a look at href="http://arxiv.org/abs/1002.4433">yet another piece of Cantor crankery
recently posted to Arxiv. In general, I’m sick and tired of Cantor crankery -
it’s been occupying much too much space on this blog lately. But this one is a
real prize. It’s an approach that I’ve never seen before: instead of the usual
weaseling around, this one goes straight for Cantor’s proof.

But it does much, much more than that. In terms of ambition, this thing
really takes the cake. According to the author, one J. A. Perez, he doesn’t
just refute Cantor. No, that would be trivial! Every run-of-the-mill crackpot
claims to refute cantor! Perez claims to refute Cantor, Gödel, Church, and
Turing. Among others. He claims to reform the axiom of infinity in set theory
to remove the problems that it supposedly causes. He claims to be able to use
his reformed axiom of infinity together with his refutation of Cantor to get
rid of the continuum hypothesis, and to eliminate any strange results proved
by the axiom of choice.

Yes, Mr. (Dr? Professor? J. Random Schmuck?) Perez is nothing if not
a true mastermind, a mathematical genius of utterly epic proportions! The
man who single-handedly refutes pretty much all of 20th century mathematics!
The man who has determined that now we must throw away Cantor and Gödel, and
reinstate Hilbert’s program. The perfect mathematics is at hand, if we will only
listen to his utter brilliance!

To give you a bit of background: towards the beginning of the 20th
century, mathematics was in a confused state. They’d just started to encounter
problems with paradoxical statements in foundational things like set theory.
David Hilbert, one of the great mathematicians of the time, set out a grand
goal: to create the perfect mathematical foundation. The goal was to carefully
start from first principles, and:

  • create a precise formal system in which everything followed a set of strict,
    well-defined rules;

  • define the rules to prevent inconsistency by strictly
    preventing anything from reasoning about itself. This was done by
    by separating everything strictly into orders. A first order statement
    could talk about mathematical objects, but not about predicates. A second
    order statement could talk about objects and first-order predicates, but
    not about second-order predicates. A third order statement could talk
    about primitive objects, first order predicates, and second order predicates – but
    not about third. But within the system, you could
    never even formulate a statement in which a second-order predicate talked
    about a second-order predicate.
  • the system was supposed to be complete: in it, all true statements could
    be proved to be true; all false statements could be proved
    to be false; and all statements were either true or false.
  • the system was supposed to be consistent: no contradictions could ever
    be derived from valid applications of the system. Every statement
    was either true or false – there would be no statements that could be
    proved to be both true and false; and there would be no statements that
    could not be proved to be either true or false.
  • the system was supposed to be decidable: there would be
    a mechanical process which, given any statement, would be able to tell you
    after a finite period of time whether the statement was true or false.

    • ere would be an algorithm which would, after a finite amount of time,

Hilbert’s program was a huge deal. It consumed a huge amount of time and
resources from the best mathematicians of the time. It’s well known for
producing a major work by Russell and Whitehead called the Principia, which
took hundreds of pages to work its way up to href="http://scienceblogs.com/goodmath/2006/06/extreme_math_1_1_2.php">being
able to prove that 1 + 1 = 2. It was a truly epic project; but if it were
successful, it would have put all of mathematics on a sound basis. It would,
in some deep and important sense, have completed mathematics.

Alas, Gödel’s work blew Hilbert’s program right out of the water.
You can’t built a complete, consistent system of mathematics. You can’t define
a complete system of math with a decision procedure. But our intrepid genius
claims that all of this is wrong: Cantor’s set theory is bogus, the set of
reals is the same size as the set of natural numbers, Gödel’s
incompleteness theorems are wrong, Turing was wrong about computability, and
we can re-instate Hilbert’s program, finish the Principia, and happily have
the perfect mathematical system, with J. A. Perez as the most brilliant
mathematician of all time.

Except for the minor problem that he’s completely wrong.

What he does is interesting, in a brain-dead sort of way. He basically
tries to find a problem with the basic proof technique used by both Cantor and
Gödel. Of course, proof by contradiction is an old, well-respected proof
system. You can’t just say that all proofs by contradiction are wrong.
There are lots of really good proofs that are done by contradiction. But
Cantor and Gödel are obviously wrong, and yet both proofs look
bulletproof – so there’s got to be something wrong with how they used
proofs by contradiction.

What he homed in on is what he calls internal contradiction versus
external contradiction.

He claim that the classical uses of proof by contradiction are what he
calls external contradiction. In proof by external contradiction, you start
with a statement P, which you want to prove is true. So you assume that it’s
false, and then you use that to derive a contradiction. So you assume not-P,
and then use that to derive a proof of some other statement, R, which
is known to be false. So by the process of proof from not-P, you’ve derived
the contradiction R∧¬R. By simple logic, that means that not-P
allowed you to prove a false statement, which in turn means that not-P is
false, and that means that P is true. Presto, you’ve got your proof.

In contrast, Cantor and Gödel are what he calls proof by
internal contradiction. He claims that in these proofs, you start
with the statement you want to prove – P. Then you negate P; and by using
not-P, you can derive a proof that P is true. So not-P is used to derive P.
Instead of ¬P deriving R∧¬R, ¬P is used to derive
¬P∧P.

It’s an interesting distinction in its way – it’s fundamentally a
difference between a proof built on self-reference, and one that isn’t.
Self-reference is the source of many problems – the fundamental paradoxical
statements that have plagued modern math are all built on self reference:
Cantor’s naive set theory was shown inconsistent by the use of a
self-referential object: the set of all sets that do not contain themselves;
Gödel’s proof is build around the self referential statement “There is no
proof that this statement is true”.

But there’s no logical flaw with a proof that has a self-referential
aspect. Or is there? Perez claims that there is.

Let’s start with his version of a proof by external contradiction. He says
that every proof is, essentially, a sequence of statements, Q1,
Q2, …, Qn, where each statement Qi+1 is an
implication of Qn. So you can state a proof as Q1 ⇒
Q2 ⇒ … ⇒ Qn, where Qn is the
conclusion. In this formulation, Q1 is the statement ¬P – that
is, the negation of the statement you want to prove; and
Qn is the statement R∧¬R, where R is some statement that is
neither P nor ¬P. (That last line is, according to Perez, very important.
He repeats it several times in different ways.) So the entire proof can be
reduced to ¬P⇒(R∧¬R).

In a proof by internal contradiction, you’ve got the same basic
setup, except that you start with ¬P, and you end up with
¬P⇒(¬P∧P). That is, the final contradiction that breaks the
proof contains the initial false assumption.

According to Perez, that’s potentially a problem. It isn’t necessarily
a problem, but it might be. See, if you can reason backwards from the
contradiction to cast doubt on any of the earlier statements, then according
to him, the proof will fail.

This is where things start to get a bit goofy. Suppose that in your basic
proof schema, all of the implications were not just implications, but logical
equivalences. That is, your proof schema for the proof by internal
contradiction was: (¬P)⇔Q2⇔…⇔Qn-1⇔(¬P∧P).
Then you’ve got a known-falsehood at the end – and you can also use that
backwards. So (¬P∧P) ⇔ Qn-1. And, in fact, (¬P∧P)
imply each any every one of the Qi. So the invalid conclusion
implies each of the statements in the proof – which means, according
to Perez, that the truth of every statement is thrown into question; in fact,
the proof by internal contradiction contains an implicit disproof of every true
statement used in the proof. Since the entire proof technique is doing something
that we know to be incorrect, that demonstrates that the proof by internal
contradiction, when the logical connectives are equivalences, is invalid.

If that proof technique is invalid, then every proof that was built using
it is also invalid. So Cantor’s diagonalization goes out the window. And so
does Gödel. And so does most of Chaitin. And, well, lots of other
stuff.

The problem for Perez is that this argument is bogus in so
many ways.

Let’s take one nice one, which he’s absolutely explicit about. His
proof schema is based on a proof as a sequence of atomic statements,
each of which implies the following statement. That’s not the
structure of a proof. A proof does have a series of implications leading to
a conclusion, but it’s not linear. Proofs are graphs of implications, not
lines.

A perfect demonstration of how bogus this is comes from Perez’s discussion
of Cantor’s diagonalization. According to Perez, you start with
the statement P that you want to prove. In Cantor’s diagonalization,
P is the statement: “The unit interval I = [0, 1)” is an uncountable set.”.
The proof is sketched as:

  1. Take ¬P to use as the foundational step of the proof by contradiction: ¬P=”The unit interval
    I := [0, 1) is a countable set”.
  2. Q1 = “The set I can be written out as an array of decimal expansions, …”
  3. Q2 = “It is possible to define a real number … such that it belongs to
    the interval, but …”
  4. Q3 = “The array is not a complete listing of the elements of I.”

According to Perez, ¬P⇔Q1. That is not true:
assuming that the interval is a countable set does not give you the
fact that the set can be written out as an array of decimal expansions. The
decimal expansions comes from an entirely different starting point. So the
proof actually has two branches from the beginning. The proof isn’t a straight
line of implication; it’s a branched structure. So the proof schema isn’t
“¬P⇔Q1⇔Q2⇔Q3.” It’s
actually “¬P. Q1. ¬P∧Q1∧…↔Q3.” (I left the dots, because
there are still missing steps; ¬P∧Q1 isn’t enough to get
get to Q2.)

The branching is a fundamental problem for Perez. Because what he wants to
say is that every statement used in the proof is invalidated by the
contradiction. But with logical connectives like “∧”, that’s not true.
Perez wants to say that since Q3 provides a contradiction, that it
invalidates Q2; which invalidates Q1. And, in fact,
according to Perez’s reasoning, it does worse than that: it invalidates every
axiom used in the proof – because the axioms are used as steps.

But axioms aren’t used as discrete atomic steps of the proof implied by
prior steps. They’re used as parts of complex statements. Axioms are used in
the form “Qi ∧ Axiom ⇔ Qi+1.” The negation of
that doesn’t imply the negation of the axiom; it implies (¬Qi)
∨ ¬Axiom).

And boom, there goes Perez’s proof; the structure of a proof by internal
contradiction doesn’t imply the falsehood of every statement used in
the proof. It doesn’t imply the falsehood of any axioms.

But there’s more stupidity. One of the most basic rules of logic is that
you can’t reason from contradiction. That is, given a statement like (A ∧
¬A), the statement is always false. Given any false statement,
you can arbitrarily construct implications: for any possible
statement S, no matter whether S is true or false, (A∧¬A)⇔S. The
fact that a contradiction implies something is utterly worthless. You
can never reason from that implication, because the statement (A∧¬A)
is always false, so you can’t infer anything about the conclusion. The
entire process that Perez uses, trying to trace backwards from a contradiction
is fundamentally meaningless.

From this point, things go downhill. Perez then verges into classic
anti-Cantor-crackpot material, providing his version of several different
constructions that allegedly demonstrate a correspondence between the natural
numbers and the reals. And then he really goes off the deep end.

Seriously, this is one of the most ridiculously grandiose works of crankery
that I’ve ever seen. This guy seriously believes that he’s pretty much the
most brilliant mathematician in the history of mathematics, and that this paper
is the ultimate mathematical tour-de-force. He’s probably sitting in his
office waiting for his Fields medal.

(71)
More »

Comments

  1. #1 Anonymous
    March 9, 2010

    “for any possible statement S, no matter whether S is true or false, (A∧¬A)⇔S”

    You’re arrow has too many heads. It should be (A∧¬A)=>S. The other direction only holds if S is false.

  2. #2 Joshua Zelinsky
    March 9, 2010

    He’s also wrong about Cantor’s argument in a different way: You can phrase the diagonalization proof as being what he calls a proof by external contradiction. This takes minimal effort. You start with your hypothetical 1-1 mapping function and you get a specific number that is not equal to itself (since it is both in the range and not in the range of your function).

  3. #3 ARS
    March 9, 2010

    Checking the Combined Membership List of the AMS, I did find a Juan Perez, who is a graduate student in mathematics at the University of Michigan. I don’t know whether he is the author of the paper, but he is the only match in the CML.

  4. #4 Max
    March 9, 2010

    ARS: Nope, that’s the wrong one. Different middle name (google “Juan Perez michigan” and look at the google profile at the bottom of the page)

  5. #5 Nemo
    March 9, 2010

    If his “reasoning backward” argument made sense for proofs by “internal contradiction”, would it not make equal sense for proofs by “external contradiction”?

    (You introduced the distinction, but then promptly failed to use it for anything. Curious whether Perez does the same thing. Well, not that curious. You seem to spend a lot of time reading crackpots.)

  6. #6 Mikael Vejdemo Johansson
    March 9, 2010

    Oh, Perez got up on the arXiv at last? I’m going to enjoy reading your analysis of his writings – he spent some time about a year back trying to convince me to sponsor his posting to the archive.

  7. #7 Spencer Bliven
    March 9, 2010

    He may be a crank, but at least he managed to derive a date with your mom!

  8. #8 ijc
    March 10, 2010

    If you assume ~P and derive P, we can proceed two ways:

    (1) Obtain P immediately by the principle of non-contradiction.

    (2) Directly, as in a conditional proof, where we have shown that ~P => P, which is equivalent to ~~P v P, and so P.

  9. #9 Ingvar
    March 10, 2010

    There’s a dangling sentence fragment under the bullet points listing the goals of the Hilbert Program. Not critical, but somewhat distracting.

  10. #10 xavier johnson
    March 10, 2010

    To P or not to P, that is the question.

  11. #11 Kuroki Kaze
    March 10, 2010

    Whoa, that’s one verbose explanation. Even I can get it, and I’m not mathematician :)

  12. #12 Tristram Brelstaff
    March 10, 2010

    “(¬P∧P) imply each any every one of the Qi”
    should probably be:
    “(¬P∧P) imply each and every one of the Qi”

  13. #13 bobh
    March 10, 2010

    Mark,

    I generally enjoy your posts but as an old physicist could use a little help on the notation. Does the little square mean “and”?

  14. #14 mike
    March 10, 2010

    @bobh 13
    The square means that your browser is not rendering properly. It inserts a square there as a filler instead of the actual symbol.

  15. #15 Robert S.
    March 10, 2010

    For those not getting the joke Bliven@7 made

    http://xkcd.com/704/

  16. #16 a soulless automaton
    March 10, 2010

    The first part makes it sound like Perez was halfway to reinventing some sort of finitist/constructivist approach to mathematics, before going off the rails.

    I suppose the difference between a crank and a mathematician is that, given a proof with a distasteful conclusion, the crank futilely attacks the proof, while the mathematician finds an axiom the proof relies on, declares it “obviously false”[0], and gets back to work.

    Maybe someone should sit these cranks down and tell them that, while Cantor’s proof really is sound, it honestly is, why don’t they just regard it as a proof-by-absurdity that real numbers don’t exist, or something? Really, for geniuses of their obvious caliber, attacking a mere proof seems trivial when they could be striking at the flawed axioms that everything else builds from.

    [0]: When Alfred Tarski sought to publish a proof of equivalence between the Axiom of Choice and the statement “every infinite set A has the same cardinality as the Cartesian product of A with itself”, it was rejected by two different reviewers; one wrote that an equivalence between propositions known to be true was not novel, while the other wrote that an equivalence between propositions known to be false was not interesting.

  17. #17 Tom
    March 10, 2010

    For those having trouble with the character rendering…the little square means that the “and” symbol (looks like an upside-down “v”) doesn’t exist in the font that your browser is using. You’ll want to change the “sans-serif” font to something that includes it. In my case, the default for sans-serif was Arial, which doesn’t include the “and” symbol (∧). I changed to Trebuchet MS, and now it renders correctly.

    Depending on the browser that you’re using, you need to open the Preferences or Options pane, find where you can set the default font, and then (probably) click on the “Advanced” button.

  18. #18 bobh
    March 10, 2010

    @mike 14

    Thanks. Using latest Firefox on Windows. Tried latest IE and it displayed properly – makes sense now.

  19. #19 ex
    March 10, 2010

    Thanks for this.
    I’m not a mathematician – but I still enjoy reading this blog. Thanks for keeping the level of math high but explaining it even for us dummies ;)

  20. #20 Quercus
    March 10, 2010

    @16: That story really cracked me up! :)

    It reminds me of another (quite unrelated) story, about a professor in my university: In one of his reviews, he said that the author gave “unnecessary and insufficient conditions for [statement]“… Pure genius :)

  21. #21 abb3w
    March 10, 2010

    Mark C. Chu-Carroll: He claims to be able to use his reformed axiom of infinity together with his refutation of Cantor to get rid of the continuum hypothesis, and to eliminate any strange results proved by the axiom of choice.

    You don’t have to reform the axiom of infinity to do that; that may just require taking Refutation of the Axiom of the Power Set. Without being able to assert that the Infinity Axiom set’s Power Set is itself a set, you can’t construct sets of higher cardinality than the initial Aleph-0, which throws out the question of the continuum hypothesis by throwing out both the Real Numbers and all the other cardinalities. =)

    Mark C. Chu-Carroll: Axioms are used in the form “Qi ∧ Axiom ⇔ Qi+1.”

    I think it would be more precise to say that they are used in the form “Qi ∧ Axiom ⇔ Qi ∧ Axiom ∧ Qi+1“.

    Mark C. Chu-Carroll: That is, given a statement like (A ∧ ¬A), the statement is always false.

    Well, in a logic based on any Boolean lattice, anyway. In a logic based on a Heyting lattice, it may be a value that is neither TRUE nor FALSE, akin to UNDEFINED. However, Heyting logic isn’t used much except by perverse philosophers who don’t like one or another Boolean axiom.

  22. #22 delosgatos
    March 10, 2010

    Pages 31-35 or so are particularly amusing. Proof of this statement is left as an exercise for the reader. :)

  23. #23 Mike
    March 10, 2010

    This distinction between internal and external contradictions seems particularly inane. Since, as mentioned, a false premise can imply anything, it doesn’t take much to get from P => R ^ ~R, and R^~R => P ^ ~P, to P => P^~P. So voila… an ‘external’ contradiction IS an ‘internal’ contradiction.

    Semi-random, amusing aside that this reminds me of….
    In a fundamentals of advanced math course several semesters ago, there was a problem on a test to prove that there were no solutions to some simple inequality, via contradiction. After about 3-4 lines, I arrived at x^2 + 1 < 0 (where x was a real number). However, I was apparently off my game this particular day… perhaps over-caffeinated… perhaps under-caffeinated… In any event, I didn’t recognize that statement as contradictory, and pressed totally aimlessly on for another 20 minutes, and another page and half or so, until I finally arrived at something that was more obviously contradictory. I left the class thinking “wow, that was insanely more difficult than expected.” When the prof handed the test back, she’d circled my (x^2 + 1 < 0) statement, and wrote a giant “WHAT?!” over top of the following page of my rambling.

  24. #24 Quercus
    March 10, 2010

    @23:

    Two mistakes:

    - I think you’re wrong on your first point. the fact that you CAN derive P^~P from R^~R doesn’t mean that it’s an “internal” contradiction – the definition does not mention continuations of the proof.

    - x^2+1 is not a statement, so you can’t really say it’s a “contradiction” :P

  25. #25 Colin T
    March 10, 2010

    I don’t think Perez is a crank, though his analysis goes against the current orthodoxy. No one has mentioned that his starting point was the construction of a proof of Goodstein’s Theorem in first-order arithmetic (arxiv.org/abs/0904.1957). I can’t see anything wrong with this proof, which doesn’t fall into the Cantor crankery camp. Mark and others have not commented on this proof, so presumably also found it correct. If this proof is correct, as you all probably know, it contradicts Godel and implies completeness. As far as I can see, Perez looked at Cantor and Godel to try and explain this discrepancy. His analysis of proofs by contradiction is spot on, as any basic text book confirms – though clearly this is uncomfortable when applied to Cantor!

    Mark is right about branching being an essential part of the construction of any proof, but only to establish the truth of intermediate statements of the main line, so doesn’t hold water as a criticism of Perez’s analysis. Mark’s other arguments against Perez are irrelevant, weak or misrepresent what is actually said in the paper. And Perez doesn’t reformulate the Axiom of Infinity, as Mark wrongly states. I think people should read the paper themselves, objectively, and not rely on Mark’s subjective comments, which address only a small part of the paper.

    However, I do agree with Mark on something – Hilbert was a great mathematician, so it’s a shame his views were discounted in favour of Godel. It might be unthinkable at the moment that Perez is right, but it might be easier to swallow if we focus on the benefits of completeness as Hilbert envisaged, and see Godel as misled by Cantor.

  26. #26 Anthony de Almeida Lopes
    March 10, 2010

    I completely agree with Colin T in #25. I found Mark’s review questionably subjective and condescending at times especially with clauses such as “[...] with J. A. Perez as the most brilliant mathematician of all time.”

    On the other hand, I understand Mark is rather tired of papers claiming to refute Cantor by people who clearly do not understand Cantor.

    I hope to see both of Perez’s papers get some more attention, especially regarding the [in]completness aspect.

  27. #27 Rilke's granddaughter
    March 10, 2010

    My personal guess is that both the last two posters are either cranks, or Perez himsel writing under an alias.

  28. #28 Rilke's granddaughter
    March 10, 2010

    My personal guess is that both the last two posters are either cranks, or Perez himsel writing under an alias.

  29. #29 Freak
    March 10, 2010

    Or maybe Perez’s proof isn’t written in first-order arithmetic. (He also apparently failed to consider the possibility that Paris and Kirby were wrong.)

    Perez doesn’t understand the contradiction Cantor’s establishing. Cantor’s immediate result wasn’t “the antidiagonal element shows P(N) is not denumerable”; it was “the antidiagonal element shows that the proposed bijection is not a bijection”. (Look at example 3.3. The sets S_k are denumerable, but not bijections.)

  30. #30 Mark C. Chu-Carroll
    March 10, 2010

    @25:

    Don’t presume anything based on what I didn’t say.

    Perez analysis of proof by contradiction is absolute, utter, total rubbish. He created a meaningless distinction between “internal” and “external” contradiction; and then formulated an invalid proof schema, which he used in his proof. My post is pretty specific about what he did wrong. He specifically claims that the initial statement, “The reals are enumerable”, implies and is implied by “The reals are representable”. That’s crucial to his critque – and yet, it’s not true.

    As for my mocking him – let’s be serious for a moment. If, indeed, Perez was able to formulate a proof that showed that Cantor, Gödel, Church, and Turing were all wrong about some of their most foundation works, it would be a truly astonishing feat of brilliance. If he really did that, he would absolutely deserve to be recognized as one of the greatest mathematicians of all time. No sarcasm there – anyone who could really do what Perez claims to have done would be a historic figure in math.

    The problem is, Perez’s “analysis” is a pile of rubbish. It’s riddled with errors. It’s based on meaningless distinctions and invalid logical reasoning. It’s purest garbage. And instead of just writing that silly piece of garbage, he uses it as a springboard to set out on a truly ridiculous and arrogant course of redefining most of modern mathematics in silly ways.

    And if he doesn’t redefine the axiom of infinity, then what the heck is his theorem of real infinity about? It’s an attempt to take the implications of the axiom of infinity that he doesn’t like, and define them out of existence. He specifically introduces it by talking about the “problems” with the axiom of infinity.

  31. #31 Mark C. Chu-Carroll
    March 10, 2010

    @28:

    Yeah, it sure looks like sockpuppetry. “Colin”‘s IP address shows up before his comment. Then there’s his comment. Then 30 minutes later, there’s another visit from Colin’s IP address, immediately followed by a comment posted through an IP anonymizer. It’s not proof, but it’s certainly suspicious.

  32. #32 Vorlath
    March 10, 2010

    Mark, you don’t understand the basics of proof by contradiction. If the infinite prime proof ended up showing that the elements in the list were both prime and composite, you’d say the proof was still valid. So when you talk about Cantor, I just sit back and laugh my head off. You’re a riot. You think that if the result is nonsensical, that this is enough for a proof by contradiction.

  33. #33 Dan Doel
    March 10, 2010

    In a logic based on a Heyting lattice, it may be a value that is neither TRUE nor FALSE, akin to UNDEFINED. However, Heyting logic isn’t used much except by perverse philosophers who don’t like one or another Boolean axiom.

    Perhaps Heyting logic isn’t popular in mathematics at large, but it’s quite relevant in (some branches of) computer science (and related mathematics). Constructive mathematics is in a sense the mathematics of the computable. Through that view, excluded middle says “we can compute proofs or disproofs for every proposition,” which is quite simply incorrect. So, it crops up quite naturally in programming languages where one wants to incorporate proofs into their programs.

    Also, I may be a bit confused, but I don’t think A ∧ ¬A is some undefined, non-false value. It’s quite simple to prove ¬(A ∧ ¬A) in intuitionistic logic. What one can’t prove in general is A ∨ ¬A. One can prove ¬¬(A ∨ ¬A) for arbitrary A, but the double-negation cannot be eliminated, making A ∨ ¬A in a sense non-false, but not true (or, non-disprovable, but not provable).

  34. #34 Freak
    March 10, 2010

    His proof of Goodstein’s theorem isn’t remotely in PA.
    The axioms of PA are very low level:
    Ax:Sx != 0
    AxAy: Sx = Sy -> x = y
    …
    Just coming up with a way to state Goodstein’s theorem in PA is pretty difficult.

    [quote=Perez]Proof. Since i) a 1 = a , ∀a  N , and ii) 1b = 1 , ∀b  N , assume that a , b ≥ 2 . Consider N , the set of the natural numbers. Now consider, within the enumeration of the elements of N, all the powers of a , which can be selected to construct the corresponding subset Na  N: Na = {a0, a1, a2, a3, a4,   } = {a k, k ∈N}.
    (3.1)
    The critical requirement is to establish that the subset Na is an infinite set. If Na were a finite set, the implication would be that one of the elements of Na would …
    [/quote]

    PA doesn’t even have the direct concept of a set, let alone finite vs. infinite. Perez might have done his proof in some first order system equivalent to PA, but if so, he should claim that explicitly.

  35. #35 Anthony de Almeida Lopes
    March 11, 2010

    Freak in #34, good point.

    Dan Doel in #33, in intuitionist logic, A ∧ ¬A would be by definition A ∧ (A → ⊥). Applying modus ponens to this renders absurdity. ¬(A ∧ ¬A) would be (A ∧ (A → ⊥)) → ⊥ which, as shown above, by definitional reduction, should reduce to ⊥ → ⊥ which is a tautology. So, I think you’re right: ¬(A ∧ ¬A) should be completely valid (and true), as my understanding goes anyway. On the other hand, A ∨ ¬A is not given as an axiom; however, you could justify it or introduce it as an assumption, depending on the specific choice of A. I’m not sure that’s relevant for this discussion though.

    MarkCC in #31, you thought I was coming from an IP anonymizer? Hmm, weird.. Anyway..

    I’m curious, “where are you coming from?” I mean, in general, what logical framework do you work in? Do you disagree with BHK and/or intuitionism in general?

    “If that proof technique is invalid, then every proof that was built using it is also invalid.”
    Indeed, I think this is what he is actually saying. The opinion is not unique to him though as this is a stance taken by many other constructivists and intuitionists. The vast majority of modern type theory operates on this premise.

  36. #36 Anthony de Almeida Lopes
    March 11, 2010

    I want to clarify that I am neither a Cantor crank nor do I necessarily agree with Perez in general. I do happen to understand Cantor’s proofs and I understand that if I were to ever disagree with Cantor it would have to be from a constructive-finitist point of view or it would involve rejecting the actual logic (the formal system itself) as Perez is doing.

    My only concern here is that we are not being as open minded from a metamathematical point of view as we could be. If we agree with classical logic, clearly Perez is wrong. That is not to say that Perez is right in any named logic (even intuionistic), but I think it is worth at least entertaining the idea of a mathematics without the specific type of redictio argument that he highlights. Does disallowing them get us anywhere? That is what I really am curious about.

    By the way, in contrast to my previous post, Gödel’s theorems and proofs for them have been formalized in a proof-assistant that is based on intuitionistic logic (namely, Coq) by Russell O’Connor in 2003. I suspect it has been done by hand many times before that although I do not have a specific reference.

  37. #37 Anthony de Almeida Lopes
    March 11, 2010

    Actually, it seems there is at least one logic that allows formally reasoning from a contradiction: “para-consistent logic” and it’s based on the principle of “dialetheism.” (Admittedly, I’m reading about this for the first time.)

    Anyway, Perez doesn’t mention any of this. So either he’s working in classical logic and is wrong, is working in a para-consistent logic and hasn’t explicitly stated that he is or doesn’t know what he’s doing at all (or by dialetheism, all of the above!)

    Stanford’s Encyclopaedia of Philosophy has a pretty good introduction to dialetheism:
    http://plato.stanford.edu/entries/dialetheism/

  38. #38 mike
    March 11, 2010

    @Anthonny de Almeida Lopes (Colin T?)
    Mark and most his readers are 15 steps ahead of you. Nobody cares what logic Perez is working with and we aren’t irked by the scope of what his claims, if true, would entail. The point is that Perez makes crazy errors all over the place while talking about the most famous proofs from the last century. It’s what Mark labels as “Grandiose” that makes this crankery noteworthy.

  39. #39 Anthony de Alemida Lopes
    March 11, 2010

    @mike:

    Thanks for your response. That’s exactly what I was wondering: whether or not his mistakes were independent of the underlying logic (or in general, philosophy) used. It just bothered me that that aspect wasn’t addressed explicitly, but I suppose that would be tedious for Mark to do in every post (and probably for his readers to read), especially since such things are probably more obvious to the more experienced here.

  40. #40 a soulless automaton
    March 11, 2010

    @Dan Doel (#33): Logics with more than two truth values are indeed useful in computer science, though it bears noting that programmers have a different standard term for a third logical value. Multi-valued logics are also useful in digital circuit design, with additional logical values for things like “disconnected”. For the truly dedicated, there’s even IEEE 1164 9-valued logic.

    @Anthony de Alemida Lopes (#39): Did you actually look at the arXiv link? Even if everything he says is correct in some nonstandard logic, he writes as if it applies to standard logic, which doesn’t inspire confidence. He also moves very quickly past the crux of his argument (which may or may not constitute a reasonable definition of a nonstandard logic) without giving it a satisfyingly rigorous definition, instead jumping into an extended discussion about all the amazing things you can prove afterwards. Like I said in my previous comment: Cranks complain about proofs, real mathematicians complain about axioms.

    Otherwise, everything you say is perfectly reasonable. In fact, speaking as a computer scientist, I’m strongly inclined to question the sensibility of non-constructivist logic, but I’m not about to claim that being unable to express a proof within a typed λ-calculus constitutes a refutation of it.

  41. #41 Mark C. Chu-Carroll
    March 11, 2010

    The non-standard logic thing is a non-starter.

    You can define a logic to produce just about any structure you want. But one of the fundamental points of Gödel is that if you do, and you can express Peano arithmetic in that logical system, that the system is necessarily either inconsistent or incomplete.

    If Perez’s work is in a non-standard logic, it doesn’t matter. Gödel’s proof still applies: it shows you how to use Peano arithmetic to construct an unprovable statement, demonstrating that the system is incomplete.

    Perez clearly includes Peano arithmetic in his system. So standard logic versus non-standard doesn’t matter. Intuitionist or constructivist versus classical doesn’t matter.

    Worse, Perez clearly states that his result shows that the halting problem is solvable. And yet, the classic problem with the halting problem – the simple counterexample that Turing used in the original proof – still exists. In fact, I can literally write it as a simple, tiny program. A dozen lines of haskell, including various type declarations.

    So whatever logic he’s using, he’s generating trivially demonstrably false results. He even makes a stab at admitting that – basically by creating the notion of “inconceivable”, and defining it so that the exception to the halting problem – even though it’s clearly trivially constructable – is inconceivable.

  42. #42 Anthony de Almeida Lopes
    March 11, 2010

    @a soulless automaton in #40: Yes, I did look at it actually, but that doesn’t say much as I already admitted, I did not see many of the errors as obvious.
    Anyway,
    “he writes as if it applies to standard logic.”

    Yeah, I definitely see that as a huge problem which I think I even mentioned before? I was just curious if anything he said made sense even if his logic was non-standard, which I think Mark, right below your post, explains perfectly.

    “but I’m not about to claim that being unable to express a proof within a typed λ-calculus constitutes a refutation of it.”

    Very good point. Syntactic inadmissability is not refutation at all. Hmmm, right.

    By the way, regarding your original comment in #16, “why don’t they just regard it as a proof-by-absurdity that real numbers don’t exist”

    After having read a few of the crank debunkings here (and the extensive comment threads they generate), I actually came to believe that. Glad to know that doesn’t make me too crazy.

    “Cranks complain about proofs, real mathematicians complain about axioms.”

    Huh?

    @Mark in #41. Awesome explanation. Thanks, I appreciate that you took the time to explain that.

  43. #43 a soulless automaton
    March 11, 2010

    @Anthony de Almeida Lopes (#42):
    My conclusion, upon cursory inspection, was that given his claims, Perez is either catastrophically wrong or is effectively constructing a very weak system (e.g., something like the propositional calculus or Presburger arithmetic) and misapplying it to ideas it cannot express (real numbers, general recursion, etc.). Either way it’s deeply confused, but I didn’t have time to figure out in which way; MarkCC’s comment suggests the former.

    “After having read a few of the crank debunkings here (and the extensive comment threads they generate), I actually came to believe that. Glad to know that doesn’t make me too crazy.”

    Outside mainstream mathematics perhaps, but not crazy; real numbers are conceptually very problematic from a computational perspective. Most real number numbers can’t be computed–or in fact described–at all, where “computed” means you can produce an approximation to arbitrary precision, like calculating digits of pi. The computable reals remain awkward as well, due to issues such as testing equality being, in general, undecidable (actually equivalent to the Halting Problem, I think).

    “Huh?”

    I just mean that, when mathematicians don’t like a valid proof, they tend to reject a key axiom rather than produce bogus “refutations”–the Axiom of Choice is perhaps the best example, being both intuitively “obvious” and providing proofs of “absurd” propositions.

  44. #44 Mark C. Chu-Carroll
    March 11, 2010

    @41:

    Real numbers are extremely strange. They start off seeming perfectly reasonable, but once you accept them, you’re stuck with some very strange results – like the fact that the vast majority of numbers cannot ever even be described. In fact, if you were to really randomly select the a real number from a uniform distribution, the odds of it being a number that can be described algorithmically is zero.

    Greg Chaitin, who I personally believe is the best mathematician working in the world today, has said that it’s worth at least considering the notion that real numbers don’t really exist, but are rather just an artifact of logic.

    It’s perfectly reasonable to discard Cantors proof for the simple reason that you think that the definition of real numbers is too strange. You can build up a perfectly reasonable mathematics using a system of computable numbers – which gives you the integers, the rationals, and all of the irrationals and transcendentals that you care about.

    But it’s not standard math. And even by doing it, you don’t get rid of much of the strangeness that Perez aims to defeat. It would invalidate Cantor’s proof – or rather, Cantor’s proof doesn’t say that the set of computable numbers is larger than the set of natural numbers; Cantor’s proof about the real numbers applies to the real numbers – not to a subset of the reals like the computables. A variant of Cantor’s proof *can* still be used to show that the powerset of the set of computables is larger than the set of computables. And it definitely doesn’t come anywhere close to touching Gödel; Gödel doesn’t use anything but natural numbers in his proof.

  45. #45 a soulless automaton
    March 11, 2010

    MarkCC raises an excellent point.

    Interestingly, we can observe that the computable reals have countably infinite cardinality, as they are (by definition) expressible as finite algorithms, so we know that a bijection between the natural numbers and the computable reals must be possible. The computable reals also have infinitely long sequences of non-repeating digits. These points together at first seem to suggest that Cantor’s diagonal proof does apply, letting us compute successive digits of a number not in the list! What is this madness?

    In actuality the argument does indeed work in a fashion, but proves something different. The flaw in the above is the assumption that the bijection from naturals to computable reals is itself computable. In other words, the computable reals have in some sense “countably infinite” cardinality, yet it is impossible to actually enumerate, and thus count, them! Gödel will not be denied so easily, I fear.

  46. #46 Dan Doel
    March 11, 2010

    @a soulless automaton (#40)

    It’s actually not that intuitionistic logic has more than two ‘truth’ values. It doesn’t have true, false, and file-not-found. :) At least, it doesn’t have three provably distinct values like that.

    Rather, one can classify propositions into something like the following:

    1) P is a theorem (these are ‘true’ propositions)
    2) ¬P is a theorem (these are ‘false’ propositions)
    3) ¬¬P is a theorem (these are non-false propositions, but not true)

    After this it collapses, because ¬¬¬P → ¬P is a theorem for all P. It’s also a theorem that P → ¬¬P, so ‘true’ propositions are also non-false. But we can’t reason from P being non-false to P being true. In fact, ¬¬(P ∨ ¬P) is a theorem for all P, so excluded middle is non-false in intuitionistic logic (this works in general for the propositional calculus; if P is a theorem in the classical propositional calculus, ¬¬P is a theorem in the intuitionistic propositional calculus). So, strictly speaking, I suppose the best way to characterize the situation is that there aren’t three truth values (there’s no file-not-found that is provably distinct from true or false), but you can’t prove that every truth value (or proposition) is either true or false.

    Here is an article that probably explains it better than I have (I haven’t fully internalized it myself).

    Also, to give the subject of the article some credit, if you’ve found a flaw in Cantor’s argument, you may well have found a flaw in Goedel’s and Turing’s (and Tarksi’s) arguments as well, because they are, in an abstract sense, all the same argument.

    Finally, I doubt a paraconsistent logic would save the guy, at least if his argument was described correctly. He apparently accepts:

    P => … => R ∧ ¬R

    as a valid disproof of P (the so-called external contradiction). But a paraconsistent logic would reject this just as easily as it’d reject

    P => … => P ∧ ¬P

    which he takes issue with. So I don’t see how that could be the answer to “what is he thinking?”

  47. #47 Anonymous
    March 11, 2010

    But I thought that Cantor’s proof was NOT a proof by contradiction?

    You know, take a function f: N |-> R and show that it isn’t surjective.

  48. #48 william e emba
    March 12, 2010

    Colin T wrote:

    I don’t think Perez is a crank, though his analysis goes against the current orthodoxy.

    Perez is obviously a crank. If you can’t tell, you’re an idiot yourself.

    No one has mentioned that his starting point was the construction of a proof of Goodstein’s Theorem in first-order arithmetic (arxiv.org/abs/0904.1957). I can’t see anything wrong with this proof, which doesn’t fall into the Cantor crankery camp.

    Perez starts off with grandiose claims that he’s done something original with Goodstein sequences (starting above 2) which is in fact entirely unoriginal. He then claims to have proven Goodstein’s theorem in Peano Arithmetic (not in First-Order Arithmetic, as you state, an assertion which doesn’t make any sense in this context whatsoever). His claim is mere handwaving.

    The assertion by a later poster that PA doesn’t have finite sets etc is a pointless distraction. PA can code for these things rather routinely, so that’s not the level Perez has failed to deliver on.

    Mark and others have not commented on this proof, so presumably also found it correct.

    An intelligent poster would have concluded that they had not bothered to look at it. I guess that’s not you.

    If this proof is correct, as you all probably know, it contradicts Godel and implies completeness.

    If the proof is correct it also implies the twin prime conjecture. It also provides a very short proof of the four color theorem!

    A more intelligent deduction from a correct PA proof that Goodstein sequences go to zero (something neither you nor Perez is capable of, apparently) is that Paris-Kirby made a mistake. I’ve been through their paper, and Kaye’s textbook treatment. They did not.

  49. #49 David
    March 14, 2010

    Perhaps I’m missing something, and I’d appreciate being shown what….

    If you assume ~P and then prove (~P)&P, that certainly seems to me to prove that ~P cannot be true, as it implies a contradiction. Fair enough.

    But does that say anything at all about the truth of P? (~P) -> (~P)&P is not equivalent to p -> (~P)&P. P could still be true. In fact, it seems to me that if (~P) -> (~P)&P, then that proves P must be true.

    So this whole “internal contradiction” thing doesn’t make any sense to me. What am I missing?

  50. #50 Dan Doel
    March 14, 2010

    @David

    The argument:

    ¬P => … => contradiction, therefore P

    is valid in classical logic because it has P ∨ ¬P as an axiom/rule/whatever (P is either true or false). This allows you to reason that if ¬P is false, then P must be true, because that’s the only way for P ∨ false to be true. Alternately, you can look at it as

    ¬P => … => false

    and P -> false is the definition of ¬P. So the contradiction is a proof of ¬¬P, and we conclude P from not-not-P.

    Those two are equivalent. However, intuitionistic logic doesn’t allow either. So, if you don’t like reasoning from ¬P is false to P is true, then that’s your logic.

    (Although, even in intuitionistic logic, there are certain P for which you can go from ¬¬P => P. For instance if P = ¬Q, we have ¬¬P = ¬¬¬Q, and ¬¬¬Q -> ¬Q is a theorem for all Q. Etc.)

  51. #51 Tony V.
    March 15, 2010

    @48 william emba wrote:
    |If the proof is correct it also implies the twin prime conjecture. It also provides a very short proof of the four color theorem!

    Interesting observation..

    Ideally, one could make a statement of the four color proof simply as:

    Any enclosed area can only be surrounded (bordered) by either an odd number of bordering areas or an even number of bordering areas. Then…If even bordered, 3 colors will suffice; if odd bordered 4 colors at most will be required.
    Then one only need to apply the “universality” implied in PA (or any other such logic) – i.e., that one can translate the zero of one’s numberline to any other point in the universe and the original axioms and symmetry must (necessarily) hold.
    And Presto…four color must be true, even without full demonstration, simply as a universal conservation of parity law. That premise could then be extended to Goldbach, Twin Primes, and perhaps even Riemann Zeta if you wish !
    *********
    The inconsistency ( or rather, source of paradox), at the foundations of most mathematics is the unstated assumption of universality – that symmetries are infinitely translatable – that I can plop my Cartesian numberline down on any table in the universe and it must still be valid.
    These same assumptions (i.e, Copernican doctrine, equivalence principle, etc.) are also a source for many of the infinities that arise in physics and cosmology.
    Perhaps the world would be better off if schoolchildren were not taught that “mathematics is the universal language” – it leads to far too many false hopes.

    There is only one universally valid assumption – Paradox is a necessity, and trying to overcome it is what makes life interesting.

  52. #52 abb3w
    March 15, 2010

    Mark C. Chu-Carroll: Greg Chaitin, who I personally believe is the best mathematician working in the world today, has said that it’s worth at least considering the notion that real numbers don’t really exist, but are rather just an artifact of logic.

    Since I’d fall in that camp, I’d be interested in a citation. (More precisely, I consider “real” numbers a philosophically valid abstract artifact, but one that may not have full expression in the “reality” we experience— and in fact, take the latter as explicit assumption. Doing otherwise leaves Hume’s problem of induction with no apparent resolution, and I prefer a pretense of being able to tell a hawk from a handsaw.)

    Mark C. Chu-Carroll: If Perez’s work is in a non-standard logic, it doesn’t matter. Gödel’s proof still applies: it shows you how to use Peano arithmetic to construct an unprovable statement, demonstrating that the system is incomplete.

    Probably… but I’m not sure what “proof” corresponds to when if you have to express the idea of “proof” itself in a Heyting logic. (While Heyting logic has been waved at me, the person doing so was uninterested in actually teaching anything about it.)

    Mark C. Chu-Carroll: A variant of Cantor’s proof *can* still be used to show that the powerset of the set of computables is larger than the set of computables.

    Provided, of course, you take the standard position and Affirm the Axiom of the Power Set. However, like Choice, the AotPS is independent from the remaining ZF axioms. Taking Powerset Refutation to get rid of larger cardinalities might be philosophically kin to taking Affirmation of Regularity to get rid of sets that contain themselves, or to taking Refutation of Choice to get rid of the assorted bizarre things THAT allows.

    So, if someone is desperate enough to throw out the PowerSet axiom, the question of whether P(Computables) is larger than the Computables is rendered moot — since P(Computables) cannot necessarily be said to “exist” (or in so far as it does, may not necessarily be a “set”), the question is syntatically inadmissible.

    But yes, you’re DEFINITELY dealing with “not standard math” there; and you’re still stuck with Gödel, even throwing out PS to leave Cantor behind.

  53. #53 William Wallace
    March 15, 2010

    As I use math in my career, my interest in it is utilitarian. I do not think much worthwhile comes from treating math as an end unto itself, though I would be interested in hearing if you disagree. I am not advocating that math as a degree program be removed from Universities, but I do know some people who have earned MS degrees in math, but have not applied those degrees in furtherance of math. In general, and this may even be true for you, they work, doing other technical tasks or analysis, using math, yes, but not for its own sake.

    Could you do a post explaining why any of this matters to engineers, computer scientists, database administrators, etc?

  54. #54 Pat Cahalan
    March 15, 2010

    > I consider “real” numbers a philosophically valid
    > abstract artifact, but one that may not have full
    > expression in the “reality” we experience—

    I’d like to know what definition of “reality” you’re using.

    > and in fact, take the latter as explicit assumption.

    Well, if you assume that the derivation of the Planck length is meaningful, then yeah, real numbers have limited expression in “reality” (for some values of “reality”), since any distance less than ~ 1.6×10^-35 doesn’t exist.

    > Doing otherwise leaves Hume’s problem of induction
    > with no apparent resolution, and I prefer a pretense
    > of being able to tell a hawk from a handsaw.

    I have no idea how you got from the previous bit to this. I’m not sure if I’d find the jump fascinating or barking nonsense.

    There is only a problem of induction if you agree with Hume’s two arguments: that the uniformity principle cannot be demonstrated, and that probable reasoning is not logically consistent. I don’t find either to be particularly compelling ontological arguments, I always thought Hume was sort of an idiot.

  55. #55 James Sweet
    March 15, 2010

    Let’s take one nice one, which he’s absolutely explicit about. His proof schema is based on a proof as a sequence of atomic statements, each of which implies the following statement. That’s not the structure of a proof. A proof does have a series of implications leading to a conclusion, but it’s not linear. Proofs are graphs of implications, not lines.

    I am not a mathematician, and in fact I understand maybe 5% of what you say on this blog, if that. (If restricted to refutations of Cantor cranks, I probably understand less than 2%)

    And yet, I caught that problem on the first read-through of your summary of Perez’s argument. I was like, “Wait, I remember doing proofs in high school where Qn was a consequence of, say, Qn-1 and Qn-6 or whatever.”

  56. #56 i-blis
    March 15, 2010

    @52 On Greg Chaitin’s views on real numbers, take a look at How real are real numbers? (for a deeper – and better – leap into his ideas see Meta Math! The Quest for Omega). On that very matter, he owes a lot to Emile Borel’s insights, which is of course a compliment.

  57. #57 James Sweet
    March 15, 2010

    Well, if you assume that the derivation of the Planck length is meaningful, then yeah, real numbers have limited expression in “reality” (for some values of “reality”), since any distance less than ~ 1.6×10^-35 doesn’t exist.

    I could be mistaken, but I think that accepting that distances less than the Plank length don’t exist does not automatically free you from real numbers.

    Consider a point x in a one-dimensional universe. Even if we assume that one cannot meaningfully measure the distance between x and x+lp/2 (because those particles would be separated by less than a Plank length), that doesn’t preclude you from measuring the distance between x and x+3*lp/2.

    Okay, it could mean you could never measure the distance that precisely… but my point is that even if we assume that it is not meaningful to speak of a distance smaller than Plank’s length (a big assumption in and of itself!), that still doesn’t apportion the universe into a discrete 3-dimensional grid.

    Probably a more accurate answer, though deeply unsatisfying, is that at the scale at which the interface between the real numbers and reality comes into play, it’s meaningless to employ existential language. Take the statement “electrons exist”. The statement is trivially true if we parse it as “the system of equations associated with electrons is predictive of observable reality. The statement is trivially false if we parse it as “there exist little spheres that zoom around the nucleus of atoms at incredible speed,” because electrons have no shape; and because the actual behavior of electrons ‘orbiting’ a nucleus, particularly in regards to any sort of notion of ‘position’, does not really correspond to anything that might reasonable be called “zooming”.

    There are probably ways in between that come closer to being accurate, but in the end, anything that goes beyond saying that the equations describe observable reality is going to, by necessity, draw an analogous relationship with something at the macroscopic level.

    Similarly, the statement “reals exist” is trivially true in the sense that our mathematical system employing them is very useful when trying to describe observable reality, but trivially false in the sense that there could never be a measurement or a position or anything that required an irrational number to accurately represent it (by definition: you cannot specify that the tolerance for a given measurement is “plus or minus the first real number that is closer to zero than any rational number”!). Do the reals “exist”? I think that at the level where it would matter, the question is ill-defined.

  58. #58 abb3w
    March 15, 2010

    Pat Cahalan: I’d like to know what definition of “reality” you’re using.

    “Reality” is whatever-the-heck is producing “experience”. (Scientists refer to “experience” by the alternate term “evidence”; however, they are somewhat more restrictive, preferring the math they do to be linear, or at least polynomial or exponential-polynomial. Full blown recursive enumerability makes most scientists flinch.) This includes indirect productions; so (as an example) if superstrings produce electrons, which produce the experience of static electricity, superstrings are also real, just as electrons are.

    Pat Cahalan: Well, if you assume that the derivation of the Planck length is meaningful,

    Probabilistic validity of that derivation ends up being taken as an inference.

    Pat Cahalan: I have no idea how you got from the previous bit to this.

    (doi:10.1109/18.825807). Vitanyi and Li assume RE complexity, and thus a degree zero hypercomputer; however, it’s trivially extensible to programs for any ordinal degree hypercomputer and associated complexity of AH.

    They specifically mention Hume in the paper, but the bulk of the paper is taken up by the math.

    Pat Cahalan: There is only a problem of induction if you agree with Hume’s two arguments: that the uniformity principle cannot be demonstrated, and that probable reasoning is not logically consistent.

    Actually, it’s that probable reasoning has to be formalized. The assumption of RE (or of AH) allow you to take both as an inference. As a bonus, you also get a rigorous expression for Occam’s Razor, and an algorithmic formalizing of Science as philosophical discipline.

    Pat Cahalan: I don’t find either to be particularly compelling ontological arguments

    They aren’t, if you explicitly or implicitly assume AH complexity as a primary premise. One can instead take them directly as premises. (However, one can also take Biblical Inerrancy directly as a premise; that does not make the results convincing or useful.) If it isn’t taken directly, it’s preferable to be able to prove it from other premises. It’s like the Axiom of Choice: you have to either assert it, prove it from something else (equivalent or more powerful; or as a subcase of something more general), or consider cases for both Assertion and Refutation.

    So, if you assume a fully real-set complexity, you start having to deal with the full weirdness of cardinalities higher than Aleph-0 alluded to by Marc — such as the probability of anything that happens being zero, despite the “fact” that it happened. This appears to preclude traditional probabilistic induction (although you might be able to toy around if you extend Kolmogorov probability axioms to hyperreal or surreal probabilities; I’m not sure).

    James Sweet: Even if we assume that one cannot meaningfully measure the distance between x and x+lp/2 (because those particles would be separated by less than a Plank length), that doesn’t preclude you from measuring the distance between x and x+3*lp/2.

    Mathematically true. However, all such computations necessarily only act as a computable multiplier; the computables are countable; and the cross-product of two countably infinite sets is itself a countably infinite set.

  59. #59 william e emba
    March 16, 2010

    Mark Chu-Carroll wrote:

    Greg Chaitin, who I personally believe is the best mathematician working in the world today, …

    So between you and Greg Chaitin, that’s two votes for Greg Chaitin.

    Sheesh. I seriously doubt he’d make the cut for a top 1000 list.

  60. #60 Pat Cahalan
    March 16, 2010

    > “Reality” is whatever-the-heck is producing
    > “experience”.

    (laugh) That’s about the best useful definition I could come up with myself, but I think we can both agree that it’s extremely unsatisfying. In practice (cough, cough), it’s either going to be inconsistent, incomplete, or incorrect, depending upon how you define “experience”.

    > It’s like the Axiom of Choice: you have to either
    > assert it, prove it from something else (equivalent
    > or more powerful; or as a subcase of something more
    > general), or consider cases for both Assertion
    > and Refutation.

    Oh, sure. My problem with Hume is that he threw up his hands and said that he wasn’t comfortable asserting it, but his reasoning always bugged me as a classic case of reductio ad absurdum. “I can’t know for sure, ergo I’ll go the other way and say we have to reject it!” It seems counter-intuitive to decide the case for probabilistic reasoning using binary logic.

    > So, if you assume a fully real-set complexity,
    > you start having to deal with the full weirdness
    > of cardinalities higher than Aleph-0 alluded
    > to by Marc [snip]

    I don’t understand why this is objectionable. It seems to me to be a more agreeable model for real number theory than the converse. Maybe that’s just because I like having my brain tied into a knot.

    You can have a workable formal number theory by throwing out the noncomputables, as Marc pointed out, but I don’t see the value in doing so. Now we’re crossing into that area of metamathematics where people start talking about elegance rather than utility. Maybe I’m just a pie-in-the-sky type.

    > — such as the probability of anything that
    > happens being zero, despite the “fact” that it
    > happened. This appears to preclude traditional
    > probabilistic induction

    I would argue that it instead shows the boundaries of probability theory. I’m perfectly comfortable saying that the probability of randomly choosing any computable number out of the set of reals in a single trial is zero. I don’t even think of it as counterintuitive. The whole, “But that means you’re excluding part of the set as a possible result, ergo you must not be choosing randomly” argument is, to me, a silly objection because it presumes that the original construction is valid.

    How do you propose (from a constructivist standpoint) to design a random number generator that really *does* pick a random real number out of an interval? If the vast majority of reals is noncomputable, good luck with that ;)

    My answer to a former CS major who tried to pull this one on me a couple of weeks ago was to turn it back on him, “Let me put it to you this way. Let us suppose you tell me you have a truly random number generator. Furthermore, you tell this random number generator to produce a real number in the interval (0,1) and when executed, it produces any kind of result. I will state that the probability is 1 that your random number generator is broken. If you want to lay odds, I’ll even let you pick ‘em and the stakes.”

  61. #61 James Sweet
    March 16, 2010

    The way I thought that seeming “paradox” was resolved was by just defining probability 0 as “almost impossible”, not “impossible”. (Similarly, P=1 is “almost certain”)

  62. #62 estraven
    March 19, 2010

    “Greg Chaitin, who I personally believe is the best mathematician working in the world today”

    By looking at his website, I wouldn’t call him a mathematician. Maybe some kind of philosopher.

  63. #63 Larry D'Anna
    March 26, 2010

    lines versus graphs isn’t the real issue here.

    you can allways just take conjunctions to make your graph a line:

    a
    a^b
    a^b^c
    ….

  64. #64 Rodrigo
    March 26, 2010

    Let I complete the Perez set theoretical program.

    “Theorem (for win my abel prize)” No infinite set is non-denumerable.
    “Proof” Let X an infinite non-denumerable set. X has an infinite countable subset, call it A0, now the difference X-A0 is non-denumerable then have again an infinite countable subset, call it A1, we have X=A0 U A1 U Y, where Y is a non denumerable subset of X. Repeating this process we obtain the decomposition of X in a denumerable sequence of disjoint denumerable sets X=A0 U A1 U A2 U … wich is, by a consequence of axiom of choice, denumerable. Then we conclude that X is infinite and non denumerable leads to a contradiction, thus every infinte sets are countable infinite.
    Q.E.D

    Find the mistakes in my “proof” guys (they are so many).

  65. #65 Anonymous
    April 4, 2010

    Actually, I’m not sure that Cantor’s proof is a proof by internal contradiction.

  66. #66 rob
    April 4, 2010

    Just a minor historical point, the Principia Mathematica was finshed a few years before Hilbert’s program started so saying that the program produced it is incorrect.

  67. #67 software development for startups
    April 5, 2010

    The statement “reals exist” is trivially true in the sense that our mathematical system employing them is very useful when trying to describe observable reality. But trivially false in the sense that there could never be a measurement or a position or anything that required an irrational number to accurately represent it.

    The way the seeming “paradox” was resolved was by just defining probability 0 as “almost impossible”, not “impossible”.

    If his “reasoning backward” argument made sense for proofs by “internal contradiction”, would it not make equal sense for proofs by “external contradiction”?

  68. #68 Joshua Zelinsky
    April 6, 2010

    Regarding the proof of Goodstein’s theorem. Even if he had a proof, that wouldn’t actually show that Godel’s theorem was wrong. That would show that ZF is inconsistent or that something was wrong with Paris and Kirby’s proof that Goodstein’s theorem can’t be proven in PA. But this doesn’t say at all that anything is wrong Godel’s theorem which is not necessary for the proof of the undecidability of Goodstein’s theorem.

  69. #69 John Ryskamp
    April 16, 2010

    You think you know what you are talking about, but you don’t. You are very, VERY much behind research into the history of set theory. If you knew what was going on, you would never make a ridiculous statement that toward the beginning of the 20th century, mathematics was in a “confused” state. YOU are the one who is in a confused state. What a ridiculous propagandist you are. How humbled and mortified you will be once you read A. Garciadiego’s BERTRAND RUSSELL AND THE ORIGINS OF THE SET-THEORETIC ‘PARADOXES.’ And check out how even Grattan-Guinness is a scathing critique of your heroes!

    Ha ha! Even Feferman’s editors critize Godel in the new edition of his works! How out of touch CAN you be? Clown!

    Ryskamp, John Henry, Paradox, Natural Mathematics, Relativity and Twentieth-Century Ideas (June 17, 2008). Available at SSRN: http://ssrn.com/abstract=897085

  70. #70 cronos telfer
    April 28, 2010

    This is from a UNSW web page:
    Set Theory: Should You Believe?

    N J Wildberger

    School of Maths UNSW Sydney NSW 2052 Australia

    webpages: http://web.maths.unsw.edu.au/~norman

    “I don’t know what predominates in Cantor’s theory – philosophy or theology, but I am sure that there is no mathematics there.” (Kronecker)

    “…classical logic was abstracted from the mathematics of finite sets and their subsets…Forgetful of this limited origin, one afterwards mistook that logic for something above and prior to all mathematics, and finally applied it, without justification, to the mathematics of infinite sets. This is the Fall and original sin of [Cantor's] set theory …” (Weyl)

    8. Axiom of Foundation: Every nonempty set has a minimal element, that is one which does not contain another in the set.

    9. Axiom of Choice: Every family of nonempty sets has a choice function, namely a function which assigns to each of the sets one of its elements.

    All completely clear? This sorry list of assertions is, according to the majority of mathematicians, the proper foundation for set theory and modern mathematics! Incredible!

    The `Axioms’ are first of all unintelligible unless you are already a trained mathematician. Perhaps you disagree? Then I suggest an experiment—inflict this list on a random sample of educated non-mathematicians and see if they buy—or even understand—any of it. However even to a mathematician it should be obvious that these statements are awash with difficulties. What is a property? What is a parameter? What is a function? What is a family of sets? Where is the explanation of what all the symbols mean, if indeed they have any meaning? How many further assumptions are hidden behind the syntax and logical conventions assumed by these postulates?

    And Axiom 6: There is an infinite set!? How in heavens did this one sneak in here? One of the whole points of Russell’s critique is that one must be extremely careful about what the words `infinite set’ denote. One might as well declare that: There is an all-seeing Leprechaun! or There is an unstoppable mouse!

    I’m not stating my own views. (I haven’t studied maths seriously for more than 40 years). The above is from the thoughts of an associate professor of maths at UNSW.

    Richard Mullins

  71. #71 AK-47
    June 3, 2010

    Dear Mark, you write:
    “Greg Chaitin, who I personally believe is the best mathematician working in the world today…”
    Considering that Deligne, Tao, Ngo, Perelman, Serre,Voevodski,Suslin, Manin, Faltings, Wiles, Lafforgue, etc. are also mathematicians “working in the world today” I’d be quite interested to learn what makes you believe
    that Chaitin is better than them.