# belief_change_and_nonmonotonic_reasoning_sans_compactness__8d9f2df4.pdf

The Thirty-Third AAAI Conference on Artiﬁcial Intelligence (AAAI-19)

Belief Change and Non-Monotonic Reasoning Sans Compactness

Jandson S. Ribeiro Macquarie University, Australia University of S ao Paulo, Brazil jandson.santos-ribeiro-sant@hdr.mq.edu.au jandson@ime.usp.br

Abhaya Nayak Macquarie University, Australia abhaya.nayak@mq.edu.au

Renata Wassermann University of S ao Paulo, Brazil renata@ime.usp.br

Belief change and non-monotonic reasoning are arguably different perspectives on the same phenomenon, namely, jettisoning of currently held beliefs in response to some incompatible evidence. Investigations in this area typically assume, among other things, that the underlying (background) logic is compact, that is, whatever can be inferred from a set of sentences X can be inferred from a ﬁnite subset of X. Recent research in the ﬁeld shows that this compactness assumption can be dispensed without inﬂicting much damage on the AGM paradigm of belief change. In this paper we investigate the impact of such relaxation on non-monotonic logics instead. In particular, we show that, when compactness is not guaranteed, while the bridge from the AGM paradigm of belief change to expectation logics remains unaffected, the return trip from expectation logics to AGM paradigm is no longer guaranteed. We ﬁnally explore the conditions under which such guarantee can be given.

1 Introduction Classical logics are monotonic: accumulation of new information (in form of additional premises) does not invalidate old conclusions. For instance, since from All birds ﬂy and Tweety is a bird we can infer Tweety ﬂies, acquiring another piece of information, Tweety is a penguin is not going to invalidate that inference we will, classically, still be able to infer that Tweety ﬂies. However, commonsense dictates that in light the new piece of information, that Tweety is a penguin, we should no longer be able to infer that Tweety ﬂies since we know that penguins, though birds, cannot ﬂy. Commonsense reasoning is non-monotonic: although some set of premises entails some conclusion x, the inference of x from may not be guaranteed even if . This realisation has led to the development of a number of approaches to non-monotonic logics, including, default logics (Besnard 2013), defeasible logics (Nute 1994) and expectation logics (G ardenfors and Makinson 1994). One may attribute the non-monotonic behaviour of the commonsense inference to our tendency to deactivate some premises in light of some conﬂicting information it is as if the new information, Tweety is a penguin, triggers deactivation of the premise, All birds ﬂy. When viewed from this

Copyright c 2019, Association for the Advancement of Artiﬁcial Intelligence (www.aaai.org). All rights reserved.

angle, non-monotonic reasoning appears to be closely connected to accounts of rational belief change, such as the classic AGM account, (Alchourr on, G ardenfors, and Makinson 1985), further developed in many works such as (G ardenfors 1988; Hansson 1999; Rott 2001). Indeed it has been argued that belief dynamics and non-monotonic reasoning are different perspectives on the same phenomenon (Makinson and G ardenfors 1991): I am licensed to (commonsensically/non-monotonically) infer sentence y from sentence x if it is rational on my part to believe y after accepting evidence x. This idea is concisely captured in the standard notation: BRNM: x | K y if and only if y K x where K represents a contextually ﬁxed background knowledge, | K is the non-monotonic inference operation that employs K in the background, and is a belief revision operation that yields the new belief set K x from the old belief set K in light of evidential input x. Oftentimes the subscript K from the relation | K is dropped for notational convenience when the intention is clear from the context. The connection between belief revision and nonmonotonic reasoning captured by BRNM comes out handy in going back and forth between these two systems. Consider for instance a constraint on belief revision, that revision of a set of beliefs K by evidence x should not license one to believe in something that does not follow from K and x together, that is, Inclusion: K x Cn(K {x}) where the consequence operation Cn represents the background (classical) logic. Assuming Cn satisﬁes Deduction, this constraint on belief revision can be rewritten as: If y K x, then x y K. Now, since a tautology brings in no new information, we can take K to be equivalent to K, which allows us to rewrite Inclusion as: If y K x, then x y K . Since this version of Inclusion is of the same syntactic form as BRNM, we get Weak Conditionalisation: If x | y, then | x y which says that if y is a non-monotonic consequence of x, then the material conditional x y should be a theorem

of that non-monotonic system. Principles of non-monotonic logic can similarly be translated to and viewed as principles of belief revision. The translation process is not always as straightforward as in this example; a rigorous recipe for this translation procedure as well as a comprehensive list of such translations can be found in in the seminal work (Makinson and G ardenfors 1991). This work was later generalised to non-monotonic reasoning based on expectation orderings, ordering over sentences reﬂecting the extent they are expected to hold true (G ardenfors and Makinson 1994). As noted in (Dix and Makinson 1992), non-monotonic reasoning based on expectation orderings is very similar to the classic approach to non-monotonic reasoning based on preference structures, often called the KLM-system, as propounded in (Kraus, Lehmann, and Magidor 1990). The belief revision operation alluded to above is one of three forms of belief change operations dealing with belief dynamics arguably in a static environment (Katsuno and Mendelzon 1992):1

(a) one for adding the new information possibly inviting inconsistency (expansion);

(b) one for removing an existing belief (contraction); and

(c) one for incorporating the new information without courting inconsistency (revision).

The desired behaviour of these operations are captured by corresponding rationality postulates that are motivated by the principle that the change involved should be minimised, and different constructions of such operations are well known. Furthermore, belief revision and belief contraction are inter-deﬁnable via well known identities. It is typical to assume in these approaches that the background logic that drives this process is, among other things, compact, that is, if this background logic allows inference of a sentence x from a set of premises , then it allows the inference of x from a ﬁnite subset of . In a recent work we have shown that this compactness assumption can be relaxed and yet rational belief contraction operations can be constructed given innocuous conditions on the background language and logic (Ribeiro, Nayak, and Wassermann 2018):

Theorem 1. (Ribeiro, Nayak, and Wassermann 2018) AGM (full) rational contraction functions can be deﬁned in every non-compact logic as long as it is Tarskian and closed under classical negation and disjunction.

Given the inter-deﬁnability between contraction and revision via the Levi Identity and the Harper Identity, it is easily shown that the compactness assumption can be similarly relaxed in case of belief revision. Indeed, one can check stepby-step the relevant proofs in (G ardenfors 1988) and verify that compactness plays no special role in them, and hence can be dispensed with without any damage. That many logics such as Temporal Logics (Gabbay, Rodrigues, and Russo 2008) that play important roles in both

1The corresponding operations of contraction and revision in a dynamic environment are respectively known as erasure and update.

Artiﬁcial Intelligence and Computing Science do not satisfy compactness lends practical signiﬁcance to such relaxation. For instance, temporal logics such as Computation Tree Logic and Linear Temporal Logic, though not compact, are widely used in both Computing Science (e.g. Formal speciﬁcation and veriﬁcation of systems) and Artiﬁcial Intelligence (in planning, for instance). Arguably, such extension of belief revision to the realm of non-compact logics will be of particular relevance to research on AI agents dealing with (semi)-automatic repair of formal system speciﬁcations when the desired formal requirements (speciﬁed in temporal logics) are not complied with. Belief revision can be used in this scenario to recommend rational modiﬁcation of a system speciﬁcation so that the required properties are satisﬁed. Some initial efforts towards this end can be found in (Guerra and Wassermann 2010; Ribeiro and Andrade 2015) and in (Guerra, Andrade, and Wassermann 2013). Since non-monotonic reasoning and belief revision are strongly connected, the nature of non-monotonic reasoning is worth enquiring when the background logic of the corresponding belief revision is not assumed to be compact. That is precisely the problem we address in this paper. In particular, we study the connection between the AGM paradigm of belief revision and the non-monotonic logic based on expectation orderings, and show that when compactness is dropped, it is still possible to walk from belief revision to non-monotonic reasoning. However, the walking back from non-monotonic reasoning to belief revision cannot be assured without further appropriate measures, and we identify such measures. In the rest of this section we will brieﬂy outline the notation we employ in this paper and the formal background. We review in the next section, Section 2, the AGM account of belief revision (Alchourr on, G ardenfors, and Makinson 1985) as well as the non-monotonic inference system based on Expectation orderings (G ardenfors and Makinson 1994), and indicate the signiﬁcance of the compactness assumption. This is followed by a demonstration in Section 3 that relaxing the compactness assumption does not affect the transition from belief revision to non-monotonic reasoning. We show in the next section, Section 4, and explain why, the trip back from non-monotonic systems to belief revision cannot be completed in absence of the compactness assumption. The subsequent Section 5 is devoted to identify the required conditions under which the desired connection between the belief revision and non-monotonic reasoning can be established in the absence of compactness and provide the expected representation results. Finally, in section 6, we conclude with a brief discussion and considerations of future work. We sketch proof of selected results in this paper; others will be provided in a planned future publication.

Notation and Technical Preliminaries Given a set A, the power set of A will be denoted as 2A. We use the terms formula and sentence interchangeably. We will use upper case Roman letters (A, B, X, Y ...) to denote sets, and lower case Greek letter (ϕ, ψ, α, β, . . . ) will

be used to denote formulas. We will reserve the upper case letter K for a sepcial kind of sets called belief sets, and the Greek lower case letter γ to denote a kind of function called selection function. The letter Γ is reserved to denote a collection of sets. Propositional symbols will be denoted by lower case Roman letters (p, q, r, ...), while and will be used to denote truth and falsum. The letter M will denote a model. Moreover we will use the symbol for subset, whereas will denote proper subset. 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 formulas to the set of all formulas that can be inferred from it. For readability, for any formula ϕ, the set Cn({ϕ}) will often simply be written as Cn(ϕ). We will often pretend that the consequence operation Cn itself represents a logic when no confusion is imminent. We limit ourselves to logics that are Tarskian, that is, logics whose consequence operator satisﬁes the following three properties:

1. (Monotonicity): A B iff Cn(A) Cn(B);

2. (Idempotence): Cn(A) = Cn(Cn(A));

3. (Inclusion): A Cn(A);

Apart from being Tarskian, the consequence operation is often taken to satisfy some other properties in the AGM belief change literature:

(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 ﬁnite subset A of A such that ϕ Cn(A ).

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).

2 Belief Revision and Non-monotonic Reasoning

Earlier in the introductory section we outlined in an informal way accounts of belief revision and non-monotonic reasoning, and the interconnection between them. We now elaborate it a bit in a more formal setting, and discuss the role that compactness plays in them.

AGM Belief Revision

All the beliefs of an agent as a whole is represented as a set of sentences K, called a belief set (or theory), that is assumed to be closed under logical consequence: K = Cn(K). For notational convenience we take K + ϕ to mean

Cn(K {ϕ}), for any belief set K and sentence ϕ.2 In the AGM paradigm of belief revision, as well as other forms of AGM belief change (Alchourr on, G ardenfors, and Makinson 1985), the background logic Cn is assumed to satisfy a set of properties called AGM assumptions, namely, it is Tarskian, supra-classical, compact, closed under all boolean connectives (conjunction, disjunction and negation), and satisﬁes deduction. Let K be the collection of all belief sets. Then any function f : K L K is a belief change operation. The full set of AGM rationality postulates is listed below.3 For any theory K, sentences ϕ and ψ, and belief revision function :

K1 K ϕ = Cn(K) (Closure) K2 ϕ K ϕ (Success) K3 K ϕ K + ϕ (Inclusion) K4 if ϕ K, then K + ϕ K ϕ (Preservation) K5 K ϕ = Cn( ) iff ϕ Cn( ) (Consistency) K6 if Cn(ϕ) = Cn(ψ), then K ϕ = K ψ (Extensionality) K7 K (ϕ ψ) (K ϕ) + ψ (Conjunctive Inclusion) K8 if ψ K ϕ, then (K ϕ) + ψ K (ϕ ψ) (Conjunctive Preservation).

Postulates (K1) to (K6) are the basic AGM postulates for revision, and the last two constitute the supplementary postulates. Discussion of and rationale behind these postulates can be found in (G ardenfors 1988), among others. We will call any belief change operation that satisﬁes postulates (K1) to (K6) an AGM rational belief revision operation. Any AGM rational belief revision operation that also satisﬁes the supplementary postulates (K7) and (K8) will be said to be fully AGM rational. The postulates (K1) to (K8) prescribe a good set of behaviours for a revision function, but do not tell us where to ﬁnd such a function. There are different available constructions of (fully) AGM-rational belief revision functions. These constructions employ certain extra-logical mechanisms in the form of preference relations over beliefs/sentences reﬂecting how epistemically entrenched each belief is (how hard it is to give up a belief) or over possible worlds captured by Grove s System of Spheres(Grove 1988) reﬂecting their plausibility. Expectation orderings studied in (G ardenfors and Makinson 1994) are generalisations of the epistemic entrenchment relation, and preference structures propounded in the KLM-system (Kraus, Lehmann, and Magidor 1990) are generalisation of such plausibility orderings.

Non-monotonic reasoning Unlike in the AGM approach to belief revision, in the nonmonotonic reasoning system based on expectation order-

2This is actually called the belief expansion operator that is used to add beliefs without consideration of whether or not the result is consistent. 3In (Alchourr on, G ardenfors, and Makinson 1985), the rationality postulates for belief revision effectively incorporated the Harper Identity which deﬁnes contraction in terms of revision as one of the postulates. Here we have followed the presentation in (G ardenfors 1988), which has become the de facto standard in the literature.

ings there are seven basic axioms and two supplementary axioms. This separation into two groups, ﬁrst proposed in (G ardenfors and Makinson 1994), makes the alignment of these axioms with the postulates for AGM belief revision explicit. We will assume that a non-monotonic inference relation, denoted | , builds up upon to an underlying logic Cn. We will assume very little about Cn, except that it is required to be Tarskian. The basic postulates (or axioms) for nonmonotonic inference relation | are:

N1 If ψ Cn(ϕ), then ϕ | ψ (Supraclassicality) N2 If Cn(ϕ) = Cn(ψ) and ϕ | α then ψ | α (Left Logical Equivalence) N3 If ϕ | ψ and α Cn(ψ) then ϕ | α (Right Weakening) N4 If ϕ | ψ and ϕ | α then ϕ | ψ α (And) N5 If ϕ | ψ then | ϕ ψ (Weak Conditionalization) N6 If | ϕ and | ϕ ψ, then ϕ | ψ (Weak Rational Monotony) N7 If ϕ | then Cn(ϕ) = Cn( ) (Consistency Preservation).

For simplicity, we will call any inference relation that satisﬁes the above seven (basic) postulates of non-monotonicity a non-monotonic inference relation. Besides these basic postulates, two supplementary postulates were also introduced for non-monotonic reasoning: N8 If ϕ ψ | φ then ϕ | ψ φ (Conditionalization) N9 If ϕ | ψ and ϕ | φ then ϕ ψ | φ (Rational Monotony). Let us, for the time being, assume that Cn satisﬁes Compactness. Then it is easily veriﬁed that postulates N3 and N4 jointly imply the following closure axiom:

Closure NM If ϕ | ψ for all ψ A, then ϕ | α for all α Cn(A).

named after the closure postulate K1 of belief revision that it corresponds to (G ardenfors and Makinson 1994). On the other hand, postulates N5 through N7 respectively correspond to the AGM revision postulates K3 through K5. Furthermore, postulate N2 corresponds to K6 (extensionality). Similarly, postulates N8 and N9 correspond respectively to the revision postulates K7 and K8. We will see in Section 4 that this nice correspondence between the revision operation and the inference relation | breaks down at many points when the compactness assumption is dropped. Here we give an indication of how compactness can have consequences for non-monotonic reasoning systems. Let us consider Closure NM which follows from axioms N3 and N4 when Cn satisﬁes compactness. However, in absence of compactness, Closure NM no longer follows from N3 and N4. Theorem 2. If the underlying logic Cn is not compact, then N3 and N4 do not imply Closure NM.

Proof Sketch. Assume that Cn is not compact. Also suppose that | is a nonmonotonic inference relation that satisﬁes N3 and N4. Let ϕ be such that ϕ | β for all β A for some (inﬁnite) set of formulae A, α Cn(A), but α Cn(A ) for any ﬁnite subset A of A. Satisfaction of Closure NM would require that ϕ | α. However, N3 and N4 would jointly allow non-monotonic derivation of α only if α Cn(A ) for some ﬁnite subset A of A contradicting our assumption.

3 From * to | without Compactness

We recall from the introductory section the intertranslatability between revision operation * and nonmonotonic inference relation | captured by BRNM:

ψ K ϕ if and only if ϕ | ψ.

This allows us to navigate between a belief revision operator and an inference relation | . For convenience, when an inference relation | is taken to have been obtained from a revision operation *, we say that * induces | . Conversely, when navigating on the opposite direction, we will say that | induces . We will not assume that the background logic Cn is compact. Let us at this point make the following observation, that if we start with a revision operator , obtain the inference | induced by it, and then again obtain the revision operator induced by this inference relation in turn, we will get back the revision operator we started with. Similarly, if we started with an inference operation | and obtain another inference via a revision operation induced by it, we will go back to our original inference operation | . This simple observation will give us much ﬂexibility with writing the proofs, and we will implicitly assume it throughout.

Observation 1. Let be a belief change operator and | an inference relation. Further more, with a bit of notational overloading, let us denote by | ( ) the inference relation induced from , and similarly, by (| ) the belief revision operator induced by | . Then,

(a) (| ( )) = , and (b) | ( (| )) = | .

Proof. Let K be ﬁxed. We sketch the proof of (a) here, and the proof of (b) is analogous. We need to show that

α K ϕ iff α K (| ) ϕ,

( .) Suppose α K ϕ. Thus, ϕ | ( ) α, which implies that α K (| ( ))ϕ. ( .) Suppose α K (| ( )). Then, ϕ | ( ) α which implies that α K ϕ.

First we show that as long as satisﬁes the six basic AGM revision postulates, the induced | relation satisﬁes the seven basic axioms of non-monotonicity (Theorem 3). Towards this end we ﬁrst make the following useful observation which trivially follows from Deduction.

Observation 2. If ϕ K + ψ then ψ ϕ K, for every theory K.

Theorem 3. If a belief change operator is (basic) AGM rational then its induced inference relation | is a nonmonotonic inference relation.

As the basic revision postulates translates to the basic non-monotonic axioms, the next step is to investigate if the supplementary postulates also imply the supplementary nonmonotonic axioms. In Corollary 1 below we show that a fully AGM rational belief revision operator induces a nonmonotonic inference relation that satisﬁes the supplementary axioms of non-monotonicity. Theorem 4 below shows a strong alignment, respectively between the revision postulates K7 and K8, and the axioms of non-monotonicity N8 and N9.

Theorem 4. Let be a belief revision operator that satisﬁes K1, and | be its induced inference relation. Then,

(i) if satisﬁes K7, then | satisﬁes N8; (ii) if satisﬁes K8, then | satisﬁes N9.

Putting Theorems 3 and 4 together tells us that a fully AGM rational belief revision operator induces a nonmonotonic inference relation that satisﬁes the supplementary axioms of non-monotonicity:

Corollary 1. Let be a fully AGM rational revision operation. The non-monotonic inference relation | induced by it satisﬁes the two supplementary axioms of non-monotonicity.

What remains to be shown is that the supplementary axioms N8 and N9 induce belief change operators that satisfy respectively K7 and K8. However, we postpone this discussion to Section 5, since the transition from the basic nonmonotonic inference axioms to the basic AGM postulates proves problematic, as we show in the next section.

4 From | to * without Compactness

We have shown that a rational belief revision function behaves as a non-monotonic inference relation. Moreover, we also saw that the supplementary revision postulates imply the supplementary non-monotonic axioms, where: N8 is obtained from K7, and N9 from K8. In this section, we examine the converse problem, that is, if every non-monotonic inference induces a rational AGM revision operator. As we will see, the basic non-monotonic axioms are too general to capture some of the basic AGM postulates in absence of compactness. We subsequently identify the conditions under which a non-monotonic inference relation behaves in accordance with the belief revision postulates. Let us ﬁrst show that the basic non-monotonic axioms do not correspond to the basic AGM revision postulates. For this purpose we need construct a non-monotonic inference relation | such that the revision function induced by it violates some of the basic AGM postulates. We will conveniently take a revision function which violates one of the AGM postulates (namely, K3), and then we show that the non-monotonic inference relation | induced by it satisﬁes all the basic non-monotonic axioms. In light of Observation 1, this will sufﬁce our purpose. We construct such a belief revision operator in Example 1.

Example 1. Let be a fully AGM rational revision function, and p an arbitrary formula. The belief revision operation is constructed as follows:

K ϕ = (K + ϕ) + p if ϕ p K K ϕ otherwise.

The revision operation from Example 1 behaves in a simple way. It adds both p and a formula ϕ to K, if both ϕ and p are jointly consistent with K. On the other hand, if K is inconsistent with ϕ or p, it resorts to the rational AGM function . It is trivial to show that although it violates postulate K3, the inference relation | induced by it satisﬁes N1 to N7. This example helps us to prove the following interesting result:

Theorem 5. Let | be the inference relation induced from the belief change function . It is not necessary for * to satisfy K1-K6 in order that | satisﬁes all the basic axioms of non-monotonicity.

Which trivially yields the following as a corollary:

Corollary 2. There is a non-monotonic inference relation | whose induced belief change operator violates some AGM revision postulates.

One might wonder that although the basic non-monotonic axioms do not lead to the six basic AGM postulates, perhaps the supplementary axioms of non-monotonicity can play a compensating role. However, the inference relation | induced from the belief change function of Example 1 already satisﬁes these supplementary axioms. This means that even in the presence of the supplementary axioms it is not possible to navigate from a non-monotonic inference relation to the AGM postulates.

Observation 3. The belief change operator used in Example 1 satisﬁes the supplementary AGM revision postulates.

Theorem 6. There is a non-monotonic inference relation that satisﬁes the supplementary non-monotonic axioms, but violate some of the basic AGM revision postulates.

Theorem 6 shows us that even in the presence of the supplementary axioms, it is not possible to establish the desired connection between AGM revision postulates and nonmonotonic inference axioms without the compactness assumption. This naturally leads to the question whether there are conditions under which the revision operation induced by a rational inference relation | is AGM-rational in absence of compactness. This is the issue we examine in the next section.

5 Bridging the gap

We have seen that the basic axioms of non-monotonicity alone are not strong enough to capture all the basic AGM revision postulates. We also saw that resorting to the supplementary axioms does not help in capturing the basic AGM revision postulates either, let alone the supplementary AGM revision postulates. In this section, we will show that it is possible to connect AGM revision and non-monotonic inference. We will also

show what conditions are needed to establish such a connection. Towards this end let us ﬁrst identify the largest set of AGM postulates that are induced by the basic axioms of non-monotonicity. Let us start with the easy ones. Axiom N2 corresponds to K6 (extensionality), and says that if two formulae are logically equivalent modulo Cn, then they entail the same set of formulae. The success postulate K2 is captured by the axiom N1. The following theorem shows that postulate K5 is jointly captured by axioms N7 and N1.

Theorem 7. Let | be an inference relation and its induced belief change operator. Then:

(i) if | satisﬁes N1, then satisﬁes K2 (success); (ii) if | satisﬁes N2, then satisﬁes K6 (extensionality); (iii) if | satisﬁes both N7 and N1 then satisﬁes K5 (consistency).

So far, of the basic AGM postulates, the ones that are missing are K1, K3 and K4. As we will see, the basic axioms of non-monotonicity are not strong enough to capture these three AGM postulates. We start with K1 (the closure). As we discussed in Section 2, when the underlying logic Cn is compact, axioms N3 and N4 trivially imply Closure NM. However, when Cn is not assumed to be compact, N3 and N4 may no longer guarantee Closure NM. Consequently, a non-monotonic inference may fail to induce a belief change operator that satisﬁes K1. Therefore, satisfaction of K1 necessitates the presence of the Closure NM axiom.

Proposition 1. An inference relation | satisﬁes Closure NM if and only if the belief change operator induced by it satisﬁes K1.

One question that immediately arises is: Do we still need N3 and N4 in presence of Closure NM? It turns out that Closure NM implies both N3 and N4.

Proposition 2. Closure NM implies N3 and N4.

Now we analyse the other two missing postulates: K3 and K4. In Section 4, we showed in Example 1 that nonmonotonic inference relations may fail to induce postulate K3. In that example, reasoning from a tautological evidence allowed the inference of new information not previously believed: recall that Cn( ) entailed the propositional symbol p which is clearly not in Cn( ). This means that, the axioms do not forbid a nonmonotonic inference to augment its body of knowledge in the light of a tautology. In other words, if a formula ϕ does not belong to a theory K, it is possible that | ϕ. So, our ﬁrst task is to prevent such inappropriate acquisition of information. Hence we propose the following condition:

(keeper) if | ϕ then ϕ K.

This allows us to capture postulate K3.

Proposition 3. Let | be an inference relation. If it satisﬁes both N5 and the keeper, then the belief change operator induced by it satisﬁes K3.

Proof. Let | be an inference relation that satisﬁes both N5 and keeper. We will show that its induced belief change operator satisﬁes K3, that is, K ϕ K + ϕ. Let α be a formula in K ϕ. It follows then that ϕ | α. Then it follows from N5 that | ϕ α. Thus, from the keeper, we get that ϕ α K. Therefore, α K + ϕ.

Though keeper is strong enough to capture K3, it fails to capture postulate K4 even in the presence of the seven basic axioms of non-monotonicity. To notice that, let us take the Example 2 below.

Example 2. Let be a fully AGM rational revision function. We construct the following belief change operation:

K ϕ = Cn(ϕ) if ϕ K K ϕ otherwise.

Example 2 is similar to Example 1 except that when the input evidence is consistent with the current knowledge, the agent believes the information contained in that evidence alone (and forgoes all the old information). Clearly * so deﬁned violates K4. We will show that induces an inference relation | that satisﬁes all basic non-monotonic inference axioms and the keeper.

Proposition 4. Satisfaction of K4 by a revision operation * is not necessary to induce an inference relation | which satisﬁes all basic axioms of non-monotonicity.

The next step deals with keeper.

Proposition 5. The belief change operation used in Example 2 induces an inference relation | that satisﬁes the keeper.

Proof. Let us suppose that | ϕ, we need to show that ϕ K. As | is induced from , we have that ϕ K . We have two cases to consider K = K or K = Cn( ). For K = K , as satisﬁes all the basic AGM revision postulates, we have from K3 that K K, thus ϕ K. For K = Cn( ) we have that ϕ Cn( ), which implies that ϕ K, as K is a theory.

Example 2 helps to show that adding the keeper is not enough to capture the K4. In that example, the main reason that K4 failed is that we are allowing loss of information. This suggests that we should avoid losing formulae when the input formula is consistent with a theory K. Hence we introduce a further condition:

(rooting) if ϕ K then | K ϕ.

The rooting axiom is the converse of the keeper and enforces that the formulae present in a theory K should remain in the non-monotonic inferences by a tautology. The rooting is the last piece of the puzzle to our ﬁrst side of the representation theorem. The rooting together with the keeper and N6 captures K4.

Proposition 6. If an inference relation | satisﬁes keeper, rooting and N6, then its induced belief change operator satisﬁes K4.

Proof. Let | be an inference relation that satisﬁes keeper, rooting and N6, and its induced belief change operator. We will show that satisﬁes K4. To show this, let us suppose that ϕ K, we need to show that K + ϕ K ϕ. In other words, for every formula α K + ϕ we need to show that α K ϕ. By hypothesis, ϕ K which from the contrapositive of the keeper implies that | ϕ. As α K + ϕ, we have that ϕ α K from Observation 1. Thus, from rooting | ϕ α. Thus we have that both | ϕ and | ϕ α. Thus, from N6 we have that ϕ | α which implies that α K ϕ.

Now we have all the pieces of the puzzle to show the ﬁrst result of the representation theorem, that is, the basic nonmonotonic axioms augmented with the keeper and rooting induces AGM rational revision operators.

Theorem 8. Let | be a non-monotonic inference relation, if it satisﬁes the keeper, rooting and Closure NM then its induced belief revision operator is AGM rational.

Proof. From Propositions 3 and 6 we have that satisﬁes K3 and K4. Moreover, from Theorem 7 we have K2, K5 and K6. Finally, from Proposition 1 we have that Closure NM implies K1. This ﬁnishes the proof.

So far, we were able to show one direction of the representation theorem. However, as we have included two new axioms to the systems, we need to show that rational AGM revision operators induces non-monotonic inferences that satisfy, besides the basic axioms, the keeper, rooting and the Closure NM.

Theorem 9. An AGM rational belief revision operator induces a non-monotonic inference that satisﬁes rooting, keeper and Closure NM.

Proof. Let be an AGM rational operator, that is, it satisﬁes the six basic AGM revision postulates. We have from Theorem 3 that it induces a non-monotonic inference relation | . We will show that it also satisﬁes rooting, keeper and Closure NM. From K3 and K4, we have that

As a formula ϕ K ψ iff ψ | ϕ, we have then from (1) that ϕ K iff | ϕ. This means that | satisﬁes both keeper and rooting. Furthermore, since * satisﬁes K1, it follows from the contrapositive of Proposition 2 that | satisﬁes the Closure NM.

We reached our ﬁrst representation theorem, in the form of Corollary 3 below, which comprises Theorems 8 and 9. This results is due to that adding keeper, rooting and Closure NM axioms to the basic set of non-monotonic inference axioms stablish a bridge between AGM belief revision operators and non-monotonic logics.

Corollary 3. A belief change operator is AGM rational iff its induced inference relation | is a non-monotonic inference relation that satisﬁes Closure NM, keeper and rooting.

Proof. It is straightforward from Theorems 8 and 9.

Capturing Supplementary postulates Our ﬁrst representation result comprises Corollary 3, which says that a non-monotonic inference relations augmented with the keeper and rooting induce an AGM rational belief revision operators, and AGM rational belief revision operators also induce non-monotonic inference relations that satisfy, besides the basic axioms, the keeper and rooting. The next representation theorem concerns the supplementary postulates and the supplementary axioms. We start showing that axioms N8 and N9 induce belief change operators that satisfy K7 and K8 respectively.

Theorem 10. If a non-monotonic inference relation | satisﬁes N8 then the belief change function induced by it satisﬁes K7.

Proof. Given a formula α K ϕ ψ, we need to show that α K ϕ + ψ. As α K ϕ ψ, we have that ϕ ψ | α which from N8 implies that ϕ | ψ α. This means that ψ α K ϕ. Thus, α K ϕ + ψ.

Theorem 11. If an inference relation | satisﬁes both N9 and Closure NM, then its induced belief change operation satisﬁes K8.

Proof. Let us suppose that ψ K ϕ, the we need to show that K ϕ+ψ K ϕ ψ. In other words, given a formula α K ϕ + ψ, we need to show that α K ϕ ψ. From ψ K ϕ, we have that ϕ | ψ. Moreover, as | satisﬁes Closure NM, we have that both K ϕ and K ϕ ψ are theories. Therefore, α (K ϕ) + ψ implies Observation 1 that ψ α K ϕ, which means that ϕ | ψ α. This together with ϕ | ψ implies from N9 that ϕ ψ | ψ α. This means that ψ α K ϕ ψ. Thus, as ψ K ϕ ψ, we have that α K ϕ ψ.

This second representation result, an immediate consequence from Corollary 3, together with Theorems 10 and 11, shows that N8 and N9 translates respectively into K7 and K8, and vice-versa.

Corollary 4. A belief change operator is fully AGM rational iff its induced inference relation | satisﬁes all the basic, and supplementary axioms of non-monotonicity together with keeper and rooting.

We know from Proposition 2 that N3 and N4 are superﬂuous in presence of Closure NM. Therefore, we may assume a shorter set of non-monotonic axioms: N1, N2, N5 to N7 and the keeper, rooting and Closure NM. Hence the Corollary 3 can be stated more simply as:

Corollary 5. A belief change operator is AGM rational iff its induced inference relation | satisﬁes N1, N2, (N5 - N7), keeper, rooting and Closure NM.

6 Conclusion and Future Works In this work we have addressed the connection between AGM revision operators and non-monotonic logics. Unlike the previous works, we no longer assume compactness. We showed that dropping compactness has some immediate consequences on the non-monotonic system. For instance,

Closure NM needs to be assumed as it no longer immediately follows from N3 and N4. Moreover, in presence of Closure NM, N3 and N4 become redundant. Another two consequences is that, though the direction from AGM revision postulates to the non-monotonic system we addressed remains untouched, the converse is not true. We showed that the postulates K3 and K4 are violated in this side of the trip. To solve this problem, we studied which axioms remained as a translation of the AGM postulates, and then we proposed two new axioms, the keeper and rooting, in order to strength the non-monotonic system to be able to reconnect with AGM paradigm. At the end, we were able to show a connection between the enhanced non-monotonic system and the AGM belief postulates: both for the basic postulates as well as the supplementary postulates. One more difference between our work and the classical one is that whereas the study between AGM revision and non-monotonic inference rides on speciﬁc belief revision operators such as partial meet or other constructions, our proofs navigate directly from postulates to axioms and vice-versa without the need to assume any speciﬁc construction. This makes the study more general, as we assume very little about the underlying logics, namely, to be only Tarskian and closed under classical negation and disjunction.

Acknowledgements

The ﬁrst author is supported by a scholarship from the CAPES Foundation within the Brazilian Government s Ministry of Education, as well as a scholarship from Macquarie University under a Cotutelle agreement. This research has also been partially supported by the Australian Research Council (ARC), Discovery Project: DP150104133.

Alchourr on, C. E.; G ardenfors, P.; and Makinson, D. 1985. On the logic of theory change: partial meet contraction and revision functions. The Journal of Symbolic Logic 50(2):510 530. Besnard, P. 2013. An introduction to default logic. Springer Science & Business Media. Dix, J., and Makinson, D. 1992. The relationship between KLM and MAK models for nonmonotonic inference operations. Journal of Logic, Language and Information 1(2):131 140. Gabbay, D. M.; Rodrigues, O.; and Russo, A. 2008. Belief revision in non-classical logics. The Review of Symbolic Logic 1(3):267 304. G ardenfors, P., and Makinson, D. 1994. Nonmonotonic inference based on expectations. Artiﬁcial Intelligence 65(2):197 245. G ardenfors, P. 1988. Knowledge in ﬂux: Modeling the dynamics of epistemic states. The MIT press. Grove, A. 1988. Two modellings for theory change. Journal of Philosophical Logic 17(2):157 170.

Guerra, P. T., and Wassermann, R. 2010. Revision of CTL models. In Proceedings of the Twelfth Ibero-American Conference on Advances in Artiﬁcial Intelligence, IBERAMIA 2010, 153 162. Springer. Guerra, P. T.; Andrade, A.; and Wassermann, R. 2013. Toward the revision of CTL models through Kripke Modal Transition Systems. In Proceedings of the Sixteenth Brazilian Symposium on Formal Methods, SBMF 2013, 115 130. Springer. Hansson, S. O. 1999. A Textbook of Belief Dynamics: Theory Change and Database Updating. Kluwer Academic. Katsuno, H., and Mendelzon, A. O. 1992. On the difference between updating a knowledge base and revising it. In Belief Revision, 387 394. Cambridge University Press. Kraus, S.; Lehmann, D.; and Magidor, M. 1990. Nonmonotonic reasoning, preferential models and cumulative logics. Artiﬁcial intelligence 44(1-2):167 207. Makinson, D., and G ardenfors, P. 1991. Relations between the logic of theory change and nonmonotonic logic. In The logic of theory change, 183 205. Springer. Nute, D. 1994. Handbook of Logic in Artiﬁcial Intelligence and Logic Programming. Oxford University Press. Ribeiro, J. S., and Andrade, A. 2015. A 3-valued contraction model checking game: Deciding on the world of partial information. In Proceedings of the Seventeenth International Conference on Formal Engineering Methods, ICFEM 2015, 84 99. Springer. Ribeiro, J. S.; Nayak, A.; and Wassermann, R. 2018. Towards belief contraction without compactness. In Proceedings of the Sixteenth International Conference on Principles of Knowledge Representation and Reasoning, KR 2018, 287 296. AAAI Press. Rott, H. 2001. Change, Choice and Inference. Oxford.