Monday, 13 June 2011

Roy's Fortnightly Puzzle: Volume 4

The axioms of separation:

For any set x and predicate F(...), there is a set y such that, for all z: z is a member of y iff (z is a member of x and F(z))

and of complement:

For any set x, there is a set y such that, for all z: z is a member of y iff z is not a member of x.

are incompatible with the existence of any sets. Proof:

Assume a set exists. Then by separation, the empty set exists. So by complement the universal set exists. So by separation, the Russell set of all non-self-membered sets exists. Russell's paradox follows.

So, we need to give up either separation or complement. Needless to say, standard mathematical practice has opted for the latter option.

The question is: Should we have? In other words, are there philosophically respectable reasons for thinking that it is complement, and not separation, that should be jettisoned?

Each of these principles corresponds to a natural intuition to have about the 'definiteness' or 'determinateness' of the results of certain set-forming operations. To put things in a bit silly terms:

Complement: If the sheep can be determinately isolated from the non-sheep, then the non-sheep can be determinately isolated from the sheep.

Separation: If the sheep can be determinately isolated from the non-sheep, then the black sheep can be determinately isolated from the non-black-sheep.

["non-black-sheep" here refers to anything that is not a black sheep, not anything that is a non-black sheep!]

The immediate answer that I usually get is that the intuition behind complement, but not the intuition behind separation, depends on the collection of all objects - the universal set - being determinate (so if the sheep are a determinate collection, than everything 'left over' is as well). But this strikes me as a little question-begging. After all, it is only our acceptance of separation (and of ZFC more generally) that throws the existence of the universal set into question. There are all sorts of alternative set theories (such as New Foundations or Boolos' DualV) that accept complement (and most of the standard ZFC axioms in the case of DualV) and hence accept the existence of a universal set.

So, what arguments can be given for the claim that it is separation and not complement that we should retain - arguments that don't depend on things like the iterative conception of set that already presuppose rejection of complement?

21 comments:

  1. Hi Roy,

    As I take it the point is that both Separation and Complement are equally motivated by our intuitions about `definiteness'. The correspond to the principles:

    (1) If xx are definite, then the non-xx are definite.

    (2) If xx are determinate, the the xx's which are phi's are definite. (Possibly, we assume here that `phi' is definite).

    In addition, there seems to be something like the following working in the background:

    (*) If xx are definite, then they form a set.

    Hence we get a paradox.

    My suggestion would be to reject the `definiteness' talk! Of course, it's enjoyed distinguished company in the past, but as far as I am aware it has never been properly explained (in the context of set theory that is), and always gets us into trouble.

    The point, as I see it, should be to replace the use of `definite' in (*) with something more tractable. That's what the iterative conception attempts to do (where `definite' is replaced by `formed before some stage', say). The iterative conception doesn't `presuppose' that everything isn't formed before some stage (i.e. isn't definite), it falls out of the conception.

    Of course, we might not be happy with the iterative conception for other reasons, but it seems to me that the methodology is right.

    What do you think?

    Best,
    Sam

    ReplyDelete
  2. Hi Roy,

    I'm a new subscriber, eager to soak up all I can about M-Phi. :)

    As a non-mathematician, but as a logician I find sets capable of the function of complement useful in starting from a metaphysics (first cause) which is casua-sui and then proceeding to develop a relative complement. I say this as more of an applied logician then a logician, because this can be used in computational logic to provide a foundation for a first-cause creating and implementing a complement (set of functions).

    ^^gut reaction.
    -------------------------------------------------
    Seperation,
    (some(x))->[[f:z is member of {y}]
    ->for all z, z is member of y iff z ~member of x]
    f(x)/:.(z&{y})

    Sets based on this can be used to construct universal variables in prolog using modules. So it's a hard choice to make...do I construct an entire model so it reduces to a single variable by deconstruction? Or do I simply write the mathematics of it directly into prolog using separation to build the architecture...

    -----------------------------
    Now I have a puzzle to ponder...thanks!

    ReplyDelete
  3. Sam: I'm not clear that it helps to reformulate the discussion in terms of plurals and definiteness.

    My first concern is that I am not sure that my (supposed) pre-theoretic intuitions, concerning Separation and Complements, are best expressed in these terms. Why aren't the intuitions just:

    (A) If we can talk about some things, we can talk about all the others.

    (B) If we can talk about some things, we can talk about only some of those things

    (V) If we can talk about some things, there's a set of exactly them.

    Of course, (V) is going to lead to inconsistency. But that just reminds us that our inchoate intuitions *are* inconsistent. So talking about "definite plurals" is already a step on the road to tidying up our inchoate intuitions, making them a bit less inchoate.

    Now, I agree with you that "definiteness", by itself, is only a tiny step away from inchoateness. So I take it that, when you say "the methodology is right", you mean that we need to move from the almost-inchoate notion of "definiteness" towards something more regimented. But:

    1. Couldn't we tidy up our inchoate intuitions about sets without ever going through the detour of plurals and almost-inchoate notions of definiteness?

    2. Even if we do want to replace the almost-inchoate notion of definiteness with something more regimented, we have no guidance as to *which* more regimented notion to employ. In more detail, whilst the almost-inchoate notion of definiteness could give way to the more regimented notion of iterativeness, it could equally well give way to other more regimented notions, such as:
    - limitation of size ("definiteness" becomes "not too big"):
    - stratifiable ("definiteness" becomes "can be comprehended by a stratifiable formula")
    etc.

    ReplyDelete
  4. This comment has been removed by the author.

    ReplyDelete
  5. Hi Tim,

    Thanks for the response!

    Just to be clear, I don't think we should go through `definiteness' at all! I was merely trying to restate what I took Roy to be saying.

    I take it that we want an answer to the following question:

    (*) When do some things form a set?

    We need not talk about `definiteness'.

    As to the plural talk: I'm just not sure how else to go about framing the debate. You ask why A, B, V might not better capture our intuitions here, so it looks like you are ok with the use of `some things'. Maybe the issue was with plural variables? If so, I'm happy to just replace xx with `some things'.

    On the question `why not other notions of set formation?': I absolutely agree. (*) could well be answered by these other notions. I didn't mean to suggest that the iterative conception was the only way of doing this, just that it is at least on the right tracks.

    I take it that your first point is something like this: while `definiteness' might not be helpful, we might still be able to get a version of Roy's problem with principles like A, B, V. However, I think that once we see answers to (*) not as attempts to satisfy the same inchoate intuitions that might motivate A, B, V, but rather as theoretical alternatives to those intuitions, then the problem loses its force.

    What do you think?

    Best,
    Sam

    Ps, can we get a contradiction from A, B, V without a form of plural comprehension?

    ReplyDelete
  6. Sam,

    Looks like I misunderstood you a bit; sorry! But regarding plurals, I'm in a few different minds. The following points may not be consistent, but here goes.

    1. I'm sympathetic to the view that "the debate" can't be formulated without plural talk. Here's my reasons for sympathy. As far as I can tell, "the debate" involves attempting to offer an analysis of some pretty inchoately intuitive pre-formal set-theoretic concepts. Since our desire is to offer some kind of an analysis, we'll want to offer it in non set-theoretic terms. Lacking the operation of set-formation, it's unclear that we then have a device for treating many things as one thing. But then the only way to talk about the things that are going to form a set is as many things. Hence the need for plural talk.

    2. But hold on! We *do* have a way to talk about many things as one thing; we talk about them "as a plurality" or "as a group" or somesuch. Plural logicians will get very angry if we read "some things" in this way. But I don't think I had either reading of "some things" particularly in mind in formulating (A), (B) and (V). I think generally it's pretty ambiguous which you mean in natural language too.

    3. But wait again! If we read "some things" as being a plurality (a many as one), then aren't (A), (B) and (V) close to being nothing more than statements of complements, separation and basic law V? In which case, aren't we as far away as ever before from answering Roy's question.

    Yes! But this is only further fuel to my mild scepticism about "the debate". If it's formulated with plural talk, but we're ambiguous about whether we're talking about many things or a many-as-one, then maybe we're saying something plausible about those intuitions, but it's hardly illuminating. If we insist that we're talking about many things, then it might be illuminating -- we can now rephrase questions in the plural locution -- but we end up offering a spuriously high level of technical precision to intuitions which were, ex hypothesis, inchoate.

    4. I'm likely being unfair; maybe "the debate" concerns only (*), and all other questions can be brushed aside. Well, I'm happy with the question posed by (*). It is a very good question. But it seems I can formulate it without plural terms:
    (#) What are the sets?
    I'm not sure why (*) is any better than (#) as a formulation (or vice versa, to be honest). And I entirely agree with you that our answers to (*) and (#) can be as theoretically motivated as we like.

    But I would caution against straying wildly from our inchoate intutions, or we don't get something answering to the name "set theory". (Indeed, if we don't cling to any of these intuitions, then our answer to Roy might well just be the pluralistic: "let 1000 flowers bloom".)

    All the best,

    Tim

    PS: I had in mind that (V) on its own is inconsistent, since it's too close to Basic Law V (i.e. I was viewing it as a comprehension principle). My argument runs thus: I can talk about the non-self-membered sets -- look, I did it just then, when I said I can talk about them -- so (V) yields a Russell set.

    ReplyDelete
  7. Hi Tim,

    Thanks for the response, it was really helpful.

    I have a few more thoughts on this which might help settle some of the questions you raise.

    So, suppose we read "some things" not as a many-one plurality but as many-many plurality. Then we can see that the contradictions which arise from our intuitions about "definiteness" and "talking about" rely essentially upon the principles about set formation which accompany them. In your case that was V, and in Roy's it was: if some things are definite, they form a set (or something similar). Without those principles, the other intuitions about "definiteness" and "talking about" aren't that problematic (unless I've missed something). So, it starts to look like any debate over complements and separation is premature. We should really be debating the underlying set formation principles.

    Very quickly we'll be engaging in the same enterprise that I take it the iterative conception of set is engaged in, i.e. answering (*). Decisions on complements and separation would then hopefully rest on our answer to that question.

    Suppose, on the other hand, that we read "some things" as a many-one plurality. I assume that these pluralities will be of the same type as the objects which can belong to them.* Then I think that the kind of plural comprehension involved in deriving a contradiction undermines the intuitions wholesale.

    You said that you thought V was inconsistent on its own, but it looks like you appealed to the fact that there is a plurality of the non-self-membered sets, which is an instance of plural comprehension. And Roy's argument, if framed with pluralities and put in terms of the definiteness principles, will need the same. But if we accept comprehension for plurals as objects, then we get a contradiction without the need to appeal to complements, separation, or set formation principles (using the Russell plurality)**. There seems little point in discussing arguments for or against intuitions framed using an inconsistent notion.***

    So, it looks like either the intuitions don't get off the ground, or if they do, the debate quickly changes focus and becomes one about different ways of answering (*) (or something similar). In that debate, there is still the question whether we need to frame it in terms of plurals and the question what place the original intuitions should have.

    My reasons for thinking that it is probably worthwhile to frame the debate in terms of plurals is pretty much what you say in your 1. It's not that I think the question is importantly phrased using plurals, it's just that I think solutions to the general question "what are the sets?" will need to avail themselves of something like plurals for the reasons you give.

    And I think that the inchoate intuitions, if they can be properly expressed, will be just one thing we need to take note of among many others in answering (*). (It's also not clear to me that it follows from disregarding them that we would then have no way to choose among the options (and thus relent and let a 1000 flowers bloom) - I assume there are lots of other considerations to choose from).

    Hope that makes sense.

    Thanks again for the discussion!

    Best,
    Sam

    *If not, then I'm not sure I see that the distinction between many-one and many-many pluralities is all that interesting.

    **You'll also need extensionality.

    ***Maybe you think that to push the intuitions even this far is too far - it is to ask too much of inchoate intuitions to choose between notions of plurality. I'm not so sure, though - maybe intuitions /that/ inchoate shouldn't be taken that seriously.

    ReplyDelete
  8. Wow. This is why I shouldn't go out of town. I miss great discussions that I instigated.

    To throw in my two cents: I actually find the plural stuff less helpful than most of the comments above suggest. Lots of complicated reasons, but the simplest has to do with (on standard treatments) plural talk doesn't allow for an empty plurality. As a result, if we start formulating the intuitions that lead us towards some set-theoretic intuitions and away from others, then we will likely lose the empty set (after all, the empty set doesn't contain objects you can talk about!) Of course, there is the standard Boolos trick to regain something like talk about the empty plurality, but it is just that - a trick (I tend to get suspicious whenever a framework is introduced in order to solve a problem or answer a question, but then an inordinate amount of work is needed in order to get that framework to deliver the results one wanted all along!)

    At any rate, what was really motivating my puzzle was my own confusion over why (mostly) we quickly reject complement in favor of separation. It doesn't seem like the plural understanding of the question favors separation over complement (once we realize we have both).

    Roy

    ReplyDelete
  9. SAM: I don't see why I am appealing to the fact that there is "a plurality of the non-self-membered sets, which is an instance of plural comprehension". Given how I've formulated (V), don't I just need to talk about the non-self-membered sets? Maybe I don't understand what you mean by "plural comprehension"; could you formulate it?

    Also, although you say I gave the reasons(!) I don't yet see why we will need to avail ourselves of plurals-talk to answer "What are the sets?" Surely "the objects described by the iterative hierarchy" is a good answer. Certainly that answer can be formulated using plurals (see Oliver & Smiley); but it can also be formulated without it (see anyone else).

    Is your point somewhat like Oliver & Smiley's, that we can't really ask whether our account of the sets does what we (initially) wanted from it, unless we use plural locutions?

    ---

    ROY: I agree. My main point was that putting matters in terms of plurals can't provide reasons to favour separation over complement.

    ReplyDelete
  10. Hi Tim,

    I haven't read Oliver & Smiley on this, so I'm not sure what they say. Though, thinking about it now, I've probably been a little too quick. What I should have said is that we need something like second-order resources. Then maybe argue for plurals as the best way of spelling out the interpretation of those resources.

    But you seem to be questioning something stronger. That is, why appeal to second-order resources at all. And it's that I question, because:

    "Since our desire is to offer some kind of an analysis, we'll want to offer it in non set-theoretic terms. Lacking the operation of set-formation, it's unclear that we then have a device for treating many things as one thing."

    If that's right, then although we could answer the question "what are the sets?" by "the objects described by the iterative hierarchy", once we ask what the iterative hierarchy is we'll need to appeal to "some device for treating many things as one thing" or simply avail ourselves of plurals.

    I take it, contra to that thought, you think the iterative conception can be formulated well without it (indeed that it is by most people). I'm not so sure about this.

    For instance, Boolos is obviously an exception. He says:

    "the full force of the [iterative] conception can be expressed in a second-order language extending L" (p92 LLL).

    And we know how he liked to gloss second-order resources. Also Shoenfield in "Axioms of set theory" appeals to the notion of "collection" which seems to be doing the same work as the plurals are in Boolos.

    Maybe you could point me to other places where this is spelled out without the use of second-order resources?

    On plural comprehension, I take it that the following is the relevant instance:

    There are some things such that x is among them just in case it's not a member of itself.

    Or, formally:

    ExxAy[y < xx iff ~(y \in y)]

    In general, I take plural comprehension to be the schema:

    ExxAy[y < xx iff \phi(y)]

    What do you think?

    ReplyDelete
  11. Hi Roy,

    I haven't thought much about the problem of empty pluralities in this setting, so will do!

    I also agree that plurals don't push us one way or another in the debate over complements and separation. If it sounded like that, I apologise.

    I do think the debate should be over conceptions of set, though (and the questions in this context: is there a good conception of set which motivates complements\separation?). Maybe this was the heart of your question anyway.

    I was thrown slightly by the use of "definiteness" and the claim that in answering your question we couldn't appeal to the iterative conception. If the debate is over conceptions of set, and the iterative conception is our best conception of set, then it looks like that is a great reason to give up complements (though I'm not saying it is our best conception of set).

    Best,
    Sam

    ReplyDelete
  12. Here's a conception of set to consider (off the top of my head, to compete with the iterative conception):

    Stage 0: We have all non-sets.
    Stage a + 1: We have any sets that can be obtained either by:
    (i) forming collections that only contain things found in previous stages.
    (ii) forming collections that only exclude things found in previous stages.

    (in other words, at each stage you can form sets of the form 'the set of blah blah' where all the blah blahs occur 'earlier', or you can form sets of the form 'all the things except for the blah blahs', where again the blah blah's occur 'earlier'.

    Of course, we have to get rid of the metaphor of 'constructing' the sets step by step, but since that is at best a metaphor (and at worst a hindrance to understanding what the universe of sets is really like) I am not sure that is a reason to reject this conception over the traditional iterative account.

    This conception will provide you with a set theory that opts for complement over separation, and (if formulated carefully) will give a set theory that is equi-consistent with the set theory provided by the analogous version of the traditional iterative conception.

    So: Why prefer the iterative conception to this conception?

    ReplyDelete
  13. Oh, and responding along the following lines:

    "But this conception presupposes that we can collect all the objects whatsoever together at once (right at step 1!)"

    is cheating - we only have reasons for doubting that we can collect together everything if we have already accepted something like the iterative conception instead of something like this (which would obviously provide a different diagnosis of the paradoxes than that suggested by iterative accounts).

    Of course, maybe it isn't cheating. Convince me ;)

    ReplyDelete
  14. Hi Roy,

    That's exactly the kind of thing I had in mind as a response to your question (suggested to me when I was discussing this with a friend).

    And I think, framed in terms of that conception v the iteratie conception, say, the debate is really very interesting. And it's something I need to think much more about!

    Here's a quick thought though: some people think that the Burali-Forti paradox puts pressure on us to accept an order-type of the collection of all ordinals. Although on the conception you suggest, we can have a set of all sets, I wonder if we can have an order-type of all ordinals.

    If we can't, then there seems to be a reason to pick the iterative conception over the one you describe, namely: we can extend the iterative conception to add the sets we want, we just add a stage in the process beyond any stages we considered previously. On the other hand, suppose we add a stage after all the stages of the conception you outlined: at that stage we'd have formed the universal set, and we'd take as our compliment the empty set. So we wouldn't actually add anything. We'd just go back through the process!

    Does that sound right? (Assuming we buy the motivation to extensibility from Burali-Forit).

    ReplyDelete
  15. Well, you certainly can't have the order type of the ordinals on my conception (not as a set, at least), but that isn't analogous to not having the universal set, but rather to not having the Russell set of non-self-membered sets.

    At any rate, I can tell an analogous story about what happens at the new stages when we extend my conception: In adding new stages, we don't get anything new in one sense, since the universal set was already there. What we get are more and more subsets of the universal set (although we never get them all). These were, of course, always in the universal set, but we couldn't 'get at them' individually until we extended the heirarchy.

    This is very loose, but I think it is right.

    I should admit at this point that I am formulating a (long-awaited!) account of how set theory works within the neo-logicist framework. It turns out that, on one way of viewing things, separation fails and complement holds for the neo-logicist. I don't want to give too much away (since I am still ironing out the details), but perhaps after I give this stuff as a talk (early July, at NIP in Aberdeen) I will post some of the material here.

    ReplyDelete
  16. Oh, and one last comment before I go home.

    Why can't we just formulate the debate here (or any debate for that matter) in terms of second-order logic where the second-order variables are understood as ranging over Fregean concepts (yeah, those mysterious 'unsaturated', not-objects entities).

    This isn't to say that plural quantification isn't coherent, isn't important, or isn't actually used in some cases. It's just to suggest that we don't need it.

    I'm serious.

    ReplyDelete
  17. Hi Roy,

    You're absolutely right on both accounts. I haven't argued for plural resources over any other kind of second-order resource (as I said in my response to Tim). I should really have framed what I said making that explicit (so sorry about that!). And also, on the account you sketch it's not at all clear to me now that you couldn't get a set of all ordinals if you add a stage.

    I am of course very interested to see how the details get worked out in full, so would really appreciate hearing about your stuff on this when it's ready.

    Best,
    Sam

    ReplyDelete
  18. Sorry, that should have been "You're right on both counts".

    ReplyDelete
  19. I suspect you won't ever get a set of all ordinals. At each point when you add a new stage, you will get the set of all ordinals up to that stage, but you will also get new ordinals (which could then be collected (or excluded) at the next stage after that, etc., etc.

    Nevertheless, you do get a lot of cool sets that you don't get on 'standard' accounts (like the set of all objects that are not finite ordinals, etc.)

    ReplyDelete
  20. Ah, I see. I think I misunderstood what you'd suggested.

    So, we have the universal set S, on this conception. And because the conception is supposed to characterise what it is to be a set, we will have that x is in S just in case it is `formed' at some stage in the hierarchy.

    Then it seems that we have two options (supposing we can make sense of the absolute generality talk):

    (1) We think that S is absolutely general, i.e. contains absolutely all sets.

    or

    (2) We think that S can be extended, i.e. there are sets which S `leaves out'.

    If (1), then we can't accept the argument that since the ordinals are well-ordered, they should have an order type. So, we'd need to resist that somehow. In general, we couldn't allow ``new stages", if these entail new sets.

    If (2), then I don't see why you couldn't literally allow stages beyond those you already have. I mean, ``the universal set" might just be the set of all sets which we currently quantify over. Then, if we added a stage, we'd quantify over more sets, and the complements part of the conception would be relative to that new universe. In particular, at the new stage, every sub-concept/plurality of S would form a set, as would each compliment of such sub-pluralities/concepts.

    In that case, we could have a set of all ordinals (where ``all" is relative to the previous universe), and resolve the Burali-Forti type worry. Your conception would be just as well equipped to deal with indefinite extensibility as the iterative conception.

    Does that sound right?

    ReplyDelete
  21. Sam,

    My intuition is that, on the rough conception I outlined above, we can always extend the conception by adding new stages. This doesn't mean, however, that we get a 'new' universal set at the new stage. Rather, the universal set we obtained at stage 1 remains the universal set, but once the new stages are added it, in some sense, contains more stuff (while remaining the same set as before).

    [And, at each stage, or universe, if you prefer, we get a set of all ordinals formed at previous stages, and a set of all sets formed at previous stages. But we never get a set of all ordinals whatsoever, and the set of all sets formed before stage m , which is formed at stage m+1, is never identical to the set of all sets, which is formed at stage 1].

    This, I think, is where the real problem with this conception lies. If we say that the universal set changes its membership as we add new stages, then we just verge near incoherence, at least if we want to claim that this conception provides a genuine notion of set (and not some other sort of entity).

    Better, I think, is to understand the universal set obtained at stage one as containing all the sets whatsoever, not just the ones that we have obtained at any particular stage. Thus, the universal set is itself indefinitely extensible in exactly the sense the entire hierarchy is, but obviously we would reject the claim that indefinitely extensible concepts don't form sets (and replace it with something like the claim that indefinitely extensible concepts whose complements are also indefinitely extensible don't form sets).

    We can explain the stages epistemically, perhaps: Each stage (and the sets formed at it) represent sets that we can know exist (and thus that are contained in the universal set). But we can always move to a higher stage, coming to know of the existence of new sets (and thus coming to know of additional members of the universal set that we obtained at stage 1).

    Anyway, as I said, this is early days, and I am still a bit unsure about all of this. I reserve the right to claim that someone hacked into my M-Phi account and posted the comments above, should I come to change my mind!

    ReplyDelete