Shielded Base Contraction (Extended Abstract)

1 Introduction

The one which is currently considered the standard model in the belief change literature is known as AGM model and has been originally presented in [Alchourr´on et al., 1985]. In that framework, each belief of an agent is represented by a sentence and the belief state of an agent is represented by a logically closed set of (belief-representing) sentences. These sets are called belief sets. Not long after its publication, several variants of that model started to appear in the literature. 1 From among those proposals we highlight (for being the ones that are directly related to the present work): (i) The use of sets of sentences not (necessarily) closed under logical consequence -the so-called belief bases- rather than belief sets to represent the belief states of an agent; (ii) Classes of, so-called, non-prioritized operators, which are operators that do not satisfy the success postulate. One of these classes is the class of shielded contractions, introduced in [Ferm´e and Hansson, 2001]. The outcome of a shielded contraction may still contain the sentence by which the contraction is made (contrary to what is the case regarding the AGMmodel). The motivation for the proposal of this kind of operators was the fact that, as pointed out by Rott [Rott, 1992], the success postulate is not a fully realistic requirement since an agent can have several (non-tautological) beliefs that he/she is not willing, for various reasons, to give up. Shielded contractions are operators that for some inputs behave just as (standard) contractions and for other inputs just do not have any effect at all -in the sense that they simply return (as output) the belief state received as input. In [Ferm´e and Hansson, 2001], a shielded contraction is defined by means of an AGM contraction and a set of sentences R satisfying certain properties, named set of retractable sentences, which models the set of sentences that the agent is willing to give up (if needed). Informally speaking, the shielded contraction is a function that receives a belief set and a sentence and returns: (i) The received belief set (unchanged), if the received sentence is not included in R; (ii) The output produced by the associated AGM contraction (when it receives those two inputs), if the received sentence is in R.

∗This paper is an extended abstract of the article [Garapa et al., 2018]. This work was partially supported by FCT - Fundac¸ ˜ao para a Ciˆencia e a Tecnologia through projects UID/MAT/04674/2019 (CIMA), UID/CEC/04516/2019 (NOVA LINCS) and PTDC/CCICOM/30990/2017.

†Contact Author.

1 For an overview see [Ferm´e and Hansson, 2011] and [Ferm´e and Hansson, 2018].

In the present paper we shall study shielded contractions defined for belief bases (rather than for belief sets). In this paper we consider classes of shielded base contraction induced by several well-known kinds of base contractions and several kinds of sets of retractable sentences (i.e. we consider several different, and non-equivalent, sets of properties for characterizing a set of retractable sentences). We axiomatically characterize all the classes of shielded base contractions considered and study the interrelations among them, namely by investigating if each of those classes is or is not (strictly) contained in each one of the remaining classes considered. The rest of the paper is organized as follows: In Section 2 we introduce the notations and recall the main background concepts that will be needed throughout this article. In Section 3 we present a formal definition of shielded base contraction and introduce some desirable properties that a set of retractable sentences should satisfy. Afterwards, we present axiomatic characterizations for the following classes of shielded base contractions: shielded contractions induced by partial meet contractions, (two classes of) shielded contractions induced by kernel contractions, and shielded contractions induced by basic AGM-generated base contractions. For each one of these four classes, we shall identify five different subclasses -each one associated to a certain list of properties of the set of retractable sentences. In Section 4 we analyse the interrelations among (all) the classes of shielded contractions considered in terms of the relation of (strict) inclusion. In Section 5 we briefly summarize and discuss the main contributions of the paper.

2 Background

2.1 Formal Preliminaries

We will assume a propositional language L that contains the usual truth functional connectives: ¬ (negation), ∧ (conjunction), ∨ (disjunction), → (implication) and ↔ (equivalence). 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(∅). The letters α, β, . . . (except for γ and σ) will be used to denote sentences of L. A,B, . . . shall denote sets of sentences of L. K is reserved to represent a belief set (i.e. K = Cn(K)).

2.2 Basic AGMContractions

Given A ⊆ L, a contraction operator (or function) on A is a function - : L -→ P(L), and, in that context, the image of a sentence α is represented by A - α.

We now recall the basic AGM postulates for contraction and the concept of basic AGM contraction.

Definition 2.1 ([Alchourr´on et al., 1985]) Let K be a belief set. An operator - on K is a basic AGM contraction if and only if it satisfies the following postulates:

Postulates (K - 1)-(K - 6) are named basic AGM postulates for contraction.

2.3 Postulates for Belief Base Contraction

We now present several postulates for belief base contraction. Some of these postulates are a direct adaptation to the belief base context of the namesake postulates proposed for belief sets that we recalled in Subsection 2.2.

(Success) If ̸⊢ α, then A ÷ α ̸⊢ α.

(Inclusion) A ÷ α ⊆ A.

(Failure) If ⊢ α, then A ÷ α = A.

(Extensionality) If ⊢ α ↔ β, then A ÷ α = A ÷ β.

(Relative Closure) A ∩ Cn(A ÷ α) ⊆ A ÷ α.

(Vacuity) If A ̸⊢ α, then A ⊆ A÷α.

(Disjunctive Elimination) If β ∈ A and β /∈ A ÷ α then A ÷ α ̸⊢ α ∨ β.

(Relevance) If β ∈ A and β ̸∈ A÷ α, then there is a set A′

such that A ÷ α ⊆ A′ ⊆ A and A′ ̸⊢ α but A′ ∪ {β} ⊢ α. (Core-retainment) If β ∈ A and β /∈ A ÷ α then there is some set A′ such that A′ ⊆ A and A′ ̸⊢ α but A′ ∪ {β} ⊢ α. (Uniformity) If it holds for all subsets A′ of A that

We now recall the definition of a contraction operator in terms of postulates presented in [Hansson, 1999].

Definition 2.2 ([Hansson, 1999]) An operator ÷ for a set A is an operator of contraction if and only if ÷ satisfies success and inclusion.

2.4 Constructive Models of Base Contraction

In this subsection we recall some explicit definitions of base change functions and their axiomatic characterizations.

Partial Meet Contractions

Partial meet contractions are operators that are based on a selection of maximal subsets of a set that do not imply a given sentence α, the so called remainder sets, whose concept is formalized in the following definition.

Definition 2.3 ([Alchourr´on andMakinson, 1981]) Let A be a belief base and α a sentence. The set A⊥α (A remainder α) is the set of sets such that B ∈ A⊥α if and only if: (i) B ⊆ A; (ii) B ̸⊢ α; (iii) There is no set B′ such that B ⊂ B′ ⊆ A and B′ ̸⊢ α.

Definition 2.4 ([Alchourr´on et al., 1985]) Let A be a belief base. A selection function for A is a function γ such that for all sentences α: (i) If A⊥α is non-empty, then γ(A⊥α) is a non-empty subset of A⊥α; (ii) If A⊥α is empty, then γ(A⊥α) = {A}.

Definition 2.5 ([Alchourr´on et al., 1985; Hansson, 1991])

The partial meet contraction operator on A based on a selection function γ is the operator ÷γ such that for all sentences α: A ÷γ α = ∩γ(A⊥α). An operator ÷ for a set A is a partial meet contraction if and only if there is a selection function γ for A such that A ÷ α = A ÷γ α for all sentences α.

Observation 2.6 ([Hansson, 1991]) Let A be a belief base. An operator ÷ on A is a partial meet contraction if and only if ÷ satisfies success, inclusion, uniformity and relevance.

Kernel Contractions

[Hansson, 1994] introduced Kernel contraction. It is based on a selection among the sentences of a set A that contribute effectively to imply α; and on how to use this selection in contracting by α. Formally:

Definition 2.7 ([Hansson, 1994]) Let A be a set in L and α a sentence. Then A⊥⊥α is the set such that B ∈ A⊥⊥α if and only if: (i) B ⊆ A; (ii) B ⊢ α; (iii) If B′ ⊂ B then B′ ̸⊢ α. A⊥⊥α is called the kernel set of A with respect to α and its elements are the α-kernels of A.

To contract a belief α from a set A one must give up sentences from each α-kernel, otherwise α would continue being implied. The so-called incision functions select the beliefs to be discarded.

Definition 2.8 ([Hansson, 1994]) Let A be a set of sentences. Let A⊥⊥α be the kernel set of A with respect to α. An incision function σ for A is a function such that for all sentences α: (i) σ(A⊥⊥α) ⊆ ⋃(A⊥⊥α); (ii) If ∅ ̸= B ∈ A⊥⊥α, then B ∩ σ(A⊥⊥α) ̸= ∅.

Definition 2.9 ([Hansson, 1994]) Let A be a set of sentences and σ an incision function for A. The kernel contraction ÷σ for A is defined as: A÷σα = A \ σ(A⊥⊥α). An operator ÷ for a set A is a kernel contraction if and only if there is an incision function σ for A such that A ÷ α = A÷σα for all sentences α.

Observation 2.10 ([Hansson, 1994]) Let A be a belief base. An operator ÷ on A is a kernel contraction if and only if ÷ satisfies success, inclusion, uniformity and core-retainment.

Now we recall smooth kernel contractions.

Definition 2.11 ([Hansson, 1994]) An incision function σ for a set A is smooth if and only if it holds for all subsets A′ of A that if A′ ⊢ β and β ∈ σ(A⊥⊥α) then A′ ∩ σ(A⊥⊥α) ̸= ∅. A kernel contraction is smooth if and only if it is based on a smooth incision function.

Observation 2.12 ([Hansson, 1994]) Let A be a belief base. An operator ÷ on A is a smooth kernel contraction if and only if it satisfies success, inclusion, uniformity, core-retainment and relative closure.

Basic AGM-generated Base Contractions

In the following definition we recall the concept of basic AGM-generated base contraction, an operator of base contraction defined from an operator of basic AGM contraction (for belief sets).

Definition 2.13 ([Ferm´e et al., 2008]) Let A be a belief base. An operator ÷ on A is a basic AGM-generated base contraction if and only if there exists some basic AGM contraction - for Cn(A), such that for all α ∈ L: A ÷ α = (Cn(A) - α) ∩ A.

Observation 2.14 ([Ferm´e et al., 2008]) Let A be a belief base. An operator ÷ on A is a basic AGM-generated base contraction if and only if it satisfies success, inclusion, vacuity, extensionality and disjunctive elimination.

3 Shielded Base Contractions

The basic idea of shielded contractions is to define a function in two steps. In the first step, one needs to define which sentences are retractable, i.e., the sentences that an agent is willing to give up when performing a contraction. Afterwards the function should: (i) leave the set of beliefs unchanged when contracting it by an irretractable sentence; (ii) work as a "standard" contraction when contracting by a retractable sentence. The following definition formalizes this concept.

Definition 3.1 Let ÷ be a contraction operator on a belief base A (i.e. an operator that satisfies success and inclusion). Let R be a set of sentences (the associated set of retractable sentences). Then ∼ is the shielded base contraction (SbC) induced by ÷ and R if and only if:

3.1 The Set of Retractable Sentences

We now present some of the properties that may be desirable from a set R of retractable sentences. The first two of the following properties were proposed in [Ferm´e et al., 2003].

Non-retractability Propagation: If α /∈ R, then Cn(α) ∩ R = ∅.

Conjunctive Completeness: If α ∧ β ∈ R, then α ∈ R or β ∈ R.

Retractability of Logical Equivalents: If ⊢ α ↔ β, then α ∈ R if and only if β ∈ R.

Uniform Retractability: If it holds for all subsets A′ of A that α ∈ Cn(A′ ) if and only if β ∈ Cn(A′ ), then α ∈ R if and only if β ∈ R.

Condition (R - ÷): If α ̸∈ R and β ∈ R, then A ÷ β ⊢ α.

3.2 Postulates for Shielded Base Contraction

In [Ferm´e et al., 2003] the postulates proposed in [Ferm´e and Hansson, 2001] for shielded contractions on belief sets were adapted to the belief bases context:

Relative success: A ∼ α = A or α ̸∈ Cn(A ∼ α).

Persistence: If β ∈ Cn(A ∼ β), then β ∈ Cn(A ∼ α).

Success propagation: If A ∼ β ⊢ β and ⊢ β → α, then A ∼ α ⊢ α.

Conjunctive constancy: If A ∼ α = A ∼ β = A, then A ∼ (α ∧ β) = A.

3.3 Representation Theorems

We start this subsection by presenting the definition and a representation theorem for the most general class of shielded base contractions that we will consider -the class of basic shielded contractions. Afterwards we recall representation theorems for other less general classes of shielded contractions.

Definition 3.2 A shielded base contraction ∼ on a belief base A induced by a contraction ÷ and a set R ⊆ L is a basic shielded contraction if and only if ÷ satisfies failure or R satisfies non-retractability of tautology.

Theorem 3.3 Let ∼ be an operator on A. Then ∼ is a basic shielded contraction if and only if ∼ satisfies relative success and inclusion.

Theorem 3.4 Let A be a belief base and ∼ an operator on A. Then: 2

2 The schema presented in this theorem should be read as follows: (1) ∼ is a SbC induced by a partial meet contraction ÷ and a set R that satisfies uniform retractability iff ∼ satisfies relative success, inclusion, uniformity and relevance. This class of operators shall be represented by SPMC. (2) ∼ is a SbC induced by a partial meet contraction ÷ and a set R that satisfies uniform retractability and non-retractability propagation iff ∼ satisfies relative success, inclusion, uniformity, relevance and success propagation. This class of operators shall be represented by SP-SPMC. ...

4 Maps Between Classes of Shielded Base Contraction Functions

The following diagram illustrates the interrelations among classes of shielded base contractions induced by the same type of contraction function, but each one of them with a different type of associated set of retractable sentences. In Figure 1 an arrow between two boxes symbolizes that the class of shielded contractions at the origin of the arrow is a strict subclass of the class of shielded contractions at the end of that arrow.

In Figure 2 we present the interrelations among classes of shielded contractions induced by different kinds of contractions.

5 Conclusion

In this paper we presented axiomatic characterizations for several kinds of shielded base contractions and studied the interrelations among those classes in terms of inclusion. By means of the provided results it is possible to predict the behaviour of any of the functions constructed as indicated in each of the definitions presented. On the other hand, it is also possible to use these results in the converse direction, that is, for certain sets of properties that are desirable from a shielded contraction function, our results allow to identify an explicit construction of a function that will satisfy all the properties included in that set.