Sunday, May 6, 2018

Comparing Size Without (Much) Set Theory

At the end of my last post, I said that I’d like to know whether it’s possible to make sense of there being more Xs than Ys when there are uncountably many of each, without using set theory. I’m not a proper mathematician, as I expect will become painfully apparent to any proper mathematicians reading this, but I’ve tried to hack something together that might sort of work. It uses plural quantification, which George Boolos (1984) has argued isn’t set theory in disguise. It does use some actual set theory too. But hopefully it’s a start.

Georg Cantor, and apparently David Hume before him, came up with a rule for comparing the sizes of infinite collections. If the Xs and the Ys can be paired off one-one, then there are the same number of each. If the Xs can be paired of one-one with some of the Ys, there are at least as many Ys as Xs. In set theory, you can use this idea to make a nice precise open formula expressing that a set x is at least as big as a set y, in terms of there being another set z that represents this one-one pairing. The usual way is to make it a set of ordered pairs with one member from each of x and y, having previously said what it is for a set to count as an ordered pair.

Since this set-theoretic version of “at least as big as” relies on there being a set in the model to represent the correspondence whenever there is such a correspondence, you can sometimes get models that don’t give the results about which sets are bigger than which that you intuitively might think they ought to. That’s how you end up with things like Skolem’s paradox, which is the puzzle of how set theories that say (under their intended interpretations) that there are uncountably large sets can have models with only countably many things in the domain. We can sort of ignore this here, although if you know a lot more than I do about Skolem's paradox it may help to keep it in mind.

Suppose I want to do this pairing thing without set theory. One thing I could do is take “at least as many” as primitive, so I’ve got a predicate Xs ⪰ Ys, which takes plural terms on both sides, and is true just when there are at least as many Xs as Ys. That’s not really legitimate for this project though, because the good standing of the concept is exactly what we’re trying to establish. What I’ll suggest is that we use just enough set theory to make comparisons of size, but not all the extra stuff that leads to indeterminacies in which model we're talking about and whether or not the continuum hypothesis is true in it.

What do we need to define “Xs ⪰ Ys”? We’ve already got plural quantification, outsourcing the defence of its set-theoretic innocence to Boolos, as is traditional. What I’m suggesting is adding just ordered pairs of things which aren’t themselves ordered pairs, and then saying that there at least as many Xs as Ys whenever there are some ordered pairs representing a one-one correspondence between some of the Xs and all of the Ys. And then you throw away the ordered pairs again, since ordered pairs are fictional and all.

So, you start off with the model M you’re interested in, and you want to extend it to a model M+ with Xs ⪰ Ys defined in it. To do that, you take another model N which is the same except you add in a bunch of ordered pairs. Whenever there are one or two things in the domain of M, there are the ordered pairs of them in N. None of the ordered pairs are duplicated, and there’s nothing else in N. Then you can define Xs ⪰ Ys as being true in M+ iff it’s true in N that whenever there are some ordered pairs Ps such that nothing is the first of more than one p in Ps, and nothing is the second of more than one p in Ps, and all the firsts of a p in Ps are in Xs, and all the seconds of a p in Ps are in Ys, and all the Ys are the second of some p in Ps.

I’ve tried to be careful not to introduce any general set-theoretic stuff in the definitions, except for the ordered pairs. The idea is that given a model M of plural logic without ⪰, we can always pin down a unique model N, and then we can define a new model M+ of plural logic with ⪰ in terms of M and N. The M+ models constructed in this way are the admissible models for plural logic with ⪰. The way this definition goes is supposed to be unaffected by what is and isn’t true about the universe of sets out there, if it even is out there, and in particular it’s unaffected by the truth or otherwise of the set-theoretic version of the continuum hypothesis. This means we should be able to express the non-set-theoretic version of the continuum hypothesis that I talked about in the last post, purely in terms of plural logic and without leaving any hostages to set theory.

A potential source of problems is that the model theory for plural logic, just like the model theory for most things, tends to be given in terms of set theory. Can you avoid that, and just give it in terms of plural logic? I sort of expect you could, perhaps with a little extra stuff but way short of full set theory, although I’m not sure whether this is something anyone has taken it upon themselves to do. The idea would be that instead of saying things like “a model M is an ordered pair <D, V> where D is a set of objects and V is a valuation function”, you say “a model M is defined by some things the Ds, which are its domain, and…”. (This is the point at which it becomes difficult.) If set theory does turn out to be indispensible to the model theory, then there will always be a suspicion that the definitions are hostage to set theory. It’s a little bit like the problem of doing the model theory for non-classical logics in classical logic, or giving a model theory for variable domains modal logic without committing yourself to a possibilist ontology. I don’t really want to get into this debate because in debates like this there’s always a danger you’ll find Tim Williamson on the other side.

So, I’m not going to present a non-set-theoretic semantics for plural logic, and I’m also not going to defend the set-theoretic innocence of plural logic with a set-theoretic semantics. But when I try to formalize the method for constructing the M+s, I’ll try to mention sets as little as possible. In particular, the ordered pairs in the domain of the intermediate model won’t actually be ordered pairs. But the domains will be sets, and the extensions will be sets of ordered n-tuples of objects and/or sets, the way you’d normally do it if you weren’t worried about set theory. The idea is that if plural logic can be set-theoretically innocent unless the subject matter happens to be sets, then this construction is set-theoretically innocent too. The model theory helps us clarify what we're saying, but you still only have to commit to the entities in the domains.

Here’s the syntax of the language L. It doesn’t have ⪰ in it yet; adding that will make L+.
  • Singular names a, b, c, etc
  • Singular variables x, y, z etc
  • Plural names C, D, E, etc
  • Plural variables X, Y, Z etc
  • Predicates P, Q, R etc, which can be any finite number of places ≥ 1, and which can be singular or plural in each position.
  • A binary “one of” predicate <, singular in the first position and plural in the second.
  • A binary “among” predicate ⊑, plural in both positions.
  • A binary identity predicate =, singular in both positions. (Plural identity can be defined in terms of = and < in the normal way if need be. (Our language L can't express many-one identities, even though regular readers will recall that I think some many-one identities are true.)
  • Atomic wffs composed out of predicates and names or variables in the normal way.
  • Compound wffs composed from wffs and & and ¬ in the normal way, with other connectives defined as normal.
  • Quantifiers ∃ and ∀. ∃! is defined as a unique-existence quantifier in the normal way.
  • If φ is a wff and v is a singular or plural variable, ∃vφ and ∀vφ are wffs.

Now the semantics:
  • A model M is an ordered pair <D, V> where D is a set of objects and V is a function on members of L.
  • An assignment A is a function from singular variables to members of D and from plural variables to non-empty subsets of D.
  • If t is a singular name, VA(t) = V(t) ∈ D.
  • If t is a singular variable, VA(t) = A(t) ∈ D.
  • If t is a plural name, VA(t) = V(t) ⊆ D, and must be non-empty
  • If t is a plural variable, VA(t) = A(t) ⊆ D, and must be non-empty
  • If P is an n-place predicate, V(P) is a set of n-tuples <o1, o2, …, on>, where oi ∈ D when P is singular in the ith place, while oi is a non-empty subset of D when P is plural in the ith place.
  • V(<) is the set of ordered pairs <x, y> where y is a subset of D and x is in y.
  • V(⊑) is the set of ordered pairs <x, y> where y is a subset of D and x is a subset of y.
  • V(=) is the set of ordered pairs <x, x> where x is in D.
  • If P is an n-place predicate and t1 … tn are terms, then VA( = T if <VA(t1), …, VA(tn)> ∈ V(P), and  VA( = F otherwise.
  • The values for & and ¬ are assigned truth-functionally in the normal way.
  • VA(∃vφ) = T iff there is an assignment B which differs from A at most in the value for v, such that VB(φ) = T, and VA(∃vφ) = F otherwise.
  • VA(∀vφ) = T iff all assignments B which differ from A at most in the value for v are such that VB(φ) = T, and VA(∀vφ) = F otherwise.
  • M(φ) = T iff VA(φ) = T for all assignments A, and M(φ) = F otherwise.
  • Σ ⊨ φ iff for every model M such that M(ψ) = T for all ψ ∈ Σ, M(φ) = T as well.

This is the basic logic. It isn’t supposed to be original. It’s supposed to be unoriginal, because if it was original I’d be in danger of having to defend its set-theoretic innocence myself, instead of outsourcing the job to Boolos. (I'm not sure if Boolos himself is the first person to formalize the model theory along these lines, but other people in the tradition use a set-theoretic model theory and lean on Boolos for the case for ontological innocence. I think they do, anyway. If I'm honest it's a long time since I read Boolos's paper. I think he says something pretty persuasive about how when you eat a bowl of Cheerios you're eating the Cheerios, not a set of Cheerios.) I felt it was important to write it down so you could see just how much set theory is involved, and what it's doing.

Now we construct a model M+ = <D, U> from a given model M = <D, V>. We start by constructing a model N = <E, W>.
  • E = D ∪ G, where G is the set of objects representing ordered pairs of members of D.
  • D and G are disjoint.
  • Introduce two binary predicates P1 and P2 which are undefined in M. These are singular in both positions. You can think of N as a model of an expanded language L*.
  • For every object x in D, there is one object y in G such that <x, y> is in W(P1) and W(P2).
  • For every two objects x and y in D, there is exactly one object z in G such that <x, z> is in W(P1) and <y, z> is in W(P2).
  • Nothing else is in G.
  • For every object x in G, <y, x> is in W(P1) and <y, z> is in W(P2) for only one y and only one z.
  • Nothing else is in W(P1) or W(P2).
  • Let A be an assignment on D, and let B be an assignment on E that extends A.
  • Now we define the extension of ⪰ in M+, that is U(⪰), in terms of the assignments A relative to which W evaluates an open sentence with two free plural variables X and Y as true.
  • Let φ be ∃Z[∀y(y<Y → ∃!z[z<Z & P1yz]) & ∀z(z<Z → ∃x[x<X & P2xz & ∀w[(w<Z & P2xw) → w = z]])]
  • U(⪰) = {<s, t>: WA(φ) = T for some assignment A such that A(X) = s and A(Y) = t}
  • In words, φ is meant to mean “There are some things [stand-ins for ordered pairs] such that every Y is the first of exactly one of them, and each of them has a distinct X as its second.”
  • Now we can say that a model of L+ is admissible iff it is the model M+ for some admissible model M of L.

That’s the proposal formalized. There’s a lot of set theory in the formalization, and indeed there’s so much that you could be forgiven for forgetting that I was trying to avoid set theory at all. But I was trying to avoid set theory. There are two things set theory is doing there. One is to construct the models of plural logic. I already said I wasn’t going to try finding a non-set-theoretic model theory for plural logic. The other thing is a very weak set theory that adds something equivalent to ordered pairs to the domains of the intermediate models (N in the construction), but the ordered pairs don't themselves form further ordered pairs. How should we interpret this? I think the most principled way for a fictionalist about sets like me is to interpret those models as representing a fiction. The fiction says that every one or two objects that aren’t themselves ordered pairs form one or two ordered pairs respectively. (So for every non-pair x there’s <x, x> and for every non-pair x and non-pair y there are <x, y> and <y, x>.) When it’s true in the ordered pairs fiction that there are some ordered pairs representing a one-one correspondence between some of the Xs and all the Ys, it’s true in reality that there are at least as many Xs as Ys.

The point of using the ordered-pairs fiction instead of the full-ZFC fiction is that the ordered-pairs fiction specifies a single fully determinate model N, given a model M for reality-minus-size-comparison-facts. You then use this to get a model M+ for reality-including-size-comparison-facts. Full ZFC doesn’t specify a single model, and the different models may have different one-one correspondences in them, which will give you different size-comparison facts. The models themselves are set-theoretic objects. I’m not sure how much of a problem that is. I think the kind of answer I’d like to give is along the lines people give for variable domains modal logic: we already understand plural logic, and the use of this model theory is just supposed to precisify which particular thing that we already understand we’re talking about. Someone who thinks you can’t understand plural logic without set theory won’t buy that, and those are the people I’m referring to Boolos.

Maybe a promising way around this would be to construct a model theory for plural logic along the same lines as the ordered-pairs fiction itself. There’s a whole lot of ZFC not being used in the model theory, so maybe you could have a much lower-powered fiction which could still do the job but didn’t have the underspecification you get with ZFC. I only have a vague idea of how that might go though, and there could be straightforward reasons why it wouldn’t work.

In closing I’d like to make it clear what my ambitions are. I claimed in my last post that we could understand a version of the continuum hypothesis independently of set theory. The continuum hypothesis without sets, or CHWS, is a statement about how many real numbers there are. To make sense of CHWS without using sets, we need to understand how there can be more Xs than Ys when there are uncountably many of each. Normally we do that using sets. I’ve been trying to show how we might do it while avoiding full ZFC and its indeterminacies, using only plural logic and the much lower-powered and more determinate fiction of ordered pairs. I’m trying to show that we can understand CHWS as something with a determinate answer, even if we’re fictionalists about sets. I’m not trying to offer any reason for optimism that we could ever settle CHWS. And if I had to guess, I’d say we probably never will.


  • Boolos, George (1984). To be is to be a value of a variable (or to be some values of some variables). Journal of Philosophy 81 (8):430-449.

No comments:

Post a Comment