Delivery-Date: 
Sender: info-hol-request@lal.cs.byu.edu
Errors-To: info-hol-request@lal.cs.byu.edu
Precedence: bulk
Date: Wed, 13 Apr 94 11:48:13 BST
From: Matt Fairtlough <M.Fairtlough@dcs.shef.ac.uk>
Message-Id: <9404131048.AA03557@dcs.shef.ac.uk>
To: info-hol@cs.uidaho.edu
In-Reply-To: <"i80fs2.ira.341:12.03.94.14.12.56"@ira.uka.de> (message from schneide on Tue, 12 Apr 1994 16:12:53 +0200)
Subject: Re: number theorie

In his article, Schneide writes:

   3) The theory of the natural numbers has a unique model up to isomorphism
      which can be axiomatised by Peano's Axioms. Therefore the set of closed
      formulae which become true under the standard interpretation contains
      either phi or ~phi. However, this means that this theory is complete,
      in contradiction to Goedels theorem! What is wrong?

As it see it, the problem with this statement is the assertion that
"the theory of the natural numbers has a unique model up to
isomorphism which can be axiomatised by Peano's Axioms".  Your logic
seems ok to me.

If by "Peano's Axioms" you mean "the axioms of Peano Arithmetic",
and by "can be axiomatised by Peano's Axioms" you mean "is equivalent to
the theorems of Peano Arithmetic", then the assertion is false--there
are non-standard models of Peano Arithmetic, as is well known.

The key axiom here is induction:

A(0) -> (forall x. (A(x) -> A(x+1))) -> forall x. A(x)

which only applies to sets A definable in Peano Arithmetic.

On the other hand, if by "Peano's Axioms" you mean "Peano's Postulates"
							    ^^^^^^^^^^
which include the axiom:

(0 in A) -> (forall x. (x in A) -> (x+1 in A)) -> forall x. x in A

which applies to ALL sets A and says that any set including 0 and
closed under the operation n |-> n+1 must be the whole of N, then we
are into the realm of second order logic, and the situation is
different.  It is true that there is, up to isomorphism, only one
model of these axioms, when "model" is used in the usual model
theoretic sense, and not in the sense of "general model".  However,
the corresponding theory T (i.e., set of sentences true in the model)
is not recursively axiomatisable--there is no finitary logic with a
recursive notion of proof whose closed theorems are exactly the
members of T.

Hamilton gives a good discussion of some aspects of this in "Logic for
Mathematicians"  (CUP, 1978).

The word "theory" is used in three distinct senses in logic.  The
first meaning, as exemplified by the phrase "the theory of Peano
Arithmetic" is a proof-theoretical one, and the phrase means "the
_theorems_ of Peano Arithmetic".  The second meaning, as exemplified
by the phrase "the theory of arithmetic" is a model-theoretic one, and
the phrase means "the closed logical consequences of the theory of
arithmetic" (equivalently, "the sentences true in every model of
arithmetic"), which, in the case of a set of axioms with only one
model N, means "the sentences true in N".  The third meaning, as
exemplified by the phrase "the theory of the natural numbers N" is also
model-theoretic, and the phrase means "all sentences true in N".


-------------------------------------------------------------------
Matt Fairtlough					matt@dcs.shef.ac.uk
Department of Computer Science			Room 115
University of Sheffield
Regent Court, 211 Portobello Street
Sheffield  S1 4DP		Tel:		0742-768555 ext 5592
				Direct dial:    0742-825592
				Fax:		0742-780972
<sorry, no more room for an amusing .sig....>
--------------------------------------------------------------------