Re: Godel's Incompleteness and Nonmonotonic Logic

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

  • Next message: russell kym horsell: "Re: Remove all asserted facts?" 
    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.

  • Next message: russell kym horsell: "Re: Remove all asserted facts?"

    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. ...
      (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 ...
      (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)