3 ms·

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.

• david927 17y ago
  I <3 HN
  • pwmanagerdied 17y ago
    ...but now I have no idea which is actually true.
    • teeja 17y ago
      I don't 'stomach' higher math (experimentalist), but thought Hofstadter did a good job in "Godel, Escher, Bach". http://geb.stenius.org/ http://geb.stenius.org/
• anatoly 17y ago
  >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 refute in any way (as you said it did) my original point you replied to, which is that the Incompleteness Theorems is syntactic in nature, not semantic, and doesn't require any notion of "true" or "false" statements in its statement or proof. And, again, the Completeness Theorem, which you mentioned as supporting your counterexample, is a complete red herring and doesn't have to do anything with any of that. In fact, if first-order logic were incomplete (say if you removed a crucial logical axiom from it) and the Completeness Theorem wouldn't hold, it would still be true that you could take all true statements about the integers, call them axioms, and get a complete axiomatic system in the other meaning of "complete". Because it'd still be true that either X or not-X would be provable for any X - it'd be an axiom [1]. The Completeness Theorem doesn't enter into that counterexample of yours in any way. [1] This is almost true, but technically speaking, you'd still need to require that the underlying logic, while incomplete, would be powerful enough to prove the equivalence of not-not-X and X, for any X.