\underline{\underline{\underline{10}}} In conjunction with qualitative probability

Abstract. Numerical probabilities (associated with propositions) are eliminated in favor of qualitative notions, with an eye to isolating what it is about probabilities that is essential to judgments of acceptability. A basic choice point is whether the conjunction of two propositions, each (separately) acceptable, must be deemed acceptable. Concepts of acceptability closed under conjunction are analyzed within Keisler’s weak logic for generalized quantifiers — or more specifically, filter quantifiers. In a different direction, the notion of a filter is generalized so as to allow sets with probability non-infinitesimally below 1 to be acceptable.

1 Introduction: weighing the evidence. Let L be a set of “formulas” (φ, ψ, …), and V be a set of “possibilities” (a, b, …), connected to L by a relation ⊧, capturing the intuition that for all a ∈ V and φ ∈ L,

a ⊧ φ iff a “supports” φ .

We can, for concreteness, take the case of predicate logic, although we can also proceed more abstractly, assuming only some relation ⊧ ⊆ V × L. In any case, the point is to pick out a set A ⊆ L of “acceptable” formulas on the basis of ⊧, so that for every φ ∈ L,

φ is acceptable iff the “evidence” {a ∈ V : a ⊧ φ}

supporting φ “has enough weight”

or, in other words,

(1)  φ ∈ A iff {a ∈ V : a ⊧ φ} ∈ H

for some family H ⊆ Pow(V) of “heavy” subsets of V. Clearly, the safest choice is to equate A with the ⊧-validities (i.e., the formulas φ such that for every a ∈ V, a ⊧ φ), which is to say, to set H = {V }. But suppose we took a chance on some other choice of A (and H) that tolerates failures or exceptions. What are the rules for doing so rationally?

“Logic” suggests the closure condition

(Up) \frac{φ ∈ A  φ |− ψ}{ψ ∈ A}  \frac{A ∈ H  A ⊆ B (⊆ V)}{B ∈ H}

where φ |− ψ means that for every a, if a ⊧ φ then a ⊧ ψ. (Up) alone introduces no element of risk into A (or H) insofar as (Up) does not yield, from the assumption that V ∈ H, any more elements of H. On the other hand, (Up) does suggest how to proceed — namely, by weakening |− to some binary relation |∼ on L or (turning to H) ⊆ to some binary relation ⪯ on Pow(V)

(Up)_{|∼} \frac{φ ∈ A φ |∼ ψ}{ψ ∈ A}  (Up)_{⪯} \frac{A ∈ H A ⪯ B}{B ∈ H} .

Although the correspondence between A and H described by (1) extends to pairs A and H closed respectively under (Up)_{|∼} and (Up)_{⪯}, for some relations |∼ and ⪯, the intuitions that most naturally come to play with the rule (Up)_{|∼} differ from those behind (Up)_{⪯} — the former being syntactic (or prooftheoretic), the latter, semantic. An example where this distinction matters concerns the operation ∧ of conjunction on L, for which it is understood that for every a ∈ V, a ⊧ φ ∧ ψ iff a ⊧ φ and a ⊧ ψ. It is largely on this simple example that the present paper turns.

1.1 Content of paper. There is a certain plausibility to asserting

(And) if φ and ψ are both acceptable, then φ ∧ ψ is acceptable if only because

(i) it takes a bit of sophistication to even sense the difference between “φ

and ψ” and “φ ∧ ψ” and

(ii) after such sophistication is acquired, we learn that the difference does not (in a sense) matter, if acceptability is construed as validity (semantic or syntactic).

(And) becomes problematic, however, as soon as we accept some exceptions. This is brought out most clearly perhaps by H. Kyburg’s “lottery paradox”: the proposition that one in say, a million tickets in a lottery will win is acceptable, as are each of a milion propositions asserting that a particular ticket will not win. The “paradox” vanishes after a moment’s thought on the underlying semantics: were we to agree that

A = {φ ∈ L : there is at most one a ∈ V
for which a |̸= φ} ,

we may run up against a pair φ and ψ of formulas in A such that the one counter-example to φ is different from the one counter-example to ψ, whence φ ∧ ψ ∉ A.

But as long as we concentrate on the syntactic side A, choosing the semantics H to support the manipulations on A that we have decided to legitimize, there is hope for (And). In this regard, it is worthwhile noting what Pearl 1994 calls a “long-standing tension between the logical and probabilistic approaches to dealing with such exceptions”: whereas the former is “prescriptive” (insofar as logic is simply a record of “conversational conventions”), probabilities are “descriptive” (be they measures of objective frequencies or subjective beliefs^{1}).

1In the case of objective probabilities, it is useful to equate L with the set of terms of a formal language (ideally: typed), whereas in the case of subjective probabilities, it is

Now, the question is how could probabilities describe the logical rule (And)? A natural way to proceed is to accept precisely the formulas with probability greater than some fixed threshold α ∈ [0, 1] (say, .999), given a probability function pr from L to the unit interval [0, 1]

A_{pr,α} = {φ ∈ L : pr(φ) > α} .

The hitch is that exceptions add up: from pr(φ) = 1 − δ and pr(ψ) = 1 − ϵ, one cannot, in general, do better than predict pr(φ ∧ ψ) ≥ 1 − (δ + ϵ). This suggests that we

(I) replace the condition that pr(φ) > α by the requirement that 1 − pr(φ) be infinitesimal, where infinitesimals are assumed to be closed under addition: if δ and ϵ are infinitesimals, then so is δ + ϵ.

The notion of an infinitesimal here is exactly that introduced by A. Robinson in his non-standard reconstruction of calculus. Reversing chronological order, we could, as an alternative to (I), (II) explain away infinitesimals by ϵδ-type limits (à la Bolzano-Weierstrass). Pearl 1994 describes the work of Adams and Spohn in much this way, though without the emphasis on (And). I have decided here to focus on (And) because, together with (Up), it supports a very direct and general analysis of approaches (I) and (II), using no more structure than that implicated by line (1) above. This is made precise by Theorems 1 and 2 in §§2.1 and 2.2 respectively, where, in particular, no appeal is made to numbers, be they in the standard unit interval [0, 1], or some non-standard copy thereof. This is not to say that the analysis given is incompatible with a numerical approach; only that it allows us to avoid all kinds of arithmetical complications — not to mention the somewhat embarrassing question: what probability function?

Without specifying a particular probability function, we return, in §3, to probabilities, beefing up the rule (Up) to a rule (Up)_{⪯}, where ⪯ means “at least as probable.” In this section, we refrain from making any commitment to the soundness or, for that matter, unsoundness of (And). (Up)_{⪯} applies not only to models of (And), but also to A_{pr,α} = {φ ∈ L : pr(φ) > α}, where pr is a probability function, and α is some number in [0, 1]. (It is easy enough to introduce a rule restricting α say, to be above \frac{1}{2}). As weak as the rule (Up)_{⪯} might be, it nevertheless constitutes a step to understanding what is involved qualitatively in accepting formulas with probabilities that fall non-infinitesimally short of 1.

1.2 Related work. There is an evidently widespread belief that it is a nontrivial (if not hopeless) enterprise to reason qualitatively about formulas with probabilities greater than some fixed threshold non-infinitesimally short of 1. Pearl 1988 puts the matter as follows

convenient to take L to be the language’s set of formulas (V the language’s collection of models, and ⊧ its satisfaction relation).

Probabilities that are infinitesimally close to 0 and 1 are very rare in the real world. Most default rules used in ordinary discourse maintain a certain percentage of exceptions, simply because the number of objects in every meaningul class is finite. Thus, a natural question to ask is, why study the properties of a logic that applies only to extreme probabilities? Why not develop a logic that characterizes moderately high probabilities, say probabilities higher than 0.5 or 0.9 — or more ambitiously, higher than α, where α is a parameter chosen to fit the domains of the predicates involved?

The answer is that any such alternative logic would be extremely complicated and probably would need to invoke many axioms of arithmetic. [pages 493, 494]

A similar view can be found in Halpern and Rabin 1987, where “a logic to reason about likelihood” is developed relative to a non-probabilistic semantics. The probabilistic approach to likelihood presented in §3 (below) is not only qualitative but quite possibly simpler than might have been feared. It proceeds along lines similar to Scott 1964 and Segerberg 1971, as discussed further below.

The literature on non-monotonic formalisms that incorporate (And) as a basic or derived rule is vast and, for the uninitiated, downright bewildering. (See, for instance, Pearl 1994 and the references cited therein, plus Kyburg 1970 for earlier work.) What the present paper offers is a logical approach that departs minimally (if at all) from standard practice in classical mathematical logic. The one possible point of departure is the appeal to the weak logic of generalized quantifiers in Keisler 1970 (which arguably belongs to the mainstream of logic) for formalizing line (1) above,^{2} and even then, the introduction of generalized quantifiers can be eliminated according to Theorems 1 and 2 below, resulting in ordinary predicate logic. Some specialists in the logic of generalized quantifiers seem to consider Theorem 1 part of the subject’s folklore. It is implicit in van Lambalgen 1991, and appears in a disguised form as Theorem 5 of Alechina and van Lambalgen 1996, the inessential notational differences being due to that work’s somewhat novel syntax (involving modality) and semantics (motivated by proof theory).

A crucial syntactic point that ought to be stressed is the expulsion of numbers from formulas below — in contrast, that is, to the quantitative approaches in Keisler 1985 and Halpern 1990, where numbers appear explicitly in formulas. The idea behind minimizing (explicit) reference to probabilities is to isolate what it is about probabilities that is essential to judgments of acceptability; but by opening the door to alternative non-probabilistic interpretations of formulas, the challenge then becomes showing that only the probabilistic semantics need matter. (More concretely, the problem in establishing completeness is how to define a probability measure from syntactic entities that do not mention numbers.)

2A fine point about (1) and weak logic is that the extension of A to a binary predicate |∼ on L can be treated by passing from unary to binary generalized quantifiers, at the cost only of notational clutter; see §2.3.

2 Reasoning according to preference: filters. A straightforward formalization of line (1) is provided by the weak logic L(Q) for generalized quantifiers of Keisler 1970 where

(i) L is a first-order language and Q is a generalized quantifier symbol, inducing formulas Qxφ (in addition to the usual closure rules on firstorder L-formulas)

and

(ii) an L(Q)-model is a pair (M, q) consisting of a first-order L-model M and a family q ⊆ Pow(|M|) of subsets of the universe |M| of M, so that (relativizing (1) to (M, q))

(M, q) ⊧ Qxφ[f] iff {a ∈ |M| : (M, q) ⊧ φ[f_{a}^{x}]} ∈ q

for every function f mapping variables to objects in |M| (and where f_{a}^{x} is the function that maps x to a, but is otherwise identical to f).

2.1 Filter quantifiers. Given a set V, a filter on V is a non-empty family H of subsets of V satisfying (Up) and closed under intersections — viz., V ∈ H; whenever A ∈ H and A ⊆ B ⊆ V, B ∈ H; and for all A ∈ H and B ∈ H, A ∩ B ∈ H (thereby supporting (And)). These properties translate in L(Q) to the (filter) schemes

(Q1) Qx x = x
(Q2) ∀x(φ ⊃ ψ) ⊃ (Qxφ ⊃ Qxψ)
(Q3) Qxφ ∧ Qxψ ⊃ Qx(φ ∧ ψ) .

Let us write F [Q] for the L(Q)-theory induced by (Q1), (Q2) and (Q3), where φ and ψ are L(Q)-formulas with the same set of free variables. Note that F [Q] holds for Q = ∀, or restricted universal quantification. The converse is not quite true: consider the standard model M of arithmetic, and let q be the family

{A ⊆ {0, 1, … } : {0, 1, … } − A is finite}

of co-finite sets of natural numbers; then (M, q) is a model of F [Q], even though q is a non-principal filter. (A filter q on V is principal if ⋂ q ∈ q, in which case ⋂ q is said to generate q.) Nevertheless, the converse can be approximated through elementary extensions and the following bit of bookkeeping due to van Lambalgen 1991. Fix a relation symbol R not in L that accepts any finite positive number of arguments, and call an L(Q)-model (M, q) relatively principal if under some expansion of (M, q) to R,

(2)  Qxφ ≡ ∀x(R(x, \overline{y}) ⊃ φ)

holds for every L(Q)-formula φ with free variables x, \overline{y} (where \overline{y} is say, ordered according to some fixed well-ordering of variables). (2) says that Q can be taken to be universal quantification ∀ restricted to some set R of “generic” (or “normal”) elements (modulo \overline{y}). These generic elements are “transcendental” in \overline{y}: assuming ∀yQx(x ≠ y), they cannot be named by L-terms with free variables drawn from \overline{y}. (Hence, the necessity of adding \overline{y} to R.)

Theorem 1.^{3} Every L(Q)-model of F [Q] can be elementarily extended to a relatively principal L(Q)-model.

Proof. Fix an L(Q)-model (M, q) of F [Q], and a finite set Φ_{0} of instances of (2). By the compactness theorem of weak logic (Keisler 1970), it suffices to show how to expand (M, q) to a model of Φ_{0}. The idea is to interpret R as the set

\{(F_{ψ}(\overline{a}), \overline{a}) : ψ is an L(Q)-formula, \overline{a} ∈ dom(F_{ψ})\} ,

for certain partial functions F_{ψ} (to be defined presently) from the set of finite sequences of (the universe) |M| (of M) to |M|. Let n be the number of free variables in Qxψ. The domain of F_{ψ} consists exactly of the n-tuples \overline{a} ∈ |M|^{n} such that

(∗) (M, q) |̸= Qxψ[\overline{a}] .

Given such a sequence \overline{a}, let φ be the conjunction

⋀{φ_{0} : Qxφ_{0} has the same set of free variables as Qxψ,
and ‘Qxφ_{0}’ ∈ Φ_{0}, and (M, q) ⊧ Qxφ_{0}[\overline{a}]\}

(appealing here to the finiteness of Φ_{0}). It is understood that an empty conjunction is some tautology. Using (Q3) in case the set is non-empty, it follows that

(M, q) ⊧ Qxφ[\overline{a}] .

Hence, by assumption (∗) and Qxφ ∧ ¬Qxψ ⊃ ∃x(φ ∧ ψ), to which (Q2) can, as pointed out to me by N. Alechina, be rewritten,

(M, q) ⊧ ∃x(φ ∧ ¬ψ)[\overline{a}] .

It remains to choose some such witness for the value of F_{ψ}(\overline{a}). □

Remark. The interpretation of R suggested in the proof of Theorem 1 can be described roughly as follows: for every L(Q)-formula ψ such that (M, q) |̸= Qxψ, throw in a witness to the set

{¬ψ} ∪ {φ ∈ L(Q) : (M, q) ⊧ Qxφ}

of formulas. What is “rough” about this description is that (a) we should be more careful to specify what variables and constants to allow in the formulas, and (b) the required witnesses may not exist in M. The first point is a simple matter of bookkepping, while the second can be handled by appealing to the existence of elementary extensions that are ω-saturated — suggesting a restatement of Theorem 1 as

Proposition 1′. Every ω-saturated L(Q)-model of F [Q] is relatively principal.

3See the note in §1.2 for bibliographic information.

In fact, Proposition 1′ can be sharpened to so-called recursively saturated models (Barwise 1975), as the sets of formulas that must be realized can be given effectively as follows

{(¬Qxψ) ⊃ ¬ψ} ∪ {(Qxφ) ⊃ φ : φ ∈ L_{n}(Q)}

for every ψ ∈ L_{n}(Q), where L_{n} is an expansion of the language L to n fresh constants (abusing notation in identifying L_{n}(Q) with the set of L_{n}(Q)-formulas with one free variable x). Note the similarity of (¬Qxψ) ⊃ ¬ψ to Henkin expansions that witness existential statements. The next section adapts notions from a celebrated method, the force of which is to omit rather than to realize types.

2.2 Graded normality. The proper extensions mentioned in Theorem 1 can be avoided, provided (2) is weakened to allow for varying grades (rather than an absolute, either/or, notion) of genericity: add an argument place to R, for a relation symbol ⊏ to be used with the intuition that

u ⊏ v iff u is “more generic” than v .

More precisely, let L be a countable first-order language, ⊏ be a fresh binary relation symbol (not in L), and let y ⊑ z abbreviate (y ⊏ z) ∨ (y = z). Given an L-model M, let L_{M} be L together with a fresh constant symbol for every object in M. To simplify the notation, we will identify an object a in M with its constant symbol in L_{M}, and write M for the L_{M}-model obtained by expanding the L-model M to L_{M}, with every a in M interpreted as a.

Theorem 2. For every countable (or finite) L(Q)-model (M, q) of F [Q], there is a transitive binary relation ≺ ⊆ |M| × |M| such that for every L_{M}(Q)- formula φ with exactly one free variable x,

(3)  Qxφ ≡ (∀z)(∃y ⊑ z)(∀x ⊏ y) φ

holds in (M, q, ≺).

Remarks.

1. (3) describes an ϵδ-limit/asymptotic/cofinal-type quantification, with (2) falling out as the special case given by

u ⊏ v ≡ R(u)

(i.e., the second argument v in ⊏ is vacuous).

2. The converse of Theorem 2 (the soundness of F [Q] under (3)) is trivial: the schemes (Q1) and (Q2) follow from (3) alone, while (Q3) is a consequence of the transitivity of ≺ (as well as (3)). (I have not investigated what generality (3) buys beyond that of (2), in the absence of the assumption that ⊏ is transitive.)

3. The restriction to one free variable is inessential, and is made only to simplify notation, allowing us to suppress the subscripts \overline{y} on ⊏ in (3).

4. It is considerably more complicated to describe an interpretation of ⊏ validating (3) in Theorem 2 than an interpretation of R supporting (2) in Theorem 1. In this connection, it is interesting to note the sentiment any fool can realize a type, but it takes a model-theorist to omit one expressed in Sacks 1972. The twist in Theorem 2 is that the “ontological promiscuity” in saturation arguments is avoided by a purely combinatorial argument (without resorting to any of the model-theorist’s tools, such as completeness).

Proof of Theorem 2. Fix an L(Q)-model (M, q) of F [Q], and partition the set Φ of L_{M}(Q)-formulas with exactly one free variable x as follows

Φ_{+} = {φ ∈ Φ : (M, q) ⊧ Qxφ}
Φ_{−} = {ψ ∈ Φ : (M, q) |̸= Qxψ} .

If for every φ ∈ Φ_{+}, (M, q) ⊧ ∀xφ, then we can set ≺ to {(a, a) : a ∈ |M|} and we are done. Otherwise, choose a φ_{0} ∈ Φ_{+} and a_{0} ∈ |M| such that

(M, q) |̸= φ_{0} [a_{0}] ,

and let {φ_{0}, φ_{1}, φ_{2}, φ_{3}, … } be an enumeration of Φ. We will define ≺ by finite approximations ≺^{i} (for i ≥ 0), with

≺ = ⋃_{i≥0} ≺^{i} .

The plan is to construct for each i ≥ 0, a finite transitive relation ≺^{i} such that the following four conditions hold, with the understanding that

Φ_{+}^{i} = Φ_{+} ∩ {φ_{j} : j ≤ i}
Φ_{−}^{i} = Φ_{−} ∩ {φ_{j} : j ≤ i}
E^{i} = {a ∈ dom(≺^{i}) : (∀b ≺^{i} a) a ≺^{i} b} (= the set of

≺^{i}-minimal points).

(C1) ≺^{i}⊆≺^{i+1}. (C2) dom(≺^{i+1} − ≺^{i}) ⊆ E^{i+1}. (C3) For every a ∈ E^{i}, (M, q) ⊧ ⋀ Φ_{+}^{i}[x/a]. (C4) There is a “witness” map w_{i} : Φ_{−}^{i} → E^{i} such that for every ψ ∈ Φ_{−}^{i},

(M, q) ⊧ ¬ψ [x/w_{i}(ψ)] ,

and for every j > i, and every a ∈ |M|,

a ⪯^{j} w_{i}(ψ) implies w_{j}(ψ) ≺^{j} a .

What makes (C1)-(C4) interesting is Lemma A. If ≺ is the union ⋃_{i} ≺^{i} of finite transitive relations ≺^{i} satisfying (C1), (C2), (C3) and (C4), then the required equivalence (3) holds.

Proof. Suppose (first) that (M, q) ⊧ Qxφ. Given a ∈ |M|, either there is some a′ ∈ |M| such that a′ ≺ a, or not. If not, then

(M, q, ≺) ⊧ (∃y ⊑ a)(∀x ⊏ y) φ

holds vacuously (by the definition of ⊑ as the disjunction of ⊏ with equality). Otherwise, choose an i such that φ ∈ Φ_{+}^{i} and appeal to (C1), (C2) and (C3) for an a′ ∈ E^{i} such that a′ ≺^{i} a.

Next, assume (M, q) |̸= Qxφ. Choose an i such that φ ∈ Φ_{−}^{i}, and conclude from (C1) and (C4) that

(M, q, ≺) ⊧ (∀y ⊑ z)(∃x ⊏ y) ¬φ[z/w_{i}(φ)] .

□ (Lemma A) To push the construction of ≺ through, the following will be useful.

Lemma B. For all φ ∈ Φ_{+}, ψ ∈ Φ_{−}, and every finite subset A_{0} of {a ∈ |M| : |M| − {a} ∈ q},

{a ∈ |M| : (M, q) ⊧ (φ ∧ ¬ψ)[x/a]} ⊈ A_{0} .

Proof. Repeated applications of (Q3) give

(M, q) ⊧ Qx(φ ∧ ⋀_{a∈A_{0}} x ≠ a) ,

and therefore, if ψ ∈ Φ_{−} then (Q2) implies

(M, q) |̸= ∀x ((φ ∧ ⋀_{a∈A_{0}} x ≠ a) ⊃ ψ) ,

i.e.,

(M, q) |̸= ∀x ((φ ∧ ¬ψ) ⊃ ⋁_{a∈A_{0}} x = a) ,

as required. □ (Lemma B) Looking more closely at {a ∈ |M| : |M| − {a} ∈ q}, observe that (Q2) implies

{a ∈ |M| : |M| − {a} ∉ q} = ⋂ q

and Lemma C. For every a ∈ ⋂ q and every φ ∈ Φ_{+}, (M, q) ⊧ φ[x/a].

Proof. If (M, q) |̸= φ[x/a], then

{b ∈ |M| : (M, q) ⊧ φ[x/b]} ⊆ |M| − {a} ,

so that φ ∈ Φ_{+} and (Q2) imply |M| − {a} ∈ q (i.e., a ∉ ⋂ q). □ (Lemma C)

Next, let I^{i} be the image of ≺^{i} minus E^{i}

I^{i} = {a ∈ |M| − E^{i} : (∃b ∈ |M|) b ≺^{i} a}

and add to the list (C1)-(C4) (C5) For every a ∈ I^{i}, there is a φ ∈ Φ_{+}^{i} such that (M, q) |̸= φ[a]. (C6) The witness map w_{i} mentioned in (C4) is surjective (onto E^{i}) and has

the additional property that for all ψ, ψ′ ∈ Φ_{−}^{i} such that ψ ≠ ψ′, if w_{i}(ψ) = w_{i}(ψ′), then w_{i}(ψ) ∈ ⋂ q.

Let us turn finally to the definition of ≺^{i} (and w_{i}). The initial stage i = 0 is trivial: since φ_{0} ∈ Φ_{+}, we can set ≺^{0}= ∅ (whence E^{0} = ∅ = w_{0}). Now, consider stage i + 1.

Case 1: φ_{i+1} ∈ Φ_{+}. Let N = {a ∈ E^{i} : (M, q) |̸= φ_{i+1}[x/a]}. By Lemma C, for every a ∈ N, a ∉ ⋂ q. Hence by (C6), each a ∈ N has a unique ψ_{a} ∈ Φ_{−}^{i} such that w_{i}(ψ_{a}) = a. Next, apply (Q3) and Lemma B to define a function new : N → |M| such that for every a ∈ N,

(M, q) ⊧ ((¬ψ_{a}) ∧ ⋀ Φ_{+}^{i+1})[x/new(a)]

(whence new(a) ∉ I^{i} by (C5)) and

new(a) ∈ (E^{i} − N) ∪ {new(a′) : a′ ∈ N − {a}} implies
new(a) ∈ ⋂ q .

Then set ≺^{i+1} to be the transitive closure of

≺^{i} ∪ {(new(a), a) : a ∈ N} ∪ {(new(a), new(a)) : a ∈ N}

and define w_{i+1} : Φ_{−}^{i+1} → E^{i+1} by

w_{i+1}(ψ) = \{ \begin{matrix}new(w_{i}(ψ)) & if w_{i}(ψ) ∈ N \\ w_{i}(ψ) & otherwise \end{matrix}

for every ψ ∈ Φ_{−}^{i+1} (= Φ_{−}^{i} by the case assumption).

Case 2: φ_{i+1} ∈ Φ_{−}. Writing ψ for φ_{i+1}, choose, by (Q3) and Lemma B, an a such that

(M, q) ⊧ ((¬ψ) ∧ ⋀ Φ_{+}^{i})[x/a]

and

a ∈ {w_{i}(ψ) : ψ ∈ Φ_{−}^{i}} implies a ∈ ⋂ q .

Then set

≺^{i+1} = ≺^{i} ∪ {(a, a_{0})}
w_{i+1} = w_{i} ∪ {(ψ, a)}

(recalling that a_{0} was the element chosen at the outset satisfying ¬φ_{0}, and that a ∉ I^{i}, by (C5)).

Verifying conditions (C1) through (C6) is routine. □

2.3 The binary case (from A to |∼). Theorems 1 and 2 generalize to binary quantifiers (with only notational complications) as follows. To step from a unary quantifier up to a binary quantifier, an L-model M is paired with a binary relation q ⊆ Pow(|M|) × Pow(|M|) such that

(M, q) ⊧ Qx(φ, ψ)[f] iff {a ∈ |M| : (M, q) ⊧ φ[f_{a}^{x}]} q
{a ∈ |M| : (M, q) ⊧ ψ[f_{a}^{x}]} .

The weak completeness and compactness theorems of Keisler 1970 lift immediately to this setting (as worked out, for instance, in Westerståhl 1989). The filter schemes (Q1), (Q2) and (Q3) turn into

Qx(φ, φ)
∀x(ψ ⊃ ψ′) ⊃ (Qx(φ, ψ) ⊃ Qx(φ, ψ′))
Qx(φ, ψ) ∧ Qx(φ, ψ′) ⊃ Qx(φ, ψ ∧ ψ′)

respectively, with line (2) becoming

(4)  Qx(φ, ψ) ≡ ∀x((φ ∧ R_{φ,x}(x, \overline{y})) ⊃ ψ)

where \overline{y} lists the free variables ≠ x in φ as well as ψ. Line (4) supports a reading of the formula Qx(φ, ψ) as “for all relevant φ-x’s, ψ.” Theorem 1 can be lifted to these binary forms, under the additional condition that R is “extensionalized” so that

∀x\overline{y}(φ ≡ φ′) ⊃ ∀x\overline{y}(R_{φ,x}(x, \overline{y}) ≡ R_{φ′,x}(x, \overline{y}))

for all L(Q)-formulas φ and φ′ with the same free variables x, \overline{y}. Similar remarks apply to Theorem 2. (I.e., the relation symbol ⊏ must also be relativized to the antecedent φ and the quantified variable x, although its extension can be arranged to depend on φ only up to ≡.)

3 Between preferences and probabilities: quasi-filters. Having upgraded a “normality” predicate R into a “preference” relation ⊏, let us proceed further, into probability measures, concentrating on H (rather than on A). Fix a non-empty set V, and a field F of subsets of V (containing V and closed under ∪ and \overline{·}). Recall that a (finitely additive) probability function on F is a function μ : F → [0, 1] such that μ(V) = 1, and for all A, B ∈ F,

μ(A ∪ B) = μ(A − B) + μ(B − A) + μ(A ∩ B) .

3.1 Weakening filters non-conservatively. A family H ⊆ F of sets in F is sizable if there is a probability function μ on F such that for every A ∈ F,

A ∈ H iff μ(A) > μ(\overline{A}) (i.e., μ(A) > \frac{1}{2}) .

Given α ∈ [0, 1], call a family H ⊆ F α-sizable if there is a probability function μ on F such that for every A ∈ F,

A ∈ H iff μ(A) > α .

Let us record some properties of α-sizable families differentiating them from filters.

Proposition 3.

(i) Sizable families verify

(Half) \frac{\overline{A} ∉ H  A ∪ \overline{B} ∉ H}{A ∪ B ∈ H} .

(ii) For n ≥ 1, let

(Cov_{n}) ⋁_{δ:{1,2,... ,n}→{+,−}} ((⋃_{i=1}^{n} A_{i}^{δ(i)}) ∈ H)

where A_{i}^{+} = A_{i} and A{− \atop i} = \overline{A}_{i}. Then (Cov_{n}) is valid for α-sizable families iff α < 1 − 2^{−n}.

Proof. Part (i) is trivial: μ(\overline{A}) ≤ \frac{1}{2} and μ(A ∪ \overline{B}) ≤ \frac{1}{2} imply μ(A ∪ B) = 1, since

μ(A ∪ B) = μ(A − B) + μ(B)
= μ(\overline{B}) − μ(\overline{B} − A) + μ(B)
= 1 − μ(\overline{B} − A)

where μ(\overline{B} − A) = 0 (because μ(\overline{A}) ≤ \frac{1}{2} and μ(A ∪ \overline{B}) ≤ \frac{1}{2}).

Part (ii) requires a little more work, the point being to prove that for every n ≥ 1, and sequence A_{1}, …, A_{n} ∈ F,

(5)  max_{δ:{1,2,... ,n}→{+,−}} μ(⋃_{i=1}^{n} A_{i}^{δ(i)}) ≥ 1 − 2^{−n}

where equality can be arranged for suitable A_{1}, …, A_{n}. To establish the equality in (5), we induct on n, with the induction hypothesis strengthened as follows (taking μ to be the uniform distribution over the power set of V = {1, 2, …, 2^{n}}) IH_{n}: there is a sequence A_{1}, …, A_{n} of subsets of {1, 2, …, 2^{n}} and an enu-

meration δ_{1}, δ_{2}, …, δ_{2^{n}} of functions from {1, 2, …, n} to {+, −} such

that for each j ∈ {1, 2,…, 2^{n}},
{1, 2, …, 2^{n}} − ⋃_{i=1}^{n} A_{i}^{δ_{j}(i)} = {j} .

The base case n = 1 is immediate. Next, assuming IH_{n}, define, for each i ∈ {1, 2, …, n},

B_{i} = A_{i} ∪ {2^{n} + j : j ∈ A_{i}}

and B_{n+1} = {1, 2, …, 2^{n}}. Then for each j ∈ {1, 2, …, 2^{n}},

\{1, 2, …, 2^{n+1}\} − (\overline{B}_{n+1} ∪ ⋃_{i=1}^{n} B_{i}^{δ_{j}(i)}) = \{j\}

{1, 2, …, 2^{n+1}} − (B_{n+1} ∪ ⋃_{i=1}^{n} B_{i}^{δ_{j}(i)}) = {2^{n} + j}

from which IH_{n+1} easily follows, and hence, the equality in (5). As for the inequality in (5), a function δ : {1, 2, …, n} → {+, −} verifying it (given any fixed sequence A_{1}, …, A_{n}) can be constructed by choosing δ(1) so that μ(A_{1}^{δ(1)}) ≥ \frac{1}{2}, and then δ(2) so that μ(A_{2}^{δ(2)} − A_{1}^{δ(1)}) ≥ \frac{3}{4} − μ(A_{1}^{δ(1)}), and so forth, the general pattern being that for every k ∈ {1, 2, …, n}, δ(k) satisfies

μ(A_{k}^{δ(k)} − ⋃_{i=1}^{k−1} A_{i}^{δ(i)}) ≥ 1 − 2^{−k} − μ(⋃_{i=1}^{k−1} A_{i}^{δ(i)}) .

□

3.2 A generalization of filters. To avoid (Half) and (Cov_{n}), we quantify away α as follows. Call H additive if it is α-sizable for some α. That is, H is additive iff for some probability function μ : F → [0, 1], and α ∈ [0, 1], H = {A ∈ F : μ(A) > α}. Rewriting (Up)_{⪯} (from §1), with μ(A) ≤ μ(B) in place of A ⪯ B, we get

(Up)_{μ} \frac{A ∈ H μ(A) ≤ μ(B)}{B ∈ H} .

Note, however, that unless we know what μ is, we cannot assert (Up)_{μ}. Could it be then that the best we could do to characterize additive families is to assert (Up)?

The following counter-example shows that there is more structure in additive families to account for.

(†) Let V ⊇ {1, 2, 3, 4} and H = {A ⊆ V : {1, 3} ⊆ A or {2, 4} ⊆ A}. Although H verifies (Up), it is not additive: were it induced by μ, then as {1, 3} ∈ H and {1, 2} ∉ H, μ({3}) > μ({2}); but as {2, 4} ∈ H and {3, 4} ∉ H, μ({2}) > μ({3}).

To strengthen (Up), some notation is useful saying (roughly) that a sequence A_{1}, A_{2}, …, A_{n} of sets in F is heavier than a sequence B_{1}, B_{2}, …, B_{n} (of equal length). With that in mind, let us write

∑_{i=1}^{n} A_{i} ≥ ∑_{i=1}^{n} B_{i}

to mean that for every a ∈ V,

∑_{i=1}^{n} χ^{A_{i}}(a) ≥ ∑_{i=1}^{n} χ^{B_{i}}(a)

where χ^{A} is the characteristic function of A (mapping elements of A to 1, and elements of V − A to 0). Now, consider the condition

(σ) for all sequences A_{1}, …, A_{n} and B_{1}, …, B_{n} ∈ F,

∑_{i=1}^{n} A_{i} ≥ ∑_{i=1}^{n} B_{i} implies (∃i ∈ {1, 2, …, n})
A_{i} ∈ H or B_{i} ∉ H .

(Up) is just the case n = 1 (as A_{1} ≥ B_{1} just means A_{1} ⊇ B_{1}). Example (†) above is handled by

\frac{A ∪ C ∉ H  B ∪ (C − A) ∈ H  A ∪ (D − B) ∈ H}{B ∪ D ∈ H}

which follows from the case n = 2.

Theorem 4. Assume F is finite. Then a family H ⊆ F is additive iff it validates (σ).

Proof. H is additive iff the inequality <_{H} given by (F − H) × H can be translated into a satisfiable system of linear inequalities as follows. Without loss of generality, let F = Pow(V) and V = {1, 2, …, n̂}. Fix an enumeration {(Â_{1}, B̂_{1}), …, (Âm̂, B̂m̂)} of (Pow(V)−H)×H, and observe that H is additive iff

(P) there exist real numbers x_{1}, …, xn̂ ≥ 0 such that

∑_{j=1}^{n̂} α_{ij}x_{j} > 0  for every i ∈ {1, …, m̂}

where for every i ∈ {1, …, m̂} and j ∈ {1, …, n̂},

α_{ij} = \{ \begin{matrix}1 & if j ∈ B̂_{i} − Â_{i} \\ −1 & if j ∈ Â_{i} − B̂_{i} \\ 0 & otherwise. \end{matrix}

Let A be the m̂ × n̂ matrix (α_{ij}), and appeal to the following well-known fact from linear algebra (e.g., Strang 1980, p. 333)

Either Ax ≥ b has a nonnegative solution x, or else there is a y such that yA ≥ 0, yb < 0 and y ≤ 0.

Passing from ≥ to >, (P) has the “dual” (D) there exist real numbers y_{1}, …, ym̂ ≥ 0, not all 0, such that

∑_{i=1}^{m̂} y_{i}α_{ij} ≤ 0  for every j ∈ {1, …, n̂} .

The reals in (P) and (D) can be assumed to be rationals, and after clearing the denominators to make the y_{i}’s in (D) positive integers, y_{i} can be taken to be the number of copies of the pair Â_{i}, B̂_{i} in (σ′) for all sequences A_{1}, …, A_{n} and B_{1}, …, B_{n} ∈ F,

(∀i ∈ {1, 2, …, n}) A_{i} <_{H} B_{i} implies

not ∑_{i=1}^{n} A_{i} ≥ ∑_{i=1}^{n} B_{i} .

Now, (σ′) is just the contrapositive of (σ). □

Remarks.

1. Theorem 4 is reminiscent of a theorem due to Kraft, Pratt and Seidenberg 1959, characterizing binary relations on finite Boolean algebras that can be read “at least as probable as.” That characterization is established again in Scott 1964, employing methods similar to that used in the proof of Theorem 4 above, although I do not see how to reduce Theorem 4 to the Kraft, Pratt, Seidenberg/Scott result, as the notion of an additive family quantifies away even more information than the comparative relation “at least as probable as.” Also, the “primal/dual” argument above applies more generally than “the general method” (Theorem 1.1) of Scott 1964.

2. Clearly, (σ) is satisfied by every filter H: taking the contrapositve (σ′) of (σ), suppose that for every i ∈ {1, 2 …, n}, A_{i} ∉ H and B_{i} ∈ H; then ⋂_{i} B_{i} ∈ H, and for every k ∈ {1, 2, …, n}, ⋂_{i} B_{i} ⊈ A_{k}, whence ∑_{i} A_{i} ≱ ∑_{i} B_{i}.

3. To force α ≥ \frac{1}{2}, it suffices to add a rule of non-empty intersection (considerably weaker than (And))

(NEI) \frac{A ∈ H  B ∈ H}{A ∩ B ≠ ∅} .

For α = \frac{m}{n}, with m < n, add the rule that for any sequence A_{1}, …, A_{n} that partitions V, there is a subset I of {1, …, n} with cardinality m such that

⋃_{i∈I} A_{i} ∈ H .

In yet another direction, the rule (Cov)_{n}, from Proposition 3(ii), adds the restriction that α < 2^{−n}.

4. To see that each case n − 1 of (σ) is insufficient, let V = {1, 2, …, n^{2}}, and, recalling the definition of <_{H} in the proof above of Theorem 4, consider

{1, 2, 3, …, n} <_{H}
{1, 2n + 1, 3n + 1, …, (n − 1)n + 1}
{2n + 1, 2n + 2, 2n + 3, …, 2n + n} <_{H}
{2, 2n + 2, 3n + 2, …, (n − 1)n + 2}
{3n + 1, 3n + 2, 3n + 3 …, 3n + n} <_{H}
{3, 2n + 3, 3n + 3, …, (n − 1)n + 3}
⋮
{(n − 1)n + 1, (n − 1)n + 2, …, n^{2}} <_{H}
{n, 2n + n, 3n + n, …, n^{2}} .

(Note that if the left hand sides are packaged as an n × n matrix A, then the right hand sides form the transpose A^{T} of A.)

4 Conclusion: directions from and applications to natural language. Although the approaches pursued in §§2 and 3 are compatible (insofar as (Up) and (And) imply (σ)), the thrust of §2 — viz., extending (And) — runs opposite that of §3, the canonical models of which, A_{pr,α}, fail to verify (And). Were we to adopt (And), then §3 would become uninteresting; were we to reject it, then §2 would become pointless. My reason for keeping the two sections in one paper is that I see no compelling argument that can (once and for all) settle the matter for or against (And). Intuitions about acceptability simply differ — intuitions expressed in languages, begging to be investigated. Among these are natural languages such as English, the semantics of which might be explored in the hope, for example, of shedding light on the acceptability of (And). The skeptical reader is bound to protest at such naiveté: natural languages are not formal; surely!

There is no denying that first-order logic is formal in a way that English is not. Even so, there is a growing body of work inspired by R. Montague’s slogan “English as a formal language” (1970/4), rephrased in more recent years as “Natural language as a programming language” (motivated by investigations into so-called “dynamic semantics,” going back to, among other papers, Kamp 1981). More concretely, generic sentences, such as “Birds fly,” provide a natural testing ground for questions about acceptability. And, in a slightly different direction, the very idea of formalizing, if not mechanizing, natural language leads to the problem of accepting exceptions. Briefly put, there is, I think, room for both §§2 and 3 in exploring the semantics of natural language.

4.1 Defeasibility in natural language interpretation. The transformation of “English as a formal language” into “natural language as a programming language” can be depicted by the equation

Natural language interpretation =

logic [e.g. model-theoretic semantics in Montague grammar]

+ control [e.g. choice of

formula/disambiguation] ,

the point being that some notion of “control” is required to formalize a natural language utterance before it can be subjected to a logical analysis. Moreover, that logical analysis may, in turn, feed back into how to formalize the natural language utterance (and so on). This suggests a broader construal of “logic” (as applied to natural language) than that traditionally associated with model theory. For instance, the resulting logic should, many argue, allow for defeasibility, a particular preferential approach to which, verifying (And), is pursued in Asher 1993 and Lascarides and Asher 1993. Integrating this with statistical/probabilistic information is an obvious task crying out for attention. Stepping back a bit, basic logical issues raised by the problem of control are discussed in Fernando 1996, where the challenge to compositionality posed by the context-dependence of disambiguation is taken up, and a logical approach based on generalized quantifiers is outlined.

4.2 A case study: back to many (naturally). Having derived much inspiration from Keisler 1970, let us close by noting that a linguistically motivated analysis of many not only calls the filter properties (sound for uncountably many) into question, but also introduces (at least) two other dimensions to the classical picture in Keisler 1970 (or, for that matter, in Westerståhl 1989): vagueness and intensionality. Passing from cardinalities to (vague subjective) probabilities over “possible worlds”, Fernando and Kamp 1996 propose to define there to be many φ-x’s iff the number of φ-x’s is more than what might be expected:

(Many-x)(φ) iff ⋁_{n≥1} ((∃_{≥n}x)(φ) ∧

Prob((∃_{<n}x)(φ))) (6)

where Prob is to be interpreted as an additive family H. A formal study of (6) within an intensionalized form of weak logic is currently being written up (with H. Kamp), drawing in no small measure on Theorem 4 above (which can be encoded within modal logic, in the manner of Segerberg 1971).

Acknowledgments. I am very grateful to N. Alechina, H. Kamp and M. van Lambalgen for helpful discussions.

References

N. Alechina and M. van Lambalgen. Generalized quantification as substructural logic. Journal of Symbolic Logic, 61(3), 1996. Nicholas Asher. Reference to Abstract Objects in Discourse. Kluwer Academic Publishers, Dordrecht, 1993. Jon Barwise. Admissible Sets and Structures. Springer-Verlag, Berlin, 1975. T. Fernando and H. Kamp. Expecting many. In Proc. Semantics and Linguistic Theory VI. Cornell University, 1996. Tim Fernando. Ambiguity under changing contexts. Manu-script, 1996. Preliminary version presented in Mathematics of Language 4 (Philadelphia, October 1995), and submitted for publication. J.Y. Halpern and M.O. Rabin. A logic to reason about likelihood. Artificial Intelligence, 32, 1987. Joseph Y. Halpern. An analysis of first-order logics of probability. Artificial Intelligence, 46, 1990. Hans Kamp. A theory of truth and semantic representation. In J. Groenendijk, T. Janssen, and M. Stokhof, editors, Formal Methods in the Study of Language. Mathematical Centre Tracts 135, Amsterdam, 1981. H. Jerome Keisler. Logic with the quantifier “there exist uncountably many”. Annals of Mathematical Logic, 1, 1970.

H. Jerome Keisler. Probability quantifiers. In J. Barwise and S. Feferman, editors, Model-Theoretic Logics, Perspectives in Mathematical Logic. Springer-Verlag, 1985.

C.H. Kraft, J.W. Pratt, and A. Seidenberg. Intuitive probability on finite sets. Ann. Math. Statist., 30, 1959.

Henry E. Kyburg, Jr. Conjunctivitis. In M. Swain, editor, Induction, Acceptance, and Rational Belief. D. Reidel, Dordrecht, 1970.

Michiel van Lambalgen. Natural deduction for generalized quantifiers. In J. van der Does and J. van Eijck, editors, Generalized Quantifier Theory and Applications. Dutch Network for Language, Logic and Information (Amsterdam), 1991. To appear in CSLI Lecture Notes.

A. Lascarides and N. Asher. Temporal interpretation, discourse relations and commonsense entailment. Linguistics and Philosophy, 16(5), 1993.

Richard Montague. English as a formal language. In R. Thomason, editor, Formal philosophy. Yale University Press, New Haven, 1974.

Judea Pearl. Probabilistic Reasoning in Intelligent Systems: Networks of Plausible Inference. Morgan Kaufmann Publishers, San Mateo, California, 1988.

Judea Pearl. From Adams’ conditionals to default expressions, causal conditionals and counterfactuals. In E. Eells and B. Skyrms, editors, Probability and Conditionals, Cambridge Studies in Probability, Induction and Decision Theory. Cambridge University Press, 1994.

Gerald E. Sacks. Saturated Model Theory. W.A. Benjamin, Reading, Mass., 1972.

Dana Scott. Measurement structures and linear inequalities. Journal of Mathematical Psychology, 1:233–247, 1964.

Krister Segerberg. Qualitative probability in a modal setting. In J.E. Fenstad, editor, Second Scandinavian Logic Symposium, pages 341–352. North-Holland, 1971.

Gilbert Strang. Linear Algebra and Its Applications. Academic Press, Orlando, 1980.

Dag Westerståhl. Quantifiers in formal and natural languages. In D. Gabbay and F. Guenthner, editors, Handbook of Philosophical Logic, volume IV. D. Reidel, Dordrecht 1989.