Notes

Defining belief as "holds with probability 1" is common in the economics/game theory literature (see, e.g., [Brandenburger and Dekel 1987]). As I mentioned in Chapter 7, interpreting belief as "truth in all worlds considered possible," just like knowledge, is standard in the modal logic literature. Typically, the Knowledge Axiom (K_iφ ⇔ φ) is taken to hold for knowledge, but not belief. Brandenburger [1999] uses filters to model beliefs.

There has been a great deal of work on logics of knowledge and belief; see, for example, [Halpern 1996; Hoek 1993; Kraus and Lehmann 1988; Lamarre and Shoham 1994; Lenzen 1978; Lenzen 1979; Moses and Shoham 1993; Voorbraak 1991]. The use of plausibility to model belief is discussed in [Friedman and Halpern 1997], from where Proposition 8.2.1 and Exercise 8.7 are taken. The observation in Exercise 8.11 is due to Lenzen [1978; 1979]; see [Halpern 1996] for further discussion of this issue.

There has been a great deal of discussion in the philosophical literature about conditional statements. These are statements of the form "if φ then ψ," and include counterfactuals as a special case. Stalnaker [1992] provides a short and readable survey of the philosophical issues involved.

Many approaches to giving semantics to defaults have been considered in the literature. Much of the work goes under the rubric nonmonotonic logic; see Marek and Truszczyński's book [1993] and Reiter's overview paper [1987a] for a general discussion of the issues. Some of the early and most influential approaches include Reiter's default logic [1980], McCarthy's circumscription [1980], McDermott and Doyle's nonmonotonic logic [1980], and Moore's autoepistemic logic [1985].

The approach discussed in this chapter, characterized by axiom system P, was introduced by Kraus, Lehmann, and Magidor [1990] (indeed, the axioms and rules of P are often called the KLM properties in the literature) and Makinson [1989], based on ideas that go back to Gabbay [1985]. Kraus, Lehmann, and Magidor and Makinson gave semantics to default formulas using preferential structures. Pearl [1989] gave probabilistic semantics to default formulas using what he called epsilon semantics, an approach that actually was used independently and earlier by Adams [1975] to give semantics to conditionals. The formulation given here using PS structures was introduced by Goldszmidt, Morris, and Pearl [1993], and was shown by them to be equivalent to Pearl's original notion of epsilon semantics. Geffner [1992b] showed that this approach is also characterized by P.

Dubois and Prade [1991] were the first to use possibility measures for giving semantics to defaults; they showed that P characterized reasoning about defaults using this semantics. Goldszmidt and Pearl [1992] did the same for ranking functions. Friedman and I used plausibility measures to explain why all these different approaches are characterized by P. Theorems 8.4.10, 8.4.12, 8.4.14, and 8.4.15, and Proposition 8.6.4 are from [Friedman and Halpern 2001].

There has been a great deal of effort applied to going beyond axiom system P. The issue was briefly discussed by Kraus, Lehmann, and Magidor [1990], where the property of Rational Monotonicity was first discussed. This property is considered in greater detail by Lehmann and Magidor [1992]. The basic observation that many of the approaches to nonmonotonic reasoning (in particular, ones that go beyond P) can be understood in terms of choosing a preferred structure that satisfies some defaults is due to Shoham [1987]. Delgrande [1988] presented an approach to nonmonotonic reasoning that tried to incorporate default notions of irrelevance, although his semantic basis was somewhat different from those considered here. (See [Lehmann and Magidor 1992] for a discussion of the differences.) The System Z approach discussed in Section 8.5 was introduced by Pearl [1990] (see also [Goldszmidt and Pearl 1992]). The conclusions obtained by System Z are precisely those obtained by considering what Lehmann and Magidor [Lehmann 1989; Lehmann and Magidor 1992] call the rational closure of a knowledge base. Lehmann and Magidor give a formulation of rational closure essentially equivalent to System Z, using total preferential structures (i.e., using ^tot rather than ^rank). They also give a formulation using nonstandard probabilities, as in Exercise 8.20. Goldszmidt, Morris, and Pearl [1993] introduce the maximum-entropy approach discussed in Section 8.5. Two other approaches that have many of the properties of the maximum-entropy approach are due to Geffner [1992a] and Bacchus et al. [1996]; the latter appxroach is discussed further in Chapter 11.

The language ^→ was introduced by Lewis [1973]. Lewis first proved the connection between → and →′ given in Theorem 8.4.7; he also showed that > could be captured by → in partial preorders, as described in Proposition 8.6.2. (Lewis assumed that the preorder was in fact total; the fact that the same connection holds even if the order is partial was observed in [Halpern 1997a].) The soundness and completeness of AX^cond for preferential structures (Theorem 8.6.3) was proved by Burgess [1981]; the result for measurable plausibility structures is proved in [Friedman and Halpern 2001].

Stalnaker [1968] first gave semantics to counterfactuals using what he called selection functions. A selection function f takes as arguments a world w and a formula φ; f(w, φ) is taken to be the world closest to w satisfying φ. (Notice that this means that there is a unique closest world, as in Exercise 8.53.) Stalnaker and Thomason [1970] provided a complete axiomatization for counterfactuals using this semantics. The semantics for counterfactuals using preorders presented here is due to Lewis [1973].

Balke and Pearl [1994] provide a model for reasoning about probability and counterfactuals, but it does not use a possible-worlds approach. It would be interesting to relate their approach carefully to the possible-worlds approach.