# the_logic_of_qualitative_probability__8980871c.pdf

The Logic of Qualitative Probability

James P. Delgrande School of Computing Science Simon Fraser University Burnaby, B.C., V5A 1S6 Canada jim@cs.sfu.ca

Bryan Renne Vancouver, B.C., Canada bryan@renne.org

In this paper we present a theory of qualitative probability. Work in the area goes back at least to de Finetti. The usual approach is to specify a binary operator with φ ψ having the intended interpretation that φ is not more probable than ψ. We generalise these approaches by extending the domain of the operator from the set of events to the set of finite sequences of events. If Φ and Ψ are finite sequences of events, Φ Ψ has the intended interpretation that the summed probabilities of the elements of Φ is not greater than the sum of those of Ψ. We provide a sound and complete axiomatisation for this operator over finite outcome sets, and show that this theory is sufficiently powerful to capture the results of axiomatic probability theory. We argue that our approach is simpler and more perspicuous than previous accounts. As well, we prove that our approach generalises the two major accounts for finite outcome sets.

1 Introduction

In qualitative probabilistic reasoning, one may assert that some event is more probable than another without specifying the exact numerical probabilities of the events in question. Consequently, this approach offers a pragmatic, intuitive, and practical counterpoint to classical probability theory, both in commonsense reasoning in particular, and in Artificial Intelligence in general. While classical probability theory provides a formal framework for reasoning under uncertainty, in some cases it may be too fine-grained. Assigning exact numerical probabilities is often difficult or impossible, combining probabilities can be complex, and often one simply wants to compare the likelihood of two events without having to give exact probabilities.1 As well, a full account of qualitative probability may shed light on the division in AI (and perhaps science as a whole) between what Kyburg [1994] calls the probabilist and the logicist way of thinking about the world; this is

1For example, without using exact probabilities, someone might believe that her second-choice candidate is more likely to win than her first-choice candidate and cast her vote accordingly.

the difference between making hedged claims (as with probabilistic reasoning) and making categorical claims in a hedged way (as in Nonmonotonic Logic).2 The central issue is to provide a satisfactory formal characterisation of qualitative probability. More precisely, the issue is to specify the principles that a binary sentential operator must satisfy in order to exactly capture the intended interpretation is no more probable than . This has been a surprisingly difficult and subtle problem. Work in this area goes back at least to de Finetti [1937; 1951] who provided a number of principles and conjectured that they were sufficient. While obviously necessary, Kraft et al. [1959] showed that they were not sufficient and gave a condition that must be added to obtain a necessary and sufficient set of principles. A shorter version of their result was given by Scott [1964]. Building on Scott s work, Segerberg [1971] provided an axiomatisation of a Boolean-complete theory with the operator that was sound and complete for the probability interpretation with events drawn from a possibly infinite outcome set. G ardenfors [1975] provided a simplified account for finite outcome sets. A drawback to these approaches is that the condition identified by Kraft et al. is complicated and non-finite. In the case of Segerberg s and G ardenfors axiomatisations, this condition is represented by a countable sequence of axiom schemes in which scheme size (number of symbols) grows exponentially with a scheme s position in the sequence. In later work on quantitative probabilistic reasoning, Fagin et al. [1990] avoid the scheme by adopting an alternative scheme (Ineq) that calls for all instances of valid formulas about linear inequalities. This powerful principle, which is not stated in the language of the logic, assumes numbers and arithmetic, and encompasses infinitely many principles of inequality involving finite sums of unbounded length. In this paper, which is part of a renewed interest in logics of qualitative and quantitative probability [Halpern, 2003; Narens, 2007; Holliday and Icard, 2013; van Eijck and Renne, 2014], we address these problems and generalise previous approaches by extending the domain of the operator from the set of events to the set of finite sequences of events.

2In fact, an original motivation for this work is the following interpretation for weak or nonmonotonic conditionals: φ ψ means that φ ψ is more probable than φ ψ. This is the fragment of our logic consisting of the derivable statements having the form φ ψ φ ψ.

Proceedings of the Twenty-Fourth International Joint Conference on Artificial Intelligence (IJCAI 2015)

We do this both for perspicuity (simpler axioms) and expressiveness (our language is more expressive). If Φ and Ψ are finite sequences of events, Φ Ψ has the intended interpretation that the summed probabilities of the elements of Φ is not greater than the summed probabilities of the events of Ψ. We provide a sound and complete axiomatisation for this extended notion of qualitative probabilistic comparison over finite outcome sets. Our approach offers several advantages over previous work. First, we claim that our axiomatisation is simpler and more perspicuous than previous accounts. In particular, unlike Segerberg s and G ardenfors axiomatisations, ours is schematically finite and it avoids the use of exponentiallylarge schemes. Unlike Fagin et al., we do not require a scheme like their (Ineq) that calls for all valid formulas about linear inequalities; instead we axiomatise this set of formulas from first principles. Further, our approach is sufficiently expressive to capture the results of axiomatic probability theory, as expressed by the Kolmogorov axioms. (For example, the relation P(φ) + P(ψ) = P(φ ψ) + P(φ ψ) is a theorem of our system, expressed as φ ψ (φ ψ) (φ ψ).) As well, our framework expressively and axiomatically generalises the two major approaches for finite outcome sets due to G ardenfors and Fagin et al. An extension to infinite outcome sets (and a more complete comparison to Segerberg s approach) is left for future work. The next section gives some background, while Section 3 presents our approach. Section 4 relates our approach to those of G ardenfors and Fagin et al. and provides a preliminary comparison with Segerberg s work. We then conclude, commenting on future work.

2 Background Consider the problem of specifying a relation between formulas, where φ ψ is to have the interpretation that φ is not more probable than ψ. That is, the problem is to provide conditions on such that for a collection of such assertions there is guaranteed to be a realizing probability measure P( ) on formulas; this means that for all formulas φ and ψ,

φ ψ iff P(φ) P(ψ).

De Finetti [1937; 1951] conjectured that the following conditions were necessary and sufficient: for each φ, ψ, and γ, 1. ψ; 2. φ ψ and ψ γ implies φ γ; 3. φ ψ or ψ φ; 4. if φ γ and ψ γ are each inconsistent, then φ ψ iff ψ γ φ γ. While these conditions are clearly sound, [Kraft et al., 1959] shows that they are not complete. For our purposes, their counterexample is most easily phrased in terms of possible worlds. Let W = {w1, w2, w3, w4, w5} be a set of possible worlds; a set of worlds can be thought of as representing a proposition. Consider the relations:

{w3} {w1, w2}, {w2, w4} {w1, w3}, {w1, w5} {w2, w3}, {w1, w2, w3} {w4, w5}.

Kraft et al. show that this set of relations can be extended to an ordering on all subsets of W that satisfies de Finetti s conditions but for which there does not exist a realizing probability measure. (In the counterexample, an assignment of probability of .2 to each world is easily seen to be inconsistent.) Kraft et al. also provide criteria so as to ensure a realizing probability measure always exists. Scott [1964] reformulated and simplified these results in an algebraic form. Segerberg [1971] developed a logic of qualitative probability that made use of Scott s results; this logic had a binary operator and a unary modal operator of necessity. G ardenfors [1975] subsequently simplified Segerberg s approach by restricting to finite sets and defining necessity by φ .= (1 φ). Segerberg s and G ardenfors axiomatisations both use the following schematic abbreviation:

φ1, . . . φm Eψ1, . . . ψm .= (C0 Cm), (1)

where m 1 and for 0 i m, the scheme Ci is the disjunction of all conjunctions

δ1φ1 δmφm ϵ1ψ1 ϵmψm,

where exactly i of the δ s and i of the ϵ s are the negation sign and the rest are the empty string. The overall import is that φ1, . . . φm Eψ1, . . . ψm, which we write as (φi)m i=1E(ψi)m i=1, says, At every probabilistically possible outcome, the number of true φ s is equal to the number of true ψ s. Notice that the size of the scheme abbreviated by (φi)m i=1E(ψi)m i=1 is Ω(2m).3 G ardenfors gives the following axiomatisation for his logic QP of qualitative probability:

(PC) All instances of propositional tautologies

(A0) (φ1 φ2) (ψ1 ψ2) ((φ1 ψ1) (φ2 ψ2))

(A2) (φ ψ) (ψ φ)

(A4)m (φi)m i=1E(ψi)m i=1 Vm 1 k=1 (φk ψk) (ψm φm)

(MP) From φ ψ and φ infer ψ

(Nec) From φ infer φ

This logic is shown to be sound and complete with respect to finite possible worlds models in which a probability measure is associated with each world. The scheme (A4)m is non-ideal for several reasons. First, it is difficult to understand (Segerberg calls it formidable ). Second, (A4)m specifies infinitely many axiom schemes, one for each positive integer m; consequently, the above axiomatisation for QP is not schematically finite. Third, the size of (i.e., number of symbols in) the scheme abbreviated by (A4)m is Ω(2m) (i.e., at least exponential). A different (and independent) approach to reasoning about probability is the theory AXmeas of quantitative probability of [Fagin et al., 1990]. Their language permits Boolean combinations of linear inequalities of the form a b1w(φ1)+ + bnw(φn), where a and the bi s are integers and the φi s do not

3Ci has m i 2 disjuncts, and Pm i=0 m i 2 Pm i=0 m i = 2m.

contain s or w(χ) s. The expression w(φ) is mapped in the semantics to a real number called the weight of φ. This ends up being the probability of event φ. The axiomatisation of AXmeas is given as follows:

(PC) All instances of propositional tautologies

(Ineq) All instances of valid formulas about linear inequalities4

(W1) 0 w(φ)

(W2) 1 w(1)

(W3) w(φ ψ) + w(φ ψ) w(φ)

(W4) w(φ) w(ψ), where φ ψ is a tautology

(MP) From φ ψ and φ infer ψ

An (Ineq)-derivable formula is a Boolean combination of valid inequalities b a1w(φ1) + + anw(φn) consisting of integers b, a1, . . . , an and real numbers w(φ1), . . . , w(φn). However, as per the other axioms, each w(φi) ends up being a probability. (Ineq), which is not stated in the language of the logic, is a powerful scheme. It assumes numbers and arithmetic, and it encompasses infinitely many principles of inequality involving finite sums of unbounded length. Although a decision procedure can effectively compute the principles encompassed in (Ineq), it is our view that this scheme assumes too much. In particular, it would be preferable to replace (Ineq) by some finite set of schemes in the language of the logic such that every (Ineq)-principle is derivable.

3 A Logic of Qualitative Probability

We now specify the syntax and semantics of our theory LQP, the Logic of Qualitative Probability.

3.1 Language and Semantics

The central intuition and innovation of our approach is that is most profitably regarded not as a binary operator on formulas, but rather as an operator on finite sequences of formulas.5 We use as suggestive notation for separating formulas in a sequence. Thus our goal is to use

φ1 φn ψ1 φm (2)

in our language to assert that Pn i=1 P(φi) Pm i=1 P(ψi). To be clear, as in (2) is strictly speaking a n,m-ary operator. There is nothing that a priori lets us interpret as any sort of a sum; rather we later axiomatically characterise such formulas so that can be consistently interpreted as a summing operator.

4This means: all members of the smallest set of formulas that (1) is closed under Classical Propositional Logic-derivable Boolean combinations and (2) contains for each n 1 all formulas of the form b a1w(φ1) + + anw(φn) for which the inequality b a1x1 + + anxn holds for all real numbers x1, . . . , xn. 5It would be possible to use multisets instead of sequences; however, sets cannot be used because repetition is meaningful.

Definition 3.1 (Language LLQP). Fix a nonempty set P of propositional atoms. The language LLQP consists of the formulas φ and the sequences Φ formed by the following recursion:

φ ::= p | φ | (φ φ) | (Φ Φ) p P Φ ::= φ | φ Φ

Formulas occurring in sequences are called elements, and expressions Φ Ψ are called inequalities. We use the symbols φ, ψ, and χ, possibly with subscripts or superscripts, as metavariables for formulas. We use Φ, Ψ, and similarly for sequences. Sequences may be written using indexed prefix notation so that, for example, L3 i=1 φi denotes φ1 φ2 φ3. We may write φ Φ to indicate that φ occurs as an element of Φ. We will often drop parentheses when no ambiguity of meaning results; hence we might write simply φ1 φ2 φ3. We use the standard definitions for the Boolean connectives , , and . We define 1 to be some arbitrary fixed tautology, and define 0 as 1. φ ψ abbreviates (φ ψ) (ψ φ), and φ ψ abbreviates (φ ψ) (ψ φ). Last, we define φ to be (1 φ). As described, the intuitive meaning of the formula Φ Ψ is that the sum of the probability of the elements on the left of the inequality is less than or equal that on the right. Note that this means that either side of the inequality may exceed 1; for example, a theorem in our approach is 1 1 1. In Section 3.3 we will show how such inequalities enable us to capture aspects of quantitative probability. We now consider the semantic theory underlying our approach. We restrict attention to models based on finite outcome spaces; such structures are well-known in the literature (see, e.g., [Halpern, 2003]).

Definition 3.2 (Model). A model is a structure M = (W, P, V ) where:

1. W is a finite nonempty set (of possible worlds).

2. P maps each world w W to a probability measure Pw : (Ωw) [0, 1] on a nonempty set Ωw W of outcomes.

3. V : W (P) is a propositional valuation assigning to each world w W a set V (w) of propositional letters taken to be true at w.

A pointed model is a pair (M, w) consisting of a model M and a world w in M that we call the point.

Definition 3.3 (Satisfaction, Validity). The semantic function J K : LLQP (W) and the satisfaction relation |= between pointed models and LLQP-formulas are defined as follows.

JφKM .= {w W | M, w |= φ}, where φ LLQP.

JφKw M .= JφKM Ωw.

1. M, w |= p iff p V (w), where p P.

2. M, w |= φ iff M, w |= φ.

3. M, w |= φ ψ iff M, w |= φ or M, w |= ψ.

4. M, w |= Φ Ψ iff P φ Φ Pw(JφKw M) P ψ Ψ Pw(JψKw M).

We say that φ is valid in M, written M |= φ, to mean that M, w |= φ for each world w M. We say that φ is valid, written |= φ, to mean that M |= φ for every model M.

3.2 Axiomatic Theory

LQP is axiomatised as follows:

(PC) All instances of propositional tautologies6

(Tran) (Φ Ψ) ((Ψ ) (Φ ))

(Tot) (Φ Ψ) (Ψ Φ)

(Sub) (φ1 φ2) (ψ1 ψ2) ((φ1 Φ ψ1 Ψ) (φ2 Φ ψ2 Ψ))

(Com) (Φ1 Φ2 Ψ) (Φ2 Φ1 Ψ) (Φ Ψ1 Ψ2) (Φ Ψ2 Ψ1)

(Add) (Φ1 Ψ1) (Φ2 Ψ2) (Φ1 Φ2 Ψ1 Ψ2)

(Succ) (Φ 1 Ψ 1) (Φ Ψ)

(K3) (φ ψ) (φ ψ φ ψ)

(MP) From φ ψ and φ infer ψ

(Nec) From φ infer φ

(Triv) avoids triviality, while (Tran) and (Tot) give properties of . (Sub) is substitution of necessary equivalents, while (Com) expresses that sequences are commutative. (Add) allows one to concatenate items to a sequence, while (Succ) allows one to remove 1 from both sides of . (K1) and (K3) correspond to the first and third Kolmogorov axioms; the second Kolmogorov axiom, which essentially says that a valid proposition has probability 1, is expressed by (Nec) and the abbreviation φ .= (1 φ). (PC) and (MP) are standard. We can derive a rich set of results in our theory. The next theorem pertains to properties of sequences.

Theorem 3.4 (Sequences). LQP derives:

1. Principle (Ref): Φ Φ.

2. Substitution principle for length-1 sequences: (φ1 φ2) (ψ1 ψ2) ((φ1 ψ1) (φ2 ψ2)).

3. Replacement principles: (Φ1 Φ2) ((Φ1 Φ Ψ) (Φ2 Φ Ψ)), (Ψ1 Ψ2) ((Φ Ψ1 Ψ) (Φ Ψ2 Ψ)).

4. Cancellation principle: (Φ Φ Φ Ψ) (Φ Ψ).

5. Ordering principle: (Φ1 Ψ1) ((Ψ1 Ψ2 Φ1 Φ2) (Ψ2 Φ2)).

6We use (PC) for brevity. (PC) can be replaced by a finite number of axiom schemes, as is explained in any logic text.

(Ref) is a simple consequence of (Tot). Item 2 is different than (Sub) because our language assumes nonempty sequences. Item 3 extends substitution to equivalence under . Item 4 extends (Succ) to arbitrary sequences. The Ordering Principle, Item 5, which we will subsequently generalise, is a key for many later results. We now consider some results of qualitative probability. Theorem 3.5 (Qualitative Probability). LQP derives:

1. φ φ 0. 2. (φ Φ 0) (φ 0). 3. φ (φ ψ) (φ ψ). 4. φ ψ (φ ψ) (φ ψ). 5. φ 1. 6. φ ψ φ ψ. 7. (φ ψ) ( ψ φ).

These results are familiar from classical probability. For example, Item 2 says that if the probability of φ plus that of some sequence Φ is 0, then the probability of φ is 0. The next theorem concerns the operator ϕ .= (1 φ). Theorem 3.6 (Modal Logic). LQP derives: 1. (φ ψ) (φ ψ). 2. (φ ψ) ( φ ψ). 3. 0. 4. φ (φ ψ ψ). Items 1 and 4 relate to , while Items 2 and 3 show that the underlying modal logic for is KD. As a result, is a normal modal operator, and so we may use results about normal modal reasoning freely. We now generalise some of the above results. Theorem 3.7 (Extended Principles). For n 1, formulas φi and ψi and sequences Φi and Ψi for each i {1, . . . , n}, taking k {1, . . . , n}, LQP derives: 1. V i =j (φi φj) (Ln i=1 φi Wn i=1 φi).

2. (( n i=1Φi n i=1 Ψi) Vn i=1(Φi Ψi)) (Ψk Φk).

3. (( n i=1Φi n i=1 Ψi) Vn 1 i=1 (Φi Ψi)) (Ψn Φn).

4. (φi)n i=1E(ψi)n i=1 (Ln i=1 φi Ln i=1 ψi).

5. (φi)n i=1E(ψi)n i=1 Vn 1 k=1(φk ψk) (ψn φn). Item 1 generalises (K3) to an arbitrary number of pairwiseinconsistent formulas. Items 2 and 3 generalise Theorem 3.4(5). Items 4 and 5 relate our -notation and sequences to Segerberg and G ardenfors E-notation. Last, turning to the metatheory, we have: Theorem 3.8 (Soundness and Completeness). For φ LLQP:

LQP φ if and only if |= φ.

Proof. For convenience, write to mean LQP. Soundness follows by a straightforward induction on the length of derivation. From soundness, we conclude that LQP is consistent (i.e., 0).

Completeness makes use of Thm. 1.2 from [Scott, 1964].7 Preliminaries: for a finite nonempty set S, let L(S) be the real vector space with coordinates in S; this is just like Rn but with coordinate set S instead of {1, . . . , n}. A linear functional on L(S) is a function f : L(S) R that is linear, meaning f(ax + by) = af(x) + bf(y) for each a, b R and x, y L(S). Given N X L(S), a linear functional f on L(S) realizes N in X iff N = {x X | f(x) 0}. X L(S) is rational iff each x X has its range in Q, and X is symmetric iff each x X implies x X. Scott s Theorem 1.2 [Scott, 1964]: for a finite nonempty set S and a finite, rational, and symmetric X L(S), there exists a linear functional on L(S) that realizes N in X iff the following items obtain: 1. for each x X, we have x N or x N; and 2. for each n 1 and x1, . . . , xm N: Pm i=1 xi = 0 implies x1 N. To prove completeness, assume LQP θ. It suffices for us to construct a pointed model for θ. For φ LLQP, let sub(φ) .= {ψ LLQP | ψ occurs in φ} be the set of subformulas of φ. For S LLQP, let sub(S) .= S φ S sub(φ). Given S LLQP and E (LLQP), define

S .= S { φ | φ S},

S .= sub(S) sub{(Ψ Φ) | (Φ Ψ) sub(S)},

Ed .= W S E V S .

Note: d .= 1. Given S T LLQP, to say S maxcons in T means S is consistent (i.e., for no finite S S do we have (V S ) 0) and adding to S any φ T not already present would produce a set that is inconsistent. Define

B .= {(0 Ed), (Ed 1), (Ed Ed) | E A},

C .= {(Ln i=0 Ed i Wn i=0 Ed i ) | n 2|A|, Ei A},

W .= {w A B C | w is maxcons in A B C},

w .= {φ A B C | (V w) (1 φ)},

Ωw .= {v W | w v} for w W,

V (w) .= w P for w W.

Note that in the definition of C, we take each positive integer n 2|A|, choose subsets E1, . . . , En A, and then include all formulas of the indicated form. It is easy to see that A B C and W are finite and W = . By modal reasoning, we have for each w W that w is consistent and so may be extended to v W satisfying w v. Hence Ωw = . For χ LLQP, define [χ] .= {v W | χ v} and [χ]w .= [χ] Ωw. For E W, let ι(E) L(W) be the characteristic function of E: ι(E)(v) .= 1 if v E, and ι(E)(v) .= 0 if v W E. For w W, define:

Nw .= {P ψ Ψ ι([ψ]w) P φ Φ ι([φ]w) | (Φ Ψ) w},

Xw .= Nw ( Nw).

7Interestingly, G ardenfors and Segerberg instead use Thm. 4.1 from [Scott, 1964].

We have Nw Xw; also, Xw is a finite, rational, symmetric subset of L(W). It is obvious that Nw satisfies Item 1 of Scott s Thm. 1.2. We prove Nw also satisfies Item 2. So assume we have x1, . . . , xn Nw satisfying Pn i=1 xi = 0. Vector xi has the form P ψ Ψi ι([ψ]w) P φ Φi ι([φ]w). By linearity, ι([χ]w) = P v [χ]w ι({v}), so the assumption implies

v [φ]w ι({v}) =

v [ψ]w ι({v}).

So writing out the sums in full without combining any summands, the equation above says that a coordinate v W has exactly the same number of appearances in a summand on the left as on the right. So by (Ref) (from Thm. 3.4) and (Com), we obtain

v [φ]w {v}d

v [ψ]w {v}d. (3)

One can show that for each χ A B C, we have

L v [χ]w{v}d χ Ωd w, and (4)

(V w) (χ Ωd w χ). (5)

(4) is proved by deriving (χ Ωd w) W v [χ]w{v}d using Thm. 3.7(1), separately proving W v [χ]w{v}d (χ Ωd w) by a reductio and then applying (Nec), and combining the two results using Thm. 3.4(2). (5) is proved by first showing (V w) Ωd w and then applying Thm. 3.6(4). It follows from (3), (4), and (5) by Thm. 3.4(3) and the equality L φ Φ φ = Φ that

(V w) (Ln i=1 Φi Ln i=1 Ψi). (6)

Since (Φi Ψi) w for each i {1, . . . , n}, it follows from (6) by Thm. 3.7(2) that (Ψ1 Φ1) w. That is, x1 Nw. Therefore, Nw satisfies 1 and 2 of Scott s Thm. 1.2. Applying the theorem, there exists a linear functional fw on L(W) that realizes Nw in Xw. By (Triv) and linearity, it follows that 0 = fw(ι( )) < fw(ι(Ωw)). So we may define Pw : (Ωw) [0, 1] by

Pw(E) .= fw(ι(E)) / fw(ι(Ωw)).

For E, E1, . . . , En Ωw, since fw realizes Nw in Xw: Pw(E) 0 because (0 Ed) w by (K1); if the Ei s are pairwise disjoint, then Pw(Sn i=1 Ei) = Pn i=1 Ei because (Wn i=1 Ed i Ln i=1 Ed i ) w can be shown using Thm. 3.7(1); Pw(Ωw) = 1 by definition. So Pw is a probability measure on (Ωw), and therefore M .= (W, P, V ) is a model. By induction on formula construction, one may prove the following Truth Lemma: for each w W and χ A B C, we have χ w iff M, w |= χ. (The right-to-left direction for χ = (Φ Ψ) uses (Tot).) So since LQP θ, there exists wθ W such that θ wθ. Applying the Truth Lemma, M, wθ |= θ. Completeness follows. Note: (Sub), (Add), and (Succ) are used in the proof of Thm. 3.4(2); (Tran) and (K3) are used in the proof of Thm. 3.7(1).

3.3 Quantitative Aspects of the Theory The results of the previous subsections are qualitative in nature.8 In this subsection we show how we can nonetheless encode quantitative notions, culminating with rational linear inequalities.

Positive Integer Coefficients: define k φ (also kφ) by

0 φ .= 0 and (k + 1) φ .= φ (k φ).

For example, 2φ 3ψ abbreviates φ φ ψ ψ ψ.

Negative Coefficients: if k < 0, then replace kφ in a sequence by 0 and add kφ to the sequence on the other side of . For example, 3ψ 2φ χ denotes 0 2φ 3ψ χ, which is provably equivalent to 2φ 3ψ χ.

Rational Coefficients: if pi

sj Q and t .= Q i,j qisj, let L i n(pi/qi) φi L j m(rj/sj) ψj

abbreviate L i n(t pi/qi) φi L j m(t rj/sj) ψj,

where t pi/qi and t rj/sj are computed arithmetically. For example, 0 (1/2)ψ (1/3)φ denotes (1/3)φ 0 (1/2)ψ 0. The latter denotes 2 φ 6 0 3 ψ 6 0, which, with some work, is provably equivalent to 2φ 3ψ.

Rational Numbers: identify 0 Q with 0 LLQP and nonzero x Q with (p/q) 1 LLQP, where p/q = x and gcd(p, q) = 1. For example, (2/3) 1 and 0 (1/2) (1/3) are derivable.

It follows that LLQP can express inequalities Lna i=1 ai Lnb i=1(bi φi) Lnc i=1 ci Lnd i=1(di ψi)

between finite sums of rational numbers and rationalcoefficient formulas. We refer to these expressions as rational linear inequalities. Based on the definition of LLQP, both sides of a rational linear inequality must be nonempty, though we could take either side to be 0.

Theorem 3.9 (Quantitative Probability Principle). For rational numbers a1, . . . , an, b1, . . . , bm Q, we have: Pn i=1 ai Pm i=1 bi LQP Ln i=1 ai Lm i=1 bi.

4 Comparisons with Related Work

In this section we compare our approach with that of [G ardenfors, 1975] and [Fagin et al., 1990]; see Section 2 for axiomatisations. We also provide a preliminary comparison with [Segerberg, 1971].

4.1 G ardenfors Logic of Qualitative Probability Informally, the language LQP of G ardenfors QP is that of LLQP restricted to length-1 sequences, and so is a binary relation on formulas only. It is not surprising then that LQP is less expressive than LLQP:

8This is an informal claim, appealing to intuitions rather than any technical distinction.

Theorem 4.1. LLQP is strictly more expressive than LQP over our class of models. For example p 1/3 denotes a satisfiable LLQP-formula that is inexpressible in LQP. Moreover, noting that LQP LLQP and making use of the fact that QP and LQP are both sound and complete with respect to our class of models, we obtain: Theorem 4.2. For all φ LQP, if QP φ then LQP φ. Consequently, LQP is a conservative extension of QP.

4.2 The Fagin et al. Logic of Quantitative Probability The language of [Fagin et al., 1990] is defined as follows: Definition 4.3. Fix a nonempty set P of propositional atoms. The language LAXmeas consists of formulas φ and weight terms W given by the following recursion:

φ ::= p | φ | (φ φ) | (a W) p P, a Z W ::= w(ψ) | a w(ψ) | W + W a Z ψ ::= p | φ | (φ φ) p P

LAXmeas does not allow nesting of s in formulas; for example, 1 (1 w(p)) is not a formula in LAXmeas. So to compare the expressivity of LAXmeas with our language LLQP, it is useful to consider the fragment L LQP of our language that does not allow nesting of s. Theorem 4.4. Over our class of models:

1. LAXmeas and L LQP are equally expressive; and 2. LLQP is strictly more expressive than LAXmeas.

The proof of Item 2 uses nesting. The proof of Item 1 defines an injective translation H : LAXmeas L LQP that recursively maps w(φ) 7 φ.9 Using the inverse H 1, we find: Theorem 4.5. AXmeas is the same theory as

LQP H .= {H 1(φ) | φ L LQP and LQP φ}.

Consequently, while AXmeas is a logic of quantitative probability, we nonetheless can express it in LQP. Among other things, this implies that we provide a (qualitative) schematically finite axiomatisation of (Ineq).

4.3 Discussion G ardenfors and Segerberg s logics both include an infinite number of complex counting schemes, as expressed using their E notation. These are required in order to use Scott s theorem for completeness. Fagin et al. s logic seems quite simple at first glance just classical logic, Kolmogorov s axioms, and an axiom (Ineq) concerning valid linear inequalities. However, (Ineq) is not stated in the language of the logic; it assumes numbers and arithmetic; and it encompasses infinitely many principles of inequality involving sums of unbounded length. Our setting has finitely many axiom schemes, each arguably simple and stated in the language of the logic. The

9We use our abbreviations for rational linear inequalities in order to ensure that H is well-defined.

cost of these advantages is that we have more schemes than the aforecited approaches. Overall, we provide a system that captures qualitative probabilistic reasoning, axiomatic probability, the major qualitative system due to [G ardenfors, 1975] and the major quantitative system due to [Fagin et al., 1990]. LLQP as it stands is expressively incomparable with the language LPK of Segerberg s logic PK. Like G ardenfors LQP, Segerberg s LPK cannot express the LLQP-formula p 1/3. On the other hand, LPK includes a Kripke-style necessity operator, which we write as to distinguish it from our symbol . The meaning of M, w |= p is that we have M, v |= p at all worlds v contained in some superset R(w) Ωw of the set Ωw of outcomes at w. As a result, it can be shown that p is not expressible in LLQP. (Essentially, allows the language to reach outside of the worlds that are probabilistically possible relative to the given world w, something that is not possible in LLQP.) Therefore we must extend our language LLQP to a language LLQP containing the operator in order to regain expressive comparability. On doing this, we find that LLQP is strictly more expressive than both LPK and LLQP over the class of models to which we add an accessibility function R : W (W) satisfying Ωw R(w) for each world w W. As for comparing the theories LQP and PK, we have a conjectured axiomatisation for the LLQP-validities over a class of models whose set of worlds (and outcome sets) need not be finite. If complete, it could easily be extended to a theory LQP axiomatizing the LLQP -validities over the class of possibly infinite models to which we have added the accessibility function R : W (W) satisfying Ωw R(w) for each world w W. In light of soundness and completeness of both theories with respect to this class and the fact that LPK LLQP , we would obtain that LQP is a conservative extension of PK. However, completeness of the proposed axiomatisation is still to be shown.

5 Conclusion

This paper has addressed the foundations of qualitative probability. While work in this area goes back many years, we have argued that no approach has provided a wholly satisfactory characterisation of qualitative probability. In earlier work, a binary operator on formulas (or events ) is given, describing the relation is no more probable than . The central innovation of our approach is that is regarded not as a binary operator on formulas but rather as an operator on finite sequences of formulas. We showed that the logic LQP of our approach can be used to reason about qualitative and axiomatic probability using a finite number of arguably simple axiom schemes. Moreover, we showed that the approach is rich enough to encode rational linear inequalities. We compared our approach to the major previous works, showed that ours subsumes those theories for finite outcome sets, and argued that our approach is methodologically preferable. A question as to the axiomatisation of the LLQP-validities over a class of models having possibly infinite outcome sets is left for future work.

Acknowledgements The first author acknowledges financial support from the Natural Sciences and Engineering Research Council of Canada. The second author was funded by Veni grant 275-20-030 from the Netherlands Organisation for Scientific Research (NWO) hosted by the Institute for Logic, Language, Information and Computation (ILLC) at the University of Amsterdam.

References [de Finetti, 1937] Bruno de Finetti. La pr evision: ses lois logiques, ses sources subjectives. Annals de l Institut Henri Poincar e, 7:1 68, 1937. Translated into English in H.E. Kyburg, Jr. and H.E. Smokler (eds.), Studies in Subjective Probability, 1964, pp. 93 158. [de Finetti, 1951] Bruno de Finetti. La logica del plausibile secondo la concezione di polya. In Atti della XLII Riunione, Societa Italiana per il Progresso delle Scienze, pages 227 236, 1951. [Fagin et al., 1990] Ronald Fagin, Joseph Y. Halpern, and Nimrod Megiddo. A logic for reasoning about probabilities. Information and Computation, 87:78 128, 1990. [G ardenfors, 1975] P. G ardenfors. Qualitative probability as an intensional logic. Journal of Philosophical Logic, 4(2):171 185, 1975. [Halpern, 2003] J.Y. Halpern. Reasoning about Uncertainty. MIT Press, 2003. [Holliday and Icard, 2013] Wesley H. Holliday and Thomas F. Icard. Measure semantics and qualitative semantics for epistemic modals. In Proceedings of SALT, volume 23, pages 514 534, 2013. [Kraft et al., 1959] Charles H. Kraft, John W. Pratt, and A. Seidenberg. Intuitive probability on finite sets. The Annals of Mathematical Statistics, 30(2):408 419, 1959. [Kyburg, 1994] H.E. Kyburg, Jr. Believing on the basis of evidence. Computational Intelligence, 10(1):3 20, 1994. [Narens, 2007] Louis Narens. Theories of Probability: An Examination of Logical and Qualitative Foundations. World Scientific, 2007. [Scott, 1964] Dana Scott. Measurement structures and linear inequalities. Journal of Mathematical Psychology, 1(2):233 247, 1964. [Segerberg, 1971] Krister Segerberg. Qualitative probability in a modal setting. In J.E. Fenstad, editor, Proceedings of the Second Scandinavian Logic Symposium, volume 63 of Studies in Logic and the Foundations of Mathematics, pages 341 352. Elsevier, 1971. [van Eijck and Renne, 2014] Jan van Eijck and Bryan Renne. Belief as willingness to bet. E-print, ar Xiv.org, December 2014. ar Xiv:1412.5090 [cs.LO].