# belief_update_without_compactness_in_nonfinitary_languages__0cef1fc6.pdf

Belief Update without Compactness in Non-finitary Languages

Jandson S. Ribeiro1,2 , Abhaya Nayak1 and Renata Wassermann2

1 Macquarie University, Australia 2 University of S ao Paulo, Brazil {jandson, renata}@ime.usp.br, abhaya.nayak@mq.edu.au

The main paradigms of belief change require the background logic to be Tarskian and finitary. We look at belief update when the underlying logic is not necessarily finitary. We show that in this case the classical construction for KM update does not capture all the rationality postulates for KM belief update. Indeed, this construction, being fully characterised by a subset of the KM update postulates, is weaker. We explore the reason behind this, and subsequently provide an alternative constructive accounts of belief update which is characterised by the full set of KM postulates in this more general framework.

1 Introduction

Belief change studies the dynamics of a body of knowledge in response to a new piece of information. The two most influential paradigms of belief change are the AGM paradigm of belief revision [Alchourr on et al., 1985] and the KM paradigm of belief update [Katsuno and Mendelzon, 1992], the latter formally developing an idea explored in [Winslett, 1988]. Broadly speaking, the former concerns the process of changing beliefs in the context of static worlds, whereas the latter considers knowledge change in dynamic worlds. In both approaches, belief change may be represented as a function f that takes an epistemic state into another one, given a new piece of information. These functions are governed by rationality postulates whose purpose is to prescribe good set of behaviours for belief change. In both these paradigms, the epistemic state of an agent is represented as a formula, or a set of formulae, in a propositional language, and the background logic is assumed to be, among others, Tarskian and compact. Compactness states that any formula entailed by a set of formulae X should be entailed by a finite subset X of X. In this work we explore the KM update with respect to a class of logics that have an infinite number of not logically equivalent formulae but are not necessarily compact. We call such logics (or languages) non-finitary since no assumption is being made as to if the alphabet in question is finite or not.1

1Propositional modal logic K is non-finitary and yet compact,

Efforts to apply AGM paradigm to non-classical logics were studied in [Restall and Slaney, 1995] and [Wassermann, 2011]. In the context of the AGM contraction (a form of AGM belief change in which an agent relinquishes a piece of information) it was shown in [Ribeiro et al., 2013] that it is not possible to define contraction functions satisfying the AGM contraction postulates in intuitionistic logics. The reason for this is that these logics are not closed under classical negation. Recently, complete accounts of AGM contraction for noncompact logics have been provided in [Ribeiro et al., 2018], subsequently extended in [Ribeiro et al., 2019]. We study KM update while dispensing with the compactness requirement, therefore finitaryness. A number of interesting logics, from both perspective of AI and computing science are not compact. Temporal logics, such as CTL and LTL [Gabbay et al., 1994], which are used in planning and formal methods. Work such as [Zhang and Ding, 2008] proposes to use KM update to repair CTL models that do not comply with the temporal requirements in the context of formal specification and verification of systems. One of the limitation of this work is that it considers only knowledge expressed via a single CTL model. The question we have tried to answer is: What happens to the standard KM update constructions when compactness is discarded? Interestingly, as in the case of AGM contraction [Ribeiro et al., 2018], the correspondence between the standard KM constructions and the KM rationality postulates breaks down. The source of this problem turns out to be not compactness itself but the inherent non-finitaryness. Accordingly, instead of only dispensing with compactness, we address the issue of belief update for non-finitary logics. Our main contributions are: (1) a new class of KM update functions that are fully characterised by the KM postulates, in non-finitary logics; (2) we keep the classical KM update functions, and identify a set of rationality postulate that characterise them. In Section 2 we briefly outline the notation employed in this paper, and introduce some useful concepts that we will need later. In Section 3, we briefly review the KM rationality postulates and the classical KM update functions. We also show the consequences that discarding compactness has over

whereas temporal logics like LTL and CTL are neither finitary nor compact.

Proceedings of the Twenty-Eighth International Joint Conference on Artificial Intelligence (IJCAI-19)

these functions. In Section 4, we devise a new class of functions characterised by the set of basic KM postulates. In particular, we extend these constructions to capture the supplementary postulates and provide a fully KM-rational account. Then in Section 5 we show that in non-finitary logics the classical KM update functions become weaker in the sense that they are characterised by a proper subset of the KM postulates. In that same section we consider the issue of total relation in the KM update relational functions, and show how to dispense with them. Finally, we recap the main results obtained and discuss some future directions for our work.

2 Notation and Technical Background We consider a logic as a pair L, Cn , where L is a language and Cn: 2L 2L is a logical consequence operator that maps a set of formulae to the set of all formulae that can be inferred from it. For readability, for any formula ϕ, the set Cn({ϕ}) will often simply be written as Cn(ϕ). We limit ourselves to logics that are Tarskian, that is, logics whose consequence operator satisfies the following three properties:

1. (Monotonicity): if A B then Cn(A) Cn(B); 2. (Idempotence): Cn(A) = Cn(Cn(A)); 3. (Inclusion): A Cn(A);

The KM paradigm was initially proposed for Propositional Logic, whereby the consequence operator Cn satisfies the following properties:

(deduction): ϕ Cn(A {ψ}) iff ψ ϕ Cn(A); (supraclassicality): if ϕ is a logical consequence of A in classical propositional logic, then ϕ Cn(A); (compactness): if ϕ Cn(A) then there is a finite subset A of A such that ϕ Cn(A ).

Given a logic L, Cn and a set of structures I, an interpretation or a model of a formula ϕ (respectively a set of formulae Φ) of L is an element of I that satisfies ϕ (or Φ). We will say that a logic L, Cn is closed under classical negation iff the language L is closed under the negation operator such that, for each formula ϕ L, Cn(ϕ) Cn( ϕ) = Cn( ), and Cn({ϕ, ϕ}) = L. In other words, the negation is interpreted classically. Analogously, a logic is closed under the disjunction if the associated language is closed under such a connective (classically interpreted, that is, if ϕ Cn(X) then ϕ ψ Cn(X), for every ψ L and X L). A pre-order is a binary relation that satisfies reflexivity and transitivity: (reflexivity) X X; (transitivity) if X Y and Y Z then X Z. The maximal elements of a set A with respect to a binary relation is given by max (A) = {x A | y A, x y}. Analogously, the minimal elements are given by Min (A) = {x A | y A, y x}. A belief set, or simply a theory, K is a set of formulae logically closed under a consequence relation Cn, that is, K = Cn(K). Given a belief set K, the collection of all the interpretations that satisfy K is given by [K]. For convenience, we write [ϕ] to denote the interpretations that satisfy the theory Cn(ϕ). Given

a set of models A, Th(A) = {ϕ | M A, M |= ϕ} is the theory of the formulae satisfied by all models in A. A theory K is complete if and only if, for every sentence ϕ, either ϕ K or ϕ K, and we use TL to denote all such complete theories that are consistent. The decomposition of a theory K in terms of its consistent complete theories is given by ω(K) = {K TL | K K }. Conveniently, we simply write ω(ϕ) to refer to ω(Cn(ϕ)). A function that maps each pair of theory and formula (K, ϕ) to another theory K is a belief change function.

3 Belief Update

In the classic KM approach to belief update, epistemic states are represented as a formula from a propositional language. When dealing with non-finitary logics, however, representing epistemic states in this way may be inconvenient, mainly because in these logics not every belief set can be represented via a single formula or a finite set of formulae. For this reason, we will translate the original KM update functions and rationality postulates in terms of epistemic states as belief sets. We start with the Classical Update (CUP) functions2:

CUP : K ϕ = Th [

M [K] Max M ([ϕ] .

Given a theory K and a formula ϕ, a CUP operator behaves as follows. For each model M of K, the operator chooses from the models of ϕ those closest to M. The notion of distance between models is usually given by a pre-order M. A model M1 is closer to M than a model M2, if M2 M M1. These selected models are then assembled, and the theory of these models corresponds to K ϕ. In [Katsuno and Mendelzon, 1992] it is shown that CUP functions are characterised precisely by a set of eight postulates U1 to U8. We translate this postulates in terms of epistemic states as belief sets which correspond respectively to the postulates (K 2) to (K 9) below.

(K 1) K ϕ is a theory. (K 2) ϕ K ϕ. (K 3) If ϕ K, then K ϕ = K. (K 4) K ϕ is consistent, if both K and ϕ are consistent. (K 5) If Cn(ϕ) = Cn(ψ), then K ϕ = K ψ. (K 6) K (ϕ ψ) K ϕ + ψ. (K 7) If ψ K ϕ and ϕ K ψ, then K ϕ = K ψ. (K 8) If K is complete, then K ϕ ψ (K ϕ) (K ψ). (K 9) (K K ) ϕ = (K ϕ) (K ϕ).

As we require an epistemic state to be a belief set, the postulate (K 1) is added here to ensure that every update function goes from a belief set to another one. Discussion of the rationality behind these postulates can be found in [Katsuno and Mendelzon, 1992].

2Originally, a CUP function is defined over minimal elements, here for convenience we will resort to maximal elements, as we will need to deal with infinite chains, and maximal elements make the reasoning task easier.

Proceedings of the Twenty-Eighth International Joint Conference on Artificial Intelligence (IJCAI-19)

. . . nk . . .

Figure 1: A preorder for the function of Example 1.

Theorem 1. A belief change function satisfies the KM update postulates iff it is a CUP function. We stress that this representation between KM postulates and CUP functions was shown for propositional logic. This connection, however, fails for non-finitary logics. For instance, for non-finitary logics CUP functions do not satisfy postulate (K 7), as illustrated in Example 1. Example 1. Let be a CUP function over the pre-order depicted in Figure 1. An edge x y means that x y. Reflexive and transitive edges are omitted in the figure for convenience. Moreover, let K be a complete consistent theory, and ϕ and ψ be two formulae such that [ϕ] = {A, B, n0, n2, . . . }, [ψ] = {A, B, n1, n3, . . . }, and [ϕ ψ] = {A, B}. According to the relation , Max (ϕ) = {B}, Max (ψ) = {B} and Max (ϕ ψ) = {A, B}. Therefore,

K ϕ = Th Max ([ϕ]) = Th({B}) K ψ = Th Max ([ψ]) = Th({B}) K ϕ ψ = Th Max ([ϕ ψ]) = Th({A, B}).

Though is a pre-order, the update function does not satisfies (K 7). The reason for this is that according to (K 7) it is required that K ϕ = K ϕ ψ, however this does not occur in this example. To see this, note that ϕ ψ K ϕ, as B is model of both ϕ and ψ. Clearly, ϕ K ϕ ψ. However, K ϕ = K ϕ ψ which violates (K 7). The reason why the function of Example 1 does not satisfy (K 7) is related to the characteristic of non-finitary logics having an infinite number of models. In this case, a pre-order may induce an infinite chain in which it is not possible to determine a maximal (resp. minimal) element. To see this, let us consider what happens to the function of Example 1 if there were no infinity chain. For this, we can easily slightly change that example to consider a finite subset of elements: n0 to n3 besides A and B. This gives us that [ϕ] = {A, B, n0, n2} and [ψ] = {A, B, n1, n3}. Thus, Max (ϕ) = {B, n2} and Max (ψ) = {B, n3}. As n2 is a model of ϕ but not a model of ψ, we do not have anymore that ϕ ψ K ϕ. Therefore, in this case, (K 7) is trivially satisfied. Example 1 shows us that the connection between the postulates for KM update and CUP functions breaks down in non-finitary logics. It is natural, then, to pose the following question: how can one perform belief update in non-compact logics? Two natural answers are:

1. one can devise a new class of functions characterised by the KM update postulates in non-finitary logics; 2. one can identify which set of postulates follow from CUP functions in non-finitary logics.

We pursue both these paths. We will propose a new class of functions that satisfy all the KM update postulates, and the results we obtain will prove useful to show that CUP functions, for non-finitary logics, are characterised by a proper subset of the KM update postulates.

4 Reconstructing Rational Update Functions In this section, we provide complete new accounts of rational KM update functions. For convenience, we split the KM postulates in two categories: basic postulates which comprise postulates (K 1) to (K 5) and (K 9); and supplementary postulates which consists of postulates (K 6) to (K 8). We will call a belief change function that satisfies the basic KM postulates a belief update function. The main difference between our new construction and the CUP functions relies on the underlying preference relations. Unlike the CUP functions, transitivity is not a requirement, instead we identify a new property called quasi-reflection which fills up the gap between the supplementary postulates in non-finitary logics.

4.1 KM Basic Rationality The functions we will devise here will operate over complete consistent theories rather than models, following the approach in [Ribeiro et al., 2018]. This will help us avoid technical issues. For instance, in modal logics, unlike in Propositional logic, two different models (but not consistent complete theories) may satisfy exactly the same set of formulae. In non-finitary logics, pre-orders are not strong enough to properly indicate which are the best elements to be used in order to update a theory K by a formula ϕ, as illustrated in Example 1. This means we will need another way to define the closeness criterion between consistent complete theories. We will assume that, instead of a pre-order, an agent has an appointee function that judges which complete theories of a formula ϕ are closest to a complete theory K. This appointee function is used to perform the update of K by ϕ. An appointee considers only consistent complete theories. We recall from Section 2 that the set of all complete consistent theories comprises TL. Definition 1. An appointee is a function δ : TL L 2TL that maps each consistent complete theory and formula ϕ to a set of consistent complete theories subject to the following conditions: (D1) δ(S, ϕ) = , if S and ϕ are consistent; (D2) δ(S, ϕ) ω(ϕ); (D3) δ(S, ϕ) = {S}, if ϕ S; (D4) δ(S, ϕ) = δ(S, ψ), if Cn(ϕ) = Cn(ψ). The purpose of an appointee is to select the best complete consistent theories that satisfy a formula ϕ (condition D2). This criterion is given locally, and it depends on the fixed complete theory S as background. An appointee is compelled to choose at least one consistent complete theory that contains ϕ, as long as ϕ is consistent (condition D1). If a formula ϕ belongs to a complete theory S, then there is no need to go after another theory, that is, the best theory for ϕ is S itself (condition D3). Finally, condition (D4) simply determines that an appointee is syntax independent.

Proceedings of the Twenty-Eighth International Joint Conference on Artificial Intelligence (IJCAI-19)

The main purpose of defining an appointee function is that it captures the concept of distance between complete consistent theories in a general way. With an appointee in hand, it will become easier to explore which conditions we need to capture all the KM update postulates. We start by defining a new class of update functions, the splinter functions which are similar in spirit to CUP functions: Definition 2. Given an appointee δ, a splinter is a function δ such that 1. if K and ϕ are consistent, then

\ δ(S, ϕ) ;

2. otherwise, K δ ϕ = Cn( ). We recall from Section 2 that ω(K) corresponds to the set of all complete consistent theories that contain a theory K. To understand how a splinter works, we will first need a property that follows from the converse of postulate (K 4). To see this, first notice that ϕ cannot be inconsistent since it is required to be in K ϕ. On the other hand, if K were inconsistent, then we would have ϕ K, rendering K ϕ inconsistent. So the only options remaining is that both K and ϕ are consistent. Conversely, if either K or ϕ are inconsistent, we get that K ϕ is inconsistent. This case is captured by the second condition of splinter function definition. For the other cases, a theory K is split into its decomposition of complete consistent theories. An appointee then is used to select for each of these consistent theories the best complete theories from ϕ. Thereafter they are all intersected and it results in K ϕ. Observation 1. Let be a belief change function that satisfies (K 1), (K 3) and (K 4). Then, K ϕ = Cn( ) iff either ϕ or K is inconsistent. Example 2. Let K = Cn(p) be a theory such that its decomposition has only two complete consistent theories: K1 and K2. Let an appointee δ be as follows: δ(K1, p) = {Cn( p, q)} and δ(K2, p) = {Cn( p, q)}. Thus,

K δ p = δ K1, p δ K2, p

= Cn( p, q) Cn( p, q) = Cn( p).

A splinter function behaves similar to a CUP function, with the difference of resorting to an appointee instead of preorders to choose elements for the update. It is easy to check that every splinter function satisfies the basic KM postulates. Theorem 2. Every splinter function δ satisfies (K 1) to (K 5) and (K 9). Not surprisingly, splinter functions not only satisfy the basic KM update postulates, but every update function is a splinter function. Another interesting property of update functions is that they are monotonic, that is, if K K then K ϕ K ϕ. Update functions are monotonic due to postulate (K 9). Proposition 1. Every belief change operation that satisfies (K 9) is monotonic.

The last piece of the puzzle towards our representation result requires us to look at splinter functions from another perspective. We begin with a special case: given a complete consistent theory K and a consistent formula ϕ, how does K δ ϕ look like? As K is a complete consistent theory, the only complete theory that contains K is K itself. Therefore, ω(K) = {K}, which gives us a simpler version of splinter:

K ϕ = \ δ(K, ϕ).

Now let us proceed for a more general case. Imagine that K is a consistent theory, but not complete. Let S be one of the complete consistent theories from the decomposition of K, then have that S ϕ = T δ(S, ϕ). Thus, we can easily see that the update of K by ϕ consists in taking each S ϕ, for S ω(K), and intersecting all of them. This leads us to the following observation. Observation 2. Given a splinter δ, a theory K and a formula ϕ, if both K and ϕ are consistent then

S ω(K) S δ ϕ.

Observation 2 will be useful to prove the Theorem 3 below. For this, we will also need the following two lemmas from [Ribeiro et al., 2018]. Lemma 1. [Cn(K K )] = [Cn(K)] [Cn(K )], for all theories K and K . Lemma 2. Cn(K K ) = Th [K] [K ] , for all theories K and K . Theorem 3. Every update function is a splinter. Our first representation result follows from Theorems 2 and 3 which jointly show that splinter functions and the basic KM postulates are equivalent.

4.2 Reviewing the Supplementary Postulates Although splinter functions satisfy the basic KM postulates, they are not strong enough to capture the supplementary postulates. In this section, we introduce a new class of update functions that satisfy the supplementary postulates. The main idea is to make the appointees to resort to binary relations in order to pick the consistent complete theories. An appointee δ will assign, for each consistent complete theory K, a binary relation K. The appointee chooses the maximal elements within ω(ϕ) modulo K. These relations will need to satisfy some requirements in order to yield splinter functions that satisfies the supplementary postulates. The first one is Maximal Cut: for every consistent formula ϕ, ω(ϕ) has a maximal element w.r.t . Maximal Cut3 was introduced in [Ribeiro et al., 2018] and its purpose is to guarantee that for every formula ϕ, as long as it is consistent, the epistemic agent chooses at least one

3In [Ribeiro et al., 2018], maximal cut is defined over the complements of a formula ϕ, since the focus is contraction. Here, we conveniently translate maximal cut in terms of the complete consistent theories of ϕ.

Proceedings of the Twenty-Eighth International Joint Conference on Artificial Intelligence (IJCAI-19)

C = Cn( p, q) D = Cn( p, q)

A = Cn(p, q) B = Cn(p, q)

Figure 2: A contra-headed relation.

consistent complete theory of ϕ. This ensures that ϕ will be successfully incorporated through the update process. A binary relation that satisfies maximal-cut is called a contraheaded relation4. Appointee functions that rely strictly on contra-headed relations will be called relational appointees. Definition 3. An appointee µ is relational iff for every consistent complete theory K, there is a contra-headed relation K such that µ(K, ϕ) = max K(ω(ϕ)), for every consistent formula ϕ. The new update functions we introduce are the royal splinter functions which consist of splinters functions founded on relational appointees. Definition 4. A splinter µ is royal iff its appointee µ is relational.

Example 3. Consider the complete theories depicted in Figure 2 and the respective contra-headed relation represented by solid arrows. Let µ be a relational appointee such that for the theory A it considers the contra-headed . Thus, µ(A, q) = {B, D} which implies that

A µ q = B D = Cn( q).

At this point, we investigate what we gain by restricting ourselves to royal splinters. The first benefit is that the contraheaded relations guarantee satisfaction of postulates (K 6) and (K 8) which is shown on Theorem 4 below. Lemma 3 will be of immediate assistance through this section. Lemma 3. Let δ be a fully KM rational splinter, and K a complete consistent theory, (i) δ(K, ϕ) ω(ψ) δ(K, ϕ ψ)); (ii) δ(K, ϕ) δ(K, ψ) δ(K, ϕ ψ). The conditions (i) and (ii) from Lemma 3 concern properties that follow from fully rational splinters, precisely the appointees of these functions, and are related respectively to postulates (K 6) and (K 8). Theorem 4. Every royal splinter satisfies (K 6) and (K 8). We impose one more restriction over the relations considered by a relational appointee in order to capture (K 7): Quasi-reflection:5 if A B and B A but A C then either (i) B C, or (ii) if C C , then B C .

4This terminology is borrowed from [Ribeiro et al., 2018]. 5This concept may be intuitively motivated by considering what we would call the Principle of Graded Indifference which can be used to represent equi-preference at the strongest level, and at weaker levels it represents ignorance coupled with certain aspects of equi-preference. This is a work in progress.

To explain quasi-reflection, we will consider conditions (i) and (ii) separately. The main intuition behind (i) is that if an agent has no preference between two elements A and B, then all elements preferable to A should be preferred to B and vice versa. The second condition elevates this mimicking process by one step. For instance, consider the relation depicted in Figure 2 by both solid and dashed arrows. In that relation, there is no preference between A and B. Note that A C and C D. However, C is not preferable to B, as condition (i) demands. In this case, instead of forcing B C, condition (ii) pushes B to mimic one of the elements immediately above A, in this case mimic the preferences over C. Thus, it makes B D (depicted as a dashed arrow). It turns out that quasi-reflection is all we need to capture (K 7). A relational appointee that considers only contraheaded relations that satisfy quasi-refection will be called a quasi-reflected appointee. To see how quasi-reflection captures (K 7), we look at a special case of (K 7) over complete consistent theories.

Lemma 4. Let µ be a royal splinter, such that µ is quasireflected. Given a complete consistent theory K, if ϕ K µ ψ and ψ K µ ϕ, then K µ ϕ = K µ ψ.

The tricky part is to show that quasi-reflection not only captures (K 7) in complete theories, but also in every theory. We make use of the monotonicity property of update functions to show, via lemma above, that (K 7) spreads from complete consistent theories to all theories.

Theorem 5. Given a royal splinter µ, if µ is quasi-reflected then µ satisfies (K 7).

We get the following corollary from Theorems 4 and 5.

Corollary 1. A royal splinter whose appointee is quasireflected is fully KM rational.

Corollary 1 provides the first piece of our representation result. The next step is to prove that every fully KM update function is a royal splinter function whose appointee is quasireflected, in short, a royal reflected splinter. We begin by showing that fully KM update functions are royal. From Theorem 2 we have that every KM update function is a splinter, which means that all of them have an appointee. All we need to show now is that appointees from fully KM splinters are relational. This is not a trivial task. We will start with a special case and then extend it to a more general case. This special case regards consistent complete theories. Let K be a complete consistent theory, and δ a splinter fully KM rational. We want to identify a contra-headed relation K, such that δ(K, ϕ) = Max K(ω(ϕ)), for every consistent formula ϕ. For now, we will say that K is the silhouette of δ within K. Let us assign to each formula ϕ a relation ϕ such that the maximal elements of ω(ϕ) modulo ϕ match δ(K, ϕ). We achieve this by making ϕ= {(A, B) ω(ϕ) ω(ϕ) | A δ(K, ϕ) and B δ(K, ϕ)}. Then, we can assemble all ϕ together to reach the general relation K. Although this seems a good idea, the relation K constructed in this way is not strong enough to satisfy quasi-reflection. We adapt triangulation [Ribeiro et al., 2018] for this purpose.

Proceedings of the Twenty-Eighth International Joint Conference on Artificial Intelligence (IJCAI-19)

Definition 5. Given a complete consistent theory K, an appointee δ and two consistent formulae ϕ and ψ, the δ triangulation of ϕ and ψ modulo K is the relation (ϕ, ψ) = {(A, B) ω(ϕ) ω(ϕ) | A ω(ϕ)\(δ(K, ϕ) ω(ψ)) and B δ(K, ψ)}.

The δ-triangulation we employ here is a weaker version of triangulation used in [Ribeiro et al., 2018]. Given a theory K, and a appointee δ, a triangulation connects the complete consistent theories of ϕ that were not chosen by δ to the theories of ψ that were chosen by δ(K, ψ). This makes all non-chosen elements of ϕ immediately less preferable to all elements chosen by ψ. The main difference between the triangulation version we use here from the original one is that we are indifferent about the complete theories that entail both ϕ and ψ. For instance, if a complete theory A entails both ϕ and ψ then A will not participate in the triangulation (ϕ, ψ). Now we go back to our problem of finding the silhouette of a complete consistent theory K within an appointee δ. This can be achieved by combining triangulation and our first naive idea of assembling relations ϕ.

Definition 6. Given a complete theory K and an appointee δ, the projection of δ modulo K is the relation K such that (A, B) K iff for some formulae ϕ and ψ

either (A, B) ϕ or (A, B) (ϕ, ψ).

To construct a relational appointee, we take the collection of all the projections of the consistent complete theories modulo δ. We say that this is the shadow of δ. It turns out that the projection of δ modulo K is also the silhouette of δ within K, when the splinter function δ is fully KM rational.

Proposition 2. Consider a splinter δ, and a consistent complete theory K. If δ is fully KM rational, then the projection of δ modulo K is the silhouette of δ within K.

Consequently appointees of fully KM rational splinters are relational. To see this, notice that from the proposition above δ(K, ϕ) = max (ω(ϕ)), for each consistent complete theory K, when δ is fully KM rational. And hence fully KM rational splinters are indeed royal.

Theorem 6. The appointee of a fully KM rational function δ is relational.

Corollary 2. Fully KM rational functions are royal splinters.

To show that fully KM rational functions are royal reflected splinters, we show that fully KM rational splinters are reflected. For this, we need to show that the appointee of fully rational splinters are quasi-reflected. The triangulation used to construct projection gives us this property in an easy way.

Theorem 7. Let µ be the appointee from a fully KM rational splinter. Given a complete consistent theory K, the projection K of δ modulo K is quasi-reflected.

Therefore, we have that every fully KM rational belief change function is a royal reflected splinter. This together with Corollary 1 constitute the representation result between KM postulates and royal reflected splinters.

Corollary 3. An update function is fully KM rational iff it is a royal reflected splinter.

5 Discussion and Conclusion Relying solely on preorders does not guarantee the success postulate in absence of the maximal-cut condition to guarantee the existence of maximal elements. We will assume a stronger version of the CUP functions: that their preorder are contra-headed. Let us call it CUP+functions. It is easy to see that CUP+are a special case of royal splinters. Thus, Theorem 8. Every CUP+function satisfies (K 1) to (K 6) and (K 8) and (K 9). It turns out that transitivity and reflexivity add no substantial change in the royal functions, and every royal splinter function that satisfies (K 6) and (K 8) is a CUP+function. Notice that CUP+functions constrained to quasi-reflected relations are royal splinters. Besides the three KM supplementary postulates, the following postulate was proposed to be used in place of postulates (K 7) and (K 8): (K 10) if K is complete and ψ K ϕ then K ϕ + ψ K ϕ ψ. Postulate (K 10) is intimately connected with total preorders as shown in [Katsuno and Mendelzon, 1992], which is taken to be a limitation [Lindstr om and Rabinowicz, 1991; Rott, 1992]. We show a new class of royal splinter functions characterised by the postulates (K 1) to (K 6) and (K 9) and (K 10) that do not depend on total preorders. As the basic KM postulates and (K 6) are satisfied by royal splinter functions, we will still maintain the restriction of appointees to be relational. To capture (K 10) we will replace the quasi-reflection by the mirroring condition proposed by [Ribeiro et al., 2018]: (Mirroring) if S1 S2 and S2 S1; then for any S TL, if S1 S then S2 S . It is worth highlighting that the mirroring corresponds to quasi-reflection constrained to its condition (i). Thus, every mirrored relation is a quasi-reflected relation. Theorem 9. Every mirrored royal splinter satisfies (K 10). Theorem 10. Every update function that satisfies (K 6) and (K 10) is a mirrored royal splinter. In this work, we have addressed the issue of KM update in the context of non-finitary logics. We have found both negative and positive results. On the negative side, the CUP functions, characterised by the KM update postulates in Propositional Logic, cannot satisfy all the postulates without being finitary. We showed that, in finitary logics, CUP functions and a slightly stronger version of them (the CUP+) are characterised by a proper subset of the KM rationality postulates. Assuming the KM update postulates as a good guide for belief update, we have devised a new class of update functions, the royal splinter functions, which are (fully) characterised by the KM postulates.

Acknowledgements We thank an anonymous reviewer for suggesting to consider non-finitary logics instead of non-compact logics. The support of the CAPES Foundation (Brazil), Macquarie University (Australia) and the Australian Research Council (DP150104133) is acknowledged.

Proceedings of the Twenty-Eighth International Joint Conference on Artificial Intelligence (IJCAI-19)

References [Alchourr on et al., 1985] Carlos E Alchourr on, Peter G ardenfors, and David Makinson. On the logic of theory change: partial meet contraction and revision functions. The Journal of Symbolic Logic, 50(2):510 530, 1985. [Gabbay et al., 1994] Dov M. Gabbay, Ian Hodkinson, and Mark Reynolds. Temporal Logic (Vol. 1): Mathematical Foundations and Computational Aspects. Oxford University Press, Inc., New York, NY, USA, 1994. [Katsuno and Mendelzon, 1992] Hirofumi Katsuno and Alberto O. Mendelzon. On the difference between updating a knowledge base and revising it. In Peter G ardenfors, editor, Belief revision, pages 183 203. Cambridge University Press, 1992. [Lindstr om and Rabinowicz, 1991] Sten Lindstr om and Wlodzimierz Rabinowicz. Epistemic entrenchment with incomparabilities and relational belief revision. In The logic of theory change, pages 93 126. Springer, 1991. [Restall and Slaney, 1995] Greg Restall and John Slaney. Realistic belief revision. In Proceedings of the Second World Conference on Foundations of Artificial Intelligence (WOCFAI-95), pages 367 378, 1995. [Ribeiro et al., 2013] M arcio M. Ribeiro, Renata Wassermann, Giorgos Flouris, and Grigoris Antoniou. Minimal change: Relevance and recovery revisited. Artificial Intelligence, 201:59 80, 2013. [Ribeiro et al., 2018] Jandson S. Ribeiro, Abhaya Nayak, and Renata Wassermann. Towards belief contraction without compactness. In Principles of Knowledge Representation and Reasoning: Proceedings of the Sixteenth International Conference, KR 2018, pages 287 296, 2018. [Ribeiro et al., 2019] Jandson S. Ribeiro, Abhaya Nayak, and Renata Wassermann. Belief change and nonmonotonic reasoning sans compactness. In the Thirty Third AAAI Conference on Artificial Intelligence, (forthcoming), 2019. [Rott, 1992] Hans Rott. Preferential belief change using generalized epistemic entrenchment. Journal of Logic, Language and Information, 1(1):45 78, 1992. [Wassermann, 2011] Renata Wassermann. On AGM for non-classical logics. Journal of Philosophical Logic, 40(2):271 294, 2011. [Winslett, 1988] Marianne Winslett. Reasoning about action using a possible models approach. In Proceedings of the Seventh AAAI National Conference on Artificial Intelligence, AAAI 88, pages 89 93. AAAI Press, 1988. [Zhang and Ding, 2008] Yan Zhang and Yulin Ding. CTL model update for system modifications. Journal of Artificial Intelligence Research, 31:113 155, 2008.

Proceedings of the Twenty-Eighth International Joint Conference on Artificial Intelligence (IJCAI-19)