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(Pt1...tn) = T if <VA(t1), …, VA(tn)> ∈ V(P), and  VA(Pt1...tn) = 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.

The Continuum Hypothesis Without Set Theory

Regular readers may recall that a while ago I posted a fallacious proof of the continuum hypothesis. They may also recall that a bit more recently I tried unsuccessfully to understand forcing. Forcing is a technique for building models of set theories, which Paul Cohen used to show that the continuum hypothesis doesn’t follow from the ZFC axioms. (The ZFC axioms are the Zermelo-Fraenkel axiomatization of set theory plus the axiom of choice, and I’m told that most normal maths that can be proved at all can in principle be cast in terms of set theory and then its set-theoretic version can be proved from these axioms, if you feel the need to do that.) Anyway, in spite of the evidence that I’m not very good at it, I’ve been thinking about the continuum hypothesis again.

The continuum hypothesis, for those of you who don’t know but are still reading, is the proposition that the number of real numbers is the second smallest infinite number. It’s been proved that the number of integers is the smallest infinite number, that the number of real numbers is bigger, and that there is a second smallest infinite number. Georg Cantor conjectured that the number of real numbers was the second smallest, Kurt Gödel proved that the continuum hypothesis was consistent with the ZFC axioms, and Paul Cohen proved that it didn’t follow from them. So we’ve established that the ZFC axioms, even if true, don’t settle the question. And in the time since Cohen finished the independence proof, set theorists have learned a great deal more about which axiom systems do and don’t settle the continuum hypothesis, which models it is and isn’t true in, and the relationships between them. (I don’t understand this work myself: in order to understand it I’d have to understand how forcing works, and I’m sorry to report that I still don’t.)

Now, some people respond to this situation by saying that the continuum hypothesis (CH from now on) is indeterminate. This might be because they think that the notion of a set corresponding to ZFC doesn’t pin down a particular model, and CH is true in some and not in others. It might be because they think there are multiple set-theoretic universes out there, and CH is true in (or of) some of them but not others. It might be because they think mathematical truth basically amounts to provability, and we know that neither CH nor its negation is provable. Or perhaps they think the indeterminacy comes in somewhere else, for example as fundamental metaphysical indeterminacy.

Some people are set-theoretic Platonists, who think there’s a real, determinate universe of sets out there, and that even though we don’t know enough about it yet to prove that CH is true or false in it, CH is nonetheless true or false in it. To settle the question we would have to learn things about the set-theoretic universe that don’t follow logically from what we already know about it. How exactly we’d go about learning something like that is a vexed question, but (so the story goes) we have already managed to learn some things about it that don’t follow from nothing, so perhaps we could pull off the trick again. I’ve heard something like this view attributed to Gödel, though I’m not sure how fair a reflection of his views what I heard was, or how badly I’ve garbled what I heard.

I’ve got a certain amount of sympathy with this kind of view in principle, but I don’t agree with it. I think sets are made up, and that makes me a fictionalist about sets. I don’t think that integers and real numbers are made up, and my attitude towards them probably makes me a Platonist about those. I sympathize with the Platonist view about CH in principle because I’d be happy to take this attitude towards mathematical entities I didn’t think were made up. But it’s not my view because I do think sets are made up. In fact, the more I hear about sets, the more made up they sound.

Sometimes we talk about things being true or false in fictions, and I think that’s a reasonable way to talk. It’s true in the relevant fictions that Miss Marple solves crimes, for example. I think that there are a few fictions relating to set theory, and that we have pretty tight rules for establishing what is and isn’t true in several of these fictions. (Much tighter rules than we have for Miss Marple.) As is the way with fictions, sometimes the rules don’t settle what’s true in the fictions, and maybe sometimes nothing settles it at all. We tend to be more easygoing about indeterminacy in fiction than about indeterminacy in reality, and that’s probably fair. If you give a set-theoretic statement of CH, that will tend to be true in some of these fictions, false in others, and indeterminate in others. So you might think that a fictionalist about CH should think this is all there is to the truth or otherwise of CH.

Well, that’s not what I think. Take another look at what I said CH was, earlier in the post:

"The proposition that the number of real numbers is the second smallest infinite number."

The eagle-eyed and literal-minded among you will notice that this doesn’t mention sets. It mentions numbers. Since in this instance we don’t need to worry about uninstantiated numbers, we can cast CH without mentioning sets, or even mentioning infinite numbers:

"There aren’t any things such that there are more of them than there are integers but fewer of them than there are real numbers."

We’ll call this CHWS, for Continuum Hypothesis Without Sets. I think that when we ask whether the continuum hypothesis is true, this is the question we’re ultimately interested in, at least under the assumption that the integers and real numbers exist. But I expect that some set theorists will like to think of the set-theoretic formulation of CH as the continuum hypothesis, and that’s fine. I’ll try to sidestep the terminological issue by giving it a slightly different name: CHWS. In deference to these imagined set theorists, from now on I’ll use CH for their set-theoretic version.

I said earlier that I was a realist, and probably a Platonist, about integers and real numbers. That’s more or less true, in that it’s my working hypothesis even if I’m not fully committed to it. As I see it, if you’ve got some things, then it makes sense to talk about how many of them there are, and whether the number of them is infinite, and whether there are more of them than there are of some other things. And none of this presupposes the existence of sets. When you say there are more even numbers than prime numbers between 1 and 100 you’re saying something about numbers, not about sets. We’re able to give a precise explication of these notions in set-theoretic terms, and this explication serves for most purposes, but you might think that one lesson of the independence of CH from ZFC is that ZFC set theory can’t help us answer the question about how many real numbers there are. But if I’m a Platonist about real numbers, which I probably am, and I don’t think that there’s indeterminacy in how many of them there are, which I don’t, then CHWS can still have an answer. It’s just that set theory alone can’t help us find it. Perhaps sometimes when you ask whether there are more Xs than Ys this doesn’t always have a determinate answer, and so CHWS could be indeterminate for that reason. But I don’t see that anything we’ve learned about set theory compels us to think that. I think it’s a very strange idea, although the subject matter seems sufficiently strange that I should be open to the possibility, and so I am. But being open to the possibility that CHWS is indeterminate is very different from thinking it actually is indeterminate. And if I had to guess, I’d say it probably isn’t.

So in summary, here are the things I said I think:

• Sets are made up, so I’m a fictionalist about sets.
• Integers and real numbers aren’t made up: I’m a Platonist about those.
• We can make sense of questions about whether or not there are more Xs than Ys without understanding them in terms of sets.
• Sometimes those questions have determinate answers, and maybe they always do.
• The continuum hypothesis can be cast as a question about how many real numbers there are, without reference to sets.
• This question may have a determinate answer, and nothing about set theory gives us much reason to think it doesn’t.

As I understand it, this isn’t a popular combination of views, and I suppose it might even be provably incoherent. Perhaps there are people who could sensibly be confident that they could prove that it’s incoherent in an afternoon. But I’ve held these views as working hypotheses for a while now, and although I don’t think I’ve converted anyone, I also haven’t noticed them leading to any problems in the general pursuit of truth, so to speak. For somebody who has the information and interests I have, they make a livable position, and livability is a source of evidence in philosophy. But I do worry that I don’t understand the issues well enough to have earned the right to hold this combination of views. Maybe my taking a position on this stuff at all is pure hubris, and my foolish, incoherent position is a result of that hubris. Or maybe I’m more or less right, and my reasons for arriving at the position are sensible enough that being right is some kind of epistemic achievement. (Or maybe I’m entitled to a view, but am nonetheless wrong.) On the one hand the Enlightenment ideal is supposed to involve having confidence in your own rational capacities and making sense of things for yourself, instead of taking things on trust from people you’re told are authorities. On the other hand, that’s exactly how people end up posting flat-earth videos on Youtube.

So, am I being like a flat-earther? The unpopular part of my position, as I understand it, is that I’m a fictionalist about sets but I think CHWS may still have a determinate truth value. It seems to me that a couple of things differentiate me from the flat-earthers. One is that I’ve studied a lot of philosophy, including some philosophy of maths, and this should give me some protection against making really silly mistakes when thinking about this kind of thing. Another is that members of the academic establishment put quite a lot of effort into debunking flat-earthism, whereas nobody’s putting much effort into debunking the combination of set-theoretic fictionalism and realism about a version of the continuum hypothesis. Although like I say, I wouldn’t be all that surprised if a philosophically informed set-theorist with a free afternoon could do it. If there is a quick debunking to be made, the main pressure point seems to be the notion that we can make comparisons of infinite sizes without dealing with sets. More specifically, there’s the notion that we can make comparisons between uncountably infinite sizes without dealing with sets. Can we? It’s not obvious to me whether we can or not. Maybe that’s the question I need to answer before I’m allowed to have an opinion on this stuff.