Re: Godel's Incompleteness and Nonmonotonic Logic
From: Herman Jurjus (h.jurjus_at_hetnet.nl)
Date: 08/24/04
- Next message: Herman Jurjus: "Re: Godel's Incompleteness and Nonmonotonic Logic"
- Previous message: R. Kym Horsell: "Re: Help with Peg Solitaire 15 hole triangle version"
- In reply to: Student: "Re: Godel's Incompleteness and Nonmonotonic Logic"
- Next in thread: Herman Jurjus: "Re: Godel's Incompleteness and Nonmonotonic Logic"
- Messages sorted by: [ date ] [ thread ] [ subject ] [ author ]
Date: Tue, 24 Aug 2004 11:25:14 +0200
Student wrote:
>>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.
>
> The "Answer Set" style logics force that everything
> or its negation is provable.
Only for weak negation.
Hence a simple encoding of arithmetic
> would result in an inconsistent system, as for example, the formula
> "F" of Godel's first incompleteness theorem cannot be proven, and so
> by answer set logics, "not F" is provable. Since "not F" is provable,
> the logic is simply inconsistent.
The inference relation of non-monotonic logic is not the same as for
classical logic. For classical logic, there are only finitely many rules
of inference, and the notion of 'provable' can be formalized in terms of
natural numbers. For non-monotonic logics with a perfect weak negation,
that's probably not the case (as your very argument shows). And such
systems will necessary be undecidable, indeed.
However, there exist systems with a 'non-perfect' weak negation,
like Donald Nute's Defeasible Logic. This system was deliberately
targeted at computability, and with success, apparantly:
Propositional Defeasible Logic has Linear Complexity, M.J.Maher, 2001,
Theory and Practice of Logic Programming (online via citeseer).
> Digging a little on the net, I have found at least one notable
> detractor to nonmonotonic logics, Jean-Yves Girard. In "Girard, J.-Y.
> : Locus Solum, Mathematical Structures in Computer Science 11, pp.
> 301-506, 2001." Girard mentions in brief that Nonmonotonic logics fall
> into the trap of inconsistency/incompleteness.
The incompleteness that he probably means is 'the logics are not
axiomatizable by finitely many rules, like FOL'.
BTW, there are lots of other NM systems than answer set programming, and
only some of them contain a weak negation. (You need weak negation to
arrive at your argument. In systems with only strong negation, it's
quite possible that neither A nor not-A are provable.)
Do you know the subject "belief revision"?
That may be a better introduction of what NML is all about.
Suppose you have 'a theory' (=some knowledge or beliefs), and now
something turns out to be true that is in contradiction with that
knowledge. Now what parts of your existing knowledge have to go, and
which parts will stay?
Finding languages to describe, beforehand, how to revise theories in
case of exceptions: that's the point of non-monotonic logic.
-- Cheers, Herman Jurjus
- Next message: Herman Jurjus: "Re: Godel's Incompleteness and Nonmonotonic Logic"
- Previous message: R. Kym Horsell: "Re: Help with Peg Solitaire 15 hole triangle version"
- In reply to: Student: "Re: Godel's Incompleteness and Nonmonotonic Logic"
- Next in thread: Herman Jurjus: "Re: Godel's Incompleteness and Nonmonotonic Logic"
- Messages sorted by: [ date ] [ thread ] [ subject ] [ author ]
Relevant Pages
|
