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.