On the Entailment Problem for a Logic of Typicality

1 Introduction

Propositional Typicality Logic (PTL) [Booth et al., 2012; 2013] is a recently proposed logic allowing for the representation of an explicit notion of typicality. It is obtained by enriching classical propositional logic with a typicality operator �, the intuition of which is to capture the most typical (or normal) situations in which a given sentence holds. PTL is characterised using a preferential semantics similar to that proposed by Shoham [1988] and extensively developed by Kraus et al. [1990] and by Lehmann and Magidor [1992].

In spite of the non-monotonic features introduced by the adoption of a preferential semantics for �, the obvious definition of entailment for PTL (based on Tarskian consequence) remains monotonic. Such a notion of entailment is inappropriate in non-monotonic contexts, in particular when reasoning about typicality, as is already clear from an enriched version of the classical Tweety example: If birds typically fly, and penguins are birds, we would expect to be able to conclude that typical penguins are typical birds, and therefore that typical penguins fly. Learning that penguins typically do not fly should lead us to conclude that penguins are not typical birds, and to retract the conclusions about typical penguins being typical birds, and about typical penguins flying.

In this paper, we investigate two semantic versions of entailment for PTL, constructed using two different forms of minimality. Both of these are based on the notion of Rational Closure as defined by Lehmann and Magidor [1992] for KLM-style conditionals in a propositional setting. We show that they can be viewed as distinct definitions of Rational Closure, equivalent with respect to the conditional language originally proposed by Kraus et al., but different in the PTL framework.

We study the different forms of entailment in an abstract formal setting, obtained by proposing a set of postulates that, at first glance, seem appropriate for any notion of entailment with regard to typicality. Our first important result is a negative one, though. It is an impossibility result proving that the set of postulates cannot all be satisfied simultaneously. A more detailed analysis of the result shows that, instead of being viewed as negative, this result should rather be interpreted as an indication that PTL allows for different types of entailment, corresponding to different subsets of the full set of postulates we provide. In line with this argument, we define two types of entailment for PTL corresponding to two subsets of the postulates, referred to as LM-entailment and PT-entailment. Our argument for more than one type of entailment for the same logic is in line with the proposal put forward by Lehmann [1995] in the context of entailment for conditional knowledge bases.

The remainder of the paper is structured as follows. Section 2 provides the background and notation for the rest of the work. In Section 3 we discuss the complexities surrounding a notion of entailment for PTL. In Section 4 we put forward our postulates and show the impossibility result. Section 5 outlines LM-entailment while Section 6 describes PTentailment. Section 7 addresses the implications of the impossibility result, making the case for two forms of PTL entailment. Section 8 concludes and discusses future work.

2 Background

Let P be a finite set of propositional atoms. We use p, q, . . . as meta-variables for atoms. Propositional sentences (and in later sections, sentences of the richer language we shall introduce below) are denoted by α, β, . . ., and are recursively defined in the usual way: α ::� p | α | α^α | J | K. All the other Boolean connectives (_, �, �, . . . ) are defined in terms of and ^ in the standard way. With L we denote the set of all propositional sentences.

We denote by U the set of all propositional valuations v : P �� t0, 1u. Sometimes we shall represent valuations as sets of literals (i.e., atoms or negated atoms), with each literal indicating the truth-value of the respective atom. Thus, for the logic generated from P � tp, qu, the valuation in which p is true and q is false will be represented as tp, qu. Satisfaction of a sentence α P L by v P U is defined in the usual truthfunctional way and is denoted by v , α.

2.1 KLM-Style Rational Conditionals

In the conditional logic investigated by Kraus et al. [1990], often referred to as the KLM approach, one is interested in (defeasible) conditionals of the form α |� β, read as "typically, if α, then β". For instance, if P � tb, f, pu, where b, f and p stand for, respectively, being a bird, being able to fly, and being a penguin, the following are examples of defeasible conditionals: b |� f (birds typically fly), p ^ b |� f (penguins that are birds typically do not fly).

The authors have put forward the following list of properties that the conditional |� ought to satisfy in order to be considered as appropriate in a non-monotonic setting:

A conditional satisfying such properties is called a preferential conditional. We can require |� to satisfy other properties as well, one of which is rational monotonicity:

A preferential conditional also satisfying (RM) is called a rational conditional.

The semantics of KLM-style rational conditionals is given by ordered structures called ranked interpretations [Lehmann and Magidor, 1992]:

Definition 1 A ranked interpretation R is a pair xV,�y, where V � U and � � V � V is a modular order over V.

Given a set X, � � X �X is modular if and only if there is a ranking function rk : X �� N s.t. for every x, y P X, x � y if and only if rkpxq � rkpyq. Note modular orders can be obtained from total preorders by imposing anti-symmetry.

Given R � xV,�y and α P L, we let JαK R :� tv P V | v , αu. In a ranked interpretation R, the intuition is that valuations lower down in the ordering are deemed more normal (or typical) than those higher up. Given α, β P L, we say R satisfies (is a ranked model of) the conditional α |� β (denoted R , α |� β) if and only if min�pJαK R q � JβK R . We say R is a ranked model of a set of conditionals C if and only if R , α |� β for every α |� β P C.

We can write a ranked interpretation R � xV, �y alternatively as a partition R � pL1, . . . , Lnq of V, where v � v1 if and only if v P Li, v1 P Lj and i � j.

For a better understanding of the reasons behind the aforementioned properties and the semantic constructions, the reader is referred to the work of Kraus et al. [1990; 1992].

2.2 Rational Closure

Given a set of conditionals C, reasoning in the KLM framework amounts to the derivation of new conditionals from C. Towards this end, Lehmann and Magidor [1992] proposed the rational closure construction. Their idea was to define a preference relation �LM over the set of possible ranked interpretations and then to base entailment on choosing only the most preferred, i.e., minimal, ranked models of C. The relation �LM can be described as follows. For any pair of ranked interpretations R1 � pL1, . . . , Lnq and R2 � pM1, . . . ,Mnq (we can assume they are of the same length, fill up the tail with H otherwise), we set:

This is not exactly the way it was defined by Lehmann and Magidor, but this representation can easily be derived from other work on rational closure such as that of Booth and Paris [1998] and Giordano et al. [2012]. The idea is that those ranked interpretations should be preferred in which as many valuations as possible are judged to be as plausible as the background knowledge C allows.

Clearly �LM forms a partial order over ranked interpretations. Lehmann and Magidor showed that for every set of conditionals C, there exists a unique �LM-minimum element Rrc pCq among all the ranked models of C. We will refer to this element as the LM-minimum. Then the rational closure of C is the set |�rc C :� tpα, βq | Rrc pCq , α |� βu. Rational closure is commonly viewed as the basic (although certainly not the only acceptable) form of entailment over propositional conditional knowledge bases, on which other, more venturous forms of entailment can be constructed. It is therefore an appropriate choice on which to base our investigations into versions of entailment for PTL.

2.3 Propositional Typicality Logic

PTL [Booth et al., 2012] is a logical formalism explicitly allowing for the representation of a notion of typicality. It extends classical propositional logic with a typicality operator �, the intuition of which is to capture the most typical (or normal) situations or worlds. Here we shall briefly present the main results about PTL relevant for our purposes.

The language of PTL, denoted by L� , is recursively defined by: α ::� p | α | α^α | J | K | �α. As before, p denotes an atom and all the other Boolean connectives are defined in terms of and ^.

Let P � tb, f, p, ou, where b, f and p are as before and o represents being an ostrich. The following are examples of L� -sentences: �b (being a typical bird), o� �b (ostriches are not typical birds), pp_oq � pb^� fq (being a penguin or an ostrich is equivalent to being a bird and being a typical non-flying creature).

Intuitively, a sentence of the form �α is understood to refer to the typical situations in which α holds. Note that α can itself be a �-sentence. The semantics of PTL is also in terms of ranked interpretations (see Definition 1). Satisfaction is defined inductively in the classical way, adding the following condition: v , �α iff v , α and there is no v1 � v s.t. v1 , α. That is, given R � xV,�y, J�αK R :�min�pJαK R q.

We say that R is a ranked model of α (denoted R , α) if JαK R � V. A PTL knowledge base is a finite set of sentences K � L� . We define ModpKq �def tR | R , � Ku.

A useful property of the typicality operator � is that it allows us to express KLM-style conditionals. That is, for every ranked interpretation R and every α, β P L, R , α |� β if and only if R , �α � β. The converse does not hold since it can be shown that there are L� -sentences that cannot be expressed as a set of KLM-style |�-statements on L.

3 The Entailment Problem for PTL

From the perspective of knowledge representation and reasoning (KR&R), a central issue is that of what it means for a PTL sentence to follow from a (finite) PTL knowledge base K. An obvious approach to the matter is to embrace the notion of entailment advocated by Tarski and largely adopted in the logic-based KR&R community.

Definition 2 (Ranked entailment) Let K � L� and α P L� . K ranked-entails α (noted K |ø0 α) iff ModpKq � Modpαq. Its associated consequence operator is defined by setting, for K � L� , Cn0pKq �def tα P L� | K |ø0 αu.

To see why this version of entailment is not appropriate in the context of PTL, consider the following definition of a conditional induced from a set of PTL sentences.

Definition 3 (Induced conditional relation) Let X � L� . Then |�X :� tpα, βq | α, β P L and �α � β P Xu.

It is worth investigating whether |�Cn0pKq is rational, i.e., whether it satisfies all the KLMproperties for rationality. The following proposition, which mimics a similar result by KLM in the propositional case, shows that this is not the case:

Proposition 1 (Booth et al. [2013]) |�Cn0pKq is a preferential conditional, but is not necessarily a rational conditional.

Hence, ranked consequence as defined above delivers an induced defeasible conditional that is preferential but that need not be rational. This forms an argument against ranked entailment being an appropriate notion of entailment for PTL.

One of the principles to give serious consideration when investigating PTL entailment is the presumption of typicality [Lehmann, 1995, p. 63]. Informally, this means that one should assume that every situation is as typical as possible. Sections 4 and 6 contain a formalisation of this principle. For now, we illustrate it with an example.

Example 1 Let K1 :� tp � b, �b � fu (penguins are birds, and typical birds fly). Given just this information about birds and penguins, it is reasonable to expect both �p � �b (typical penguins are typical birds) and therefore �p � f (typical penguins fly) to follow from K1. It is easy to see that with ranked entailment these requirements are not met.

Certainly we require PTL entailment to be defeasible, that is, the conclusions derived under the presumption of typicality can be retracted in case of new conflicting information. This is illustrated by the following example.

Example 2 Assume �p � �b and �p � f (somehow) could follow from K1 in Example 1, and assume we are informed that typical penguins do not fly. That is, let K2 :� K1 Y t�p � fu. While we want p � � b (penguins are not typical birds) to follow from K2, we do not want �p � f to follow from K2, which is not possible with ranked entailment.

4 Towards a Notion of Entailment for PTL

We have seen that ranked entailment has some drawbacks. Therefore, the question as to what logical consequence in PTL should mean remains mostly unanswered. In this section, we first specify and discuss a list of postulates that, at first glance, seem reasonable for an appropriate notion of entailment in PTL. In the subsequent section, we consider specific alternatives to ranked entailment and check them against our postulates.

We start by introducing some notation. With |ø? � PpL� q � L� , we denote any entailment relation on the language of PTL. Given an entailment relation |ø?, its associated consequence operator is defined in the usual way by setting, for each K � L� , Cn?pKq �def tα P L� | K |ø? αu.

The obvious starting point is to consider some of the basic properties of classical consequence operators.

Ranked entailment, as defined in Section 3, satisfies Properties P1-P2. However, Cn0p�q, the associated consequence relation of Ranked entailment, also satisfies the classical property of Monotonicity: If K � K1 , then Cn0pKq � Cn0pK1 q. As seen in Example 1, this is a property that we do not want Cn?p�q to satisfy (certainly not in general).

So, we require Cn?p�q to be a non-monotonic consequence operator. Traditionally, this amounts to requiring Cn?p�q to satisfy the following two properties:

Ampliativeness says that Cn?p�q should be more venturous than its underlying ranked entailment. In Example 1, we have �p � f R Cn0pK1q, i.e., it does not follow that "typical penguins fly". However, given the information in K1, a case can be made for having �p � f as a plausible (though provisional) conclusion, e.g. in the absence of information to the contrary.

Defeasibility specifies that Cn?p�q should be flexible enough to disallow previously derived conclusions in the light of new (possibly conflicting) information. In Example 1, assuming �p � f P Cn?pK1q is the case, then �p � f should no longer be concluded if �p � f is added to K1.

Similarly to KLM in the propositional case, we would ideally like the defeasible conditional induced by Cn?pKq (see Definition 3) to satisfy all the rationality properties:

P5 |�Cn?pKq is a rational conditional relation on L (Conditional Rationality)

It is easy to see that P5 implies P4. The following 'single model' property can be straightforwardly shown to be a strengthening of P5:

P6 For every K � L� , there is a ranked interpretation R s.t. for all α P L� , α P Cn?pKq iff R , α (Single Model)

In the special case when K is a (propositional) conditional knowledge base (i.e., when K is of the form t�α � β | α, β P Lu), the result should coincide with Lehmann and Magidor's definition of rational closure:

P7 If K is a conditional knowledge base, then |�Cn?pKq�|�rc K (Extends Rational Closure)

The following property was shown by Lehmann and Magidor to be satisfied by the rational closure for conditional knowledge bases.

• P8 Let α P L. Then α P Cn?pKq if and only if α P Cn0pKq (Strict Entailment)

It states that Cn?p�q should coincide with ranked entailment for those sentences not involving typicality. The motivation for Strict Entailment is that ranked entailment, being Tarskian in nature, already deals adequately with such sentences.

We are also interested in a couple of progressively weaker versions of Strict Entailment. The first restricts it to hold only when K is a conditional knowledge base.

• P9 Let K be a conditional knowledge base and α P L. Then α P Cn?pKq if and only if α P Cn0pKq (Conditional Strict Entailment)

Note that P7 implies both P4 and P9. The latter requires entailment for PTL to coincide with classical propositional entailment in the case of propositional knowledge bases.

P91 Let K � L and α P L. Then α P Cn?pKq iff K entails α in classical propositional logic. (Classical Entailment)

Since for every K Y tαu � L, K entails α in classical propositional logic if and only if α P Cn0pKq, and any α P L is equivalent � α�K, P91 is indeed a weakening of P9.

Finally, we consider another property shown by Lehmann and Magidor to be satisfied by the rational closure for conditional knowledge bases.

Considering the 'if' part of P10, any appropriate entailment relation for PTL should go beyond ranked entailment in terms of the consequences it produces. Conversely, for the 'only if' part, consequences of the form �J � α are those for which α holds in the most typical situations, and for those cases, ranked entailment is sufficient. Put another way, it is only when dealing with atypical situations that ranked entailment, being Tarskian in nature, is not always sufficient.

Although these postulates all seem reasonable on their own, it turns out that they cannot all be satisfied simultaneously. In fact, this impossibility result already holds for a strict subset of the postulates.

Theorem 1 There is no PTL consequence operator Cn?p�q satisfying all of P1, P6, P8 and P10.

Proof: (Outline) Assume Cn?p�q satisfies the given properties. Let K � t�J � p, � p � �qu. By Strict Entailment (P8), p R Cn?pKq (because of e.g. the 2-layered ranked model pttp, quu, tt p, quuq of K). By Typical Entailment (P10), �J � q R Cn?pKq (because of e.g. the 1-layered ranked model pttp, qu, tp, quuq of K). By Inclusion (P1), t�J� p, � p � �qu � Cn?pKq. Then by Single Model (P6), there is a ranked model R such that R . p, R . �J � q, R , �J � p and R , � p � �q, but no such model can possibly be constructed.

While, at first glance, this seems to be a negative result, our contention is that it should be interpreted as an indication that a logic as expressive as PTL admits more than one form of entailment. We elaborate directly on this point in Section 7, and indirectly in Sections 5 and 6, where we define and discuss two instances of entailment for PTL.

5 LM-Entailment

We now come to our first construction of an entailment relation in PTL. The idea is to try to lift the rational closure construction from conditional knowledge bases to arbitrary knowledge bases in L� . We first observe that there is nothing to stop us from using the preference relation �LM (see Section 2.2) to compare ranked interpretations of any PTL knowledge base K. The question is, does there always exist a unique LM-minimum element of the ranked models of K, as there does in the restricted conditional case? And if so, how can we construct it? We now answer these questions.

We assume as input a PTL knowledge base K � tα1, . . . , αnu, where each sentence αj is in normal form:

Definition 4 (Normal form) α P L� is in normal form iff it is of the form �i/t �θi � pφ _ �i/s �ψiq, where t, s ¥ 0 and the θi, φ and ψi are all purely propositional sentences.

It can be shown that for every sentence α in L� there is a (finite) set of sentences S in normal form such that Modpαq � Modp� Sq. That is, the normal form is complete for L� . For any ranked interpretation R � xV, �y and S � V, we define R � S (the restriction of R to S) as xV X S, � XpS � Sqy.

We construct a sequence pR0,R1, . . .q of ranked interpretations as follows, where Ri � xU, �iy (i.e., the set of valuations V is always the full set of all valuations):

Step 1 Initialise �0:� H (start with an initial ranked interpretation in which all valuations are equally preferred.)

• Step 2 Si�1 :� JKK Ri (separate the valuations which satisfy K w.r.t. the current ranked interpretation Ri from those that do not.)

Step 3 If Si�1 � Si then STOP and return R� pKq � Ri � Si�1 (if the division is the same as in the previous round then eliminate completely from the current ranked interpretation those valuations that do not satisfy K w.r.t. Ri and return the interpretation that remains.)

Step 4 Otherwise �i�1:��i YpSi�1 � Sc i�1 q, i :� i � 1 and go to Step 2 (otherwise create a new ranked interpretation Ri�1 by making every valuation not in Si�1 less plausible than every valuation in Si�1. Note that Sc here denotes UzS.)

Example 3 Let us assume, for the sake of the example, that we are only talking about birds. Let K :� t�J � p p ^ paq, �p � � f, �pa � �fu (the most typical things are neither penguins nor parrots, typical penguins are typical non-flying birds, and typical parrots are typical flying birds).

The procedure initialises with �0� H. The only valuations that satisfy all three sentences w.r.t. R0 are those satisfying both p and pa. Thus S1 :� JKK R0 � tt p, pa, fu, t p, pa, fuu and so we obtainR1 by setting �1 to be the 2-layer modular order with S1 as the lower layer. Note that J� fK R1 � tt p, pa, fuu and J�f K R1 � tt p, pa, fuu, so we can see that none of the

valuations in Sc 1 is able to satisfy either �p � � f or �pa � �f w.r.t. R1. As a consequence, S2 :� JKK R1 � S1 and so the procedure terminates here with R� pKq � R1 � S2. That is, R� pKq is the ranked interpretation consisting of just a single layer containing the valuations t p, pa, fu and t p, pa, fu.

We now need to show: (i) the algorithm always terminates; (ii) it returns a ranked model of K, and (iii) for any other ranked model R of K, we have R� pKq �LM R. We know the following about (i) and (ii):

Lemma 1 Assuming each sentence in K is in normal form, the following hold for each i ¥ 0:

• (i) Si � Si�1, i.e., JKK Ri�1 � JKK Ri ,

(iii) Ri�1 is a ranked interpretation, i.e., �i�1 is modular.

• (ii) For all v1, v2 P U, if v1 �i v2 then v1 P JKK Ri ,

From (i) above we know the algorithm terminates, since it generates a sequence of ranked (by (iii)) interpretations in which the set of valuations satisfying K increases monotonically from one ranked interpretation to the next. Since each of these is finite, the stopping criterion in Step 3 of the algorithm is guaranteed to occur eventually.

To show that the algorithm returns a ranked model of K it suffices to show the following.

Lemma 2 Assuming each sentence in K is in normal form, for each i ¥ 0, Ri � Si�1 is a model of K.

So at each stage of the algorithm, the current ranked interpretation, when those valuations not satisfying K are excluded, forms a ranked model of K. Since the output R� pKq takes precisely this form we have the following result.

Proposition 2 Assuming each sentence in K is in normal form, we have R� pKq , � K.

Next we want to show that for any other ranked model R of K, we have R� pKq �LM R. Let R� pKq :� pS1, . . . , Smq and let R :� pT1, . . . , Tmq be any other ranked model of K. If one of the two sequences is shorter than the other, we simply fill its tail with an appropriate number of empty sets to ensure the sequences have equal length.

Lemma 3 Let i ¥ 1. If Tj � Sj for all j � i then Ti � Si.

From this lemma we can state:

Proposition 3 Assume each sentence in K is in normal form and let R be a ranked model of K. Then R� pKq �LM R.

Given this, we define LM-entailment, denoted by |ø�LM , as follows: K |ø�LM α if and only if R� pKq , α. Its corresponding consequence operator is defined as CnLMpKq �def tα P L� | R� pKq , αu. The next result outlines which properties from the previous section are satisfied by CnLMp�q.

Theorem 2 CnLMp�q satisfies P1-7 , P9, P10, but not P8.

Thus the only property that fails is Strict Entailment. This can be seen in Example 3. There we have p P CnLMpKq (there is no penguin) because p holds in both of the valuations occurring in R� pKq. But p R Cn0pKq because there does exist a ranked model R of K for which JpK R � H, for instance the model R2 appearing in Example 4 below. Thus LM-entailment forces us, unjustifiably, to infer p fromK.

In summary then, LM-entailment satisfies all our postulates, except for Strict Entailment (P8). Lest this be seen as a negative result, bear in mind that LM-entailment satisfies Conditional Strict Entailment (P9), the weakened version of Strict Entailment, and therefore also Classical Entailment.

In the next section we turn to a form of entailment satisfying Strict Entailment, but at the price of having to forego Conditional Rationality, and therefore the Single Model postulate as well.

6 PT-Entailment

In this section we consider another option for entailment based on a version of minimality, and derived from the characterisation of rational closure by Giordano et al. [2012]. The general idea is to respect the presumption of typicality. Semantically, given the ranked models of a given K, this corresponds to considering only those models in which every valuation is taken as typical as possible, that is, it is 'pushed downward' in the interpretation as much as possible, modulo the satisfaction of K.

In order to identify the interpretations that can be interesting for the definition of a notion of entailment, we introduce a preference relation �PT between the ranked interpretations that follows directly from the presumption of typicality. To do that, we need a way to compare the relative positions of the valuations between the models of a knowledge base.

Definition 5 (Height function) For a ranked interpretation R � pL1, . . . ,Lnq and v P V, the height hRpvq of v corresponds to the number of the layer in R in which v is positioned, or to 8, if it is not in the interpretation. That is hRpvq � i if v P Li, for 0 / i / n, hRpvq �8 otherwise.

The lower the height of a valuation in an interpretation, the more typical such a valuation is considered in the ranked interpretation, while the height value is 8 if the valuation does not appear in the interpretation at all. Using the height of a valuation, we can define a preorder over the interpretations.

Definition 6 (Relation �PT) For two ranked interpretations R � xVR,�Ry and R1 � xVR1 ,�R1y, R �PT R1 if and only if for every w P U, hRpwq / hR1 pwq. R �PT R1 if and only if R �PT R1 and not R1�PTR.

It is easy to check that �PT is a preorder. Consistent with the presumption of typicality, we choose the models of K in which the valuations are presumed to be as typical as possible, that is, min�PT pModpKqq. Then, K entails α if and only if α holds in all the (preferred) models in min�PT pModpKqq.

If we consider knowledge bases composed only of classical non-monotonic conditionals α |� β, it corresponds exactly to LM-minimality as defined in the previous sections [Giordano et al., 2012]. However, due to the expressivity of our language, we obtain the surprising result that the two semantic constructions are not equivalent anymore. Moreover, in the present context, this notion of minimality can give back a number of minimal models, as the following example shows.

Note that R1 is the LM-minimum of K. In fact it is easy to check from the characterisation of rational closure in Section 3 and Definition 6 that the LM-minimum of K is always in min�PT pModpKqq.

Proposition 4 For every knowledge base K, the LMminimum of K is in min�PT pModpKqq.

Given this, we define PT-entailment, denoted by |ø�PT , as follows: K |ø�PT α if and only if min�PT pModpKqq � Modpαq. Its corresponding consequence operator CnPTp�q is inferentially weaker than CnLMp�q, since it is defined on a possibly larger set of models.

Proposition 5 CnPTp�q satisfies P1-4, P7, and P8-P10.

Unfortunately, Conditional Rationality (P5) is not valid and therefore, neither is the Single Model postulate.

Theorem 3 There is some K such that the conditional induced by CnPTpKq is not a rational conditional.

To see this, consider Example 4: we have � p � q P CnPTpKq (typical non-penguins are not parrots-since we know the most typical things are not parrots), but neither � p � t P CnPTpKq, nor �p p ^ tq � q P CnPTpKq. On the other hand, unlike with CnLMp�q, p R CnPTpKq.

7 Making Sense of the Impossibility Result

Theorem 1 in Section 4 shows that there is no PTL consequence operator satisfying all of our postulates-more specifically, none satisfying P1, P6, P8, and P10. This raises the important question of which of these postulates ought to be foregone in the search for an appropriate form of PTL entailment. In trying to find an answer to this question, it is useful to consider the two forms of entailment we proposed in the previous sections. The answer seems to be that it makes sense to consider two forms of entailment for PTL, represented here by LM-entailment and PT-entailment. In essence, it comes down to a choice between having a form of entailment that satisfies Strict Entailment (PT-entailment), and one that satisfies the Single Model postulate and Conditional Rationality, i.e., is based on a rational conditional (LM-entailment).

The advantage of LM-entailment is that it satisfies all postulates except for Strict Entailment, which includes not only Single Model and Conditional Rationality, but also Conditional Strict Entailment and Classical Entailment, the weakened versions of Strict Entailment. On the other hand, the argument for PT-entailment is that the Single Model property is too restrictive in the context of full PTL, and ought to be dropped. That is, in a logic as expressive as PTL in which there are not any restrictions on the typicality operator, any form of entailment based on minimality, and adhering to the presumption of typicality, as outlined in Section 6, is likely to violate the Single Model property.

The point of view that different forms of entailment can be appropriate in enriched versions of propositional logic, particularly enriched versions dealing with aspects of typicality, is not surprising, nor new. Lehmann [1995], makes the case for two forms of entailment for the conditional logic discussed in Section 2.1 on which PTL is based. He draws a distinction between prototypical reasoning, corresponding to Rational closure as discussed in Section 2.2, and presumptive reasoning. The details of the differences between prototypical and presumptive reasoning is not that important for our purposes here. The important point is that differences in context will determine which form of entailment is appropriate. It is our contention that the same principle applies to the differences between LM-entailment and PT-entailment.

8 Conclusion

The focus of this paper is an investigation into the entailment problem for the logic PTL. We approached the problem from two angles: an abstract formal perspective, in which a set of appropriate postulates were presented and discussed, and a constructive perspective, in which two specific entailment relations were defined and studied. The primary conclusion to be drawn from this investigation is that a logic as expressive as PTL supports more than one form of entailment. This conclusion is supported from the abstract perspective via an impossibility result, as well as through the constructive approach via the definition of two distinct types of PTL entailment. While both forms of entailment are generalisations of rational closure, only one, LM-entailment, retains all the rationality properties associated with Rational closure, formalised as the Conditional Rationality postulate (P5). However, it does not satisfy Strict Entailment (P8), a postulate which requires an entailment relation to remain Tarskian for conclusions not involving typicality, although it satisfies weakened versions of Strict Entailment (P9 and P91 ). On the other hand, the other form of entailment we studied, PTentailment, satisfies P8, but not Conditional Rationality, and therefore not the Single Model postulate (P6) either.

The framework of Booth et al. [2012; 2013] is, to the best of our knowledge, the first attempt to introduce a full-fledged typicality operator into propositional logic. In terms of other related work, the closest we are aware of is the restricted form of typicality for description logics by Giordano et al. [2009]. However, a consequence of their restricted use of typicality is that a propositional version of their logic would correspond to a KLM-style conditional logic in which rational closure behaves well, and which is much less expressive than PTL.

Britz et al. [2009] and Giordano et al. [2009] have investigated the connection between the KLM approach and G¨odelL¨ob modal logic, which is closely related to PTL. Exploiting this connection should deliver an axiomatisation of an inference relation corresponding to ranked entailment, but it does not seem useful for modelling entailment relations based on minimisation as LM- and PT-entailment.

For future work, an obvious open question is whether our conjecture, that the subsets of postulates satisfied by LMentailment and PT-entailment respectively provide appropriate abstract formalisations of two distinct forms of PTL entailment, can be formalised through representation theorems. From a computational perspective, it is worth investigating whether, as is the case for rational closure for conditional logics, the computation of (the different forms of) PTL entailment can be reduced to a series of classical entailment checks.

Our results in the propositional setting pave the way for an investigation of appropriate forms of entailment in other, more expressive, preferential approaches, such as preferential description logics [Britz et al., 2011b; 2013; Giordano et al., 2013] and modal logics of defeasibility [Britz et al., 2011a; Britz and Varzinczak, 2013]. The move to logics with more structure is of a challenging nature, and a simple rephrasing of our approach to these logics may not deliver the expected results. We are currently investigating these issues.

Acknowledgments

Richard Booth's contribution was mostly written while visiting the Individual and Collective Reasoning group at the University of Luxembourg. Part of the work of Giovanni Casini has been supported by the Fonds National de la Recherche, Luxembourg, and cofunded by the Marie Curie Actions of the European Commission (FP7-COFUND) (AFR/9181001). Ivan Varzinczak has been supported in part by the Brazilian National Council for Scientific and Technological Development (CNPq) under grant number 302002/2014-6, and by the National Research Foundation of South Africa (UID 85482, IFR2011032700018). A preliminary version of this work was presented at Commonsense [Booth et al., 2015].