# What exactly are the meaning of the followings in the definition of a category?

In Awodey's Category Theory a category is defined as follows.

A category consists of the following data,

• Objects: $A, B, C,\ldots$

• Arrows: $f,g,h,\ldots$

• For each arrow $f$ there are given objects, $$\operatorname{dom}(f),\ \ \operatorname{cod}(f)$$ called the domain and codomain of $f$. We write $f : A → B$ to indicate that $A = \operatorname{dom}(f)$ and $B = \operatorname{cod}(f)$.

• Given arrows $f : A → B$ and $g : B → C$, that is, with $\operatorname{cod}(f) = \operatorname{dom}(g)$ there is given an arrow $g \circ f : A → C$ called the composite of $f$ and $g$.

• For each object $A$, there is given an arrow $1_A : A → A$ called the identity arrow of A.

These data are equired to satisfy the following laws,

• Associativity: $$h \circ (g \circ f)=(h \circ g) \circ f$$ for all $f : A → B, g : B → C, h : C → D$.

• Unit: $f \circ 1_A = f = 1_B \circ f$ for all $f : A → B$.

My questions are,

1. What do we mean when we say that a category "consists of" something? Do the functions and objects "belong to" the category in some more general sense of $\in$ as in $\sf{ZFC}$?

2. Presumably, here Awodey talks of "collection of objects" and "collection of arrows" but what precisely is a collection here? Will it be sets? classes? or, something else?

3. What is(are) the difference(s) between data and laws?

4. As has been hinted in Q the Platypus's answer below, I think we may define a category to be a triple of obljects, arrows and composition. But then we need to know whether we are taking the notion of triple as a primitive notion. For if not, then naturally the question is, what is the definition of a triple?

• The discussion he gives in section 1.8 seems like it would be interesting to you. Most introductions to category theory are really more focused on building up a way of using the language to do some job and don't spend much time on any underlying set theory. – Hoot Jun 26 '16 at 3:42
• Unless you already are fluent in category theory, worrying about foundational material (like if ordered triples are provided by the ground set theory or not...) is really a bad idea. You are only making things more complicated for yourself, as it is harder to learn two things at the same time than it is to learn one. – Mariano Suárez-Álvarez Jun 26 '16 at 4:09
• @MarianoSuárez-Alvarez I think it can be much harder to learn one loosely formulated thing than two precisely interconnected things. The actual reason to ignore foundations is that they're not really written down anywhere well, nobody really cares to teach them well, and working mathematicians will outright pressure you to spend your time proving new theorems and solving problems than learning the foundations of it all... – Vladimir Sotirov Jun 26 '16 at 5:00
• @VladimirSotirov, there are infinitely many more generally useful things to spend your studing time on that the meaning of «consists of the data...» or whether triples are defined using Kurratowski's construction or otherwise. – Mariano Suárez-Álvarez Jun 26 '16 at 6:13
• Foundations of X is a subject different and usually almost disjoint from X itself, for almost all values of X. – Mariano Suárez-Álvarez Jun 27 '16 at 2:10

This question is not really about category theory itself (though category theory is the first subject in which the issue you are running into cannot be easily swept under the rug). 1. and 2. could be equally well asked of set theory and basic algebra

1. "In what way does the collection of all sets consist of sets?"
2. "What are collections of sets actually?"

Slightly more subtle is 3. but it can be asked in algebra

1. "What is the difference between declaring a group to be a set equipped with a binary multiplication operation so that every element has an inverse, vs. declaring a group to be a set equipped with a binary multiplication operation and a unary inversion operation (both structures with the appropriate axioms)?"

The answers to 1. and 2. is that you have to set up some theory that allows you to talk about collections. The standard theory do this with is first-order logic, in which every formula with free variables is a description of a collection (aka a class), and these collections may also be described by auxillary functions and relations.

Set theory is then a particular collection with an auxillary relation called "belonging" ($\in$) that satisfies certain axioms (e.g. ZFC). We call the objects that constitute this collection sets.

Peano arithmetic is another collection, called the natural numbers, equipped with a designated object $0$ and special function called "successor" subject to certain axioms. This is different (but related) to the natural numbers considered as a set, because any set determines a collection of its elements with properties mirroring the properties of the set.

Categories in general are (or rather, can be presented as) a pair of collections in the above sense (collections described by formulas with free variables in first-order logic) known as the collections of objects and collections of morphisms, equipped with auxillary functions and relations between them (identity, domain, codomain, partially-defined composition), satisfying certain axioms (identity, associativity).

Things get complicated because if you also have a fixed set theory (e.g. ZFC), then you can build categories as the collections of elements of pairs of sets equipped with set-functions and relations that satisfy the appropriate axioms. These would be so-called small categories. A fundamental category is then the category of sets because traditional mathematics is built on top of it, so you have to study the interactions of set theory (i.e. the category of sets) with all the other categories, paying attention to which ones are small and which ones are large.

A further complication is that there is no class of all class functions, for the same reason there is no set of all sets. But there is a class of all class functions whose domain is a set, i.e. a small class. So, because categories can be large, when constructing categories and generally thinking about them you have to pay attention to size issues, to whether they are small (given by classes of elements of some set or not).

People find this to be annoying to deal with by hand, so instead they enlarge ZFC with an "axiom of universes", which asserts there is a set all of whose elements form a collection satisfying the axioms of ZFC. Such sets are then called small, the others called large, and you can then go through category theory without having to learn about first-order logic and only using this extension of ZFC in a naive fashion. Doing this, you no longer have a category of ALL sets, but you work instead with the category of small sets.

• I realize I didn't answer explicitly answer 3... data are the components (collections, relations, functions in first-order logic) and laws are the axioms (statements about how the collections, relations, and functions interact) that can be used to present a thing. Things can have multiple presentations, e.g. groups have many different axiomatizations. – Vladimir Sotirov Jun 26 '16 at 6:07
• But "collections" (or perhaps, more specifically domain of discourse)need not always be class, right? This means that we first need to specify the Theory of Collections for which we can say that the variables, in some sense, 'belong to' that collection. But then we need to specify a Theory of Collection at the outset for example to talk about first-order logic, then we can't use that logic as the underlying logic for our Theory of Collection. This process can be repeated indefinitely (well, I think so). – user170039 Jun 26 '16 at 14:22
• The question is, to avoid this infinite regression do we need to take a Theory of Collection as a primitive (ontological) notion? – user170039 Jun 26 '16 at 14:24
• The point is that you can view first-order logic itself as a primitive "Theory of Collections", hence avoiding infinite regress. We are not describing or postulating how actual collections behave, but we are describing the language by which we express or refer to the collections. The potential for regress lies in disagreeing on what it takes to specify a formal language (since of course, we never actually have access to ALL formulas unless there were only finitely many), but certainly specifying the rules for producing well-formed statements and the rules for judging them justified is – Vladimir Sotirov Jun 26 '16 at 23:30
• considered sufficient description: most humans seem to be expected to apply some sort of "pattern-matching" to the rules and to comprehend from them how to form well-formed statements (i.e. how to speak) and how to judge whether a statement is justified (what a proof is). So you don't to actually go ahead and develop a formal theory of languages before you can specify a formal language, but there is an important philosophical shift from mental to social activity in the level of justification required. – Vladimir Sotirov Jun 26 '16 at 23:33

To say that a category "consists of the data" means that in order to specify a category, one has to tell their reader exactly the data that lies inside the definition. For instance, a monoid consists of the following data: A set $M$; a binary operation $\circ:M \times M \to M$ that is associative, i.e., $\circ(g,\circ(h,k)) = \circ(\circ(g,h),k)$; and a distinguished element $e \in M$ called the identity that has the property $\circ(g,e) = g = \circ(e,g)$ for all $g \in M$. To give a monoid $M$ is to define all of these things simultaneously. Thus to say what a category consists of is to define what makes up a category. In this sense to say that something belongs to a category, we mean that it is an element of the object "set," has a corresponding identity morphism in the morphism "set," and satisfies the necessary identities with respect to composition. Here we need some notion of "set," but whatever theory you wish to work in will be appropriate; for instance, you can use ZFC, you can use some set theory involving some appropriate notion of a Grothendieck universe in which every "set" smaller than some fixed strongly inaccessable cardinal $\kappa$ is "small" and every other "set" is large, or even a strange model of set theory. The beauty of the elementary axioms of category theory is that they hold so long as your set theory can handle the quantification and universal instantiation that is necessary to give the required data. Note that we can move past the notion of a primitive universe, say such as the category $\mathbf{Set}$, by then moving through an enrichment process, i.e., we add to our set theory all the things we need to define a universe in which our theory makes sense. If you are interested in this theory, you may want to read some enriched category theory and learn about $\mathscr{V}$-enriched universes. Note that when you enrich your set theory, even though you have, say, a new way of sovling the halting problem, you now have a $\mathscr{V}$-halting problem that you will have to enrich again to fix. This problem occurs infinitely, and needs some sort of transfinite induction to really talk about precisely.

When Awodey talks about the collection of objects and the collection of morphisms, he means a "Set" in whatever relevant set theory you care about for the moment. For instance, when we define the category $\mathbf{Set}$, the collection of objects is not, in the sense of ZFC, a set: It is a proper class! However, in this case we simply acknowledge the fact that sometimes we need to move up a universe of set theory in order to work. Again we run into the topic of enrichment, which makes this topic precise. Many people in math, myself included, just take for granted that we live in some Grothendieck universe and eventually have to move into dealing with "large" categories. These categories generally behave strangely, but are extremely important. For instance, in algebraic geometry, if $X = (X,\mathcal{O}_X)$ is a scheme, then the category $\mathbf{\mathcal{O}_X-Mod}$ is (generally) a large Abelian category, while for any ring $R$, the category of left $R$-modules with nondegenerate $R$ actions is a very nice Abelian category, al. In fact, the celebrated Mitchell-Freyd Embedding Theorem tells us that if $\mathfrak{A}$ is a small Abelian category, then there is a full and faithful embedding of $\mathfrak{A} \to \mathbf{R-Mod}$ for some ring of unit $R$ that preserves exactness. This gives us the result that essentially means that if you are arguing with a finite diagram in an Abelian category $\mathfrak{A}$, then you may as well use modules and module theory in order to make your life easier. For the most part you can treat the object "Set" and morphism "Set" of a category as if they were sets, or elements of some enriched and larger theory where such things make syntactic sense. Just be careful: objects in a category need not be sets, and you cannot argue set theoretically about some things. For instance, if we are dealing with a large Abelian category $\mathfrak{A}$ and we have an infinite diagram that we need to deal with, such as a cohomology long exact sequence, then we CANNOT, at least in general, use Mitchell-Freyd and we must argue with universal properties and such, save for special cases.

To address your third question, the difference between data and laws is that laws, in this sense, are syntactic or algebraic rules that MUST hold at all times, while data can vary. For an example, note that the categories $\mathbf{FinSet}$ of finite sets and $\mathbf{FinGrp}$ of finite groups have varying data: the morphisms in $\mathbf{FinSet}$ are very different from the morphisms in $\mathbf{FinGrp}$; however, the morphisms satisfy the same basic composition laws ($f:A \to B$ and $g:B \to C$ gives a composition $g \circ f:A \to C$), the same associativity laws ($f \circ (g \circ h) = (f \circ g) \circ h)$, and the same unit laws ($f \circ \operatorname{id} = f, \operatorname{id} \circ f = f$)!

• Does it mean that Category Theory is not a fully formalized theory? Is it a fully formalizable theory? – user170039 Jun 26 '16 at 3:37
• I'm not familiar with fully formalized theories or even the definition of a fully formalizable theory, but maybe this will help: Topos theory gives a model for higher order intuitionistic logic and provides a natural setting for synthetic geometry and the "forcing" proof of the indepence of ZFC and the continuum hypothesis; homotopy type theory gives a foundation for mathematics that's based on type theory with identity types and the fact that type theory with identity types leads you to higher category theory and higher topos theory if you care to see things that way. – Geoff Jun 26 '16 at 3:42
• For no ring the category of modules is small, not even skeletally small. There are modules of arbitrarily large cardinal so the category is "as large as" that of sets. – Mariano Suárez-Álvarez Jun 26 '16 at 4:03
• On the other hand, you can use Mitchell-Freyd to deal with infinite diagrams. What you need is to have something happening inside a set-sized part of your abelian category. – Mariano Suárez-Álvarez Jun 26 '16 at 4:05
• @MarianoSuárez-Alvarez Yes, it seems I was mistaken with that comment. Thank you for pointing it out; I have edited my post to correct my error. The demons of no sleep strike again! – Geoff Jun 26 '16 at 4:22

A category consists of something in much the same way a group consists of an operation and a set. Often a category is a tuple of a class of objects and a class of arrows. However because sometimes categories deal with collections that are larger then classes it makes sense to use a vague term that basically means "Use the appropriate set/class/etc concept here"

• So we take the tuple here as an undefined primitive? – user170039 Jun 26 '16 at 3:04
• Tipples can be defined in terms of sets. – Q the Platypus Jun 26 '16 at 3:05
• But then there would be no sense in talking about category of sets because sets are objects of a particular category which we denote by $\textbf{Set}$. – user170039 Jun 26 '16 at 3:07
• By the way, a group $G$ can simply be defined in the following manner (which is what probably you wanted to mean), Let $G$ be a set. Let the $\mathcal{O}$ be the "set" (you may ask, how do you know that it is a set? But let's assume that for the sake of simplicity) of all $\circ$'s such that $\circ: G\times G\to G$. Then a group is simply an element of the set (again, I am being vague) $\{G\}\times \mathcal{O}$. – user170039 Jun 26 '16 at 3:12
• The cross product operator creates pairs (2-tupples) by definition – Q the Platypus Jun 26 '16 at 3:26

Some thoughts from a definitely non expert:

When doing mathematics, you have to first choose a logical system within which to work. The first axiomatic system introduced to mathematicians is practically always ZFC, but by no means is it the only choice.

Category theory is interested in the consequences of composition of events, and so it only defines itself in terms of what it needs:

1. You have some logical things called objects that you find interesting
2. Things happen to these objects in a compositional way that is even $more$ interesting
3. One possible thing that can happen to your objects is nothing

There is then, in a sense, a different category theory for each definition of "logical thing", but not all logical systems are created equal with respect to discussing categorical questions!

As an example, we certainly have logical things called sets, functions act on sets compositionally, and the identity map certainly doesn't effect a set. So we $should$ be able to talk about the category of sets, but this is a pain to do in ZFC, because, as you have experienced first hand, when you try to talk about all of sets as an object, ZFC screams in your ear, "That's not a set, that's not a set, be suspicious of this thing's existence!"

The solution is simple: if you want to ask categorical questions about ZFC(or the theory of groups, rings, modules, and many other subjects) don't use ZFC as your logical system. You could instead use a logical system that axiomatizes things larger than sets(logical things $a$ for which $a\in b$ is not defined), and then SETS(and many other interesting things!) will be within your grasp.

An example of such a system that is similar to ZFC is NBG(von Neumann Bernays Gödel) theory, wherein one begins with the notion of class as a starting point, but there are of course others.

Alternative, you could ask yourself if you even $want$ set theory when doing category theory. Set theory is, in a word, an axiomatic system used to describe the use of the symbol $\in$ in a way that hopefully doesn't, but possibly might lead to paradoxes. Since category theory tends to focus on $actions$(which compose) instead of $things$(which belong), this is rarely useful. So a simple, and seemingly often suggested course of action is: take what you've learned from set theory, and just stop asking $\in$ questions.

Either way, your worries are now no longer a concern: SETS is a reasonable object to consider, as you are either using a larger theory to study it, or you are not asking questions which presuppose the nonexistence of SETS.

• Can you point out which parts of your answer specifically addresses the questions raised in my post? In other words, which part of your post addresses $(1)$, which part addresses $(2)$, which part addresses $(3)$ and which part addresses $(4)$? While your answer was interesting to read, I would be glad to know how it specifically answers my questions. – user170039 Jun 26 '16 at 5:12
• The answers would depend heavily on what approach you decided to take towards category theory(and my post did not exhaust these). If you choose to use a larger than ZFC theory such as NBG, then (1) is in the negative, because the RHS of $\in$ is a class, and ZFC(iirc) does not have an axiomatized notion of a class. (2) will be class membership for objects and depending on the assumptions made in your text, either set membership or class membership for morphisms. The introduction of my post was aiming to redo your text's description of what a category is, which is (3). As for (4)... – QTHalfTau Jun 26 '16 at 6:00
• In NBG, again as an example, to every two classes $A$, $B$, there is an associated class $\{A,B\}$. From here you can obtain ordered triples in the usual way. – QTHalfTau Jun 26 '16 at 6:06