Selective Credibility-Limited Belief Update Costas D. Koutras2
Theofanis Aravanis1, *
1 Department of Digital Systems School of Economics and Technology University of the Peloponnese Sparta 231 00, Greece [email protected] *
Corresponding author
arXiv:2607.28523v1 [cs.AI] 30 Jul 2026
2
College of Engineering and Technology American University of the Middle East Kuwait [email protected]
Abstract Belief update concerns changes in an agent’s beliefs induced by changes in the underlying world. Standard Katsuno–Mendelzon update assumes that an epistemic input can be incorporated from every initially possible world, whereas credibility-limited belief update restricts, for each source world, the successor worlds regarded as credible or reachable. Nevertheless, existing credibility-limited approaches treat the epistemic input as an indivisible whole, and therefore cannot represent cases in which only part of a compound epistemic input can be realized. We introduce selective credibility-limited belief update, in which the epistemic input is transformed, relative to each source world, into a weaker proxy before the credibilitylimited transition is performed. We provide semantic and axiomatic characterizations of the resulting class of update operators. We then identify two well-behaved sub-classes; namely, consistency-preserving update operators, which require every transformed epistemic input to be credible from its source world whenever the original epistemic input is consistent, and maximal consistency-preserving update operators, which additionally require the selected proxy to be maximally informative among the credible consequences of the original epistemic input. Finally, we establish the generality of the proposed framework by showing that credibilitylimited belief update is recovered as a special case, while Katsuno–Mendelzon belief update emerges when credibility restrictions are removed and the transformation functions are taken to be identities. These results demonstrate that the framework provides a unified and strictly more expressive account of belief update, encompassing established approaches while supporting source-dependent selective acceptance.
Keywords: Belief Update, Non-Prioritized Belief Change, Selective Acceptance, CredibilityLimited Belief Update, Knowledge Representation and Reasoning
1
T. Aravanis and C. D. Koutras
1
Selective Credibility-Limited Belief Update
Introduction
Belief change concerns the rational modification of an agent’s beliefs in response to new information [11]. A fundamental distinction is commonly drawn between belief revision, which is appropriate when the new information corrects the agent’s description of a fixed world [1, 14], and belief update, which is appropriate when the information reports a change in the world itself. Belief update was introduced in an early form by Keller and Winslett [18] and was subsequently given its standard axiomatic and semantic characterization by Katsuno and Mendelzon [17]. In the Katsuno–Mendelzon (KM) framework, each possible world (or simply world) compatible with the agent’s prior beliefs is treated as a possible initial state, and is equipped with an ordering of potential successor worlds. Updating by an epistemic input then amounts to selecting, from each initial world, the most plausible successor worlds satisfying that epistemic input. Standard KM belief update is a prioritized form of belief change, as the epistemic input is required to be incorporated into the resulting state of belief. This unconditional success requirement reflects the assumption that the reported change has occurred and must therefore be accommodated, even when doing so requires departing substantially from the agent’s previous beliefs. In many applications, however, an epistemic input may describe a transition that is physically impossible, causally inadmissible, unreliable, or otherwise unrealizable from some of the worlds regarded as initially possible. In such cases, unconditional priority is too demanding. Non-prioritized belief change relaxes the success requirement by allowing an epistemic input to be rejected or only partially accepted when it fails to meet the relevant admissibility conditions [8]. The resulting change operation is not required to accept every epistemic input in its entirety; instead, acceptance may depend on factors such as credibility, consistency, reliability, or reachability. In the update setting, this dependence is naturally source-relative, because an epistemic input may be realizable from one initially possible world but not from another. Therefore, a rational non-prioritized update mechanism must determine, for each source world, whether the reported transition can be accepted and how the corresponding branch should be treated when complete acceptance is not possible. The credibility-limited belief-update framework of Fermé et al. introduces source-relative credibility restrictions into belief update, by associating each source world with a restricted set of credible or reachable successors [12]. Only credible worlds of the epistemic input may be selected. Under the credibility-limited (CL) approach, a source branch contributes no successor when the epistemic input has no credible world, relative to that source world; consequently, unconditional success is retained, but consistency may fail. Consistent credibility-limited (CCL) belief update adopts the complementary policy of retaining the source world whenever the epistemic input cannot be credibly realized. This preserves consistency, but permits the epistemic input to be locally rejected. Thus, both mechanisms depart from standard KM belief update by making the treatment of each source branch dependent on source-relative credibility, although only CCL permits local rejection of the epistemic input. Although these approaches provide credibility-sensitive departures from standard KM belief update, they continue to treat the epistemic input as an indivisible whole. Relative to each source world, the complete epistemic input is either realized, rejected, or rendered ineffective through
2
T. Aravanis and C. D. Koutras
Selective Credibility-Limited Belief Update
the elimination of the corresponding branch. This all-or-nothing treatment is restrictive when the epistemic input expresses a compound change whose components need not be equally realizable. For example, suppose that a robot is instructed to move a cup to a table and fill it. If the cup is intact, both parts of the instruction may be executable. If the cup is broken, however, the robot may still be able to move it, while being unable to fill it. In such a real-world scenario, standard KM belief update may represent the complete instruction as successful by selecting a physically impossible successor. Credibility-limited belief update may instead eliminate the broken-cup branch, while its consistent variant may reject the instruction altogether and leave the cup in its original position. None of these outcomes represents the intermediate case in which only the executable part of the compound instruction is realized. The present article introduces selective credibility-limited belief update, abbreviated as SCL belief update, as a more flexible form of non-prioritized belief update. The framework builds on three principal lines of research; namely, the pointwise semantics of KM belief update [17], the credibility-limited belief-update models of Fermé et al. [12], and the transformation-based methodology developed for selective belief revision [10, 13]. Rather than requiring a source-relative choice between complete acceptance and complete rejection, SCL belief update permits the epistemic input to be transformed into a weaker proxy before the transition mechanism is applied. As a consequence, acceptance can vary not only between source worlds, but also in extent, as the same epistemic input may be fully accepted from one source world and selectively weakened from another. This makes it possible to represent the partial realization of compound epistemic inputs without either admitting non-credible successor worlds, eliminating the corresponding source branch, or leaving that branch entirely unchanged. The contributions of the article are both foundational and comparative. First, we provide semantic and axiomatic characterizations of SCL update operators, in terms of credible faithful assignments [12] and source-dependent transformation functions [10]. Second, we identify two progressively more constrained sub-classes. Consistency-preserving SCL update operators require the transformed epistemic input to be credible from its corresponding source world whenever the original epistemic input is consistent, thus ensuring that every initially possible world contributes at least one successor in such cases. Maximal consistency-preserving SCL update operators additionally require, for every consistent epistemic input, the selected proxy to be maximally informative among its credible consequences. Third, we isolate an unrestricted-credibility variant that captures selective belief update independently of credibility limitations. Finally, we locate the established KM, CL, and CCL approaches within the proposed framework; accordingly, CL belief update is recovered by means of identity transformations, CCL belief update by transformations that retain the source world whenever the epistemic input is not locally credible, and KM belief update by additionally removing credibility restrictions. We further establish that the principal inclusion relations among these classes are proper, showing that SCL belief update constitutes a strictly more expressive framework than the approaches it subsumes. Roadmap. The remainder of the article is organized as follows. Section 2 situates the proposed framework within the literature on non-prioritized belief change. Section 3 introduces the logical notation and preliminary results used throughout the article. Section 4 reviews the axiomatic and 3
T. Aravanis and C. D. Koutras
Selective Credibility-Limited Belief Update
semantic foundations of KM belief update. Section 5 presents CL and CCL belief update, and illustrates their limitations through a real-world cup scenario. Section 6 introduces SCL belief update and establishes its semantic and axiomatic characterization. Section 7 studies consistencypreserving and maximal consistency-preserving SCL update operators. Section 8 shows how KM, CL, and CCL belief update arise within the SCL hierarchy, and establishes the strictness of the corresponding inclusions. The final section summarizes the main results and outlines directions for future research.
2
Related Work
The proposed framework lies at the intersection of several lines of research on belief change and the partial realization of compound information. This section situates SCL belief update in relation to existing non-prioritized approaches to belief change and clarifies the respects in which it differs from them. Research on non-prioritized belief change has concentrated primarily on belief revision, giving rise to models in which incoming information may be rejected, partially accepted, or assessed according to different levels of credibility; see the recent survey by Fermé, Garapa, and Reis [8]. Among these models, selective revision is particularly relevant to the present work, since it allows an epistemic input to be replaced by a weaker proxy representing the part of the information that the agent is prepared to accept [10, 13]. Non-prioritized belief update has received comparatively less attention, although two distinct approaches have recently been developed within, or in close connection with, the KM framework. First, Grimaldi, Martinez, and Rodriguez introduce local promotion, an update counterpart of belief promotion [22], in which the new information need not receive unconditional priority [15]. Local promotion is represented through two underlying update operators and a trigger function that determines which part of the prior information may be preserved relative to the epistemic input. Therefore, its principal concern is the controlled preservation of old information when the prior state and the epistemic input are combined. Second, the credibility-limited belief-update framework of Fermé et al. associates each source world with a restricted set of credible or reachable successor worlds [12]. Under this approach, source-relative credibility determines whether the complete epistemic input has an admissible realization: CL eliminates a source branch when no such realization exists, whereas CCL retains the source world and thereby permits local rejection of the epistemic input. A related, but conceptually different, treatment of compound epistemic inputs is provided by the compositional belief update of Delgrande, Jin, and Pelletier [6]. Their operator recursively decomposes the syntactic structure of the update formula and combines the results obtained from its constituent sub-formulae. Hence, compositional belief update makes the internal structure of a compound epistemic input operationally significant and supports comparatively direct implementations. Nevertheless, it retains success for the complete epistemic input and, in its general form, does not satisfy the full set of standard KM postulates, including invariance under the substitution of logically equivalent update formulae. Therefore, its purpose is different from selective acceptance — it determines how a compound epistemic input is realized from its syntactic composition, rather than whether only a weaker part of that epistemic input should be accepted. 4
T. Aravanis and C. D. Koutras
Selective Credibility-Limited Belief Update
The present article addresses a distinct problem by combining the pointwise credibility restrictions of credibility-limited belief update [12], with the transformation-based methodology of selective revision [10]. In SCL belief update, the epistemic input is weakened semantically and independently at each source world before credible successor selection is performed. Unlike local promotion, SCL belief update does not obtain non-prioritization by combining separate contributions associated with the prior state and the new information; instead, it directly transforms the epistemic input into a source-relative proxy. Unlike compositional belief update, the transformation is invariant under logical equivalence and is not tied to the syntactic decomposition of the epistemic input. Consequently, SCL belief update can represent not only whether an epistemic input is accepted from a given source world, but also the extent to which it is accepted there, while excluding non-credible successor worlds. This idea also bears a conceptual affinity to partial-satisfaction planning, where an agent seeks valuable solutions when the complete set of objectives cannot be achieved, including recent extensions to hierarchical task-network planning [3]. The difference is that SCL belief update operates at the epistemic level, selecting a credible logical consequence of the epistemic input relative to each source world, rather than optimizing over subsets of planning objectives.
3
Formal Prelude
We assume a non-empty finite propositional signature P, and let L be the propositional language constructed from the atoms in P, using the standard Boolean connectives ¬, ∧, ∨, →, and ↔. All formulae are evaluated under classical propositional semantics, and |= denotes classical entailment. The symbol ⊤ denotes an arbitrary, but fixed, tautology. A possible world, or simply a world, is a truth assignment w : P 7→ {0, 1}. We shall identify w with the corresponding complete set of literals p ∈ P : w(p) = 1 ∪ ¬p : p ∈ P and w(p) = 0 . The collection of all possible worlds is denoted by M. Since P is finite, so is M. For readability, relative to a fixed ordering of the atoms, worlds will often be represented as sequences of literals, with set braces and commas omitted. Moreover, the negation of an atom a ∈ P may be written as ā; thus, for example, the world {a, ¬b, c} may be displayed as ab̄c. For every sentence φ ∈ L, we write [φ] = w ∈ M : w |= φ for the set of worlds satisfying φ. This notation n o extends to arbitrary sets of formulae Γ ⊆ L by [Γ] = w ∈ M : w |= γ, for every γ ∈ Γ . Two sentences φ, ψ ∈ L are logically equivalent, written φ ≡ ψ, iff they have the same worlds; that is, φ ≡ ψ iff [φ] = [ψ]. For Γ ⊆ L, its set of classical consequences is Cn(Γ) = φ ∈ L : Γ |= φ . For a sentence φ ∈ L, we use Cn(φ) as an abbreviation for Cn {φ} . A set K ⊆ L is called a theory, or belief set, whenever it is closed under classical consequence, that is, whenever K = Cn(K). A theory K is complete if [K] is a singleton. The expansion of a belief set K by a formula φ is denoted by K + φ, and is given by K + φ = Cn K ∪ {φ} . 5
T. Aravanis and C. D. Koutras
Selective Credibility-Limited Belief Update
Intuitively, expansion incorporates φ into K without removing any of the beliefs already contained in K, and then closes the resulting set under logical consequence. Let X ⊆ M. A binary relation ⪯ over X is a partial preorder, or simply a preorder, if it is reflexive and transitive. Its strict component ≺ is defined, for r, r′ ∈ X, by r ≺ r′ iff r ⪯ r′ and r′ ̸⪯ r. Given Y ⊆ X, the worlds in Y that are minimal according to ⪯ form the set n o min(Y, ⪯) = r ∈ Y : there exists no r′ ∈ Y such that r′ ≺ r . Finally, we record the following elementary property of minimal elements with respect to a partial preorder, which will be used in Subsection 6.2. Lemma 1. Let ⪯ be a partial preorder over X ⊆ M, and let A, B ⊆ X. If min(A, ⪯) ⊆ B and min(B, ⪯) ⊆ A, then min(A, ⪯) = min(B, ⪯). Proof. Suppose that min(A, ⪯) ⊆ B and min(B, ⪯) ⊆ A. We first show the inclusion min(A, ⪯) ⊆ min(B, ⪯). Let r ∈ min(A, ⪯). By min(A, ⪯) ⊆ B, we derive that r ∈ B. Suppose, towards a contradiction, that r ∈ / min(B, ⪯). Since M is finite, there exists r′ ∈ min(B, ⪯) such that r′ ≺ r. By min(B, ⪯) ⊆ A, we derive that r′ ∈ A. Hence, r′ ∈ A and r′ ≺ r, contradicting r ∈ min(A, ⪯). Therefore, r ∈ min(B, ⪯). Thus, min(A, ⪯) ⊆ min(B, ⪯). The reverse inclusion, min(B, ⪯) ⊆ min(A, ⪯), follows symmetrically. Consequently, min(A, ⪯) = min(B, ⪯), as desired. ■
4
Belief Update
Belief update is intended to model changes in an agent’s beliefs when the new information reports an evolution of the underlying world, rather than, as in belief revision, indicating that the agent’s previous description of an unchanged world was mistaken. Early foundations of this form of belief change were developed by Keller and Winslett [18], while its standard formal treatment was subsequently provided by Katsuno and Mendelzon [17]. In this section, we briefly recall the axiomatic characterization of Katsuno–Mendelzon (KM) belief update and its corresponding semantic representation.
4.1
Axiomatic Characterization
An update operator is a function ⋄ that maps each pair consisting of a theory K and a formula φ ∈ L to a theory K ⋄ φ. The formula φ is referred to as the epistemic input, while K ⋄ φ represents the agent’s resulting state of belief after the change described by φ is incorporated into K. The operator ⋄ is said to be a KM update operator precisely when it satisfies the KM postulates listed below [17].
6
T. Aravanis and C. D. Koutras
Selective Credibility-Limited Belief Update
(K ⋄ 1)
K ⋄ φ is a theory.
(K ⋄ 2)
φ ∈ K ⋄ φ.
(K ⋄ 3)
If φ ∈ K, then K ⋄ φ = K.
(K ⋄ 4)
If both K and φ are consistent, then K ⋄ φ is consistent as well.
(K ⋄ 5)
If φ ≡ ψ, then K ⋄ φ = K ⋄ ψ.
(K ⋄ 6)
K ⋄ (φ ∧ ψ) ⊆ (K ⋄ φ) + ψ.
(K ⋄ 7)
If ψ ∈ K ⋄ φ and φ ∈ K ⋄ ψ, then K ⋄ φ = K ⋄ ψ.
(K ⋄ 8)
If K is complete, then K ⋄ (φ ∨ ψ) ⊆ Cn (K ⋄ φ) ∪ (K ⋄ ψ) . T If [K] ̸= ∅, then K ⋄ φ = Cn(w) ⋄ φ .
(K ⋄ 9)
w∈[K]
Postulates (K⋄1)–(K⋄9) restate the standard Katsuno–Mendelzon conditions (U1)–(U8) for the setting in which epistemic states are represented by deductively closed theories [17, p. 189]. Since belief states are commonly represented in this way in the belief-change literature, we adopt the theory-based formulation throughout the article rather than the original formula-based presentation. The role of each postulate may be summarized as follows. Postulate (K ⋄ 1) ensures that every update result is closed under logical consequence, and (K ⋄ 2) imposes success by requiring the epistemic input to be fully accepted. Postulate (K ⋄ 3) states that no change occurs when the epistemic input is already believed, whereas (K ⋄ 4) preserves consistency whenever both the prior theory and the epistemic input are consistent. Postulate (K ⋄ 5) makes the operation insensitive to logically equivalent representations of the epistemic input. Postulate (K ⋄ 6) constrains the relation between updating by a conjunction and subsequently expanding by one of its conjuncts. Postulate (K ⋄ 7) identifies the outcomes of two updates when each epistemic input is accepted after updating by the other, and (K ⋄ 8) governs the treatment of disjunctive epistemic inputs when the initial theory is complete. Finally, (K ⋄ 9) captures the distinctive pointwise nature of belief update, by requiring the update of a consistent theory to be determined by the updates of the complete worlds compatible with it.
4.2
Semantic Characterization
Postulates (K ⋄ 1)–(K ⋄ 9) have a pointwise semantic characterization based on preference relations over possible successor worlds. More precisely, each world w that may describe the initial state is associated with its own partial preorder over M. This relation ranks the possible outcomes of a change relative to w: if r ≺w r′ , then r is regarded as a strictly more plausible successor of w than r′ . Definition 2 (Faithful Pointwise Assignment, [17]). A faithful pointwise assignment is a mapping that associates every world w ∈ M with a partial preorder ⪯w over M such that, for every r ∈ M distinct from w, w ≺w r. 7
T. Aravanis and C. D. Koutras
Selective Credibility-Limited Belief Update
Therefore, the faithfulness requirement makes the source world w strictly preferred to every other world in its associated preorder. Using these source-relative plausibility relations, the following representation theorem characterizes KM update operators semantically. Theorem 3 ([17]). An update operator ⋄ satisfies postulates (K ⋄ 1)–(K ⋄ 9) iff there exists a faithful pointwise assignment that maps every world w ∈ M to a partial preorder ⪯w over M, such that, for every belief set K and every sentence φ ∈ L, S (U) [K ⋄ φ] = min([φ], ⪯w ). w∈[K]
Condition (U) highlights the pointwise structure of KM belief update.1 To update a theory K by an epistemic input φ, each world w ∈ [K] is considered separately. From every such source world, the update mechanism selects the ⪯w -minimal worlds satisfying φ. The worlds of the resulting theory K ⋄ φ are then obtained by collecting the worlds selected from all source worlds compatible with K. Remark 4 (Consistency Assumption). Throughout the article, unless explicitly stated otherwise, we restrict attention to consistent prior belief sets. This restriction involves no loss of generality. Indeed, the only inconsistent belief set is L, and postulate (K ⋄ 3) entails that L ⋄ φ = L, for every epistemic input φ. Correspondingly, in each semantic representation considered herein, [L] = ∅, so the union indexed by the worlds of the prior belief set is empty, and therefore represents the inconsistent belief set L. Thus, all representation results extend immediately to the inconsistent prior case. The following running example, adapted from the cup-domain scenario of Fermé et al. [12], will be used throughout the article to illustrate the behaviour and limitations of the update mechanisms considered. We first examine the scenario under standard KM belief update, and subsequently revisit it in the context of credibility-limited and selective forms of belief update. Example 5 (Running Cup Scenario). Let t denote that the cup is on the table, e that the cup is empty, and b that the cup is broken. The agent’s initial state of belief is represented by K = Cn (t ∧ ¬e ∧ ¬b) ∨ (¬t ∧ e ∧ ¬b) ∨ (¬t ∧ e ∧ b) . Thus, [K] = {w1 , w2 , w3 }, where w1 = tēb̄, w2 = t̄eb̄, and w3 = t̄eb. According to w1 , the cup is on the table, non-empty, and intact; according to w2 , it is on the floor, empty, and intact; and according to w3 , it is on the floor, empty, and broken. Assume that a broken cup is necessarily empty and that brokenness is irreversible. These physical constraints will later be encoded by assigning a credible set Cw of worlds to each source world w ∈ {w1 , w2 , w3 } (see Definition 6): n o Cw1 = Cw2 = [b → e] = teb, teb̄, tēb̄, t̄eb, t̄eb̄, t̄ēb̄ and Cw3 = [b ∧ e] = {teb, t̄eb}. 1 This pointwise semantics contrasts with the standard possible-worlds semantics for belief revision, in which a single plausibility ordering is associated with the prior theory as a whole [16]. The semantic relationship between revision and update, and the precise nature of their differences, have been further investigated in [20, 2, 4].
8
T. Aravanis and C. D. Koutras
Selective Credibility-Limited Belief Update
A robot is instructed to move the cup to the table and fill it. The intended postcondition is φ = t ∧ ¬e,
with
[φ] = {tēb̄, tēb}.
The complete postcondition can be realized when the cup is intact. If the cup is broken, however, only its table-location component can be realized. Now, consider a KM update operator ⋄ whose pointwise preorders select min([φ], ⪯w1 ) = min([φ], ⪯w2 ) = {tēb̄}
and
min([φ], ⪯w3 ) = {tēb}.
Then, condition (U) yields [K ⋄KM φ] = {tēb̄, tēb}, and therefore, K ⋄KM φ = Cn(t ∧ ¬e). The world tēb ∈ [K ⋄KM φ] represents a cup that is both broken and non-empty. Thus, standard KM belief update guarantees acceptance of the complete postcondition, but does so at the cost of violating the physical constraint that every broken cup is empty.
5
Credibility-Limited Belief Update
Fermé et al. [12] modify the pointwise semantics of KM belief update by restricting, for each source world, the successor worlds that are regarded as credible or reachable. The resulting framework weakens standard KM belief update by restricting the admissible successors of each source world. Credibility-limited (CL) belief update retains formal success but may sacrifice consistency, whereas consistent credibility-limited (CCL) belief update preserves consistency by permitting the epistemic input to be rejected locally. Both approaches are based on the following semantic structure. Definition 6 (Credible Faithful Assignment, [12]). A credible faithful assignment is a mapping that associates every world w ∈ M with a pair (Cw , ⪯w ), where {w} ⊆ Cw ⊆ M, and ⪯w is a partial preorder over Cw such that, for every w′ ∈ Cw , if w′ ̸= w, then w ≺w w′ . The non-empty set Cw contains the worlds that are regarded as credible successors of w; therefore, worlds outside Cw are excluded as possible outcomes of a transition from w. The preorder ⪯w ranks the worlds in Cw according to their comparative transition plausibility. Faithfulness ensures that w is the uniquely most plausible element of its own credible set.
5.1
The CL Approach
CL belief update retains all the standard KM postulates (K ⋄ 1)–(K ⋄ 9), except consistency preservation, encoded in postulate (K ⋄ 4). Therefore, it requires the epistemic input to be accepted, but allows the updated belief set to become inconsistent when the epistemic input is not credibly realizable from the prior state of belief. Definition 7 (CL Update Operator, [12]). An update operator ⋄ is a CL update operator iff it satisfies postulates (K ⋄ 1)–(K ⋄ 3) and (K ⋄ 5)–(K ⋄ 9). 9
T. Aravanis and C. D. Koutras
Selective Credibility-Limited Belief Update
The corresponding representation theorem restricts the KM-style minimization process to the credible successors of each source world. Theorem 8 ([12]). An update operator ⋄ is a CL update operator iff there exists a credible faithful assignment w 7→ (Cw , ⪯w ), such that, for every belief set K and every sentence φ ∈ L, [ min [φ] ∩ Cw , ⪯w . (CL) [K ⋄ φ] = w∈[K]
Thus, each source world w ∈ [K] contributes its most plausible credible φ-successors. If [φ] ∩ Cw = ∅, the branch originating from w contributes no successor. In particular, if this occurs for every w ∈ [K], then the update result is inconsistent. The following continuation of Example 5 of the previous section illustrates how this local elimination of non-credible branches affects the update result. In particular, CL belief update avoids the physically impossible successor produced by standard KM belief update, but may do so by discarding an initially possible source branch altogether. Example 9 (Cup Scenario under CL Belief Update). Let ⋄CL be a CL update operator. Recall that the physical constraints of the scenario are encoded by the credible sets Cw1 = Cw2 = [b → e]
and
Cw3 = [b ∧ e].
Hence, for the source worlds w1 and w2 , the epistemic input φ = t ∧ ¬e has credible worlds, and min [φ] ∩ Cw1 , ⪯w1 = min [φ] ∩ Cw2 , ⪯w2 = {tēb̄}. For the broken-cup world w3 , however, [φ] ∩ Cw3 = ∅. Consequently, we have from condition (CL) that [K ⋄CL φ] = {tēb̄}, and hence, K ⋄CL φ = Cn t ∧ ¬e ∧ ¬b . Observe that CL belief update avoids the physically impossible successor tēb. However, the branch originating from w3 contributes no successor at all. That is to say, the result fails to represent the fact that, although the broken cup cannot be filled, it can still be moved to the table. The elimination of the entire source branch motivates the consistent variant considered in the next subsection, which preserves the branch but, as will be shown, still does not capture this partial realization.
5.2
The CCL Approach
CCL belief update adopts a different policy for locally non-credible epistemic inputs. Rather than eliminating a source branch, it leaves the corresponding source world unchanged. This restores consistency, but requires unconditional success to be replaced by a weaker, source-relative acceptance principle. Definition 10 (CCL Update Operator, [12]). An update operator ⋄ is a CCL update operator iff it satisfies postulates (K ⋄ 1), (K ⋄ 3)–(K ⋄ 9), together with the following postulates: 10
T. Aravanis and C. D. Koutras
Selective Credibility-Limited Belief Update
(RSC)
If K is complete, then φ ∈ K ⋄ φ or K ⋄ φ = K.
(SM)
If φ |= ψ and φ ∈ K ⋄ φ, then ψ ∈ K ⋄ ψ.
(IR)
If φ is inconsistent, then K ⋄ φ = K.
Postulate (RSC), relative success for complete theories, requires an update originating from a single source world either to accept the epistemic input or to leave that source world unchanged. Postulate (SM), success monotonicity, ensures that whenever an epistemic input is successfully accepted, its logical consequences are successfully accepted as well. Finally, postulate (IR) requires every inconsistent epistemic input to be rejected.2 The following representation theorem provides the corresponding semantic characterization of CCL belief update. Theorem 11 ([12]). An update operator ⋄ is a CCL update operator iff there exists a credible faithful assignment w 7→ (Cw , ⪯w ), such that, for every belief set K and every sentence φ ∈ L, (CCL)
[K ⋄ φ] =
[
gw (φ),
w∈[K]
where, for every w ∈ M and every φ ∈ L, min [φ] ∩ C , ⪯ , if [φ] ∩ C ̸= ∅, w w w gw (φ) = {w}, otherwise. Consequently, CL and CCL belief update coincide at every source world w for which the epistemic input has a credible world. They differ only when [φ] ∩ Cw = ∅; specifically, CL belief update discards the branch originating from w, whereas CCL belief update retains w, thus, representing the failure of the transition without eliminating the corresponding initial possibility. The running cup scenario illustrates this distinction. Example 12 (Cup Scenario under CCL Belief Update). Let ⋄CCL be a CCL update operator represented by the credible faithful assignment considered in Example 9. For the source worlds w1 and w2 , CCL belief update behaves exactly as CL belief update, since φ = t ∧ ¬e has credible worlds relative to both worlds. For the broken-cup world w3 , however, no credible world of φ is reachable. Hence, we derive that gw3 (φ) = {w3 } = {t̄eb}. Then, it follows from condition (CCL) that [K ⋄CCL φ] = {tēb̄, t̄eb}, and hence, K ⋄CCL φ = Cn (t ∧ ¬e ∧ ¬b) ∨ (¬t ∧ e ∧ b) . 2
Postulate (IR) is not stated explicitly in the axiomatization of CCL belief update presented in [12]. However, the proof of the corresponding representation theorem implicitly restricts attention to consistent epistemic inputs. We include (IR) herein to obtain the stated characterization over arbitrary epistemic inputs.
11
T. Aravanis and C. D. Koutras
Selective Credibility-Limited Belief Update
Thus, CCL belief update preserves the broken-cup branch but leaves it unchanged, thereby failing to realize any part of the compound postcondition on that branch. Consequently, the broken cup remains on the floor, even though moving it to the table is physically possible. The running example exposes a limitation shared by CL and CCL belief update. Both treat the compound epistemic input φ = t ∧ ¬e as an indivisible whole. When the complete epistemic input is not credible, CL belief update eliminates the corresponding source branch, whereas CCL belief update rejects the complete epistemic input and retains the source world. Neither mechanism captures the intermediate case in which only one component of the compound postcondition is realized. The selective framework introduced in the next section relaxes this all-or-nothing treatment.
6
Selective Acceptance in Credibility-Limited Belief Update
Having reviewed standard KM belief update and its credibility-limited generalizations, we now introduce selective acceptance into the update setting. As shown, the existing credibility-limited approach by Fermé et al. [12] continue to treat the epistemic input as an indivisible whole: relative to a source world, it is either fully realized, locally rejected by retaining the source world, or rendered ineffective by eliminating the source branch. This all-or-nothing treatment is inadequate for compound epistemic inputs whose components may differ in their credibility or executability. The basic idea is to interpose a transformation stage before the underlying belief-change mechanism is applied. In this respect, the proposed construction is the belief-update analogue of selective belief revision [10], in which an epistemic input is transformed into an acceptable proxy before being processed by a revision operator. In the update setting, however, the pointwise character of the KM semantics requires the accepted portion of the epistemic input to be determined relative to each source possible world. The semantic realization of this idea is developed below.
6.1
Semantic Characterization
Selective acceptance is represented by transforming the epistemic input before the credibilitylimited transition is performed. Accordingly, we associate each source world w with a transformation function fw . Given an epistemic input φ, the formula fw (φ) represents the part of φ that is accepted from w. The transition mechanism is then applied to this transformed epistemic input rather than directly to φ. This source dependence preserves the pointwise semantics of KM belief update, while allowing the extent of acceptance to vary across source worlds. Thus, the same epistemic input may be fully accepted from one source world, and weakened from another. The collection of source-dependent transformations is formalized by the following assignment. Definition 13 (Pointwise Transformation Assignment). A pointwise transformation assignment is a family F = {fw : w ∈ M}, where every fw : L 7→ L is a transformation function. For every source world w and epistemic input φ, the formula fw (φ) is intended to represent the information conveyed by φ that can be accepted from w. To capture this interpretation, a pointwise transformation assignment may satisfy the following basic properties.
12
T. Aravanis and C. D. Koutras
Selective Credibility-Limited Belief Update
(F1)
φ |= fw (φ).
(F2) (F3)
If φ ≡ ψ, then fw (φ) ≡ fw (ψ). fw fw (φ) ≡ fw (φ).
(F4)
If [φ] ∩ Cw ̸= ∅, then fw (φ) ≡ φ.
Properties (F1)–(F3) are adapted from corresponding conditions on transformation functions in selective belief revision [10, p. 335]. More specifically, they are the source-dependent counterparts of implication, extensionality, and idempotence, respectively. Property (F1) permits the transformation to discard information, but prevents it from introducing information not implied by the original epistemic input. Property (F2) guarantees that the transformation is insensitive to syntactic representation, while property (F3) requires the selected proxy to be a fixed point of the transformation. Property (F4) may be viewed as the source-relative credibility counterpart of weak maximality in selective belief revision [10, p. 335]. There, weak maximality requires the epistemic input to be retained unchanged whenever it is consistent with the prior belief set. Here, consistency with the prior belief set is replaced by local credibility from w — whenever [φ] ∩ Cw ̸= ∅, no weakening occurs and the epistemic input is accepted unchanged from w. A pointwise transformation assignment F and a credible faithful assignment w 7→ (Cw , ⪯w ) jointly determine the update process. For each source world w, the epistemic input φ is first transformed into the proxy fw (φ); the most plausible worlds in Cw satisfying that proxy are then selected according to the preorder ⪯w . Taking the union of these locally selected successors yields the updated belief set. This two-stage construction defines a selective credibility-limited update operator, abbreviated as an SCL update operator. Definition 14 (SCL Update Operator). An update operator ⋄ is an SCL update operator iff there exist a credible faithful assignment w 7→ (Cw , ⪯w ) and a pointwise transformation assignment F = {fw : w ∈ M} satisfying properties (F1)–(F4), such that, for every belief set K and every sentence φ ∈ L, [ (SCL) [K ⋄ φ] = min [fw (φ)] ∩ Cw , ⪯w . w∈[K]
The following continuation of the running cup scenario illustrates how source-dependent transformations allow a compound epistemic input to be only partially realized, thus, demonstrating the greater expressive capacity of SCL belief update relative to KM, CL, and CCL update. Example 15 (Cup Scenario under SCL Belief Update). Let ⋄SCL be an SCL update operator represented by the credible faithful assignment considered in Examples 9 and 12. Regard the epistemic input φ = t ∧ ¬e as a compound postcondition and consider the candidate proxies ⊤,
t,
¬e,
t ∧ ¬e.
For the source worlds w1 and w2 , the complete epistemic input is credible. Therefore, property (F4) gives fw1 (φ) ≡ φ and fw2 (φ) ≡ φ. 13
T. Aravanis and C. D. Koutras
Selective Credibility-Limited Belief Update
For the broken-cup world w3 , neither the complete epistemic input nor the component ¬e is credible, since [t∧¬e]∩Cw3 = ∅ and [¬e]∩Cw3 = ∅, respectively. The component t, however, is credible, as [t] ∩ Cw3 = {teb}. Accordingly, take the pointwisetransformation assignment F representing ⋄SCL to satisfy fw3 (φ) ≡ t. Since min [t] ∩ Cw3 , ⪯w3 = {teb}, condition (SCL) gives [K ⋄SCL φ] = {tēb̄, teb}. Equivalently, K ⋄SCL φ = Cn (t ∧ ¬e ∧ ¬b) ∨ (t ∧ e ∧ b) . Thus, from an intact-cup source world, the complete postcondition is realized. From the brokencup source world, only its table-location component is realized. Consequently, SCL belief update represents the partial realization of the compound postcondition.3 The different treatments of the broken-cup branch are summarized below: Update Mechanism Successor from w3
Interpretation
KM
tēb
Physically impossible full success
CL
∅
Source branch eliminated
CCL
t̄eb
Compound postcondition not realized
SCL
teb
Compound postcondition partially realized
As the table shows, SCL belief update is the only update mechanism that both preserves the broken-cup branch and respects the physical constraints, while capturing the partial realization of the compound postcondition.
6.2
Axiomatic Characterization
Let us now proceed to the axiomatic characterization of SCL belief update. To that end, we retain postulates (K ⋄ 1), (K ⋄ 3), (K ⋄ 5), (K ⋄ 7), and (K ⋄ 9) from the standard KM framework, and replace postulates (K ⋄ 2), (K ⋄ 6), and (K ⋄ 8) with the following selective variants. Postulates (K ⋄2)S , (K ⋄6)S , and (K ⋄8)S are weakenings of their respective standard counterparts, reflecting the fact that an epistemic input need not be accepted in its entirety. We also introduce the local credibility postulate (LC), which connects the observable acceptance behaviour of the operator with source-relative credibility. 3 This partially realized outcome also clarifies the distinction between SCL belief update and both local promotion [15] and compositional belief update [6]. Local promotion regulates how much of the prior information may be preserved while the new information is processed, whereas compositional belief update exploits the syntactic structure of the epistemic input in order to determine how that epistemic input is realized. In their standard formulations, however, neither approach transforms the epistemic input into a weaker proxy relative to the particular source world from which the complete transition is unrealizable. Consequently, neither directly represents the intermediate outcome in which only the realizable part of the compound epistemic input is effected.
14
T. Aravanis and C. D. Koutras
Selective Credibility-Limited Belief Update
(K ⋄ 2)S
If K is complete, then there is a ψ ∈ L such that φ |= ψ, ψ ∈ K ⋄ φ, and K ⋄ φ = K ⋄ ψ.
(K ⋄ 6)S
If φ ∈ K ⋄ φ, then K ⋄ (φ ∧ ψ) ⊆ (K ⋄ φ) + ψ.
(K ⋄ 8)S
If K is complete, φ ∈ K ⋄ φ, and ψ ∈ K ⋄ ψ, then K ⋄ (φ ∨ ψ) ⊆ Cn (K ⋄ φ) ∪ (K ⋄ ψ) .
(LC)
If K is complete, φ ∈ K ⋄ φ, and ¬ψ ∈ / K ⋄ φ, then ψ ∈ K ⋄ ψ.
Some comments on these postulates are in order. Postulate (K ⋄ 2)S is a selective counterpart of the KM success postulate (K ⋄2). Rather than requiring the whole epistemic input φ to be accepted, it requires the existence of an accepted proxy ψ that is implied by φ and produces the same update result. In this respect, it is the source-local update analogue of the proxy-success postulate used in selective belief revision [10, p. 334]. The restriction to complete prior theories serves to isolate a single source world; when K = Cn(w), the update originates from a single source world w, and the witnessing proxy can be identified with the corresponding transformed epistemic input fw (φ). Postulate (K⋄6)S preserves the KM-style interaction between update and conjunction whenever the first conjunct is itself accepted. Without the condition φ ∈ K ⋄ φ, the epistemic input φ may have been replaced by a weaker proxy, and the standard conjunctive constraint would no longer be justified. Thus, the postulate reinstates the usual KM-style behaviour precisely in those cases in which selective weakening has not prevented the acceptance of φ. Similarly, postulate (K ⋄ 8)S retains the KM-style constraint on update by a disjunction only when each disjunct is accepted under its corresponding update. If either disjunct is selectively weakened, the updates by φ, by ψ, and by φ ∨ ψ may be based on different proxies, so the unconditional KM disjunctive postulate (K ⋄ 8) would be too strong. Finally, postulate (LC) provides a behavioural expression of local credibility. Suppose that K = Cn(w) (for a world w), that the update by φ accepts φ, and that ψ remains possible after that update. Then, some selected successor of w satisfies ψ, showing that ψ is credible from w. Condition (LC) requires this local credibility to be reflected in the result of updating directly by ψ, which must then accept ψ. Against this background, we can state the following representation theorem for SCL belief update. Theorem 16. An update operator ⋄ satisfies postulates (K ⋄1), (K ⋄2)S , (K ⋄3), (K ⋄5), (K ⋄6)S , (K ⋄ 7), (K ⋄ 8)S , (K ⋄ 9), and (LC) iff there exist a credible faithful assignment w 7→ (Cw , ⪯w ) and a pointwise transformation assignment F = {fw : w ∈ M} satisfying properties (F1)–(F4), such that, for every belief set K and every sentence φ ∈ L, [ (SCL) [K ⋄ φ] = min [fw (φ)] ∩ Cw , ⪯w . w∈[K]
Proof. Right-to-left implication. Let ⋄ be an update operator, let K be a belief set, let φ be a sentence of L, and assume that there exist a credible faithful assignment w 7→ (Cw , ⪯w ) and a pointwise transformation assignment F satisfying properties (F1)–(F4), such that condition (SCL) holds; 15
T. Aravanis and C. D. Koutras
that is, [K ⋄ φ] =
[
Selective Credibility-Limited Belief Update
min [fw (φ)] ∩ Cw , ⪯w . We show that ⋄ satisfies postulates (K ⋄ 1),
w∈[K]
(K ⋄ 2)S , (K ⋄ 3), (K ⋄ 5), (K ⋄ 6)S , (K ⋄ 7), (K ⋄ 8)S , (K ⋄ 9), and (LC). • Postulate (K ⋄1) follows immediately, since the right-hand side of (SCL) determines a theory. • For postulate (K ⋄ 2)S , let K = Cn(w) be complete, let φ be an epistemic input, and put ψ = fw (φ). By property (F1), φ |= ψ. Since K is complete, we have that [K] = {w}. Hence, by condition (SCL), we have that [K ⋄ φ] = min [fw (φ)] ∩ Cw , ⪯w ⊆ [ψ], so ψ ∈ K ⋄ φ. Finally, by property (F3), we have that fw (ψ) = fw fw (φ) ≡ fw (φ), and therefore, K ⋄ φ = K ⋄ ψ, as desired. • For postulate (K ⋄ 3), suppose that φ ∈ K. Then, for every w ∈ [K], we have that w ∈ [φ] ∩ Cw . By w is faithful to w, it property (F4), fw (φ) ≡ φ. Since the preorder ⪯[ {w} = [K], and is true that min [φ] ∩ Cw , ⪯w = {w}. Consequently, [K ⋄ φ] = w∈[K]
hence, K ⋄ φ = K. • Postulate (K ⋄ 5) follows from property (F2), combined with condition (SCL). • For postulate (K ⋄ 6)S , suppose that φ ∈ K ⋄ φ. Let ψ ∈ L and fix an arbitrary world w ∈ [K]. We prove the following local inclusion: min [fw (φ)] ∩ Cw , ⪯w ∩ [ψ] ⊆ min fw (φ ∧ ψ) ∩ Cw , ⪯w . (1) – First, assume that min [fw (φ)] ∩ Cw , ⪯w = ∅. Then, min [fw (φ)] ∩ Cw , ⪯w ∩ [ψ] = ∅. Hence, inclusion (1) follows trivially. – Next, assume that min [fw (φ)] ∩ Cw , ⪯w ̸= ∅. By condition (SCL), min [fw (φ)] ∩ Cw , ⪯w ⊆ [K ⋄ φ]. Since φ ∈ K ⋄ φ, we have that [K ⋄ φ] ⊆ [φ]. Therefore, min [fw (φ)]∩Cw , ⪯w ⊆ [φ]. Moreover, min [fw (φ)]∩Cw , ⪯w ⊆ Cw . Since min [fw (φ)] ∩ Cw , ⪯w ̸= ∅ by our standing assumption, there exists a world r ∈ min [fw (φ)] ∩ Cw , ⪯w . Consequently, r ∈ [φ] ∩ Cw , and hence, [φ] ∩ Cw ̸= ∅. Property (F4) therefore gives fw (φ) ≡ φ, meaning that min [fw (φ)] ∩ Cw , ⪯w = min [φ] ∩ Cw , ⪯w . (2) Now, if [φ ∧ ψ] ∩ Cw ̸= ∅, then property (F4) also gives fw (φ ∧ ψ) ≡ φ ∧ ψ. 16
(3)
T. Aravanis and C. D. Koutras
Selective Credibility-Limited Belief Update
We show that min [φ] ∩ Cw , ⪯w ∩ [ψ] ⊆ min [φ ∧ ψ] ∩ Cw , ⪯w . Let r ∈ min [φ] ∩ Cw , ⪯w ∩ [ψ]. Then, r ∈ [φ] ∩ Cw and r ∈ [ψ], so r ∈ [φ ∧ ψ] ∩ Cw . Suppose, towards a contradiction, that r ∈ / min [φ ∧ ψ] ∩ Cw , ⪯w . Then, there exists r′ ∈ [φ ∧ ψ] ∩ Cw such that r′ ≺w r. Since [φ ∧ ψ]∩ Cw ⊆ [φ] ∩ Cw , we have that r′ ∈ [φ] ∩ Cw , contradicting r ∈ min [φ] ∩ Cw , ⪯w . Therefore, min [φ] ∩ Cw , ⪯w ∩ [ψ] ⊆ min [φ ∧ ψ] ∩ Cw , ⪯w .
(4)
By conditions (2)–(4), we derive that inclusion (1) holds. Suppose instead that [φ ∧ ψ] ∩ Cw = ∅. Then, by condition (2), min [fw (φ)] ∩ Cw , ⪯w ∩ [ψ] = min [φ] ∩ Cw , ⪯w ∩ [ψ] ⊆ [φ] ∩ Cw ∩ [ψ] = [φ ∧ ψ] ∩ Cw = ∅.
Therefore, min [fw (φ)] ∩ Cw , ⪯w ∩ [ψ] = ∅, which means that inclusion (1) holds. Since w ∈ [K] was arbitrary, inclusion (1) holds for every w ∈ [K]. Taking the union over all w ∈ [K], we obtain that (K ⋄ φ) + ψ = [K ⋄ φ] ∩ [ψ] ! [ = min [fw (φ)] ∩ Cw , ⪯w ∩ [ψ] w∈[K]
=
[
!
min [fw (φ)] ∩ Cw , ⪯w ∩ [ψ]
w∈[K]
⊆
[
min
fw (φ ∧ ψ) ∩ Cw , ⪯w
w∈[K]
= K ⋄ (φ ∧ ψ) . Therefore, K ⋄ (φ ∧ ψ) ⊆ (K ⋄ φ) + ψ, meaning that postulate (K ⋄ 6)S is satisfied. • For postulate (K ⋄7), suppose that ψ ∈ K ⋄φ and φ ∈ K ⋄ψ. Fix an arbitrary world w ∈ [K]. Assume, towards a contradiction, that min [fw (φ)] ∩ Cw , ⪯w = ∅, while min [fw (ψ)] ∩ Cw , ⪯w ̸= ∅. By condition (SCL), min [fw (ψ)] ∩ Cw , ⪯w ⊆ [K ⋄ ψ]. Since φ ∈ K ⋄ ψ, we have that [K ⋄ ψ] ⊆ [φ]. Therefore, min [fw (ψ)] ∩ Cw , ⪯w ⊆ [φ]. Moreover, min [fw (ψ)] ∩ Cw , ⪯w ⊆ Cw . Since min [fw (ψ)] ∩ Cw , ⪯w ̸= ∅ by our 17
T. Aravanis and C. D. Koutras
Selective Credibility-Limited Belief Update
standing assumption, there exists a world r ∈ min [fw (ψ)] ∩ Cw , ⪯w . Consequently, r ∈ [φ]∩C w , and hence, [φ]∩C w ̸= ∅.Then, property(F4) entails that fw (φ) ≡ φ, meaning that min [fw (φ)] ∩ Cw , ⪯w = min [φ] ∩ Cw , ⪯w ̸= ∅, which is a contradiction. By a totally symmetric line of reasoning,we can show that [ψ] ∩ Cw ̸= ∅, and that it cannot be the case that min [fw (ψ)] ∩ Cw , ⪯w = ∅, while min [fw (φ)] ∩ Cw , ⪯w ̸= ∅. Hence, either min [fw (φ)] ∩ Cw , ⪯w = min [fw (ψ)] ∩ Cw , ⪯w = ∅, or min [fw (φ)] ∩ Cw , ⪯w ̸= ∅ and min [fw (ψ)] ∩ Cw , ⪯w ̸= ∅. In the former case, obviously min [fw (φ)] ∩ Cw , ⪯w = min [fw (ψ)] ∩ Cw , ⪯w . Now consider the latter case, in which min [fw (φ)] ∩ Cw , ⪯w ̸= ∅ and min [fw (ψ)] ∩ Cw , ⪯w ̸= ∅. Since ψ ∈ K ⋄ φ, condition (SCL) gives min [fw (φ)] ∩ Cw , ⪯w ⊆ [K ⋄ φ] ⊆ [ψ]. Moreover, the left-hand side of the previous inclusion is a subset of Cw and is non-empty. Consequently, [ψ] ∩ Cw ̸= ∅. Similarly, from φ ∈ K ⋄ψ and the non-emptiness of min [fw (ψ)]∩Cw , ⪯w , we obtain that [φ]∩Cw ̸= ∅. Property (F4) therefore yields fw (ψ) ≡ ψ and fw (φ)≡ φ. Combining the above, we deduce that min [φ] ∩ Cw , ⪯w ⊆ [ψ] ∩ Cw and min [ψ] ∩ Cw , ⪯w ⊆ [φ] ∩ Cw . Then, Lemma 1 of Section 3 yields min [φ] ∩ Cw , ⪯w = min [ψ] ∩ Cw , ⪯w , equivalently, min [fw (φ)] ∩ Cw , ⪯w = min [fw (ψ)] ∩ Cw , ⪯w . Thus, in either case, min [fw (φ)] ∩ Cw , ⪯w = min [fw (ψ)] ∩ Cw , ⪯w . Since w ∈ [K] was arbitrary, this equality holds for every w ∈ [K]. Taking unions and ap[ plying condition (SCL), we obtain that [K ⋄ φ] = min [fw (φ)] ∩ Cw , ⪯w = w∈[K]
[
min [fw (ψ)] ∩ Cw , ⪯w
= [K ⋄ ψ]. Therefore, K ⋄ φ = K ⋄ ψ, as desired.
w∈[K]
• For postulate (K ⋄ 8)S , let K = Cn(w) be complete, and suppose that φ ∈ K ⋄ φ and ψ ∈ K ⋄ ψ. If either [K ⋄ φ] = ∅ or [K ⋄ ψ] = ∅, then Cn (K ⋄ φ) ∪ (K ⋄ ψ) = L. It follows then trivially that K ⋄ (φ ∨ ψ) ⊆ Cn (K ⋄ φ) ∪ (K ⋄ ψ) . Suppose, therefore, that [K ⋄ φ] ̸= ∅ and [K ⋄ ψ] ̸= ∅. Since K = Cn(w) is complete, we have that [K] = {w}. Then, by condition (SCL), [K ⋄ φ] = min [fw (φ)] ∩ Cw , ⪯w and [K ⋄ ψ] = min [fw (ψ)] ∩ Cw , ⪯w . Since φ ∈ K ⋄ φ, every world in the non-empty set [K ⋄ φ] satisfies φ. Moreover, condition (SCL) ensures that every such world belongs to Cw . Consequently, there exists a world in [φ] ∩ Cw , and hence, [φ] ∩ Cw ̸= ∅. Similarly, from ψ ∈ K ⋄ ψ and the non-emptiness of [K ⋄ ψ], we obtain that [ψ] ∩ Cw ̸= ∅. It 18
T. Aravanis and C. D. Koutras
Selective Credibility-Limited Belief Update
follows immediately that [φ ∨ ψ] ∩ Cw ̸= ∅. Property (F4) therefore applies to all three epistemic inputs, and yields fw (φ) ≡ φ, fw (ψ) ≡ ψ, and fw (φ ∨ ψ) ≡ φ ∨ ψ. Hence, condition (SCL) gives [K ⋄ φ] = min [φ] ∩ Cw , ⪯w , [K ⋄ ψ] = min [ψ] ∩ Cw , ⪯w , and [K ⋄ (φ ∨ ψ)] = min [φ ∨ ψ] ∩ Cw , ⪯w . Now, it is easy to verify that min [φ] ∩ Cw , ⪯w ∩ min [ψ] ∩ Cw , ⪯w ⊆ min [φ ∨ ψ] ∩ Cw , ⪯w . Combining the above, we deduce that [K ⋄φ] ∩ [K ⋄ ψ] ⊆ [K ⋄ (φ ∨ ψ)], which is equivalent to K ⋄ (φ ∨ ψ) ⊆ Cn (K ⋄ φ) ∪ (K ⋄ ψ) , as desired. • For postulate (K ⋄ 9), first note that [K] ̸= ∅ by our standing assumption on the consistency of prior belief sets. For every w ∈ [K], the theory Cn(w) is complete and [Cn(w)] = {w}. Applying condition (SCL) to Cn(w) gives [ min [fr (φ)] ∩ Cr , ⪯r = min [fw (φ)] ∩ Cw , ⪯w . [Cn(w) ⋄ φ] = r∈[Cn(w)]
Consequently, [K ⋄φ] =
[
[Cn(w)⋄φ], which is equivalent to K ⋄φ =
w∈[K]
\
Cn(w)⋄φ .
w∈[K]
Therefore, postulate (K ⋄ 9) is satisfied. • Finally, for postulate (LC), let K = Cn(w) be complete, suppose that φ ∈ K ⋄ φ, and assume that ¬ψ ∈ / K ⋄ φ. Since an inconsistent theory contains every sentence of L, K ⋄ φ is consistent and, therefore, [K ⋄ φ] ̸= ∅. Since ¬ψ ∈ / K ⋄ φ, there exists a world r ∈ [K ⋄ φ] such that r |= ψ. Recall that K = Cn(w) is complete, and hence, [K] = {w}. By condition (SCL), [K ⋄ φ] = min [fw (φ)] ∩ Cw , ⪯w . Therefore, every world in [K ⋄ φ], and in particular the world r, belongs to Cw . Since r |= ψ, we have that r ∈ [ψ] ∩ Cw , and consequently, [ψ] ∩ Cw ̸= ∅. Property (F4) now applies and yields fw (ψ) ≡ ψ. Applying condition (SCL) once again, this time to the epistemic input ψ, we obtain that [K ⋄ ψ] = min [fw (ψ)] ∩ Cw , ⪯w = min [ψ] ∩ Cw , ⪯w ⊆ [ψ]. Consequently, ψ ∈ K ⋄ ψ, as desired. Left-to-right implication. Let ⋄ be an update operator that satisfies postulates (K ⋄ 1), (K ⋄ 2)S , (K ⋄ 3), (K ⋄ 5), (K ⋄ 6)S , (K ⋄ 7), (K ⋄ 8)S , (K ⋄ 9), and (LC). We show that there exist a credible faithful assignment w 7→ (Cw , ⪯w ) and a pointwise transformation assignment F satisfying properties (F1)–(F4), such that condition (SCL) holds. Construct an Auxiliary Operation. First, we define an auxiliary operation ⋄c . For every complete theory Cn(w) and every sentence φ ∈ L, put Cn(w) ⋄ φ, if φ ∈ Cn(w) ⋄ φ, (5) Cn(w) ⋄c φ = L, otherwise. 19
T. Aravanis and C. D. Koutras
Selective Credibility-Limited Belief Update
Moreover, for every consistent belief set K, define \ K ⋄c φ = Cn(w) ⋄c φ .
(6)
w∈[K]
For the inconsistent belief set L, put L ⋄c φ = L. We show that ⋄c is a CL update operator, by showing that it satisfies postulates (K ⋄ 1)–(K ⋄ 3) and (K ⋄ 5)–(K ⋄ 9); see Definition 7 of Subsection 5.1. If K is inconsistent, these postulates are satisfied trivially. Hence, in what follows, it suffices to consider consistent K. • Postulate (K ⋄ 1) follows immediately from the definition of ⋄c , since both conditions (5) and (6) determine a theory. • For postulate (K ⋄ 2), condition (5) ensures that φ ∈ Cn(w) ⋄c φ, for every w ∈ [K]. Hence, by condition (6), φ ∈ K ⋄c φ, as desired. • For postulate (K ⋄ 3), let φ be a sentence of L such that φ ∈ K. Fix an arbitrary world w ∈ [K]. Then, φ ∈ Cn(w). By postulate (K ⋄ 3) for ⋄, we have that Cn(w) ⋄ φ = Cn(w). Hence, Cn(w) ⋄c φ = Cn(w), and, using condition (6), we obtain that K ⋄c φ = K, as desired. • For postulate (K ⋄ 5), let φ, ψ be two sentences of L such that φ ≡ ψ. Fix an arbitrary world w ∈ M. By postulate (K ⋄ 5) for ⋄, we have that Cn(w) ⋄ φ = Cn(w) ⋄ ψ. Since φ ≡ ψ, it follows that φ ∈ Cn(w) ⋄ φ iff ψ ∈ Cn(w) ⋄ ψ. Thus, the same clause of condition (5) applies to both epistemic inputs φ and ψ, meaning that Cn(w) ⋄c φ = Cn(w) ⋄c ψ. Since w ∈ M was arbitrary, condition (6) entails K ⋄c φ = K ⋄c ψ, as desired. • For postulate (K ⋄6), it is enough to establish the postulate for every complete theory Cn(w). Indeed, by condition (6), for every belief set K and every sentence χ ∈ L, [K ⋄c χ] = [ [Cn(w) ⋄c χ]. Suppose, therefore, that, for every w ∈ [K], Cn(w) ⋄c (φ ∧ ψ) ⊆ w∈[K]
Cn(w) ⋄c φ + ψ. Equivalently, [Cn(w) ⋄c φ] ∩ [ψ] ⊆ Cn(w) ⋄c (φ ∧ ψ) . Taking the union over all w ∈ [K], we obtain that (K ⋄c φ) + ψ = [K ⋄c φ] ∩ [ψ] [ = [Cn(w) ⋄c φ] ∩ [ψ] w∈[K]
=
[
[Cn(w) ⋄c φ] ∩ [ψ]
w∈[K]
⊆
[ Cn(w) ⋄c (φ ∧ ψ) w∈[K]
= K ⋄c (φ ∧ ψ) . 20
T. Aravanis and C. D. Koutras
Selective Credibility-Limited Belief Update
Hence, K ⋄c (φ ∧ ψ) ⊆ (K ⋄c φ)+ ψ. Thus, it remains only to verify the local inclusion Cn(w) ⋄c (φ ∧ ψ) ⊆ Cn(w) ⋄c φ + ψ, for an arbitrary complete theory K = Cn(w). To that end, assume first that K ⋄c φ = L. Then, the required local inclusion follows trivially. Suppose, therefore, that K ⋄c φ is consistent. By condition (5), it follows that φ ∈ K ⋄ φ and K ⋄c φ = K ⋄ φ. Next, we distinguish two cases, according to whether φ ∧ ψ belongs to K ⋄ (φ ∧ ψ). – Suppose that φ ∧ ψ ∈ K ⋄ (φ ∧ ψ). Then, from the first clause of condition (5), we have that K ⋄c (φ ∧ ψ) = K ⋄ (φ ∧ ψ). Thus, ⋄c coincides with ⋄ on both epistemic inputs φ and φ ∧ ψ. Hence, the required local inclusion follows directly from postulate (K ⋄ 6)S for ⋄. – Suppose that φ ∧ ψ ∈ / K ⋄ (φ ∧ ψ). Then, from condition (5), we have that K ⋄c (φ ∧ ψ) = L. Now, we claim that ¬ψ ∈ K ⋄ φ. Assume, towards a contradiction, that ¬ψ ∈ / K ⋄ φ. Since φ ∈ K ⋄ φ, it follows that ¬(φ ∧ ψ) ∈ / K ⋄ φ. Indeed, if ¬(φ ∧ ψ) ∈ K ⋄ φ, then, by the deductive closure of K ⋄ φ guaranteed by postulate (K ⋄ 1) and the fact that φ ∧ ¬(φ ∧ ψ) |= ¬ψ, we would obtain ¬ψ ∈ K ⋄ φ, contrary to our assumption. Then, applying postulate (LC) with φ ∧ ψ in place of ψ, we obtain that φ ∧ ψ ∈ K ⋄ (φ ∧ ψ), contradicting the assumption of the present case. Therefore, ¬ψ ∈ K ⋄φ. Consequently, (K ⋄c φ) + ψ = L. This, combined with K ⋄c (φ ∧ ψ) = L, leads to K ⋄c (φ ∧ ψ) ⊆ (K ⋄c φ) + ψ, as desired. • For postulate (K ⋄ 7), it is sufficient to establish the postulate for every complete theory Cn(w), since ⋄c is extended to arbitrary consistent theories pointwise by condition (6). To that end, let K = Cn(w) be complete, and let φ, ψ be two sentences of L, such that ψ ∈ K ⋄c φ and φ ∈ K ⋄c ψ. If both K ⋄c φ and K ⋄c ψ are inconsistent, then K ⋄c φ = K ⋄c ψ = L. Thus, postulate (K ⋄ 7) trivially holds. Suppose now that exactly one is inconsistent; say K ⋄c φ = L and K ⋄c ψ is consistent. By condition (5), it follows that ψ ∈ K ⋄ ψ and K ⋄c ψ = K ⋄ ψ. Since φ ∈ K ⋄c ψ = K ⋄ ψ and K ⋄ ψ is consistent, we derive that ¬φ ∈ / K ⋄ ψ. By postulate (LC), φ ∈ K ⋄ φ, and hence, by the first clause of condition (5), K ⋄c φ = K ⋄ φ = L. Therefore, ψ ∈ K ⋄ φ, and postulate (K ⋄ 7) applied to ⋄ gives K ⋄ φ = K ⋄ ψ, contradicting the consistency of K ⋄ ψ. The opposite mixed case —i.e., K ⋄c ψ = L and K ⋄c φ is consistent— can be proved symmetrically, by interchanging φ and ψ. Thus, either both K ⋄c φ and K ⋄c ψ are inconsistent or both are consistent. In the former case, it was previously shown that postulate (K ⋄ 7) trivially holds. In the latter case, by condition (5), it follows that φ ∈ K ⋄ φ, ψ ∈ K ⋄ ψ, K ⋄c φ = K ⋄ φ, and K ⋄c ψ = K ⋄ ψ. Hence, ⋄c coincides with ⋄ on both epistemic inputs φ and ψ. Moreover, from the standing assumptions ψ ∈ K ⋄c φ and φ ∈ K ⋄c ψ, we obtain that ψ ∈ K ⋄ φ and φ ∈ K ⋄ ψ. Therefore, postulate (K ⋄7) applied to ⋄ yields K ⋄φ = K ⋄ψ. Consequently, K ⋄c φ = K ⋄φ = K ⋄ψ = K ⋄c ψ, meaning that postulate (K ⋄ 7) is satisfied in this case as well. 21
T. Aravanis and C. D. Koutras
Selective Credibility-Limited Belief Update
c • For postulate (K ⋄ 8), let K be complete, and let φ, ψ be two sentences of L. If either K ⋄ φ c c c or K ⋄ ψ is inconsistent, then Cn (K ⋄ φ) ∪ (K ⋄ ψ) = L, and it follows trivially that K ⋄c (φ ∨ ψ) ⊆ Cn (K ⋄c φ) ∪ (K ⋄c ψ) , as required by postulate (K ⋄ 8).
Suppose now that both K ⋄c φ and K ⋄c ψ are consistent. By condition (5), we have that φ ∈ K ⋄ φ, ψ ∈ K ⋄ ψ, K ⋄c φ = K ⋄ φ, and K ⋄c ψ = K ⋄ ψ. Since K ⋄ φ is consistent and entails φ, it follows that ¬(φ ∨ ψ) ∈ / K ⋄ φ. Then, by postulate (LC), φ ∨ ψ ∈ K ⋄ (φ ∨ ψ), and hence, by the first clause of condition (5), K ⋄c (φ ∨ ψ) = K ⋄ (φ ∨ ψ). Thus, ⋄c coincides with ⋄ on φ, ψ, and φ ∨ ψ. Therefore, postulate (K ⋄ 8)S applied to ⋄ yields c c c K ⋄ (φ ∨ ψ) ⊆ Cn (K ⋄ φ) ∪ (K ⋄ ψ) , as required by postulate (K ⋄ 8). • Finally, postulate (K ⋄ 9) follows directly from condition (6). Consequently, we have shown that ⋄c is a CL update operator. Hence, by Theorem 8, it follows that there exists a credible faithful assignment w 7→ (Cw , ⪯w ), such that Cn(w) ⋄c φ = min [φ] ∩ Cw , ⪯w . (7) Construct a Pointwise Transformation Assignment. Thereafter, we construct a pointwise transformation assignment F = {fw : w ∈ M}. For every world w ∈ M, define fw as follows. If φ ∈ Cn(w) ⋄ φ, put fw (φ) = φ. (8) If φ ∈ / Cn(w) ⋄ φ, use postulate (K ⋄ 2)S to choose a sentence ψ ∈ L such that φ |= ψ,
ψ ∈ Cn(w) ⋄ φ,
Cn(w) ⋄ φ = Cn(w) ⋄ ψ,
(9)
and put fw (φ) = ψ.
(10)
The choice in (10) is made uniformly on logical-equivalence classes. This is well defined since postulate (K ⋄ 5) ensures that logically equivalent epistemic inputs yield the same update result, while the conditions in (9) are invariant under logical equivalence. Hence, the same choices are available for logically equivalent epistemic inputs. Verify (F1)–(F4). We now prove that the F = {fw : w ∈ M} satisfies properties (F1)–(F4).
pointwise
transformation
assignment
• Property (F1) follows directly from the definition of fw . • For property (F2), let φ ≡ χ. Fix w ∈ M. By postulate (K ⋄ 5), Cn(w) ⋄ φ = Cn(w) ⋄ χ, and therefore, φ ∈ Cn(w) ⋄ φ iff χ ∈ Cn(w) ⋄ χ. Suppose first that φ ∈ Cn(w) ⋄ φ. Then, χ ∈ Cn(w)⋄χ, and condition (8) yields fw (φ) = φ and fw (χ) = χ. Hence, fw (φ) ≡ fw (χ). Suppose instead that φ ∈ / Cn(w) ⋄ φ. Then, χ ∈ / Cn(w) ⋄ χ, and the uniform choice in condition (10) ensures that the same sentence is selected for both epistemic inputs. Therefore, fw (φ) ≡ fw (χ), and property (F2) follows. 22
T. Aravanis and C. D. Koutras
Selective Credibility-Limited Belief Update
• For property (F3), if φ ∈ Cn(w) ⋄ φ, then from condition (8) we have that fw (φ) = φ, and thus, fw fw (φ) = fw (φ). If, on the other hand, φ ∈ / Cn(w) ⋄ φ, let fw (φ) = ψ, as specified by conditions (9) and (10). Then, ψ ∈ Cn(w)⋄ψ, because Cn(w)⋄ψ = Cn(w)⋄φ. Therefore, condition (8) applies to ψ, and fw fw (φ) = fw (ψ) = ψ = fw (φ). • For property (F4), suppose that [φ] ∩ Cw ̸= ∅. By condition (7), we derive that [Cn(w) ⋄c φ] ̸= ∅. Hence, Cn(w) ⋄c φ ̸= L. Then, by condition (5), we have that φ ∈ Cn(w) ⋄ φ. Therefore, condition (8) yields fw (φ) = φ. Prove Condition (SCL). As a last step, we show that condition (SCL) holds. Fix an arbitrary world w ∈ M and a sentence φ ∈ L. We distinguish two cases, according to whether φ belongs to Cn(w) ⋄ φ. • Suppose that φ ∈ Cn(w) ⋄ φ. Then, by conditions (5) and (8), we derive that Cn(w) ⋄c φ = Cn(w) ⋄ φ and fw (φ) = φ, respectively. Hence, by condition (7), we deduce that [Cn(w) ⋄ φ] = min [fw (φ)] ∩ Cw , ⪯w . • Suppose that φ ∈ / Cn(w) ⋄ φ. Let fw (φ) = ψ, as specified by conditions (9) and (10). Then, Cn(w) ⋄ φ = Cn(w) ⋄ ψ. Moreover, ψ ∈ Cn(w) ⋄ ψ, and hence, by condition (5), Cn(w) ⋄c ψ = Cn(w) ⋄ ψ. Using condition (7), we obtain that [Cn(w) ⋄ φ] = [Cn(w) ⋄ ψ] = [Cn(w) ⋄c ψ] = min [ψ] ∩ Cw , ⪯w = min [fw (φ)] ∩ Cw , ⪯w . Finally, in view of our standing assumption on consistent prior belief sets, let K be a consis tent belief set. By postulate (K ⋄ 9) and the equality [Cn(w) ⋄ φ] = min [fw (φ)] ∩ Cw , ⪯w , [ established above for every w ∈ [K], we obtain that [K ⋄ φ] = [Cn(w) ⋄ φ] = w∈[K]
[
min [fw (φ)] ∩ Cw , ⪯w . Thus, ⋄ is represented by condition (SCL), as required.
■
w∈[K]
6.3
An Unrestricted-Credibility Variant: Selective Belief Update
The SCL framework combines two conceptually distinct mechanisms; i.e., a source-dependent transformation that determines which part of the epistemic input is accepted, and a credibility restriction that limits the successor worlds available from each source world. To isolate the former mechanism, we now remove the credibility restrictions by taking every credible set to be the entire set of worlds M. In this unrestricted setting, properties (F1)–(F3) retain the essential structural 23
T. Aravanis and C. D. Koutras
Selective Credibility-Limited Belief Update
requirements on selective transformations, whereas property (F4) is deliberately omitted, since it would force every consistent epistemic input to be accepted unchanged.4 Therefore, the resulting framework captures selective belief update independently of credibility limitation. Remark 17. Let ⋄ be an update operator specified by the semantic clause underlying condition (SCL), by means of a credible faithful assignment w 7→ (Cw , ⪯w ) and a pointwise transformation assignment F = {fw : w ∈ M} satisfying properties (F1)–(F3). If Cw = M, for every world w ∈ M, then this semantic clause reduces to [ min [fw (φ)], ⪯w . [K ⋄ φ] = w∈[K]
Thus, the epistemic input φ is selectively transformed relative to each source world w, and the resulting proxy fw (φ) is processed by the standard pointwise update mechanism. In this case, ⋄ implements (genuinely) selective belief update. Selective belief update may be regarded as the belief-update analogue of selective belief revision [10, 13] — whereas selective belief revision transforms the epistemic input through a single function f before applying revision, the present construction transforms the epistemic input relative to each source world w, and then applies the KM pointwise update mechanism.
7
Well-Behaved Classes of SCL Update Operators
In this section, we identify and characterize two sub-classes of SCL update operators obtained by progressively strengthening the requirements imposed on the pointwise transformation assignment F. Consistency-preserving SCL update operators, introduced in Subsection 7.1, require the transformed epistemic input to be credible from its corresponding source world whenever the original epistemic input is consistent. This guarantees that each source world contributes at least one successor to the updated belief set whenever the epistemic input is consistent. Maximal consistencypreserving SCL update operators, introduced in Subsection 7.2, additionally require, for every consistent epistemic input, the selected proxy to be maximally informative among its credible consequences. For each sub-class, we provide both a semantic definition and an axiomatic characterization.
7.1
Consistency-Preserving SCL Update Operators
The general SCL framework does not require the transformed epistemic input fw (φ) to be credible from its source world w. Consequently, it may be the case that [fw (φ)] ∩ Cw = ∅, in which case the branch associated with w contributes no successor to the updated belief set. To exclude this possibility for consistent epistemic inputs, we impose the following additional requirement on the pointwise transformation assignment F = {fw : w ∈ M}. 4
Indeed, if Cw = M and φ is consistent, then [φ] ∩ Cw = [φ] ̸= ∅; hence, property (F4) entails fw (φ) ≡ φ.
24
T. Aravanis and C. D. Koutras
(F5)
Selective Credibility-Limited Belief Update
If [φ] ̸= ∅, then [fw (φ)] ∩ Cw ̸= ∅.
Property (F5) requires the transformed epistemic input to be credible from its corresponding source world whenever the epistemic input is consistent. Since the set M of possible worlds is finite, every non-empty subset of Cw has at least one minimal element under a preorder ⪯w . Therefore, whenever [φ] ̸= ∅, it follows that min [fw (φ)] ∩ Cw , ⪯w ̸= ∅. Thus, for every consistent epistemic input, every source world contributes at least one selected successor under condition (SCL). Definition 18 (Consistency-Preserving SCL Update Operator). An SCL update operator ⋄ is a consistency-preserving SCL update operator iff it admits a representation satisfying condition (SCL), in which the pointwise transformation assignment F = {fw : w ∈ M} additionally satisfies property (F5). The semantic requirement imposed by property (F5) has a direct axiomatic counterpart. Since every source world contributes at least one successor whenever the epistemic input is consistent, updating a consistent prior belief set by a consistent epistemic input always produces a consistent result. This is expressed by the standard KM consistency postulate (K ⋄ 4). On that basis, the following theorem strengthens Theorem 16 accordingly, and characterizes consistency-preserving SCL update operators. Theorem 19. An update operator ⋄ satisfies postulates (K ⋄ 1), (K ⋄ 2)S , (K ⋄ 3), (K ⋄ 4), (K ⋄ 5), (K ⋄ 6)S , (K ⋄ 7), (K ⋄ 8)S , (K ⋄ 9), and (LC) iff there exist a credible faithful assignment w 7→ (Cw , ⪯w ) and a pointwise transformation assignment F = {fw : w ∈ M} satisfying properties (F1)–(F5), such that, for every belief set K and every sentence φ ∈ L, condition (SCL) holds. Proof. Right-to-left implication. Let ⋄ be an update operator, let K be a belief set, let φ be a sentence of L, and assume that there exist a credible faithful assignment w 7→ (Cw , ⪯w ) and a pointwise transformation assignment (F1)–(F5), such that condition (SCL) holds; F satisfying properties [ that is, [K ⋄ φ] = min [fw (φ)] ∩ Cw , ⪯w . We show that ⋄ satisfies postulates (K ⋄ 1), w∈[K] S (K ⋄ 2) , (K ⋄ 3), (K ⋄ 4), (K ⋄ 5), (K ⋄ 6)S , (K ⋄ 7), (K ⋄ 8)S , (K ⋄ 9), and (LC).
Since F satisfies properties (F1)–(F4), Theorem 16 entails that ⋄ satisfies postulates (K ⋄ 1), (K ⋄ 2)S , (K ⋄ 3), (K ⋄ 5), (K ⋄ 6)S , (K ⋄ 7), (K ⋄ 8)S , (K ⋄ 9), and (LC). It remains to establish postulate (K ⋄ 4). To that end, suppose that both K and φ are consistent. Then, [K] ̸= ∅. By property (F5), for every w ∈ [K], [fw (φ)] ∩ Cw ̸= ∅. Hence, min [fw (φ)] ∩ Cw , ⪯w ̸= ∅, for every w ∈ [K]. [ Then, it follows from condition (SCL) that [K ⋄ φ] = min [fw (φ)] ∩ Cw , ⪯w ̸= ∅. w∈[K]
Therefore, K ⋄ φ is consistent, and postulate (K ⋄ 4) follows. 25
T. Aravanis and C. D. Koutras
Selective Credibility-Limited Belief Update
Left-to-right implication. Let ⋄ be an update operator that satisfies postulates (K ⋄ 1), (K ⋄ 2)S , (K ⋄ 3), (K ⋄ 4), (K ⋄ 5), (K ⋄ 6)S , (K ⋄ 7), (K ⋄ 8)S , (K ⋄ 9), and (LC). We show that there exist a credible faithful assignment w 7→ (Cw , ⪯w ) and a pointwise transformation assignment F satisfying properties (F1)–(F5), such that condition (SCL) holds. By Theorem 16, there exist a credible faithful assignment w 7→ (Cw , ⪯w ) and a pointwise transformation assignment F = {fw : w ∈ M} satisfying properties (F1)–(F4), such that condition (SCL) holds. It remains to show that the transformation assignment F also satisfies property (F5). To that end, fix an arbitrary world w ∈ M and an arbitrary consistent sentence φ ∈ L. Since Cn(w) is consistent, postulate (K ⋄ 4) entails that Cn(w) ⋄ φ is consistent, and therefore, [Cn(w) ⋄ φ] ̸= ∅. Since [Cn(w)] = {w}, condition (SCL) gives [Cn(w) ⋄ φ] = min [fw (φ)] ∩ Cw , ⪯w . Consequently, min [fw (φ)] ∩ Cw , ⪯w ̸= ∅, which implies that [fw (φ)] ∩ Cw ̸= ∅. Thus, the transformation assignment F = {fw : w ∈ M} satisfies property (F5), as desired. ■ The following lemma provides a behavioural characterization of the credible sets occurring in the representations supplied by Theorem 19. Intuitively, it shows that a consistent sentence φ is credible from a source world w exactly when updating the complete theory Cn(w) by φ results in a belief set that accepts φ. Thus, the semantic condition [φ] ∩ Cw ̸= ∅ can be characterized entirely in terms of the observable behaviour of an update operator ⋄. This equivalence will be used in Subsection 7.2 to characterize maximal consistency-preserving SCL update operators. Lemma 20. Let w 7→ (Cw , ⪯w ) and F = {fw : w ∈ M} be assignments witnessing a representation of ⋄ as in Theorem 19. Then, for every world w ∈ M and every consistent sentence φ ∈ L, [φ] ∩ Cw ̸= ∅ iff φ ∈ Cn(w) ⋄ φ. Proof. Let w be a world of M and let φ be a consistent sentence of L. First, suppose that [φ] ∩ Cw ̸= ∅. By property (F4),fw (φ) ≡ φ. Since [Cn(w)] = {w}, condition (SCL) gives [Cn(w) ⋄ φ] = min [φ] ∩ Cw , ⪯w ⊆ [φ]. Therefore, φ ∈ Cn(w) ⋄ φ. Conversely, suppose that φ ∈ Cn(w) ⋄ φ. By property (F5), [fw (φ)] ∩ Cw ̸= ∅. Hence, condition (SCL) yields [Cn(w) ⋄ φ] = min [fw (φ)] ∩ Cw , ⪯w ̸= ∅. Let r ∈ [Cn(w)⋄φ]. Since φ ∈ Cn(w) ⋄ φ, we have r |= φ, while condition (SCL) ensures that r ∈ Cw . Consequently, r ∈ [φ] ∩ Cw , and therefore, [φ] ∩ Cw ̸= ∅. ■
7.2
Maximal Consistency-Preserving SCL Update Operators
Theorem 19 characterizes consistency-preserving SCL update operators by requiring every transformed epistemic input fw (φ) to be credible from its corresponding source world w, whenever the original epistemic input φ is consistent. This requirement guarantees the existence of a credible proxy, but does not determine how informative that proxy must be. In particular, when several credible consequences of φ are available, properties (F1)–(F5) permit the transformation to select a proxy even though a strictly stronger credible consequence could have been retained. To exclude such unnecessarily weak selections, we impose the following maximality requirement. 26
T. Aravanis and C. D. Koutras (F6)
Selective Credibility-Limited Belief Update
There is no sentence ψ ∈ L such that φ |= ψ, ψ |= fw (φ), fw (φ) ̸|= ψ, and [ψ] ∩ Cw ̸= ∅.
Properties (F5) and (F6) jointly require fw (φ) to be maximally informative among the credible consequences of φ. More precisely, property (F5) ensures that fw (φ) is credible from w, while property (F6) excludes the existence of a credible consequence ψ of φ that is strictly stronger than fw (φ) and lies logically between φ and fw (φ). The requirement concerns maximality rather than the existence of a uniquely strongest credible consequence; thus, several mutually incomparable maximal proxies may be available. Definition 21 (Maximal Consistency-Preserving SCL Update Operator). A consistency-preserving SCL update operator ⋄ is a maximal consistency-preserving SCL update operator iff it admits a representation satisfying condition (SCL), in which the pointwise transformation assignment F = {fw : w ∈ M} additionally satisfies property (F6). We next formulate the axiomatic counterpart of this semantic requirement. By Lemma 20 of the previous subsection, for a complete theory K = Cn(w), the condition χ ∈ K ⋄ χ holds exactly when χ is credible from the source world w. Consequently, the credibility condition [χ] ∩ Cw ̸= ∅ occurring in property (F6) can be expressed entirely in terms of the observable behaviour of the update operator ⋄. This leads to the following strengthening of postulate (K ⋄ 2)S . In addition to requiring an accepted proxy that is implied by the epistemic input and induces the same update result, postulate (K ⋄ 2)SM requires that proxy to be maximally informative among the locally credible consequences of the epistemic input. (K ⋄ 2)SM
If K is complete, then there exists a sentence ψ ∈ L such that φ |= ψ, ψ ∈ K ⋄ φ, K ⋄ φ = K ⋄ ψ, and, for every χ ∈ L, if φ |= χ, χ |= ψ, χ ∈ K ⋄ χ, then ψ |= χ.
As stated, postulate (K ⋄ 2)SM strengthens (K ⋄ 2)S . Its first three requirements provide an accepted proxy ψ that is a consequence of φ and produces the same update result. Its final requirement imposes local maximality. If a locally credible consequence χ lies between φ and ψ, then ψ |= χ; since χ |= ψ is already assumed, it follows that χ ≡ ψ. Thus, no strictly stronger locally credible consequence of φ can lie between φ and the selected proxy. Against this background, we can formulate the representation theorem for maximal consistencypreserving SCL update operators. Theorem 22. An update operator ⋄ satisfies postulates (K ⋄ 1), (K ⋄ 2)SM , (K ⋄ 3), (K ⋄ 4), (K ⋄ 5), (K ⋄ 6)S , (K ⋄ 7), (K ⋄ 8)S , (K ⋄ 9), and (LC) iff there exist a credible faithful assignment w 7→ (Cw , ⪯w ) and a pointwise transformation assignment F = {fw : w ∈ M} satisfying properties (F1)–(F6), such that, for every belief set K and every sentence φ ∈ L, condition (SCL) holds. Proof. Right-to-left implication. Let ⋄ be an update operator, let K be a belief set, let φ be a sentence of L, and assume that there exist a credible faithful assignment w 7→ (Cw , ⪯w ) and a pointwise transformation assignment F satisfying properties (F1)–(F6), such that condition (SCL) holds; 27
T. Aravanis and C. D. Koutras
that is, [K ⋄ φ] =
[
Selective Credibility-Limited Belief Update
min [fw (φ)] ∩ Cw , ⪯w . We show that ⋄ satisfies postulates (K ⋄ 1),
w∈[K]
(K ⋄ 2)SM , (K ⋄ 3), (K ⋄ 4), (K ⋄ 5), (K ⋄ 6)S , (K ⋄ 7), (K ⋄ 8)S , (K ⋄ 9), and (LC). Since F satisfies properties (F1)–(F5), Theorem 19 entails that ⋄ satisfies postulates (K ⋄ 1), (K ⋄ 2)S , (K ⋄ 3), (K ⋄ 4), (K ⋄ 5), (K ⋄ 6)S , (K ⋄ 7), (K ⋄ 8)S , (K ⋄ 9), and (LC). It remains to establish postulate (K ⋄ 2)SM . Let K = Cn(w) be complete, and put ψ = fw (φ). By property (F1), we have that φ |= ψ. Since [K] = {w}, condition (SCL) gives [K ⋄ φ] = min [fw (φ)] ∩ Cw , ⪯w ⊆ [ψ]. Hence, ψ ∈ K ⋄ φ. Moreover, by property (F3), we have that fw (ψ) = fw fw (φ) ≡ fw (φ) = ψ. Therefore, [K ⋄ ψ] = min [fw (ψ)] ∩ Cw , ⪯w = min [ψ] ∩ Cw , ⪯w = [K ⋄ φ]. Thus, K ⋄ φ = K ⋄ ψ. Now, let χ ∈ L be such that φ |= χ, χ |= ψ, and χ ∈ K ⋄ χ. We show that ψ |= χ. We distinguish two cases. • Suppose first that χ is consistent. By property (F5), we derive that [fw (χ)] ∩ Cw ̸= ∅. Hence, min [fw (χ)] ∩ Cw , ⪯w ̸= ∅. By condition (SCL), it follows that [K ⋄ χ] = min [fw (χ)] ∩ Cw , ⪯w . Choose a world r ∈ [K ⋄ χ]. Since χ ∈ K ⋄ χ, we have that r |= χ, while condition (SCL) ensures that r ∈ Cw . Consequently, [χ] ∩ Cw ̸= ∅. Then, property (F6), applied to φ, χ, and fw (φ) = ψ, yields ψ |= χ. • Suppose now that χ is inconsistent. Since φ |= χ, the sentence φ is also inconsistent, and hence, φ ≡ χ. By property (F2), we have that fw (φ) ≡ fw (χ), and therefore, ψ ≡ fw (χ). Since χ ∈ K ⋄ χ and χ is inconsistent, the Hence [K ⋄ χ] = ∅. theory K ⋄ χ is inconsistent. By condition (SCL), it follows that min [fw (χ)] ∩ Cw , ⪯w = ∅. Hence, every non-empty subset of Cw has a minimal element under ⪯w . Consequently, [fw (χ)] ∩ Cw = ∅. Since ψ ≡ fw (χ), we obtain that [ψ] ∩ Cw = ∅. Suppose, towards a contradiction, that ψ is consistent. By property (F5), it follows that [fw (ψ)] ∩ Cw ̸= ∅. However, property (F3) gives fw (ψ) = fw fw (φ) ≡ fw (φ) = ψ, and therefore, [ψ] ∩ Cw ̸= ∅, contrary to the conclusion above. Hence, ψ is inconsistent. It follows immediately that ψ |= χ. Thus, in either case, ψ |= χ. Therefore, the sentence ψ satisfies all the requirements of postulate (K ⋄ 2)SM , and the postulate follows. Left-to-right implication. Let ⋄ be an update operator that satisfies postulates (K ⋄ 1), (K ⋄ 2)SM , (K ⋄ 3), (K ⋄ 4), (K ⋄ 5), (K ⋄ 6)S , (K ⋄ 7), (K ⋄ 8)S , (K ⋄ 9), and (LC). We show that there exist a credible faithful assignment w 7→ (Cw , ⪯w ) and a pointwise transformation assignment F satisfying properties (F1)–(F6), such that condition (SCL) holds. 28
T. Aravanis and C. D. Koutras
Selective Credibility-Limited Belief Update
Since postulate (K ⋄ 2)SM implies postulate (K ⋄ 2)S , Theorem 19 provides a credible faithful assignment w 7→ (Cw , ⪯w ) and a pointwise transformation assignment G = {gw : w ∈ M} satisfying properties (F1)–(F5), such that, for every belief set K and every sentence φ ∈ L, [ min [gw (φ)] ∩ Cw , ⪯w . (1) [K ⋄ φ] = w∈[K]
Since w 7→ (Cw , ⪯w ) and G witness a representation of ⋄ as in Theorem 19, Lemma 20 yields, for every world w ∈ M and every consistent sentence φ ∈ L, [φ] ∩ Cw ̸= ∅
iff
φ ∈ Cn(w) ⋄ φ.
(2)
Construct a New Pointwise Transformation Assignment. We shall use the above equivalence to construct a new pointwise transformation assignment satisfying the additional maximality property (F6). To that end, for each w ∈ M, define a new transformation function fbw as follows: ( φ, if φ ∈ Cn(w) ⋄ φ, fbw (φ) = ψ, otherwise, where, in the second case, ψ is supplied by postulate (K ⋄ 2)SM so that φ |= ψ,
ψ ∈ Cn(w) ⋄ φ,
Cn(w) ⋄ φ = Cn(w) ⋄ ψ,
and, for every χ ∈ L, if φ |= χ, χ |= ψ, and χ ∈ Cn(w) ⋄ χ, then ψ |= χ. The choices in the second clause are made uniformly on logical-equivalence classes. This is well defined because postulate (K ⋄ 5) ensures that logically equivalent epistemic inputs yield the same update result, while the entailment and maximality conditions in postulate (K ⋄ 2)SM are invariant under logical equivalence. Hence, the same witnesses are available for logically equivalent epistemic inputs. Verify (F1)–(F6). Now, we show that the Fb = {fbw : w ∈ M} satisfies properties (F1)–(F6).
pointwise
transformation
assignment
• Property (F1) follows immediately from the definition of fbw . • For property (F2), let φ ≡ ψ. By postulate (K ⋄ 5), Cn(w) ⋄ φ = Cn(w) ⋄ ψ, and therefore, φ ∈ Cn(w) ⋄ φ iff ψ ∈ Cn(w) ⋄ ψ. Hence, the same clause in the definition of fbw applies to both epistemic inputs. If the first clause applies, then fbw (φ) = φ ≡ ψ = fbw (ψ). If the second clause applies, the uniform choice on logical-equivalence classes ensures that the same sentence is selected for both epistemic inputs. Thus, fbw (φ) ≡ fbw (ψ). b • For property (F3), if φ ∈ Cn(w) ⋄ φ, then from the first clause of the definition of fw we have that fbw (φ) = φ, and thus, fbw fbw (φ) = fbw (φ). If, on the other hand, φ ∈ / Cn(w) ⋄ φ, let fbw (φ) = ψ, as specified in the definition of fbw . Since ψ ∈ Cn(w) ⋄ φ and Cn(w) ⋄ φ = Cn(w) ⋄ ψ, it follows that ψ ∈ Cn(w) ⋄ ψ. Hence, the first clause of the definition of fbw b b b applies to ψ, and gives fw fw (φ) = fw (ψ) = ψ = fbw (φ). 29
T. Aravanis and C. D. Koutras
Selective Credibility-Limited Belief Update
• For property (F4), suppose that [φ] ∩ Cw ̸= ∅. By condition (2), we derive that φ ∈ Cn(w) ⋄ φ, and the first clause of the definition of fbw entails that fbw (φ) = φ. • For property (F5), let φ be consistent. Suppose first that φ ∈ Cn(w)⋄φ. Then, the first clause of the definition of fbw entails fbw (φ) = φ, while condition (2) gives [fbw (φ)] ∩ Cw ̸= ∅, as required. Suppose instead that φ ∈ / Cn(w) ⋄ φ, and let fbw (φ) = ψ, as specified b in the definition of fw . Since φ |= ψ and φ is consistent, ψ is consistent. Moreover, ψ ∈ Cn(w) ⋄ φ = Cn(w) ⋄ ψ, and hence, ψ ∈ Cn(w) ⋄ ψ. Therefore, condition (2) yields [ψ] ∩ Cw ̸= ∅. Consequently, [fbw (φ)] ∩ Cw ̸= ∅, and property (F5) follows. • For property (F6), suppose first that φ ∈ Cn(w) ⋄ φ. Then, the first clause of the definition of fbw entails that fbw (φ) = φ, and there cannot be a sentence ψ ∈ L such that both φ |= ψ and fbw (φ) ̸|= ψ. Suppose, therefore, that φ ∈ / Cn(w) ⋄ φ. Assume, towards a contradiction, that there exists a sentence ψ ∈ L such that φ |= ψ, ψ |= fbw (φ), fbw (φ) ̸|= ψ, and [ψ] ∩ Cw ̸= ∅. Since [ψ] ∩ Cw ̸= ∅, the sentence ψ is consistent. Hence, condition (2) gives ψ ∈ Cn(w) ⋄ ψ. Then, postulate (K ⋄ 2)SM gives fbw (φ) |= ψ, contradicting fbw (φ) ̸|= ψ. Consequently, property (F6) holds. Prove Condition (SCL). As a last step, we show that condition (SCL) holds. Fix an arbitrary world w ∈ M and a sentence φ ∈ L. Since [Cn(w)] = {w}, condition (1) gives, for every sentence θ ∈ L, [Cn(w) ⋄ θ] = min [gw (θ)] ∩ Cw , ⪯w . (3) We distinguish two cases, according to whether φ belongs to Cn(w) ⋄ φ. • Suppose first that φ ∈ Cn(w) ⋄ φ. By the first clause of the definition of fbw , we have that fbw (φ) = φ. Suppose first that φ is consistent. By condition (2), [φ] ∩ Cw ̸= ∅. Therefore, property (F4) for gw gives gw (φ) ≡ φ. Consequently, by condition (3), [Cn(w) ⋄ φ] = min [gw (φ)] ∩ Cw , ⪯w = min [φ] ∩ Cw , ⪯w = min [fbw (φ)] ∩ Cw , ⪯w . Suppose instead that φ is inconsistent. Since φ ∈ Cn(w) ⋄ φ, the theory Cn(w) ⋄ φ is inconsistent. Hence, [Cn(w) ⋄ φ] = ∅. Moreover, fbw (φ) = φ and [φ] = ∅. Therefore, min [fbw (φ)] ∩ Cw , ⪯w = ∅ = [Cn(w) ⋄ φ]. • Suppose now that φ ∈ / Cn(w) ⋄ φ. Let fbw (φ) = ψ, as specified by the second clause of the b definition of fw . Then, Cn(w) ⋄ φ = Cn(w) ⋄ ψ and ψ ∈ Cn(w) ⋄ φ = Cn(w) ⋄ ψ. Suppose first that ψ is consistent. By condition (2), [ψ] ∩ Cw ̸= ∅. Therefore, property (F4) for gw
30
T. Aravanis and C. D. Koutras
Selective Credibility-Limited Belief Update
gives gw (ψ) ≡ ψ. Consequently, by condition (3), [Cn(w) ⋄ φ] = [Cn(w) ⋄ ψ] = min [gw (ψ)] ∩ Cw , ⪯w = min [ψ] ∩ Cw , ⪯w = min [fbw (φ)] ∩ Cw , ⪯w . Suppose instead that ψ is inconsistent. Since ψ ∈ Cn(w) ⋄ ψ, the theory Cn(w) ⋄ ψ is inconsistent. Hence, [Cn(w) ⋄ ψ] = ∅. Since Cn(w) ⋄ φ = Cn(w) ⋄ ψ, it follows that [Cn(w) ⋄ φ] = ∅. Moreover, fbw (φ) = ψ and [ψ] = ∅. Therefore, min [fbw (φ)] ∩ Cw , ⪯w = ∅ = [Cn(w) ⋄ φ]. Finally, in view of our standing assumption on consistent prior belief sets, let K be a consis tent belief set. By postulate (K ⋄ 9) and the equality [Cn(w) ⋄ φ] = min [fbw (φ)] ∩ Cw , ⪯w , [ established above for every w ∈ [K], we obtain that [K ⋄ φ] = [Cn(w) ⋄ φ] = w∈[K] b min [fw (φ)] ∩ Cw , ⪯w . Thus, ⋄ is represented by condition (SCL), as required.
[
■
w∈[K]
8
KM, CL, and CCL Belief Update as Special Cases of SCL Belief Update
Having introduced the SCL framework and characterized its principal sub-classes, we now examine its relationship with standard KM belief update [17] and the credibility-limited approaches of Fermé et al. [12]. We show that CL and CCL belief update arise as special cases of SCL belief update through particular choices of the pointwise transformation assignment, while KM belief update is recovered by additionally removing the credibility restrictions. These results establish that the SCL framework subsumes all three approaches.
8.1
CL and CCL Belief Update as Special Cases
Fix a credible faithful assignment w 7→ (Cw , ⪯w ). For every pointwise transformation assignment F = {fw : w ∈ M}, let ⋄F denote the operation determined by condition (SCL), relative to this credible faithful assignment. We first show that CL belief update is recovered by taking every source-dependent transformation function to be the identity function. Proposition 23. For every w ∈ M and every φ ∈ L, define the transformation function fwCL (φ) = φ, and let FCL = fwCL : w ∈ M be the corresponding pointwise transformation assignment. Then, FCL satisfies properties (F1)–(F4), and [ [K ⋄FCL φ] = min [φ] ∩ Cw , ⪯w . w∈[K]
31
T. Aravanis and C. D. Koutras
Selective Credibility-Limited Belief Update
Hence, ⋄FCL is a CL update operator. Proof. Since every fwCL is the identity function, properties (F1)–(F4) follow immediately. By condition (SCL), we have that, for every belief set K and every sentence φ ∈ L, [ [ min [φ] ∩ Cw , ⪯w . min fwCL (φ) ∩ Cw , ⪯w = [K ⋄FCL φ] = w∈[K]
w∈[K]
This is exactly condition (CL) of Subsection 5.1. Therefore, by Theorem 8, ⋄FCL is a CL update operator. ■ Notice that the pointwise transformation assignment FCL neednot satisfy property (F5). Indeed, CL it may be the case that [φ] ̸= ∅, while [φ] ∩ Cw = ∅. In that case, fw (φ) ∩ Cw = [φ] ∩ Cw = ∅, and the source branch associated with w contributes no successor world to the updated state of belief. We next turn to CCL belief update. Its source-retention behaviour can be recovered by leaving locally credible epistemic inputs unchanged and replacing each locally non-credible epistemic input φ with φ ∨ γw , where γw is a complete sentence characterizing the source world w. Relative to Cw , this proxy has w as its unique credible world and is maximally informative among the credible consequences of φ. Proposition 24. For every w ∈ M, let γw be a sentence such that [γw ] = {w}, and define the transformation function ( φ, if [φ] ∩ Cw ̸= ∅, fwCCL (φ) = φ ∨ γw , otherwise. Let FCCL = {fwCCL : w ∈ M} be the corresponding pointwise transformation assignment. Then, FCCL satisfies properties (F1)–(F6), and min [φ] ∩ Cw , ⪯w , if [φ] ∩ Cw ̸= ∅, min fwCCL (φ) ∩ Cw , ⪯w = {w}, otherwise. Hence, ⋄FCCL is a CCL update operator and, in particular, a maximal consistency-preserving SCL update operator. Proof. First, we show that the pointwise transformation assignment FCCL satisfies properties (F1)–(F6). • Property (F1) follows because fwCCL (φ) is either φ or φ ∨ γw , and φ |= φ ∨ γw . • Property (F2) follows because the condition [φ] ∩ Cw ̸= ∅ is invariant under logical equivalence.
32
T. Aravanis and C. D. Koutras
Selective Credibility-Limited Belief Update
• For property (F3), suppose first that ∩ Cw ̸= ∅. Then, fwCCL (φ) = φ, and thus, we have [φ] CCL CCL CCL immediately that fw fw (φ) = fw (φ). Suppose instead that [φ] ∩ Cw = ∅. Since w ∈ Cw , we have that [φ ∨ γw ] ∩ Cw = {w} ̸= ∅. Hence, fwCCL fwCCL (φ) = fwCCL (φ ∨ γw ) = φ ∨ γw = fwCCL (φ). • Property (F4) follows directly from the first clause of the definition of the transformation function fwCCL . • Property (F5) follows because CCL fw (φ) ∩ Cw =
( [φ] ∩ Cw , if [φ] ∩ Cw ̸= ∅, {w}, otherwise,
and both sets are non-empty in their respective cases. Thus, property (F5) holds. • For property (F6), suppose first that [φ] ∩ Cw ̸= ∅. Then, fwCCL (φ) = φ, so there cannot be a sentence ψ such that φ |= ψ and fwCCL (φ) ̸|= ψ. Suppose instead that [φ] ∩ Cw = ∅, so that fwCCL (φ) = φ ∨ γw . Let ψ satisfy φ |= ψ, ψ |= φ ∨ γw , and [ψ] ∩ Cw ̸= ∅. Choose r ∈ [ψ] ∩ Cw . Since ψ |= φ ∨ γw and [φ] ∩ Cw = ∅, it follows that r = w. Hence, w |= ψ. Since [γw ] = {w}, it follows that γw |= ψ. Together with φ |= ψ, this yields φ ∨ γw |= ψ. Therefore, no strictly stronger credible consequence of φ lies between φ and fwCCL (φ), and property (F6) follows. Finally, if [φ] ∩ Cw ̸= ∅, then fwCCL (φ) = φ, and hence, min fwCCL (φ) ∩ Cw , ⪯w = min [φ] ∩ Cw , ⪯w . If, on the other hand, [φ] ∩ Cw = ∅, then fwCCL (φ) ∩ Cw = [φ ∨ γw ] ∩ Cw = {w}, and therefore, min fwCCL (φ) ∩ Cw , ⪯w = {w}. Consequently, in view of condition (SCL), we obtain that, for every belief set K and every sentence φ ∈ L, [ min [φ] ∩ Cw , ⪯w , if [φ] ∩ Cw ̸= ∅, K ⋄FCCL φ = otherwise, w∈[K] {w}, which is exactly condition (CCL) of Subsection 5.2. Hence, ⋄FCCL is a CCL update operator and, in particular, a maximal consistency-preserving SCL update operator. ■ The preceding propositions, together with the semantic characterizations of CL and CCL belief update, yield the following inclusion relations between the corresponding classes of update operators. 33
T. Aravanis and C. D. Koutras
Selective Credibility-Limited Belief Update
Corollary 25. Every CL update operator is an SCL update operator, while every CCL update operator is a maximal consistency-preserving SCL update operator. Proof. Let ⋄ be a CL update operator. By Theorem 8, there exists a credible faithful assignment w 7→ (Cw , ⪯w ) representing ⋄ by condition (CL). Applying Proposition 23 to this assignment, with fwCL (φ) = φ, yields a pointwise transformation assignment FCL satisfying properties (F1)–(F4), such that condition (SCL) holds for ⋄. Hence, every CL update operator is an SCL update operator. Now, let ⋄ be a CCL update operator. By Theorem 11, there exists a credible faithful assignment w 7→ (Cw , ⪯w ) representing ⋄ by condition (CCL). Applying Proposition 24 to this assignment yields a pointwise transformation assignment FCCL satisfying properties (F1)–(F6), such that condition (SCL) holds for ⋄. Hence, every CCL update operator is a maximal consistency-preserving SCL update operator. ■
8.2
KM Belief Update within the SCL Hierarchy
Corollary 25 establishes that CL and CCL update operators arise as sub-classes of the class of SCL update operators. To complete the inclusion structure among the principal classes considered in this article, we now locate standard KM belief update within this hierarchy. KM belief update is recovered by taking every credible set to be the entire set of worlds and every transformation function to be the identity. Proposition 26. Every KM update operator is a CL update operator and a maximal consistencypreserving SCL update operator. Proof. Let ⋄ be a KM update operator. By Theorem 3, there exists a faithful pointwise assignment [ w 7→⪯w such that [K ⋄ φ] = min([φ], ⪯w ). For every world w ∈ M, put Cw = M and define w∈[K]
fw (φ) = φ. Since Cw = M, condition (CL) reduces to [K ⋄ φ] =
[
min [φ], ⪯w , which is
w∈[K]
exactly condition (U). Therefore, ⋄ is a CL update operator. Moreover, the identity transformation fw (φ) = φ satisfies properties (F1)–(F4) and (F6). It also satisfies property (F5), since, whenever [φ] [ ̸= ∅, [fw (φ)] ∩ Cw = [φ] ∩ M = [φ] ̸= ∅. Finally, condition (SCL) reduces to [K ⋄ φ] = min [φ], ⪯w , which is again exactly condition (U). w∈[K]
Therefore, ⋄ is a maximal consistency-preserving SCL update operator.
■
Remark 27. When the epistemic input φ is consistent and Cw = M, for every w ∈ M, condition (CCL) of Theorem 11 reduces to condition (U). Thus, under unrestricted credibility, KM and CCL belief update coincide on consistent epistemic inputs. This coincidence does not, however, amount to an inclusion between the corresponding classes of operators over the unrestricted domain of epistemic inputs.
34
T. Aravanis and C. D. Koutras
Selective Credibility-Limited Belief Update
SCL Update Operators (K ⋄ 1), (K ⋄ 2)S , (K ⋄ 3), (K ⋄ 5), (K ⋄ 6)S , (K ⋄ 7), (K ⋄ 8)S , (K ⋄ 9), (LC)
CL Update Operators
Consistency-Preserving SCL Update Operators
(K ⋄ 1)–(K ⋄ 3), (K ⋄ 5)–(K ⋄ 9)
(K ⋄ 1), (K ⋄ 2)S , (K ⋄ 3), (K ⋄ 4), (K ⋄ 5), (K ⋄ 6)S , (K ⋄ 7), (K ⋄ 8)S , (K ⋄ 9), (LC)
Maximal Consistency-Preserving SCL Update Operators
CCL Update Operators
(K ⋄ 1), (K ⋄ 2)SM , (K ⋄ 3), (K ⋄ 4), (K ⋄ 5),
(K ⋄ 1), (K ⋄ 3)–(K ⋄ 9), (RSC), (SM), (IR)
(K ⋄ 6)S , (K ⋄ 7), (K ⋄ 8)S , (K ⋄ 9), (LC)
KM Update Operators (K ⋄ 1)–(K ⋄ 9)
coincide if Cw = M and [φ] ̸= ∅
Figure 1: Relations among the principal classes of SCL update operators. Solid arrows point from proper sub-classes to their super-classes. The dashed bidirectional arrow indicates that KM and CCL belief update coincide under unrestricted credibility for consistent epistemic inputs.
8.3
Inclusion Hierarchy and Strictness
The inclusion relations established above yield the hierarchy depicted in Figure 1. Maximal consistency-preserving SCL update operators form a sub-class of consistency-preserving SCL update operators, which in turn form a sub-class of SCL update operators. CL update operators form a sub-class of SCL update operators, whereas CCL update operators form a sub-class of maximal 35
T. Aravanis and C. D. Koutras
Selective Credibility-Limited Belief Update
consistency-preserving SCL update operators. KM update operators form a common sub-class of CL update operators and maximal consistency-preserving SCL update operators. Moreover, under unrestricted credibility, KM and CCL belief update coincide whenever the epistemic input is consistent. As a matter of fact, the inclusions depicted in Figure 1 are all proper, as Proposition 28 below proves. Hence, the proposed SCL framework offers a unified and strictly more expressive model of belief update, as it subsumes the established approaches, while also accommodating sourcedependent selective acceptance. Proposition 28. All inclusion relations represented by the solid arrows in Figure 1 are proper. Proof. Fermé et al. [12] show that expansion is a simple example of a CL update operator that is not a KM update operator. Since expansion may produce an inconsistent result from a consistent prior belief set and a consistent epistemic input, it is not a consistency-preserving SCL update operator. Hence, the class of KM update operators is a proper sub-class of the class of CL update operators, while the class of consistency-preserving SCL update operators is a proper sub-class of the class of SCL update operators. The CCL update operator illustrated in Example 12 of Subsection 5.2 does not satisfy the success postulate (K ⋄ 2), since φ ∈ / K ⋄CCL φ. Therefore, it is neither a KM nor a CL update operator. Since every CCL update operator is a maximal consistency-preserving SCL update operator, this establishes that KM update operators form a proper sub-class of maximal consistency-preserving SCL update operators. It also shows that CL update operators form a proper sub-class of SCL update operators. It remains to separate the class of CCL update operators from the class of maximal consistencypreserving SCL update operators. Consider a language built from P = {a, b}, and let the worlds w = āb̄ and r = ab̄. Define a credible faithful assignment by setting Cw = {w, r}, with w ≺w r, and Cu = {u}, with ⪯u = {(u, u)}, for every u ∈ M \ {w}. For each u ∈ M, let γu be a complete sentence such that [γu ] = {u}. Define the source-dependent transformation functions by ( χ, if [χ] ∩ Cw ̸= ∅, fw (χ) = χ ∨ γr , otherwise, and, for every u ̸= w, by ( χ, fu (χ) = χ ∨ γu ,
if u ∈ [χ], otherwise.
Let F = {fu : u ∈ M}, and let ⋄ be the SCL update operator determined by the above credible faithful assignment and the pointwise transformation assignment F, through condition (SCL). By the same argument as in Proposition 24, we can show that F satisfies properties (F1)–(F6). Hence, ⋄ is a maximal consistency-preserving SCL update operator. Now, let K = Cn(w) and φ = a ∧ b. Since [φ] ∩ Cw = ∅, we have that fw (φ) = φ ∨ γr and [fw (φ)] ∩ Cw = {r}. Therefore, condition (SCL) gives [K ⋄ φ] = {r}. Since r ̸|= φ and r ̸= w, we have that φ ∈ / K ⋄ φ and K ⋄ φ ̸= K. Thus, postulate (RSC) of Definition 10 fails, and ⋄ is not
36
T. Aravanis and C. D. Koutras
Selective Credibility-Limited Belief Update
a CCL update operator. Therefore, the class of CCL update operators is a proper sub-class of the class of maximal consistency-preserving SCL update operators. Finally, to separate the class of maximal consistency-preserving SCL update operators from the class of consistency-preserving SCL update operators, consider a language built from P = {a, b}, and let the worlds w = āb̄, r1 = ab̄, and r2 = āb. Define a credible faithful assignment by setting Cw = {w, r1 , r2 }, where w ≺w r1 , w ≺w r2 , and r1 and r2 are incomparable with respect to ⪯w . For every u ∈ M \ {w}, put Cu = {u} and ⪯u = {(u, u)}. Define the transformation function associated with w by χ, if [χ] ∩ Cw ̸= ∅, fw (χ) = a ∨ b, if χ ≡ a ∧ b, ⊤, otherwise. For every u ∈ M \ {w}, let γu be a complete sentence such that [γu ] = {u}, and define ( χ, if u ∈ [χ], fu (χ) = χ ∨ γu , otherwise. Let F = {fu : u ∈ M}, and let ⋄ be the SCL update operator determined by the above credible faithful assignment and the pointwise transformation assignment F, through condition (SCL). It is readily verified that F satisfies properties (F1)–(F5). Hence, ⋄ is a consistency-preserving SCL update operator. Now, let K = Cn(w) and φ = a ∧ b. Since [φ] ∩ Cw = ∅, we have that fw (φ) = a ∨ b and [fw (φ)] ∩ Cw = {r1 , r2 }. Since r1 and r2 are incomparable with respect to ⪯w , condition (SCL) gives [K ⋄ φ] = {r1 , r2 }. Suppose that a sentence ψ ∈ L satisfies φ |= ψ, ψ ∈ K ⋄ φ, and K ⋄ φ = K ⋄ ψ. Since ψ ∈ K ⋄ φ, both r1 and r2 satisfy ψ; moreover, φ |= ψ entails that ab |= ψ. As the language contains only the atoms a and b, it follows that ψ is logically equivalent either to a ∨ b or to ⊤. The latter possibility is excluded because [K ⋄ ⊤] = {w} ̸= {r1 , r2 }. Hence, every possible witness ψ for postulate (K ⋄ 2)SM is logically equivalent to a ∨ b. Consider now the sentence χ = a. We have that φ |= a and a |= a ∨ b, and, since [a] ∩ Cw = {r1 }, [K ⋄ a] = {r1 }. Consequently, a ∈ K ⋄ a, while a ∨ b ̸|= a. Thus, no possible witness ψ satisfies the maximality requirement of postulate (K ⋄ 2)SM . Therefore, ⋄ is not a maximal consistency-preserving SCL update operator. Hence, the class of maximal consistencypreserving SCL update operators is a proper sub-class of the class of consistency-preserving SCL update operators. The aforementioned separating examples establish the strictness of every inclusion represented in Figure 1. ■
9
Conclusion
This article introduced selective credibility-limited belief update, a non-prioritized framework that builds on three principal lines of research; namely, the pointwise semantics of Katsuno–Mendelzon 37
T. Aravanis and C. D. Koutras
Selective Credibility-Limited Belief Update
(KM) belief update [17], the credibility-limited (CL) and consistent credibility-limited (CCL) belief-update models of Fermé et al. [12], and the transformation-based approach developed for selective belief revision [10]. The proposed framework combines these ideas by integrating sourcedependent transformation functions into credibility-limited transition structures. For each initially possible world, the epistemic input is first replaced by a weaker proxy representing the information that can be accepted from that source world; the most plausible credible worlds of the resulting proxy are then selected as possible successors. This two-stage construction preserves the pointwise character of KM belief update, while overcoming the all-or-nothing treatment of compound epistemic inputs found in existing credibility-limited approaches [12]. We provided both semantic and axiomatic characterizations of the resulting class of selective credibility-limited (SCL) update operators. We also identified two progressively more constrained sub-classes. Consistency-preserving SCL update operators require every transformed epistemic input to have a credible world relative to its source world whenever the original epistemic input is consistent, thus ensuring that every initially possible world contributes at least one successor in such cases. Maximal consistency-preserving SCL update operators additionally require, for every consistent epistemic input, the selected proxy to be maximally informative among its credible consequences. The corresponding representation results clarify the relationship between the semantic properties imposed on source-dependent transformations and the observable rationality properties of the induced update operators. The SCL framework also provides a unified perspective on the established approaches from which it originates. CL belief update is recovered by taking all source-dependent transformation functions to be identities, whereas CCL belief update is obtained by replacing locally non-credible epistemic inputs with proxies that retain the corresponding source worlds. Standard KM belief update is recovered by additionally removing the credibility restrictions. Moreover, the inclusion results establish that the principal classes considered herein are related by proper containment. Therefore, selective credibility-limited belief update provides a strictly more expressive framework than the established approaches it encompasses, as it supports source-dependent partial acceptance, without requiring the elimination or unchanged retention of source branches from which the complete epistemic input cannot be realized. Several directions for future work arise from the proposed framework. First, further study could address more relaxed variants of the framework, including selective belief update based only on properties (F1)–(F3), as specified in Subsection 6.3, as well as intermediate settings obtained by weakening the full set of requirements (F1)–(F4). Additional properties of pointwise transformation assignments could also be investigated, drawing on the conditions studied for transformation functions in selective belief revision [10, p. 335]. In particular, source-relative counterparts of monotonicity, negation conditions, conjunctive and disjunctive distribution, and disjunctive factoring may yield additional well-behaved classes of SCL update operators and corresponding axiomatic characterizations. Related questions concern the existence and uniqueness of admissible proxies, as well as the computational complexity of determining them and computing the resulting updates. Further work may also address iterated belief update [9, 7], and extensions to richer logical settings [21], multi-agent settings [24, 19], and action-based formalisms [5, 23].
38
T. Aravanis and C. D. Koutras
Selective Credibility-Limited Belief Update
Declarations Competing Interests: The authors have no relevant financial or non-financial interests to disclose. Data Availability: Data sharing is not applicable to this article as no datasets were generated or analysed during the current study.
References [1] Carlos Alchourrón, Peter Gärdenfors, and David Makinson. On the logic of theory change: Partial meet contraction and revision functions. Journal of Symbolic Logic, 50(2):510–530, 1985. [2] Theofanis I. Aravanis. On the consistency between belief revision and belief update. Journal of Artificial Intelligence Research, 82:1743–1771, 2025. [3] Gregor Behnke, David Speck, Michael Katz, and Shirin Sohrabi. On partial satisfaction planning with total-order HTNs. In Proceedings of the 33rd International Conference on Automated Planning and Scheduling (ICAPS 2023), pages 42–51, 2023. [4] Giacomo Bonanno. A Kripke-Lewis semantics for belief update and belief revision. Artificial Intelligence, 339:104259, 2025. [5] Alvaro del Val and Yoav Shoham. Deriving properties of belief update from theories of action. Journal of Logic, Language and Information, 3:81–119, 1994. [6] James Delgrande, Yi Jin, and Francis Jeffry Pelletier. Compositional belief update. Journal of Artificial Intelligence Research, 32:757–791, 2008. [7] Liangda Fang, Tong Zhu, Quanlong Guan, Junming Qiu, Zhao-Rong Lai, Weiqi Luo, and Hai Wan. On the logic of theory change iteration of KM-update, revised. In Proceedings of the 33rd International Joint Conference on Artificial Intelligence (IJCAI 2024), pages 3351–3359. International Joint Conferences on Artificial Intelligence Organization, 2024. [8] Eduardo Fermé, Marco Garapa, and Maurı́cio D. L. Reis. Non-prioritized Belief Change. Springer Cham, 2026. [9] Eduardo Fermé and Sara Gonçalves. On the logic of theory change iteration of KM-update. International Journal of Approximate Reasoning, 162:109005, 2023. [10] Eduardo Fermé and Sven Ove Hansson. Selective revision. Studia Logica, 63:331–342, 1999. [11] Eduardo Fermé and Sven Ove Hansson. Belief Change: Introduction and Overview. Springer International Publishing, 2018.
39
T. Aravanis and C. D. Koutras
Selective Credibility-Limited Belief Update
[12] Eduardo Fermé, Sébastien Konieczny, Ramón Pino Pérez, and Nicolas Schwind. Credible models of belief update. In Proceedings of the 20th International Conference on Principles of Knowledge Representation and Reasoning (KR 2023), pages 252–261, 2023. [13] Marco Garapa. Selective base revisions. Journal of Philosophical Logic, 51:1–26, 2022. [14] Peter Gärdenfors. Knowledge in Flux: Modeling the Dynamics of Epistemic States. MIT Press, Cambridge, Massachusetts, 1988. [15] Daniel A. Grimaldi, M. Vanina Martinez, and Ricardo O. Rodriguez. Updating the belief promotion operator. In Proceedings of the 30th International Joint Conference on Artificial Intelligence (IJCAI 2021), pages 1901–1907, 2021. [16] Hirofumi Katsuno and Alberto Mendelzon. Propositional knowledge base revision and minimal change. Artificial Intelligence, 52(3):263–294, 1991. [17] Hirofumi Katsuno and Alberto Mendelzon. On the difference between updating a knowledge base and revising it. In Peter Gärdenfors, editor, Belief Revision, pages 183–203. Cambridge University Press, 1992. [18] Arthur Keller and Marianne Winslett. On the use of an extended relational model to handle changing incomplete information. IEEE Transactions on Software Engineering, 11:620–633, 1985. [19] Emiliano Lorini and François Schwarzentruber. Multi-agent belief base revision. In Proceedings of the 30th International Joint Conference on Artificial Intelligence (IJCAI 2021), pages 1959–1965, 2021. [20] Pavlos Peppas, Abhaya C. Nayak, Maurice Pagnucco, Norman Foo, R. Kwok, and Mikhail Prokopenko. Revision vs. update: Taking a closer look. In W. Wahlster, editor, Proceedings of the 12th European Conference on Artificial Intelligence (ECAI 1996), pages 95–99, Budapest, Hungary, 1996. John Wiley & Sons, Ltd. [21] Márcio Moretto Ribeiro. Belief Revision in Non-Classical Logics. SpringerBriefs in Computer Science. Springer, 2013. [22] Nicolas Schwind, Sébastien Konieczny, and Pierre Marquis. On belief promotion. In Proceedings of the 16th International Conference on Principles of Knowledge Representation and Reasoning (KR 2018), pages 297–306, 2018. [23] Steven Shapiro, Maurice Pagnucco, Yves Lespérance, and Hector J. Levesque. Iterated belief change in the situation calculus. Artificial Intelligence, 175(1):165–192, 2011. [24] Luciano H. Tamargo, Alejandro J. Garcı́a, Matthias Thimm, and Patrick Krümpelmann. Selective revision with multiple informants and argumentative support. Inteligencia Artificial, 15(50):4–17, 2012.
40