Following the derail a little further...while you got my vote for the pedantipoint, the misuse of "beg the question" is so pervasive that I've given up. It means what people use it to mean, now. We probably need a new name for the logical fallacy, unless lumping it into circular reasoning is sufficient.
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.
I once told people the correct definition of "begs", and they refused to believe me, and thought I was wrong. To them begs means: raises a very obvious question.
So it's over, "begs" has a new meaning, and complaining about it is pointless.
This includes some surprisingly complicated systems, like real (as opposed to integer) arithmetic.
Real arithmetic is not enough to express integer arithmetic?
I suppose it all boils down to how you define "arithmetic", but what is it that the integers have that the reals lack under the relevant definition? I would think that real arithmetic by any reasonable definition would give you enough tools to check whether a number was an integer, and in that case, doesn't it necessarily contain integer arithmetic as a subset?
"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]."
The system need be no more complex than first-order Peano arithmetic, which is the Peano axioms (reflexivity, transitivity, succession, etc.) combined with the concept of induction.
To construct the Gödel number (a part of the proof) requires use of an arithmetic that can express addition and multiplication. If any one of them is missing, the system can be shown to be complete.
Not quite; this is a liar's paradox. the Gödel's sentence deals with "provability", not "truth". (see Tarski's undefinability theorem if you wonder why it matters)
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.
Wow, that was a disappointment. I've always thought of Gödel's incompleteness theorem as something so arcane that I'd never understood it. Now it turns out to be both trivial and really similar to the Halting problem.
This isn't a proof of Goedel's incompleteness theorem. It's a demonstration of Tarski's undefinability theorem. Goedel's theorem is far stronger and more difficult to prove.
The confusion between the two is widespread.
Goedel's first incompleteness theorem doesn't talk about "true" or "false" statements at all. Technically speaking, it is entirely syntactic, not semantic. It says that in any sufficiently complex axiom system there will be statements that it can neither prove nor refute, "undecidable" statements. The notions of "prove", "refute", "axiom", "undecidable" do not require any definition of "true" or "false".
My guess is that Raymond Smullyan is not confused about this. The explanation isn't presented as proof, it's an explanation of the theorem and its consequences.
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 believe you are incorrect in your last paragraph. The Incompleteness Theorem shows that no first order axiomatic system is powerful enough to encapsulate all true statements in the second order Peano axioms for the natural numbers.
In fact, his Completeness Theorem proves the opposite of what you claim. If you use as your axiom system all true statements of the model you are working in you will have a complete axiom system. All true statements will be trivially provable. The problem with this is that one will have a hard time determining if a given statement is an axiom or not.
If a statement can not be refuted - meaning no counterexample exists - then this is a proof that it is true.
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...
You are confused by the implications and meanings of the results of Godel.
There are two (popular) axiom systems of the natural numbers. Both are from Peano. One system is first order and the other is second order. The second order system is not recursively enumerable. The first order system is.
At the beginning of the 20th century mathematicians were looking for a first order system that would encapsulate all true statements of the second order Peano system. The reason for this is because a recursively enumerable system is computable. The second order system is not.
Now there is a only one model of the second order Peano axioms (up to isomorphism). This model is the natural numbers we all know and love. What Godel showed was that there is no first order system capable of encapsulating all true statements in the integers (the model we all know and love).
If you have a statement that can't be disproven then it is true. A statement is true if and only if there is no counterexample to it in any model of the axiomatic system you are dealing with. That's what the Completeness result is. So, if you have a statement for which there is no counterexample in any model then it's true. This is what the Completeness result is all about.
The statement you made:
" It says that in any sufficiently complex axiom system there will be statements that it can neither prove nor refute, "undecidable" statements."
is incorrect. Just take a model and collect all the true statements. Voila, you have an axiomatic system that is complete. Do this for any model and you have a complete axiomatic system. If your model contains the natural numbers then this complete axiomatic system isn't computable.
>You are confused by the implications and meanings of the results of Godel.
No, I'm really not.
>There are two (popular) axiom systems of the natural numbers. Both are from Peano. One system is first order and the other is second order. The second order system is not recursively enumerable. The first order system is.
That is correct.
>At the beginning of the 20th century mathematicians were looking for a first order system that would encapsulate all true statements of the second order Peano system.
That's still nonsense. I've already explained why.
>Now there is a only one model of the second order Peano axioms (up to isomorphism). This model is the natural numbers we all know and love. What Godel showed was that there is no first order system capable of encapsulating all true statements in the integers (the model we all know and love).
While that is partially correct, in fact Goedel's incompleteness theorem establishes a much stronger result.
>If you have a statement that can't be disproven then it is true. A statement is true if and only if there is no counterexample to it in any model of the axiomatic system you are dealing with. That's what the Completeness result is. So, if you have a statement for which there is no counterexample in any model then it's true. This is what the Completeness result is all about.
That is correct although completely irrelevant to everything else, and uses bad terminology. Logicians usually use "true" to mean "true in a particular model", and "valid" or "logically valid" to mean "true in all models of a given system" or "true in all models".
The thing is, you're still not clear on the difference between the two meanings of "complete". Think it through. It's an important distinction because not understanding it leads to confusion.
In one meaning, the first-order logic is called complete because every logically valid statement is provable from the logical axioms. Or, more broadly, every statement valid in an axiomatic system T (meaning, it's true in any possible model in which axioms of T are true) can be proved in T. That's one meaning of "complete", and it's not changing from one axiomatic system to another, as long as we stay in first-order logic. It's been proved for this logic once and for all by Godel.
In another meaning of "complete", a particular axiomatic system T is complete if it proves either X or not-X for any statement X whatsoever. This meaning of "complete" is true for some axiomatic systems T and false for others.
Now, let's go back again to my statement about the Incompleteness Theorem: "It says that in any sufficiently complex axiom system there will be statements that it can neither prove nor refute, "undecidable" statements." Among some very confused statements, you pointed out correctly that this has a trivial counterexample: take all true statements about natural numbers and call them axioms - that'll be a complete system. This is true, because I glossed over the "recursively enumerable" requirement on purpose - and then, replying to your previous comment, tried to simplify it by saying that such a counterexample is not a "manageable" axiomatic system. The reason is that I'm trying to use as few technical words as possible while avoiding dumbing down the content to the Liar paradox. I'm trying to make the content interesting to the passers-by rather than lead a flame war (which is why if my next comment would just have to rehash the same material again, you can count on me not posting it).
Sometimes the "manageability" of the axiomatic system - what's technically called "recursive enumerability", and really means that we have a reasonable way of checking what our axioms are - is baked into the very definition of what "an axiomatic system" is. Sometimes it isn't and needs to be mentioned additionally. It doesn't really matter because everyone who understands the Incompleteness Theorems technically knows about this requirement.
Anyway, yes, this requirement is important and necessary. But pointing it out doesn't refut...
I didn't confuse completeness in the sense of the Completeness Theorem with the sense in the Incompleteness Theorem. I made two separate points. One point was to state what the Incompleteness Theorem means and the other was to show that what you wrote was wrong.
You made the claim:
"It says that in any sufficiently complex axiom system there will be statements that it can neither prove nor refute,...
This is clearly false unless you restrict yourself to recursively enumerable axiomatic systems. My proof of this was to take all true statements of the model of the integers under the second order system. That forms an axiomatic system in which all true statements are provable. That is all I have really said in this matter.
The recursively enumerable criterion is important because of how all this came about historically. Humans - Hilbert, Russell, etc. - had a perception of what the integers are. Their goal was to encapsulate mathematical truth 'algorithmically' (in a computable way) and Godel showed this wasn't possible. All true statements of the first order axioms are true in the model of the second order axioms. The reverse isn't true. The dream was crushed.
They didn't know before Godel that the natural numbers we all grew up with couldn't be modeled properly with a recursively enumerable set of axioms but that's what they wanted and were looking for.
EDIT: I conflated the terms 'refute' and 'disprove'. Sorry about that. There is a difference between proving ~A and finding a counterexample to A in some model. I read 'refute' as 'disprove'.
"It says that in any sufficiently complex axiom system there will be statements that it can neither prove nor refute,..."
...is absolutely correct.
Your claim...:
"...take all true statements of the model of the integers under the second order system. That forms an axiomatic system in which all true statements are provable."
...is patently false. You are abusing the term 'truth' and confusing yourself. What 'truth' means in logic is not the same as what it means in the colloquial sense. In logic, we speak of truth only in terms of interpretation. Hence, axiomatic truth is an equivalent notion to provability.
In light of this, what you are saying is that if we take all the provable theorems in an axiomatic system, and add those theorems as axioms, we will have captured all possible truths - Godel's theorem actually proves that this is untrue for any sufficiently powerful axiomatic theorems (and 'powerful' here means capable of expressing number-theoretic statements.)
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.
At least this much was shown in original post; All proofs Goedel's theorem rely on the ability of a very particular language to be self-describing. Thus you cannot have "any system" but rather must a particular system, one "at least a powerful as arithmetic", one which is self-describing.
And this is where Anatoly's false distinction between "syntactic" and "semanitc" proofs breaks down. The proof of Goedel's theorem relies on these mechanics (one's ability to create Goedel numbering or the equivalent), these semantics of arithmetic. There is no Goedel's theoreom for Tarrot Cards because Tarrot Card don't have a set of rules which allow them to be self-describing.
> Goedel's first incompleteness theorem doesn't talk about "true" or "false" statements at all.
Isn't completeness about relating what can be proved with what is "true"? I get that you can discuss proofs with no notion of "true" or "false", but how do you discuss completeness without them?
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.
Strongly recommend Manin to the mathematically literate interested in a sophisticated and worldly introduction to logic. Manin gives very understandable details of the Smullyan proof this guy is taking bits and pieces of.
-- And Antoly's "semantic/syntax" distinction is overdone.
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.
Well, I think I'm starting to understand your take on the subject. Thank you for putting in the effort to explain it (where I agree or not).
It seems like the issue is whether the case of D not being a subset of T is "interesting" or not.
I think Manin has a point in sense that if we know that D is not a subset of T, then we are in a rather pathological case.
But I can see your point in the sense that if it's impossible to prove within an axiomatic system that the system itself is inconsistent, then one has to keep a situation like D not being a subset of T in mind.
It's very roughly speaking, the computational versus the syntactic view of logic...
The genius is in the mechanics of the proof. It's not at all obvious that you can express self-referential statements about provability within arithmetic, but Gödel showed how to do it.
It's worth following a description of the proof in one of the various popularizations to feel your mind get pleasantly twisted.
The proof presented in Nagel and Newman's book is not that difficult to follow, and the insight that you get from following the proof itself is genuinely worth the effort of sitting down with the book for a weekend. I should think that anyone who can construct a working computer program is capable of this.
A much larger challenge would be sitting down afterward and explaining it to someone else.
The article in Wikipedia is pretty good, although stops short of the full details. In particular it addresses this question of the Liar's Paradox versus Gödel's theorem "proper".
Okay. I have a problem maybe someone can help me with.
The article says:
"If the machine prints NPRNPR, it has printed a false statement. But if the machine never prints NPRNPR, then NPRNPR is a true statement that the machine never prints."
This part seems logically true:
"If the machine prints NPRNPR, it has printed a false statement." It seems logically true, and I wont say why because I view it as obvious =/
This part seems logically false:
"if the machine never prints NPRNPR, then NPRNPR is a true statement" I don't understand the logic of "If it is not printed, it is true." I was under the impression that the only true statement was "If it prints, then it is true", and of course the contrapositive: "If it is not true, it doesn't print". The statement taken from the article is NOT the contrapositive. It is the inverse, and because the converse of a statement is not always true, the inverse is not always true because the inverse is always equal to the converse.
"if the machine never prints NPRNPR, then NPRNPR is a true statement" That statement is the inverse of the original if-then statement, and the inverse/converse is FALSE because it allows opportunities which violate the original if-then statement.
I logically concluded that the statement in the proof:
"if the machine never prints NPRNPR, then NPRNPR is a true statement" is a false statement. And therefore the proof is incorrect.
Okay. If I am wrong, can someone please tell me where?
The truth of the statement does not derive from being an inverse, converse, or contrapositive of the statement before it. Rather, it is inferred from what we defined "NPR" to mean.
Since "NPR" is defined as true if what follows it is never printed twice in succession, and "NPRNPR" is never printed as a given, then "NPRNPR" as a statement is true.
55 comments
[ 3.1 ms ] story [ 117 ms ] threadMeaning you could come up with a trivial system to which it doesn't apply. Which begs the question: How do you define triviality here?
This includes some surprisingly complicated systems, like real (as opposed to integer) arithmetic.
Bonus pedantipoint: it's not begging the question - that actually means 'to assume X in your proof of X'. It's just raising the question.
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.
So it's over, "begs" has a new meaning, and complaining about it is pointless.
Real arithmetic is not enough to express integer arithmetic?
I suppose it all boils down to how you define "arithmetic", but what is it that the integers have that the reals lack under the relevant definition? I would think that real arithmetic by any reasonable definition would give you enough tools to check whether a number was an integer, and in that case, doesn't it necessarily contain integer arithmetic as a subset?
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]."
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.
If you print only true statements, you can not print all true statements. Proof:
"I do not print this statement"
http://en.wikipedia.org/wiki/G%C3%B6del%27s_incompleteness_t...
'The analysis of the truth and provability of G is a formalized version of the analysis of the truth of the liar sentence.'
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.
Gödel figured out how to encode the statement "you can't prove me" as an arithmetical expression. Minds blew.
Good explanation though.
The confusion between the two is widespread.
Goedel's first incompleteness theorem doesn't talk about "true" or "false" statements at all. Technically speaking, it is entirely syntactic, not semantic. It says that in any sufficiently complex axiom system there will be statements that it can neither prove nor refute, "undecidable" statements. The notions of "prove", "refute", "axiom", "undecidable" do not require any definition of "true" or "false".
In fact, his Completeness Theorem proves the opposite of what you claim. If you use as your axiom system all true statements of the model you are working in you will have a complete axiom system. All true statements will be trivially provable. The problem with this is that one will have a hard time determining if a given statement is an axiom or not.
If a statement can not be refuted - meaning no counterexample exists - then this is a proof that it is true.
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...
There are two (popular) axiom systems of the natural numbers. Both are from Peano. One system is first order and the other is second order. The second order system is not recursively enumerable. The first order system is.
At the beginning of the 20th century mathematicians were looking for a first order system that would encapsulate all true statements of the second order Peano system. The reason for this is because a recursively enumerable system is computable. The second order system is not.
Now there is a only one model of the second order Peano axioms (up to isomorphism). This model is the natural numbers we all know and love. What Godel showed was that there is no first order system capable of encapsulating all true statements in the integers (the model we all know and love).
If you have a statement that can't be disproven then it is true. A statement is true if and only if there is no counterexample to it in any model of the axiomatic system you are dealing with. That's what the Completeness result is. So, if you have a statement for which there is no counterexample in any model then it's true. This is what the Completeness result is all about.
The statement you made:
" It says that in any sufficiently complex axiom system there will be statements that it can neither prove nor refute, "undecidable" statements."
is incorrect. Just take a model and collect all the true statements. Voila, you have an axiomatic system that is complete. Do this for any model and you have a complete axiomatic system. If your model contains the natural numbers then this complete axiomatic system isn't computable.
http://geb.stenius.org/
No, I'm really not.
>There are two (popular) axiom systems of the natural numbers. Both are from Peano. One system is first order and the other is second order. The second order system is not recursively enumerable. The first order system is.
That is correct.
>At the beginning of the 20th century mathematicians were looking for a first order system that would encapsulate all true statements of the second order Peano system.
That's still nonsense. I've already explained why.
>Now there is a only one model of the second order Peano axioms (up to isomorphism). This model is the natural numbers we all know and love. What Godel showed was that there is no first order system capable of encapsulating all true statements in the integers (the model we all know and love).
While that is partially correct, in fact Goedel's incompleteness theorem establishes a much stronger result.
>If you have a statement that can't be disproven then it is true. A statement is true if and only if there is no counterexample to it in any model of the axiomatic system you are dealing with. That's what the Completeness result is. So, if you have a statement for which there is no counterexample in any model then it's true. This is what the Completeness result is all about.
That is correct although completely irrelevant to everything else, and uses bad terminology. Logicians usually use "true" to mean "true in a particular model", and "valid" or "logically valid" to mean "true in all models of a given system" or "true in all models".
The thing is, you're still not clear on the difference between the two meanings of "complete". Think it through. It's an important distinction because not understanding it leads to confusion.
In one meaning, the first-order logic is called complete because every logically valid statement is provable from the logical axioms. Or, more broadly, every statement valid in an axiomatic system T (meaning, it's true in any possible model in which axioms of T are true) can be proved in T. That's one meaning of "complete", and it's not changing from one axiomatic system to another, as long as we stay in first-order logic. It's been proved for this logic once and for all by Godel.
In another meaning of "complete", a particular axiomatic system T is complete if it proves either X or not-X for any statement X whatsoever. This meaning of "complete" is true for some axiomatic systems T and false for others.
Now, let's go back again to my statement about the Incompleteness Theorem: "It says that in any sufficiently complex axiom system there will be statements that it can neither prove nor refute, "undecidable" statements." Among some very confused statements, you pointed out correctly that this has a trivial counterexample: take all true statements about natural numbers and call them axioms - that'll be a complete system. This is true, because I glossed over the "recursively enumerable" requirement on purpose - and then, replying to your previous comment, tried to simplify it by saying that such a counterexample is not a "manageable" axiomatic system. The reason is that I'm trying to use as few technical words as possible while avoiding dumbing down the content to the Liar paradox. I'm trying to make the content interesting to the passers-by rather than lead a flame war (which is why if my next comment would just have to rehash the same material again, you can count on me not posting it).
Sometimes the "manageability" of the axiomatic system - what's technically called "recursive enumerability", and really means that we have a reasonable way of checking what our axioms are - is baked into the very definition of what "an axiomatic system" is. Sometimes it isn't and needs to be mentioned additionally. It doesn't really matter because everyone who understands the Incompleteness Theorems technically knows about this requirement.
Anyway, yes, this requirement is important and necessary. But pointing it out doesn't refut...
You made the claim:
"It says that in any sufficiently complex axiom system there will be statements that it can neither prove nor refute,...
This is clearly false unless you restrict yourself to recursively enumerable axiomatic systems. My proof of this was to take all true statements of the model of the integers under the second order system. That forms an axiomatic system in which all true statements are provable. That is all I have really said in this matter.
The recursively enumerable criterion is important because of how all this came about historically. Humans - Hilbert, Russell, etc. - had a perception of what the integers are. Their goal was to encapsulate mathematical truth 'algorithmically' (in a computable way) and Godel showed this wasn't possible. All true statements of the first order axioms are true in the model of the second order axioms. The reverse isn't true. The dream was crushed.
They didn't know before Godel that the natural numbers we all grew up with couldn't be modeled properly with a recursively enumerable set of axioms but that's what they wanted and were looking for.
EDIT: I conflated the terms 'refute' and 'disprove'. Sorry about that. There is a difference between proving ~A and finding a counterexample to A in some model. I read 'refute' as 'disprove'.
"It says that in any sufficiently complex axiom system there will be statements that it can neither prove nor refute,..."
...is absolutely correct.
Your claim...:
"...take all true statements of the model of the integers under the second order system. That forms an axiomatic system in which all true statements are provable."
...is patently false. You are abusing the term 'truth' and confusing yourself. What 'truth' means in logic is not the same as what it means in the colloquial sense. In logic, we speak of truth only in terms of interpretation. Hence, axiomatic truth is an equivalent notion to provability.
In light of this, what you are saying is that if we take all the provable theorems in an axiomatic system, and add those theorems as axioms, we will have captured all possible truths - Godel's theorem actually proves that this is untrue for any sufficiently powerful axiomatic theorems (and 'powerful' here means capable of expressing number-theoretic statements.)
At least this much was shown in original post; All proofs Goedel's theorem rely on the ability of a very particular language to be self-describing. Thus you cannot have "any system" but rather must a particular system, one "at least a powerful as arithmetic", one which is self-describing.
And this is where Anatoly's false distinction between "syntactic" and "semanitc" proofs breaks down. The proof of Goedel's theorem relies on these mechanics (one's ability to create Goedel numbering or the equivalent), these semantics of arithmetic. There is no Goedel's theoreom for Tarrot Cards because Tarrot Card don't have a set of rules which allow them to be self-describing.
Isn't completeness about relating what can be proved with what is "true"? I get that you can discuss proofs with no notion of "true" or "false", but how do you discuss completeness without them?
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.
Incorrect - Goedel is not much harder to prove or wider-ranging than Tarski.
Goedel is proven as a corollary to Tarski in Manin, Course In Mathematical Logic (Springer - http://www.amazon.com/Course-Mathematical-Logic-Graduate-Mat...)
Strongly recommend Manin to the mathematically literate interested in a sophisticated and worldly introduction to logic. Manin gives very understandable details of the Smullyan proof this guy is taking bits and pieces of.
-- And Antoly's "semantic/syntax" distinction is overdone.
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.
It seems like the issue is whether the case of D not being a subset of T is "interesting" or not.
I think Manin has a point in sense that if we know that D is not a subset of T, then we are in a rather pathological case.
But I can see your point in the sense that if it's impossible to prove within an axiomatic system that the system itself is inconsistent, then one has to keep a situation like D not being a subset of T in mind.
It's very roughly speaking, the computational versus the syntactic view of logic...
It's worth following a description of the proof in one of the various popularizations to feel your mind get pleasantly twisted.
[1]http://en.wikipedia.org/wiki/Gödel_number
I wouldn't characterize either as "trivial", though. May seem obvious in hindsight, but both were a pretty big deal at the time.
A much larger challenge would be sitting down afterward and explaining it to someone else.
This makes sense in that the machine has told itself never to print NPR@NPR@ in the future.
It would be like trying to verify someone doesn't know a secret by asking them about the secret they shouldn't know.
Zero knowledge proofs come to mind.
And that's probably a good description of my knowledge on this subject.
edit: changed asterisks to @ because HN doesn't display asterisks.
http://en.wikipedia.org/wiki/Goedel%27s_incompleteness_theor...
The article says:
"If the machine prints NPRNPR, it has printed a false statement. But if the machine never prints NPRNPR, then NPRNPR is a true statement that the machine never prints."
This part seems logically true:
"If the machine prints NPRNPR, it has printed a false statement." It seems logically true, and I wont say why because I view it as obvious =/
This part seems logically false:
"if the machine never prints NPRNPR, then NPRNPR is a true statement" I don't understand the logic of "If it is not printed, it is true." I was under the impression that the only true statement was "If it prints, then it is true", and of course the contrapositive: "If it is not true, it doesn't print". The statement taken from the article is NOT the contrapositive. It is the inverse, and because the converse of a statement is not always true, the inverse is not always true because the inverse is always equal to the converse. "if the machine never prints NPRNPR, then NPRNPR is a true statement" That statement is the inverse of the original if-then statement, and the inverse/converse is FALSE because it allows opportunities which violate the original if-then statement.
I logically concluded that the statement in the proof:
"if the machine never prints NPRNPR, then NPRNPR is a true statement" is a false statement. And therefore the proof is incorrect.
Okay. If I am wrong, can someone please tell me where?
Since "NPR" is defined as true if what follows it is never printed twice in succession, and "NPRNPR" is never printed as a given, then "NPRNPR" as a statement is true.