Re: Godel's Incompleteness and Nonmonotonic Logic

From: Clive (clive.jervis_at_mot.com)
Date: 08/25/04 

Date: 25 Aug 2004 16:25:42 -0700

Just to clarify what Aattu is saying ...

Goedel's Completeness Theorem states that the First Order Predicate
Calculus (FOPC) is complete, by which he means that any sentence which
is true in every model of the FOPC is provable in that calculus (and
vice-versa). Clearly the catch is "true in every model".

Although it seems common to refer to "the" FOPC, etc, there are
alternative axiomatizations; also the FOPC here excludes equality.

Personally, I think this result is often underrated, since my reading
of this is that if any extension of FOPC is proven to be incomplete
(e.g. PA), then this must be because of the extensions - you do not
need to doubt the FOPC part. I also find the proof(s) of the theorem
to be pretty hard to follow.

Goedel's First Incompletness Theorem states that any any consistent
extension of first order Peano Arithmetic (PA) is incomplete. This can
be weakened to Robinson Arithmetic.

That the Second Order Predicate Calculus is incomplete is a direct
consequence of PA's incompleteness, since any sentence of PA can be
coded as a sentence of SOPC - in particular, the Goedelean sentence.

Clive.

Aatu Koskensilta <aatu.koskensilta@xortec.fi> wrote in message news:<cgiklc$1op$1@phys-news1.kolumbus.fi>...
 
> There are two standard meanings for incompleteness. First order logic is
> complete in the sense that if A is true in all of the models of a theory
> T, then A is provable from T. Obviously first order logic is not
> complete in the sense that either A or ~A is provable for all A. First
> order theories which contain a modicum of elementary arithmetic can be
> shown to be either inconsistent or incomplete, in the sense that there
> are propositions which are neither provable nor refutable in these theories.
>
> Second order logic is incomplete in the sense that there is no complete
> deductive system for it, or in other words the second order logical
> consequences of a given second order theory or sentence are not
> recursively enumerable. Gödel's incompleteness theorems do apply to
> second order theories as well in the sense that for all theories
> containing a fragment elementary arithemtic and (sound) deductive system
> there are propositions which are neither refutable nor provable in the
> theory according to the deductive system.

Relevant Pages

  • Re: Godels Incompleteness and Nonmonotonic Logic
    ... Goedel's Completeness Theorem states that the First Order Predicate ... is true in every model of the FOPC is provable in that calculus (and ... extension of first order Peano Arithmetic is incomplete. ...
    (comp.lang.prolog)
  • Re: Godels Incompleteness and Nonmonotonic Logic
    ... then A is provable from T. Obviously first order logic is not ... > shown to be either inconsistent or incomplete, ... there is indeed a deep link between completeness ... provability in L becomes a predicate of the first order ...
    (sci.logic)
  • Re: Godels Incompleteness and Nonmonotonic Logic
    ... then A is provable from T. Obviously first order logic is not ... > shown to be either inconsistent or incomplete, ... there is indeed a deep link between completeness ... provability in L becomes a predicate of the first order ...
    (comp.lang.prolog)