World's shortest explanation of Gödel's theorem

I'm sure that Smullyan's not confused. In fact, his _Goedel's Incompleteness Theorems_ is the most lucid and brillian exposition (a mathematical and rigorous one) of the theorems I've ever seen. I absolutely adore that book. However, I also doubt that Smullyan presented the NPR* story as a proof of Goedel's theorem. He probably said something to the effect of it being a good demonstration of the relevant issues. And that's probably right.

I hesitate to say this, because it sounds harsh, but your comment is a heap of confusion. You're using words like "first order", "second order", "axiom system", "true statements", "refuted", with confused understanding of what they mean. They all have clear technical meanings.

If you're interested in this stuff and can stomach mathematical rigor, I highly recommend Enderton's _A Mathematical Introduction to Logic_ for mathematical logic in general, and Smullyan's own _Goedel's Incompleteness Theorems_ for this topic.

Now, to back my harsh words a little.

An axiomatic system, in the context of Goedel's theorems, is a bunch of axioms with some inference rules. Axioms are statements that are automatically taken as proved, while inference rules allow one to infer more proved statements from some already proved statements. Given an axiomatic system, you can define a proof of statement X to be a sequence of statements that starts with axioms and always goes through inference rules until it reaches X.

All of the above is purely syntactic, meaning it has to do with rules that govern how symbols are written on the paper, and there's no need for any interpretation of what the symbols mean. You could have an axiomatic system where statements would be Tarot cards, axioms some particular cards, and inference rules would govern which card you can place next to ones you already have. It'd be a silly axiomatic system, but it would be one, and you wouldn't need to know anything about what the cards "mean". Similarly, you can write down an axiomatic system with statements that use symbols like "0", "1", "+", "x" "forall", without caring what it means for a statement to be true or false.

Any axiomatic system really comes with a _logic_ in the background: the logic specifies what kinds of statements you're allowed to write down. The most important and frequently used kind is first-order logic, which lets you use constant symbols like "0", "1", function symbols like "+" (again, as purely abstract marks-on-paper without caring what their meaning is), equality sign "=", variables like "x", "y" etc., and crucially quantifiers "for all" and "exists" that let you say things like "for all x, something-that-depends-on-x".

Second-order logic, in addition, also lets you quantify over sets or functions. In first-order logic, you can only have a few fixed symbols like + and write some statements about them, but in second-order logic you can express statements about any possible function, like, say, "for every function F on two variables, F(x,y) = F(y,x)". This kind of statement is invalid in first-order logic, for some good reasons. Not "true" or "false", just impossible to write down in the first place.

This is why when you say "The Incompleteness Theorem shows that no first order axiomatic system is powerful enough to encapsulate all true statements in the second order Peano axioms", this is nonsense, because a first-order axiomatic system cannot prove statements in a second-order system, in general. They come from different logics. Second-order systems contain statements that first-order systems can't express at all, much less prove.

Now, independently of defining an axiomatic system, we can also define a meaning - "semantics" - for any statement in a particular logic. For example, we can decide, with good reason, that the symbol "0" actually stands for the number 0, the symbol "+" stands for the operation of addition, and so on. The statement "2+2=5" will then not be just a string of five meaningless marks on paper, it will also have a meaning and a truth value (which is false, in this case). We can decide what it means for the more complex statements like "for all x ..." to be true - appropriately enough, it means that if you try to substitute any number for x inside the "...", you'll always get a true statement. Now every statement in our logic is either true or false, although for many of them it's difficult to know which is the case.

Going back to axiomatic systems, we remember that they have axioms and inference rules. Typically, some of the axioms and all of the inference rules are called "logical" and are independent of the particular math structure we're trying to investigate (natural numbers, in this case). The logical axioms and inference rules say things like "x=x" and "if you proved "for all x, ...", you can also count as proved any version of ... in which you substituted something for x". We regard them as intuitively, tautologically true. The other, remaining non-logical axioms say things like "a+0=a" and "every number except 0 has a predecessor". They could be for example the Peano axioms for natural numbers.

Godel's Completeness Theorem has absolutely nothing to do with his Incompleteness Theorem, and the "completeness" it talks about is very different from the "incompleteness" the other theorem talks about. Goedel's Completeness Theorem really says something important about the usual bunch of logical axioms and inference rules, the one that form the backbone of pretty much every first-order axiomatic system we study. It says that they're strong enough to prove anything that must always be true in any semantics. For example (trivial example), no matter how we define what the symbol '0' means, it will always be true that "for any x, if x=0, then 0=x". All tautologies like that are better be provable with logical axioms alone, and Goedel's Completeness Theorem ensures that they are. The fact that we have a Goedel's Completeness Theorem is really what allows us to confidently use first-order logic as a conceptual basis for all mathematics. It tells us that axiomatic systems for first-order logic are complete in the sense of "strong enough to prove all tautologies". But it has nothing to do with the Incompleteness Theorems, which are about "complete" in the sense of "strong enough to prove every sentence or its negation".

So your second paragraph "In fact, his Completeness Theorem proves the opposite of what you claim" is nonsense, too. It's true that you can make up a trivial example of a complete system just by declaring all true statements to be axioms. But that fact has nothing to do with Goedel's Completeness Theorem. The reason that trivial example is inadequate is that, as you mention, it's not manageable - you can't determine what's an axiom and what isn't.

Finally, your third paragraph is also wrong. To refute means to prove the negation of. If X cannot be refuted, that means you can't prove not-X. From this it only follows that you can prove X if you have a complete axiomatic system. Since normally, in fact, you don't (by virtue of Goedel's incompleteness theorems), it doesn't follow at all. Now what's true and may be confusing you is that there are certain simple kinds of statements for which this is true, because they're very simple. You can prove that e.g. the Peano Axioms are powerful enough to prove any true statement, or refute any false statement, of a particular simple kind. But not in any statement in general - that'd contradict the Goedel's incompleteness theorems.

An axiomatic system is complete if it can either prove or refute every possible statement. "Refute" means "prove the negation of". So a complete axiomatic system is as powerful as possible w/o being inconsistent (if you prove both X and not-X, you're inconsistent).

To say that a system is incomplete is to say that there are things it can neither prove nor refute. These things could be true or false, no matter. In fact, if X is one such "undecidable" statement, not-X is also one, and one of them has to be true, the other false. But it doesn't matter for the definition of "completeness".

You could have axiomatic systems that are built on axioms some of which are known to be false, and yet they're consistent. These systems could be complete or incomplete.

Think about "what's provable" and "what's true" as completely independent layers of information you can have about statements. It's very good when they partially coincide, for example, when all the things you can prove are in fact true things (which will happen if you start out from true axioms). But they don't have to. They could fail to coincide at all.

Now for the layer of information "what's true" there is automatically a very nice property that either X or not-X is true, for any statement X. You get that for free just from the nature of what truth/falseness are.

For the layer of information "what's provable" it's not at all guaranteed that either X or not-X is provable for any statement X (this is, again, what "completeness" means). If your axiomatic system is very weak, it can only prove a few paltry statements, and it will not nearly be complete, there'll be a huge universe of statements out there that it'll be too stupid to prove anything interesting about, either about X or about not-X. But you could hope that as you add more and more strong, powerful axioms to your system (and nevermind if they're true or not! it's intuitively easy to think of them as true, but they don't have to be), you get to be able to prove more and more stuff, and eventually you'll have a complete system. Goedel's result is the hugely surprising fact that you can't: once your system is powerful enough, and yet manageable (you can't just pour everything in as axioms) it'll have to be incomplete, because it's powerful enough to formalize statements about itself, and that kind of self-awareness will have to be (because of the reasons similar to the Liar's Paradox) an essential check on what it can prove.

Well, let's agree to disagree on the recommendation of Manin's book. I think it's confusing, rambling and often downright unhelpful.

The reason Godel's theorem is proved as (little other than) a corollary to Tarski's in Manin's book is that Manin presents a weaker, semantic version of Godel's theorem that is indeed little other than a corollary to Tarski's. See Manin's discussion of "Godel's argument" and particularly step (c) on p.255 of his book. Manin explains that Godel's proof doesn't use the assumption that D is a subset of T (all provable statements are true), but that he, Manin, doesn't think it's important to care about that, so he presents the theorem this way. In the form Godel proved it, the theorem doesn't require any semantic assumptions.

Manin is entitled to his own spin on what is and isn't important about the Incompleteness Theorem, but it should be apparent to you that his presentation uses an assumption that Godel's theorem in its general form doesn't require. It's interesting (where by interesting I mean "weird, and goes toward explaining my opinion of Manin's book") that Manin nowhere even deigns to mention Godel's Second incompleteness theorem, the one about axiomatic systems being unable to prove their own consistency. Now if you were to take up a better book than Manin's, say Smullyan's Godel's Incompleteness Theorems, and study the proof of the second incompleteness theorem, you'd find out that its proof requires a syntactic proof of the first theorem, the proof that Manin says isn't important. This is because proving the second theorem entails formalizing the proof of the first theorem inside the axiomatic system itself, and you can't do that with a proof that uses semantic arguments and talks about true and false theorems (why? because of Tarski's undefinability of truth!). Think of that what you will.

This is only approximately true. What really is a straightforward formalized version of the liar paradox is Tarski's undefinability theorem, which is what's demonstrated in the blogpost.

Goedel's incompleteness sentence is more like inspired by the liar sentence rather than being its formalization; and the proof of Goedel's incompleteness is much more challenging than the simple true->false->true bounce of the liar paradox.

English is my second language, and until a few years ago I wasn't even aware of the original usage, while I'd seen the "misuse" on a regular basis.

I don't think I've actually ever seen it used in the original usage "in the wild", as opposed to in the posts of pedants complaining about people using it wrongly.

Cribbing from this book:

http://books.google.com/books?id=71pK8Zz9Dd8C&printsec=f...

"Since the natural numbers form a subset of the real numbers, it may seem odd that the theory of real numbers can be complete when the theory of the natural numbers is incomplete. The incompleteness of the theory of the natural numbers does not carry over to the theory of the real numbers because even though every natural number is also a real number, we cannot define the natural numbers as a subset of the real numbers [...]

How would we ordinarily define the natural numbers as a subset of the real numbers? The real numbers 0 and 1 can be identified with the corresponding natural numbers, and using addition of real numbers we get the natural numbers as the subset of the real numbers containing 0, 1, 1+1, 1+1+1, and so on. However, this "and so on" cannot be expressed in the language of the theory of real numbers [because it requires the notion of sets, a second-order concept outside of the theory]."

Your reasoning is correct, so it means that integers are not definable inside "real arithmetic".

http://en.wikipedia.org/wiki/Real-closed_field

If you don't believe this, try writing down a formula in the language of this theory that says "x is an integer".

Ultimately, the issue is that the first-order theory of real closed fields contains no axiom approaching the induction scheme of PA in power.

Well, leave out succession and you get the reals, which are still complex enough (no pun intended) to offer hours of fun.