Re: Godel's Incompleteness and Nonmonotonic Logic

From: Stephan Lehmke (Stephan.Lehmke_at_ls1.cs.uni-dortmund.de)
Date: 08/26/04 

Date: 26 Aug 2004 11:52:18 GMT

In article <cgiklc$1op$1@phys-news1.kolumbus.fi>,
        Aatu Koskensilta <aatu.koskensilta@xortec.fi> writes:
> 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.

Interesting. Thanks for the clarification.

Senn this way, there is indeed a deep link between completeness
in the "Hilbert" sense and "classical" completeness, because
if logic L is formulated as a first order theory T, then
provability in L becomes a predicate of the first order
formalization, and "classical" completeness of L is linked with
"Hilbert completeness" of T.

Although I'm not completely sure what the link is. "Hilbert
completeness" of T would mean that either provable(F) or -provable(F)
is provable in T for every formula F of L. But wouldn't this again
mean decidability of L?

Anyway, I see these things much clearer now.

regards
Stephan

Relevant Pages

  • 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)
  • =?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)
  • Re: My talk about Godel to the post-grads.
    ... the first incompleteness theorems. ... I never claimed that the subject of first order reasoning is unrelated ... What then is a meta theorem, ... are the originating points of a proof, provability of a meta theorem flows ...
    (sci.logic)
  • 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
    ... 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)