Re: Godel's Incompleteness and Nonmonotonic Logic

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

Date: 24 Aug 2004 09:59:42 GMT

In article <1b626f1.0408231337.1f0dd837@posting.google.com>,
        jagasian@mailinator.com (Student) writes:
>> The incompleteness theorems of Goedel, however, refer to a completely
>> unrelated concept of completeness meaning "whatever follows is also
>> provable".
>
> You are wrong. The two incompleteness theorems of Godel refer to what
> you called "Hilbert completeness". Godel's theorems imply that you
> cannot have both completeness and consistency. The incompleteness
> Godel refers to is that there exist (closed first-order, not
> necessarily ground or atomic) logical formulas that cannot be proven,
> even though they are
> definitely true.

I can confirm that indeed, classical completeness follows from Hilbert
completeness (wrt. provability) and consistency.

Apart from that, I'm too confused by what you write to answer very
much.

Does "Answer Set Logic" have anything to do with negation by failure?
To get the kind of paradox you're after, one would at least imagine
provability to have to be decidable.

How to stitch this together with second order logics to which Goedels
incompleteness theorems refer escapes me.

Closed world assumption, which is a more mainstream representative of
the kind of nonmonotonic logics you seem to be talking about,
guarantees "Hilbert completeness" only wrt ground atomic formulae.

regards
Stephan 

-- 
  Stephan Lehmke     		 Stephan.Lehmke@cs.uni-dortmund.de
  Fachbereich Informatik, LS I	 Tel. +49 231 755 6434 
  Universitaet Dortmund		 FAX 		  6555
  D-44221 Dortmund, Germany      http://ls1-www.cs.uni-dortmund.de

Relevant Pages

  • Re: Godels Incompleteness and Nonmonotonic Logic
    ... >> The incompleteness theorems of Goedel, however, refer to a completely ... The two incompleteness theorems of Godel refer to what ... classical completeness follows from Hilbert ...
    (comp.lang.prolog)
  • Re: Godels Incompleteness and Nonmonotonic Logic
    ... > unrelated concept of completeness meaning "whatever follows is also ... The two incompleteness theorems of Godel refer to what ... The "Answer Set" style logics force that everything ...
    (sci.logic)
  • Re: Godels Incompleteness and Nonmonotonic Logic
    ... > unrelated concept of completeness meaning "whatever follows is also ... The two incompleteness theorems of Godel refer to what ... The "Answer Set" style logics force that everything ...
    (comp.lang.prolog)