Notes

The discussion of first-order logic here is largely taken from [Fagin, Halpern, Moses, and Vardi 1995], which in turn is based on that of Enderton [1972]. The axiomatization of first-order logic given here is essentially that given by Enderton, who also proves completeness. A discussion of generalized quantifiers can be found in [Ebbinghaus 1985]. Trakhtenbrot [1950] proved that the set of first-order formulas valid in finite relational structures is not recursively enumerable (from which it follows that there is no complete axiomatization for first-order logic over finite structures). The fact that there is a translation from propositional epistemic logic to first-order logic, as mentioned in Section 10.1, seems to have been observed independently by a number of people. The first treatment of these ideas in print seems to be due to van Benthem [1974]; details and further discussion can be found in his book [1985]. Finite model theorems are standard in the propositional modal logic literature; they are proved for epistemic logic in [Halpern and Moses 1992], for the logic of probability in [Fagin, Halpern, and Megiddo 1990], and for conditional logic in [Friedman and Halpern 1994].

Hintikka [1962] was the first to discuss first-order epistemic logic. The discussion in Section 10.2 on first-order reasoning about knowledge is also largely taken from [Fagin, Halpern, Moses, and Vardi 1995]. Garson [1984] discusses in detail a number of ways of dealing with what is called the problem of "quantifying-in": how to give semantics to a formula such as ∃xK_i(P (x)) without the common domain assumption. The distinction between "knowing that" and "knowing who" is related to an old and somewhat murky philosophical distinction between knowledge de dicto (literally, "knowledge of words") and knowledge de re (literally, "knowledge of things"). See Hintikka [1962] and Plantinga [1974] for a discussion.

Section 10.3 on first-order reasoning about probability is largely taken from [Halpern 1990], including the discussion of the distinction between the two interpretations of probability (the statistical interpretation and the degree of belief interpretation), the axiom systems AX^prob,fo_{n, N} and AX^stat_N, and Theorems 10.3.1 and 10.3.2. The idea of there being two types of probability is actually an old one. For example, Carnap [1950] talks about probability₁ and probability₂. Probability₂ corresponds to relative frequency or statistical information; probability₁ corresponds to what Carnap calls degree of confirmation. This is not quite the same as degree of belief; the degree of confirmation considers to what extent a body of evidence supports or confirms a belief, along the lines discussed in Section 3.4. However, there is some commonality in spirit. Skyrms [1980] also considers two types of probability, similar in spirit to Carnap although not identical. Skyrms talks about first- and second-order probabilities, where first-order probabilities represent propensities or frequency—essentially statistical information—while second-order probabilities represent degrees of belief. He calls them first- and second-order probabilities since typically an agent has a degree of belief about statistical information; that is, a second-order probability on a first-order probability.

Bacchus [1988] was the first to observe the difficulty in expressing statistical information using a possible-worlds model; he suggested using the language ^QU,stat. He also provided an axiomatization in the spirit of AX^stat_N that was complete with respect to structures where probabilities could be nonstandard; see [Bacchus 1990] for details. On the other hand, there can not be a complete axiomatization for either ^QU,fo_n or ^QU,stat_n, with respect to ^meas,fo_n or ^meas,stat, respectively [Abadi and Halpern 1994].

The material in Section 10.4 on first-order conditional logic is largely taken from [Friedman, Halpern, and Koller 2000], including the analysis of the lottery paradox, the definitions of Pl4*, Pl4^†, Pl5*, and all the technical results. Other papers that consider first-order conditional logic include [Delgrande 1987; Brafman 1997; Lehmann and Magidor 1990; Schlechta 1995; Schlechta 1996]. Brafman [1997] considers a preference order on the domain, which can be viewed as an instance of statistical plausibility. He assumed that there were no infinitely increasing sequences, and showed that, under this assumption, the analogue of C9, together with F1–5, UGen, and analogues of C1–4 in the spirit of PD1–4 provide a complete axiomatization. This suggests that adding C5–7 and C9 to the axioms will provide a complete axiomatization of ^→,fo_n for _n^rank+,fo, although this has not yet been proved. Lehmann and Magidor [1990] and Delgrande [1988] consider ways of using conditional logic for default reasoning.

There has been recent work on extending Bayesian networks to deal with relational structures. This is an attempt to combine the representational power given by Bayesian networks and first-order logic. See [Koller and Pfeffer 1998; Friedman, Getoor, Koller, and Pfeffer 1999] for details.