Gödel-Penrose-Franzen: an “eternal golden tree”
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.