Drawing Blanks

Premature Optimization is a Prerequisite for Success

Gödel-Penrose-Franzen: an “eternal golden tree”

with 6 comments

Popular texts which describe or exploit Gödel’s Theorems are full of inaccuracies. I’d like to describe one out of many widespread erroneous claims related to Gödel’s Theorems. Not that it’s a particularly important one, but its content is purely mathematical (as opposed to philosophical), and it’s somewhat non-trivial.

The sentence Con(PA) (that means “Peano Arithmetic is consistent”) is proved to be undecidable in PA. So we can add either Con(PA) or its negation ~Con(PA) to Peano Arithmetic as an axiom and obtain new consistent theories. So far so good. “Let’s keep adding axioms stating consistency or inconsistency of the theory itself to those new theories” – the authors say – “and we can build an infinite tree of consistent theories”.

That is wrong.

Consider the theory PA = PA + ~Con(PA). It is consistent, and it proves that PA is inconsistent. Let’s add the axiom Con(PA) to PA :

PA-+ = PA + Con(PA).

Is PA-+ consistent? No. It can prove both Con(PA) and ~Con(PA). It proves ~Con(PA) because PA itself proves ~Con(PA). Because it proves ~Con(PA):

PA |- ~Con(PA)  –>   PA |- ~Con(PA)  ->  PA-+ |- ~Con(PA)

Confused? Let’s go back to PA. It proves that a part of it (PA) is inconsistent. So it proves its own inconsistency. But didn’t I say that it is consistent? Sure it is consistent. But it is unsound – it proves a falsehood.

But what about Gödel’s 2nd Theorem? Doesn’t it guarantee that a consistent theory can’t prove/disprove own consistency? Well, not quite. In order to ensure that the theory T + Con(T) is consistent, it is not enough to assume that T is consistent. We need to require some stronger conditions. Without going into details (omega-consistency or 1-consistency),  I’ll just say that the semantic property of soundness (not proving any falsehoods) is a sufficient condition. The 2nd Theorem is full of nuances. It is not a simple consequence of the 1st Theorem, as many popular books present it. In essence, the 2nd Theorem relies on the ability of Peano Arithmetic to prove (formally, syntactically, on its own) the equivalence between the Con sentence and the Gödel sentence G. And that is a very subtle matter.

So you can’t really build an “infinite tree of consistent theories” by keeping adding Con and ~Con. You can only build some infinite chains.

It wasn’t a surprise for me to see the above described fallacy in Roger Penrose’s “Shadows of the Mind”. Penrose plays with logic in order to justify his philosophical ideas which are indeed entertaining.

But I was unpleasantly surprised to encounter it in Torkel Franzen’s brilliant “…Incomplete Guide…”. If you don’t believe me, here it is: http://www.amazon.com/Godels-Theorem-Incomplete-Guide-Abuse/dp/1568812388/ (highly recommended), 2.8, page 52, last paragraph. 😦 😦

“Hero gets model” – anagram of “Godel’s theorem”, via Xworder.

Advertisements

Written by bbzippo

12/22/2009 at 6:41 am

Posted in math

6 Responses

Subscribe to comments with RSS.

  1. Hi Zippo,

    You seem to have a firm grasp of what’s going on here, so I’d like to run something by you.

    I’ve often wondered if we could start with a suitable theory, say, PA, and obtain an endlessly branching tree of consistant theories by adding A to one branch and ~A to another branch, for some statement A independent of PA.

    I guess only one of the branches will describe reality, while other branches might describe theories of alternate realities. Compare Euclidian and non-Euclidian geometries.

    Lastly, since it is apparently difficult to find candidates for new axioms, we might look at removing or altering some existing axioms of PA to reveal some of this tree structure.

    Does this make sense? Or am I misinterpreting something?

    Happy Holidays,
    -Chris

    navaburo

    12/22/2011 at 1:34 am

    • Hi Chris and thanks for your interest.

      I’m not prepared to discuss the “reality vs alternative reality” subject in details. Any consistent theory has a model. So it describes some reality. For some theories we have a standard model in our head, so we tend to name any other model “an alternative reality”. And some theories are specifically designed to describe a vast number of realities. You can find many examples in algebra: “group”, “vector space” etc. They are extremely useful since they derive properties which hold in so many applied “realities”.

      Regarding “endlessly branching trees”, we need to be cautious. This is exactly what I warn about in this post: one cannot bulid an endlessly branching tree by keeping adding the Goedel statement and its negation. You’ll get two consistent theories, but then you may run into a trouble. Consistency is not a very strong condition. Consistent theories may lie. (You may want to check out this post:
      https://bbzippo.wordpress.com/2011/03/09/consistency-and-soundness/ ). And if you attempt to extend a theory that lies (an unsound theory) you may run into a contradiction.

      Another common misconception is that in order for the theory to have multiple models it has to be incomplete, so you can add an independent formula as an axiom. But you can simply extend theories by adding new symbols, as I demonstrated here: https://bbzippo.wordpress.com/2011/03/02/from-compactness-to-non-standard-models/

      Another cool alternative model to check out is the non-standard calculus (hyperreal numbers).

      Happy Holidays to you too.

      bbzippo

      12/22/2011 at 3:39 am

  2. This is a really interesting, subtle post. I think I was taught this fallacy at uni. Either that, or I just assumed it.

    I’m curious to what extent it would be interesting to extend the PA axiom scheme by adding more and more Godel sentences for successive theories. I guess you can do it for any recursive order type, but would the resulting systems be interesting? ie could one prove anything extra of interest that’s not provable in PA? Eg, the strengthened finite Ramsey Theorem (which implies Con(PA)). My guess is ‘no’.

    Ian

    07/06/2012 at 7:58 pm

    • Thanks for your interest. Infinitely extending PA is indeed interesting. It was studied in depth by Turing and Feferman.
      I don’t have a good understanding of this subject, but I know that you run into some curios things when you attempt to build extensions for ordinals beyond omega. Thing is, you no longer have a unique canonical enumeration of your set of axioms, and need to choose a particular ordinal notation in order to define your procedure of proof. Apparently, the “logical content” of the theory will strongly depend on the choice of enumeration. What the theory can and cannot prove will not only depend on its axiom set, but also on the procedure of resolving that set. So the very notion of proof becomes kind of relative. I believe that by choosing a “proof machine” (ordinal notation) you can make you theory able to prove pretty much any arithmetic truth.
      Can’t we then express the proof predicate in the theory, and make the theory prove own consistency? My understanding is yes, that’s what Feferman did in his “Arithmetization of metamathematics in a general setting”. Problem is, when we formalize a proof predicate of such power, we can no longer satisfy all Hilbert-Bernays conditions. Since those conditions are necessary for Goedel’s Second theorem, that theorem is not violated.

      bbzippo

      07/07/2012 at 5:02 pm

      • That certainly is interesting! Your response prompted me to do some googling which turned up this nice summary by Feferman of Turing’s work on “ordinal logics” and Feferman’s own work building on that:

        http://www.ams.org/notices/200610/fea-feferman.pdf

        I find the amount of extra strength that can be added in this way remarkable.

        Ian

        07/09/2012 at 6:44 pm

  3. Ian, thanks a lot for the link to Feferman’s paper. I haven’t read it before.

    bbzippo

    07/10/2012 at 1:54 am


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: