When is something too big to be a set? - MathOverflow

When is something too big to be a set?

2010-07-20T18:02:26Z

Hello, recently, I've been reading some algebra and sometimes I stumble up on the concept of something "being too big" to be a set. An example, is given in (http://www.dpmms.cam.ac.uk/~wtg10/tensors3.html) , where he writes, "Let B be the set of all bilinear maps defined on VxW. (That's the naughtiness - B is too big to be a set, but actually we will see in a moment that it is enough to look just at bilinear maps into R.)" (where V and W are vector spaces over R). This is, too big to be a set, but why?

My general question is this, when is something too big to be a set? What is it instead? Why have we put these requirements on the definition? Do we run into any problems if we let, say, B as defined up there be a set? What kind of problems do we run into?

Answer by Andrew Stacey for When is something too big to be a set?

2010-07-20T18:26:24Z

The problem with

Let B be the set of all bilinear maps defined on VxW.

is that there is no mention of the target of these bilinear maps. Without specifying that (which appears to be the author's intention), one has to take bilinear maps into all vector spaces. The "collection" of all vector spaces is "the same size" as the "collection" of all sets, and the "set of all sets" is the Big NoNo in set theory (look up "Russell's paradox" on an online encyclopedia near you). Assuming reasonable axioms, there is at least one bilinear map from V x W into any other vector space so the "collection" of all bilinear maps on V x W is at least as big as the collection of all vector spaces, hence not a set.

But, as the author no doubt goes on to show, although one starts by wanting something representing all bilinear maps into anywhere, it's enough to work with bilinear maps into the ground field to get a-hold of the tensor product.

This crops up with many of these so-called universal constructions. You want something with nice properties relating to all other thingys lying around, but that's too big to deal with so you try to find an actual set which will do the job. Then you do the construction with respect to that set of thingys and, thanks that clever soldier General Nonsense, it turns out that it works for all thingys, not just the set you happened to think of.

Answer by Greg Kuperberg for When is something too big to be a set?

2010-07-20T18:44:03Z

To add to Andrew's answer: Something is a set when you construct it as one. In that sense, saying that something is too "big" to be a set is a bit misleading. It means: (a) You didn't construct it as a set in your axiomatic setting. (b) If you make a second level of set theory in which to study the first level, then externally it is a set, which is one meaning (I think) of the word "class". (c) "C is too big to be a set" means that every internal set has an internal bijection with a set which is a subclass of C.

If you take "class" to mean "external set", then it yields a simple resolution of Russell's paradox. The class of all sets that aren't elements of themselves is the class of all sets, since cycles are not allowed in the directed graph of set membership.

Answer by Simon Thomas for When is something too big to be a set?

2010-07-20T18:46:56Z

The cumulative hierarchy is defined inductively as follows:

$V_{0} = \emptyset$

$V_{\alpha + 1} = \mathcal{P}({V_{\alpha}})$, the powerset of $V_{\alpha}$

$V_{\delta} = \bigcup_{\alpha < \delta} V_{\alpha}$ if $\delta$ is a limit ordinal.

The $ZFC$ axioms essentially say that the set theoretic universe $V$ is the union of the $V_{\alpha}$, where $\alpha$ runs through the ordinals. It turns out that a collection of sets $X$ is a set if and only there exists an ordinal $\alpha$ such that $X \subseteq V_{\alpha}$. Thus $X$ is a set if and only if $X$ has ``finished being created'' before the entire universe is created.

Answer by Charles Stewart for When is something too big to be a set?

2010-07-20T19:31:09Z

I find the terminology of "too big" to be misleading. I think it comes about from thinking that the strength of a set theory comes from the generosity of its comprehension axioms, that stronger set theories can describe bigger things, and that the paradoxes come from bad comprehension axioms.

That this is naive one gets immediately from the existence of set theories that allow sets of all sets, such as Quine's New Foundations: comprehending over everything is as strong as it gets, and nothing can be bigger than the set of all sets, can it? In fact, though, NF without ur-elements is not a big theory: Thomas Forster has shown that the definable sets of the theory are those that can be got by taking a hereditarily finite set in ZF set theory, and replacing none, some, or all of its empty set "leaves" by the set of all sets.

And this shows a better viewpoint: set theories are "about" the structure over their definable elements, and the problem with the set-theoretic paradoxes is that they introduce inconsistencies into that structure. I'm sure real set theorists have more sophisticated viewpoints, although one does sometimes hear them talk about "too big".

Answer by Paul Siegel for When is something too big to be a set?

2010-07-20T19:40:14Z

I just want to give a refinement of other answers so far, as well as a different point of view (namely, that of a person who knows little about set theory but who also encounters these kinds of issues).

As others have mentioned, the root cause of the problem is that there are big logical problems with considering "the set of all sets". Unless you would like to learn more about set theory, you needn't concern yourself with what these problems are (though Russel's paradox is fairly elementary and kind of fun). It is just one of those facts of life that non-set theorists learn to live with and that set theorists learn to love. The non-existence of the set of all sets forces us to abandon other putative sets, such as "the set of all groups", "the set of all vector spaces", "the set of all manifolds", etc. For example, it is possible to equip any set with the structure of a group and so if we were able to build the set of all groups then we would necessarily have also build the set of all sets. This is almost always what people mean when they claim that a certain construction is "too big to be a set" - the construction invokes a sloppy use of set theory language that taken literally accidentally constructs the set of all sets as a byproduct. In your case, the existence of the set of all bilinear maps on $V \times W$ constructs as a byproduct the set of all vector spaces over $R$ (every bilinear map has to have a target), and if there were a set of all vector spaces over $R$ then there would be a set of all sets.

This is probably not the last time you will encounter this sort of issue. In basically every case, however, there is a trick that swoops in and saves the day. Generally the idea is to observe that you don't actually need all of the flexibility that you tried to give yourself by constructing a non-set, and that it is enough to consider a simpler object (in your case the set of all bilinear maps from $V \times W$ to $\mathbb{R}$) which is small enough to be a set but big enough to have the property that you want (in your case you want it to function as a sort of universal bilinear pairing between $V$ and $W$).

Ultimately I regard these sorts of concerns as analogous to the "end user agreements" that you have to certify you've read whenever you install a Microsoft product or sign up for a gmail account. I'm sure all that fine print is important, but I feel like I would have to become a lawyer to understand it all. And just as in that case, you don't have to be a set theorist to understand how to resolve these sorts of issues most of the time - usually it just requires you to capture the flexibility present in what you are already working on.

Just recently I was reading about an object which was given as the quotient by a certain equivalence relation of the set of all pairs $(T, H)$ where $H$ is a Hilbert space and $T$ is a certain kind of operator on $H$. The book pointed out that one cannot consider the set of all Hilbert spaces, but that the set theoretic difficulties can be resolved by proving that every pair $(T', H')$ is equivalent to a pair $(T, H)$ on a fixed Hilbert space $H$. So the problem was avoided by exploiting some inherent flexibility in the equivalence relation under consideration. This sort of behavior is quite typical.

Answer by Sebastian Reichelt for When is something too big to be a set?

2010-07-20T21:01:34Z

Just an addition to all the excellent answers, on a more informal and elementary level.

The question whether something is a set or not makes sense only if sets are treated as objects, i.e. if there is (conceptually) a "universe" which all sets reside in. This is indeed the case in first-order axiomatic set theory. In particular, in Zermelo-Fraenkel set theory, sets are actually the only objects (e.g. numbers are ultimately built from sets). Therefore, in ZF the question can be asked as "does a set/object with the following properties exist..." Other set theories have "proper classes" in addition to sets, as some have mentioned; then you can ask the question as stated.

However, in naive (i.e. non-formalized) set theory, it is far from obvious that sets should be treated as objects. For example, if the question whether "the set of natural numbers is a member of the Cartesian product of the real numbers and their power set" does not make sense to you, maybe you are not thinking of sets as objects at all. In that case, you might also consider Russell's paradox a meaningless combination of symbols. But there is one paradox which should still work; it's called Burali-Forti.

This paradox says that if you call equivalence classes of sets with well-order relations "ordinals," you can derive a contradiction by building an ordinal from the set of all ordinals. The most obvious remedy is to forbid the construction of the set of ordinals and other similar ones (or rather, specify exactly which sets can be constructed, such that the set of ordinals is not among them). So the convention in informal mathematics is to name the collection of ordinals something other than "set." But in principle, what really matters is that you don't try to build an ordinal from it. (And you wouldn't have done that anyway, right?)

The notion of "too big" sort of makes sense when looking at the Burali-Forti paradox because the contradiction follows from ordinal comparisons (which technically provides yet another remedy; see NF). However, I too consider it misleading, as it suggests that the question of whether something is a set is a question of fact rather than convention.

Answer by Theo Johnson-Freyd for When is something too big to be a set?

2010-07-20T22:50:49Z

Since we're talking about algebra, here's one important example where you really do care whether something is too big to be a set, and where the definitions are important.

Recall the notion of limit in category theory. A good example of a category with all "small" limits is the category VECT of vector spaces over a fixed field. Here "small" means that the limit is indexed by a (a category whose class of objects is a) set. For many purposes, it would be nice if the category of vector spaces in fact had all limits, i.e. limits indexed by arbitrary categories; and often for developing the ideas of a proof you can pretend that in fact all limits exist in VECT. Except that a classical theorem says that any category with limits as big as the number of objects is necessarily (equivalent to) a partially ordered set: a category in which between any two objects there is at most one morphism. This is clearly false in VECT.

For details, I recommend adjoint functor theorem in nLab.

Answer by T. for When is something too big to be a set?

2010-07-20T23:39:39Z

This has nothing to do with being "too big to be a set". There is no logical difference between the tensor product construction for vector spaces, and constructions such as $X \times Y$ or $S \to 2^S$ for sets. The latter don't raise questions of being unsetlike due to quantifying over all sets, because they aren't construed as extensional functions with domain the set-of-all-sets. Instead, they are function definitions in set theory, i.e., provable formulas of the form "for all $X,Y$, there exists a unique $Z$ such that ...".

For any sets $U,V$ and $W$ the collection of maps from $U \times V \to W$ is a set. The same is true if the sets have the additional data of vector spaces and the maps are required to be bilinear. "Bilinear maps from $U \times V$" can be construed as a function, or a functor, taking a set $W$ as input and producing the set of bilinear maps into $W$ as an output. This is well-defined and well within the realm of sets. (ADDED: this means that set theory can prove a set of maps exists as a function of $U,V$ and $W$; "for all $U, V, W$ there exists a unique $H$ such that ...".) There is also the construction of a universal object $W_0$ as the target of such bilinear maps, and the discussion of whether an unspecified collection of bilinear maps is too big may be just a way of motivating the generators-and-relations construction (which is big, but not too big or too vague to be a set).

Constructions that seem like they might bump against the ceiling of the universe of sets are dealt with by more technical means, such as Quillen's small object argument, or explicitly tracking the cardinalities that can arise. In this case it is a matter of pure linguistics and not of any object being gargantuan.