# epistemicentrenchment_characterization_of_parikhs_axiom__93855981.pdf

Epistemic-entrenchment Characterization of Parikh s Axiom

Theofanis Aravanis1, Pavlos Peppas1,2, Mary-Anne Williams2

1University of Patras, Greece 2University of Technology Sydney, Australia {taravanis, pavlos}@upatras.gr, Mary-Anne.Williams@uts.edu.au

In this article, we provide the epistemicentrenchment characterization of the weak version of Parikh s relevance-sensitive axiom for belief revision known as axiom (P) for the general case of incomplete theories. Loosely speaking, axiom (P) states that, if a belief set K can be divided into two disjoint compartments, and the new information φ relates only to the ﬁrst compartment, then the second compartment should not be affected by the revision of K by φ. The above-mentioned characterization, essentially, constitutes additional constraints on epistemicentrenchment preorders, that induce AGM revision functions, satisfying the weak version of Parikh s axiom (P).

1 Introduction Belief Revision is the study of knowledge in ﬂux. The article that is widely considered to mark the birth of the ﬁeld is the seminal work of Alchourr on, G ardenfors, and Makinson, reported in [Alchourr on et al., 1985]. This work has given rise to a formal framework, now known as the AGM paradigm (or simply AGM), after the initials of its three founders. Part of the AGM paradigm is a set of rationality postulates for belief revision, known as the AGM postulates for revision. Parikh, recently, identiﬁed that the AGM postulates for revision are rather liberal in their treatment of the notion of relevance. More precisely, according to Parikh, a rational agent does not change her entire belief corpus during belief revision, but only the portion of it that is relevant to the new information. To fully capture this intuition of local change, Parikh introduced an additional axiom, named (P), in [Parikh, 1999]. Despite all the research on axiom (P), only recently it has been characterized in terms of possible worlds [Peppas et al., 2004; 2015]. Nevertheless, such a characterization in terms of epistemic entrenchments has not been formulated yet, for the general case of incomplete theories only for the special case of a complete theory as an initial belief set, in [Peppas et al., 2000]. This is the gap that the present article aims to ﬁll. We examine new constraints on sentences, that characterize precisely the class of epistemic entrenchments, corresponding to revision functions, satisfying the weak version of ax-

iom (P) (in addition to AGM postulates for revision), for the general case of incomplete theories. The paper is structured as follows. The next section introduces some notation and terminology. We then present some background material on the AGM paradigm and the notion of relevance (Sections 3 and 4). In Section 5, we characterize precisely the weak version of axiom (P) in terms of epistemic entrenchments, for the general case of incomplete theories. In the last section, we make some concluding remarks.

2 Formal Preliminaries

Throughout this article, we work with a ﬁnite set of propositional variables P. We deﬁne L to be the propositional language generated from P (using the standard Boolean connectives , , , , , and the special symbol ) and governed by classical propositional logic. A literal is a propositional variable p P or its negation. For any set of propositional variables Q P, by Q we denote the set containing all literals induced by Q; i.e., Q = Q { p : p Q}. For any set of literals Q P , by Q we denote the disjunction of the literals in Q. A sentence φ L is contingent iff φ and φ. For a set of sentences Γ of L, we denote by Cn(Γ) the set of all logical consequences of Γ, i.e., Cn(Γ) = {φ L : Γ |= φ}, and by Γ the set of all the negative elements of Γ. We shall write Cn(φ1, φ2, . . . , φn), for sentences φ1, φ2, . . . , φn, as an abbreviation of Cn({φ1, φ2, . . . , φn}). For any two sentences φ, ψ, we shall write φ ψ iff Cn(φ) = Cn(ψ). A theory K of L is any set of sentences of L closed under |=; i.e., K = Cn(K). A theory K is complete iff, for all sentences φ L, φ K or φ K. For a theory K and a set of sentences Γ of L, we denote by K + Γ the closure under |= of K Γ; i.e., Cn(K Γ). For a sentence φ L, we shall write K + φ as an abbreviation of K + {φ}. We deﬁne a possible world r (or simply a world), to be a consistent set of literals, such that for any propositional variable p P, either p r or p r. The set of all possible worlds is denoted by M. For a set of sentences Γ of L, [Γ] denotes the set of all possible worlds that satisfy Γ; i.e., [Γ] = {r M : r |= Γ}. We often use the notation [φ] for a sentence φ L, as an abbreviation of [{φ}]. For a set of worlds V M, we denote by t(V ) the set of sentences satisﬁed by all worlds in V ; i.e., t(V ) = {φ L : r |= φ, for

Proceedings of the Twenty-Sixth International Joint Conference on Artiﬁcial Intelligence (IJCAI-17)

all r V }. If V = , then we deﬁne t(V ) = L. It is easy to observe that t(V ) is always a theory. We often consider sublanguages of L. Let Q be a subset of the set of propositional variables P. We denote by LQ the sublanguage of L, deﬁned over Q. In the limiting case where Q is empty, we take LQ to be the language generated by and the Boolean connectives. For a sentence χ of L, we denote by Lχ the minimal sublanguage of L, within which χ can be expressed.1 If χ is inconsistent, we take Lχ to be L .2 Moreover, by Pχ we denote the propositional variables in the minimal language of χ, and by Lχ the language LP Pχ. Lastly, for a set of sentences Γ of L, LΓ denotes the minimal sublanguage of L, within which all the sentences of Γ can be expressed. Furthermore, we shall often project operations deﬁned above for the entire language L, to one of its sublanguages L . When this is the case, all notation will be subscripted by the sublanguage L . For instance, for a set of sentences Γ, the term Cn L (Γ) denotes the logical closure of Γ in L ; i.e., Cn L (Γ) = Cn(Γ) L . It is clear that the operation is relative to the original language L, when no subscript is present. Finally, some deﬁnitions on preorders. A preorder (e.g., ) over a set V is any reﬂexive, 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 }.

3 The AGM Paradigm In this section, we shall brieﬂy review the axiomatic approach of the AGM paradigm, as well as two explicit constructions for this process; the ﬁrst is based on preorders over sentences (epistemic entrenchments), and the second on preorders over possible worlds (faithful preorders).

3.1 Belief Revision In the AGM paradigm, belief revision is modelled as a function , mapping a theory K and a sentence φ to the theory K φ. The AGM postulates for revision, motivated by the principle of minimal change, which appear to capture much of what characterizes rational belief revision, are listed below (see [G ardenfors, 1988] or [Peppas, 2008] for an extended discussion on the postulates):

(K*1) K φ is a theory of L. (K*2) φ K φ. (K*3) K φ K + φ. (K*4) If φ / K, then K + φ K φ. (K*5) K φ |= iff |= φ. (K*6) If φ ψ, then K φ = K ψ. (K*7) K (φ ψ) (K φ) + ψ. (K*8) If ψ / K φ, then (K φ) + ψ K (φ ψ).

1That means that Lχ contains a sentence that is logically equivalent to χ, and, moreover, no proper sublanguage of Lχ contains such a sentence. 2It is easy to verify that, for every χ, Lχ is unique see [Parikh, 1999] for details.

3.2 Epistemic Entrenchments Apart from the above axiomatic approach to belief revision, a number of explicit constructions for this process have been proposed. The ﬁrst constructive model that we discuss here has been proposed by G ardenfors and Makinson, [G ardenfors and Makinson, 1988], and it is based on the notion of epistemic entrenchment. Formally, an epistemic entrenchment, related to a theory K of L, is a binary relation in L, that satisﬁes the following postulates (see [G ardenfors, 1988] or [Peppas, 2008] for an extended discussion on the postulates):

(EE1) For all φ, ψ, χ L, if φ ψ and ψ χ, then φ χ. (EE2) For all φ, ψ L, if φ |= ψ, then φ ψ. (EE3) For all φ, ψ K, φ φ ψ or ψ φ ψ. (EE4) When K = L, φ / K iff φ ψ, for all ψ L. (EE5) If ψ φ for all ψ L, then |= φ.

Note that, from the above postulates, it follows that every epistemic entrenchment is a total preorder in L. Intuitively, an epistemic entrenchment , related to a theory K, represents the relative epistemic loss caused by the removal of a belief from K; that is, the higher a belief is in the epistemic-entrenchment preorder , the more is lost in terms of epistemic value by its removal from K. Consequently, for any two formulas φ and ψ, such that φ ψ, whenever a choice exists between giving up φ and giving up ψ, the former will be surrendered, in order to minimize the epistemic loss. Formally, the idea of an epistemic entrenchment determining the result of belief revision is captured by the following condition:

( ) ψ K φ iff either φ < φ ψ or |= φ.

G ardenfors and Makinson, [G ardenfors and Makinson, 1988], proved that the family of functions over theories constructed from epistemic entrenchments by means of ( ) is precisely the class of AGM revision functions (i.e., the functions satisfying the postulates (K*1) (K*8)).3 The aim of this article is to characterize the subclass of epistemic entrenchments, that induce revision functions satisfying the weak version of axiom (P)4 (in addition to (K*1) (K*8)), for the general case of incomplete theories.

3.3 Faithful Preorders Another popular construction introduced by Katsuno and Mendelzon, [Katsuno and Mendelzon, 1991], is based on total preorders over possible worlds, called faithful preorders.5 For a theory K, a preorder over possible worlds is said to be faithful to K iff it is total and such that the minimal

3To be precise, G ardenfors and Makinson established a connection between epistemic entrenchments and contraction functions, in [G ardenfors and Makinson, 1988]. However, thanks to the Levi Identity, the connection with revision functions, mentioned above, follows directly. Note that ( ) appears in [Lindstr om and Rabinowicz, 1991; Rott, 1991]. 4Axiom (P) will be discussed, in details, later in this article. 5The construction model, introduced by Katsuno and Mendelzon, is basically a subsequent reformulation of Grove s system of spheres [Grove, 1988].

Proceedings of the Twenty-Sixth International Joint Conference on Artiﬁcial Intelligence (IJCAI-17)

worlds (with respect to ) are those satisfying K; i.e., min(M, ) = [K].6 Given a preorder that is faithful to K, the revision of K by any sentence φ can be deﬁned as follows:

( ) K φ = t(min([φ], )).

Intuitively, represents a plausibility ranking over possible worlds: the more plausible a world r is, the lower it appears in the ranking. Hence, ( ) essentially deﬁnes K φ as the theory corresponding to the most plausible worlds, satisfying the new information φ. Katsuno and Mendelzon proved that the functions induced from faithful preorders are precisely those satisfying the AGM postulates for revision. For ease of presentation, throughout this article we shall not consider the limiting cases of an inconsistent belief set and/or epistemic input, nor a tautological epistemic input. Hence, from now, unless explicitly stated otherwise, we assume that the initial belief set K is a consistent theory, and that the epistemic input φ is a contingent sentence (i.e., neither a tautology, nor a contradiction). Finally, given the connection between faithful preorders and revision functions, which in turn are connected to epistemic entrenchments, it should in principle be possible to establish a direct connection between faithful preorders and epistemic entrenchments. Indeed, this connection is expressed by the following condition (throughout this paper, the symbols r and r always represent possible worlds):

(SE) For any two contingent sentences φ, ψ L, φ ψ iff, for some r [ φ], r r , for every r [ ψ].

The result below, that appears also in a slightly different way in [Peppas and Williams, 1995], follows almost immediately, connecting revision functions to epistemic entrenchments and faithful preorders.

Lemma 1. Let K be a theory of L, an epistemic entrenchment related to K, and a preorder faithful to K. Then, and correspond to the same revision function by means of ( ) and ( ), respectively, iff they satisfy condition (SE).

4 Relevance-sensitive Belief Revision

When revising a theory K by a sentence φ, it seems plausible to assume that only the beliefs that are relevant to φ should be affected, while the rest of the belief corpus remains unchanged. For example, an agent that is revising her beliefs about quantum mechanics is unlikely to revise her beliefs about Greek economy. This simple intuition is not fully captured in the AGM paradigm [Alchourr on et al., 1985]. In this sense, Parikh in [Parikh, 1999] introduced a new axiom, named (P), as a supplement to the AGM postulates. The main intuition that axiom (P) aims to capture is that an

6To be precise, in [Katsuno and Mendelzon, 1991], faithful preorders are associated to sentences rather than theories, since a belief set is represented as a sentence rather than a theory. However, the two approaches are equivalent, given that we are working with a language built over ﬁnitely many propositional variables.

agent s beliefs can be subdivided into disjoint compartments, referring to different subject matters, and that when revising, the agent modiﬁes only the compartment(s) affected by the new information:

(P) If K = Cn(χ, ψ), where χ, ψ are sentences of disjoint sublanguages L1, L2, respectively, and φ L1, then K φ = (Cn L1(χ) φ)+ψ, where is a revision operator of the sublanguage L1.

Parikh, in [Parikh, 1999], showed that (P) is consistent with the AGM postulates (K*1) (K*6) (known as the basic AGM postulates), while Peppas et al. in [Peppas et al., 2015] proved that axiom (P) is in fact consistent with all eight AGM postulates (K*1) (K*8). Furthermore, in [Peppas et al., 2015], it was shown that axiom (P) is open to two different interpretations. According to the ﬁrst reading, i.e., the weak version of axiom (P), which we denote (w P), the revision function that modiﬁes the relevant part of K call it the local revision function may vary from theory to theory, even when the relevant part Cn(χ) stays the same. That means that weak (P) allows the local revision function to be context-dependent. According to the second reading, i.e., the strong version of axiom (P), which we denote (s P), the local revision function becomes context-independent. To avoid ambiguity between the two versions, Peppas et al. recast axiom (P) in terms of the following two conditions, that make no reference to a local revision operator:

(w P) If K = Cn(χ, ψ), Lχ Lψ = , and φ Lχ, then (K φ) Lχ = K Lχ. (s P) If K = Cn(χ, ψ), Lχ Lψ = , and φ Lχ, then (K φ) Lχ = (Cn(χ) φ) Lχ.

In the same work, both versions of axiom (P) or, equivalently, conditions (w P) and (s P) were characterized in terms of possible worlds. Herein, we use the weak version of axiom (P), because it is much more general and intuitive.

4.1 Possible-world Characterization for the Special Case of Complete Theories

It turns out that the possible-world characterization of (w P), for the special case of complete theories, is the following condition:

(SP) If Diff (K, r) Diff (K, r ), then r r .

By Diff (K, r) is denoted the set of propositional variables, over which a consistent complete theory K and a world r disagree (i.e., the symmetric difference of the variables that are satisﬁed by K and r); that is, Diff (K, r) = ((K r) (r K)) P.7 Note that a characterization of condition (SP) and consequently of (w P) for the special case of complete theories in terms of epistemic entrenchments has been done in [Peppas

7Since K is a consistent complete theory, there is a world w, such that [K] = {w}.

Proceedings of the Twenty-Sixth International Joint Conference on Artiﬁcial Intelligence (IJCAI-17)

et al., 2000]. In this article, we provide such a characterization for the general case of incomplete theories.

4.2 Possible-world Characterization for the General Case

To elevate the possible-world characterization of (w P) for the general case, an extension of the deﬁnition of Diff was proposed in [Peppas et al., 2015], in order to cover comparisons between a world r and an arbitrary, possibly incomplete, theory K. This is accomplished, taking into account the concept of a K-splitting, that is central to Parikh s notion of relevance. Let K be a theory and Q = {Q1, . . . , Qn} a partition of P; i.e., S Q = P, Qi = , and Qi Qj = , for all 1 i = j n. We say that Q = {Q1, . . . , Qn} is a Ksplitting iff there exist sentences φ1 LQ1, . . . , φn LQn, such that K = Cn(φ1, . . . , φn). Parikh has shown in [Parikh, 1999] that, for every theory K, there is a unique ﬁnest Ksplitting (denoted by F); i.e., one which reﬁnes every other K-splitting.8 Under the above, the extended deﬁnition of Diff is as follows: Diff (K, r) = S{Fi F : for some φ LFi, K |= φ and r |= φ}. Note that, in the special case of a consistent complete theory K, the above deﬁnition of Diff collapses to the one given for (SP). Having deﬁned Diff, the appropriate possible-world characterization of (w P), for the general case, are the conditions (Q1) and (Q2) below:

(Q1) If Diff (K, r) Diff (K, r ) and Diff (r, r ) Diff (K, r) = , then r r . (Q2) If Diff (K, r) = Diff (K, r ) and Diff (r, r ) Diff (K, r) = , then r r .

Both conditions (Q1) and (Q2) are variants of (SP). Like (SP), both these conditions relate the plausibility of a world r to its difference Diff (K, r) from the initial belief set K.

5 Epistemic-entrenchment Characterization of Weak (P) for Incomplete Theories

We now proceed to our objective, which is to characterize the weak version of axiom (P) or, equivalently, condition (w P) in terms of epistemic entrenchments, for the general case of incomplete theories. This is accomplished, taking into account the K-splitting concept, as in the case of the possibleworld characterization for the general case. We ﬁrst introduce some more notation. Let K be a consistent and (possibly) incomplete theory of L, and let F = {F1, . . . , Fn} be the ﬁnest K-splitting. Then, there exist unique (modulo logical equivalence) sentences χ1 LF1, . . . , χn LFn, such that K = Cn(χ1, . . . , χn), with Lχi Lχj = , for all 1 i = j n. We call these sentences the units of K. Intuitively, the units of K can be regarded as the building blocks of K, with all other sentences of K following from them. The unit set of K, namely, the set of all units of K, is denoted by U; i.e., U = {χ1, . . . , χn}.

8A partition Q reﬁnes another partition Q iff, for every Q i Q , there is Qj Q, such that Q i Qj.

Consider now a sentence φ in L. A support set for φ in K is a set Γ of units of K, that entails φ; i.e., Γ U and Γ |= φ. A support set for φ in K is minimal iff no proper subset of it entails φ. The intuitive reading of the above and the following deﬁnitions is based on the view that the units of K are the primary beliefs. Thus for example, intuitively, a minimal support set for φ in K is a minimal set of units, that sufﬁces to justify the presence of φ in K. Note that the set of all minimal support sets for φ in K is denoted by SS(φ). In this sense, we deﬁne a cut for a sentence φ in K to be a minimal set of units, whose withdrawal from K will leave φ unsupported. Formally, a cut for φ in K is a set θ of units of K, θ U, such that U θ φ, and for every proper subset θ of θ, U θ |= φ. Since a cut θ for a sentence φ in K intersects every minimal support set for φ in K, it follows that θ LS SS(φ). At this point, it should be noted that the notions of support set and cut correspond to the notions of kernel and incision function, respectively, presented in [Hansson, 1994]. More precisely, Hansson provides in his article a natural nonrelational generalization of safe contraction [Alchourr on and Makinson, 1985], called kernel contraction. For this purpose, he deﬁnes a φ-kernel of Γ to be a minimal subset of a set of sentences Γ, that imply a sentence φ, and the kenrel set to be the set of all φ-kernels of Γ, denoted by Γ φ.9 Moreover, he also deﬁnes an incision function σ for Γ to be a function, that makes an incision into every φ-kernel of Γ, selecting sentences to be discarded. Then, kernel contractions are deﬁned as follows: given a set of sentences Γ, a sentence φ and an incision function σ for Γ, the kernel contraction of Γ by φ, denoted by Γ . σ φ, is equal to Γ σ(Γ φ). That is, Γ . σ φ can be obtained erasing from Γ the sentences cut by σ. Note, lastly, that the support sets and cuts presented herein refer to units of K, while Hansson s kernels and incision functions refer to arbitrary sentences. For this reason, support sets and cuts are compatible with Parikh s notion of relevance, while kernels and incision functions are not. We can now deﬁne that a sentence ψ is better supported than a sentence φ in K, which we denote by φ ψ, iff the following two conditions hold:

(i) For every minimal support set for φ in K, there is a minimal support set for ψ in K, such that the latter is a subset of the former; i.e., S SS(φ), Q SS(ψ), such that Q S.

(ii) There is a minimal support set for ψ in K, that is disjoint from every minimal support set for φ in K; i.e., R SS(ψ), such that R S = , S SS(φ).

In terms of cuts, a sentence ψ is better supported than a sentence φ in K iff, for every cut θ for ψ in K, there is a cut θ for φ in K, such that θ θ . Intuitively, ψ is better supported than φ in K, if whenever ones cuts enough links to disconnect ψ from the units of K, regardless of how this is done (there are, in general, more than one ways), φ also gets disconnected. Sentences φ and ψ are equally supported in K, which we denote by φ ψ, iff φ, ψ K, and, moreover, the set of

9In [Fuhrmann, 1991], kernels are called entailment sets.

Proceedings of the Twenty-Sixth International Joint Conference on Artiﬁcial Intelligence (IJCAI-17)

all minimal support sets for φ in K is equal to the set of all minimal support sets for ψ in K; i.e., SS(φ) = SS(ψ). In terms of cuts, sentences φ and ψ are equally supported in K iff φ, ψ K, and, moreover, the set of all cuts for φ in K is equal to the set of all cuts for ψ in K. For any two sentences φ, ψ L, we deﬁne that φ and ψ are logically equivalent modulo LΓ (where Γ is a set of sentences of L), which we denote by φ Γ ψ, iff, for every sentence λ LΓ, λ |= φ iff λ |= ψ. Clearly, if LΓ = L, then φ ψ. With the above deﬁnitions, we can formulate the counterparts of (Q1) and (Q2) for epistemic entrenchments. Consider an epistemic entrenchment , related to a consistent and (possibly) incomplete theory K. The conditions (EP1) and (EP2) below turn out to be the epistemic-entrenchment duplicate of (Q1) and (Q2):

(EP1) If φ ψ and φ S SS(φ) ψ, then φ < ψ. (EP2) If φ ψ and φ S SS(φ) ψ, then φ ψ.

To understand the intuition behind the above conditions, let us consider a concrete example, referring to condition (EP1); the same intuition applies for (EP2). Let K = Cn(a b, c d), where a, b, c, d are propositional variables. The ﬁnest K-splitting is F = {{a, b}, {c, d}}, and the unit set of K is U = {a b, c d}. Moreover, let φ = a b c d and ψ = a b c d. Then, SS(φ) = {{a b}} and SS(ψ) = {{a b}, {c d}}. Hence, we derive that φ ψ and φ S SS(φ) ψ, and according to the condition (EP1), it follows that φ < ψ. However, this is not the case for the sentences φ = a b c d and ψ = a b c d. Here, although SS(φ) = {{a b}} and SS(ψ) = {{a b}, {c d}} (and thus φ ψ), there is a sentence λ LS SS(φ) (e.g., λ = a b), such that λ |= φ and λ ψ (and thus φ S SS(φ) ψ). Hence, the relative order of φ, ψ, with respect to , is not constrained by (EP1). In the special case of a consistent complete theory as an initial belief set (i.e., [K] = {w}), (EP1) is equivalent to condition (EP) presented below which appears in [Peppas et al., 2000] as a constraint on sentences while (EP2) reduces to a vacuous condition.10

(EP) If φ ψ, then φ < ψ.

Condition (EP), basically, associates the epistemic entrenchment of a sentence, with the degree of support it has in a theory; the more supported a sentence is, the higher the sentence appears in the epistemic-entrenchment ordering. Both conditions (EP1) and (EP2) are variants of (EP). Indeed, the antecedent of (EP1) is stronger than the one of (EP), since it requires not only that ψ is better supported than φ in K, but, moreover, that φ and ψ are logically equivalent modulo LS SS(φ). Condition (EP2) is, also, in the spirit of (EP). It deals with the limiting case of two sentences φ and ψ, that are equally supported in K, and, moreover, they are logically equivalent modulo LS SS(φ) = LS SS(ψ). For such sentences, (EP2) states that they ought to be equally entrenched.

10Note that condition (EP) is, basically, a translation of (SP) in the realm of epistemic entrenchments.

Theorem 1 below establishes the connection between (Q1) (Q2) and (EP1) (EP2), and, thus, provides the epistemic-entrenchment characterization of the weak version of axiom (P), for the general case of incomplete theories.

Theorem 1. Let K be a consistent theory of L, a preorder faithful to K, and the epistemic entrenchment related to K, corresponding to by means of (SE). satisﬁes (Q1) (Q2) iff satisﬁes (EP1) (EP2).

Proof. ( ) Suppose that satisﬁes (Q1) and (Q2). For (EP1), assume that, for any two contingent sentences φ, ψ L, φ ψ and φ S SS(φ) ψ. We need to show that φ < ψ. Notice that from φ ψ it follows that ψ K. Therefore, if φ / K, (EP1) follows directly from (EE4). Assume, therefore, that φ K. Consider any world r , such that r [ ψ]. Clearly, there is a cut θ for ψ in K, such that r |= θ .11 Since φ S SS(φ) ψ, it follows that {r LS SS(φ) : for all r [ φ]} = {r LS SS(φ) : for all r [ ψ]}, hence there is a world r [ φ], such that r agrees with r on all propositional variables in LS SS(φ), and with a K-world on the remaining variables.12 Moreover, since φ ψ, for every cut θ for ψ in K, there is a cut θ for φ in K, such that θ θ (with LS SS(φ) θ ), from which we derive that r |= θ. Hence, it follows that Diff (K, r) Diff (K, r ) and Diff (r, r ) Diff (K, r) = , therefore from (Q1), it follows that r r . Finally, since for some r [ φ], r r , for every r [ ψ], we derive from (SE) that φ < ψ, as desired. For (EP2), assume that, for any two contingent sentences φ, ψ L, φ ψ and φ S SS(φ) ψ. We need to show that φ ψ. If LS SS(φ) = LS SS(ψ) = L, then φ ψ, and therefore trivially φ ψ. Assume, therefore, that LS SS(φ) = LS SS(ψ) L. Consider any world r, such that r [ φ]. Clearly, there is a cut θ for φ in K, such that r |= θ (see Footnote 11). Since φ S SS(φ) ψ, it follows that {r LS SS(φ) : for all r [ φ]} = {r LS SS(φ) : for all r [ ψ]}, hence there is a world r [ ψ], such that r agrees with r on all propositional variables in LS SS(φ) = LS SS(ψ), and with a K-world

11Assume, on the contrary, that r |= θ , for all cuts θ for ψ in K. Observe that {θ : such that θ is a cut for ψ in K} = S SS(ψ). Therefore r |= S SS(ψ), hence r |= ψ. Contradiction. 12Let Si be the set of worlds in [ φ], that satisfy the i-th element of R = {r LS SS(φ) : for all r [ φ]}. Clearly, S

i R Si = [ φ]. It sufﬁces to show that there is a world, in every

Si, such that it agrees with a K-world, on all propositional variables in L LS SS(φ). Now, assume, for contradiction, that there is no such world in Si. Then, for every world w in Si, there is a sentence ν L LS SS(φ), such that K |= ν and w |= ν. Clearly then, there is a sentence ζ L LS SS(φ), such that K |= ζ and t(Si) |= ζ. However, W

i R t(Si) φ, hence there is a sentence

ξ L LS SS(φ), such that K |= ξ and φ |= ξ (or ξ |= φ), from which it follows that K |= φ, through a sentence in L LS SS(φ). Contradiction.

Proceedings of the Twenty-Sixth International Joint Conference on Artiﬁcial Intelligence (IJCAI-17)

on the remaining variables (see Footnote 12). If r agrees with a K-world too, on all propositional variables in L LS SS(φ), then it follows that Diff (K, r) = Diff (K, r ) and Diff (r, r ) Diff (K, r) = , therefore from (Q2), r r . If r disagrees with all K-worlds, on some propositional variables in L LS SS(φ), then it follows that Diff (K, r ) Diff (K, r) and Diff (r , r) Diff (K, r ) = , therefore from (Q1), r r. In either case, we derive from (SE) that φ ψ. By a totally analogues argument, considering now any world r such that r [ ψ], we can also prove that ψ φ. Consequently, φ ψ as desired. ( ) Suppose that satisﬁes (EP1) and (EP2). For (Q1), assume that, for any two worlds r, r M, Diff (K, r) Diff (K, r ) and Diff (r, r ) Diff (K, r) = . We need to show that r r . If Diff (K, r) = , then r is consistent with K, and therefore r [K] (and of course r / [K]). Then, the faithfulness of entails (Q1). Assume, therefore, that Diff (K, r) = . Construct the sentence ψ as follows: ψ = ( r ). Clearly, K |= ψ and r |= ψ. Moreover, by construction, the only cut θ for ψ in K is the set of all units of K, that can be expressed in LDiﬀ(K,r ). Now, construct the sentence φ as follows: φ = ( r). Clearly, K |= φ and r |= φ. Moreover, by construction, the only cut for φ in K is the set of all units of K, that can be expressed in LDiﬀ(K,r). Since Diff (K, r) Diff (K, r ), it follows that, for every cut θ for ψ in K, there is a cut θ for φ in K, such that θ θ , in other words, φ ψ. By the construction of φ and ψ, and since Diff (r, r ) Diff (K, r) = , we derive that φ S SS(φ) ψ. Hence, from (EP1) it follows that φ < ψ. Finally, the construction of φ and ψ entails, also, that [ φ] = {r} and [ ψ] = {r }, hence from (SE), r r as desired. For (Q2), assume that, for any two worlds r, r M, Diff (K, r) = Diff (K, r ) and Diff (r, r ) Diff (K, r) = . We need to show that r r . If Diff (K, r) = P, then r = r and, therefore, (Q2) trivially holds. Moreover, if Diff (K, r) = , then r, r [K]. Then, the faithfulness of entails (Q2). Assume, therefore, that = Diff (K, r) P. Construct the sentence ψ as follows: ψ = ( r ). Clearly, K |= ψ and r |= ψ. Moreover, by construction, the only cut θ for ψ in K is the set of all units of K, that can be expressed in LDiﬀ(K,r ). Now, construct the sentence φ as follows: φ = ( r). Clearly, K |= φ and r |= φ. Moreover, by construction, the only cut for φ in K is the set of all units of K, that can be expressed in LDiﬀ(K,r). Since Diff (K, r) = Diff (K, r ), it follows that θ = θ (i.e., the set of all cuts for φ in K is equal to the set of all cuts for ψ in K), in other words, φ ψ. By the construction of φ and ψ, and since Diff (r, r ) Diff (K, r) = , we derive that φ S SS(φ) ψ. Hence, from (EP2) it follows that φ ψ. Finally, the construction of φ and ψ entails, also, that [ φ] = {r} and [ ψ] = {r }, hence from (SE), r r as desired.

6 Conclusion

It is clear that Parikh s relevance-sensitive axiom (P) can be, basically, considered as a very important axiom for rational belief revision, in addition to the AGM postulates (K*1)

(K*8). This is true, not only from a theoretical viewpoint, but also from the perspective of a successful implementation of an AGM belief revision system, for real-world applications. In this paper, we have provided the epistemicentrenchment characterization of the weak version of Parikh s relevance-sensitive axiom (P) or, equivalently, of condition (w P) for belief sets that are not necessarily complete. What is quite appealing about our results is that the conditions (EP1) and (EP2), that characterize precisely weak (P), are natural constraints on the relative retractability of sentences. Note that an equivalent condition to (EP1) (EP2), for the special case of consistent complete theories, appears in [Peppas et al., 2000]. The notion of language splitting seems intrinsic to any attempt to form a theory of anything at all. The assumption that we can ignore some aspects, while considering others, is inherent in almost all intellectual activity. As a consequence, the results reported herein could also be signiﬁcant for other related domains of Artiﬁcial Intelligence, where the notions of relevance and local change play an important role, such as description logics, ontology update and merging, spatiotemporal reasoning, legal reasoning, multi-agent systems revision, and many others. Lastly, we note that the epistemic-entrenchment characterization of (w P) contrary to its possible-world characterization, provided in [Peppas et al., 2015] is better alligned with the notion of ensconcement [Williams, 1992; 1993; 1994], in the context of belief base revision schemes [Nebel, 1998]. Brieﬂy, an ensconcement is a total preorder on a belief base B,13 that can be blown up to a full epistemic entrenchment , related to Cn(B). In other words, it is some sort of base for ; i.e., a (typically) concise representation of an epistemic entrenchment. An ensconcement ordering satisﬁes the priority consistency condition, reported in [Rott, 1991], where Rott has shown that it is a necessary and sufﬁcient condition for the extension of any total preorder to an epistemic entrenchment on Cn(B). Hence, ensconcement orderings are always extensible to epistemic entrenchments. Williams, in [Williams, 1993; 1994], provided an explicit construction of such an extension. Of course, these observations are crucial for a possible implementation of a successful AGM belief revision system, where one major obstacle is the large amount of information, that the user needs to provide to the system. We will conclude our work by pointing out that an interesting direction for future work would be to extend the epistemic-entrenchment characterization to cover the strong version of axiom (P) or, equivalently, condition (s P).

Acknowledgments

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

13A belief base B is a set of sentences of L, that is not (except as a limiting case) closed under logical consequence, and for all practical purposes it is in fact ﬁnite.

Proceedings of the Twenty-Sixth International Joint Conference on Artiﬁcial Intelligence (IJCAI-17)

References [Alchourr on and Makinson, 1985] Carlos Alchourr on and David Makinson. On the logic of theory change: Safe contractions. Studia Logica, 44:405 422, 1985. [Alchourr on et al., 1985] Carlos Alchourr on, Peter G ardenfors, and David Makinson. On the logic of theory change: Partial meet contraction and revision functions. Journal of Symbolic Logic, 50(2):510 530, 1985. [Fuhrmann, 1991] Andr e Fuhrmann. Theory contraction through base contraction. Journal of Philosophical Logic, 20(2):175 203, 1991. [G ardenfors and Makinson, 1988] Peter G ardenfors and David Makinson. Revisions of knowledge systems using epistemic entrenchment. In Proceedings of the 2nd Conference on Theoretical Aspects of Reasoning About Knowledge, pages 83 95, Paciﬁc Grove, California, 1988. Morgan Kaufmann. [G ardenfors, 1988] Peter G ardenfors. Knowledge in Flux Modeling the Dynamics of Epistemic States. MIT Press, Cambridge, Massachusetts, 1988. [Grove, 1988] Adam Grove. Two modellings for theory change. Journal of Philosophical Logic, 17(2):157 170, 1988. [Hansson, 1994] Sven Ove Hansson. Kernel contraction. Journal of Symbolic Logic, 59:845 859, 1994. [Katsuno and Mendelzon, 1991] Hirofumi Katsuno and Alberto Mendelzon. Propositional knowledge base revision and minimal change. Artiﬁcial Intelligence, 52(3):263 294, 1991. [Lindstr om and Rabinowicz, 1991] Sten Lindstr om and Wlodzimierz Rabinowicz. Epistemic entrenchment with incomparabilities and relational belief revision. In Andr e Fuhrmann and Michael Morreau, editors, The Logic of Theory Change, volume 465 of Lecture Notes in Artiﬁcial Intelligence, pages 93 126. Springer Berlin Heidelberg, Berlin, Heidelberg, 1991. [Nebel, 1998] Bernhard Nebel. How hard is it to revise a belief base? In Didier Dubois and Henri Prade, editors, Handbook of Defeasible Reasoning and Uncertainty Management Systems, Vol. 3: Belief Change, pages 77 145. Kluwer Academic, 1998. [Parikh, 1999] Rohit Parikh. Beliefs, belief revision, and splitting languages. In Lawrence S. Moss, Jonathan Ginzburg, and Maarten de Rijke, editors, Logic, Language and Computation, volume 2, pages 266 278. CSLI Publications, 1999. [Peppas and Williams, 1995] Pavlos Peppas and Mary-Anne Williams. Constructive modellings for theory change. Notre Dame Journal of Formal Logic, 36(1):120 133, 1995. [Peppas et al., 2000] Pavlos Peppas, Norman Foo, and Abhaya Nayak. Measuring similarity in belief revision. Journal of Logic and Computation, 10:603 619, 2000.

[Peppas et al., 2004] Pavlos Peppas, Samir Chopra, and Norman Foo. Distance semantics for relevance-sensitive belief revision. In Proceedings of the 9th International Conference on the Principles of Knowledge Representation and Reasoning, KR 04, pages 319 328, 2004. [Peppas et al., 2015] Pavlos Peppas, Mary-Anne Williams, Samir Chopra, and Norman Foo. Relevance in belief revision. Artiﬁcial Intelligence, 229:126 138, December 2015. [Peppas, 2008] Pavlos Peppas. Belief revision. In Frank van Harmelen, Vladimir Lifschitz, and Bruce Porter, editors, Handbook of Knowledge Representation, pages 317 359. Elsevier Science, 2008. [Rott, 1991] Hans Rott. A nonmonotonic conditional logic for belief revision. Part 1: Semantics and logic of simple conditionals. In Andr e Fuhrmann and Michael Morreau, editors, The Logic of Theory Change, volume 465 of Lecture Notes in Artiﬁcial Intelligence, pages 135 181. Springer Berlin Heidelberg, Berlin, Heidelberg, 1991. [Williams, 1992] Mary-Anne Williams. Two operators for theory bases. In Proceedings of the Australian Joint Conference on Artiﬁcial Intelligence, pages 259 265. World Scientiﬁc, 1992. [Williams, 1993] Mary-Anne Williams. Transmutations of Knowledge Systems. Ph D thesis, University of Sydney, Australia, 1993. [Williams, 1994] Mary-Anne Williams. On the logic of theory base change. In Craig Mac Nish, David Pearce, and Luis Pereira, editors, Logics in Artiﬁcial Intelligence European Workshop JELIA 94, volume 838 of Lecture Notes in Artiﬁcial Intelligence, pages 86 105. Springer-Verlag Berlin Heidelberg, 1994.

Proceedings of the Twenty-Sixth International Joint Conference on Artiﬁcial Intelligence (IJCAI-17)