We introduce novel classes of fully rational contraction operators for belief bases. These operators are founded on a plausibility relation on models, called tracks, that allow distinguishing between suitable and unsuitable models. We obtain two main representation theorems: the first one semantically characterizes the class of partial-meet operators, which are related to the rationality postulate of relevance; while the second one semantically characterizes the class of smooth kernel contraction operators, which are related to the postulates of core-retainment and relative closure. For the supplementary postulates (conjunction and intersection), we strengthen such operators by imposing the mirroring condition on the track relations. We consider logics that are both Tarskian and compact.
tion. We call such operators that follow this strategy tracked contraction operators. We show a representation theorem between the basic rationality postulates of belief base contraction and such a novel class of contraction operators. Equivalently, the tracked contraction operators correspond to the semantic counterpart of the partial meet operators. We then impose the mirroring condition [10] upon such tracks, and we show that tracks satisfying mirroring induce belief base contraction 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.
We also characterize semantically the smooth kernel contraction operators for bases. For this, we explore some properties of the track relations which unveil the permissive behaviour of smooth kernel contraction on models. We then relax the tracked contraction operators in order to capture such behaviour.
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, inators, we review the faithful pre-orders of Katsuno and Mendelzon [7] 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 two novel classes of contraction operators and the representation theorem connecting tracks and the basic rationality postulates of contraction. In Section 5, we semantically characterize the smooth kernel contraction operators using the track relations. Finally, in Section 6 we conclude the work and discuss some future works. We sketch the proofs of the most important results. The full proofs are available in the appendix at https://jandsonribeiro.github.io/home/ appendix/NMR_23_appendix.pdf
The power set of a set is denoted by (). We treat a logic as a pair ⟨ℒ, ⟩, where ℒ is a language, and : (ℒ) → (ℒ) is a logical consequence operator that indicates all the formulae that are entailed from a set of formulae in ℒ consequence operator satisfies:
. We limit ourselves to logics whose monotonicity: if ⊆ then () ⊆ (); tulate of contraction as well as the smooth kernel and cluding both basic and supplementary rationality pos- then we say that is a model of . If an interpretation partial meet contraction operators. For semantic oper- then we say that is a counter-model of . The set inclusion: ⊆ (); idempotency: (()) = (); compactness: if
∈ () then there is some finite set ′ ⊆ such that ∈ (′). that = ().
Consequence operators that satisfy the first three conditions above are called Tarskian. Likewise, consequence operators satisfying the compactness property will be called compact. Sometimes we say that the logic itself is Tarskian or compact. 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 ⊆ ℒ
such
As we are interested to define semantic operators, we exploit the semantics of the logics. Given a logic ⟨ℒ, ⟩ and a set of structures ℐ, an interpretation or a model is an element of ℐ that gives meaning to the formulae of ℒ; ℐ is called an interpretation domain of that logic, whereas each subset of ℐ 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 |= ⊆ ℐ × ℒ which interpretations a formula is satisfied. If |= ,
is used to indicate on does not satisfy a formula , denoted by ̸|
= , J
K J
K of all models of is given by , while the set of all counter-models of is given by .
In Tarskian logics, the consequence operator can be semantically defined as: a formula model that satisfies all formulae in
∈ () if every also satisfies [12].
Let ℐ be an interpretation domain of a logic ⟨ℒ, ⟩, and a model in ℐ
. The set of all formulae of ℒ satisfied by is the theory ℎ( ) = {
∈ ℒ | |= }. ℐ | ∀
∈ , |= } Generalising, given a set of models , ℎ() = {
| ∀ ∈ , |= } is the theory of the formulae satisfied by all models in . Moreover, given a set ⊆ ℒ , the set of models that satisfy all formulae in is JK
= { ∈ . For simplicity, given a set of mean that satisfies every formula in
. formulae and a model , we will write |= to
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 of atomic propositional symbols, via the operators of conjunction (∧), disjunction (∨) and classical negation (¬). The models are subsets of , and the satisfaction relation is defined as usual.
A pre-order on a domain is binary relation ⩽: × that satisfies transitivity and reflexivity. The minimal elements of a set ⊆ w.r.t a binary relation ⩽: × is min⩽() = { ∈ | if ⩽ then ⩽ , for all ∈ }. We write < to denote that ⩽ but ̸⩽ . We also write ∼ as a shorthand for ⩽ and ⩽ .
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.
We assume that an agent’s corpus of beliefs is represented as a belief base, which will be denoted by the letter .
The term belief base has been used in the literature with Several rational contraction operators were proposed in two main purposes: (i) as a finite representation of an the literature. The two most influential ones are partial agent’s beliefs [13, 14, 15], and (ii) as a more general meet (Definition 4), and Smooth Kernel (Definition 9). and expressive approach that distinguishes explicit from Partial meet makes use of remainders. implicit beliefs [16, 4]. We follow the latter approach, and therefore a belief base can be infinite. Definition 1. Given a belief base and formula , an
Let be a belief base, a contraction function for -remainder of is a set ⊆ such that: ̸∈ (),
is a function − ̇ : ℒ → (ℒ) that given an unwanted and if ⊂ ⊆ , then ∈ ( ). The set of all
piece of information , outputs a subset of which does -remainders of is denoted by ⊥ .
not entail . A contraction function is subject to the
following basic rationality postulates [
(success): if ̸∈ (∅) then ̸∈ ( − ̇ ); (inclusion): − ̇ ⊆ ; (vacuity): if ̸∈ () then − ̇ = ; (uniformity): if for all ′ ⊆ it holds that ∈
(′) if ∈ (′), then − ̇ = − ̇ ; (core-retainment): if ∈ ∖ ( − ̇ ) then there is a
′ ⊆ s.t ̸∈ (′) but ∈ (′ ∪ { }); (relative closure): ∩ ( − ̇ ) ⊆ − ̇ ;
Each member of ⊥ is called a remainder, and it is a maximal subset of 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 from ⊥ such that, (i) ( ⊥ ) ̸= ∅; and (ii) ( ⊥ ) ⊆ ⊥ , if ⊥ ̸= ∅; and (intersection) − ̇ ∩ − ̇ ⊆ − ̇ ∧ (iii) ( ⊥ ) = {}, if ⊥ = ∅. (relevance): if ∈ ∖ ( − ̇ ) then there is some ′ such that − ̇ ⊆ ′ ⊆ , ̸∈ (′) but ∈ (′ ∪ { }).
A selection function works as an extra-logical mechanism that realises the agent’s epistemic preferences. In the original work of [2], the authors propose to repre
For a discussion on the rationale of these postulates, sent an agent’s preferences as a binary relation ⩽ on see [4]. The postulate of uniformity guarantees that con- all remainders. Precisely, a pair ⩽ means that the traction is not syntax sensitive: if two formulae, say remainder is at least as preferable as . The agent and , are entailed exactly by the same subsets of (we picks the most preferable -remainders w.r.t ⩽. say and are -uniform), then and must present the same contraction result. We call the set of rationality Definition 3. A selection function is relational if there postulates listed above the basic rationality postulates exists some binary relation ⩽ on all remainders such that of contraction. A contraction function that satisfies all ( ⊥ ) = min⩽( ⊥ ), for all ⊥ ̸= ∅. If ⩽ is the basic rationality postulates above will be dubbed a transitive then is called transitive relational. rational contraction function. It is worth highlighting that Remainder sets and selection functions are used to derelevance implies core-retainment. Moreover, in Tarskian ifne a contraction operator called partial meet contraction: logics, relevance also implies relative closure [4].
There are other two postulates, called supplementary
postulates [
tion , the operation − ̇ defined as − ̇ = ⋂︀ ( ⊥ ) is a partial meet contraction function. Theorem 5. [19] A contraction operator is rational if 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 6. [2] On theories, a contraction operator is fully rational if it is a transitive relational partial meet contraction operator.
As Hansson [
Another influential class of rational contraction operations is the class of smooth kernel contraction operations, which are defined on kernels and incision functions:
such that (1) ⊆ ; (2) ∈ (); and (3) if ′ ⊂ then ̸∈ (′).
An -kernel of a belief base is a minimal subset of that does entail . The set of all -kernels of a belief base is denoted by ⊥⊥ . Formulae that do not appear in any -kernel are not responsible for entailing the formula to be contracted, and therefore they should be kept intact. In contrast, only formulae that appear in the kernels should be picked for removal. This choice of removal is realised by an incision function: Definition 8. Let () = {⊥⊥ | ∈ ℒ} be the set of all kernel sets of . An incision function on a belief base is a function : () → (ℒ) such that (1) (⊥⊥ ) ⊆
⋃︀ ⊥⊥ ; (2) if ∈ ⊥⊥ and ̸= ∅ , then ∩ (⊥⊥ ) ̸= ∅.
Intuitively, in order to contract a formula , an agent chooses at least one formula from each -kernel, and only formulae from such kernels. An incision function works as an extra-logical device that realises an agent’s epistemic preferences, and it chooses the least preferable formulae in each -kernel to be removed. A contraction operation can be constructed by removing the formulae picked by an incision function. Contraction operations that follow this recipe are called kernel contractions:
function for , the kernel contraction function − ̇ is defined as: − ̇ = ∖ (⊥⊥ ).
Kernel contractions functions, however, are not strong
enough to satisfy relevance and relative closure. To
capture relative closure, Hansson [
Incision functions that satisfy smoothness are called smooth incision function and the respective kernel contractions are called smooth kernel contraction operations. Intuitively, smoothness states that any removed formula cannot be entailed by the remaining formulae.
The smooth kernel contraction operations are
characterised by the first six rationality postulates:
Theorem 10. [
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 , it sufices to obtain a theory that is a subset of (due to the inclusion postulate) and it is satisifed by some counter-models of . This can be formalised by taking a function : ℒ → (ℐ) that picks, for every non-tautological formula , some counter-models of . For tautological formulae , we make ( ) = ∅, as tautologies have no counter-models. When ̸∈ (), there is nothing to be removed, and should be kept untouched, according to vacuity. Therefore, in this case, we make ( ) = J K ∩ JK, that is, the most plausible counter-models of are those ones that satisfy . 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 11. The contraction function induced by a model choice function is the operator
− ̇ = { ∈ | ( ) ⊆ J K}.
Indeed, the basic rationality postulates of contraction characterise such a class of semantic contraction operators for theories, as long as the underlying logic is Tarskian, compact and the language is closed under classical negation and disjunction[12, 10]1. Examples of such logics include classical propositional logic, first-order logic, a number of temporal logics, and several normalmodal logics such as the systems , and 4.
Theorem 12. A contraction function − ̇ on a theory is rational if it is induced by some model choice function . 1The language of the logic contains the classical boolean operators of negation and disjunction and they are interpreted as usual. For full rationality, there are two main classes of belief
Example 1. Consider the belief base = {, , ∨ the revision operators based on Grove’s spheres[6]. Al- There are only three rational contraction results: orders of Katsuno and Mendelzon (KM, for short) [7] and operators: the revision operators based on faithful pre- , ¬ ∨ }, expressed in classical propositional logics, with = {, }. We want to contract the formula ∧ .
Definition 13.
[7]2 Given a belief base , a pre-order ⩽
Observe that J ∧ K = {2, 3, 4}. Let ⩽ be the though 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. Caridroit et al. [21] have shown a similar translation, for classical propositional logic, where a theory is represented as a single formula. The translation we present below works directly on bases (sets of formulae instead of a single formula). is faithful w.r.t if it satisfies the two following conditions: (1) if , ′ ∈ JK then ̸< ′; (2) if ∈ JK and ′ ̸∈ JK then < ′.
Definition 14.
base , the faithful contraction operator founded on ⩽ is the operation − ̇ ⩽ min⩽ (
J
K contraction operator.
). If ⩽ is total then − ̇ ⩽ such that J − ̇ ⩽
K = JK ∪ is a total faithful
A faithful pre-order works as an epistemic preference relation on models. In order to contract a formula , the agent chooses exactly the most plausible countermodels of . In the current presentation, KM operators 3 = { ∨ }.
1 = {, ∨ , ¬ ∨ }, 2 = {, ∨ }, Not every model choice function, however, induces a rational contraction operator. To see this, note that we have only four models
1 = {, }, 2 = {}, 3 = {}, and 4 = ∅. following faithful pre-order on :
1 ⩽ 4 ⩽ 3 ⩽ 2.
Let be a model choice function such that ( ∧ ) = min⩽ 4 satisfies is
J
K ( ∧ ) = {4}. The only formula of that ¬ ∨ . Thus, − ̇ ∧ = {¬ ∨ possible rational contraction results listed above. }. However, this does not correspond to any of the three
In this section, we provide a novel class of semantic conare suitable only for theories, because, for belief bases, traction operators for belief bases. there is no guarantee that − ̇ ⩽ outputs a subset of
In terms of models, contracting a formula from a , as the inclusion postulate demands. Towards this end, theory consists in picking some counter-models of in order to satisfy the inclusion postulate we need only to rewrite faithful contraction in the spirit of Definition 11: get the greatest subset of satisfied by the minimal and maintaining the formulae in satisfied by all such picked counter-models. While this strategy yield rational contractions for theories (Theorem 12), it fails for counter-models of the formula to be contracted. Indeed, belief bases as Example 1 illustrates. This occurs because within classical propositional logics, the KM operations some counter-models of might satisfy less formulae is a special kind of contraction induced by a model choice than allowed by the relevance postulate. For instance, function as per Definition 11. In classical propositional logics, for theories, the faithful contraction operators on total pre-orders are fully rational: Theorem 15. [7, 21] In classical propositional logics, a a total faithful contraction operator. contraction operator on a theory is fully rational if it is
Observe that the representation theorems above (Theorem 12 and Theorem 15) are established only for theories.
Indeed, as Example 1 below illustrates, both representation theorems break down for bases, which is due to violation of the relevance postulate. 2Originally, KM defines an assignment that maps each formula to a pre-order, and defines such an assignment to be faithful. This assignment has only the purpose to provide general contraction operators. As here we focus on local contraction, we opt to remove this complication and operate directly on the pre-orders. looking back at Example 1, according to relevance the formula ∨ must be kept. Observe that this formula appears in all the three possible rational contraction results. The counter-model 4, however, does not satisfy ∨, which makes it unsuitable for performing a rational contraction, as picking it would remove ∨ . The main hurdle is to properly distinguish between suitable and unsuitable models. To solve this problem, we establish a plausibility relation ⩽ on the models. Intuitively, a pair ⩽ ′ means that the model is at least as plausible as ′. Towards this end, in order to contract a formula , only the most plausible counter-models of
w.r.t ⩽ should be chosen, that is, only models within min⩽(J K).
The question at hand is which properties a pre-order on models should satisfy in order to be an adequate plausibility relation that distinguishes between suitable and unsuitable models. those involving the model 4 which is not among the most plausible ones (the suitable ones). Also, observe that other tracks exist: for instance, augmenting the illustrated track by making 2 and 3 comparable or even 3 and 4 comparable. However, for any of the possible tracks, 4 is never among the suitable ones, as it must be strictly definition. This suggests that tracks can be used as an adequate class of plausibility relations to distinguish between suitable and unsuitable models.
Here, we propose such plausibility relations be defined upon the notion of information preservation. Intuitively, the more information from a model preserves the more plausible it is. The set of all formulae from satisfied by a model is given by the set Pres( | ) = { ∈
. Generalising, given a set of models, Definition 16 below formalises a class of pre-orders based on this notion, which we call tracks.
Definition 16. ⩽ ⊆ ℐ × ℐ such that
and ⩽ ′; and (1) If Pres ( | ) = Pres ( ′ | ) then ′ ⩽ (2) If Pres( | ) ⊂
Pres( ′ | ) then ′ < .
In short, a track relation imposes models that strictly preserve more information to be strictly more plausible (condition 2), while models that preserve the same set of information are equally plausible (condition 1). Thus, in every track for a belief a base , the models of are the most plausible ones, and they are also all equally plausible.
A least track of a knowledge base is a least relation satisfying all conditions of Definition 16. It is easy to see that every belief base has a unique least track. We denote the least track of a belief base as ⩽−. models are: is a track of then min⩽ (ℐ) = JK.
Example 2 (continued from Example 1). The beliefs in = {, , ∨ , ∨ ¬} preserved by each of the four
Pres(1 | ) = Pres(2 | ) = {, ∨ , ¬ ∨ } Pres(3 | ) = {, ∨ }
Pres(4 | ) = {¬ ∨ }. is the only model of , it is strictly more plausible than since they preserve diferent beliefs in reason, 4 and 3 are incomparable. However, 2 is strictly more plausible than 4, as 2 preserves strictly more information than 4. At this point, we can see that a track can distinguish between suitable and unsuitable models. According to this track, both models 2 and 3 are the most plausible counter-models of ∧ . If we choose either 2 or 3 then we get a rational contraction: either 1 = {, ∨ , ¬ ∨ }, or 2 = {, ∨ }. By picking both models we get the last rational contraction 3 = { ∨ }. The only non-rational contractions are
. For the same all other models. Models 2 and 3 are incomparable, track: its least track. ∈ | |= , for all ∈ }. less plausible than 2, due to condition 2 of the track’s inclusion relation on the preservation set of the models (on the right).
As tracks establish an adequate notion of plausibility between models, the most plausible ones to contract a formula are the minimal counter-models of . In classical propositional logics, such minimal models always exist, as there is only a finite number of models.
However, for more expressive logics, such as First Order Logics and several Description Logics [22], there are formulae with an infinite number of (counter-)models.
In the presence of an infinite amount of models, some tracks arrange the models through infinite chains. In general, these infinite chains prevent identifying the most plausible counter-models for some formulae. Thus, we need to constrain ourselves to tracks that do not present such bad behaviour, that is, tracks that are founded: Definition 18.
min⩽(J K) ̸= ∅ for every non-tautological formula .
Relying on founded tracks guarantees that for every non-tautological formula , there is at least one countermodel to be picked to perform such a contraction. In fact, as long as the underlying Tarskian logic satisfies compactness, every belief base presents at least one founded is founded if
We can then define a function that selects among the most plausible models: such that Definition 20.
selection function on ⩽ is a function ⩽ : ℒ → (ℐ) 1. ⩽ ( ) ⊆ min⩽ (J K); 2. ⩽ ( ) ̸= ∅, if is not a tautology; 3. if and are -uniform, ∈ ⩽ ( ), ∼ ′ and ′ ∈ min⩽ (J K) then ′ ∈ ⩽ ( ). Example 4 (continued from Example 2). Let ⩽− be the least track of the belief base = {, , ∨ , ¬ ∨ }.
Observe that min⩽− ( ∧ ) = {2, 3}. Then, we can Recall that ⩽− denotes the least track of . Assume we want the solution 1 for contracting either the formulae or . Thus, a track selection function − can pick only counter-models that satisfy 1, when ⩽contracting such formulae. We have only four models: Example 3. Let = { ∨ , ↔ } be a knowledge base. Observe that the formulae and are -uniform. choose any combination of 2 and 3 to contract ∧ . There are only three possible results to contract either or Let 1, 2 and 3 be tracked selection functions founded on that satisfy relevance, which are ⩽− such that 1( ∧ ) = {2}, 2( ∧ ) = {3} and 3(∧) = {2, 3}. They induce the following tracked 1 = { ∨ }, 2 = { ↔ } and 3 = ∅. contraction operators: − ̇ 1 ¬ ∨ = {, ∨ , ¬ ∨ }, − ̇ 2 ¬ ∨ = {, ∨ }, and − ̇ 3 ¬ ∨ = { ∨ }.
As one can easily check, each one of them is a rational contraction operator.
Theorem 22. Every tracked contraction function is rational.
⩽
Fig. 2 illustrates the least track ⩽− on the base . For clarity, in Fig. 2, we depict within rectangles the formulae from that are satisfied by each model. The countermodels of are 3 and 4, and the only one satisfying 1 is 3. So, we make − () = {3}. As and are -uniform, their contr⩽action must coincide. Ideally, we would make ⩽ () = ⩽ (). However, this is not possible, as 3 is not a counter-model of . In fact, the only counter-models of are 2 and 4. Observe that 2 is the only counter-model of that satisfy 1. Therefore, the track selection function must choose 2, that is, − () = {2}. Not surprisingly, 2 and 3 are equally preferable modulo ⩽−, and according to Condition 3 from the definition of track selection function 2 must be picked for contracting , since 1 was chosen to contract . This condition, as this example illustrates, ensures uniformity.
Proof sketch. Postulates of success, inclusion, vacuity and uniformity are easy to prove. We focus on relevance.
Let ∈ ∖ ( − ̇ ⩽ ). Thus, there is some model ∈ ⩽ ( ) such that ̸|= . As ∈ ⩽ ( ), we have that |= − ̇ ⩽ and ∈ min⩽ (J K). Thus, − ̇ ⩽ ⊆
Pres( | ) ⊆ .
Let us suppose for contradiction that ̸∈ (Pres( | ) ∪ { }). Thus, there is some model ′ ∈ J K such that
′ |= Pres( | ) ∪ { }, which implies Pres ( | ) ∪ { } ⊆ Pres( ′ | ).
As ̸|= , we have that ̸∈ Pres( | ). Therefore, Pres( | ) ⊂ Pres( | ) ∪ { }. This means that Pres( | ) ⊂ Pres( ′ | ) which implies that ′ < . Therefore, ̸∈ min⩽ (J K), which is a contradiction.
Theorem 23. Every rational base contraction function is
Following the same strategy as for theories, a contrac- a tracked contraction function. tion on a belief base is performed by keeping the formulae from the current belief base that are satisfied by all the Since a track establishes a plausibility relation between counter-models selected by a tracking selection function. models, it is natural to expect that a track also works as an epistemic preference relation. Therefore, instead of simply picking some of the most plausible models w.r.t a track, it would be rational to pick all such most plausible models. We will call contraction operators that follow this strategy full tracked contraction: some operations satisfying core-retainment do incorporate models of . This exhibits the permissive and drastic behaviour of smooth kernel contraction for bases. Example 5 illustrates this behaviour. Example 5. Let = {, → , ∨ , }, and suppose Definition 24. Let ⩽ be a founded tracking of a belief that we want to contract ‘’. There are only four possibase . The full tracked selection of ⩽ is the function ⩽ ble solutions satisfying both core-retainment and relative such that ⩽ ( ) = min⩽ (J K). Tracked contraction closure: operators founded on full tracking selection functions are full tracked contraction operators. 1 = {, ∨ , } 2 = { → , }
Full tracked contraction operators do satisfy intersection, due to the transitivity of tracks.
Theorem 25. Every full tracked contraction satisfies intersection.
Although tracks capture intersection, they are not strong enough to capture conjunction. Observe that tracks form a special case of faithful pre-orders (Definition 14).
It would be natural then to simply impose totality upon As Example 5 illustrates, we need to allow selection the tracks in the hope of capturing conjunction. Totality, functions to pick not only counter-models but also modhowever, has been criticised in the literature for being els of the formulae being contracted. However, even for too demanding, as an agent might be indiferent or igno- core-retainment, not all models can be chosen. For inrant on how to grade some of its beliefs [23]. Moreover, stance, although ′ = {} is a model of ‘’, ′ violates works such as [10, 24] have observed that totality is not all the four rational solution for contracting in Examstrong enough to capture conjunction, even for theories, ple 5, as ′ violates . On one hand, we need to relax in more expressive logics. As a solution, Ribeiro et al. the selection functions to pick models of the formulae be[10] has introduced mirroring: ing contracted. On the other hand, we need to constrain mirroring: if ̸⩽ and ̸⩽ but ⩽ the selection function so we do not choose unsuitable then ⩽ . models. The tracks still capture enough information to allow distinguishing between such suitable and unsuitable models. We slightly modify the definition of the tracking selection function to capture this permissive behaviour:
Mirroring is similar to the modular relations introduced at [23] which was based on the modular partial orders of Lehmann and Magidor [25]. Though modular relations are defined as partial orders, we do not impose such restrictions. According to mirroring, if two models are incomparable then they should agree upon their preferences. We will show here that by employing mirroring upon tracks, conjunction is also captured for belief bases.
than its full tracked contraction operator satisfies conjunction.
In this section, we characterise semantically the class of smooth kernel contraction operations. In terms of rationality postulates, we are capturing core-retainment and relative closure. While semantic operators satisfying relevance, as shown in the previous section, select only countermodels of the formula being contracted; 3 = { ∨ , }
4 = {}.
Solutions 1, 2 and 4 satisfy relevance, while 3 does not satisfy relevance but core-retainment. The base 3 can only be obtained selecting the models {, } and {, }.
Observe that the latter model satisfies . Therefore, in order to capture core-retainment, it is necessary to relax the selection functions to choose both models and countermodels of the formulae to be contacted.
Definition 27. A permissive selection function on a founded track ⩽ is a map ⩽ : ℒ → (ℐ) such that (1) ⩽ ( ) = ∅, if is a tautology; (2) ⩽ ( ) ∩ J K ̸= ∅, if is not a tautology; (3) ⩽ ( ) = ⩽ ( ), if and are -uniform; (4) permissiveness: if ∈ ⩽ ( ), then
Pres(min⩽ (J K) | ) ⊆
Pres( | ).
As tautologies cannot be contracted, Condition 1 enforces that no model will be picked for tautologies. Condition 2 relaxes the selection mechanism to choose both models and counter-models, while enforcing that at least one counter-model will be chosen, so the contraction is successful. Condition 3 is related to the uniformity postulate, and states that -uniform formulae present the same choice. Since models are allowed to be picked, the last condition, permissiveness, dictates how permissive 8 :
{ → } 4 :
{ → , } 2 : { → , ∨ , } 1 : 7 :
{, ∨ } 3 : {, ∨ , }
The contraction function is defined analogously to the tracked contractions: Definition 28. Let be a permissive selection function on a track ⩽. The permissive contraction founded on is defined as − ̇ = { ∈ | ( ) ⊆ J K}.
The permissive contraction operators are as rational as smooth kernel contraction operators: Theorem 29. Every permissive contraction function satisifes success, inclusion, vacuity, uniformity, core-retainment and relative closure.
Theorem 30. If − ̇ satisfies success, inclusion, vacuity, uniformity and core-retainment and relative closure, then − ̇ is a permissive contraction.
Our representation result follows from Theorem 29 and Theorem 30 which jointly state that the most basic rationality postulates characterize the class of permissive contraction operations. This result jointly with Theothe selection mechanism can be. While contracting a for- rem 10 implies that smooth kernel contraction operations mula , instead of picking only the best models w.r.t the and permissive contraction correspond to the same class track relation, permissiveness allows any (counter)model of operators: being the latter the semantic counterpart to be chosen, as long as preserves as much infor- of the former. mation as the best counter-models of . For clarity, we will omit the subscript ⩽ and simply write .
Example 6. (continued from Example 5). We have eight models in total: While both syntactic and semantic operators are well known for belief theory contraction (and other forms 1 = {, , } 5 = {, } of belief change), only syntactic operators are known 2 = {, } 6 = {} to be rational on belief bases. In this work, we have introduced new classes of semantic contraction operators 3 = {, } 7 = {} for belief bases: tracked contraction operators, full tracked 4 = {} 8 = ∅. contraction operators, and permissive tracked contraction operators. These operators rely on plausibility relations Fig. 3 illustrates the least track ⩽− for the knowledge base between models, called tracks. . For clarity, in Fig. 3, we depict within rectangles the In order to contract a formula , the (full) tracked formulae from that are satisfied by each model. Observe contraction operators select among the most plausible that the counter-models of are {3, 4, 7, 8}, and counter-models of w.r.t a track relation (the most relismelienc⩽ti−on( fu n)ct=ion{tha3t, pic4ks}ownhl yicha3reorcolou4ryeidelidnsgrreasyp.eAc- the selection mechanisms, allowing to pick models in
J K able ones). The permissive tracked contraction relaxes tively the solutions 1 and 2, while picking both 3 and 4 yields the solution 4. The solution 3, which satisfies core-retainment but fails relevance, can only be obtained by choosing the model 2. Observe that 2 preserves as much as 3 and 4 combined, that is,
Pres(3 | ) ∩ Pres (4 | ) ⊆
Pres (2 | ).
Therefore, according to permissiveness, a selection function can choose any of the models in {2, 3, 4}. Notice that 2 is a model of ‘’, while 3 and 4 are countermodels of ‘’. The models that preserve as much information as 3 and 4 combined are depicted within the dashed lines. stead of only counter-models, as long as some innocuous requirements are satisfied. We have established two important representation theorems: the first one connects tracked contraction operations with relevance and the other basic rationality postulates, while the second one connects the permissive tracked contraction operators with core-retainment and the most basic rationality postulates. Equivalently, the tracked contraction operations semantically characterize the partial meet operators, while the permissive tracked contraction operators characterize semantically the smooth kernel contraction operators. A track unveils an agent’s epistemic preferences: the most plausible models coincide with the most