I’ve mentioned Gödel’s incompleteness theorems many times on this blog, but I’ve never actually written about them in detail. I was asking, on twitter, for topics that readers would be interested in, and one thing that came up is actually go through the proof of incompleteness. I’m happy to take the time to do that incompleteness is one of the most beautiful and profound proofs that I’ve ever seen.
It takes a fair bit of effort though, so it’s going to take a couple of posts just to get through the preliminaries. What I’m going to do is work with this translation of the original paper where Gödel published his first incompleteness proof. Before we can get to the actual proof, we need to learn a bit about the particular kind of logic that he used in his proof.
The story of incompleteness is really pretty interesting. In the late 19th and early 20th centuries, mathematicians started to get really interested in formal foundations. Why, exactly, this happened is somewhat of a debate, but the story I find most likely is that it’s a result of Cantor and his naive set theory.
Set theory came along, and it seemed like such a great idea. It seems incredibly simple, and it makes many proofs in many different subject areas appear to be really simple. But there’s a huge problem: it’s not consistent.
The problem is what’s come to be known as Russell’s paradox. I’ve explained Russell’s paradox a bunch of times on the blog. For this post, I’m going to do it a bit differently. As part of my prep for this series of posts, I’ve been reading the book Gödel’s Proof
If you think about the set of all sets, you can partition it into two non-overlapping subsets. There’s a subset of normal sets, and a class of abnormal sets. What makes a set abnormal is that it’s self-referential – an abnormal set contains itself as a member.
So considered the set of all normal sets. Is it, itself, a normal set?
The answer is: argh! Because if the set of all normal sets is normal, then it must be a member of itself. But if it’s a member of itself, it can’t be normal. Similarly, if you start off saying that the set of all normal sets isn’t normal, then by definition, it is normal. No matter what you do, you’re screwed.
What Russell’s paradox did was show that there was a foundational problem in math. You could develop what appeared to be a valid mathematicial structure and theory, only to later discover that all the work you did was garbage, because there was some non-obvious fundamental inconsistency in how you defined it. But the way that foundations were treated simple wasn’t strong or formal enough to be able to detect, right up front, whether you’d hard-wired an inconsistency into your theory. So foundations had to change, to prevent another Cantor incident.
So, eventually, along came two mathematicians, Russell and Whitehead, and they created an amazing piece of work called the Principia Mathematica. The principia was supposed to be an ideal, perfect mathematical foundation. The Principia was supposed to have two key properties: it was supposed to consistent, and it was supposed to be complete.
- Consistent meant that the statement would not allow any inconsistencies of any kind. If you used the logic and the foundantions of the Principia, you couldn’t even say anything like Russell’s paradox: you couldn’t even write it as a valid statement.
- Complete meant that every true statement was provably true, every false statement was provably false, and every statement was either true or false.
A big part of how it did this was by creating a very strict stratification of logic. You could reason about a specific number, using level-0 statements. You could reason about sets of numbers using level-1 statements. And you could reason about sets of sets of numbers using level-2 statements. In a level-1 statement, you could make meta-statements about level-0 properties, but you couldn’t reason about level-1. In level-2, you could reason about level-1 and level-0, but not about level-2. This meant that you couldn’t make a set like the set of normal sets – because that set is formed using a predicate – and when you’re forming a set like “the set of proper sets”, the sets you can reason about are a level below you. You can form a level-1 set using a level-1 statement about level-0 objects. But you can’t make a level-1 statement about level-1 objects! So self-referential systems would be completely impossible in the Principia’s logic.
As a modern student of math, it’s hard to understand what a profound thing they were trying to do. We’ve grown up learning math long after incompleteness became a well-known fact of life. (I read “Gödel Escher Bach” when I was a college freshman – well before I took any particularly deep math classes – so I knew about incompleteness before I knew enough to really understand what completeness woud have meant!) The principia would have been the perfection of math, a final ultimate perfect system. There would have been nothing that we couldn’t prove, nothing in math that we couldn’t know!
What Gödel did was show that using the Principia’s own system, and it’s own syntax, that not only was the principia itself flawed, but that any possible effort like the principia would inevitably be flawed!
With the incompleteness proof, Gödel showed that even in the Principia, even with all of the effort that it made to strictly separate the levels of reasoning, that he could form self-referential statements, and that those self-referential statements were both true and unprovable.
The way that he did it was simply brilliant. The proof was a sequence of steps.
- He showed that using Peano arithmetic – that is, the basic definition of natural numbers and natural number arithmetic – that you could take any principia-logic statement, and uniquely encode it as a number – so that every logical statement was a number, and ever number was a specific logical statement.
- Then using that basic mechanic, he showed how you could take any property defined by a predicate in the principia’s logic, and encode it as a arithmetic property of the numbers. So a number encoded a statement, and the property of a number could be encoded arithmetically. A number, then, could be both a statement, and a definition of an arithmetic property of a stament, and a logical description of a logical property of a statement – all at once!
- Using that encoding, then – which can be formed for any logic that can express Peano arithmetic – he showed that you could form a self-referential statement: a number that was a statement about numbers including the number that was statement itself. And more, it could encode a meta-property of the statement in a way that was both true, and also unprovable: he showed how to create a logical property “There is no proof of this statement”, which applied to its own numeric encoding. So the statement said, about itself, that it couldn’t be proven.
The existence of that statement meant that the Principia – and any similar system! – was incomplete. Completeness means that every true statement is provably true within the system. But the statement encodes the fact that it cannot be proven. If you could prove it, the system would be inconsistent. If you can’t, it’s consistent, but incomplete.
We’re going to go through all of that in detail. But to do that in a way where we can really understand it, we’re going to need to start by looking at the logic used by the Principia. Then we’ll look at how to encode Principia-logical statements as natural numbers using a technique called Gödel numbering, and how to express predicates numerically. And then, finally, we can look at how you can form the classic Gödel statement that shows that the Principia’s system of logic is incomplete.
I think I’ve been subscribed to your RSS for years just to wait for this post. Thanks!
BTW, I think I found a typo: “A big part of how it did this was being creating a very strict stratification of logic.”
Fixed, thanks for catching it!
You have a small typo at the end of the first sentence in the third step of how Gödel prove the incompleteness. The sentence starting “Using that encoding…” appears to be missing a work (probably “the”) just before “…statement itself.”
I have to say I’d be more worried about a logical/theoretical system that allowed me to “prove” falsehoods than one than didn’t encompass all possible truths, personally.
I’ve always loved this ONE-page, MONOsyllabic explanation of Godel’s Second Incompleteness Theorem that creative logician George Boolos once wrote:
http://tinyurl.com/cgexvsy
or pdf here:
http://www2.kenyon.edu/Depts/Math/Milnikel/boolos-godel.pdf
…just wonderful!
Thank you so much for this. 🙂
so that every logical statement was a number, and ever number was a specific logical statement.
So it’s impossible for a positive integer to decode into gibberish, like “1+++1=<"?
As I’ll show, it’s possible to define a set of numeric encoding rules that are based on the grammar of the logic. The encoding isn’t a sequence of tokens – it’s more like an encoding of a parse tree. So no, you can’t encode syntactically invalid gibberish.
I’m sort of surprised at that, since every other description of Gödel-numbering I’ve seen allows for exactly that sort of gibberish.
The thing is, the rules of syntax and construction themselves also can be encoded in terms of arithmetic, so the numbers corresponding to well-formed formulas can be recognized arithmetically.
Just another longtime RSS subscriber grateful for this post and eagerly awaiting the rest. Mahalo!
Very, very nice and clear explanation. Little bit of a nit-pick: Russell and Whitehead never claimed Principia should be complete. In particular, Russell said the Axiom of Infinity should be neither provable nor disprovable, as it’s a question for physics, not logic: if the universe is finite in size, and if there is a true smallest indivisible constituent of matter, then the Axiom of Infinity is false. It was Hilbert who later defined consistency and completeness and emphasised their importance.
I have a question: what about the message placed on the website http://plus.maths.org/content/goumldel-and-limits-logic ? There is the information that Teodor J. Stepien and Lukasz T. Stepien constructed a proof of the consistency of Peano’s Arithmetic System and in this proof only the axioms of first-order logic and the axioms of Peano’s Arithmetic System were used. So, as it has been written on http://plus.maths.org/content/goumldel-and-limits-logic , “from the construction of this proof, it follows that Gödel’s Second Incompleteness Theorem is invalid.”
They presented a sketch of this proof at the Conference “Logic Colloquium 2009” in Sofia (Bulgaria) in 2009. The abstract of their talk was published in “The Bulletin of Symbolic Logic”: T. J. Stepien and L. T. Stepien, Bull. Symb. Logic 16, No. 1, 132 (2010). URL:
http://www.math.ucla.edu/~asl/bsl/1601/1601-004.ps .
As far as I can tell, the actual proof described there isn’t published anywhere. The abstract is not enough to judge.
But just from the title: Gödel didn’t show that Peano arithmetic + first order logic is inconsistent – it shows that it’s incomplete. Proving the consistency of the system doesn’t refute Gödel. Proving completeness would.
@MarkCC
Part I.
Well, it must be reminded that there are TWO Gödel’s Incompleteness Theorems and one should distinguish them.
FIRST Gödel s Theorem: if Peano’s Arithmetic is consistent, then Peano’s Arithmetic is incomplete. So, you meant this theorem.
SECOND Gödel ‘s Theorem: the consistency of Peano’s Arithmetic cannot be proved using only the axioms of the first-order Logic and the axioms of Peano’s Arithmetic System.
@MarkCC
Part II
As one can read in the mentioned message, placed on the website http://plus.maths.org/content/goumldel-and-limits-logic , the result of: T. J. Stepien and L. T. Stepien (Bull. Symb. Logic vol. 16, No. 1, 132 (2010), (URL: http://www.math.ucla.edu/~asl/bsl/1601/1601-004.ps) is the following: the consistency of Peano’s Arithmetic System can be proved using only the axioms of the first-order logic and the axioms of Peano’s Arithmetic System. Thus, in short: the consistency of Peano’s Arithmetic System is provable in Peano’s Arithmetic System.
Hence, the following inferences arise:
I. Peano’s Arithmetic is incomplete.
Proof. By the First Gödel’s Theorem and by the result (mentioned above) of T. J. Stepien and L. T. Stepien.
II. Second Gödel’s Incompletemness Theorem is invalid.
Proof. By the result (mentioned above) of T. J. Stepien and L. T. Stepien.
Then why do the slides for that talk open with the overview “In this talk we establish that Peano’s Arithmetic System is consistent in the traditional sense and that Peano’s Arithmetic System is structurally incomplete.” and conclude by proving that Peano Arithmetic is incomplete which surely is consistent with Gödel’s Incompleteness Theorem?
http://lc2009.fmi.uni-sofia.bg/contributedslides/Stepien,%20Stepien.pdf
@Jim White
Well, I am not sure what you have meant, by asking your question. So, one can only repeat that as it follows from the slides, cited by you, T. J. Stepien and L. T. Stepien proved that:
1. Peano’s Arithmetic System is traditionally consistent
2. Peano’s Airthmetic System is structurally incomplete.
Comments:
ad. 1. As far as the point 1 is concerned, as T. J. Stepien and L. T. Stepien have claimed, in their proof of consistency of Peano’s Arithmetic System only the axioms of first-order logic and the axioms of Peano’s Arithmetic System have been applied. Therefore, from the construction of their proof of consistency of Peano’s Arithmetic System, it follows that Goedel’s Second Incompleteness Theorem is invalid.
ad. 2. At first, it should be mentioned that for introducing of the notion of structural completeness, the notion of structural rule is necessary. As I know, the notion of structural rule was introduced by J. Łoś and R. Suszko in 1958. In 1971 W. Pogorzelski introduced the notion of structural completeness. Briefly, there is proved very well-known theorem that each complete logical system is structurally complete, but inverse theorem does not hold. As one can read in the slides of the talk of T. J. Stepien and L. T. Stepien, they proved that Peano’s Arithmetic System is structurally incomplete.
Referring to my previous message here, I write that in the paper: T. J. Stępień, Ł. T. Stępień, „On the Consistency of the Arithmetic System”, Journal of Mathematics and System Science, vol. 7, 43 (2017), arXiv:1803.11072 , a full proof of the consistency of the Arithmetic System has been published. This proof has been done within this Arithmetic System.
Yes! Since dm’s ( = diagonal methods) can be refuted by dm d’s ( = diagonal methods disproofs/disqualifications), that thesis must be correct. I was waiting for such a one!
Goedel has been refuted on that. So,
Complete (PA). ⇔ Consistent (PA). .
And now, the consequent has been proved. Thus, the antecedent has, too.
I was partly wrong again: that thesis does conclude that PA is incomplete, which is false. But by the above argument, that also can be falsified.
Re-correction: The Goedel denial means that “Complete (PA) & Consistent (PA).” with or without that thesis.