Unpublished manuscript  Written and typeset September 25, 1981; reset September 6, 1996

Non-Monotonic Logic and System G^{1}

Jon Doyle September 25, 1981

Abstract

This note refutes the conjecture that Boolos’ modal logic G forms a basis for an interesting non-monotonic logic.

In [2] and [3] I conjectured that the correct non-monotonic logic is the weak logic of [3] strengthened by axiom schema corresponding to the theorems of Boolos’ modal logic G [1]. The motivation for this conjecture was the view that since nonmonotonic logic is a logic concerning provability, it ought to reduce to the logic of ordinary provability “in the limit” as the specifically nonmonotonic aspects were ignored. Because G captures the logic of provability in Peano arithmetic, I concluded it was the correct “limit” for such reductions. I was wrong.

The interesting property of G is that it exactly captures the notion of provability in Peano arithmetic (PA) by means of its modality. Put another way, G exactly characterizes the set of theorems of the axiom set PA in the set of all formulas L. G exactly describes the sets Th(PA) and L − Th(PA).

The point of non-monotonic logic, however, is to describe the notion of provability under varying sets of axioms and assumptions. For each set of axioms and assumptions A, the modality of nonmonotonic logic should characterize the sets of formulas Th(A) and L − Th(A). Since PA is merely one possible set A, restricting the modality of non-monotonic logic to describing Th(PA) and L − Th(PA) misses the point of the logic.

The weak logic of [3] does require strengthening to capture a better notion of provability, but should not include notions of provability from a fixed set of axioms.

1. Boolos, G., 1979. The Unprovability of Consistency, Cambridge: Cambridge University Press.

2. Panel on non-monotonic logic, First Annual Conference of the American Association for Artificial Intelligence, Stanford, California, August 1980.

3. McDermott, D., and Doyle, J., 1980. Non-monotonic logic—I, Artificial Intelligence 13, 41-72.

1Questions from Robert Moore and Richard Stallman helped lead me to this refutation. This research was supported by Carnegie-Mellon University.

\begin{matrix}c \\ ◯ \end{matrix}1981, 196 Jon Doyle. All rights reserved.