From: hwatheod@leland.Stanford.EDU (theodore hwa) Newsgroups: sci.math Subject: Re: Godel's Incompleteness Theorem Date: 19 Oct 1997 22:32:44 GMT The Master (kerinp@dynamite.com.au) wrote: : Can someone explain the significance of this theorem? : : My understanding of it is that it proves that in any formal consistent : expressive system you can formulate arguments which can not be proven to be : true or false within that system. Well, I would say "formulate statements". The problem is this: we have a system, say the natural numbers N={0,1,2,...} This is a precisely defined system. Any statement in N is either true or false. But now we want to know how we can prove such statements to be true or false. In order to do that, we have to assume some axioms. The question is: can we choose a set of axioms that allows us to prove any true statement in N, and refute any false statement in N? Well, in one sense we can: we can take the axioms which "precisely define" N as I mentioned two paragraphs ago. But Godel's Incompleteness Theorem concerns itself with "first-order" axioms, which means that you can make statements such as "for all natural numbers x, ..." or "there exists a natural number x such that... ", but you can't say things like "for all subsets of the natural numbers x, ..." Now the problem with a limited set of axioms is that, unless N is the only system satisfying these axioms, the things you prove will have to be true not only of N, but of any other system which also satisfies the same axioms. In fact, this will always happen for any infinite system, such as N. You can't write down a set of first-order axioms that uniquely defines an infinite system. But that doesn't in and of itself imply G.I.T., since the new system might coincide with N on all first-order properties, but still be different because of properties that cannot be expressed in first-order language. In fact, if we restrict ourselves further to statements involving only 0, S, + (where S is the successor operation: x->(x+1)), then we can write down a set of axioms that proves all such statements true in N and refutes all false ones. Nevertheless, N is not the only system satisfying the axioms. But Godel's Incompleteness Theorem (G.I.T.) says that if we extend the statement to allow multiplication as well, then we cannot write down any "recursive" set of axioms that accomplishes the same thing. ("Recursive" means that there must be an algorithm to tell whether something is an axiom. A system isn't very useful if you can't tell whether a statement is an axiom before you use it.) : It seems to only indicate that there is a false dichotomy in the mind of the : system's user if they can only conceive of true and false statements : existing. The distinction is between truth in an absolute system (N) and provability from a given set of first-order axioms. In the former case, every statement is true or false. In the latter case, there will be statements which are true in some system satisfying the axioms, but then false in another system satisfying the same axioms, so such statements will be unprovable with those axioms. An example is the parallel postulate in geometry. In short: there are two different contrasts: i) truth and falsity in an absolute system ii) provability and unprovability in an axiom system : If we assume that only true results can come from such a system, then surely : the incompleteness theorem may have amounted to a proof of false statements : existing. : The reply is then that we'll add the possible result of False. : After godel's incompleteness theorem, what if we allow a third result: : Paradox. Well, we'd better only be able to _prove_ true results, or else our system is inconsistent. We knew that false statements "existed" before G.I.T. (Here's one: 0=1). (What do you mean by "exist" here? Surely they exist as a sequence of symbols.) : Then any statement may result in True, False or Paradox. You'd have to define "Paradox" here. Right now it only seems to be "any statement which is neither provable nor unprovable in a particular axiom system" (notice I said provable nor unprovable, not true nor false). But that's not saying much, and doesn't necessarily have the ordinary connotations of the word. Sure, the original proof may have involved statements of the form "this statement is false", but there are more "natural-looking" statements in N which are true but nevertheless independent the formal framework of Peano's Axioms of the natural numbers. They don't sound paradoxical in any ordinary sense of the word.