## Monday, 11 July 2011

### Roy's Fortnightly Puzzle: Volume 6

This one is easy to state, but hard, I think, to answer.

As we all know, the axiom of foundation (loosely speaking, that there do not exist sets with infinitely descending membership chains in their transitive closure, but usually formulated in a manner apparently custom-designed to confuse one's students) is a standard part of the machinery of ZFC. The question is: Why?

The answer, of course, depends on the role that we think ZFC should, and must, play. Here are some options:

Option 1: Foundation blocks the paradoxes, by ruling out the existence of non-well-founded sets such as the Russell set.

Worry: This is just insane. Full ZFC is, in some intuitive sense, more likely to be inconsistent for including foundation. In other words, if full ZFC (including foundation) is consistent, then ZFC-minus-foundation is consistent. (Another way to see the point: Adding foundation to Frege's Basic Law V, or any other formulation of set theory, doesn't make the resulting theory consistent - in fact, it might make contradictions easier to prove!)

Option 2: We are attempting to formulate the one true description of the unique set-theoretic universe. This universe is given to us informally by the iterative conception (as described by Boolos and others). Foundation follows on this conception.

Worry: If this is right, then one wonders why we also include the axiom of replacement (which, it seems to me, and seemed to Boolos, does not follow on the iterative conception of set). Also, one might wonder why the iterative conception is privileged in this way. There are other conceptions of set, including but not limited to the limitation-of-size conception, that don't support foundation.

Option 3: We are looking for the 'safest' reasonable looking set theory that will support the reconstruction of current mathematics.

Worry: Setting aside what 'safe' and 'reconstruction' amount to, we need some evidence that foundation plays any ineliminable role in such a reconstruction. After all, we could have a set theory that admitted various sorts of non-well-founded sets (either Aczel style or Forster style), and then just restrict our attention to the hereditary sets (those that can be built up from the empty set, loosely - see Boolos' stuff for exact details) and proceed as before. If there are no reasons for thinking we need foundation for our reconstructions, then any reasonable notion of safe will surely rank ZFC-minus-foundation as safer than ZFC.

Option 4: We are looking for the most powerful consistent set theory.

Worry: Well, this depends on what one means by 'most powerful'. Aczel's non-well-founded set theory is (if I am remembering correctly) equiconsistent with standard ZFC, but it admits far more sets. So why isn't this more powerful? At any rate, this just means we want one of either ZFC or ZFC-minus-foundation-plus-not-foundation (since either of these is more powerful than ZFC-minu-foundation), but doesn't seem to select between them.

Thoughts?

1. The consistency strength of ZFC with Foundation is the same as ZFC without Foundation, which is the same as the consistency strength of ZFC with Aczel's Antifoundation Axiom.

Given the general tendency of mathematics to eventually accept the existence of irrational, imaginary, nonstandard, irregular entities, my guess is that if ill-founded sets are useful enough, the meaning of "set" will expand to include them, with the well-founded sets as a special case. (If the ill-founded sets are not useful enough, then they'll join quaternions as an example of an attempted generalization that turned out in the end to be no more than a curiosity.)

2. I think the reason is that V = WF is simply a convenient restriction of the set theoretic universe, to well-behaved pure WF sets. One can add in the non-WF sets, if one likes, much as one can add ur-elements if one wishes - I predict this will become normal, as non-WF have useful applications in computer science and elsewhere. Barwise & Moss 1996 is a nice monograph on their applications.

3. Hi Roy and Jeff,

I have a naive question: suppose that we're onboard with the limitation of size type conception. So, no matter which sets we accept they can't be too big. In particular, the transitive closure of any non-well founded set will be equinumerous with some ordinal. My question is: in this case, can't we get the practical benefits of non-well-founded sets by simulating them in the well-founded sets?

Best,
Sam

4. Hi Sam, yes, you're right that one can interpret non WF sets into WF (interpret ZFA in ZF + foundation) . But it's not very natural, in my view: maybe it's like saying that given sets, we can interpret natural numbers, integers, rationals, reals and complex numbers as, respectively, finite vN ordinals (N), pairs thereof (Z), pairs thereof (Q), Dedekind cuts (Q) and pairs again (C), so needn't take them as "additional entities".

But my point is epistemological not ontological. I'm ontologically liberal, so ontological scepticism doesn't appeal to me; and I think the working scientist and mathematician has a similar policy - if a theory we introduce "works" (is coherent, explains things, improves our understanding of how thing fit together, accords with experience, etc.) then it's justified.

In that sense, I think ZFA might be argued to be an (epistemologically) better theory than ZF + foundation. But as you mention, the nay-sayer can insist that only WF sets are needed, strictly. They might even say the issue is verbal ...

5. Hi Jeff,

Thanks for the reply!

So, we want to say that it's unnatural to interpret the natural numbers as sets. Is there a good reason to think it's not unnatural to interpret the well-founded sets as (some of) the sets of ZFA? Or rather, do we have reason to think that the sets of ZF + foundation are some of the sets of ZFA?

Best,
Sam

6. Hi Sam, "do we have reason to think that the sets of ZF + foundation are some of the sets of ZFA?"

Seems right to me!

7. Hey,

Maybe I should have been clearer. What I was wondering is how we could claim, on the one hand, that arithmetic and ZF + foundation treat of different kinds of objects, but maintain that this is not true for ZFA and ZF + foundation (though one treats of more objects than the other).

I'm probably missing something very simple.

Thanks again,
Sam

8. angelweed: "(If the ill-founded sets are not useful enough, then they'll join quaternions as an example of an attempted generalization that turned out in the end to be no more than a curiosity.)"

I agree with the general points you make; but quaternions are used a lot in group theory!
Here's a mention of them today in connection with the group SO(3),

http://mathoverflow.net/questions/70154/matrix-expression-for-elements-of-so3/70160#70160

9. Hi Sam, "What I was wondering is how we could claim, on the one hand, that arithmetic and ZF + foundation treat of different kinds of objects, but maintain that this is not true for ZFA and ZF + foundation (though one treats of more objects than the other)."

Ah - I misunderstood. But this seems consistent to me.
Arithmetic is about numbers, not sets.
ZF and ZFA are both about sets (the latter, more).
Are those claims in tension?
Am I missing your point?

10. Oops - the "Am I missing your point?" at the bottom - that's from your comment, not mine!!

11. I think they might be, but I can't quite put my finger on why!

I think one worry I have is that ZF + foundation doesn't seem to be about the well-founded sets, but rather about all sets. And so too ZFA seems to be about all sets. But then they are straightforwardly incompatible.

(If ZF + foundation was simply a theory of the well-founded sets, we could have signaled this by restricting the quantifiers in the appropriate way.)

If that's right, then the fact that ZF + foundation and (we can suppose) ZFA work" should actually lead us to think there are two distinct universes of set-like things.

But maybe you think ZF + foundation doesn't work" in the way you indicate (i.e. if it's coherent, explains things, improves our understanding of how thing fit together, accords with experience, etc.)?

Then I'd be interested to know why. (One obvious thought would be that foundation isn't necessary - but then neither is A!).

12. Hi Sam, "I think one worry I have is that ZF + foundation doesn't seem to be about the well-founded sets, but rather about all sets. And so too ZFA seems to be about all sets. But then they are straightforwardly incompatible."

Right, yes - then ZF+foundation is mistaken, since it denies the existence of certain sets. Here's Mirimanoff on this. (See Aczel's book for this quote):

"Let E be a set, E' one of its elements, E" any element of E', and so on. I call a descent the sequence of steps from E to E', E' to E", etc I say that a set is ordinary when it only gives rise to finite descents; I say that it is extraordinary when among its descents there are some which are infinite." (Mirimanoff 1917)

I don't think that the fact that two logically incompatible theories both work (in the epistemological sense) to some degree implies the existence of two "worlds" for them to be about. Rather, there is one world - in this case V - and it means that one is mistaken (but perhaps in a local way). So, the question is: which is (epistemologically, mathematically) better?

13. Hi Jeff,

Thanks! That makes things a lot clearer for me.

So, there's one universe of sets, V, and our two theories say incompatible things about it. One must be wrong: the question is which. If we can determine which one is epistemologically or mathematically better, then that will provide good evidence for the truth of one of them over the other.

I take it that there is a fairly common sense in which they are mathematically equivalent (i.e. they are mutually interpretable). So that can't be the sense you have in mind.

And I also take it from what you say that they both work" in the sense you outlined.

Could you say a little more about what epistemological and mathematical criteria you have in mind?

Thanks again for all the help!

14. "I take it that there is a fairly common sense in which they are mathematically equivalent (i.e. they are mutually interpretable). So that can't be the sense you have in mind."

Right. Interpretability is too weak (e.g., we can interpret ZF in PA + Con(ZF)).

"And I also take it from what you say that they both work" in the sense you outlined."

The argument one has to give is to try and establish the following:

(C) ZFA is mathematically/epistemologically preferable to ZF with Foundation.

Some reasons might include:
(i) Foundation doesn't really do any work.
(ii) A mathematical reason: think of AFA as a completeness axiom (giving the solution lemma).
(iii) Epistemological reason: hypersets have wider applicability - we can model circular dependence.

15. I need to think more about this. Particularly about your (ii). On point (i): I'm not sure I see yet the sense in which foundation doesn't (really) do any work; and on (ii): having read Barwise and Moss's examples of circular phenomena (in their 1991), I just find the modifications needed to model them in ZF + foundation too simple to be worth worrying about. I'm sure there are more complicated examples that would require much more work, but I just haven't seen them yet.

Best,
Sam

16. Hi Sam, the argument concerning (i) is that Foundation doesn't play a role in core mathematics - defining N, Z, etc., geometry, functional analysis, etc.: these are all already well-founded.

17. Ah, I see. Is fair to say that anti-foundation also doesn't play a role in core mathematics?

Best,
Sam

18. Yes, I think it's fair to say that's so at the moment. So, this is where the action might (or might not) take place. If people in computer science (and related areas) doing discrete mathematics start invoking hypersets, taking AFA for granted, etc., then it will have moved into core mathematics. But I don't have a good sense of the extent to which this is presently the case. (I think it will be. But I could be wrong. Hypersets might go the way of non-standard reals.)