Epistemic-entrenchment Characterization of Parikh’s Axiom

1 Introduction

Belief Revision is the study of knowledge in flux. The article that is widely considered to mark the birth of the field 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, identified 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 fill. We examine new constraints on sentences, that characterize precisely the class of epistemic entrenchments, corresponding to revision functions, satisfying the weak version of axiom (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 finite set of propositional variables P. We define 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 define 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 satisfied by all worlds in V ; i.e., t(V ) = {φ ∈ L : r |= φ, for all r ∈ V }. If V = ∅, then we define 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, defined 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 defined 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 CnL′ (Γ) denotes the logical closure of Γ in L′ ; i.e., CnL′(Γ) = Cn(Γ) ∩L′ . It is clear that the operation is relative to the original language L, when no subscript is present.

Finally, some definitions on preorders. A preorder (e.g., ⪯) 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′ }.

3 The AGMParadigm

In this section, we shall briefly review the axiomatic approach of the AGM paradigm, as well as two explicit constructions for this process; the first 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 ∗ (φ ∧ψ).

1 That means that Lχ contains a sentence that is logically equivalent to χ, and, moreover, no proper sublanguage of Lχ contains such a sentence.

2 It 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 first 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 satisfies 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:

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 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 defined as follows:

3 To 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].

4 Axiom (P) will be discussed, in details, later in this article.

5 The construction model, introduced by Katsuno and Mendelzon, is basically a subsequent reformulation of Grove's system of spheres [Grove, 1988].

Intuitively, ⪯ represents a plausibility ranking over possible worlds: the more plausible a world r is, the lower it appears in the ranking. Hence, (⪯ ∗) essentially defines 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):

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 agent's beliefs can be subdivided into disjoint compartments, referring to different subject matters, and that when revising, the agent modifies only the compartment(s) affected by the new information:

6 To 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 finitely many propositional variables.

• (P) If K = Cn(χ, ψ), where χ, ψ are sentences of disjoint sublanguages L1, L2, respectively, and φ ∈ L1, then K∗φ = (CnL1 (χ)⋄φ)+ψ, 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 first reading, i.e., the weak version of axiom (P), which we denote (wP), the revision function ⋄ that modifies 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 (sP), 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:

In the same work, both versions of axiom (P) - or, equivalently, conditions (wP) and (sP) - 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 (wP), for the special case of complete theories, is the following condition:

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 satisfied 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 (wP) for the special case of complete theories - in terms of epistemic entrenchments has been done in [Peppas et al., 2000]. In this article, we provide such a characterization for the general case of incomplete theories.

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

4.2 Possible-world Characterization for the General Case

To elevate the possible-world characterization of (wP) for the general case, an extension of the definition 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., ⋃ 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 finest Ksplitting (denoted by F); i.e., one which refines every other K-splitting. 8

Under the above, the extended definition of Diff is as follows: Diff (K, r) = ⋃{Fi ∈ F : for some φ ∈ LFi ,K |= φ and r |= ¬φ}. Note that, in the special case of a consistent complete theory K, the above definition of Diff collapses to the one given for (SP).

Having defined Diff, the appropriate possible-world characterization of (wP), 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 (wP) - 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 first introduce some more notation.

Let K be a consistent and (possibly) incomplete theory of L, and let F = {F1, . . . , Fn} be the finest 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}.

8 A partition Q′ refines 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 definitions 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 suffices 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 define 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 θ ⊆ L⋃ 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 defines 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 defines 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 defined 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 define 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 ψ inK, 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 all minimal support sets for φ in K is equal to the set of all minimal support sets for ψ in K; i.e., SS(φ) = SS(ψ).

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

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 define 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 definitions, 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 φ ≡⋃ 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 finest 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 φ ≡⋃ 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 λ ∈ L⋃ SS(φ) (e.g., λ = ¬a ∨ b), such that λ |= φ and λ ⊭ ψ (and thus φ ̸≡⋃ 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

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 L⋃ 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 L⋃ SS(φ) = L⋃ SS(ψ). For such sentences, (EP2) states that they ought to be equally entrenched.

10 Note 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). ⪯ satisfies (Q1) - (Q2) iff ≤ satisfies (EP1) - (EP2).

Proof.

( ⇒ )

Suppose that ⪯ satisfies (Q1) and (Q2).

For (EP1), assume that, for any two contingent sentences φ, ψ ∈ L, φ ◁ ψ and φ ≡⋃ 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 φ ≡⋃ SS(φ) ψ, it follows that {r ∩ L⋃ SS(φ) : for all r ∈ [¬φ]} = {r′ ∩L⋃ SS(φ) : for all r′ ∈ [¬ψ]}, hence there is a world r ∈ [¬φ], such that r agrees with r′ on all propositional variables in L⋃ 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 L⋃ 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 φ ≡⋃ SS(φ) ψ. We need to show that φ ≃ ψ. If L⋃ SS(φ) = L⋃ SS(ψ) = L, then φ ≡ ψ, and therefore trivially φ ≃ ψ. Assume, therefore, that L⋃ SS(φ) = L⋃ SS(ψ) ⊂ L.

Consider any world r, such that r ∈ [¬φ]. Clearly, there is a cut θ for φ in K, such that r |= ¬θ (see Footnote 11). Since φ ≡⋃ SS(φ) ψ, it follows that {r ∩ L⋃ SS(φ) : for all r ∈ [¬φ]} = {r′ ∩ L⋃ SS(φ) : for all r′ ∈ [¬ψ]}, hence there is a world r′ ∈ [¬ψ], such that r′ agrees with r on all propositional variables in L⋃ SS(φ) = L⋃ SS(ψ), and with a K-world on the remaining variables (see Footnote 12). If r agrees with a K-world too, on all propositional variables in L-L⋃ 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-L⋃ 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. ( ⇐ )

11 Assume, on the contrary, that r′ |= θ′ , for all cuts θ′ for ψ in K. Observe that {θ′ : such that θ′ is a cut for ψ inK} = ⋃ SS(ψ). Therefore r′ |= ⋃ SS(ψ), hence r′ |= ψ. Contradiction.

12 Let Si be the set of worlds in [¬φ], that satisfy the i-th element of R = {r ∩ L⋃ SS(φ) : for all r ∈ [¬φ]}. Clearly, ⋃ i∈R Si = [¬φ]. It suffices to show that there is a world, in every

Si, such that it agrees with a K-world, on all propositional variables in L - L⋃ 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-L⋃ SS(φ), such that K |= ν and w |= ¬ν. Clearly then, there is a sentence ζ ∈ L -L⋃ SS(φ), such that K |= ζ and t(Si) |= ¬ζ. However, ∨ i∈R t(Si) ≡ ¬φ, hence there is a sentence

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

Suppose that ≤ satisfies (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 LDiff (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 LDiff (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 φ ≡⋃ 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 LDiff (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 LDiff (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 φ ≡⋃ 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 (wP) - 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 significant for other related domains of Artificial 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 (wP) - 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]. Briefly, 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 satisfies the priority consistency condition, reported in [Rott, 1991], where Rott has shown that it is a necessary and sufficient 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 (sP).

Acknowledgments

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

13 A 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 finite.