Abstract
This is a discussion of the problem of extending the basic AGM belief revision theory to iterated belief revision: the problem of formulating rules, not only for revising a basic belief state in response to potential new information, but also for revising one’s revision rules in response to potential new information. The emphasis in the paper is on foundational questions about the nature of and motivation for various constraints, and about the methodology of the evaluation of putative counterexamples to proposed constraints. Some specific constraints that have been proposed are criticized. The paper emphasizes the importance of meta-information—information about one’s sources of information—and argues that little of substance can be said about constraints on iterated belief revision at a level of abstraction that lacks the resources for explicit representation of meta-information.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
Notes
See Grove (1988).
I discuss some of the potential confusions, in the context of a discussion of theories of non-monotonic reasoning, in Stalnaker (1994).
I think some of the issues about updating vs. revision would be clearer if sentences were more clearly distinguished from what they are used to say.
Any representation of cognitive states that uses this coarse-grained notion of proposition will be highly idealized. It will be assumed that agents know or believe all the logical consequences of their knowledge or beliefs. This is a familiar feature of all theories in this general ballpark, including probabilistic representations of degrees of belief. The syntactic formulations make an analogous idealization. There are various different ways of motivating the idealization, and of explaining the relation between theory and reality on this issue, but that is a problem for another occasion. Most will agree that the idealization has proved useful, despite its unrealistic character.
The usual formulation of the AGM theory, in the syntactic context, has eight postulates. One of them (that logically equivalent input sentences have the same output) is unnecessary in the model-theoretic context, since logically equivalent propositions are identical. Analogues of my AGM1 and AGM4 are, in the usual formulation, each separated into two separate conditions. Finally, the first of the usual postulates is the requirement that the output of the revision function is a belief set, which is defined as a deductively closed set of sentences. This is also unnecessary in the model theoretic context. In the syntactic formulation, there is no analogue of our B*: it is assumed that every consistent and deductively closed set of sentences is an admissible belief set.
Hans Rott discusses such theories in Rott (2001).
It should be emphasized that ranking functions of the kind I have defined are not the same as Wolfgang Spohn’s ranking functions. Or more precisely, they are a special case of Spohn ranking functions. Spohn’s ranking functions are richer structures than AGM ranking functions, since they allow the values of the function to be any ascending sequence of non-negative integers. In a Spohn function, it might happen that there are gaps in the ranking (a positive integer k such that some worlds have ranks greater than k, and some less, but none with rank k), and the gaps are given representational significance when the theory is extended to an iterated revision theory. But any Spohn ranking function determines a unique AGM structure, and any AGM structure determines a unique Spohn ranking function with no gaps. See Spohn (1988).
By “taking oneself to know” I do not intend a reflective state of believing that one knows, but just a cognitive state that is like knowledge in its consequences for action. I also think that in the idealized context of belief revision theory, it is appropriate to make the kind of transparency assumptions relative to which taking oneself to know, in the relevant sense, entails believing that one knows, but that is a controversial question that I need not commit myself to here.
So I am assuming a different conception of knowledge from that assumed by, for example, in Friedman and Halpern (1999). They assume that to take observations to be knowledge is to take them to be unrevisable. In terms of our notation, they are, in effect, identifying knowledge with what is true in all possible worlds in B*. Friedman and Halpern’s way of understanding knowledge is common in the computer science literature, but I think it is a concept of knowledge that distorts epistemological issues. See Stalnaker (2006) for a discussion of some of the questions about logics of knowledge and belief.
Gärdenfors and Rott (1995, p. 37).
Recall that a belief state consists of a pair of sets of possible worlds, B and B*, the first being a subset of the second. In the general case of a belief system, it will be important to consider the case where B* as well as B may take different values for different arguments of the belief system. But to simplify the discussion, I will assume for now that for any given belief system there is a fixed B* for that system.
As we defined AGM revision functions, the input proposition could be an impossible proposition (the empty set). In this vacuous limiting case, the postulates imply that the output is also the empty set. This was harmless in the simple theory. The empty set is not really a belief state, but it doesn’t hurt to call it one for technical purposes. But we need to do some minor cleaning up when we turn to the extension to a full belief system. One simple stipulation would be to require that in the empty ‘belief state’, the B* is also empty. Alternatively, one might restrict the input sequences to sequences of nonempty propositions, or in the general case where B* may change with changes in the belief state, to sequences of nonempty subsets of the relevant B*.
A pedantic qualification is needed to get this exactly right. In the case where B(α) is the set of all possible worlds of a certain rank greater than 0, the Boutilier rule, as stated, will result in a ranking function with a gap. If a simple AGM function is represented by a ranking function with no gaps, one needs to add that after applying the rule, gaps should be closed.
The ranking function representation is just a notational convenience. The theory, and all the DP constraints, could be stated without using numbers.
This rule holds on the assumption that α is a proposition that is not believed in the prior state. The revision rule becomes a contraction rule when the value of k is 0.
The proof is simple: By AGM2 (and the assumption that Ψ is an AGM− system),
1. If Ψ(β1, … β n ,ϕ)∩α∩ϕ ≠ Λ, Ψ(β1, … β n ,ϕ,α∩ϕ) = Ψ(β1, … β n ,ϕ)∩α∩ϕ
But by AGM1, Ψ(β1, … β n ,ϕ)∩α∩ϕ = Ψ(β1, … β n ,ϕ)∩α, so it follows from 1 that
2. If Ψ(β1, … β n ,ϕ)∩α ≠ Λ, Ψ(β1, … β n ,ϕ,α∩ϕ) = Ψ(β1, … β n ,ϕ)∩α
By (C1),
3. Ψ(β1, … β n ,ϕ,α∩ϕ) = Ψ(β1, … β n ,α∩ϕ)
Therefore, by 2 and 3,
4. If Ψ(β1, … β n ,ϕ)∩α ≠ Λ, Ψ(β1, … β n ,α∩ϕ) = Ψ(β1, … β n ,ϕ)∩α
But 4 is just the claim that AGM4 holds in all revision functions generated by Ψ.
Hild (1998, p. 334).
Darwiche and Pearl (1997, p. 11).
Thanks to Hans Rott for raising this issue in his comments on a version of this paper. The issue deserves more discussion.
Though not in as much detail as Rott provides about the example. One should consult his discussion in Rott (2004). He includes one additional scenario, since he aims to raise problems for six different principles, as well as more detail to the example. But I think my sketch of the example includes everything relevant to the issue I am raising about it.
Most of the principles Rott considers are weaker than AGM4, but entailed by the full set of AGM postulates.
Rott (2004, p. 230).
Ibid., p. 233.
Ibid., p. 233.
Ibid., p. 237.
An example with the structure of the example I will describe was originally given, in the context of a discussion of counterfactuals, in Ginsberg (1986). Ginsberg’s story was a variation on an old example used by Quine for a different purpose. Ginsberg’s example is discussed in Stalnaker (1994) and in Rott (2001, p. 188ff).
The example raises a problem for the basic AGM theory, and not just for the iteration rule, but as I suggested above, I think the postulate AGM4 is really an iteration principle, and should stand or fall with the DP rule, (C1).
Lehmann (1995).
The full AGM system requires a total ordering of the possibilities, so the assumption that neither HT nor TH has priority over the other implies that they are tied. It might be more reasonable to assume that they are incomparable (and that the ordering of possibilities is only a partial order). But all we need for the current argument is that both HT and TH have priority over TT.
I am assuming here that the conjunction of the two simultaneously received reports count as a single input, since the subject comes to believe, at one time, that both reports are true. One might question this assumption, but nothing the theory as it stands provides any constraint on what counts as a single input, or any resources for representing the independence of sources.
Here is the argument: Since HA contradicts TATB, Ψ(HAHB, TATB, HA) = Ψ(HAHB, HA) by (C2). But since HAHB entails HA, Ψ(HAHB, HA) = Ψ(HAHB).
References
Boutilier, C. (1996). Iterated revision and minimal change of conditional beliefs. Journal of Philosophical Logic, 25, 262–305.
Darwiche, A., & Pearl, J. (1997). On the logic of iterated belief revision. Artificial Intelligence, 89, 1–29.
Friedman, N., & Halpern, J. (1999). Belief revision: A critique. Journal of Logic, Language, and Information, 8, 401–420.
Gärdenfors, P., & Rott, H. (1995). Belief revision. In D. Gabbay, et al. (Eds.), Handbook of logic in artificial intelligence and logic programming IV: Epistemic and temporal reasoning (pp. 35–132). Oxford: Oxford University Press.
Ginsberg, M. (1986). Counterfactuals. Artificial Intelligence, 30, 35–80.
Grove, A. (1988). Two modellings for theory change. Journal of Philosophical Logic, 17, 157–170.
Hild, M. (1998). Auto-epistemology and updating. Philosophical Studies, 92, 321–361.
Lehmann, D. (1995). Belief revision, revised. In Proceedings of the Fourteenth International Joint Conference on Artificial Intelligence (pp. 1534–1540).
Rott, H. (1999). Coherence and conservativism in the dynamics of belief. Erkenntnis, 50, 387–412.
Rott, H. (2001). Change, choice and inference. Oxford Logic Guides (Vol. 42). Oxford: Clarendon Press.
Rott, H. (2004). A counterexample to six fundamental principles of belief formation. Synthese, 139b, 225–240.
Spohn, W. (1988). Ordinal conditional functions: A dynamic theory of epistemic states. In W. Harper & B. Skyrms (Eds.), Causation in decision, belief change and statistics (Vol. 2, pp. 105–134). Dordrecht: Reidel.
Stalnaker, R. (1994). What is a nonmonotonic consequence relation? Fundamenta Informaticae, 21(1/2), 7–12.
Stalnaker, R. (2006). On logics of knowledge and belief. Philosophical Studies, 120, 169–199.
Williamson, T. (2001). Knowledge and its limits. Oxford: Oxford University Press.
Acknowledgements
Thanks to the participants in the Konstanz workshop on conditionals and ranking functions, in particular to Thony Gillies, Franz Huber, Hans Rott and Wolfgang Spohn, for discussion of the issues about iterated belief revision and ranking functions, and for advice about the relevant literature. Thanks also to the editors and an anonymous referee for helpful comments and corrections. I am particularly grateful to Hans Rott, who gave me detailed comments and suggestions on a previous draft, leading to some revision of my beliefs about belief revision, and I hope to significant improvements in the paper.
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Stalnaker, R. Iterated Belief Revision. Erkenn 70, 189–209 (2009). https://doi.org/10.1007/s10670-008-9147-5
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10670-008-9147-5