Re: Godel's Incompleteness and Nonmonotonic Logic

From: Aatu Koskensilta (aatu.koskensilta_at_xortec.fi)
Date: 08/25/04

  • Next message: Jamie Andrews; real address _at_ bottom of message: "Re: Godel's Incompleteness and Nonmonotonic Logic" 
    Date: Wed, 25 Aug 2004 21:09:47 +0300

    Stephan Lehmke wrote:

    > You [Student] are very generous with your references. I have none of them
    > immediately available, but as they stem from respectable authors, I am
    > sure you will find in them no claim that first-order predicate logic
    > is in danger of being incomplete in the standard meaning of this
    > concept.

    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. 

    -- 
Aatu Koskensilta (aatu.koskensilta@xortec.fi)
"Wovon man nicht sprechen kann, daruber muss man schweigen"
  - Ludwig Wittgenstein, Tractatus Logico-Philosophicus
  • Next message: Jamie Andrews; real address _at_ bottom of message: "Re: Godel's Incompleteness and Nonmonotonic Logic"

    Relevant Pages

    • Re: Godels Incompleteness and Nonmonotonic Logic
      ... order theories which contain a modicum of elementary arithmetic can be ... shown to be either inconsistent or incomplete, ... Second order logic is incomplete in the sense that there is no complete ... containing a fragment elementary arithemtic and deductive system ...
      (sci.logic)
    • Re: Godels Incompleteness and Nonmonotonic Logic
      ... or in other words the second order logical ... > second order theories as well in the sense that for all theories ... > containing a fragment elementary arithemtic and deductive system ...
      (comp.lang.prolog)
    • Re: Godels Incompleteness and Nonmonotonic Logic
      ... or in other words the second order logical ... > second order theories as well in the sense that for all theories ... > containing a fragment elementary arithemtic and deductive system ...
      (sci.logic)
    • =?ISO-8859-1?Q?Re:_Has_BS_Anand_Refuted_G=F6dels_Theorem?=
      ... PA, and still incomplete, again like second order PA. ... But I wonder what could it mean to "drop completeness" for first order ...
      (sci.logic)