Adaptive Logic as a Modal Logic

Patrick Allo

Adaptive Logic as a Modal Logic

Abstract. Modal logics have in the past been used as a unifying framework for the minimality semantics used in defeasible inference, conditional logic, and belief revision. The main aim of the present paper is to add adaptive logics, a general framework for a wide range of defeasible reasoning forms developed by Diderik Batens and his co-workers, to the growing list of formalisms that can be studied with the tools and methods of contemporary modal logic. By characterising the class of abnormality models, this aim is achieved at the level of the model-theory. By proposing formulae that express the consequence relation of adaptive logic in the object-language, the same aim is also partially achieved at the syntactical level. Keywords: Adaptive logic, Modal logic, Preference logic, Nonmonotonic inference.

1.

Introduction

Adaptive logics have evolved from systems for handling inconsistent premises [4–6] to a general framework for all kinds of defeasible reasoning. The standard format developed in [8] subsumes all adaptive logics for non-prioritised premise-sets. Modal logics have gone through a similar evolution. They were originally conceived as an analysis of alethic modalities, but have now become the privileged language to reason about all kinds of relational structures [10, p. xii]. One field where modal logics have been used as a unifying framework is in the analysis of what [14] describes as the different “faces of minimality” in defeasible inference, conditional logic, and belief revision. Modal translations of so-called minimality semantics are found in [11], and more recently in [16]. Given the hypothesis that the standard format of adaptive logic is sufficiently general to incorporate most (if not all) forms of defeasible inference [9, Chap. 1], it is natural to ask whether the consequence relation of adaptive logic can also be embedded in a modal language. Such a modal reconstruction can be given because the consequence relations for adaptive logics can be formalised as formula-preferential systems in the sense of [1].

Presented by Heinrich Wansing; Received October 23, 2011

Studia Logica (2012) DOI: 10.1007/s11225-012-9403-1

c Springer Science+Business Media B.V. 2012 

P. Allo

That is, models are ordered on the basis of the formulae they verify, and the ordering is used to select a subset of the models of the premises. This subset is then used to define the semantic consequence relation. By defining Kripke-style models wherein states are ordered in a similar way, we can then select states in the same manner as we selected models. Insights and results laid out in the present paper are essentially preparatory. The long term aim of this project is to integrate adaptive consequence relations into dynamic doxastic logics (in the style of [2]). The short term aim is more modest, as we merely wish to understand how the Kripke-style models that are needed to obtain a faithful modal reconstruction of adaptive consequence relations differ from the Kripke-style models that have been used to reformulate other types of minimality semantics. The present paper is primarily concerned with the model-theoretic aspects of the modal embedding of adaptive logic. Sections 2 and 3 contain the preliminaries: The standard format of adaptive logic is described (Sect. 2), and the desiderata and formal features of the target systems for a modal reconstruction are reviewed (Sect. 3). The core of the reconstruction is in Sect. 4, and proofs for the correctness of the construction are given in Sect. 5. A specific example follows in Sect. 6. The one exception to the purely model-theoretic approach to the modal reconstruction of adaptive logic is the discussion of modal formulae that express the adaptive consequence relation. This is the topic of Sect. 7. A final section (Sect. 8) situates the results that were obtained in a broader context, and lists what remains to be done.

2.

Adaptive Logics: Purpose and Standard Format

Adaptive logics were initially introduced as a non-monotonic strengthening of standard paraconsistent logics. These so-called inconsistency-adaptive logics are meant to overcome the main flaws of paraconsistent reasoning; for instance, the inability to account for intuitively acceptable uses of the disjunctive syllogism. Inconsistency-adaptive logics solve this problem by invalidating the instances of such argument forms rather than the argument form itself. The functioning of adaptive logics has two sides: a formulapreferential semantics and a dynamic proof-theory. The former is the focus of the present paper. The latter is more closely connected to the core aim of adaptive logics; namely, the explication of actual reasoning processes. A generalisation of how inconsistency adaptive logics are defined can be applied to many reasoning processes, and is characterised by the standard format for adaptive logics.

Adaptive Logic as a Modal Logic

2.1.

Standard Format

An adaptive logic is characterised by a triple that comprises: 1. A Tarski-logic referred to as the lower limit logic (LLL), 2. a set of formulae Ω characterised by a logical form and referred to as the set of abnormalities, and 3. a criterion, referred to as the adaptive strategy, which (in its model-theoretic form) selects models of premise-sets that are no more abnormal than what is actually required by that premise-set. Adaptive consequence relations are defined over a base-language L0 . To simplify meta-theoretical proofs, this language is customarily extended with a classical negation (¬), disjunction (∨), and absurdity-constant (⊥). I shall refer to the resulting language as L1 . The lower limit logic (LLL) is a logic that is defined over the language L1 , enjoys all the usual Tarskian properties, is compact and includes classical logic. An LLL-model of a premise-set Γ is defined as an L1 -model of Γ. We say that ϕ is an LLL-consequence of Γ (formally: Γ |=LLL ϕ) iff ϕ is verified by all LLL-models of Γ. The set of abnormalities Ω is a set of L1 -formulae characterised by a (possibly restricted) logical form that contains at least one logical connective. Adaptive consequence relations are obtained by only considering LLLmodels of the premises that do not verify more members of Ω than needed. There are multiple non-equivalent criteria to ensure this. We only consider two of them: the minimal abnormality strategy and the reliability strategy. The comparison of LLL-models is formalised in terms of their abnormal parts. Definition 1. (Abnormal Part of a Model) Ab(M) = {ϕ ∈ Ω : M  ϕ}. A first way of selecting models by looking at their abnormal parts proceeds by selecting only the normal models. Definition 2. (Normal Model) An LLL-model M of Γ is a normal model iff its abnormal part Ab(M) is empty. A more interesting selection is the minimal abnormality strategy, which selects only those LLL-models (of a premise-set) that are minimal relative to an ordering of models based on their abnormal parts: Definition 3. (Minimally Abnormal Model) An LLL-model M of Γ is minimally abnormal iff there is no LLL-model M of Γ such that Ab(M ) ⊂ Ab(M).

P. Allo

Because the ordering of the models is not total, the above selection of models is not the only sensible one. A more cautious alternative to the one given above is the reliability strategy. Definition 4. (Dab-formulae and (minimal)Dab-consequences) A disjunction of abnormalities Dab(Δ) is the disjunction of the members of a finite Δ ⊆ Ω. Dab-consequences of Γ, are the Dab-formulae verified by all LLLmodels of Γ. A Dab-consequence Dab(Δ) is minimal iff there is no Θ ⊂ Δ such that Dab(Θ) is also a Dab-consequence. Definition 5. (Unreliable Formulae) If Dab(Δ1 ), Dab(Δ2 ), . . . are the minimal Dab-consequences of Γ, then U (Γ) = Δ1 ∪Δ2 ∪· · · is the set of formulae that are unreliable with respect to Γ. Definition 6. (Reliable Model) An LLL-model M of Γ is reliable iff Ab(M) ⊆ U (Γ). The following proposition, which we shall use later on, is a corollary of Lemma 4 from [8] and relates the abnormalities verified by minimally abnormal models to the set of unreliable formulae. Proposition 1. If Γ has LLL-models, then ω ∈ Ω belongs to U (Γ) iff it is verified by some minimally abnormal model of Γ. This immediately implies that the consequence relation for minimal abnormality is at least as strong as the consequence relation for reliability. The following generic example illustrates why the reliability-strategy is more cautious than the minimal-abnormality strategy. Example 1. Let Γ be a premise-set, and ω1 and ω2 be two abnormalities such that for some adaptive consequence relation AL with a logic L as its lower limit logic we have Γ |= ω1 ∨ ω2 while Γ |= ω1 and Γ |= ω2 . Assume, without loss of generality, that M, M and M are L-models of Γ such that Ab(M) = {ω1 }, Ab(M ) = {ω2 } and Ab(M ) = {ω1 , ω2 }. In that case, M and M are minimally abnormal (as well as reliable) models of Γ, whereas M is a reliable but not a minimally abnormal model of Γ. Definition 7. (Semantic Consequence for Minimal Abnormality) Γ |∼m ϕ iff ϕ is verified in all minimally abnormal models M of Γ. Definition 8. (Semantic Consequence for Reliability) Γ |∼r ϕ iff ϕ is verified in all reliable models M of Γ. Definition 9. (Upper Limit Logic) Γ |=ULL ϕ iff ϕ is verified by all normal models M of Γ. Both |∼m and |∼r reduce to |=ULL whenever Γ has normal models.

Adaptive Logic as a Modal Logic

A meta-theoretical property of adaptive logics that should be mentioned at this point is the property of strong-reassurance. Theorem 1. (Strong Reassurance for Minimal Abnormality) If M is an LLL-model of Γ that is not minimally abnormal, then there is a minimally abnormal model M of Γ such that Ab(M ) ⊂ Ab(M). What this property ensures is that there are no infinite paths of less and less abnormal models of a premise-set (cfr. the so-called limit-assumption form conditional logic. For a general discussion see [1] and [7]). The property of reassurance, which is a consequence of strong reassurance, says that whenever a premise-set has LLL-models, there is also a selection of minimally abnormal models of that premise-set.

3.

What Kind of Reconstruction?

The main difference between the standard format of adaptive logic and its intended reformulation within a modal logic is that the former is based on the selection of LLL-models of Γ, whereas the latter is based on the selection of states in the truth-set of Γ in a class of Kripke-style models. In this section we describe a specific type of model that is particularly well-suited for the purpose at hand, and propose two correctness conditions. 3.1.

Preference Models and Preference Languages

Since preference languages have already been used to reduce the conditionals of a basic conditional logic to a combination of two unary modalities [16], we extend the language L1 (which we used to define LLL-models) accordingly and use preference models as the intended class of models for that language. Definition 10. (Basic Preference Language) The set of formulae of the basic preference language L2 is defined by: ϕ ::= ψ| ⊥ |¬ϕ|ϕ1 ∨ ϕ2 |Uϕ|♦ ϕ with ψ ranging over the formulae of a base-language L0 (or a set of propositional atoms). The dual modal operators E and  are standardly defined. Definition 11. (Preference Frame) A preference frame is a pair F = (S, ) with S a non-empty set of states, and a pre-order on S. Definition 12. (Preference Models) A preference model is a three-tuple M = (S, , ·M ) with (S, ) a preference frame, and ·M : Form → P(S) a valuation-function (with Form the set of L0 -formulae).

P. Allo

Satisfaction is standardly defined. We only mention the clauses for the modalities. – M, s  Uϕ iff M, s  ϕ for all s ∈ S, – M, s  Eϕ iff M, s  ϕ for some s ∈ S, – M, s   ϕ iff M, s  ϕ for all s s ∈ S, – M, s  ♦ ϕ iff M, s  ϕ for some s s ∈ S. To facilitate the reference to (possibly infinite) semantic propositions we lift the identity s ∈ ϕM iff M, s  ϕ to arbitrary sets of L1 -formulae. When ϕ is true at all states in a model, we write M  ϕ instead of M, s  ϕ. A natural extension of the bi-modal language L2 consists in the addition of the strict preference operators ♦≺ and ≺ with the following satisfaction-clauses: – M, s  ≺ ϕ iff M, s  ϕ for all s ≺ s ∈ S, – M, s  ♦≺ ϕ iff M, s  ϕ for some s ≺ s ∈ S. Where the requirement that ≺ be a strict sub-relation of is captured by: s ≺ s iff s s and s  s

(≺-adequacy)

When it comes to reconstructing the minimal conditional logic, all that needs to be done is to come up with a formula of the preference-language that is equivalent to ϕ > ψ (with > the conditional). As explained in [11] and [16], this is achieved by the following formula:1 U(ϕ → ♦ (ϕ ∧  (ϕ → ψ)))

(ESI)

A reconstruction based on the language and models of a basic preference logic isn’t sufficient for the intended reconstruction of the adaptive consequence relation. First, unlike conditional logics, adaptive logics are not defined relative to any pre-ordering of models (in the standard format) or states (in the intended reconstruction). LLL-models of Γ are ordered in terms of the abnormalities they verify. We should therefore try to achieve a similar ordering of the states in a preference model. Second, the conditional is a connective, but |∼ is not. In particular, the antecedents can be sets of formulae rather than single formulae. 1 The label we use for this formula refers to the fact that it captures the so-called “eventual strict implication” condition rather than the minimality-condition for the truth of a conditional. The former approach is unavoidable whenever the limit-assumption fails. We shall come back to this issue in Sect. 7.

Adaptive Logic as a Modal Logic

3.2.

Correctness Conditions

We consider two correctness conditions, a semantic and a syntactic one. The semantic correctness condition expressed by (AL) is only concerned with the extension of the modal reconstruction of the adaptive consequence relation. Γ |∼x ϕ iff ΓxM ⊆ ϕM for all M ∈ M

(AL)

with x ∈ {m, r}, and ΓxM ⊆ ΓM . The syntactical correctness condition bears on additional definability and expressivity issues. Namely, for every Γ and ϕ of the language L1 there should be a ψ (not in L1 ) such that (AL*) holds for x ∈ {m, r}. ΓxM ⊆ ϕM iff M  ψ

(AL*)

In combination with (AL) this amounts to the requirement that there should be a formula ψ of the language L2 (or some further extension of that language) that is globally valid (i.e. true at all states in all models of M) iff ϕ is an adaptive consequence of Γ.

4.

Abnormality Models

As a preliminary, we define what it means for a class of preference models to generate a certain logic. Definition 13. Where M is a class of preference models and L a logic defined over a language L, we say that the class of models M generates the logic L iff ΓM ⊆ ϕM for all M ∈ M iff Γ |=L ϕ for all Γ ∪ {ϕ} that only contain L-formulae. For now, we are primarily interested in the L1 -fragments of the modal logics generated by M. Definition 14. (Abnormality Models) An abnormality model is a 3-tuple M = (S, Ω, ·M ) where S is a set of states, Ω the set of abnormalities, and ·M a valuation-function. We define a function AbM : S → P(S), and a binary relation over S in accordance with the following clauses: 1. AbM (s) = {ω ∈ Ω : s ∈ ωM } 2. s s =⇒ AbM (s) ⊆ AbM (s ) 3. AbM (s) ⊆ AbM (s ) =⇒ s s and restrict the valuation such as to comply with a last clause:

P. Allo

4. For every proposition ΓM ⊆ S and every s ∈ ΓM , if for some Δ ⊂ AbM (s), we have Γ ∪ {¬ϕ : ϕ ∈ Ω \ Δ} |=LLL ⊥, then there is an s ∈ ΓM such that AbM (s ) = Δ. In the above definition the Clauses (1) and (2) warrant that is an ordering that only depends on the abnormalities true at a state, while Clause (3) ensures that every difference (and identity) in abnormality between states is captured by the order-relation . Finally, Clause (4) forces the presence of “sufficiently normal states” in every proposition.2 Because abnormality models give rise to preference-models (the definition of ensures that it is a pre-order) that comply with an additional restriction on the admissible valuations on a preference frame (which technically makes it a general frame) we should verify whether the bi-conditional (for formulae in L1 ) in Definition 13 is preserved when the restrictions imposed by the clauses of Definition 14 are applied. Proposition 2. Where M1 and M2 are, respectively, the class of all preference models and the class of all abnormality models, both classes generate the same logic over the language L1 (equivalently: the logics generated by both classes have the same propositional fragment). Proof. We need to prove that ΓM ⊆ ϕM (where Γ ∪ {ϕ} contains only L1 -formulae) holds for all M ∈ M1 iff it holds for all M ∈ M2 . =⇒ Immediate in view of the fact that M2 ⊂ M1 . ⇐= We prove the contrapositive. Assume that ΓM ⊆ ϕM for some M ∈ M1 . That is, some s ∈ ΓM does not verify ϕ. If M is also in M2 the result is trivial, so we only consider the case where M isn’t an abnormality model. If M isn’t an abnormality model because it fails to satisfy Clauses (1), (2), or (3), it is easily seen that there is an abnormality model M that only differs from M with respect to the extension of . Since Γ and ϕ are L1 formulae, it immediately follows that some s ∈ ΓM won’t verify ϕ either. If M isn’t an abnormality model because it (also) fails to satisfy Clause (4), we only need to extend it to a model M = (S  ,  , Ω, AbM , ·M ) that does satisfy Clause (4) (and, if necessary, also the remaining clauses). Since this can be done in such a way that M is a sub-model of M (in particular: S ⊂ S  , and for all p we have pM = S ∩ pM ), the fact that ϕ and Γ do 2 An alternative to Clause (4) would be the following: Whenever Γ |=LLL ⊥, we have ΓM = ∅ for all abnormality models. This would ensure that for every maximally nontrivial set of L1 -formulae the corresponding infinite proposition is non-empty in every abnormality model. This approach is dismissed for being unnecessarily restrictive.

Adaptive Logic as a Modal Logic

not contain modal formulae suffices to ensure that for any s ∈ ΓM that does not verify ϕ there is an s ∈ ΓM that does not verify ϕ either. Proposition 3. If M is a class of preference models that generates a logic L over the language L1 , then for all M ∈ M it holds that s ∈ ΓM iff the L1 -theory of M, s (the set of all L1 -formulae true at s) is the L1 -theory of some L-model of Γ (the set of all L1 -formulae verified by M). Proof. If M generates L, we have ΓM ⊆ ϕM for all M ∈ M iff Γ |=L ϕ. By substituting ⊥ for ϕ we obtain Γ |=L ⊥ iff ΓM is non-empty for some M ∈ M, which shows that there is a model M of Γ iff Γ is also satisfiable in a model M ∈ M. ⇐= Let Θ be the L1 -theory of some L-model M of Γ. From the above, it follows that Θ can be satisfied in some M ∈ M and thus that some s in that model will verify all members of Θ. Since Γ ⊆ θ this s is also in ΓM . =⇒ Let Θ be the L1 -theory of M, s with s ∈ ΓM . From the above it follows that Θ must have an L-model M, while Γ ⊆ Θ warrants that M is also an L-model of Γ. Hence, we have an L-model of Γ that verifies all members of Θ. To find out whether the class of abnormality models complies with (AL), we now need to define the different ways of selecting states in terms of . As a preliminary, we define the relation of abnormality-comparability. Definition 15. (Ab-comparable) The states s and s are Ab-comparable (formally, s ∼ s ) iff s s or s s. Note that the relation of Ab-comparability is not an equivalence-relation; it is reflexive and symmetric, but not transitive. Definition 16. (Minimally abnormal states) The set of minimally abnormal states in ΓM is given by:    Γm M = {s ∈ ΓM : (s ∈ ΓM & s ∼ s ) =⇒ s s )}

The definition of minimally abnormal states follows quite closely the original definition of minimally abnormal models. The only difference lies in the use of an abnormality pre-ordering rather than a strict pre-order (but see Proposition 8 for an alternative). For the definition of reliable states we follow a different approach. Definition 17. (Reliable States) The set of reliable states in ΓM is given by:

P. Allo  ΓrM = {s ∈ ΓM : ∀ω ∈ Ω(s ∈ ωM ⇒ ∃s ∈ Γm M & s ∈ ωM )}

To see how the above characterisation relates to an order-theoretic characterisation in terms of , consider first the following definition. Definition 18. (Minimal Upper Bound) Where W,  is a pre-ordered set and X a subset of W , we say that u is an upper-bound of X in W,  iff u ∈ W and x u for all x ∈ X. An upper-bound u of X in W,  is minimal iff there’s no upper-bound u of X in W,  such that u u and u  u . The following negative result shows that the set of reliable states cannot be given a direct order-theoretic formulation in terms of . Proposition 4. Let M = (S, Ω, ·M ) be an abnormality model. 1. s ∈ ΓrM =⇒ s u for some minimal upper-bound u of an X ⊆ Γm M in ΓM . 2. s ∈ ΓrM ⇐= s u for some minimal upper-bound u of an X ⊆ Γm M in ΓM . Proof. (Ad1.) Let ΓM = {s1 , s2 , s3 } with Ab(s1 ) = {ω1 , ω2 }, Ab(s2 ) = {ω3 , ω4 }, and Ab(s3 ) = {ω1 , ω2 , ω3 }. It is clear that s1 and s2 are the minimally abnormal states in ΓM and that s3 is a reliable state, while there is no upper-bound u of any subset of {s1 , s2 } such that s3 u. (Ad2.) Consider a premise-set Γ = {ω1 ∨ ω2 , (ω1 ∧ ω2 ) → ω3 }, and let M be an abnormality model such that for some s, s ∈ ΓM we have Ab(s) = ω1 and Ab(s ) = ω2 , and thus s, s ∈ Γm M . Since Γ ∪ {ω1 , ω2 , ¬ω3 } cannot be satisfied, there is no s ∈ ΓM such that Ab(s ) = {ω1 , ω2 }. Hence, if u is a minimal upper-bound of {s1 , s2 } in ΓM , then ω3 ∈ Ab(u). Yet, u u, but u is not a reliable state. r Proposition 5. Γm M ⊆ ΓM

Proof. Immediate in view of Definition 17. Proposition 6. If the restriction of to ΓM is connected (for every r s, t ∈ ΓM we have s t or t s), then Γm M = ΓM . Proof. Assume that the restriction of to ΓM is connected. In view of Proposition 5, we only need to show ΓrM ⊆ Γm M.  m  Let s, s be two states in ΓM . Since s ∼ s holds by assumption, it follows from Definition 16 that s s and s s. In other words, all minimally

Adaptive Logic as a Modal Logic

abnormal states in ΓM have the same abnormal part, and only minimally abnormal states can be reliable. To see why the converse doesn’t hold, just consider a model where Γm M and ΓM coincide, while some s, t ∈ ΓM have different and hence incomparable abnormal parts. To conclude this section, we briefly consider abnormality models with a strict abnormality ordering. Definition 19. (Strict Abnormality Models) Where (S, Ω, ·M ) is an abnormality model, we define a binary relation ≺ over S such that: 1. AbM (s) ⊂ AbM (s ) =⇒ s ≺ s 2. s ≺ s =⇒ AbM (s) ⊂ AbM (s ) Proposition 7. (≺-adequacy of strict abnormality-ordering) M = (S, Ω, ·M ) is a strict abnormality model iff: (i) it satisfies clauses (2) and (3) from Definition 14, and (ii) ≺ is the strict sub-relation of that satisfies ≺-adequacy. Proof. We only need to prove that AbM (s) ⊂ AbM (s ) ⇔ s ≺ s holds for all states iff ≺ is the strict sub-relation of that satisfies ≺-adequacy. This follows immediately from that fact that (i) we already have AbM (s) ⊆ AbM (s ) ⇔ s s , and (ii) ⊂ is itself the strict sub-relation of ⊆ such that A ⊂ B iff A ⊆ B and B ⊆ A. The strict ordering ≺ can be used to formulate an alternative definition of minimally abnormal states by requiring that a state s is minimally abnormal in ΓM iff there is no state s in ΓM such that s ≺ s. As shown below, the alternative approach is equivalent to that of Definition 16. Proposition 8. A state s ∈ ΓM is a minimally abnormal state iff there is no s ∈ ΓM such that s ≺ s. Proof. The following claims are all equivalent: 1. For all s ∈ Γ that are Ab-comparable with s we have s s . 2. For no s ∈ Γ we have s s and s  s . 3. For no s ∈ Γ we have s ≺ s. The crucial step is the equivalence of (2) and (3), which holds in virtue of ≺-adequacy.

P. Allo

5.

Correctness and Related Results

We first establish that versions of the properties of strong reassurance and reassurance (cfr. Theorem 1) do hold within the class of abnormality models. The main reason why these results carry over to Abnormality Models is that Clause (4) from Definition 14 ensures that whenever there is a state s ∈ ΓM and an LLL-model M of Γ such that Ab(M) ⊂ Ab(s), there is also an s ∈ ΓM such that Ab(s ) = Ab(M). Theorem 2. (Strong Reassurance for Abnormality Models) Whenever s ∈   m  ΓM \ Γm M , there is an s ∈ ΓM such that s ∈ ΓM and s s. Proof. Recall that in virtue of Proposition 3 every s ∈ ΓM will have the same L1 -theory as some LLL-model of Γ. Let M1 be the LLL-model with the same L1 -theory as some s ∈ ΓM \ Γm M . Since s isn’t -minimal in ΓM , there should be si ’s in ΓM such that si s and s  si . Since for every such si there must be an LLL-model of Γ with the same L1 -theory, M1 isn’t a minimally abnormal model of Γ. By Theorem 1, there must then be a minimally abnormal model M2 of Γ such that Ab(M2 ) ⊂ Ab(M1 ). But then by Clause (4) of Definition 14 one of the states in virtue of which s isn’t included in Γm M must have the same L1 -theory as M2 . Call this state sm . By Clause (3) it follows that sm s and by Clause (2) it follows that s  sm . What remains to be shown is that sm is also -minimal in ΓM and thus a member of Γm M . Assume, for reductio, that there is an s ∈ ΓM such that s sm and sm  s . In view of clauses (1) and (3), this implies that AbM (s ) ⊂ AbM (sm ), and because there should be an LLL-model M3 of Γ that verifies exactly the same L1 -formulae as s , we would also have that Ab(M3 ) ⊂ Ab(M2 ). The latter is impossible if M2 is a minimally abnormal model of Γ. Corollary 2.1. (Reassurance for Abnormality Models) If ΓM is nonempty, then Γm M is also non-empty. We can now start with the actual proof of the correctness of our reconstruction of adaptive logic. We first show that (AL) holds for minimal abnormality. Theorem 3. (Semantic Correctness for Minimal Abnormality) If M is the class of all abnormality models that generates a logic with LLL as its L1 fragment, then (AL) holds relative to the adaptive consequence relation |∼m with LLL as its lower limit logic. Proof. The left-to-right direction follows immediately from Lemma 3.1, while the right-to-left direction follows from Lemma 3.2.

Adaptive Logic as a Modal Logic

Lemma 3.1. For all s ∈ S we have s ∈ Γm M iff there is a minimally abnormal model M of Γ such that Ab(M) = AbM (s). Proof. =⇒ Assume that s ∈ Γm M . In view of Proposition 3 we only need to prove that the LLL-model of Γ with the same L1 -theory as s is itself a minimally abnormal model of Γ. Call this model M1 . Assume, for reductio, that there is an M2 such that Ab(M2 ) ⊂ Ab(M1 ). This would mean that for some Δ ⊂ AbM (s) we have Γ ∪ {¬ϕ : ϕ ∈ Ω \ Δ} |=LLL ⊥, but then by Clause (4) of Definition 14 there should be an s ∈ ΓM such that AbM (s ) = Δ. This implies that s ∈ ΓM and AbM (s ) ⊂ AbM (s), and thus also s s and s  s . The latter two contradict the assumption that s is a minimally abnormal state in ΓM . ⇐= Immediate from the proof of Theorem 2. Lemma 3.2. For every minimally abnormal model M of Γ, there is an abnormality model M such that for some s ∈ Γm M we have Ab(M) = AbM (s). Proof. Immediate in view of (the proof of) Theorem 2 and the fact that all L1 -formulae verified by some LLL-model can be satisfied at some point in a preference model. Theorem 4. (Semantic Correctness for Reliability) If M is the class of all abnormality models that generates a logic with LLL as its L1 -fragment, then (AL) holds relative to the adaptive consequence relation |∼r with LLL as its lower limit logic. Proof. The left-to-right direction follows immediately from Lemma 4.2, while the right-to-left direction follows from Lemma 4.3. Lemma 4.1. For all s ∈ ΓM , the state s is in ΓrM iff AbM (s) ⊆ U (Γ). Proof. =⇒ Assume that s is a reliable state in ΓM . By Lemma 3.1 there is for every t ∈ Γm M a minimally abnormal model M of Γ with the same L1 -theory as t. By Proposition 1 every abnormality verified by such an M is an unreliable formula. Since AbM (t) = Ab(M ), we have AbM (t) ⊆ U (Γ) for every t ∈ Γm M . Finally, by Definition 17, since every abnormality true at s must also be true at some t ∈ Γm M we obtain AbM (s) ⊆ U (Γ) as required. ⇐= Assume for reductio that AbM (s) ⊆ U (Γ) and s ∈ ΓM , but s ∈ ΓrM . By Definition 17 this means that M, s  ω for some ω ∈ Ω that is not verified by any s in Γm M . But then, because by Lemma 3.1 s has the same L1 -theory as some minimally abnormal model of Γ, it follows by Proposition 1 that ω ∈ U (Γ), which contradicts AbM (s) ⊆ U (Γ). Lemma 4.2. For all s ∈ S we have s ∈ ΓrM iff there is a reliable model M of Γ such that Ab(M) = AbM (s).

P. Allo

Proof. =⇒ Assume that s ∈ ΓrM . By Lemma 4.1, it then follows that AbM (s) ⊆ U (Γ). Let M be an LLL-model of Γ that verifies exactly the same L1 -formulae as s. It then holds that Ab(M) = AbM (s) ⊆ U (Γ), and thus by Definition 5 that M is a reliable model of Γ. ⇐= We prove the contrapositive. Assume that s ∈ ΓrM . By Lemma 4.1, it then follows that some ω ∈ AbM (s) does not belong to U (Γ). Let M be the LLL-model of Γ with the same L1 -theory as s. It then holds that because ω is also verified by M, we have that Ab(M) ⊆ U (Γ), and thus by Definition 5 that M isn’t a reliable model of Γ. Lemma 4.3. For every reliable model M of Γ, there is an abnormality model M such that for some s ∈ ΓrM we have Ab(M) = AbM (s). Proof. Let M1 be an arbitrary reliable model of Γ and M a preference model where some s ∈ ΓM has the same L1 -theory as M1 . We then need to prove s ∈ ΓrM . From our construction, it follows that (i) Ab(M1 ) = AbM (s), (ii) Ab(M1 ) ⊆ U (Γ), and thus AbM (s) ⊆ U (Γ). Our result then follows by Lemma 4.1.

6.

An Example: Inconsistency Adaptive Logic

We give a detailed account of the modal reconstruction of the inconsistency adaptive logic CLuNm . The paraconsistent logic CLuN is used as a lower limit logic of CLuNm . It is defined over a language L0 with the following connectives {∼, ∨, ∧, ⊃} (with ∼ a paraconsistent negation), which we extend to a language L1 with the remaining classical connectives (classical negation and absurdity constant). The axiomatic presentation of the L0 -fragment of CLuN is obtained by adding excluded middle (ϕ∨ ∼ ϕ) to the positive fragment of propositional classical logic. Except for the assignment-function (which ranges over both atomic propositions and negated formulae) and the clause for the paraconsistent negation (v∼ ), the semantic characterisation is classical. vM (∼ ϕ) = 1 iff vM (ϕ) = 0 or v(∼ ϕ) = 1

(v∼ )

The set of abnormalities is the set Ω = {ϕ∧ ∼ ϕ : ϕ ∈ Form} of all explicit contradictions. The combination of CLuN as a lower limit logic, and Ω as the set of abnormalities suffices to conclude that the normal models of a premise-set are just its classical models, and that the upper limit logic is

Adaptive Logic as a Modal Logic

classical propositional logic. As suggested by the notation, the strategy is minimal abnormality.3 We start by defining the class of abnormality models that generates the L0 -fragment of the paraconsistent logic CLuN. The first step is to modify the standard assignment-function for CLuN to obtain a mapping from pairs of propositional constants and states to truth-values, and from pairs of negated L0 -formulae and states to truth-values: – v : (Prop ∪ Form∼ ) × S → {0, 1}, We then modify the standard CLuN valuation-function accordingly: – vM (ϕ, s) = 1 iff v(ϕ, s) = 1, for ϕ ∈ Prop, – vM (∼ ϕ, s) = 1 iff vM (ϕ, s) = 0 or v(∼ ϕ, s) = 1, – vM (ϕ1 ∨ ϕ2 , s) = 1 iff vM (ϕ1 , s) = 1 or vM (ϕ2 , s) = 1, – vM (ϕ1 ∧ ϕ2 , s) = 1 iff vM (ϕ1 , s) = 1 and vM (ϕ2 , s) = 1, – vM (ϕ1 ⊃ ϕ2 , s) = 1 iff vM (ϕ1 , s) = 0 or vM (ϕ2 , s) = 1. Given an abnormality model M = (S, Ω, ·M ), we can then require that ·M extends vM by stipulating that for all L0 -formulae we have: ϕM = {s ∈ S : vM (ϕ, s) = 1} The classical behaviour of ¬ and ⊥ is ensured by the usual satisfactionclauses. As before, we use ·M to refer to the truth-set of any L1 -formula or set of L1 -formulae in a preference model M, and therefore lift the above identity to the level of arbitrary sets of formulae. ΓM = {s ∈ S : ϕ ∈ Γ ⇒ vM (ϕ, s) = 1} In the previous section we already showed that (AL) holds for both minimal abnormality and reliability whenever the class of abnormality models generates a logic with the lower limit logic as its L1 -fragment. Specifically, it follows from Theorem 3 that when a class M of abnormality models generates a logic with CLuN as its propositional fragment, we have that Γ |∼ CLuNm ϕ iff Γm (∗) M ⊆ ϕM for all M ∈ M As a result, we only need the following proposition to prove (∗).

3

The propositional fragment of CLuN is described in [3]; it’s first-order formulation and the adaptive logics based on it can be found in [5] and [9, Chap. 2].

P. Allo

Proposition 9. Where vM is a CLuN valuation-function, and M the class of abnormality models such that s ∈ ϕM iff vM (ϕ, s) = 1, then M generates the L1 -fragment of the logic CLuN. Proof. =⇒ We prove the contrapositive. Assume that ΓM ⊆ ϕM for some M ∈ M. Let s be a state in M such that s is in ΓM , but not in ϕM . Since for all M ∈ M we have that s ∈ ϕM iff vM (ϕ, s) = 1, this is equivalent to saying that for some vM we have vM (ψ, s) = 1 for all ψ ∈ Γ while vM (ϕ, s) = 1. Let v  be an assignment-function for CLuN such that v  (ϕ) = 1 iff v(ϕ, s) = 1 for all ϕ ∈ Prop ∪ Form∼ . By induction on the complexity of the formulae we can show that there should be a CluN valuation    vM such that vM (ψ) = 1 for all ψ ∈ Γ while vM (ϕ) = 1, which gives us Γ |=CLuN ϕ as required. ⇐= We prove the contrapositive. Assume that Γ |=CLuN ϕ, and thus that for some CLuN-valuation vM that extends v we have vM (ψ) = 1 for all ψ ∈ Γ while vM (ϕ) = 1. Let v  : (Prop ∪ Form∼ ) × S → {0, 1} be an assignment-function such that v  (ϕ, s) = 1 iff v(ϕ) = 1 for all ϕ ∈ Prop ∪ Form∼ . By induction on the complexity of the formulae we can show that there is a   valuation vM : Form × S → {0, 1} (as defined above) such that vM (ψ, s) = 1  for all ψ ∈ Γ while vM (ϕ, s) = 1. Consequently s is in ΓM , but not in ϕM , which gives us ΓM ⊆ ϕM .

7.

Expressing Adaptive Consequence

To comply with the second correctness criterion (AL*) we need to find formulae ϕ and ψ whose satisfaction-conditions are equivalent to, respectively, r Γm M ⊆ ϕM and ΓM ⊆ ϕM . Because the latter are global conditions on the models, the corresponding satisfaction-conditions should be global as well. The latter fact can be illustrated by first considering a simpler example. We can express ΓM ⊆ ϕM as the strict implication ⎞ ⎛  γi → ϕ⎠ . (STRICT) U⎝ γi ∈Γ

Since this formula starts with a universal modality it expresses a global condition. It is important to keep the following in mind: (STRICT) counts as a formula of the language L2 only when Γ is finite. When Γ is infinite, it can only be expressed in a language that allows for countably infinite conjunctions. Yet, since lower limit logics have has to be  to be compact, there n a finite subset Δ of Γ such that M  U( γi ∈Δ γi → ϕ) iff ΓM ⊆ ϕM .

Adaptive Logic as a Modal Logic

7.1.

Minimal Abnormality

We now consider two different options that correspond to the minimal abnormality strategy. The first one is a version of (ESI)         γi → ♦ γi ∧  γi → ϕ , (ESI*) U γi ∈Γ

γi ∈Γ

γi ∈Γ

and only makes use of the universal modality and the modalities for the preorder . The second one, by contrast, uses the box-operator for the strict order ≺ (see e.g. [12, p. 37]) ⎛⎛ ⎞ ⎞   U ⎝⎝ (MIN) γi ∧ ≺ ¬ γi ⎠ → ϕ⎠ . γi ∈Γ

γi ∈Γ

The need to express premise-sets as the conjunction of all the premises can be problematic because the failure of compactness for adaptive logics blocks the detour via finite premise-sets we used for (STRICT). As a consequence, (ESI*) as well as (MIN) can either only be used to express adaptive consequence for finite premise-sets, or they have to be formulated in a suitable infinitary extension of the modal language L2 . We provisionally restrict ourselves to finite premise-sets. (ESI*) is indirect in the sense that it does not refer to minimally abnormal states; it even works when there are no such states. (MIN), by contrast, directly captures the idea that ϕ needs to be true at all states in Γm M. The former is preferable when there is no guarantee that there are always minimally abnormal states, but given Corollary 2.1 this is not a concern. We show that within the class of strict abnormality models both versions are equivalent by proving that they both comply with (AL*). Theorem 5. (Syntactic Correctness for Minimal Abnormality (I)) For all strict abnormality models M, the formula    ≺ U γi ∧  ¬ γi → ϕ γi ∈Γ

γi ∈Γ

is verified by all s in M iff Γm M ⊆ ϕM .   Proof. We only need to prove that M, s  γi ∈Γ γi ∧ ≺ ¬ γi ∈Γ iff s ∈ Γm M . The first conjunct is true iff s is in ΓM . The second conjunct is true iff every s ≺ s falsifies at least one member of Γ, which by Proposition 8 is necessary and sufficient for s to be in Γm M whenever it is in ΓM .

P. Allo

Theorem 6. (Syntactic Correctness for Minimal Abnormality (II)) For all (strict) abnormality models M, the formula       U γi → ♦ γi ∧  γi → ϕ γi ∈Γ

is verified by all s in M iff

γi ∈Γ

Γm M

γi ∈Γ

⊆ ϕM .

Proof. ⇐= Assume that Γm M ⊆ ϕM . If this is trivially satisfied because is empty, then we know by Corollary 2.1 that ΓM is empty as well. Γm M  But then we know that γi ∈Γ γi is false at all states, and hence the implication within the scope of U is true at all states. The more interesting case is when Γm M is non-empty. Since the implication within the scope of U is again vacuously true at all states that do not belong to ΓM , we only need Let s be an to check that the same implication is true at all states  in ΓM .  arbitrary state in ΓM . We need to show that ♦ ( γi ∈Γ γi ∧ ( γi ∈Γ γi → ϕ)) is true at s. That is, there must be an s ∈ ΓM such that s s, and   γi → ϕ (†) s   γi ∈Γ

We first show that (†) holds for all s ∈ Γm M , and then show that for any   s ∈ ΓM there is such an s for which s s holds. Let s be an arbitrary state such that s s . If s is also in Γm M, then the implication within the scope of  is true in virtue of Γm M ⊆  m ϕM . If s isn’t in ΓM , then it cannot be in ΓM either. Two cases need to be considered. Either we have s s , which contradicts s ∈    m Γm M ; or we have s  s which contradicts s ∈ ΓM . The falsity of Γ at s makes the implication within the scope of  vacuously true at s . We need to consider two separate cases to show that for any s ∈ ΓM ,  m there is always an s ∈ Γm M such that s s. If s is itself already in ΓM , m the result follows immediately from s s. If s isn’t in ΓM , then we only need to appeal to Theorem 2. =⇒ To prove the contrapositive we assume Γm M ⊆ ϕM . Let s be that doesn’t verify ϕ. Note first that since s doesn’t a statein Γm M verify γi ∈Γ γi → ϕ, it follows in virtue of s s that s doesn’t ver ify  ( γi ∈Γ γi → ϕ) either. But for the same reason, it won’t verify   ♦ ( γi ∈Γ γi ∧  ( γi ∈Γ γi → ϕ)), and yet verify Γ. Since U is a global modality, we only need one state where the implication within its scope is false for the strict implication to be false everywhere.

Adaptive Logic as a Modal Logic

The (restricted) strict implications expressed by (STRICT), (ESI*), and (MIN) can also be seen as conditional box-operators. It is useful to introduce some specific notation that reflects this. We shall henceforth write [Γ]ϕ as shorthand for (STRICT), and (because they’re equivalent in the present context) write [Γ]m ϕ as shorthand for (ESI*) as well as for (MIN). For reasons that shall become clear below, it is also useful to consider their duals Γϕ and Γm ϕ. ⎛ ⎞  Γϕ ↔ E ⎝ γi ∧ ϕ⎠ ⎛ Γm ϕ ↔ E ⎝ ⎛ Γm ϕ ↔ E ⎝

γi ∈Γ

 γi ∈Γ



⎛ γi ∧  ⎝ ⎛

⎛ γi → ♦ ⎝

γi ∈Γ



γi ∧ ≺ ⎝¬

γi ∈Γ

7.2.



⎞



⎞⎞⎞ γi ∧ ϕ⎠⎠⎠

γi ∈Γ

⎞

γi ⎠ ∧ ϕ⎠

γi ∈Γ

Reliability

Finding a formula that corresponds to the reliability strategy is more cumbersome. The main reason is that from a model-theoretic viewpoint the selection of reliable states is less straightforward—it either requires a reference to unreliable formulae or it requires a reference to states that do not verify any abnormality that isn’t also verified by some minimally abnormal state. By contrast, from a proof-theoretic viewpoint reliability is much more natural. The two-step procedure described below partly exploits this proof-theoretic naturalness.4 Formulae of the form  ωi Γ ωi ∈Δ

(with Δ ⊆ Ω) can be used to express that all abnormalities in Δ are verified by some state in ΓM . Similarly, formulae of the form  Γm ωi ωi ∈Δ

(again, with Δ ⊆ Ω) can then be used to express that each abnormality in Δ is verified by some minimally abnormal state in ΓM . By putting the two 4

What I primarily refer to is the following theorem: Γ |∼r ϕ iff Γ |=LLL ϕ ∨ Dab(Δ) and U (Γ) ∩ Δ = ∅. See Theorem 7 in [8].

P. Allo

together we can express an important feature of the abnormalities that are verified by reliable states in ΓM ; namely the fact that at most all abnormalities verified by some minimally abnormal state in ΓM are verified by reliable states in ΓM . To state this fact in its full generality, we need all instances of the following two formulae (for Γ a set of L1 -formulae and Δ ⊆ Ω)       m Γ ωi ∧ Γ ωi ∧ ¬θi ωi (R1) → Γr ωi ∈Δ

ωi ∈Δ

Γr



ωi ∈Δ

θ∈Ω\Δ

→

ωi ∈Δ



Γm ωi

(R2)

ωi ∈Δ

Remark also that in view of Proposition 4, we cannot use the simpler unique version given below:     m Γ ωi ∧ Γ ωi ↔ Γr ωi ωi ∈Δ

ωi ∈Δ

ωi ∈Δ

As before, this requires the use of infinitely long conjunctions. Fortunately, if we’re only interested in finite premise-sets, we can restrict our attention to instances where Δ is finite as well. More exactly, we can make use of the following finitary restriction: Let at(Γ) be the set of all atomic formulae in Γ, and FormΓ the set of L1 formulae that can be obtained from at(Γ) and the connectives of L1 . Use this set to define ΩΓ as Ω ∩ FormΓ . If Γ is finite, at(Γ) will be finite as well. For many lower limit logics (e.g. classical logic, but also some paraconsistent and paracomplete logics) a restriction to a finite stock of atoms will suffice to ensure that ΩΓ contains only finitely many non-equivalent abnormalities as well. If, by contrast, the lower limit logic is a modal logic with infinitely many non-equivalent modalities (for instance K or T [see 13, p. 56], but also the paraconsistent logic CluN when ∼ is seen as a modality), the required finitary restriction cannot be achieved by merely restricting the set of atoms. In these cases, we need to define the set FormΓn ⊂ FormΓ of formulae in FormΓ with modal degree ≤ n, with n the modal degree of Γ.5 Using a standard result in modal logic, we can then show that for any n the set Ω ∩ FormΓn will again only contain finitely many non-equivalent abnormalities.6 5

The modal degree of a formula is inductively defined as follows: (i) deg( ) = 0, (ii) deg(ϕ ∧ ψ) = max(deg(ϕ), deg(ψ)), (iii) deg(♦ϕ) = deg(ϕ) + 1. The modal degree of a set of formulae Γ is the maximum of the degree of its members. 6 See for instance Proposition 2.29 on p. 74 in [10].

Adaptive Logic as a Modal Logic

The above results hold a fortiori for each Δ ⊆ ΩΓ and Δ ⊆ ΩΓn , and thus for each finite Γ, we will only have to consider (finitely many) instances of (R1) and (R2) that contain finite conjunctions of abnormalities. Since there are countably many finite premise-sets, there will only be countably many instances of (R1) and (R2).7 We now show that the conjunction of (R1) and (R2) gives us the right answer to the question which abnormalities are verified by reliable states. Proposition 10. For all abnormality models M, and finite Δ ⊆ Ω we have      m M Γ ωi ∧ Γ ωi ∧ ¬θi ωi ∈Δ

ωi ∈Δ

θ∈Ω\Δ

ΓrM .

only if Δ is verified by some s ∈  Proof. The formula ωi ∈Δ Γm ωi is globally true in M iff every ωi ∈ Δ is verified by  some minimally abnormal state in ΓM . Likewise, Γ( ωi ∈Δ ωi ∧ θ∈Ω\Δ ¬θi ) is globally true in a model iff there is an s ∈ ΓM such that Δ = Ab(s). Let Δ be the set of all abnormalities that are verified by some minimally abnormal state in ΓM . Since Δ ⊆ Δ and s falsifies all abnormalities in Ω \ Δ, it also falsifies all abnormalities in Ω \ Δ . By Definition 17, this implies s ∈ ΓrM . Proposition 11. For all abnormality models M, and finite Δ ⊆ Ω we have  Γm ωi M ωi ∈Δ

if Δ is verified by some s ∈

ΓrM .

Proof. Immediate in view of Definition 17. The conjunction of (R1) and (R2) is not sufficient to express ΓrM ⊆ ϕM . This is because it allows us to derive facts about which abnormalities hold at reliable states, but remains silent about other formulae verified at those states. The following equivalence closes this gap:8





  r r ∧ ¬Γ , (R3) [Γ] ϕ ↔ [Γ] ϕ ∨ ωi ωi ωi ∈Δ

7

ωi ∈Δ

Non-modal logics where a finite supply of atoms isn’t sufficient to obtain a finite set of non-equivalent formulae require a different strategy. This lies beyond the scope of the present paper. 8 Remark that (R3) does not imply that [Γ]r and Γ r would fail to be duals.

P. Allo

Roughly, the right hand-side of (R3) states that ΓM ⊆ (ϕM ∪ ω1 M ∪ · · · ωn M ) and ΓrM ∩(ω1 M ∪ · · · ωn M ) = ∅, for {ω1 , . . . , ωn } = Δ ⊆ Ω (cfr. Lemma 7.1 below). This is all we need to prove (AL*) for reliability. Theorem 7. (Syntactic Correctness for Reliability) For all abnormality models M we have ΓrM ⊆ ϕM iff





  r ∧ ¬Γ [Γ] ϕ ∨ ωi ωi ωi ∈Δ

ωi ∈Δ

is globally true in M. Proof. Immediate in view of Lemma’s 7.1 and 7.2 for which the proofs are given below. Lemma 7.1. For all abnormality models M we have ΓM ⊆ (ϕM ∪ ω1 M ∪ · · · ωn M ) and ΓrM ∩(ω1 M ∪ · · · ωn M ) = ∅, for {ω1 , . . . , ωn } = Δ ⊆ Ω iff:





  r ∧ ¬Γ ωi ωi M  [Γ] ϕ ∨ ωi ∈Δ

ωi ∈Δ

Proof. We first observe that

ΓM ⊆ (ϕM ∪ ω1 M ∪ · · · ∪ ωn M ) is equivalent to M  [Γ](ϕ ∨ ( ωi ∈Δ ωi )) in virtue of the meaning of [Γ] and classical disjunction. Next, M  ¬Γr ( ωi ∈Δ ωi ) is equivalent to M   [Γ]r ( ωi ∈Δ ¬ωi ), which holds iff ΓrM ⊆ (¬ω1 M ∩ · · · ∩ ¬ωn M ). The last condition is equivalent to ΓrM ∩ (ω1 M ∪ · · · ∪ ωn M ) = ∅ in virtue of the meaning of classical negation. Lemma 7.2. For all abnormality models M we have ΓrM ⊆ ϕM iff ΓM ⊆ (ϕM ∪ω1 M ∪ · · ·∪ωn M ) and ΓrM ∩(ω1 M ∪ · · ·∪ωn M ) = ∅, for {ω1 , . . . , ωn } = Δ ⊆ Ω. Proof. ⇐= Assume that for some set of abnormalities {ω1 , . . . , ωn } = Δ we have ΓM ⊆ (ϕM ∪ ω1 M ∪ · · · ∪ ωn M ) and ΓrM ∩ (ω1 M ∪ · · · ∪ ωn M ) = ∅. Since ΓrM ⊆ ΓM , it follows by the transitivity of ⊆ that ΓrM ⊆ (ϕM ∪ ω1 M ∪ · · · ∪ ωn M ). Yet, because no state in ΓrM verifies an abnormality ωi ∈ Δ, it follows that all states in ΓrM must verify ϕ. =⇒ Assume that ΓrM ⊆ ϕM . Let Θ be the set of all abnormalities that are not verified by any s in ΓrM . Any state of ΓrM will verify the negation of every abnormality in Θ. Thus we obtain the following identity ΓrM = ΓM ∩ {¬θ : θ ∈ Θ}M ,

Adaptive Logic as a Modal Logic

which we use to derive {¬θ : θ ∈ Θ}M ∩ ΓM ⊆ ϕM . By compactness and classical logic we then obtain ΓM ⊆ ϕM ∪ ω1 M ∪ · · · ∪ ωn M with {ω1 , . . . , ωn } a finite subset of Θ. To complete the proof, we just need to observe that since no abnormality in Θ is verified by any state in ΓrM , we have ΓrM ∩ (ω1 M ∪ · · · ∪ ωn M ) = ∅ as required.

8.

Final Remarks

The modal reconstruction of adaptive logic described in this paper is only partial. We can highlight a few valuable features and challenges of the broader project of trying to look at adaptive logic from the perspective of modal logic by explaining in which senses the present reconstruction is incomplete. (1) The present reconstruction is only partial because an axiomatisation (and matching completeness result) is missing. This is a non-trivial task that forces us to go beyond the basic preference language. (2) A further lacuna is the absence of a satisfactory way of coping with infinite premisesets. We have already seen that the failure of compactness blocks a detour via finite conjunctions of premises. When there is no finite subset Δ of some infinite premise-set Γ such that, for some adaptive strategy, Γ |∼x ϕ only if Δ |∼x ϕ, infinite conjunctions cannot be avoided if we want to express that ϕ is an adaptive consequence of Γ in terms of (ESI*), (MIN), or (R3). (3) Although abnormality models get the adaptive consequence relation right, these models fail to shed a light on the dynamic proof-theory that distinguishes adaptive logics from other logics for defeasible inference. This brings us to the final question of what we may gain from presenting adaptive logics as a modal logic. The specific preference models developed in the present paper allow us to present logics with a non-standard semantics and proof-theory in a different setting, and enables one to appreciate the specificity and richness of adaptive logics against (what many would consider) a more familiar background-formalism. This should facilitate the

P. Allo

dialogue with several other formalisms like the preference logics and conditional logics already mentioned in Sect. 3, but also, for instance, with the conditional doxastic models from [2]. A dialogue between different systems works in more than one way. We could, on the one hand, just use the common formalism to compare logics where the ordering of the states is syntactic as well as formal in the sense that it is determined by the formulae of a certain logical form that are verified by those states (adaptive logics) with logics where the ordering of the states obeys fewer constraints (doxastic logics, preference logic, conditional logic).9 On the other hand, we can use the common formalism to apply methods from one domain in another one. This can work in two directions. We can consider how updates would take place in abnormality models to model the external dynamics of adaptive logic as a kind of belief revision, but we can also import the reliability strategy to formulate a more cautious alternative to the standard definition of belief as truth in all most plausible states in an agent’s information partition,10 or consider doxastic logics that are based on some kind of abnormalityordering. Acknowledgements. The author is a postdoctoral Fellow of the Research Foundation – Flanders (FWO). Thanks are due to the organisers and audiences of the Logics for Dynamics of Information and Preferences Working Sessions in Amsterdam (2007), the Third Workshop in the Philosophy of Information in Ankara (2010), and the Logic, Reasoning and Rationality Conference in Ghent (2010).

9 For the intermediate situation where the ordering is syntactical, but not formal see [1] and [15]. For a criticism of logics based on non-formal orderings, see [9, 5.5]. 10 If we use the doxastic models from [2], both strategies still coincide. This is because doxastic plausibility-models are locally connected; for all states s, s that an agent considers possible, it holds that either s ≤ s or s ≤ s, and hence (what would correspond to) the reliable states are just the minimal states. Thus, rather than providing an additional type of belief, the move to pre-orders really leads to a splitting of notions. Note also that the sense in which the reliability strategy is more cautious than the minimality strategy is quite different from the sense in which, say, the notions of strong and safe belief are more cautious than plain belief. Since it all depends on how a pre-order is used to select states, any notion of belief could (provided that states are pre-ordered based on the formulas of a certain class they satisfy) be replaced or supplemented with a version that uses the reliability selection instead of the minimality selection.

Adaptive Logic as a Modal Logic

References [1] Avron, A., and I. Lev, A formula-preferential base for paraconsistent and plausible reasoning systems, Workshop on Inconsistency in Data and Knowledge (KRR4) Int. Joint Conf. on AI (IJCAI 2001), 2001. [2] Baltag, A., and S. Smets, A qualitative theory of dynamic interactive belief revision, in G. Bonanno, W. van der Hoek, and M. Woolridge (eds.), Logic and the Foundations of Decision Theory, Amsterdam University Press, Amsterdam, 2008, pp. 11–58. [3] Batens, D., Paraconsistent extensional propositional logics, Logique & Analyse 23(90–91):195–234, 1980. [4] Batens, D., Dynamic dialectical logics, in G. Priest, R. Routley, and J. Norman (eds.), Paraconsistent Logic—Essays on the inconsistent, Philosophia Verlag, M¨ unchen, 1989, pp. 187–217. [5] Batens, D., Inconsistency-adaptive logics, in E. Orlowska (ed.), Logic at Work— Essays dedicated to the Memory of Helena Rasiowa, Springer, Heidelberg, 1999, pp. 445–472. [6] Batens, D., A survey of inconsistency-adaptive logics, in D. Batens, C. Mortensen, G. Priest, and J. P. Van Bendegem (eds.), Frontiers of Paraconsistent Logic, Research-Studies Press, Baldock, 2000, pp. 49–73. [7] Batens, D., Minimally abnormal models in some adaptive logics, Synthese 125(1):5–18, 2000. [8] Batens, D., A universal logic approach to adaptive logics, Logica Universalis 1(1):221–242, 2007. [9] Batens, D., Adaptive Logics and Dynamic Proofs. Mastering the Dynamics of Reasoning, with Special Attention to Handling Inconsistency, 2012 (manuscript). [10] Blackburn, P., M. De Rijke, and Y. Venema, Modal Logic, Cambridge University Press, Cambridge, 2001. [11] Boutilier, C., Conditional logics of normality: a modal approach, Artificial Intelligence, 68:87–154, 1990. [12] Girard, P., Modal logic for belief and preference change, PhD thesis, Department of Philosophy, Stanford University, Stanford. ILLC Dissertation Series DS-2008-04, 2008. [13] Hughes, G. E., and M. J. Cresswell, A New Introduction to Modal Logic, Routledge, London, 1996. [14] Makinson, D., Five faces of minimality, Studia Logica 52(3):339–379, 1993. [15] Makinson, D., Bridges between classical and nonmonotonic logic, Logic Journal of the IGPL 11(1):69–96, 2003. [16] van Benthem, J., S. van Otterloo, and O. Roy, Preference logic, conditionals and solution concepts in games, in H. Lagerlund, S. Lindstr¨ om, and R. Sliwinski (eds.), Modality Matters: Twenty-Five Essays in Honour of Krister Segerberg, Uppsala Philosophical Studies, Uppsala, 2006, pp. 61–77.

P. Allo Patrick Allo Centre for Logic and Philosophy of Science Vrije Universiteit Brussel Pleinlaan 2 Brussels, Belgium [email protected]