Wolfgang Schwarz :: (Unary) Numerical and Proportional Quantifiers

(Unary) Numerical and Proportional Quantifiers

Posted on Tuesday, 09 May 2006.

A quick Google search didn't come up with anything, so here are a couple of questions about the definability of certain unary quantifiers.

Just as all truth-functional operators are definable in terms of the Sheffer stroke, all numerical quantifiers are definable in terms of $$m[1]$ together with truth-functional operators and identity. By a numerical quantifier I mean a quantifier like "at least one", "at least two", "exactly 17", etc.: a quantifier Q such that the truth value of QxA(x) is determined by the finite cardinality of the objects satisfying A(x).

By the Skolem-Loewenheim theorems, this fact doesn't generalize to quantifiers for arbitrary cardinalities: "exactly aleph-0" is not definable in terms of the first-order $$m[1]$ . Though it is definable in terms of the second-order $$m[1]$ . So my first question is: which cardinal quantifiers are second-order definable? (Clearly not all, as there are far more cardinalities than second-order formulas.)

Curiously, $$m[1]$ itself is not a numerical quantifier in the sense defined above. Rather, it is a unary proportional quantifier: a quantifier Q such that the truth value of QxA(x) is determined by the proportion (among all objects) of objects satisfying A(x).

My second question is: how would a minimal basis for unary proportional quantifiers look like? $$m[1]$ is not a minimal basis, as, for instance, "at least half" is not definable in terms of $$m[1]$ . But "exactly half", "more than half" etc. are definable from "at least half" (e.g. exactly 1/2x are A(x) iff 1/2xA(x) and 1/2x~A(x)), and "at least 3/4" is definable from "at least 1/4" (at least 3/4x are A(x) iff not: at least 1/4x are ~A(x)). However, I think neither "at least half" is definable from "at least a quarter" nor vice versa. So do we need a primitive proportional quantifier "1/n" for each n?

Update 2006-05-11: For some reason, the end of the last paragraph got cut off. I've repaired it.

Comments

# Robbie Williams on 09 May 2006, 22:32

I don't have it to hand, but I think I remember that Stewart Shapiro's "Foundations without Foundationalism" has some stuff about relative strengths of systems of second order logic and first order logic+cardinality quantifiers.

# lumpy pea vest and armbands on 10 May 2006, 18:16

Which cardinal quantifiers are second-order definable?

By a second-order existential (Sigma-1-1) formula, the largest cardinality quantifier you can define is "there are countably infinitely many...". You can keep going up in cardinality but it becomes necessary to use second-order universal quantifiers. I imagine you can go as high as "there are aleph_n..." for finite n. That last sentence might be a really bad guess though.

I wonder what sizes of models up to isomorphism satisfy certain classes of SO formulas.

# Kim on 16 May 2006, 17:41

"how would a minimal basis for unary proportional quantifiers look like?"
I guess the set consisting of the 1st and 2nd order universal quantifiers is a minimal basis for proportional quantifiers. For example, you could define "at least half of all entities are A" as: there is a binary relation R such that for every x that is A there is at most one unique y such that Rxy and y is not A.

Any special reason why you're interested in this stuff??

# wo on 21 May 2006, 12:41

Thanks all! To explain, these questions just occurred to me when I was preparing last week's session on quantifiers for the philosophy of language class I'm teaching.

Robbie, that's exactly what I was looking for! Took a while to get my hands on the book again; it's in section 5.1.2. And Lumpy, you're right: all finite alephs are second-order definable; the definition is really quite simple: there are aleph-1 Fs iff 1) the Fs are not countable and 2) for any X, if all Xs are Fs, then the Xs are either countable or correspond 1-1 with the Fs; etc. Shapiro also shows the definability of "aleph-omega", "inaccessible", the finite beth-cardinals (via "the Fs have the cardinality of the powerset of the Gs") and a few others. He doesn't give an example of an undefinable cardinality. For more results, he points at S. Garland, "Second order cardinal characterizability", Proceedings of the Symposia in Pure Mathematics, 13 (1974): 127-46 and two articles by H. Hodes called "Cardinality logics" from 1988, but my curiosity for now is already satisfied.

Kim, yes, I also guess the proportional quantifiers are probably second-order definable. For instance, I think exactly n/m are F (for n < m and with all cancelations applied) iff there are distinct equipollent G_1, ..., G_m that together comprise all things such that some 1-1 relation R relates each F to some G_1 or ... or G_n. I don't see a single rule for "at least n/m" right now, but I'd be surprised if there is none. What I had in mind originally was a minimal basis of *proportional quantifiers* for all other proportional quantifiers. I still guess that would have to be infinite.

Wolfgang Schwarz

(Unary) Numerical and Proportional Quantifiers

Comments

Add a comment