Construction of System of Spheres-based Transitively Relational Partial Meet Multiple Contractions: An Impossibility Result (Extended Abstract)

1 Introduction

In the belief revision literature the partial meet contraction, introduced in the seminal paper [Alchourr´on et al., 1985], constitutes the standard model of belief contraction functions. The main purpose of such framework - which is commonly known as AGM contraction - is modelling the dynamics of the set of beliefs of an agent. More precisely, the AGM model essentially provides a definition for a class of contraction functions that receive a belief set - a logically closed set of sentences - and a sentence, and return a belief set which is a subset of the original one that does not contain the received sentence. A possible worlds semantics for partial meet contractions (i.e. a characterization of those functions in terms of possible worlds) was proposed in [Grove, 1988; Hansson, 1999]. Furthermore, based on such semantics, Grove [Grove, 1988] presented a way of defining a contraction function by means of a system of spheres - the so-called system of spheres-based contractions. In that same paper it was shown that such class of functions coincides with the class of transitively relational partial meet contractions, a special (proper) subclass of partial meet contractions which was also introduced in [Alchourr´on et al., 1985].

A natural generalization of the above mentioned contraction functions is to allow the epistemic input to be a set of sentences rather than a single sentence. In [Fuhrmann and Hansson, 1994], Fuhrmann and Hansson introduced the socalled package contractions which return a new belief set that is a subset of the original one and does not contain any element of a given (possibly infinite) set of sentences. In this paper we study only package contractions by finite sets of sentences, which from now on we shall call multiple contractions. We shall often use the expression singleton contraction to refer to an operation of contraction by a single sentence.

∗This paper is an extended abstract of the article [Reis et al., 2016b]. We thank the Editors-in-Chief of the Artificial Intelligence Journal for granting us permission to reuse (part of) the content of that article.

Multiple contraction is an important type of belief change that has been studied extensively in the literature since the early '90s [Nieder´ee, 1991; Fuhrmann and Hansson, 1994; Zhang and Foo, 2001; Peppas, 2012; Reis and Ferm´e, 2012; Ferm´e and Reis, 2012; 2013; Reis et al., 2016a]. Nowadays its significance has increased even further, partially due to the emergence of intelligent agents (softbots, robots, etc) which typically receive input from more than one source simultaneously (for example, through several sensors). We note that such scenarios are outside the scope of classical belief change operators that can only handle changes by a single input at a time.

The generalization of partial meet singleton contractions was originally presented in [Hansson, 1989; 1991] where the class of partial meet multiple contractions was introduced. Afterwards, in [Reis, 2011; Reis and Ferm´e, 2012] the possible worlds semantics for such functions was provided.

A generalization to the multiple contraction case of Grove's system of spheres-based contractions was presented in [Reis, 2011; Ferm´e and Reis, 2012] and three different axiomatic characterizations for those multiple contractions were presented in [Ferm´e and Reis, 2013; Reis et al., 2016a]. However, in none of those references it was analysed if the class of multiple contractions there considered coincides or not with the class of transitively relational partial meet multiple contractions. In this paper we will show that this does not hold. In fact we will prove, more generally, that it is not possible to construct all the transitively relational partial meet multiple contractions by means of a system of spheres-based method. After that we will present two system of spheres-based definitions of multiple contractions that generate only, however not all, transitively relational partial meet multiple contractions.

1.1 Basic Notations and Conventions

We will assume a language L that is built from a finite set of propositional symbols and the Boolean connectives

¬, ∧, ∨,→ and ↔. We shall make use of a consequence operation Cn that takes sets of sentences to sets of sentences and which satisfies inclusion, monotony, iteration, supraclassicality, compactness and deduction. We will sometimes use Cn(α) for Cn({α}). The letters α, αi, β, . . . (except for γ) will be used to denote sentences. A,Ai,B, . . . shall denote subsets of sentences of L. K is reserved to represent a set of sentences that is closed under logical consequence (i.e. K = Cn(K)) - such a set is called a belief set or theory. We shall denote the set of all consistent complete theories (i.e. maximal consistent subsets) of L by ML. We will use the expression possible world (or just world) to designate an element of ML. Given a possible world W, we shall denote by ∧ W the conjunction of all literal in W. M,Ni,W, . . ., (except for L and P), shall be used to denote subsets of ML. Such sets are called propositions. Given a set of sentences R, the set consisting of all the possible worlds that contain R is denoted by ‖R‖. The elements of ‖R‖ are the R-worlds. ‖ϕ‖ is an abbreviation of ‖{ϕ}‖ and the elements of ‖ϕ‖ are the ϕ-worlds. To any set of possible worlds V we associate a belief set Th(V) given by Th(V) = ⋂ V - under the convention that ⋂ ∅ = L.

2 Background

In this section we recall the main definitions and results which we shall need in the remaining of the paper.

2.1 Singleton Contraction

In what follows we recall two of the most well known models of singleton contraction (i.e. contraction of a belief set K by a single sentence α).

Partial Meet Contractions

A Partial Meet Contraction function [Alchourr ´on and Makinson, 1982; Alchourr´on et al., 1985] is built upon a selection from the maximal subsets of K that do not imply the sentence to be contracted.

Given a belief set K and a set of sentences B, the remainder set of K by B, denoted by K⊥B, is the set of maximal subsets of K that do not imply any element of B - which are called remainders (of K, by B) ([Alchourr´on and Makinson, 1981]). For any sentence α, K⊥α is an abbreviation of K⊥{α} and is called the remainder set of K by α.

A selection function for K is a function γ such that for all sentences α: if K⊥α ̸= ∅ then ∅ ̸= γ(K⊥α) ⊆ K⊥α, and if K⊥α = ∅, then γ(K⊥α) = {K}.

An operation - is a partial meet contraction on K if and only if there is a selection function γ for K such that for all sentences α: K - α = ⋂ γ(K⊥α).

If there is a transitive relation ⊑ over ⋃ε∈L K⊥ε such that, for all α ∈ L \ Cn(∅), γ(K⊥α) = {B ∈ K⊥α : B′ ⊑ B for all B′ ∈ K⊥α}, then - is a transitively relational partial meet contraction.

System of Spheres-based Contractions

Now we recall the definitions of a system of spheres and of the system of spheres-based contractions presented in [Grove, 1988].

Given a set of possible worlds X. A system of spheres (abrev. S.S.) centred on X is a set S of subsets of ML that is totally ordered with respect to set inclusion, has X as its minimum andML as its maximum, and is such that for every consistent sentence ϕ ∈ L, the set formed by the elements of S that intersect ‖ϕ‖ has a minimum.

For any consistent sentence ϕ ∈ L, the smallest element of S intersecting ‖ϕ‖ will be denoted by Sϕ and the set consisting of the ϕ-worlds in Sϕ will be denoted by fS(ϕ), i.e. fS(ϕ) = ‖ϕ‖ ∩ Sϕ.

Given a belief set K and a system of spheres S centred on ‖K‖, the S-based contraction on K is the contraction operation -S defined, for any α ∈ L, as follows: K-Sα = Th(‖K‖ ∪ fS(¬α)) if α ̸∈ Cn(∅), and K-Sα = K, if α ∈ Cn(∅). An operation - on K is a system of spheresbased contraction on K if and only if there is a system of spheres S centred on ‖K‖, such that, for all sentences α ∈ L, K-α = K-Sα.

To close this subsection we remind that Grove [Grove, 1988] has shown that the class of system of spheres-based contractions coincides with the class of transitively relational partial meet contractions.

Observation 2.1 ([Grove, 1988]) Let K be a belief set and - be a (singleton) contraction function on K. Then - is a system of spheres-based contraction if and only if it is a transitively relational partial meet contraction.

2.2 Multiple Contraction

Below we recall the definition of partial meet multiple contraction as well as its possible worlds semantics.

Partial Meet Multiple Contractions

The partial meet multiple contractions are a generalization of the partial meet contraction functions to the case of contractions by (possibly non-singleton) sets.

A package selection function for K is a function γ such that for all sets of sentences B: if K⊥B ̸= ∅, then ∅ ̸= γ(K⊥B) ⊆ K⊥B, and if K⊥B = ∅ then γ(K⊥B) = {K}.

An operation ÷ is a partial meet multiple contraction (abrev. PMMC) on K if and only if there is some package selection function γ for K, such that for all sets of sentences B: K÷B = ⋂ γ(K⊥B).

If there is a transitive relation ⊑ on the set ⋃B⊆L K⊥B such that, for all sets of sentences B not containing tautologies, γ(K⊥B) = {X ∈ K⊥B : X′ ⊑ X for all X′ ∈ K⊥B}, then ÷ is a transitively relational partial meet multiple contraction (abrev. TRPMMC).

To finish this section we recall the main concepts and results concerning the possible worlds semantics for package remainders, which was presented in [Reis, 2011; Reis and Ferm´e, 2012], and will be useful further ahead.

Given a belief set K and a set of sentences B, we denote by H (〈B ∩ K〉) the set of minimal sets of possible worlds containing (at least) one ¬αi-worlds, for (all) sentences αi ∈ B ∩ K. 1

The following example clarifies this notation.

1 In [Reis, 2011; Reis and Ferm´e, 2012] this set is denoted by WK⊥B .

Example 2.2 Let L be the propositional language that is built from the two propositional symbols p and q and consider the worlds W0 = Cn(p ∧ q), W1 = Cn(p ∧ ¬q), W2 = Cn(¬p ∧ ¬q), and W3 = Cn(¬p ∧ q). Let K be the theory K = W0, consider the sentences α = q, β = p and δ = p ∨ ¬q and set B = {α, β, δ}.

In these circumstances, α, β, δ ∈ K and ‖¬α‖ = {W1, W2}, ‖¬β‖ = {W2, W3} and ‖¬δ‖ = {W3}.

Therefore the set H (〈B∩K〉) is composed by all the subsets of {W1,W2,W3} which contain (at least) one element of each one of the sets ‖¬α‖, ‖¬β‖ and ‖¬δ‖ and whose proper subsets do not fulfil that requirement. Hence, it holds that H (〈B ∩ K〉) = {{W1, W3}, {W2, W3}}.

Now we present the relation between the sets H (〈B∩K〉) and K⊥B.

Observation 2.3 ([Reis, 2011; Reis and Ferm´e, 2012]) Let K be a belief set and B be a finite set of sentences. Then X ∈ K⊥B if and only if there is some W ∈ H (〈B ∩ K〉) such that X = T h(‖K‖ ∪ W).

3 The Impossibility of Constructing (all the) TRPMMCs by Means of Systems of Spheres

At this point, having in mind the interrelation between transitively relational partial meet (singleton) contractions and system of spheres-based (singleton) contractions recalled in Observation 2.1, the following question arises naturally:

- Is there a system of spheres-based definition of multiple contractions which generates all, and only, transitively relational partial meet multiple contractions?

In this section we will show that the answer to this question is negative.

We start by remarking that in [Reis, 2011; Ferm´e and Reis, 2012] the class of system of spheres-based multiple contractions 2 (which can be seen as a generalization to the case of multiple contraction of Grove's system of spheres-based contractions) was introduced and proven to be a subclass of the class of partial meet multiple contractions. However, in those references the interrelation among system of spheres-based multiple contractions and TRPMMCs was not investigated.

The following counterexample shows that not only the construction of system of spheres-based multiple contractions proposed in [Reis, 2011; Ferm´e and Reis, 2012] fails to generate all TRPMMCs but, furthermore, any (other) method for constructing multiple contractions which is based on systems of spheres shall equally fail to fulfil such goal.

Counterexample 3.1 Let L, W0, W1, W2, W3, K, α, β and δ be as stated in Example 2.2. Having in mind Observation 2.3, it follows that

2 In [Reis et al., 2016b] these functions were designated by the (more appropriate) less general denomination spheres filtrationbased multiple contractions.

Now consider the two preorders ⊑ and ⊑′ on ⋃B⊆L K⊥B - the set of all remainders of K- defined as follows: 3

Let ÷ be the TRPMMC based on ⊑ and ÷′ be the TRPMMC based on ⊑′ . Then:

Now, assume there is a method for constructing all the TRPMMCs by means of systems of spheres and let K⊖S A denote the result of contracting a belief set K by (a set of sentences) A by means of a system of spheres S (centred on ‖K‖) applying such method. Assume additionally that this method generalizes Grove's system of spheres-based construction of (singleton) contraction functions in the sense that, for any sentence ε of L, K⊖S {ε} = K-Sε, where -S is the S-based (singleton) contraction on K.

Then, since ÷ and ÷′ are TRPMMCs, there exist systems of spheres S and S′ (centred on ‖K‖ = {W0}) such that, for any set of sentences A, K÷A = K⊖S A and K÷′ A = K⊖S′ A. Therefore, in particular, it holds that, for any sentence ε of L, K÷{ε} = K-Sε and K÷′ {ε} = K-S′ ε, where -S is the Sbased contraction on K and -S′ is the S′ -based contraction on K.

Having in mind the definitions of -S and -S′ , it follows from (1) and (3) that S∧ W1 ⊂ S∧ W2 and S′∧ W1 ⊂ S′∧ W2 . Similarly, from (2) and (4) it follows that S∧ W2 ⊂ S∧ W3 and S′∧ W2 ⊂ S′∧ W3 . Hence, S = S′ =

= {{W0}, {W0, W1}, {W0, W1, W2}, {W0, W1, W2, W3}}. Then for any set of sentences A, K÷A = K⊖SA = K⊖S′ A = K÷′ A. However, this contradicts (5) and (6).

The idea that underlies Counterexample 3.1 can be generalized in order to show that for any belief set K there is not a system of spheres-based method for constructing multiple contractions that generates all the TRPMMCs (on K). More precisely, having in mind the main arguments used in that counterexample, we can conclude that to prove that no construction of a multiple contraction which is based on a system of spheres can cover the entire spectrum of TRPMMCs it is enough to show that there are more transitive binary relations

3 In these definitions of ⊑ and ⊑′ , as usual, ⊏ and ⊏′ denote the strict part of ⊑ and ⊑′ , respectively. Notice that the binary relation ⊑′ results from replacing in the binary relation ⊑ the pair (Th({W0,W1,W3}), Th({W0,W2,W3})) by its symmetric (T h({W0, W2, W3}), T h({W0, W1, W3})).

⊑ on remainders than there are systems of spheres, and moreover, that each such relation ⊑ induces a different multiple contraction. These facts are formally stated in the following results (for which proofs have been presented in [Reis et al., 2016b]).

Theorem 3.2 Let KR be the set of all remainders of K not including K (i.e. KR = (⋃B⊆L K⊥B) \ K). Let K be a theory such that ML \ ‖K‖ contains at least two worlds. Then there are more preorders in KR, than there are systems of spheres centred on ‖K‖.

Theorem 3.3 Let K be a theory and ⊑, ⊑′ be two preorders on the remainders of K such that ⊑ and ⊑′ disagree on their projection on KR. Then the transitively relational partial meet multiple contractions ÷ and ÷′ induced from ⊑ and ⊑′ respectively, are different.

The following corollary follows immediately from the two previous results:

Corollary 3.4 Let K be a theory such that ML \ ‖K‖ contains at least two worlds. Then there are more transitively relational partial meet multiple contractions on K, than there are systems of spheres centred on ‖K‖.

At this point we must emphasise that it follows from the above corollary that (given a theory K which is such that ML \ ‖K‖ contains at least two worlds) independently of how we define it, any class of multiple contractions (on K) defined by means of system of spheres does not subsume the class of transitively relational partial meet multiple contractions (on K).

4 TwoMethods for Constructing (some) TRPMMCs by Means of Systems of Spheres

Now that we have shown that there is not a method for constructing all the TRPMMCs by means of a (single) system of spheres-based method, the following related question arises naturally:

- Is there a system of spheres-based definition of multiple contractions which generates only transitively relational partial meet multiple contractions?

In what follows we show that the answer to this question is affirmative.

We start by presenting, in the two following definitions two ways of constructing multiple contraction functions by means of a system of spheres.

Definition 4.1 Let K be a belief set and S be a system of spheres centred on ‖K‖, the multiple contraction function ÷1S is defined, for any set of sentences B, as follows:

K÷1SB = Th(‖K‖ ∪ (⋃ {V ∈H (〈B ∩K〉) : for all V ′ ∈ H (〈B ∩K〉), V ′ ⊑1S V })), where ⊑1S is the binary relation on 2ML defined by:

V ′ ⊑1S V iff for all W ∈ V there is someW ′ ∈ V ′ such that S∧W ⊆ S∧W ′ .

Definition 4.2 Let K be a belief set and S be a system of spheres centred on ‖K‖, the multiple contraction function ÷2S is defined, for any set of sentences B, as follows: K÷2SB = Th(‖K‖ ∪ (⋃ {V ∈H (〈B ∩K〉) : for all V ′ ∈

H (〈B ∩K〉), V ′ ⊑2S V })), where ⊑2S is the binary relation on 2ML defined by:

V ′ ⊑2S V iff for all W ∈ V there is someW ′ ∈ V ′ such that S∧W ⊆ S∧W ′ and for all R ∈ V ′ there is some S ∈ V such that S∧S ⊆ S∧R.

The following counterexample on the one hand clarifies the two above definitions and, on the other hand, proves that ÷1S and ÷2S are, in general, different functions.

Counterexample 4.3 Let L, W0, W1, W2, W3, K, α and δ be as stated in Example 2.2. Consider the system of spheres (centred on ‖K‖) S = {{W0}, {W0,W1}, {W0,W1,W2,W3}} and set A = {α, δ}.

Since ‖¬α‖ = {W1,W2} and ‖¬δ‖ = {W3}, it holds that H (〈A ∩ K〉) = {V1, V2}, where V1 = {W1,W3} and V2 = {W2,W3}.

In these circumstances, S∧W1 ⊂ S∧W2 = S∧W3 . Therefore, having in mind the definitions of the binary relations ⊑1S and ⊑2S we have that: V2 ⊑1S V1; V1 ⊑1S V2; V2 ⊑2S V1; and V1 ̸⊑2S V2.

Therefore, according to Definitions 4.1 and 4.2 it holds that:

K ÷1S A = T h(‖K‖ ∪ V1 ∪ V2) = T h({W0, W1, W2, W3}).

Thus, we can conclude that K ÷1S A ̸= K ÷2S A.

To close this section we present the following result which asserts that ÷1S and ÷2S are TRPMMCs (for which a proof has been presented in [Reis et al., 2016b]).

Theorem 4.4 Let K be a belief set and S be a system of spheres centred on ‖K‖. Then the multiple contractions ÷1S and ÷2S on K are transitively relational partial meet multiple contractions.

5 Conclusions

The most relevant outcome here reported is the fact that there is no system of spheres-based definition of multiple contraction functions which generates all the transitively relational partial meet multiple contractions. This fact has been thoroughly exposed in Section 3 and constitutes a noteworthy difference among the multiple and the singleton contractions since, in the case of the latter it is a very well-known result that Grove's class of system of spheres-based (singleton) contractions is identical to the class of transitively relational partial meet (singleton) contractions.

Another significant contribution of this paper, is the proposal of two system of spheres-based constructive methods for defining multiple contractions which give rise to two (different) classes of functions that are subsumed by the class of transitively relational partial meet multiple contractions.

Acknowledgements

M.R. was supported by FCT - Fundac¸˜ao para a Ciˆencia e a Tecnologia through project UID/MAT/04674/2013 (CIMA). E.F. was supported by FCT MCTES and NOVA LINCS UID/CEC/04516/2013.