Towards a Semantic Construction for Belief Base Contraction (A Preliminary Report) Jandson S. Ribeiro∗ University of Hagen, Germany Abstract We introduce a novel class of fully rational contraction operators that work by selecting models, which we call tracked contraction operators. These operators are founded on a plausibility relation on models, called a track, that allows distinguishing between suitable and unsuitable models. We show a representa- tion theorem between tracked contraction operators and the basic rationality postulates of contraction. For the supplementary postulates (conjunction and intersection), we strengthen such operators by im- posing the mirroring condition on the track relations. We consider logics that are both Tarskian and compact. Keywords Belief Change, Belief Contraction, Belief Base, Models 1. Introduction The field of Belief Change [1, 2, 3] studies how an agent should rationally modify its corpus of beliefs in response to incoming pieces of information. The two most important kinds of change are: contraction, which relinquishes undesirable/obsolete information; and revision, which accommodates new information with the caveat of keeping the corpus of beliefs consistent. Each of these kind of changes are governed by sets of rationality postulates, split into basic and supplementary rationality postulates, which prescribe adequate behaviours of change. Such rationality postulates are motivated by the principle of minimal change: in response to a piece of information, say α, an agent should remove only beliefs that either conflict with α (in the case of revision), or that contribute to entail α (in the case of contraction). Several classes of belief change operators were proposed that abide by such rationality postulates, called rational belief change operators (see [3], for a list). These classes of operators can be split in two main kinds: syntactic operators and semantic operators. Operators belonging to the first kind select sentences from the language, while operators of the second kind select models. Examples of syntactic operators are partial meet operators [1] and smooth kernel operators [4], while Grove’s system of spheres [5, 2] and the faifthful pre-orders of Katsuno and Mendelzon [6] are the main frameworks for constructing semantic operators. In the most 8th Workshop on Formal and Cognitive Reasoning, September 19, 2022, Trier, Germany ∗ Corresponding author. " jandson.ribeiro@fernuni-hagen.de (J. S. Ribeiro) ~ https://jandsonribeiro.github.io/home/ (J. S. Ribeiro)  0000-0003-1614-6808 (J. S. Ribeiro) © 2022 Copyright for this paper by its authors. Use permitted under Creative Commons License Attribution 4.0 International (CC BY 4.0). CEUR Workshop Proceedings http://ceur-ws.org ISSN 1613-0073 CEUR Workshop Proceedings (CEUR-WS.org) 4 fundamental case, when an agent’s corpus of beliefs is represented as a logically closed set of sentences, called a theory, all these classes of operators are characterised by the rationality postulates of contraction/revision. Theories, however, are very restrictive, as they do not distinguish between explicit and implicit beliefs. One can achieve this distinction by dropping the logical closure requirement, and simply representing an agent’s corpus of beliefs as a set of sentences, called a belief base [3]. For bases, however, very few belief change operators are capable of satisfying the rationality postulates of belief change. Precisely, only partial meet, a syntactic operator, remains rational for belief bases [3, 4]. As a result, research on belief base change has focused on partial meet operators or other similar syntactic operators [3, 7, 8]. This poses a severe limitation in advancing belief base change, as syntactic operators are highly dependent on the assumptions made about the underlying logic used to represent an agent’s knowledge, as for instance, imposing that the language is closed under classical negation [9]. By devising belief change operators via models, such conditions upon the language of the logics can be easily waived. In this work, we devise two novel classes of semantic operators for belief base contraction. Our approach consists in imposing a pre-order, called a track, upon the models of the logics. A track indicates the most plausible models, which in turn are selected to perform a contraction. We show a representation theorem between the basic rationality postulate of belief base con- traction and such novel class of contraction operators. We then impose the mirroring condition [10] upon such tracks, and we show that tracks satisfying mirroring induce belief base con- traction operators that capture the supplementary postulates of belief contraction. It is worth highlighting that, except for safe contraction [11], the study of the supplementary postulates on belief bases has been neglected. As contraction is a central operation in belief change, our result can be extended to provide semantic operators for other kinds of belief change such as revision. Road map: Section 2 introduces some basic notations and definitions that will be used throughout this work. In Section 3, we briefly review belief contraction, including both basic and supplementary rationality postulates of contraction as well as the partial meet contraction operators. For semantic operators, we review the faithful pre-orders of Katsuno and Mendelzon [6] for revision, and we translate them in terms of belief contraction. We show that such operators, though fully rational for theories, are not rational for belief bases. In Section 4, we introduce our two novel classes of contraction operators and the representation theorem connecting tracks and the basic rationality postulates of contraction. Finally, in Section 5 we conclude the work and discuss some future works. Full proofs of the results can be found in the appendix at https://jandsonribeiro.github.io/home/appendix/FCR_22_appendix.pdf 2. Notation and Technical Background The power set of a set A is denoted by P(A). We treat a logic as a pair hL, Cni, where L is a language, and Cn : P(L) → P(L) is a logical consequence operator that indicates all the formulae that are entailed from a set of formulae in L. We limit ourselves to logics whose consequence operator Cn satisfies: monotonicity: if A ⊆ B then Cn(A) ⊆ Cn(B); 5 inclusion: A ⊆ Cn(A); idempotency: Cn(Cn(A)) = Cn(A); compactness: if ϕ ∈ Cn(A) then there is some finite set A0 ⊆ A such that ϕ ∈ Cn(A0 ). Consequence operators that satisfy the first three conditions above are called Tarskian. Some times we say that the logic itself is Tarskian. Throughout this work, unless otherwise stated, all the presented results regard logics whose consequence operators are Tarskian and satisfy compactness. A theory is a set of formulae X ⊆ L such that X = Cn(X). As we are interested to define semantic operators, we exploit the semantic of the logics. Given a logic hL, Cni and a set of structures I, an interpretation or a model is an element of I that gives meaning to the formulae of L; I is called an interpretation domain of that logic, whereas each subset of I is called an interpretation set. For instance, an interpretation domain for the Propositional Logic is the power set of the propositional symbols of the language. A satisfaction relation |= ⊆ I × L is used to indicate on which interpretations a formula is satisfied. If M |= α, then we say that M is a model of α. If an interpretation M does not satisfy a formula α, denoted by M 6|= α, then we say that M is a counter-model of α. The set of all models of α is given by JαK, while the set of all counter-models of α is given by JαK. In Tarskian logics, the consequence operator can be semantically defined as: a formula ϕ ∈ Cn(X) iff every model that satisfies all formulae in X also satisfies ϕ [12]. Let I be an interpretation domain of a logic hL, Cni, and M a model in I. The set of all formulae of L satisfied by M is the theory T h(M ) = {ϕ ∈ L | M |= ϕ}. Generalising, given a set of models A, T h(A) = {ϕ | ∀M ∈ A, M |= ϕ} is the theory of the formulae satisfied by all models in A. Moreover, given a set X ⊆ L, the set of models that satisfy all formulae in X is JXK = {M ∈ I | ∀ϕ ∈ X, M |= ϕ}. For simplicity, given a set of formulae X and a model M , we will write M |= X to mean that M satisfies every formula in X. Throughout this paper we will provide examples to support the intuition of the proposed contraction operators. Due to its simplicity, we will use classical propositional logics to construct such examples. Observe, however, that our results are not confined to classical propositional logics. As usual, the formulae of classical propositional logics are Boolean formulae constructed from a set AP of atomic propositional symbols, via the operators of conjunction (∧), disjunction (∨) and classical negation (¬). The models are subsets of AP , and the satisfaction relation is defined as usual. A pre-order on a domain D is binary relation ⩽ ⊆ D × D that satisfies transitivity and reflexivity. The minimal elements of a set A ⊆ D w.r.t ⩽ is given by the set min⩽ (A) = {a ∈ A | if b ⩽ a then a ⩽ b, for all b ∈ A}. We write a < b to denote that a ⩽ b but b a. 3. Belief Contraction We assume that an agent’s corpus of beliefs is represented as a belief base, which will be denoted by the letter K. The term belief base has been used in the literature with two main purposes: (i) as a finite representation of an agent’s beliefs [13, 14, 15], and (ii) as a more general and expressive approach that distinguishes explicit from implicit beliefs [16, 3]. We follow the latter approach, and therefore a belief base can be infinite. 6 Let K be a belief base, a contraction function for K is a function −̇ : L → P(L) that given an unwanted piece of information α, outputs a subset of K which does not entail α. A contraction function is subject to the following basic rationality postulates [17, 4]: (success): if α 6∈ Cn(∅) then α 6∈ Cn(K −̇ α); (inclusion): K −̇ α ⊆ K; (vacuity): if α 6∈ Cn(K) then K −̇ α = K; (uniformity): if for all K0 ⊆ K it holds that α ∈ Cn(K0 ) iff β ∈ Cn(K0 ), then K−̇α = K−̇β; (relevance): if β ∈ K \(K −̇ α) then there is some K0 such that K −̇ α ⊆ K0 ⊆ K, α 6∈ Cn(K0 ) but α ∈ Cn(K0 ∪ {β}) For a discussion on the rationale of this postulates, see [3]. We call the set of rationality postulates listed above as the basic rationality postulates of contraction. A contraction function that satisfies all the basic rationality postulates above will be dubbed a rational contraction function. There are other two postulates, called supplementary postulates [1, 3, 18]: (intersection) K −̇ ϕ ∩ K −̇ ψ ⊆ K −̇ ϕ ∧ ψ (conjunction) If ϕ 6∈ Cn(K −̇ ϕ ∧ ψ) then K −̇ (ϕ ∧ ψ) ⊆ K −̇ ϕ It is important to stress that the study of the supplementary postulates has been confined to theories, and very little is known about their behaviours on belief bases. Rational contraction operators that satisfy the supplementary postulates will be dubbed fully rational. 3.1. Partial Meet Contraction Several rational contraction operators were proposed in the literature. One of the most influential ones is partial meet (Definition 3, below), which makes use of remainders. Definition 1. Given a belief base K and formula α, an α-remainder of K is a set X ⊆ K such that: α 6∈ Cn(X), and if X ⊂ Y ⊆ K, then α ∈ Cn(Y ). The set of all α-remainders of K is denoted by K ⊥ α. Each member of K ⊥ α is called a remainder, and it is a maximal subset of K that does not entail α. A partial meet operator works by selecting remainders and intersecting them. As a remainder set might have many remainders, a choice must be made about which ones are the best to perform the contraction. This choice is done via an extra-logical mechanism called a selection function: Definition 2. A selection function γ picks some remainder of K ⊥ α such that, (i) γ(K ⊥ α) 6= ∅, (ii) γ(K ⊥ α) ⊆ K ⊥ α, if K ⊥ α 6= ∅; and (iii) γ(K ⊥ α) = {K}, otherwise. A selection function γ is relational iff there is some binary relation ⩽ on all remainders such that γ(K ⊥ α) = min⩽ (K ⊥ α), for all K ⊥ α 6= ∅. If ⩽ is transitive then γ is called transitive relational. 7 A selection function works as an extra-logical mechanism that realises the agent’s epistemic preferences. In the original work of [1], the authors propose to represent an agent’s preferences as a binary relation ⩽ on all remainders. Precisely, a pair A ⩽ B means that the remainder A is at least as preferable as B. The agent picks the most preferable α-remainders w.r.t ⩽. Remainder sets and selection functions are used to define a contraction operator called partial meet contraction: DefinitionT3. Given a belief base K, and a selection function γ, the operation −̇γ defined as K −̇γ α = γ(K ⊥ ϕ) is a partial meet contraction function. Theorem 4. [19] A contraction operator is rational iff it is a partial meet contraction operator. For theories, the transitive relational partial meet operators are characterised by all the rationality postulates of contraction. Theorem 5. [1] On theories, a contraction operator is fully rational iff it is a transitive relational partial meet contraction operator. As Hansson [18] shows, the transitive relational partial meet operators are not strong enough to satisfy the two supplementary postulates on belief bases. Hansson proposed to strengthen the transitive relations with a property called maximising. However, a representation theorem was not obtained. 3.2. Semantic Contraction Operators We start by explaining how belief contraction works on models when the agent’s corpora of beliefs are represented as theories. After that, we show why such strategies do not work for belief bases. In terms of models, in order to contract a formula α from a theory K, it suffices to obtain a theory that is a subset of K (due to the inclusion postulate) and it is satisfied by some counter- models of α. This can be formalised by taking a function σ : L → P(I) that picks, for every non-tautological formula α, some counter-models of α. For tautological formulae α, we make σ(α) = ∅, as tautologies have no counter-models. Moreover, if two formulae α and β are logically equivalent, then σ(α) = σ(β). This guarantees that the choice function is not syntax sensitive. We say that σ is a model choice function. Definition 6. The contraction function induced by a model choice function σ is the operator K −̇σ α = {ϕ ∈ K | σ(α) |= ϕ}. Indeed, the basic rationality postulates of contraction characterise such class of semantic contraction operators for theories: Theorem 7. [10, 12] In classical propostionl logics, a contraction function −̇ on a theory K is rational iff it is induced by some model choice function σ. For full rationality, there are two main classes of belief operators: the revision operators based on faithful pre-orders of Katsuno and Mendelzon (KM, for short) [6] and the revision operators based on Grove’s spheres[5]. Although both classes of operators were originally framed for belief revision, they can be easily translated to contraction. In the following, we present a translation of KM operators based on faithful pre-orders in terms of contraction: 8 Definition 8. [6]1 Given a belief base K, a pre-order ⩽K is faithful w.r.t K iff it satisfies the two following conditions: (1) if M, M 0 ∈ JKK then M 6