# When is something too big to be a set?

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?

-
These large collections are called proper classes. There is an axiomatization of set theory (NBG: von Neumann, Bernays, Goedel) which allows proper classes as well as sets. But these have to be distinuguished from sets somehow to avoid Russell's paradox. –  Robin Chapman Jul 20 '10 at 18:06
Is this something related to things like "the class of all ordinals"? It lead to a paradox if it's defined as a set. –  Chao Xu Jul 20 '10 at 18:07
This is really a question for the set-theorists and logicians in here. I think they're really the ones that can give more then a hand waving response invoking classes. –  Andrew L Jul 20 '10 at 18:10
When Frege first tried to axiomatize arithmetic, one of his axioms was (something like) for every property P, there exists a set of all things that satisfy P. He then defined n, in essence, as the set of all sets having n elements (only his version was not circular). Then Russell wrote him a letter pointing out that this axiom allows us to form the set of all sets that are not elements of themselves, leading to a contradiction. When you say something like "the set of all___," rather than "the set of all ___ contained in the set Y," you are implicitly using Frege's faulty axiom. –  Charles Staats Jul 20 '10 at 21:52

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.

-
A similar example is in metric geometry: given two compact metric spaces $X,Y$, one can define the Gromov-Hausdorff distance $d_{GH}(X,Y)$, which is some nonnegative real number. Since $d_{GH}$ satisfies the triangle inequality, one often says something like "$d_{GH}$ is a metric on the set of all compact metric spaces". Technically, that set is "too big." But it turns out that a compact metric space has at most a certain cardinality, and so by fixing a set $S$ of that cardinality, any metric space is isometric to some metric on some subset of $S$. –  Nate Eldredge Jul 20 '10 at 22:18
@Nate: indeed, and even the definition of $d_{GH}$ requires you to consider all possible isometric embeddings of $X$ and $Y$ into all possible metric spaces, so the 'too big' issue already occurs at this level. –  Thierry Zell Aug 11 '10 at 23:16
I still don't quite understand how it works exactly. For example, I want to define the tensor product as the universal object in B. But within ZFC, B is too big to form a set. So, the definition cannot be formulated in ZFC? –  Brian May 5 '11 at 14:34
The notion of a universal object in a "big" category is not a priori an affront to ZFC. This is because I can say "the tensor product of $V$ and $W$ is a vector space $T$ and a bilinear map $t: V \times W \to T$ such that for any vector space $L$ and any bilinear map $B: V \times W \to L$ the following diagram commutes..." without referring to the set of all vector spaces. Indeed, I can check that a given construction of $(T,t)$ has the appropriate property one bilinear map at a time rather than being forced to quantify over all bilinear maps (and therefore vector spaces) at once. –  Paul Siegel May 6 '11 at 21:45
In contrast, I can't define an equivalence relation on the objects of a big category and expect that there will be a "set of all equivalence classes" in ZFC. Instead I first have to construct an honest set whose elements are objects in the category and prove that every object is equivalent to one in the set (a statement which can be checked one object at a time). –  Paul Siegel May 6 '11 at 21:51

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.

-
"Assuming reasonable axioms, there is at least one bilinear map from V x W into any other vector space..." For example, the zero map. –  Daniel Litt Jul 20 '10 at 18:34
I wish I could +1 for content and +1 for General Nonsense. –  Willie Wong Jul 20 '10 at 18:42
@Daniel: It was late when I wrote that (still is when I write this) and I threw that line in as a foil to ward off the rapiers of the foundationalists. @Willie: my favourite incarnation of that joke is due to Flanders and Swann and I repeat it whenever I get the chance! –  Loop Space Jul 20 '10 at 21:22

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.

-
I like your last sentence very much. –  Antonio E. Porreca Jul 20 '10 at 20:08
I'd wondered for a quite a while how ZFC deals with this sort of issue (I know essentially nothing about modern set theory) and I'm delighted to see that the answer is so simple yet so informative. –  Ian Morris Jul 21 '10 at 10:02

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.

-

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".

-

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.

-

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.

-

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.

-
If you use the standard construction of functions via Cartesian products, how would you define a function that takes a set W as input? Otherwise, if you are talking about a more general kind of function (or functor), I don't see how you could build a set of such functions. Am I missing something? –  Sebastian Reichelt Jul 21 '10 at 20:58
I edited to clarify what "function" means here. –  T.. Jul 22 '10 at 8:03
Thanks. But the author explicitly writes "Let B be the set of all bilinear maps defined on VxW" and then admits that B isn't actually a set -- and I don't see how anything you say would invalidate that claim. –  Sebastian Reichelt Jul 23 '10 at 16:31
As the author specifically stated a few lines above, and is also clear in that line by itself, what he intended to express and what is sufficient for his purpose is quantification over all bilinear maps B. That doesn't require any special care in set theory. Organizing the bilinear maps into a large mega-object is superfluous: reference to B being a "set" can simply be deleted and what he wrote becomes set-theoretically correct. So this is not a genuine example of running into set-theoretic complications; it is a superficial linguistic addition of sets to a set-free problem. –  T.. Jul 23 '10 at 19:24