Re: Godel's Incompleteness and Nonmonotonic Logic

From: Student (jagasian_at_mailinator.com)
Date: 08/24/04 

Date: 24 Aug 2004 14:41:03 -0700

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

Decidability is a separate issue. The problem is that an inconsistent
logic will allow for incorrect answers.

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

Godel's two famous theorems apply to first-order predicate logic. See
Kleene's "Introduction to Metamathematics", Kleene's "Mathematical
Logic", or Girard's "Proof Theory and Logical Complexity : Volume I",
if you cannot get your hands on the Godel's original work (or a
translation thereof).

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

Well, the answer set style logics work with non-ground formula by
assuming a possibly infinite grounding. See "Knowledge
Representation, Reasoning, and Declarative Problem Solving" by Chitta
Baral.

Relevant Pages
Loading