Posts Tagged ‘Set Theory’

h1

Size and Modality

March 25, 2009

There’s this thing that’s been puzzling me for a while now. It’s kind of related to the literature on indefinite extensibility, but the thing that puzzles me has nothing to do with sets, quantification or Russell’s paradox (or at least, not obviously.) I think it is basically a puzzle about infinities, or sizes.

First I should get clear on what I mean by size. Size, as I am thinking about it, is closely related to what set theorists call cardinality. But there are some important differences.

(i) Cardinality is heavily bound up with set theory, whereas I take it that size talk does not commit us to sets. For example, I believe I can truly say there are more regions than open regions of spacetime, even if I’m a staunch nominalist. Think of size talk as analogous to plural quantification: I am not introducing new objects into the domain (sizes/pluralities), I am just quantifying over the existing individuals in a new way.

(ii) Only sets have cardinalities. I believe you can talk about the sizes of proper class sized pluralities.

(iii) Points (i) and (ii) are compatible with a Fregean theory of size. But Fregean sizes, as well as cardinalities, are thought to be had by pluralities (concepts, sets) of individuals in the domain. In particular: every size, is the size of some plurality/set. I reject this. I think there are sizes which no plurality has – I think there could have been more things than there in fact are, and thus, that there are sizes which no plurality in fact has. So sizes are inherently bound up with modality on this view – sizes are had by possible pluralities.

(iv) Frege and the set theorists both believe sizes are individuals. I’m not yet decided on this one, but Frege’s version of Hume’s principle forces the domain to be infinite, which contradicts (i) – that size talk isn’t ontologically committing. Interestingly, the plural logic version of HP is satisfiable on domains of any size – thus size’s can be always be construed as objects, if needs be. But I’m inclined to think that size talk is fundamentally grounded in certain kinds of quantified statements (e.g., “there are countably many F’s”.)

I’m going to mostly ignore (iv) from hereon and talk about sizes like they were objects, because as noted, you can consistently do this if needs be (given global choice.) That said, I can’t adopt HP because of point (iii). It’s built into the notation of HP that every size is the size of some plurality. Furthermore, Hume’s principle entails there is a largest size. (Cardinality theory say there is no largest cardinality, but this is because of an expressive failure on it’s part – proper classes don’t have cardinalities.) However, if we accept the following principle:

  • Necessarily, there could have been more things.

it follows from (iii) that there is no largest size.

I think this is right. It just seems weird and arbitrary to think that there could be this largest size, \kappa. Why \kappa and not 2^\kappa? Clearly, it seems, there are worlds, that have this many things (think of, e.g. Forrest-Armstrong type constructions.) If not, what metaphysical fact could possibly ground this cutoff point?

What I don’t object to is there being a largest size of an actual plurality. I’m fine with arbitrariness, so long as it’s contingent. But to think that there is some size that limits the size of all possible worlds seems really strange. Just to state the existence of a limit seems to commit us to larger sizes – it’s like saying there are sizes which no possible world matches.

Here is a second principle about sizes I really like. Any collection of sizes has an upperbound. This is something that Fregean, and in a certain sense, cardinality theories of size share with me, so I’m not going to spend as long defending it. But intuitively, if you can have possible worlds with domains of sizes \kappa for each \kappa \in S, then there should be a world containing the union of all these domains – a world with at least Sup(S) things.

So this is what I mean by size. Here is the puzzle: this conception of size seems to be inconsistent. To see this we need to formalise a bit further. Take as our primitive a binary relation over sizes, < (informally “smaller than”.) For simplicity, assume we are only quantifying over sizes. Here are some principles. You can ignore 3. and 4. if you want, 1. and 2. are obvious, and 5. and 6. we have just argued for.

  1. \forall x \neg x < x
  2. \forall xyz(x<y<z \rightarrow x<z)
  3. \forall xy(x<y \vee x=y \vee x>y)
  4. \forall xx\exists x(x \prec xx \wedge \forall y(y \prec xx \rightarrow x \leq y))
  5. \forall x \exists y x<y
  6. \forall xx\exists x\forall y(y \prec xx \rightarrow y \leq x)

The first three principles say that < than is a total order, which is pretty much self evident. The fourth says it’s a well order. (The inconsistency to follow doesn’t require (3) or (4).) The fifth encodes the principle that there is no largest size, and the sixth says that every collection of sizes has an upper bound.

These principles are jointly inconsistent: let xx be the plurality of self-identical things. By (6) xx has an upper bound, k. By (5) there is a size larger than k, k<k+. Since k+ is in xx, and k is an upperbound for xx, k+ \leq k. Thus k<k by (2) and logic, which is impossible by (1).

There are roughly three ways out of this usually considered. Fregean theories reject (5), cardinality theory (with unrestricted plural quantifiers) deny (6) and indefinite extensibilists do something funky with the quantifiers (I’ve never really worked out how that helps, but it’s there for completeness.) Also note, the version of (6) restricted to “small” (roughly, “set-sized”) pluralities is consistent.

My own diagnosis is that the above formulation of size theory simply fails to take account of the modal nature of sizes. If we are pretending that sizes are objects at all (which, I think, is also not an innocent assumption), we should remember that just because there could be such a size, doesn’t mean in fact there is such a size. This is the same kind of fallacious reasoning encoded in the Barcan formula and its converse  (this is partly why it is very unhelpful to think of sizes as objects; we are naturally inclined to think of them as abstract, necessarily existing objects.)

Anyway – a natural way to formulate (1)-(6) in modal terms would be in a second order modal logic, perhaps with a primitive second level size comparison relation. For example (1) would be ‘necessarily, if the xx are everything, then there aren’t more xx than xx‘, (2) would be ‘necessarly for all xx, necessarily for all yy, necessarily for all zz, if there are more zz‘s than yy‘s and more yy‘s than zz‘s there are more zz‘s than xx‘s’ and (5) would be ‘necessarily, there could have been more things’. The only problem is, how would we state (6)?

I’ve been toying around with propositional quantification. Let me change the primitives slightly: instead of using \Box p, \Diamond p to talk about possibility and necessity, I’ll interpret them as saying p is true in some/every accessible world with a larger domain than the current world. Also, since I don’t care about anything about a world except the size of it’s domain, let us think of the worlds not as representing maximally specific ways for things to be, but as sizes themselves. Thus the intended models of the theory will be Kripke frames of the following form: \langle W, R \rangle where (i) the transitive closure of R is a well order on W, and (ii) for each w in W, R is a well order on R(w). (We’re going to have to give up S4, so we mustnt assume R is transitive on W, although it’s locally transitive on R(w) for each w in W.) Propositions are sets of worlds, so the range of the propositional quantifiers differ from world to world, since R is non-trivial.

Call R a local well order on W iff it satisfies (i) and (ii). I’m going to assert without defence (for the time being) that the formulae valid over the class of local well orders, will be the modal equivalent of (1)-(4) holding (I expect it would be fairly easy to come up with an axiomatisation of this class directly and that this axiomatisation would correspond to (1)-(4). For example, the complicated one, (4), would correspond to \forall p(\Diamond p \rightarrow \exists q\forall r(\Box(r \rightarrow p) \rightarrow \Box(q \rightarrow \Diamond r))).)

The important thing is that it is possible to state (5) and (6) directly, and, it seems, consistently (although we’ll have to give up on unrestricted S4.) [Note: I may well have made some mistakes here, so apologies in advance.]

  1. \Box p \rightarrow p
  2. \forall pqr(\Diamond(p \wedge \Diamond(q \wedge \Diamond r)) \rightarrow \Diamond(p \wedge \Diamond r))
  3. \forall p(\Diamond p \rightarrow \exists q\forall r(\Box(r \rightarrow p) \rightarrow \Box(q \rightarrow \Diamond r)))
  4. \Box\exists p(p \wedge \Diamond \neg p)
  5. \forall p \Diamond\exists q(q \wedge \neg p)

(I decided halfway through writing this post it was simpler to axiomatise a reflexive well order, so the modal (1)-(4) above don’t correspond as naturally to the original (1)-(4) – I’ll try and neaten this up at some point).

What is slightly striking is the failure of S4. Informally, if I were to have S4 I would be able to quantify over the universal proposition of all worlds, take its supremum by (6), and find a world not in the proposition by (5). This would just be a version of the inconsistency given for the extensional size theory above.

Instead, we have a picture on which worlds can only see a limited number of world sizes – to see the larger sizes you have to move to larger worlds. At no point can you “quantify” over all collections of worlds – so, at least in this sense, the view is quite close to the indefinite extensibility literature. But of course, the non-modal talk is misleading: worlds are really maximally specific propositions, and the only propositions that exist are those in the range of our propositional quantifiers at the actual world – the worlds inaccessible to the actual world in the model should just be thought of as a useful picture for characterising which sentences in the box and diamond language are true at the actual world.

Advertisements
h1

Cardinality and the intuitive notion of size

January 1, 2009

According to mathematicians two sets have the same size iff they can be put in one-one correspondence with one another. Call this Cantor’s principle:

  • CP: X and Y have the same size iff there is a bijection \sigma:X\rightarrow Y

Replace ‘size’ by ‘cardinality’ in the above and it looks like we have a definition: an analytic truth. As it stands, however, CP seems to be a conceptual analysis – or at the very least an extensionally equivalent charaterisation. In what follows I shall call the pretheoretic notion ‘size’ and the technical notion ‘cardinality. CP thus states that two sets have the same size iff they have the same cardinality.

Taken as a conceptual analysis of sizes of sets, as we ordinarily understand it, people often object. For example, according to this definition the natural numbers are the same size as the even numbers, and the same size as the square numbers, and many more sets even sparser than these. This is an objection to the right to left direction of CP.

I’m not inclined to give these intuitions too much weight. In fact, I think the intuitive principles behind these judgements are inconsistent. Here are two principles that seem to be at work: (i) if X is a proper subset of Y then X is smaller than Y, (ii) if by uniformly shifting X you get Y, then X and Y have the same size. For example (i) is appealed to when it’s argued that the set of evens is smaller than the set of naturals. (ii) is appealed to when people argue that the evens and the odds have the same size. Furthermore, both principles are solid when we are dealing with finite sets. However (i) and (ii) are clearly inconsistent. If the evens and the odds have the same size, so do the odds and the evens\{2}. This is just an application of (ii), but intuitively, the evens\{2} stand in exactly the same relation to the odds, as the odds to the evens. By transitivity, the evens and the evens\{2} are the same size – but this contradicts (i) since one is a proper subset of the other.

In fact Gödel gave a very convincing argument for the right to left direction: (a) changing the properties of the elements of a set does not change its size, (b) two sets which are completely indistinguishable have the same size and (c) if \sigma:X \rightarrow Y , each x \in X can morph its properties so that x and \sigma(x) are indistinguishable.  Thus, if \sigma is a bijection, X can be transformed in such a way that it is indiscernable from Y, and must have the same size. (Kenny has a good discussion of this at Antimeta.)

The direction of CP I think there is a genuine challenge to is the left to right. And without it, we cannot prove there is more than one infinite size! (That is, if we said every infinite set had the same size, that would be consistent with the right to left direction of CP alone.)

What I want to do here is justify the left to right direction of CP. The basic idea is to do with logical indiscernability. If two sets have the same size, I claim, they should be logically indiscernable in the following sense: any logical property had by one, is had by the other. Characterising the logical properties as the permutation invariant ones, we can see that if two sets have the same cardinality, then they are logically indiscernable. Since we accept the inference from having the same cardinality to having the same size, this partially confirms our claim.

But what about the full claim? If two sets have the same size, how can they be distinguished logically? There must be some logically relevant feature of the set which is distinguishing them, but has nothing to do with the size. But what could that possibly be? Surely size tells us everything we can know about a set without looking at the particular characteristics of  its elements (i.e. its non-logical properties.) If there is any natural notion of size at all, it must surely involve logical indiscernability.

The interesting thing is that if we have the principle that sameness in size entails logical indiscernability we get CP in full. The logical properties over the first layer of sets of the urelemente are just those sets invariant under all permutations of the urelemente. Logical properties of these sets are just unions of collections sets of the same size. Thus logically indiscernable sets are just sets with the same cardinality!

Ignore sets for a moment. The usual setting for permutation invariance tests is on the quantifiers. A variant of the above argument can be given. This time we assume that size quantifiers are maximally specific logical quantifiers. There are two ways of spelling this out, both of which will do:

  • For every logical quantifier, Q, Sx\phi \models Qx\phi or Sx\phi \models \neg Qx\phi
  • For every logical quantifier, Q, if Qx\phi \models Sx\phi then Qx\phi \equiv Sx\phi

The justification is exactly the same as before: the size of the \phi‘s tells us everything we can possibly know about the \phi‘s without looking at the particular characteristics of the individuals phi‘s – without looking at their non-logical properties. Since the cardinality quantifiers have this property too, we can show that every size quantifier is logically equivalent to some cardinality quantifier and vice versa.

I take this to be a strong reason to think that cardinality is the only natural notion of size on sets. That said, there’s still the possibility that the ordinary notion of size is simply underdetermined when it comes to infinite sets. Perhaps our linguistic practices do not determine a unique extension for expressions like ‘X is the same size as Y’ for certain X and Y. One thing to note is that the indeterminacy view seems to be motivated by our wavering intuitions about sizes. But as we saw earlier, a lot of these intuitions turn out to be inconsistent, so there won’t even exist precisifications of ‘size’ corresponding to these intuitions. On the other hand, if we are to think of the size of a set as the most specific thing we can say about that set, without appealing to the particular properties of its members, then there is a reason to think this uniquely picks out the cardinality precisification.

h1

Russell’s paradox and symmetry

September 24, 2008

Michael O’Connor has a very interesting post on symmetry as a way out of the set theoretic paradoxes. The paper he discusses uses this conception of set to motivate New Foundation like set theories. I haven’t fully absorbed the details, but if this can do for NF what the iterative conception or limitation of size does for ZFC, that would be pretty interesting, philosophically speaking…

h1

Which things occupy the set role?

September 21, 2008

Question: out of everything there is, which of those things are sets? A standard (platonist) answer would go something like the following: just those objects that are setty – those objects that have some special metaphysical property had only by sets. No doubt being setty involves being abstract, but presumably it involves something more – unless you’re a hardcore set theoretic reductionist there are non-setty abstract objects too.

I’ve been wondering about giving a more structuralist answer to this question: there is no primitive metaphysical property of being setty, rather, the sets are just whichever things happen to fill the set role. To get a rough idea, a model of set theory is just a relation R, (and by relation here I mean the things second order quantifiers range over.) Thus the set role is some third order property, F, which characterises the role the sets play. Since there will certainly be several relations satisfying the set role we have a choice: we can either ramsify or supervaluate. I prefer the supervaluational route here: it is (semantically) indeterminate whether the empty set is Julius Ceasar, but even so, it is supertrue that the empty set belongs to its singleton. More generally, a set theoretic statement \phi(\in) is supertrue iff \phi(R) is true for every R satisfying F, superfalse iff … and so on as usual, where an admissible precisification of the membership relation is just any relation R that satisfies F.

[Of course there may be no relations satisfying the set role. But presumably this will only happen if there aren’t enough things. On the ontological side, I’m just imagining there only being concrete things, and the more worldly abstract objects such as properties. I’m not assuming that there are any mathematical objects, but I am assuming there is a wealth of properties including loads of modal properties and haecceities. I’m also assuming the use of full second order logic, which we can interpret in terms of plural quantification over pairs, where pairs are constructed from 0-ary properties (e.g. <x,y> = the proposition that x is taller than y.)]

Ok, all that was me setting things up the way I like to think about it. The real question I’m concerned with is: what is the set role?

Several obvious candidates come to mind. Perhaps the most natural is that it satisfies the axiom of second order set theory F(R) = ZFC(R), i.e. R satisfies second order replacement and a couple of other constraints. One nice thing about this on the supervaluational approach, if you assume there are enough things, is that you can retrieve a version of indefinite extensibility: however long the ordinals stretch there will be a precisification on which the ordinals stretch further. In general this depends on F – depending on F there may be a maximal precisification. Whether there is a maximal precisification, when F(R)=ZFC(R), depends on how many objects there are to begin with (e.g. indefinite extensibility holds if the number of things is an accessible limit of inaccessibles.)

The problem with this view is that if the number of things is at least the second inaccessible it will be indeterminate whether the number of sets is the first inaccessible, since there will be at least two precisifications. However, it shouldn’t be indeterminate whether the number of sets is the first inaccessible, it should be superfalse – the set theoretic hierarchy is much bigger than that! Perhaps we can tag some large cardinal property onto the end of F. For example, F(R) = “ZFC(R) & Ramsey(R)”, that is, an admissible precisification of membership is one that satisfies ZFC + there is a Ramsey cardinal/there is a supercompact cardinal/whatever… But this seems just as unsatisfactory as before – why does any one LC property in particular encode the practice of set theorists? What is more, for obvious reasons there are only countably many large cardinal properties we can define is second order logic, which gives rise to the following complaints: (a) we might expect the size of the set theoretic universe to be ineffable – i.e. that it’s cardinality is not definable by any second order formula and (b) if sethood is determined by the linguistic practices of mathematicians, presumably it must meet some constraints such as definability in some finite language. Sethood must be a concept graspable by beings of finite epistemic means.

So here is the view I’m toying with: the sets must be maximal in the domain. The height of the set theoretic universe is not fixed by some static large cardinal property. Rather it inflates to be as big as possible with respect to the domain. This leads to some rather nice consequences, which I’ll come to in a second. But first let’s work out what it means to be maximal. Let R \leq S be the second order formula that says that R is isomorphic to an initial segment of S as a model of second order ZFC. Then just define

  • F(R) := ZFC(R) \wedge \forall S(R \leq S \rightarrow S \leq R).

Here are the nice things. Firstly, this is simple definable property. It also captures the intuition that the sets are ‘as big as they possibly could be’. But what is particularly interesting is that the height of the hierarchy is not some fixed cardinality – it varies depending on the size of the domain you start with. In particular, the height of the hierarchy varies from world to world. In a world where there are the first inaccessible number of things, the sets only goes up as high as the first inaccessible, but at worlds where there are more, the sets go higher. Add to this the following modal principle

  • Necessarily, however many things there are, there’s possibly more.

and it seems like we can defend a version of indefinite extensibility. That the set theoretic hierarchy could always be extended higher, can be interpreted literally as metaphysical possibility.

Two things to iron out. Firstly note that it follows from some results due to Zermelo that any two maximal models are isomorphic. Thus there is at most one maximal model of ZFC up to isomorphism, so no set theoretic statements will come out indeterminate. Secondly, we need to know if there will always be a maximal model. Obviously, if there aren’t enough objects (less than the first inaccessible) there won’t be a maximal model, as there won’t be any models. However, I’m assuming there are a lot of objects. Certainly 2^{2^{\aleph_0}} from just the regions of spacetime alone (which, by a forcing argument, is consistently enough objects for a model), but I’m also assuming there are lots of properties hanging about too.

More worryingly, however, there can fail to be a maximal model even when there are lots of objects. This was a possibility I, foolishly, hadn’t considered until I checked it. Let \kappa_\omega be the omega’th inaccessible. Obviously \kappa_\omega is not itself inaccessible because it’s not regular, and for every inaccessible less than it there is a larger one, thus for every model of ZFC there is a bigger one, and thus no maximal one.

So that’s a bit of a downer. But nonetheless, even if the size of the actual world is of an unfortunate cardinality, we can regain all the set theory by going to the modal language, where we have indefinite extensibility.