I wold like to know what does it mean to say something is a set.

For me, any collection of elements is a set. Then this Russel paradox says collection of all sets is not a set.

All this came when looking at locally small categories. They are the categories where Hom class of any two objects is a set.

What is a set? What is a class? Do we loose anything if we assume all categories are locally small?

  • 2
    $\begingroup$ It sounds like you're trying to run "up the pyramid" too fast. Mathematics is an ultra-marathon of ultra-marathons, not a sprint. If you want to understand something, you need to spend more time with it. If you had the naive assumption that every collection is a set, then perhaps starting out by studying a bit more set theory is advisable before you move on to category theory. $\endgroup$ – Asaf Karagila Jul 24 '17 at 7:52
  • $\begingroup$ @AsafKaragila thanks for your suggestion. $\endgroup$ – user87543 Jul 24 '17 at 8:37
  • 6
    $\begingroup$ @Asaf Not sure I agree with that assessment: it's reasonable and productive to try to understand category theory concepts where objects and morphisms are naive "collections of stuff," and perhaps OP just needs to read from a different source. If someone was reading from a text that tried to distinguish right away between "small groups" and "large groups" that might be class-sized, would we tell them they need to learn set theory before algebra? $\endgroup$ – user231101 Jul 24 '17 at 8:39
  • 1
    $\begingroup$ @Mike: There's a reason why some set theory is being taught in the first semester, and category theory is being taught much much later (if at all) during undergrad. So yeah, I would say that some basic understanding of set theory is important for a lot of thing. And if someone is trying to understand the difference between small groups and large groups, then it is a good idea to understand some set theory. Because not doing so leads to mistakes, and leads to "fear of set theory" as some menacing evil limiting your steps in mathematics. And I've seen plenty of my teachers feel that way. $\endgroup$ – Asaf Karagila Jul 24 '17 at 8:42

Set theory makes a distinction between sets and classes in order to avoid Russell's paradox and related inconsistencies. Briefly, given any property of sets, you can form the class of all sets with that property. You can not do the same for sets: there is only a set of sets with a given property if you can prove it from the axioms of set theory.

We can make an additional philosophical distinction between sets and classes: while both sets and classes can contain elements, only sets can be contained as elements of these. It is possibly enlightening to consider a third possibility: some frameworks for set theory allow one to discuss "ur elements" which can be contained by sets and classes, but cannot themselves contain elements. (I suppose there's also a fourth possibility of entities which can neither contain nor be contained, but then there's no way for them to interact with anything.)

If we're working in a set-theoretic framework, we need to make these distinctions if we want to be precise, because Russell's paradox is real. As a way of thinking, it is sometimes convenient to "ignore" the problem, at least temporarily, but only when one believes the details can be worked out later.

Finally, regarding your question about the harm in assuming all categories are locally small, my answer is an unsatisfying "it depends." The vast majority of categories you run across in practice seem to be locally small, for sure, so it's often a harmless assumption. In my opinion, however, it's probably best to keep the abstract idea of a "category" somewhat fluid, and use a suitable notion for whatever context you're working with. That notion may often be "locally small category," but I think it's a harm to make that a rigid definition to the point where you reject working with anything that doesn't fit it. This question on Math Overflow may interest you.

  • $\begingroup$ Can you tell me in simple terms what is a class? $\endgroup$ – user87543 Jul 24 '17 at 5:57
  • $\begingroup$ @PraphullaKoushik "Class" is a primitive notion, like "set". One can axiomatize classes using, e.g., von Neumann-Bernays-Godel set theory, as mentioned in Derek's answer and described at en.wikipedia.org/wiki/… . $\endgroup$ – user231101 Jul 24 '17 at 7:06
  • 1
    $\begingroup$ @PraphullaKoushik Since it's primitive, axiomatizing is the only way to be precise. The "idea" the axioms are trying to capture, however, is just what I described: 1) classes contain sets as elements; 2) classes cannot be elements of either sets or classes; 3) whenever one has a property of sets in mind, there is a class containing exactly those sets satisfying the property. We talk about classes because (3) is convenient, but we run into Russell's paradox if we allow ourselves to form sets freely like that. $\endgroup$ – user231101 Jul 24 '17 at 7:09
  • $\begingroup$ @PraphullaKoushik: math.stackexchange.com/questions/172966, math.stackexchange.com/questions/139330, math.stackexchange.com/questions/469339, and probably a bunch of other questions. $\endgroup$ – Asaf Karagila Jul 24 '17 at 7:57
  • 1
    $\begingroup$ @MikeHaskel ok ok. This idea of axiomatising is giving me a better picture. Thank you.. $\endgroup$ – user87543 Jul 24 '17 at 8:41

Mike Shulman's Set Theory for Category Theory goes into this in probably more detail than you want.

For ZFC, a class is the extent of a relation in the ambient first-order logic. In other words, there is a one-to-one correspondence between predicates $\varphi$ and classes. Every set gives rise to a class because we can always defined the predicate $\varphi(x)\equiv x \in S$ for a set $S$, but there are predicates, such as $\varphi(x)\equiv \top$, the class of all sets, for which there is no set, $X$, that can be defined in terms of the ZFC axioms such that $\forall x. x\in X \Leftrightarrow \varphi(x)$.

Classes are a metalogical concept in ZFC. NBG (von Neumann–Bernays–Gödel) set theory has an explicit sort of classes which allows classes to be directly manipulated.

The category of locally small categories, what we usually mean by $\mathbf{Cat}$ is not locally small. This is easy to show: consider the endofunctors of $\mathbf{Set}$, i.e. $\mathbf{Cat}(\mathbf{Set},\mathbf{Set})$. Just considering constant functors already produces a proper class as there's a constant functor for each set.

Sometimes as with the notion of a Grothendieck universe (and also in a slightly different way in algebraic set theory), we simply declare some sets to be the "small" sets. In particular, we declare a set (the universe) to be the set of all "small" sets. In this formulation, sets that aren't "small" play the role of proper classes. Since a Grothendieck universe is a model of ZF set theory, it can't exist within ZF set theory or else ZF set theory would be able to prove its own consistency. A more powerful notion of set theory is needed if you want to have a Grothendieck universe be a set. One option is Tarsk-Grothendieck set theory which states that each set is a "small" set for some Grothendieck universe. This is way more than is needed for most applications of Grothendieck universes but can be useful for higher category theory.

The universe idea can also be explored from a type theoretic context. This is a different notion of "universe", but it serves much the same purpose.

  • $\begingroup$ +1, but I think the "category of locally small categories" is a misleading example. Its objects don't form a class, so it's not even a (large) category by the classical definition! $\endgroup$ – user231101 Jul 24 '17 at 5:24
  • $\begingroup$ Can you make it a bit simple.. i do not understand what do you mean when you say class is the extent of a relation in the ambient first order logic. I do not know what is predicate.. what is metalogical? $\endgroup$ – user87543 Jul 24 '17 at 5:52
  • $\begingroup$ @PraphullaKoushik Most of that terminology is covered in the syntax section of the Wikipedia page on first-order logic. ZFC is a theory within first-order logic. The first paper I linked also describes itself as assuming "some basic knowledge of category theory, but little or no prior knowledge of formal logic or set theory", though I think that's somewhat optimistic. I strongly recommend becoming familiar with at least the terminology of first-order logic. $\endgroup$ – Derek Elkins left SE Jul 24 '17 at 6:14
  • $\begingroup$ The extent of a predicate like $\varphi(x)\equiv x < 10$ is the items of the domain, say the natural numbers in this case, that satisfy the predicate, in this case the numbers 0 through 9. For the first-order theory of ZFC set theory, the domain is all sets and the extent of a predicate in that context would be the sets that satisfy it, e.g. a predicate like $\varphi(x)\equiv 3\in x$ would be all the sets that contain $3$. $\endgroup$ – Derek Elkins left SE Jul 24 '17 at 6:14

Well be prepared to have your mind blown. Not all "collections" can be called "sets" in a rigorous form of set theory, or else we run into paradoxes such as Russel's Paradox, where a set $A$ has itself as an element ($A \in A$), which unfortunately leads to so-called "naive set theory" (where every "collection" is a set) being inconsistent theory.

In set theory, this is typically resolved using the Zermelo-Frankel-Choice (ZFC) or Neumann-Berney-Godel (often called NBG) axioms. Basically, NBG is just a "conservative extension" of ZFC, and both treatments are equivalent. You can start reading about the ZFC axioms here and NBG axioms here (and the other answers provide even better references), but truly understanding such treatment involves having a pretty good handle on mathematical logic, which isn't necessarily required to understand small, large, and locally small categories.

Saunders Mac Lane (seen as generally the "standard" text of category theory) resolves the issue in a pretty informally simple way in Ch. I Sec. 6 (pg. 21-24) that is ultimately equivalent to ZFC, which I reference in my definition below. Essentially what is going on is we define the so-called "set of all sets" $U$ to be a collection with closure properties in a way where neither $U$ nor any other potentially problematic "collections" are included.

Definition. We define the collection $U$ as follows:

(i.) $x \in u \in U$ implies $x \in U$;

(ii.) $u, v \in U$ implies $\{u, v\}, \langle u, v \rangle, u \times v, u-v \in U$;

(iii.) $x \in U$ implies $\mathcal{P}(x), \bigcup x \in U$;

(iv.) $\mathbb{N} \in U$;

(v) if $f \colon a \to b$ is a surjective function with $a \in U$ and $b \subset U$, then $b \in U$;

A collection $a$ is a set if and only if $a \in U$ (note that these closure properties of $U$ are redundant, but sufficient as a criteria for determining which collections are sets).

A category $\mathcal{C}$ is small if $Obj(\mathcal{C}) \in U$, and large otherwise. Morever, $\mathcal{C}$ is locally small if for each $A, B \in Obj(\mathcal{C})$, we have $Hom(A, B) \in U$.

With the way this is set up, note that we can just talk about "small" and "large" categories in terms of naive set theory and get on with our lives. But I understand that this state of affairs leads to a bit of a predicament.

In particular, where you might be unsatisfied is the fact that I used "collections" and haven't exactly defined what those are, and that leads to answering second question, since a "class" is really what I've been calling a "collection" (and what category theory texts call "small sets") this whole time. I don't think you're ever going to be 100% happy (so much as 60% happy) with any definition you read of "classes" until you brush up on enough formal logic where you're comfortable looking at logic symbols. Because what separates "axiomatic set theory" from "naive set theory" is precisely the careful use of symbolic logic vs. treating any old collection with criteria $\{ x \colon \phi(x) \}$ as a set. There just isn't really a sufficient shortcut. But I'll do my best in terms of "informal logic" in the definition below.

Definition. A "class" is a logical statement $\Phi(x)$ with a variable $x$ (treated as any "set") in the "language of set theory". A given set $z$ is contained in a class if and only if the statement $\Phi(z)$ is true.

Such classes $\Phi$ define a set if there is some $z \in U$ such that $\forall x(x \in z \leftrightarrow \Phi(x)).$

Personally, I believe thinking of classes as simply logical statements that are separate and isolated from "sets" (as you'll find standard set theory texts often do more rigorously than I)--except when classes serve as legitimate "definitions" for particular sets--resolves a lot of annoying tension in your brain that distracts you from settling "more important" matters in mathematics.

The big thing to get is that it doesn't matter if the mathematical statements are regarded (in the "language" you're using) as sets or not. These "proper classes" can still be talked about as simply statements about sets. For example, the universal set $U$ can be denoted as the statement "$x=x$", which is always true for any set $z$. Another important example is the class $ON$ of ordinal numbers, where a set $x$ is an ordinal if and only if $\forall y (y \in x \rightarrow y \subset x) \land \exists z(z \in x \land \forall y(y \in x \rightarrow y \notin z))$. The class $Card$ of all cardinal numbers can be established similarly but defining the statement for it takes a quite a bit more work.

You can of course extend your "language of sets" to a "language of classes" (where the logical statements refer to classes instead of sets) and that way talking about classes is formalized "less awkwardly". This is the language that the NBG axioms operate on that conservatively extend ZFC in the language of sets. But you run into the same problems where you have statements about classes (such as again $x=x$ which is true for all classes) that can't be considered to define a "class", and we have the same issue all over again. That's why it's better to just appreciate the fact that everything you talk about in math can be written (in some weird way) in the language of sets and just move on with life.

And to answer your final (and arguably most important question in terms of category theory) we don't lose anything "important" to assume all categories are "locally small", since the goal of category theory is to generalize mappings. To do this, we need to be responsible in our distinction between "small" vs. "large" categories in category theory terminology (analogous to "sets" vs. proper "classes" in set theory terminology), so that we have $\mathbf{Set}$, $\mathbf{Grp}$, $\mathbf{Top}$, etc., with all the nice pretty functors between them, but without the paradox-related problems. However, you'll find not only $\mathbf{Set}$, $\mathbf{Grp}$, and $\mathbf{Top}$, but other large categories (such as $\mathbf{Rng}$, $\mathbf{K}$-$\mathbf{Vec}$, $\mathbf{Grph}$, $\mathbf{pTop}$, and even $\mathbf{Cat}$!) we care about are all "locally small". So we lose nothing in practical mathematics to conveniently assume that all categories are "locally small".

Sorry that it's a bit of a long post, and I hope this clears at least some of the confusion.

  • $\begingroup$ It is useful and cleared some confusion. Thank you $\endgroup$ – user87543 Jul 24 '17 at 17:29
  • $\begingroup$ No problem! And quick disclaimer: I read Derek Elkin's answer and we mean different things by $\mathbf{Cat}$. I think Mac Lane denotes $\mathbf{Cat}$ as the category of all small categories, which is locally small since $Hom(A, B) \subset Obj(B)^{Obj(A)}$ and $Obj(B)^{Obj(A)}$ is small. $\endgroup$ – Dark Logician Jul 24 '17 at 18:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy