Re: Godel's Incompleteness and Nonmonotonic Logic

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

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

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