Set Of All Sets

Now and then someone says the SetOfAllSets is dead. There is an easy proof of this, namely, that the SetOfAllSets would have to be in one-to-one correspondence with its power set (the set of all its subsets). Then [in ZF set theory] you can apply diagonalization to create a new set that can't be in the power set: for every A in the SetOfAllSets, put A in the new set iff A is not in the subset it is matched with. Et voila, a new set that can't be in the SetOfAllSets, a contradiction if ever there was one. But...

Our old (very old) friend MrAristotle had a good deal of trouble believing in infinite, and actually argued that it could not exist. The reason for this is that it satisfies all sorts of strange properties that no decent number ever could, like x+1=x and 2x=x (he also didn't believe in zero).

But, of course, infinite sets do exist (in what ever sense you think mathematical objects do). They just satisfy a reduced set of axioms. This leads to the possibility that, maybe, the SetOfAllSets (2^x=x) could exist if you reduced the axioms even more...

The reason for all this is that, from what I am told, CategoryTheory is the answer. A category is a lot like a set, but it isn't one, since category theorists want to talk about the category of all sets. But what's important here is that, from what I have heard, they also allow a category of all categories. If so, categories are basically the weakened sets suggested above.

Or so I would guess. -- JoshuaGrosse

I think most category theorists don't worry too much about foundational issues. SaundersMacLane?'s book has a brief discussion of "small categories" (ones that can live inside your favourite variety of set theory) but pretty much ignores the issue otherwise. Categories aren't "weakened sets"; the axioms for categories are very different from those for sets.

: Aren't foundational issues what CategoryTheory is all about?... Categories are pretty different from sets, but I was under the impression that whenever you had a set, you had some sort of equivalent category. Maybe not... feel free to change the above to something that makes sense. Today, I heard the term "class" as something categories are; maybe that's what I was looking for. In any case, the below does just as well:

There are varieties of set theory (most notably Quine's "NF") that do have a set of all sets. In NF, the reason why this doesn't give a contradiction is because what the Cantor argument turns out to give you is that V (the universe) is strictly bigger than the set of all singleton sets, and while you might think there's an obvious bijection (x <-> {x}) this isn't actually allowed in NF for technical reasons. So far as anyone knows, NF is about as likely to be consistent as any other sort of set theory.

: Can you hint how it works? Which x 's are not allowed to form singletons?--YauKwanKiu:

For any x, {x} is a singleton set. The thing is that the transformation from x to {x} isn't defined by a function that exists within NF. -- JamesDennett

[Older comments, from GoedelsIncompletenessTheorem... I think I have summarized most of this above, though.]

The problem is not with the set of all sets; rather, it is with the set of all sets that do not contain themselves, and the question as to whether this set contains itself.

No. The set of all sets is its own power set, and if diagonalizations can happen, that isn't allowed. But categories seem to work differently somehow.(?)

But that assumes that the set of all sets has the cardinality of the integers. Since it has the cardinality of the reals, then diagonalization can't be used to prove it doesn't contain itself. Hence, no problem.

No, you can do the diagonalization argument irrespective of the cardinality of the set. The set of all sets certainly doesn't have the cardinality of the reals, if only because it does not exist.

(Scott scurries away to do some reading and realizes just how wrong his statement was.) Thanks. Feel free to clean up this mini-thread.

A 'set of all sets' would have to contain, as a subset, a set of all sets that do not contain themselves. Hence, the impossibility of that set (if established) prevents one having a set of all sets. (But maybe there's a hidden assumption in this approach which implies the ZF approach.) -- vk

Indeed - And NewFoundations SetTheory admits an axiom of comprehension only for properties which are stratified (layered) so that they don't admit loops like this one. -- JamesDennett

I'm curious about cardinality. I understand, for example, that the cardinality of the rationals is the same as that of the integers; this is the canonical introduction to diagonalization. Diagonalization allows you to use a representational dimension as a trick to establish an infinitely-extensible (by induction) one-one mapping between two infinite sets. -- IanKjos

Discussion of TransfiniteCardinality moved to new page, concluding that the cardinality of reals is greater than any constructible cardinality. The same is true of the SetOfAllSets. Either:

1. the reals don't all exist (and I think they do {you must be one of those HardCorePlatonists ;-})
2. the SetOfAllSets cannot be dismissed by purporting that, because it contains itself and its power-set as strict subsets, its cardinality is unconstructible
3. SetOfAllSets is undecidable
4. my logic is flawed, and I'd appreciate knowing where.

PS: The set of all sets not containing themselves is the classic undecidable set. I challenge anyone to enumerate the set of all descriptions of undecidable sets. What would be its cardinality? -- IanKjos

You can show that in ZF, all sets have to be strictly smaller than their power sets, which excludes the set of all sets but does not in any way exclude the real numbers. That leaves open the possibility that things are different in non-ZF, but that doesn't seem to be what your comments are working with. I'm not sure what you mean by #3.

There is no set of all sets. However, there is a CLASS of all sets. Trickery, yes, but important trickery (or else we'd all dive into our own navels and vanish).

In axiomatic formulations of (now so-called "naive") set theory, there used to be a set-construction axiom to the effect that, for any proposition there was a set of all the objects satisfying that proposition. E.g. if S(x) means "x is a set", then this axiom says that there is a set "SS" which is a set of all x such that S(x). If this worked, then SS would be the set of all sets. However, this naive axiom blows up because letting N(x) mean "x is a set which doesn't contain itself" then gives you the set NS, all x which don't contain themselves, and then you need to decide whether N(NS) is true or false. bang.

There is a simple solution: change the set-construction axiom to a class-construction axiom. Every set is a class, but some classes are not sets. Then you say that, if you have a proposition P, there is a class of all x such that P(x). HOWEVER, it need not be a set. So Russell's Paradox boils down to a proof that NS is not a set, but a class. Poof, no more problem, and people can get back to doing math.

I'm not too strong on category theory, but as far as I recall, a category is a class together with some morphisms (read "well-behaved functions") between the objects in the class, provided that some axioms are satisfied. So you have to be careful not to assume that your category's objects form a set.

-- JamesWilson

Classes act pretty much the same way most people would intuitively expect sets to, so in considering them it would be better to treat them as replacements for sets. That is, the issue isn't whether a class of all sets exists, since it side-steps the self-membership entirely, but whether a class of all classes exists. Supposedly, it does.

The above amounts to saying that different (and better) axioms (for classes) can avoid problems arising in relation to sets. However, the Z-F axioms for set theory avoid the problems anyway.

ZF avoids the problems by simply not including a set of all sets. Sort of like the integers avoid the problems of infinite by simply not bothering with it. This is all well and good as far as it goes, but I don't think is quite the same thing as the death of the concept.

IanKjos makes too many points (some rather woolly (eg., does 'descriptions' mean 'finite descriptions using a finite set of axioms'? What does 'enumerate' mean in his context?)) to deal with here. Most can be settled by reference to any good textbook introducing the theory of finite and infinite sets.

-- VickiKerr

A good guide to SetTheory is NaiveSetTheory, by PaulHalmos?, ISBN 0387900926 . Oh, and a good way to show that the real numbers have the same cardinality as the power set of the integers uses a different way of looking at the reals. Consider the interval (0, 1). This has a trivial 1-1 correspondence with the reals. Now, for any x in this interval, take its continued fraction. The numbers appearing in this form a sequence of positive integers. The sequence is finite if x is rational, infinite if not. Map

  ()                    to ∅
  (a1, a2, a3, ..., an) to {a1, a1+a2, a1+a2+a3, ..., a1+a2+a3+...+an}
  (a1, a2, a3, ...)     to {a1, a1+a2, a1+a2+a3, ...}

Remember, no a here is zero. So, R ~ (0,1) ~ Sequences of positive integers ~ Sets of positive integers ~ Sets of integers.

-- EricJablow

I wouldn't object to the above-mentioned book as I own a copy. However, for a thin volume, its current price is excessive. -- vk

I have a copy too - that's why I thought of it. There are libraries. Now, when I was in grad school (20 years ago), we used to sell Categories for the Working Mathematician by SaundersMacLane? to each other for -0.50 USD. This tells you how much we loathed categories. -- ej

NewFoundations SetTheory (known as NF) does have a UniversalSet: a SetOfAllSets, and has never been shown to be inconsistent. Variations with "Urelemente" (atoms), that still have a UniversalSet, have been shown to be consistent. NF avoids all known paradoxes by restricting set-forming axioms to working with stratified formulae to avoid loops. Forming a power set is possible; applying a diagonalization argument to show that the power set P(x) of a set x is larger than x is not possible within NF (if NF is consistent). NF was originally devised by Quine, though his study of it was quite flawed. The set of all sets can exist. A book "Set Theory With a Universal Set" by T. Forster (my old lecturer) covers this in more detail, and is rather readable (if you've a good background in at least advanced undergraduate logic and set theory). -- JamesDennett

I did some more thinking about this. NF is OK but it would be nice to keep the bijection x <-> {x}, which it claims above isn't allowed in this new framework.

It is allowed. Cantor's theorem doesn't fail at that point; see below.

It occurs to me, though, that when you diagonalize this, the set you end up with is the set of all sets which don't contain themselves, which shouldn't exist. Is this the problem with the set of all sets in ZF, that it will necessarily contain this as a subset? Because I don't see why that should work. Of course here I mean ZF without the Axiom of Regularity, which looks specifically designed to keep the set of all sets out.

It is actually the Axiom of Separation in ZF that keeps the set of all sets out. In non-well-founded set theories without Regularity but with Separation, the proof that there is no SetOfAllSets (http://en.wikipedia.org/wiki/Cantor%27s_theorem) still goes through. In set theories without Separation (including NewFoundations and NFU), it doesn't:

"Let f be any one-to-one function from A into the power set of A. It must be shown that f is necessarily not surjective. To do that, it is enough to exhibit a subset of A that is not in the image of f. That subset is B = { x in A : x not in f(x) }."

But B need not exist in NF[U] because "x not in f(x)" is not stratified. That's OK; "x not in f(x)" is self-referential and not a sensible thing to want to express anyway. Stratified comprehension doesn't exclude any reasonable sets -- see <http://math.boisestate.edu/~holmes/holmes/fomletter3.txt>.

Actually, I don't really understand why people consider the Axiom of Separation to be uncontroversial. Stratified comprehension as used in NF[U] clearly prevents all self-referential paradoxes. Separation looks more like a hack that happens to get around the RussellParadox. -- DavidSarahHopwood