Iterated revision and minimal change of conditional beliefs (Q1918913)

In the now classic AGM model of theory change [\textit{C. E. Alchourrón}, \textit{P. Gärdenfors} and \textit{D. Makinson}, J. Symb. Log. 50, 510-530 (1985; Zbl 0578.03011); \textit{P. Gärdenfors}, Knowledge in flux: modeling the dynamics of epistemic states, MIT Press (1988)], no intuitively reasonable account of repeated change seems to be available. Let \(K\) be a belief set and \(\leq\) a relation of entrenchment for \(K\) (or any equivalent mechanism for changing \(K)\). We can regard the pair \(\langle K,\leq\rangle\) as a representation of the current belief state. When an input sentence \(\alpha\) is received, we can use \(\leq\) to obtain the revised belief set \(K^* \alpha\) that replaces \(K\). However, we are not provided with a new entrenchment relation to go with \(K^* \alpha\). In other words, the belief state \(\langle K,\leq \rangle\) is replaced by only an incomplete representation \(\langle K^* \alpha,? \rangle\) of the new belief state. Since we do not now have an entrenchment relation or other mechanism for change, we do not know how to change the new belief state when revision by yet another sentence \(\beta\) is called for. In this paper, the author summarizes and extends previous work in which he introduced a formally elegant and well worked-out solution to this problem. His minimal conditional revision (in earlier work called ``natural revision'') constructs a new mechanism for change by minimal change of the old one. The mechanisms for belief change used in this model are orderings on possible worlds. Intuitively, each such ordering represents an assignment of a degree of implausibility to each world. A belief state can then be represented by a pair consisting of a belief set and an implausibility ordering in which the minimal elements coincide with the worlds that are compatible with the belief set. (An entrenchment relation can easily be derived from such an implausibility ordering.) Actually, the first element of the pair, the belief set, is redundant since it is equal to the intersection of the worlds that are minimal according to the ordering. After revision, all worlds compatible with the new belief set are assigned minimal status according to the new implausibility ordering, whereas the rest of the implausibility ordering is left unchanged. With this simple construction, revision of a given belief state by a sequence of arbitrary length can be shown to be equivalent to revision of that same belief state in one step by a single sentence. Equivalently, every right-nested Ramsey conditional can be shown to have (relative to some specified belief state) the same acceptability condition as some unnested conditional. The author provides several formal characterizations of his construction. One of them is particularly interesting since it, just like the AGM postulates for revision, only refers to the logical relations between belief sets that can be obtained from an original belief set through revisions by various sentences. It consists of the following two postulates. \[ \text{If } K^* \alpha \vdash \neg \beta, \text{ then } K^* \alpha^* \beta = K^* \beta \tag{a} \] \[ \text{If } K^* \alpha \nvdash \neg \beta, \text{ then } K^* \alpha^* \beta = K^* (\alpha \& \beta) \tag{b} \] Unfortunately these postulates have problems in terms of their intuitive interpretation. Counterintuitive results are obtainable if (a) is combined with the following very plausible property of revision: \[ \text{If } K \nvdash \neg \alpha, \text{ then } K^* \alpha = \text{Cn} \bigl(K \cup \{\alpha\} \bigr) \tag{v} \] (v) follows from two of the basic Gärdenfors postulates (vacuity and inclusion), that the author subscribes to. To see why the combination of (a) and (v) is problematic, let \(\alpha\) denote that there is life on Mars and \(\beta\) that Bob is a Scotsman. For simplicity, let us assume that \(K= \text{Cn} (\{ \neg \beta\})\), i.e., that in the original belief state the only beliefs are the sentence \(\neg \beta\) and its logical consequences. Clearly, \(K^* \alpha = \text{Cn} (\{\alpha, \neg \beta\})\), and it follows from (a) that \(K^* \alpha^* \beta = K^* \beta\). On the other hand, it seems equally inescapable that \(K^*\beta = \text{Cn} (\{\beta\})\), contrary to the intuitively reasonable assumption that \(K^* \alpha^* \beta = \text{Cn} (\{\alpha, \beta\})\). (A similar example can be found in a recent paper of \textit{A. Darwiche} and \textit{J. Pearl} [``On the logic of iterated belief revision'', Artif. Intell. (to appear)]. Furthermore, the following counter-intuitive property (c) follows from (a) and (v): \[ \text{If } K \text{ is consistent and finite-based, and } K \vdash \neg \beta, \text{ then } K^* \beta = \text{Cn} \bigl(\{\eta\} \bigr). \tag{c} \] (A belief set is finite-based iff it is the logical closure of some finite set.) Proof: Since \(K\) is finite-based, there is a finite set \(\{k_1,\dots,k_n\}\) such that \(K = \text{Cn} (\{k_1, \dots, k_n\})\). Let \(k\) denote the conjunction \(k_1 \& \dots\& k_n\). Then \(K = \text{Cn} (\{k\})\). It follows from (v) that \(K = \text{Cn} (\emptyset)^*k\). We can use (a) to obtain \(K^* \beta = \text{Cn} (\emptyset)^* k^* \beta\), and then again (v) to obtain \(\text{Cn} (\emptyset)^* \beta = \text{Cn} (\{\beta\})\). However, (as was pointed out to the reviewer by Veronica Becher) (c) does not hold for the author's construction. To see this, just consider a model with only four worlds with decreasing degrees of implausibility, and such that \(\alpha \& \beta\) is true in the first (most implausible) world, \(\alpha \& \neg \beta\) in the second, \(\neg \alpha \& \beta\) in the third and \(\neg \alpha \& \neg \beta\) in the fourth (least implausible). It turns out that (a) does not hold either. Its subformula \(K^* \alpha\) is not fully well-defined. A belief set \(K\) may be the intersection of the minimal worlds of two distinct revision models \(M_1\) and \(M_2\), such that the intersection of the minimal worlds of \(M_1{}^* \alpha\) does not coincide with the intersection of the minimal worlds of \(M_2{}^* \alpha \). It may be tempting to write \(K^*\alpha\) to denote the belief set corresponding to \(M_1{}^* \alpha\), since this notation allows postulates to be written in the same style as the AGM postulates (like (a) and (b) above), but as we have seen this notation is misleading. As was also observed by Veronica Becher, a fully precise and correct version of (a) can be written: \[ \text{If } \neg \beta \in s(M^* \alpha), \text{ then } s(M^* \alpha^* \beta) = s(M^* \beta), \] where \(s\) is the support function [the reviewer, ``In defense of the Ramsey test'', J. Philos. 89, 522-540 (1992)] that assigns to every belief state the belief set that it supports.