On the logic of theory change: iteration of expansion

Constructing models that allow for iterated changes is one of the most studied problems in the literature on belief change. However, up to now, iteration of expansion was only studied as a special case of consistent revision and, as far we know, there is no work in the literature that deals with expansions into inconsistency in a supraclassical framework.

In this paper, we provide a semantics for iterated expansion, as well as its axiomatic characterization. We extend the model to two well-known families of iterated belief change (natural and lexicographic). Iteration of expansion can be combined with existent models of iteration of revision and contraction. Since we are able to accommodate different inconsistent belief states, iteration of expansion allows us to define new belief change functions that are currently only defined for belief bases: semi-revision, external revision, as well as consolidation.

Belief revision addresses the problem of changing a knowledge base in the presence of new information. The main paradigm in the literature is known as the AGM theory, after the initials of the authors of the seminal paper [1]. AGM distinguishes three different kinds of change: expansion, where new information is simply added to the knowledge base; contraction, where information is removed; and revision, where new information is added preserving logical consistency, i.e., removing previous information if needed.

The AGM theory has been widely criticized for not providing a framework where the change operations can be iterated. The AGM operations come equipped with some choice mechanism which depends on the initial knowledge base. After applying the operation, we have a new set, but no choice mechanism for it. Darwiche and Pearl have enriched the AGM theory with extra postulates to deal with iterated revision [10]. Meanwhile, several newer proposals appeared for iterated revision (see [25] for an overview), but only a few dealing with contraction [4, 23, 28]. Expansion is usually a very simple operation, and when the new information is consistent with the existing knowledge base it can be seen as a special case of revision. But the case of expansion into inconsistency has been overlooked in the iterated change literature.

In the AGM framework, a knowledge base is represented by a belief set, a set of formulas closed under (classical) logical consequence. This means that if the result of an expansion is inconsistent, all information is lost as there is a unique inconsistent belief set, corresponding to the full language. However, this is highly unintuitive as we think about iterated change operations. Inconsistency can be momentaneous and disappear after the next change. As the example below shows, contracting after an expansion into inconsistency should not always lead to the same result.

Example 1

Ann and Bob believe that the restaurant around the corner is always open for lunch. While being happily married, they do not share the same political convictions. While Ann admires the new president and thinks he is trustworthy, Bob is sure the president is not to be trusted. One day, they arrive at the corner at lunch time and see that the restaurant is closed. For a moment, they both hold inconsistent beliefs. When they notice the inconsistency, they solve it by contracting the belief that the restaurant is always open for lunch. And each one continues to hold his own view on the president.

Up to now, inconsistent expansions have only been dealt with in the belief base change literature [12, 16], where the knowledge base is represented by an arbitrary set of sentences, not necessarily closed under logical consequence. Testa, Coniglio, and Ribeiro have recently defined a model for belief states that can deal with inconsistency [30]. Furthermore, they defined external and semi-revision for belief sets. However, they use a paraconsistent logic, whereas in our work we use supraclassical logic. In this paper, we tackle the problem of iterated change involving inconsistent expansions applied to belief sets. We adopt the representation proposed in [10], where belief sets are just one of the components of a more complex belief state. This allows us to account for different belief states even if the belief sets are inconsistent, as in the example above. We then provide an axiomatization and semantics for iterated expansion that covers the inconsistent case, as well as a representation result.

This paper is organized as follows: In “Background” section we introduce the formal preliminaries, the classical AGM model and its extension to iterated belief change. In “Iteration of expansion” section, we define the formal apparatus for iteration of expansion for belief sets. “Different kinds of iterated expansion functions” section is devoted to introducing additional properties to create different kinds of iterated expansion functions. In “Applications” section, we use iteration of expansion to define semi-revision, external revision, and consolidation for belief states. Finally, in the last two sections we develop a concrete example of iteration of expansion and conclusions and future work.

In this section, we briefly introduce the notation and background needed for the rest of the paper.

Formal preliminaries

We will assume a language \(\mathcal {L}\) of finite set of atomic propositions that is closed under truth-functional operations. The elements of \(\mathcal {L}\) are denoted by lower case Greek letters α, β, … (possibly with subscripts). ⊤ stands for an arbitrary tautology and ⊥ for an arbitrary contradiction. We shall make use of a consequence operation Cn that takes sets of sentences to sets of sentences and which satisfies the standard Tarskian properties, namely, inclusion, monotony, and iteration. Furthermore, we will assume that Cn satisfies supraclassicality, compactness, and deduction. We will sometimes use Cn(α) for Cn({α}), A⊩α for α∈Cn(A), ⊩α for α∈Cn(∅), A⊯α for α∉Cn(A), ⊯α for α∉Cn(∅). K is reserved to represent a belief set (i.e., K=Cn(K)). Since \(\mathcal {L}\) is finite, we can define a belief set as a propositional sentence φ, such that K=Cn(φ).

An important class of subsets of \(\mathcal {L}\) are its inclusion-maximal consistent subsets, more commonly called possible worlds. The set of possible worlds will be denoted by \(\mathfrak {W}\). Given a set of sentences A, the set consisting of all the possible worlds that contain A is denoted by ∥A∥. The elements of ∥A∥ are called A-worlds. ∥φ∥ is an abbreviation of ∥{φ}∥ and the elements of ∥φ∥ are the φ-worlds. To any set of possible worlds \(\mathcal {V}\), we associate a belief set \(Th(\mathcal {V})\) given by \(Th(\mathcal {V}) = \bigcap \mathcal {V} -\) under the assumption that \(\bigcap \emptyset = \mathcal {L}\). If M is a set of possible worlds, we denote by α_M a formula such that ∥α_M∥=M. If ≤ is a total pre-order (a total and transitive relation), then ≃ is a notation for the associated equivalence relation (a≃b iff a≤b and b≤a), and < is the notation for the associated strict order (a<b iff a≤b and b≦̸a).

The AGM model for belief change

In the model proposed by Alchourrón, Gärdenfors, and Makinson, there are three change operations for a belief set K (or φ, when K=Cn({φ})):

• Expansion. A sentence α is added to the belief set and nothing is removed (represented as K+α);

• Contraction. A sentence α is removed (unless α is a tautology) from the belief set and nothing is added (represented as K−α);

• Revision. A sentence α is added to the belief set, and at the same time, other sentences are removed if necessary to ensure the consistency of the revised set (represented as K∗α).

Expansion is the simplest operation and is defined as K+α=Cn(K∪{α}) or φ+α≡_defφ∧α when K=Cn(φ). Alchourrón, Gärdenfors, and Makinson have proposed two sets of independent postulates to govern the process of belief contraction and revision [1]. Katsuno and Mendelzon rephrased these postulates for a finite language [18]. (R1) φ∗α⊩α (R2) If \(\varphi \wedge \alpha \nvdash \bot \), then φ∗α≡φ∧α (R3) If \(\alpha \nvdash \bot \), then \(\varphi * \alpha \nvdash \bot \) (R4) If φ₁≡φ₂ and α₁≡α₂, then φ₁∗α₁≡φ₂∗α₂ (R5) (φ∗α)∧ψ⊩φ∗(α∧ψ) (R6) If \((\varphi * \alpha) \wedge \psi \nvdash \bot \), then φ∗(α∧ψ)⊩(φ∗α)∧ψ

Along with this definition, Katsuno and Mendelzon provided a representation theorem that shows an equivalence between the postulates and a revision mechanism based on total pre-orders where these are defined as the following:

Definition 1

Let \(\mathfrak {W}\) be the set of all worlds of \(\mathcal {L}\). A function that maps each sentence φ in \(\mathcal L\) to a total pre-order ≤_φ on worlds \(\mathfrak {W}\) is called a faithful assignment if and only if^{Footnote 1}:

1. 1.

   If φ∈ω₁ and φ∈ω₂, then ω₁=_φω₂

2. 2.

   If φ∈ω₁ and φ∉ω₂, then ω₁<_φω₂

Their representation theorem shows that a revision operator is equivalent to a faithful assignment where the result of a revision φ∗α is determined by α and the total pre-order assigned to φ:

Proposition 1

Katsuno and Mendelzon [18] A revision operator ∗ satisfies postulates (R1) – (R6) precisely when there exists a faithful assignment that maps each sentence φ into a total pre-order ≤_φ such that

where ∥α∥ is the set of all worlds satisfying αand min(∥α∥,≤_φ) contains all worlds that are minimal in ∥α∥ according to the total pre-order ≤_φ, i.e., all the worlds that include α and are closest to φ.

Iterated change

In order to represent iterated (repeated) belief change, we need models in which the outcome of a belief contraction or a belief revision can itself be contracted or revised. This is not possible if the outcome of a contraction or revision consists only of a new belief set. It also has to contain information on how that new belief set will be changed in response to new inputs. Whereas standard AGM operations take us from a complete belief state (belief set + change mechanism) to an incomplete belief state (belief set only), for iterated change, we need operations that take us from a complete belief state to another complete belief state.

The most influential formulation of this approach is due to Darwiche and Pearl:

Definition 2

Darwiche and Pearl [10] Let there be a set \({\mathcal {E}}\) of objects called belief states. A belief state is an object Ψ to which we associate a propositional formula B(Ψ) that denotes the current beliefs of the agent in the epistemic state.

Darwiche and Pearl modified the list of the Katsuno and Mendelzon postulates for revision to work in the more general framework of belief states: (R*1) B(Ψ∗α)⊩α nem[(R*2)] If \(B(\Psi) \wedge \alpha \nvdash \bot \), then B(Ψ∗α)≡B(Ψ)∧α (R*3) If \(\alpha \nvdash \bot \), then \(B(\Psi * \alpha) \nvdash \bot \) (R*4) If Ψ₁=Ψ₂ and α₁≡α₂, then B(Ψ₁∗α₁)≡B(Ψ₂∗α₂) (R*5) B(Ψ∗α)∧ψ⊩B(Ψ∗(α∧ψ)) (R*6) If \(B(\Psi * \alpha) \wedge \psi \nvdash \bot \), then B(Ψ∗(α∧ψ))⊩B(Ψ∗α)∧ψ

For the most part, the Darwiche and Pearl postulates are obtained from the Katsuno and Mendelzon ones by replacing each φ by B(Ψ) and each φ∗α by B(Ψ∗α). The only exception to this is (R*4), which is stronger than its simple translation.

In addition to this set of basic postulates, Darwiche and Pearl proposed a set of postulates devoted to iteration: (DP1) If α⊩μ, then B((Ψ∗μ)∗α)≡B(Ψ∗α) (DP2) If α⊩¬μ, then B((Ψ∗μ)∗α)≡B(Ψ∗α) (DP3) If B(Ψ∗α)⊩μ then B((Ψ∗μ)∗α)⊩μ (DP4) If \(B(\Psi *\alpha)\nvdash \neg \mu \), then \(B((\Psi *\mu)*\alpha) \nvdash \neg \mu \)

In [5,17], admissible revision operators are defined as operators satisfying (DP1), (DP2), and a new postulate (P) (note that (DP3) and (DP4) can be obtained as consequences: (P) If B(Ψ∗α)⊯¬μ, then B((Ψ∗μ)∗α)⊩μ

The semantics for iterated revision is defined as follows:

Definition 3

[10,18] Let Ψ be a belief state. A total pre-order ≤_Ψ on possible worlds, with the strict part <_Ψ and the symmetric part ≃_Ψ, is a faithful assignment associated with the belief state Ψ if and only if the following conditions hold for every \(\omega, \omega ' \in \mathfrak {W}\):

1. 1.

   If ω⊩B(Ψ) and ω^′⊩B(Ψ), then ω≃_Ψω^′.

2. 2.

   If ω⊩B(Ψ) and ω^′⊯B(Ψ), then ω<_Ψω^′.

Observation 1

Darwiche and Pearl [10] Let Ψ be a belief state:

1. 1.

   An operation ∗ on Ψ satisfies (R*1)–(R*6) if and only if there is a faithful assignment ≤_Ψ for Ψ such that ∥B(Ψ∗α)∥=min(∥α∥,≤_Ψ).

2. 2.

   ∗ also satisfies (DP1)–(DP4) if and only if ≤_Ψ satisfies: (DPR1) If α∈ω₁ and α∈ω₂, then ω₁≤_Ψω₂ if and only if ω₁≤_Ψ∗αω₂. (DPR2) If ¬α∈ω₁ and ¬α∈ω₂, then ω₁≤_Ψω₂ if and only if ω₁≤_Ψ∗αω₂. (DPR3) If α∈ω₁, ¬α∈ω₂ and ω₁<_Ψω₂, then ω₁<_Ψ∗αω₂. (DPR4) If α∈ω₁, ¬α∈ω₂ and ω₁≤_Ψω₂, then ω₁≤_Ψ∗αω₂.

In terms of faithful assignment, postulate (P) corresponds to the following property [5,17]: (R-P) If α∈ω₁, ¬α∈ω₂, and ω₁≤_Ψω₂, then ω₁<_Ψ∗αω₂.

The original AGM postulates for contraction [1] were adapted to propositional finite logic and belief states [8]: (C-1) B(Ψ)⊩B(Ψ−α) (C-2) If B(Ψ)⊯α, then B(Ψ−α)⊩B(Ψ) (C-3) If B(Ψ−α)⊩α, then ⊩α (C-4) B(Ψ−α)∧α⊩B(Ψ) (C-5) If B(Ψ₁)=B(Ψ₂) and α₁≡α₂, then B(Ψ₁−α₁)≡B(Ψ₂−α₂) (C-6) B(Ψ−(α∧ψ))⊩B(Ψ−α)∨B(Ψ− ψ) (C-7) If B(Ψ−(α∧ψ))⊯α, then B(Ψ−α)⊩B(Ψ−(α∧ψ))

For the case of iterated contraction, the following are the counterpart of Darwiche and Pearl’s iterated revision postulates [9,19]: (DP-1) If α⊩¬μ, then B((Ψ−μ)∗α)≡B(Ψ∗α) (DP-2) If α⊩μ, then B((Ψ∗μ)−α)≡B(Ψ∗α) (DP-3) If B((Ψ∗α)⊩¬μ, then B((Ψ−μ)∗α)⊩¬μ (DP-4) If \(B((\Psi *\alpha)\nvdash \mu \), then \(B((\Psi -\mu)*\alpha) \nvdash \mu \) (P-) If \(B((\Psi *\alpha)\nvdash \mu \), then B((Ψ−μ)∗α)⊩¬μ

In order to define iteration of expansion, we first need to define what it means to expand a belief state:

Definition 4

Let Ψ be a belief state. + is an expansion function for Ψ if and only if B(Ψ+α)≡B(Ψ)∧α.

Observation 2

Let Ψ be a belief state and ≤_Ψ its associate faithful assignment. Then \({\Vert {B(\Psi + \alpha)}\Vert } = min(\mathfrak {W}, \leq _{\Psi })\cap {\Vert {\alpha }\Vert }\).

Due to the definition of revision, B(Ψ+α₁+⋯+α_n), iteration of expansion is well defined when B(Ψ+α₁+⋯+α_n)⊯⊥. In order to cover the inconsistent case, we need to adapt the (DP1) – (DP4) and (P) postulates for expansion: (DP1+) If α⊩μ, then B((Ψ+μ)∗α)≡B(Ψ∗α) (DP2+) If α⊩¬μ, then B((Ψ+μ)∗α)≡B(Ψ∗α) (DP3+) If B(Ψ∗α)⊩μ, then B((Ψ+μ)∗α)⊩μ (DP4+) If \(B(\Psi *\alpha)\nvdash \neg \mu \), then \(B((\Psi +\mu)*\alpha) \nvdash \neg \mu \) (P+) If B(Ψ∗α)⊯¬μ, then B((Ψ+μ)∗α)⊩μ

Given the revision postulates (R1)–(R6), (P+) is stronger than (DP3+) and (DP4+).

To provide a semantics for iteration of expansion, we have to solve the same problem as in the syntactic level, i.e., when B(Ψ+α₁+⋯+α_n)⊩⊥ and hence, ∥B(Ψ+α₁+⋯+α_n)∥=∅. Therefore, we propose to extend the set of possible worlds by adding \(\omega _{\bot } = \mathcal {L}\), that we call impossible world^{Footnote 2}. We denote \(\mathfrak {W}+ = \mathfrak {W}\cup \{ \omega _{\bot }\}\).

Definition 5

Let Ψ be a belief state. A total pre-order ≤_Ψ on \(\mathfrak {W}+\), with the strict part <_Ψ and the symmetric part ≃_Ψ, is an extended faithful assignment associated with the belief state Ψ if and only if the following conditions holds:

1. 1.

   If ω⊩B(Ψ) and ω^′⊩B(Ψ), then ω≃_Ψω^′.

2. 2.

   If ω⊩B(Ψ) and ω^′⊯B(Ψ), then ω<_Ψω^′.

Note that for all Ψ, ω_⊥∈∥B(Ψ)∥, so the two conditions in Definition 5 always hold for the impossible world.

Expansion and revision, in terms of extended faithful assignment can be easily adapted as follows:

Observation 3

Let Ψ be a belief state and ≤_Ψ its associate extended faithful assignment. Then \({\Vert {B(\Psi + \alpha)}\Vert } = {\text {min}}(\mathfrak {W}+, \leq _{\Psi })\cap {\Vert {\alpha }\Vert }\).

When B(Ψ+α)⊩⊥, \({\text {min}}(\mathfrak {W}, \leq _{\Psi })\cap {\Vert {\alpha }\Vert }= \emptyset \) whereas \({\text {min}}(\mathfrak {W}+, \leq _{\Psi })\cap {\Vert {\alpha }\Vert } = \omega _{\bot }\)

Observation 4

Let Ψ be a belief state. An operation ∗ on Ψ satisfies (R1)–(R6) if and only if there is an extended faithful assignment ≤_Ψ for Ψ such that ∥B(Ψ∗α)∥=min((∥α∥∖ω_⊥),≤_Ψ)∪ω_⊥.^{Footnote 3}

We can enrich extended faithful assignment with some additional properties in order to define the iteration of expansion for belief states: (DPR1+) If α∈ω₁ and α∈ω₂, then ω₁≤_Ψω₂ if and only if ω₁≤_Ψ+αω₂. (DPR2+) If ¬α∈ω₁ and ¬α∈ω₂, then ω₁≤_Ψω₂ if and only if ω₁≤_Ψ+αω₂. (DPR3+) If α∈ω₁, α∉ω₂ and ω₁<_Ψω₂, then ω₁<_Ψ+αω₂. (DPR4+) If α∈ω₁, α∉ω₂ and ω₁≤_Ψω₂, then ω₁≤_Ψ+αω₂. (R-P+) If α∈ω₁, α∉ω₂, and ω₁≤_Ψω₂, then ω₁<_Ψ+αω₂.

Theorem 1

Let Ψ be a belief state. Let + be an expansion on Ψ. Then + also satisfies:

1. 1.

   (DP1+) if and only if ≤_Ψ satisfies (DPR1+).

2. 2.

   (DP2+) if and only if ≤_Ψ satisfies (DPR2+).

3. 3.

   (DP3+) if and only if ≤_Ψ satisfies (DPR3+).

4. 4.

   (DP4+) if and only if ≤_Ψ satisfies (DPR4+).

5. 5.

   (P+) if and only if ≤_Ψ satisfies (R-P+).

The most controversial point of our work is, undoubtedly, the definition of the impossible world ω_⊥. Although in our case, ω_⊥ is mainly a technical device in order to preserve the untouchable formal apparatus of classical faithful assignment, the controversy about impossible worlds has a long tradition in Philosophy^{Footnote 4}.

The impossible world has also been called non-normal world. Non-normal worlds were introduced by Saul Kripke in [20] to provide a semantics for modal logic where the necessitation rule was not valid. Zalta pointed out that

• [t]hese atypical worlds have been used in the following ways: (1) to interpret unusual modal logics, (2) to distinguish logically equivalent propositions, (3) to solve the problems associated with propositional attitude contexts, intentional contexts, and counterfactuals with impossible antecedents, and (4) to interpret systems of relevant and paraconsistent logic [31].

One of the first attempts to develop a metaphysical theory and a deep analysis of impossible worlds was due to Priest [26]. In this paper, he pointed out that in general, non-normal worlds were defined as a mere technical device with no real significance. According to Priest, non-normal worlds are essentially those where theorems, that is, semantically logical truths, may fail. In the rest of the paper, he analyzed the essence of impossible worlds, their semantics, and proof theory. Later, Priest [27] has edited a special issue of the Notre Dame Journal of Formal Logic to discuss the topic [24].

In our case, ω_⊥ plays a technical role in order to guarantee that even in the presence of inconsistency, parts of the underlying order of a belief state are preserved and play a role when consistency is regained.

Postulates (DP1+)–(DP4+) and (P+) offer a conceptual schema to define iterable expansion operations. As in the case of revision, we can extend them by means of additional properties in order to define more specific operations. We can adapt to belief expansion the following well-known iterable belief change functions: Natural expansion is adapted from natural revision [6,7,29] (also called conservative). This operation is conservative in the sense that it only makes the minimal changes of the pre-order that are needed to accept the input. In expansion by α, the minimal ¬α-worlds (with the exception of ω_⊥) are moved one step up from the bottom of the pre-order which is otherwise left unchanged. The distinctive characteristics of this operation are (CRNat1) If ω₁∈min(∥α∥,≤_Ψ) and ω₂∉min(∥α∥,≤_Ψ), then ω₁<_Ψ+αω₂. (CRNat2) If ω₁∉min(∥α∥,≤_Ψ) and ω₂∉min(∥α∥,≤_Ψ), then ω₁≤_Ψω₂ if and only if ω₁≤_Ψ+αω₂.

Lexicographic expansion is adapted from lexicographic revision [21,22]. When expanding by α, this operation rearranges the pre-order by placing all the α-worlds at the bottom (but preserving their relative order) and all the ¬α-worlds at the top (but preserving their relative order). It is defined by the following property: (CRLex) If α∈ω₁ and α∉ω₂, then ω₁<_Ψ+αω₂

In the context of belief bases, Hansson has proposed three new operations that may involve inconsistent belief states:

• External revision [12]. Consists in first expanding with the new information and then contracting by its negation (as in Example 1). The intermediate state may be inconsistent.

• Consolidation [11]. Consolidating a belief base amounts to making it consistent, possibly giving up previous beliefs.

• Semi-revision [13]. Semi-revision is an alternative operation of belief revision, where the agent receives an input and then decides whether or not to incorporate it into the belief set. This means that it is a form of non-prioritized revision, i.e., the new information may be discarded^{Footnote 5}. One possible way to implement a semi-revision function is similar to external revision, but the second step is a consolidation instead of a contraction, i.e., φ?α=φ+α−⊥.

In this section, we discuss how these operations may be transferred from the belief base to the belief state setting, allowing us to maintain the elegance of belief sets.

One important advantage of distinguishing different inconsistent belief states is that this feature can be used to construct two different types of revision operations based on contraction, depending on whether the negation of the added sentence is contracted before or after its addition:

Definition 6

Let Ψ a belief state, + an expansion function and − a contraction function. Then,

• Ψ∗α=(Ψ−¬α)+α is an internal revision. Alchourrón et al. [1]

• Ψ∗α=(Ψ+α)−¬α is an external revision. Hansson [12]

Recall Example 1, where Ann and Bob first expand into inconsistency and then contract by the negation of the new information (the restaurant is not open).

External revision recovers from inconsistency by a contraction by the negation of the input. However, it is possible to recover consistency without specifying an input sentence by consolidating the belief state:

Definition 7

A consolidation function for a belief state Ψ, denoted by Ψ! is a function such that B(Ψ!)⊯⊥.

Observation 5

Let Ψ a belief state and ∗ a revision operator for ∗. Then, Ψ∗⊤ is a consolidation function.

Consolidation can be combined with expansion to construct semi-revision:

Definition 8

Let Ψa belief state, + an expansion function, and ! a consolidation function. ? is a semi-revision for Ψ if and only if

Note that as a result of the consolidation, the input sentence may be discarded. Furthermore, the consolidation process may even discard both α and ¬α.

Example 1 revisited

Suppose that instead of seeing that the restaurant is closed, Ann and Bob receive this information from a friend. In this case, even if they still have a contradiction, the new information is not necessarily more important than the previous one. Consequently, it is more natural that they perform a semi-revision instead of an external revision. In the end, each one can believe that the restaurant is open, closed, or be agnostic with respect to that.

Postulates for semi-revision

Let us now look to the semi-revision of belief states in more detail. Postulates for semi-revision were originally proposed by Hansson in [13] in the context of belief bases. Here, we adapt them to belief states.

The first postulate says that if α is consistent with B(Ψ), then α must be accepted: (SR1) If \(B(\Psi) \wedge \alpha \nvdash \bot \), then B(Ψ?α)⊩α

The following postulates are variations of revision postulate (R2): (SR2) B(Ψ)∧α⊩B(Ψ?α) (SR2’) If \(B(\Psi) \wedge \alpha \nvdash \bot \), then B(Ψ?α)⊩B(Ψ)∧α (SR2”) If \(B(\Psi) \wedge \alpha \nvdash \bot \), then B(Ψ?α)≡B(Ψ)∧α

(R3) can be strengthened in the following way, as in semi-revision, an inconsistent input can be rejected: (SR3) \(B(\Psi ? \alpha) \nvdash \bot \)

(R4) is about the irrelevance of syntax. Consequently, it is reasonable to maintain it in semi-revision: (SR4) If Ψ₁=Ψ₂ and α₁≡α₂, then B(Ψ₁?α₁)≡B(Ψ₂?α₂)

Another interesting question is to see when a sentence may be discarded in the semi-revision process: (SRR) If B(Ψ)⊩β and B(Ψ?α)⊯β, then there exists φ^′ such that B(Ψ)∧α⊩φ^′⊩B(Ψ?α), φ^′⊯⊥, but φ^′∧β⊩⊥.

Observation 6

Let Ψ be a belief state, − a contraction function, and ? a semi-revision function on Ψ defined as B(Ψ)?α=B(Ψ)+α−⊥. Then ? satisfies (SR1), (SR2), (SR2’), (SR3), (SR4), and (SRR).

Note that (SR2) together with (SR2’) entails that if α is consistent with the original belief state, that semi-revision by α is the same as an expansion by α.

In this section, we work out an example step by step in order to illustrate the use of iterated expansion.

Example 2

Nat and Lex share the following political convictions: “If the economy grows, then we have a good government” and “If there is a cut in the budget assigned to education, then we have a bad government.” On Friday, they watch a TV program about economy, where some important economists state that the economy is growing. On Saturday, in the news, a reporter comments that the government will make a big cut in the budget assigned to education. On Sunday, they discover that their beliefs imply a contradiction and both try to solve it by consolidating their beliefs.

This example can be modeled by the following logical representation: we take three propositional variables, p,q, and r in this order, encoding respectively the economy is growing, there is a cut in the budget assigned to education, and we have a good government. The original beliefs of Nat and Lex are p→r and q→¬r. We will denote the epistemic state of Nat by Ψ and the epistemic state of Lex by Φ. Thus, ∥B(Ψ)∥=∥B(Φ)∥=∥(p→r)∧(q→¬r)∥={ω_⊥,000,001,101,010}. We will also assume (as their names suggest) that Nat will use a natural iteration strategy and Lex a lexicographic one. For the sake of simplicity, we will complete the rest of the initial belief states by means of the Hamming distance [3]^{Footnote 6}.

We will use the following convention for the graphical representation of the pre-orders. Black lines represent levels in the preorder, where the minimal elements (that correspond to B(Ψ)) are placed on the bottom line. Thus, the initial belief states are

After Nat expands by p, we obtain

After Nat expands by q

After Lex expands by p

After Lex expands by q

The outcomes of applying consolidation (revising by ⊤) differ in both cases:

∥B(((Ψ+p)+q)∗⊤)∥={ω_⊥,101}

∥B(((Φ+p)+q)∗⊤)∥={ω_⊥,110,111}

Note that Nat now believes that we have a good government whereas Lex has no belief about it. This shows that even if both run into inconsistent belief states after the expansions, the states are different since they use different expansion strategies.

In this paper, we have filled the existing gap in iteration functions for AGM by providing iteration of expansion, which coincides with iteration of revision in the consistent case and that can be combined with contractions and revision functions. Thus, it is now possible to create sequences of changes like Ψ+α−β+γ∗δ…

We defined and characterized the basic model and showed two families of iteration of expansion. Moreover, we use iteration of expansion to bring from belief bases to belief sets the functions of external revision, consolidation, and semi-revision.

There are numerous research paths opened by this work:

• In belief bases, neither external or internal revision is a special case of the other [12]. It is still an open question whether both operations coincide for belief states.

• We will analyze which properties emerge in the combination of the three AGM belief change functions, sharing or not the same strategies (i.e., all of them lexicographic or combine lexicographic contraction with natural expansion).

• We will investigate if there exist interesting families of iterated expansion functions that are not necessarily related to the classical families of iterated revision or contraction.

• We would like to further explore the relation between our model and the paraconsistent model proposed in [30] looking for possible mappings between them.

Lemma 1

Hansson [15] Let Ψbe a belief state and − a revision function on Ψthat satisfies (C1)–(C7). Then − satisfies (CR) If B(Ψ)⊩β and B(Ψ)−α⊯β, then there exists φ^′ such that B(Ψ)⊩φ^′⊩B(Ψ)−α; φ^′⊯α and φ^′∧β⊩α.

Proof of Theorem 1

1) (⇒) Assume (DP1+) holds. Let μ∈ω₁ and μ∈ω₂. Let \(\alpha \equiv \alpha _{\{\omega _{1},\omega _{2}\}}\). Due to α⊩μ, we obtain by (DP1+) that B((Ψ+μ)∗α)≡B(Ψ∗α). Hence, by observation 4 min({ω₁,ω₂}∖ω_⊥,≤_Ψ)∪ω_⊥=min({ω₁,ω₂}∖ω_⊥,≤_Ψ+μ)∪ω_⊥, i.e., that ω₁≤_Ψω₂ if and only if ω₁≤_Ψ+μω₂. (⇐) Assume (DPR1+) holds and let α⊩μ. Condition (DPR1+) implies that ≤_Ψ and ≤_Ψ+μ coincide in ∥μ∥, so they coincide on ∥α∥. Therefore, min((∥α∥∖ω_⊥),≤_Ψ)∪ω_⊥=min((∥α∥∖ω_⊥),≤_Ψ+μ)∪ω_⊥, that is B((Ψ+μ)∗α)≡B(Ψ∗α).

2) The proof is symmetric with the one above.

3) (⇒) Assume (DP3+) holds and let μ∈ω₁ and μ∉ω₂ and ω₁<_Ψω₂. Let \(\alpha \equiv \alpha _{\{\omega _{1},\omega _{2}\}}\). Then ∥B(Ψ∗α)∥=min((∥α∥∖ω_⊥),≤_Ψ)∪ω_⊥={ω₁,ω_⊥}, from which it follows that B(Ψ∗α)⊩μ. By (DP3+) B((Ψ+μ)∗α)⊩μ, from which it follows that ∥(B(Ψ+μ)∗α)∥=min((∥α∥∖ω_⊥),≤_Ψ+μ)∪ω_⊥⊆∥μ∥, hence ∥B((Ψ+μ)∗α)∥={ω₁,ω_⊥}, from which we can conclude that ω₁<_Ψ+μω₂. (⇐) Assume (DPR3+) holds and let B(Ψ∗α)⊩μ. From ∥B(Ψ∗α)∥=min((∥α∥∖ω_⊥),≤_Ψ)∪ω_⊥ it follows that if ω^′∈∥B(Ψ∗α)∥ then α∧μ∈ω^′ and for all ω^″≠ω_⊥ such that α∧¬μ∈ω^″ it follows that ω^′<_Ψω^″. (DPR3+) yields ω^′<_Ψ+μω^″, hence ω^″∉min((∥α∥∖ω_⊥),≤_Ψ+μ), from which it follows that B((Ψ+μ)∗α)⊩μ.

4) (⇒) Assume (DP4+) holds and let μ∈ω₁ and μ∉ω₂ and ω₁≤_Ψω₂. Let \(\alpha \equiv \alpha _{\{\omega _{1},\omega _{2}\}}\). Then ω₁∈min((∥α∥∖ω_⊥),≤_Ψ)∪ω_⊥=∥B(Ψ∗α)∥, from which it follows that B(Ψ∗α)⊯¬μ. By (DP4+) B((Ψ+μ)∗α)⊯¬μ, from which it follows that ∥B((Ψ+μ)∗α)∥=min((∥α∥∖ω_⊥),≤_Ψ+μ)∪ω_⊥∩(∥μ∥∖ω_⊥)≠∅, hence ω₁∈∥B((Ψ+μ)∗α)∥, from which we can conclude that ω₁≤_Ψ+μω₂. (⇐) Assume (DPR4+) holds and let B(Ψ∗α)⊯¬μ. From ∥B(Ψ∗α)∥=min((∥α∥∖ω_⊥),≤_Ψ)∪ω_⊥ it follows that for some ω^′∈min((∥α∥∖ω_⊥),≤_Ψ)∪ω_⊥ it holds that α∈ω^′, ¬μ∉ω^′ and for all ω^″ such that α∧¬μ∈ω^″ it follows that ω^′≤_Ψω^″. (DPR4+) yields ω^′≤_Ψ+μω^″ for all ω^″ such that α∧¬μ∈ω^″, hence ω^′∈min((∥α∥∖ω_⊥),≤_Ψ+μ), from which it follows that B((Ψ+μ)∗α)⊯¬μ.

5. (⇒) Assume (P+) holds and let μ∈ω₁ and μ∉ω₂ and ω₁≤_Ψω₂. Let \(\alpha \equiv \alpha _{\{\omega _{1},\omega _{2}\}}\). Then ω₁∈min((∥α∥∖ω_⊥),≤_Ψ)∪ω_⊥=∥B(Ψ∗α)∥, from which it follows that B(Ψ∗α)⊯¬μ. By (P+) B((Ψ+μ)∗α)⊩μ, from which it follows that ∥B((Ψ+μ)∗α)∥=min((∥α∥∖ω_⊥),≤_Ψ+μ)∪ω_⊥⊆∥μ∥, hence ∥B((Ψ+μ)∗α)∥={ω₁,ω_⊥}, from which we can conclude that ω₁<_Ψ+μω₂. (⇐) Assume (PR+) holds and let B(Ψ∗α)⊯¬μ. From ∥B(Ψ∗α)∥=min((∥α∥∖ω_⊥),≤_Ψ)∪ω_⊥ it follows that for some ω^′∈min((∥α∥∖ω_⊥),≤_Ψ)∪ω_⊥ it holds that α∈ω^′, ¬μ∉ω^′ and for all ω^″ such that α∧¬μ∈ω^″ it follows that ω^′≤_Ψω^″. (P+) yields ω^′<_Ψ+μω^″, hence ω^″∉min((∥α∥∖ω_⊥),≤_Ψ+μ), from which it follows that B((Ψ+μ)∗α)⊩μ. □

1. ω₁<_φω₂ is defined as ω₁≤_φω₂ and ω₂≦̸_φω₁, and ω₁=_φω₂ is defined as ω₁≤_φω₂ and ω₂≤_φω₁.

2. Strictly speaking, impossible world is not a world but only a technical apparatus. We use this denomination since its behavior in the model will be the same as the behavior of the possible worlds. This is further motivated on “4” section

3. The proof of this observation is virtually the same as the proof of Theorem 3.3. in [18] and Theorem 9 in [10].

4. For an overview see [2]

5. For an overview of this kind of functions see [14].

6. The Hamming distance d_H between two interpretations ω₁ and ω₂ is the number of propositional variables on which the two interpretations differ, i.e., \(d_{H}(\omega,\omega ')=|\{a \in {\mathcal {P}} \mid \omega (a) \neq \omega '(a) \}|\). The Hamming distance between an interpretation ω and a set of interpretations X is d_H(ω,X)= minω^′∈Xd_H(ω,ω^′).

AGM:

Alchourrón, Gärdenfors and Makinson

We want to thank the audiences of The Brazilian Logic Meeting (EBL2017), the workshop on Belief Revision, Argumentation, Ontologies, and Norms (BRAON17) and the Brazilian Conference on Intelligent Systems (BRACIS 2017) for their fruitful discussions. We also thank Eduardo Barrio for his comments.

Funding

EF was partially supported by FCT MCTES and NOVA LINCS UID/ CEC/04516/2013, FCT SFRH/BSAB/127790/2016 and FAPESP 2016/13354-3. RW was partially supported by CNPq grant PQ309605/2013-0.

Availability of data and materials

Data sharing not applicable to this article as no datasets were generated or analyzed during the current study.

Authors and Affiliations

1. Universidade da Madeira and NOVA LINCS, Madeira, Portugal

   Eduardo Fermé

2. Department of Computer Science, University of São Paulo, Rua do Matõ, 1010 - Cidade Universitária, São Paulo, 05508-090, Brazil

   Renata Wassermann

Corresponding author

Correspondence to Renata Wassermann.

Competing interests

The authors declare that they have no competing interests.

Publisher’s Note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

Authors’ contribution’s

Both authors have discussed all the topics that appear in the paper and have equally contributed for the results presented. All authors read and approved the final manuscript.

Authors’ information

The work described here was conceived during EF’s visit to the University of São Paulo.

Open Access This article is distributed under the terms of the Creative Commons Attribution 4.0 International License (http://creativecommons.org/licenses/by/4.0/), which permits unrestricted use, distribution, and reproduction in any medium, provided you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons license, and indicate if changes were made.

Reprints and permissions