Observations on Darwiche and Pearl's Approach for Iterated Belief Revision

1 Introduction

The celebrated "AGM paper", [Alchourr´on et al., 1985], laid the foundations of what is now called the AGM paradigm for belief revision [G¨ardenfors, 1988; Peppas, 2008]. Within this framework, the beliefs of an agent are modelled as a logical theory K, also called a belief set, epistemic input is represented as a logical sentence ϕ, and the revision of K by ϕ, denoted by K ∗ ϕ, is modelled as a function ∗ mapping theories and sentences to theories. Revision functions are constrained by eight postulates, the AGM postulates for revision, introduced to capture the notion of rationality in the context of belief change. The functions that satisfy these postulates are known as AGM revision functions.

One of the main shortcomings of the original AGM paradigm is its lack of any guidelines for iterated belief revision - see [Peppas, 2014] for a survey on this issue. Perhaps the most influential work addressing the problem of iterated revision, within the confines of the AGM paradigm, is Darwiche and Pearl's approach; for short, DP approach [Darwiche and Pearl, 1994]. In the DP approach, four new postulates were introduced, namely, the DP postulates, to regulate the process of iterated revision.

However, as originally introduced in [Darwiche and Pearl, 1994], not all the DP postulates were consistent with the AGM postulates for revision [Lehmann, 1995]. The inconsistency was later resolved in [Darwiche and Pearl, 1997], by defining revision functions to operate on belief states, rather than on belief sets. With the switch to belief states, Darwiche and Pearl modified the AGM postulates for revision accordingly; we shall refer to the functions satisfying these modified postulates as modified AGM revision functions.

Even so, the DP approach remains controversial. The criticism, typically, comes in the form of counter-examples in which the DP postulates produce unintuitive results; see, for example, [Konieczny and P´erez, 2000; Jin and Thielscher, 2007; Stalnaker, 2009]. One of the latest criticism constitutes the result of [Peppas et al., 2008], that points out a first conflict between each one of the DP postulates and Parikh's relevance-sensitive axiom (P), introduced in [Parikh, 1999] as an attempt to capture relevance in belief revision.

In this work, we make further observations on the DP approach. In particular:

• The main incompatibility result of [Peppas et al., 2008] has been proved assuming a set of propositional variables with fixed cardinality; hence, it is confined to only one type of modified AGM revision functions. Specifically, Peppas et al. proved their result for modified AGM revision functions defined over a propositional language built from only three variables, utilizing a particular theory of the language. Herein, we provide a fully-fledged incompatibility result between relevance-sensitive and iterated belief revision, extending the result of [Peppas et al., 2008] for any finite, non-empty set of propositional variables, as well as for any splittable or (non-trivially) confined theory. Hence, the possibility for modified AGM revision functions of any type to satisfy both axiom (P) and the DP postulates is excluded.
• The aforementioned incompatibility results imply significant corollaries for existing belief-change proposals. Parametrized Difference revision operators [Peppas and Williams, 2016; 2018], and their specialization Dalal's operator [Dalal, 1988], are incompatible with the DP approach. Moreover, the Independence postulate [Jin and

Thielscher, 2007] (that remedies problems with the DP postulates) and the well-known Spohn's conditionalization [Spohn, 1988] (restricted to revision scenarios) are incompatible with axiom (P).

• We discuss the relation between belief states and total preorders over possible worlds, and prove that the oneto-one correspondence between them is not sufficient to "cover" all possible revision policies aligned with the DP postulates. This result implies that a preference ordering (over worlds) is an insufficient structure for representing a belief state. This "non-reductionist" view was also recently supported in [Booth and Chandler, 2017; 2018], where relevant considerations were provided.

The rest of the paper is structured as follows. In the next section, we fix some notation and terminology. Then, assuming basic knowledge of the AGM paradigm, the DP approach is introduced. The subsequent section presents the fully-fledged incompatibility results between the DP postulates and axiom (P), whereas Section 5 presents their direct consequences. Section 6 studies the relation between belief states and total preorders over possible worlds. The last section is devoted to some concluding remarks.

2 Formal Preliminaries

Throughout this paper, we work with a finite, non-empty set of propositional variables P. We define L to be the propositional language generated from P, using the standard Boolean connectives, the special symbol ⊥ (Falsity), and governed by classical propositional logic. The logic is identified by its consequence operation Cn and/or by its inference relation |=; see [Alchourr´on et al., 1985] for their formal properties.

A sentence ϕ ∈ L is contingent iff ⊭ ϕ and ⊭ ¬ϕ. For a set of sentences Γ of L, Cn(Γ) denotes the set of all logical consequences of Γ; i.e., Cn(Γ) = {ϕ ∈ L : Γ |= ϕ}. We shall write Cn(ϕ1, . . . , ϕn) as an abbreviation of Cn({ϕ1, . . . , ϕn}). A theory (belief set) K of L is any set of sentences of L closed under Cn; i.e., K = Cn(K).

A literal is a propositional variable p ∈ P or its negation. We define a possible world (abbrev. world) r to be a consistent set of literals, such that, for any propositional variable p ∈ P, either p ∈ r or ¬p ∈ r. Sometimes, we treat a set of literals as a sentence, i.e., the conjunction of all its literals, leaving it to the context to resolve any ambiguity. The set of all possible worlds is denoted by M. For a sentence (set of sentences) ϕ, [ϕ] is the set of worlds at which ϕ is true. For a set of worlds V , th(V ) is the set of sentences (theory) satisfied by all worlds in V . If V = ∅, then we define th(V ) = L.

Let Q be a (strict) subset of P. We denote by LQ the sublanguage of L defined over Q. If Q = ∅, we take LQ to be the language generated by ⊥, and the Boolean connectives. For a sentence x of L, we denote by Lx the unique minimal sublanguage of L, within which we can write a sentence that is logically equivalent to x. If x is inconsistent or a tautology, we take Lx to be L∅. Moreover, Lx denotes the complement language of Lx; that is, the language built from the propositional variables that do not appear in Lx.

Lastly, some definitions on preorders. A preorder over a set V is any reflexive, transitive binary relation in V . The preorder ⪯ is called total iff, for all r, r′ ∈ V , r ⪯ r′ or r′ ⪯ r. We shall write r ≺ r′ iff r ⪯ r′ and r′ ⪯̸ r. We shall also write r ≈ r′ iff r ⪯ r′ and r′ ⪯ r. In addition, for any X ⊆ V , by min(X,⪯) we denote the set {r ∈ X : for all r′ ∈ X, if r′ ⪯ r, then r ⪯ r′ }.

For ease of presentation, we shall consider only consistent belief sets, and contingent epistemic input.

3 The DP Approach

One of the most influential proposals addressing the problem of iterated belief revision, that comply with the assumptions of the AGM paradigm, is the work of Darwiche and Pearl [Darwiche and Pearl, 1994]. This proposal was later modified in [Darwiche and Pearl, 1997], partially in response to a problem identified in [Lehmann, 1995]. 1 In the modified version, Darwiche and Pearl defined revision functions to operate on belief states (rather than on belief sets), and reformulated accordingly the AGM postulates for revision - hence, they slightly deviated from the AGM paradigm. 2 As stated, we shall call a function ◦ a modified AGM revision function iff it satisfies the modified AGM postulates for revision, to differentiate it from the one in the original AGM paradigm. Clearly, ◦ is a function that maps a belief state S and a sentence ϕ of L to a new belief state S ◦ ϕ.

Darwiche and Pearl did not fully specify what exactly they consider a belief state to be. What was clear from their exposition is that, to each belief state S, corresponds a belief set B(S), and, moreover, it is possible to assign the same belief set to different belief states. This latter feature of belief states is crucial for resolving the original inconsistency identified by Lehmann. Herein, although this is not required by the DP approach, we shall identify a belief state with a special kind of total preorder over all possible worlds, called faithful preorder, unless explicitly stated otherwise.

Definition 1 (Faithfulness, [Katsuno and Mendelzon, 1991; Darwiche and Pearl, 1997]). For a belief state S, a preorder ⪯S over the possible worlds of M is faithful to B(S) iff it is total, and such that the minimal worlds (with respect to ⪯S) are those satisfying B(S); i.e., min(M, ⪯S) = [B(S)].

Darwiche and Pearl proved that, for any revision function ◦ that satisfies the modified AGM postulates for revision, any belief state S and any ϕ ∈ L, the following condition, denoted by (⪯ ◦), holds: B(S ◦ ϕ) = th(min([ϕ], ⪯S)).

Given the aforementioned background, Darwiche and Pearl introduced four additional postulates, known as the DP postulates, to regulate the process of iterated revision.

• (DP1) If ϕ |= ψ, then B((S ◦ ψ) ◦ ϕ) = B(S ◦ ϕ).
• (DP2) If ϕ |= ¬ψ, then B((S ◦ ψ) ◦ ϕ) = B(S ◦ ϕ).
• (DP3) If ψ ∈ B(S ◦ ϕ), then ψ ∈ B((S ◦ ψ) ◦ ϕ).
• (DP4) If ¬ψ ̸∈ B(S ◦ ϕ), then ¬ψ ̸∈ B((S ◦ ψ) ◦ ϕ).

There is a one-to-one correspondence between (DP1)- (DP4) and the following constraints on possible worlds:

1 Lehmann showed that one of the DP postulates, as originally stated, was inconsistent with the AGM postulates for revision.

2 Due to space limitations, the modified AGM postulates for revision have been omitted; see [Darwiche and Pearl, 1997] for details.

• (R1) If r, r′ ∈ [ϕ], then r ⪯S r′ iff r ⪯S◦ϕ r′ .

4 Relevance and the DP Postulates

Despite relevance and iteration seem to be unrelated at first glance, dealing with different aspects of the revision process, it turns out that each one of the DP postulates is, in a strong sense, incompatible with Parikh's axiom (P).

4.1 Parikh's Notion of Relevance

Relevant change is not properly addressed in the classical AGM paradigm, as identified by Parikh [Parikh, 1999]. Accordingly, Parikh proposed a new axiom, named (P), to supplement the AGM postulates for revision. Axiom (P) was further analysed in [Peppas et al., 2015], where two different interpretations of it were identified, called the weak and the strong version of (P). 3 The weak version of (P), denoted by (wP), is sufficient for the promised results. Peppas et al. introduced (wP) in terms of belief sets. However, it can quite straightforwardly be recast in terms of belief states, simply by replacing K with B(S) and K ∗ ϕ with B(S ◦ ϕ):

Condition (wP) says that the revision of S by ϕ will not affect any belief content outside Lx. In order to present the possible-world characterization of (wP), as introduced in [Peppas et al., 2015], we need some additional terminology. 4

Definition 2 (Diff). The difference between two worlds w, r of M, denoted by Diff (w, r), is: Diff (w, r) = {p ∈ P : w |= p and r |= ¬p} ∪ {p ∈ P : w |= ¬p and r |= p}.

The definition of Diff can be extended to include the difference between a theory of L and a world of M. To this end, the subsequent definition is necessary.

Definition 3 (Theory Splitting, [Parikh, 1999]). Let K be a theory of L, and let Q = {Q1, . . . , Qn} be a partition of P; i.e., ⋃ Q = P, Qi ̸= ∅, and Qi ∩ Qj = ∅, for all 1 ⩽ i ̸= j ⩽ n. The set Q is a K-splitting iff there exist sentences ϕ1 ∈ LQ1 , . . . , ϕn ∈ LQn , such that K = Cn(ϕ1, . . . , ϕn).

For every theory K of L, there is a unique finest Ksplitting, denoted by F; i.e., one which refines every other K-splitting [Parikh, 1999]. 5

Definition 4 (Extended Diff, [Peppas et al., 2015]). Let K be a theory of L, and let F be the finest K-splitting. The difference between K and a world r of M, denoted by Diff (K, r), is: Diff (K, r) = ⋃{Fi ∈ F : for some ϕ ∈ LFi , K |= ϕ and r |= ¬ϕ}.

3 In the same work, it was shown that (P) is consistent with the full set of AGM postulates for revision.

4 For the epistemic-entrenchment characterization of (wP), refer to [Aravanis et al., 2017].

5 A partition Q′ refines another partition Q iff, for every Q′i ∈ Q′ , there is a Qj ∈ Q, such that Q′i ⊆ Qj .

In the special case of a complete theory K (i.e., [K] is a singleton), Definition 4 collapses to Definition 2. Having defined the extended Diff, the possible-world characterization of (wP) (in terms of belief states) is the following conditions:

Finally, and before proceeding with the incompatibility results, we introduce the following useful definition:

Definition 5 (Splittable/Confined Theory). Let K be a theory of L. Iff, for some contingent sentences x, y ∈ L, K = Cn(x, y) and Lx∩Ly = ∅, we shall say that K is splittable. Iff, for some contingent sentence x ∈ L, K = Cn(x) and Lx ⊂ L, we shall say that K is confined (to Lx).

Note that, if K is confined to a sublanguage L′ of L, it also "splits" between L′ and L′ ; the L′ part is trivial. Moreover, there is no sentence ξ ∈ L′ , such that K |= ξ.

4.2 Main Incompatibility Results

Theorem 1. Let K be any splittable theory of L. There exists a belief state S, associated with K, and a sentence ϕ of L, such that no modified AGM revision function ◦ satisfies (P) at S and S◦ϕ, in addition to any of the postulates (DP1)-(DP4).

Proof. Let K be any theory of L, such that, for some contingent sentences x, y ∈ L, K = Cn(x, y) and Lx ∩ Ly = ∅. We will show that there exists a belief state S associated with K, such that, for some sentence ϕ of L, the transition from ⪯S to ⪯S◦ϕ cannot obey the dictates of (SQ1)-(SQ2), in addition to the dictates of each one of (R1)-(R4).

To this end, consider any belief state S, such that B(S) = K, and assume that (SQ1)-(SQ2) and (R1)-(R4) are satisfied. Moreover, suppose that Fx, Fy are two elements of the finest B(S)-splitting, such that Fx, Fy contain propositional variables of Lx, Ly, respectively.

· Violation of (R1):

Let w be any B(S)-world. Consider a world r′′ , such that it disagrees with all B(S)-worlds on some propositional variables in Fx and in Fy (i.e., r′′ ∩LFx ̸= w′ ∩LFx and r′′ ∩ LFy ̸= w′ ∩ LFy , for all w′ ∈ [B(S)]), and it agrees with w on the remaining variables (if any, namely, in case P - (Fx ∪ Fy) ̸= ∅). Then, Diff (B(S), r′′ ) = Fx ∪ Fy, and thus r′′ /∈ [B(S)]. 6 Moreover, consider the two worlds r, r′ , such that r = (r′′ ∩LFx )∪(w∩LP-Fx ) and r′ = (r′′ ∩ LFy ) ∪ (w ∩ LP-Fy ) (see Figure 1). 7

6 To see that Diff (B(S), r′′ ) contains the propositional variables of Fx, observe that, by the choice of r′′ , there is a sentence ξ ∈ LFx (i.e., ξ = r′′ ∩LFx ), such that K |= ¬ξ and r′′ |= ξ. The same applies for Fy. To see that Diff (B(S), r′′ ) contains only the propositional variables of Fx and Fy, suppose towards contradiction that this is not the case (of course, in case P - (Fx ∪ Fy) ̸= ∅). Then, there is a sentence ζ ∈ LP-(Fx∪Fy) , such that K |= ζ and r′′ |= ¬ζ. This again entails that w |= ζ, contradicting the fact that w and r′′ agree on the variables outside Fx ∪ Fy.

7 It is not hard to verify that the worlds r, r′ , r′′ indeed exist.

Then, Diff (B(S), r) = Fx, Diff (B(S), r′ ) = Fy (see Footnote 6), and thus r, r′ /∈ [B(S)].

Therefore, we derive that Diff (B(S), r) ⊂ Diff (B(S), r′′ ) and Diff (r, r′′ ) ∩ Diff (B(S), r) = ∅, and Diff (B(S), r′ ) ⊂ Diff (B(S), r′′ ) and Diff (r′ , r′′ ) ∩ Diff (B(S), r′ ) = ∅. Then from (SQ1), it follows that r ≺S r′′ and r′ ≺S r′′ . Since Diff (B(S), r) ∩ Diff (B(S), r′ ) = ∅, (SQ1)-(SQ2) place no constraints on the relative order of r and r′ , with respect to ⪯S (these two worlds are Diff-incomparable).

Now, consider the particular belief state, and call this S from now on, where it holds that r ≺S r′ ≺S r′′ . Define ϕ to be the sentence ϕ = r ∨ r′ ∨ r′′ . According to the definition of ⪯S, there is only one ⪯Sminimal ϕ-world, namely r; therefore from (⪯ ◦), it follows that [B(S ◦ ϕ)] = {r}. Then, again by the choice of r′ , r′′ , we derive that Diff (B(S ◦ ϕ), r′′ ) = Diff (r, r′′ ) ⊂ Diff (B(S ◦ ϕ), r′ ) = Diff (r, r′ ). Hence, no matter what the new faithful preorder ⪯S◦ϕ is, as long as it satisfies (SQ1), it holds that r′′ ≺S◦ϕ r′ .

However, given that r′ , r′′ ∈ [ϕ] and r′ ⪯S r′′ , (R1) entails that r′ ⪯S◦ϕ r′′ . Contradiction.

· Violation of (R2):

Consider the three worlds r, r′ , r′′ /∈ [B(S)] of the previous case. As stated, the fact that r ≺S r′′ and r′ ≺S r′′ holds for any belief state S associated with K. Define ϕ to be the sentence ϕ = r. Therefore from (⪯ ◦), it follows that [B(S ◦ ϕ)] = {r}. Then, we derive that Diff (B(S ◦ ϕ), r′′ ) = Diff (r, r′′ ) ⊂ Diff (B(S ◦ ϕ), r′ ) = Diff (r, r′ ). Hence, no matter what the new faithful preorder ⪯S◦ϕ is, as long as it satisfies (SQ1), it holds that r′′ ≺S◦ϕ r′ .

However, given that r′ , r′′ ∈ [¬ϕ] and r′ ⪯S r′′ , (R2) entails that r′ ⪯S◦ϕ r′′ . Contradiction.

· Violation of (R3) and (R4):

Assume the aforementioned three worlds r, r′ , r′′ /∈ [B(S)], and consider again the particular belief state S where r ≺S r′ ≺S r′′ . Defining ϕ = r ∨ r′ , we can derive the desired contradictions, with a totally analogous reasoning. ■

A stronger incompatibility result concerning postulate (DP2) can be established as well. First however, the following definition regarding confined theories is introduced.

Definition 6 (Non-Trivially Confined Theory). We shall say that a theory K of L is non-trivially confined iff K is confined to a sublanguage L′ of L, and, moreover, L′ contains at least two propositional variables.

Clearly, if a theory of L is non-trivially confined, then the set P contains at least three propositional variables.

Theorem2. Let K be any splittable or non-trivially confined theory of L, and let S be any belief state, associated with K. There exists a sentence ϕ of L, such that no modified AGM revision function ◦ satisfies (P) at S and S ◦ ϕ, in addition to postulate (DP2).

Proof. The proof is divided into two parts. The first part corresponds to the case of any splittable theory K, such that, for some contingent sentences x, y ∈ L, K = Cn(x, y) and Lx ∩ Ly = ∅. The second part corresponds to the case of any non-trivially confined theory K, such that, for some contingent sentence x ∈ L, K = Cn(x) and Lx ⊂ L.

Part I: Splittable Theory - K = Cn(x, y)

This part of the proof is identical to the proof of Theorem 1, concerning the violation of (R2), as the fact that r ≺S r′′ and r′ ≺S r′′ holds for any belief state S associated with any splittable theory K.

Part II: Non-Trivially Confined Theory - K = Cn(x)

We will show that, for any belief state S associated with K, there exists a sentence ϕ of L, such that the transition from ⪯S to ⪯S◦ϕ cannot obey the dictates of (SQ1)-(SQ2), in addition to the dictates of (R2).

To this end, consider any belief state S, such that B(S) = K, and assume that (SQ1)-(SQ2) and (R2) are satisfied. Since B(S) is non-trivially confined to Lx, it follows that Lx contains at least two propositional variables, and, moreover, there exist at least four worlds outside [B(S)], such that they agree on all propositional variables in Lx.

Let r be a world outside [B(S)]. Consider the world r′ /∈ [B(S)], such that it agrees on all propositional variables with r, except from one variable of Lx. Moreover, consider the world r′′ /∈ [B(S)], such that it agrees on all propositional variables with r′ , except from one variable of Lx, and r′′ ̸= r (see Figure 2). 8 Then, by the choice of r, r′ , r′′ (that they are outside [B(S)] and agree on all propositional variables in Lx) and since theory B(S) knows nothing about Lx (i.e., there is no sentence ξ ∈ Lx, such that B(S) |= ξ), we have that ∅ ̸= Diff (B(S), r) = Diff (B(S), r′ ) = Diff (B(S), r′′ ) ⊆ Lx, Diff (r, r′ ) ∩ Diff (B(S), r) = ∅, and Diff (r′ , r′′ ) ∩ Diff (B(S), r′ ) = ∅. Hence from (SQ2), r ≈S r′ ≈S r′′ .

Now, define ϕ to be the sentence ϕ = r. Therefore from (⪯ ◦), it follows that [B(S ◦ϕ)] = {r}. Then, by the choice of r, r′ , r′′ , we derive that Diff (B(S ◦ϕ), r′ ) = Diff (r, r′ ) ⊂ Diff (B(S ◦ϕ), r′′ ) = Diff (r, r′′ ). Hence, no matter what the new faithful preorder ⪯S◦ϕ is, as long as it satisfies (SQ1), it holds that r′ ≺S◦ϕ r′′ .

However, given that r′ , r′′ ∈ [¬ϕ] and r′ ≈S r′′ , (R2) entails that r′ ≈S◦ϕ r′′ . Contradiction. ■

8 It is not hard to verify that the worlds r, r′ , r′′ indeed exist.

Theorems 1 and 2, essentially, entail that there exists no modified AGM revision function of any type, satisfying Parikh's relevance-sensitive axiom (P) in addition to the DP postulates.

5 Corollaries

The incompatibility results of the previous section affect other existing belief-revision proposals.

5.1 Parametrized Difference Revision Operators

Parametrized Difference revision operators (abbrev. PD operators) is an important family of operators, recently introduced in [Peppas and Williams, 2016; 2018] as a generalization of Dalal's concrete revision operator [Dalal, 1988]. It was shown in [Peppas and Williams, 2016] that PD operators satisfy (wP). 9 Thus, in view of Theorems 1 and 2, we obtain immediately the following two corollaries: 10

Corollary 1. Parametrized Difference revision operators are inconsistent with the DP postulates.

Corollary 2. Dalal's revision operator is inconsistent with the DP postulates.

PD operators, as well as Dalal's operator, are based on a simple and intuitive construction, and they are the only among a series of popular operators (including the ones in [Borgida, 1985], [Winslett, 1988] and [Satoh, 1988]) that satisfy the full set of (modified) AGM postulates for revision. Obviously, having such "well-behaved" revision operators violating the DP postulates is a major drawback.

5.2 The Independence Postulate

The Independence postulate (Ind) was introduced to remedy problems with the DP ones [Jin and Thielscher, 2007].

The possible-world characterization of (Ind) is as follows:

It has been shown in [Jin and Thielscher, 2007] that (Ind) implies both (DP3) and (DP4); hence, the following corollary is an immediate consequence of Theorem 1.

Corollary 3. Parikh's axiom (P) is inconsistent with the Independence postulate (Ind).

9 In [Aravanis et al., 2019], it was shown that PD operators satisfy strong (P) as well.

10 Although PD operators and Dalal's operator were introduced in terms of belief sets, they can straightforwardly be recast in terms of belief states, as it was done for conditions (wP) and (SQ1)-(SQ2).

5.3 Spohn's Conditionalization

Spohn uses a quantitative structure for representing a belief state, related to a belief set. He calls this structure ordinal conditional function (OCF) [Spohn, 1988].

Definition 7 (OCF, [Spohn, 1988]). An OCF κ is a function from the set M of possible worlds to the class of ordinals, such that at least one world is assigned the ordinal 0.

Intuitively, κ assigns a plausibility grading to worlds; the larger κ(r) is for a world r, the less plausible r is. This plausibility grading can be extended to sentences; i.e., for any contingent sentence ϕ ∈ L, κ(ϕ) = min({κ(r) : r ∈ [ϕ]}). Lastly, the most plausible worlds define the belief set B(κ) that κ is related to; i.e., B(κ) = th({r ∈ M : κ(r) = 0}).

Given an OCF κ, the new information ϕ, and the degree of firmness d ⩾ 0 with which ϕ is incorporated into the new OCF κ · 〈ϕ, d〉, Spohn's conditionalization is as follows:

Darwiche and Pearl showed that (DP1)-(DP4) are satisfied by Spohn's proposal, restricted to the principal case of revision scenarios (where κ(ϕ) > 0, κ(¬ϕ) = 0 and d > 0) [Darwiche and Pearl, 1997]. Roughly speaking, this was achieved by constructing an OCF-based revision operator, herein denoted by ⋄, and proving that ⋄ satisfies (DP1)-(DP4) (in addition to the modified AGM postulates for revision). 11

Therefore, in view of Theorems 1 and 2, we obtain immediately the following result, that indicates the inconsistency between Spohn's conditionalization (as expressed by means of ⋄) and Parikh's relevance-sensitive axiom (P).

Corollary 4. Revision operator ⋄ does not satisfy axiom (P).

6 Belief States and Total Preorders

A belief state represents the current beliefs of an agent. Furthermore, it contains preference information which guides the revision process. This information is usually represented by a total preorder over all possible worlds. In this section, we study the relation between belief states and total preorders.

With the assumption that each total preorder of the language is associated with exactly one belief state, there is a set Σ of belief states, such that it contains belief states that are in a one-to-one correspondence with the preorders. We shall say that such a set Σ is a simple set of belief states.

On the other hand, if each preorder is associated with finitely many belief states, then more belief states arise (since two distinct belief states could be associated with the same preorder), which are contained in a "wider" (and obviously not simple) set Σ′ of belief states, such that |Σ| < |Σ′ |.

Clearly then, there are two sets R and R′ of modified AGM revision functions satisfying the DP postulates, and defined over the domains Σ and Σ′ , respectively.

Subsequently, we show that there exist revision policies encoded in the revision functions of R′ (hence, aligned with the DP postulates), that cannot be "captured" by means of the revision functions of R. This is accomplished in Theorem 3, utilizing the notion of "simulation" defined below.

11 See Theorem 14 in [Darwiche and Pearl, 1997] for more details.

Definition 8 (Simulation). Let Σ be a simple set of belief states, Σ′ be a "wider" set of belief states such that |Σ| < |Σ′ |, and ◦, ◦′ be two modified AGM revision functions defined over Σ, Σ′ , respectively. We shall say that ◦ simulates ◦′ iff there exists a function f from Σ′ to Σ, such that, for every belief state S′ ∈ Σ′ and for all sequences of sentences ϕ1, . . . , ϕn of L, it holds that B((S′ ◦′ ϕ1) ◦′ · · · ◦′ ϕn ) = B((f(S′ ) ◦ ϕ1) ◦ · · · ◦ ϕn ).

Informally, the function ◦ simulates the function ◦′ iff, for every belief state in Σ′ (the input of ◦′ ), there exists a belief state in Σ (the input of ◦), such that, for any sequence of sentences, ◦ and ◦′ present the same behaviour (with respect to the belief content of the resulting belief states).

Theorem 3. Let Σ be a simple set of belief states, and let Σ′ be a "wider" set of belief states, such that |Σ| < |Σ′ |. There exists a modified AGM revision function ◦′ satisfying the DP postulates, defined over Σ′ , that cannot be simulated by any modified AGM revision function ◦ satisfying the DP postulates, defined over Σ.

Proof. Assume that P = {a, b, c}, and that ⪯1, ⪯2, ⪯3 are the following three total preorders over the worlds of M: 12

Consider four belief states S1, S2, S3 and S4 of Σ′ . We assign at S1 and S4 the same preorder ⪯1, at S2 the preorder ⪯2, and at S3 the preorder ⪯3. For simplicity, we assume that each one of the remaining preorders over M is associated with exactly one belief state. Clearly then, Σ′ is not a simple set of belief states.

Suppose now that, for a modified AGM revision function ◦′ , defined over Σ′ , it holds that S1 ◦′ ¬a = S2, S2 ◦′ a = S4, and S4 ◦′ ¬a = S3, as depicted in Figure 3.

12 For the sake of readability, possible worlds are represented as sequences (rather than sets) of literals, and the negation of a propositional variable p is represented as p (instead of ¬p).

Next, we show that there is no modified AGM revision function satisfying the DP postulates, defined over the simple set of belief states Σ, that simulates ◦′ .

First, let us denote by Q1, Q2, Q3 the belief states of Σ that correspond to the preorders ⪯1, ⪯2, ⪯3, respectively.

Now, assume, towards contradiction, that there exists a modified AGM revision function ◦ satisfying (DP1)-(DP4), defined over Σ, that simulates ◦′ . It is not hard to verify that, in order for ◦ to simulate ◦′ , it must hold that Q1 ◦ ¬a = Q2 and Q2 ◦ a = Q1. Then, B((((Q1 ◦ ¬a) ◦ a) ◦ ¬a) ◦ (a ∨ ¬b ∨ ¬c)) = B(((Q2 ◦ a) ◦ ¬a) ◦ (a ∨ ¬b ∨ ¬c)) = B((Q1 ◦ ¬a) ◦ (a ∨ ¬b ∨ ¬c)) = B(Q2 ◦ (a ∨ ¬b ∨ ¬c)) = Cn((¬a ∧ ¬b ∧ c) ∨ (¬a ∧ b ∧ ¬c) ∨ (a ∧ b ∧ c)) ̸= B((((S1 ◦′ ¬a) ◦′ a) ◦′ ¬a) ◦′ (a ∨¬b ∨¬c)), which is clearly a contradiction. ■

Theorem 3 indicates that a total preorder over worlds is not a sufficient representation for a belief state, in order to achieve "full coverage" of DP-compliant revision policies. This "nonreductionist" thesis was also recently supported in [Booth and Chandler, 2017; 2018], where it is argued that "a preference ordering over the set of possible worlds provides insufficient structure to represent an agent's commitments to policies of iterated revision" [Booth and Chandler, 2017, p. 413].

7 Conclusion

In this article, important observations on the DP approach were pointed out. At first, we generalized the conflicts between relevance-sensitive and iterated belief revision, proving that there is no modified AGM revision function of any type, satisfying axiom (P) in addition to the DP postulates. These fully-fledged incompatibilities imply significant corollaries; PD operators and Dalal's operator are incompatible with the DP approach, as well as the Independence postulate and Spohn's conditionalization (restricted to revision scenarios) are incompatible with axiom (P). Lastly, we shed more light on the nature of belief states, by showing that a preference ordering (over possible worlds) is an insufficient structure for representing a belief state, as the DP postulates allow for more revision polices than the ones that can be captured by identifying belief states with total preorders over worlds.

Arguably, iteration and relevance play a central role in the revision process. The established results show that the dominant models for these two aspects of belief revision are in a deep conflict. Undoubtedly however, any comprehensive formal framework for belief change would need to consistently combine iterated and relevance-sensitive belief revision.

Finding ways to reconcile iteration and relevance - either by weakening the involved postulates or by following an entirely new approach - as well as identifying the exact nature of a belief state constitute imperative future tasks.

Acknowledgements

We are grateful to the anonymous reviewers for their insightful comments on this work.