Math 202A: Lecture 1

As in common parlance, a mathematical category consists firstly of a collection of objects which are distinct but similar in some way. In category theory the relationships between the objects of are morphisms, and for each pair of objects we have a corresponding collection of morphisms Morphisms in are called endomorphisms, and the collection itself is denoted Morphisms can be composed: given objects and morphisms and we have a corresponding morphism Composition is both associative and unital. Associativity means that for any morphisms such that and both make sense, they in fact coincide. Unitarity means that for every pair of objects there exist morphisms and such that

holds for all morphisms We say that two objects are isomorphic if there exist morphisms and such that

We denote by the subcollection of consisting of isomorphisms. Thus, and are isomorphic if is a nonempty collection. Isomorphism is a weaker notion than equality, since may contain multiple isomorphisms. We write and call morphisms in automorphisms of

Problem 1.1. Show that is nonempty.

You might ask: what is the point of the category formalism introduced above? My preferred answer to this question is another question: what is the point of anything? This ontological response is sincere but runs the risk of being perceived as facetious. A more practical answer is that category theory is provides a very general and flexible way to organize objects and relationships, and is applied as such in the sciences. For more about this you can browse the Topos Institute website, or watch the short video below.

The fundamental example of a category is the category whose objects are sets and whose morphisms are functions. The law of composition in is composition of functions.

Problem 1.2. Prove that two sets are isomorphic if and only if there exists a bijective function  

Looking at the category calls attention to the use of the term “collection” in the general definition of a category. This term is used because the collection of all sets is not itself a set and attempting to view it as such leads to paradoxes. Thus, in order to think about categories in general we need to consider aggregations of objects which are in some sense larger than sets, and we refer to these as collections. Here you may feel the urge to object that the term “collection” has not been clearly defined. However, unless you also took issue with the use of the word “set” during your undergraduate studies, you forfeited the right to this objection long ago and I will happily ignore it. Of course, Math 202A does not occupy all of reality and you are welcome to examine these foundational issues yourself in its complement.

Having pointed out that the collection of all sets is a somewhat subtle concept, let us point out that the collections which make up the morphisms are not so bad: they can be considered as sets without running into any foundational issues. Indeed, if you believe that and being sets is enough to certify

as a set, than there is no further issue because a function is by definition a subset with the property that contains exactly one point of the form for each Thus, the collection of all functions is contained in the collection of all subsets of the set and hence is contained in a set.

The upshot is that categories are more general than sets, with being just one example of a category. A helpful heuristic to have in mind is that categories are like directed graphs, possibly very large ones, with objects being vertices and morphisms being directed edges. Composing morphisms is analogous to concatenating arrows. A subcategory should then be like a subgraph, and a function from one category to another should be like a graph homomorphism. We will come back to this.

Definition 1.1: Combinatorics is the study of the category whose objects are finite sets and whose morphisms are functions.

From the general perspective of Definition 1, the typical problems of combinatorics can be formulated along the following lines. First there is the counting problem: given a finite nonempty set defined in some explicit but not transparent way (for example, the set of alternating sign matrices), what is the natural number such that is isomorphic to ? The study of questions of this kind is called enumerative combinatorics. Another type of question is: given two finite nonempty sets again defined in some explicit but non-transparent way, is nonempty? If so, can we explicitly describe an isomorphism ? This endeavor is usually called bijective combinatorics.

The category is a subcategory of . Hoping that the collection of all finite sets can be thought of as a set without running into paradoxes is a bit too optimistic (to see why, observe that for any set the set is finite…). However, the set of functions between two finite sets is finite, and more than this functions between finite sets can be efficiently encoded as matrices. Indeed, suppose and By definition, this means that there exist isomorphisms

and

It is natural to think of these isomorphisms as labelings of the elements of and writing

and

With these labelings in place, we can represent the function as the matrix whose -entry is if and if not. Thus, every is represented by an element of i.e. an matrix with entries in The cardinality of all such binary matrices in but the cardinality of is only because the matrix representation of a function has exactly one in each column. It is important to note that the matrix representation of a given function is not unique because it depends on the labelings In particular, the number of distinct matrix representations of a given function is at most

Since every finite set is a set, every object of is an object of Moreover, for any two finite sets the collection of morphisms is the same whether we view as objects of or as objects of We say that is a full subcategory of to indicate that no morphisms are lost. Contrast this with the category whose objects are finite sets and whose morphisms are injective functions; this is a subcategory of but not a full subcategory. Indeed, is not even a full subcategory of — it has the same collection of objects but a restricted collection of morphisms. One says that is a wide subcategory of

Problem 1.3. Verify that really is a category, i.e. obeys the axioms stipulated above. Calculate and

Continuing onward, most courses you took as an undergraduate can be defined as the study of a particular category. Here is another example.

Definition 1.2. Group theory is the study of the category whose objects are groups and whose morphisms are group homomorphisms.

Groups form an extremely important and fundamental category because they occur in every category, more or less. The “more or less” is due to the fact that a group is, by definition, a set. A category is said to be locally small if is a set for every pair of objects In particular, every subcategory of is a locally small category.

Problem 1.4. Prove that in any locally small category, is a group for every object

Thus, every locally small category gives us a group for each of its objects. The subject known as representation theory is concerned with reversing this observation by representing the elements of a given group as automorphisms in a preferred locally small category For any object we can consider actions of on which by definition are group homomorphisms

Now we can consider all ways in which can act on the objects of and assemble these into a new category whose objects are pairs as above. Such pairs are called representations of , and for every representation is a subgroup of Thus, we are representing the elements of as automorphisms of the object . This might result in losing some of the structure of since several group elements could map to the same automorphism of For example, the extreme case is the trivial representation where for every In the opposite extreme case, where is injective and is a subgroup of isomorphic to , the we say that is a faithful representation of

It remains to define the morphisms of our nascent category For any two representations and we define the corresponding set of morphisms to be the subset of consisting of so-called -equivariant morphisms . By definition, these are morphisms which intertwine the actions in the sense that

holds for every group element

Let us consider the above construction in the case where For a set the group is called the permutation group of and its elements are called permutations of Consequently, objects of are called permutation representations of Now, since a group is by definition a set, is itself an object of Furthermore, there is a canonical action

of on itself defined by where are elements of and is the product of these elements in This gives a permutation representation called the regular representation of

Problem 1.5. Prove that as defined above really is a group homomorphism, and that really is a set-theoretic automorphism of for every Finally, prove Cayley’s theorem: the groups and are isomorphic.

Cayley’s theorem is a very familiar result from elementary group theory which, in the language introduced above, says that every group has a faithful representation in the category of sets. Representations of groups on the category of vector spaces are called linear representations and we will study these in Math 202B. In Math 202A, we have a much more modest task, namely that of studying the category of vector spaces as is, without any group acting in the background.

Definition 1.3. Linear algebra is the study of the category whose objects are vector spaces and whose morphisms are linear transformations.

Technically, Definition 1.3 is incomplete because we must specify the field over which our vector spaces are defined. We will do this next lecture, where we further argue that finite-dimensional linear algebra can be viewed as a “quantization” of combinatorics.