Hello Veeky Forums, and welcome to the second lecture in my Brave New Algebra series...

Hello Veeky Forums, and welcome to the second lecture in my Brave New Algebra series. Today we will be discussing category theory. This won't be as careless as yesterday's lecture, but it is NOT going to be super duper careful either. You've been warned. All of this stuff has been fully formalized and carefully handled in a variety of great textbooks (Categories for the Working Mathematician by Mac Lane is pretty good). This lecture is meant to familiarize people with the language and methods of category theory. My goal is not a starkly rigorous handling. With that said, let's begin.

I will be fixing a suitable Grothendieck universe U for this discussion, for those curious. When I say small, I mean U-small. An arbitrary category need not be U-small here, but it will be U'-small for some sufficiently large universe U'.

A category C consists of a U'-small set of objects, which I will denote C_0, and a U'-small set of arrows or morphisms, which I will denote C_1. This notation should remind you of objects being 0-cells, and arrows being 1-cells. We will handle this generalization later on.

There are parallel functions s,t: C_1 -> C_0. We call s(f) the source or domain of f, and t(f) the target or codomain of f. A pair of arrows (f,g) is called composable if s(g)=t(f). There is a binary operator called composition ∘: {(f,g) : (f,g) is composable} -> C_1 which is associative. We will write g∘f for ∘(f,g). Furthermore, we impose the following relations: s(g∘f)=s(f) and t(g∘f)=t(g).

There is always an injective function Id : C_0 -> C_1, satisfying f∘Id(X)=f whenever s(f)=X, and Id(X)∘g=g whenever t(g)=X. We call Id(X) the identity arrow of X, or just its identity. (Exercise: show that identities are unique (ie, that if two arrows exhibit the properties of an identity, then they are equal).)

Given objects A and B in C, we will denote the set of arrows {f : s(f)=A and t(f)=B} := C[A,B]. This is the set of arrows going from A to B. We write f:A->B if f is in C[A,B]. Generally, C will be clear from context in this case.

A morphism f:A->B is called an isomorphism if there exists a morphism g:B->A such that f∘g=Id(B) and g∘f=Id(A). We call g a two-sided inverse to f. (Exercise: show that two-sided inverse are unique.) With this, we will simply call g "the" inverse of f, omitting "two-sided."

The elements of C[X,X] are called endomorphisms of X. The subset of C[X,X] consisting of the isomorphisms is called the set of automorphisms on X, Aut(X). (Exercise: show that Aut(X) satisfies the group axioms.) With this, we call Aut(X) the automorphism group of X.

If r∘s=Id(X), we call r a retract of s (a left inverse), and we call s a section of r (a right inverse). A morphism f is called idempotent if f∘f=f. (Exercise: show that, if s is a section of r, then s∘r is idempotent.) We say that such an r and s split this idempotent.

A monomorphism is an arrow f:A->B such that, given any two arrows g,h:C->A, f∘g=f∘h implies that g=h. Dually, an epimorphism is an arrow f:A->B such that i∘f=j∘f implies that i=j. Later, we will provide a more concise and elegant way to characterize epimorphisms and monomorphisms. (Exercise: show that the composition of two monomorphisms is again a monomorphism, and that the same holds for composable epimorphisms.)

If f∘g is an epimorphism, then f is an epimorphism. Indeed, suppose we had some i and j where i∘f=j∘f but i=/=j (such a pair must exist for f not to be an epimorphism). Then, after composing with g on the right, we have (i∘f)∘g=(j∘f)∘g. By associativity, we have i∘(f∘g)=j∘(f∘g), but by hypothesis, f∘g is an epimorphism. We thus have that i=j, a contradiction. So, f must also be an epimorphism. A similar argument applies to monomorphisms, so that if f∘g is a monomorphism, then g is a monomorphism.

Clearly every isomorphism is both an epimorphism and a monomorphism, but the converse need not hold in general.

A category C is called small (by our use of universes, this is technically U-small) if C_0 is a small set and C_1 is a small set. It is locally small if C[A,B] is a small set for all A,B in C. (Exercise: show that a small category is locally small.)


We will now examine some of the categories which we will be working with most heavily.

The category Set has for objects U-small sets, and Set[A,B]=B^A, the set of functions from A to B. (Exercise: check that Set indeed forms a category. Is it small? Locally small?)

The category Grp has for objects (small) groups, with group homomorphisms between them.

Vect_k has for objects vector spaces over a fixed base field k, with linear maps between them.

CRing has commutative rings (with multiplicative identity) for objects and homomorphisms between them.

Top is the category with objects topological spaces, and with continuous functions between them.

Let's discuss transformations between categories: functors.

A functor F:C->D, from a category C to a category D, is a function F_0: C_0 -> D_0 (we will write F_0=F when the argument is clearly on objects) together with a function F_(A,B) : C[A,B] -> D[F(A),F(B)] (again, if the morphism is understood, we will omit the subscript) satisfying the following axioms: F(Id(X))=Id(F(X)) and F(f)∘F(g)=F(f∘g), for all X, f, and g in C. A functor essentially transports commutative diagrams in C to commutative diagrams in D. This will be made precise later in this lecture. Think of functors as preserving all of the categorical structure of C and putting it in terms of D.

Functors can be composed in an obvious way, by simply composing all of the functions involved. Since they are all functions, and functions are associative (even in U'), we have that functor composition enjoys associativity. Given any category C, we can define the identity functor Id(C) by Id(C)(X)=X and Id(C)(f)=f for all X and f in C. (Exercise: show that Id(C) is an identity morphism with respect to functors into and out of C.)

With this fact in tow, we see that locally small categories themselves form a (not small) category, which we will call Cat. We will avoid referring to large categories, as nearly all of our categories in these lectures will be locally small in some reasonable sense.

A functor F is called full if F_(A,B) is surjective for all A,B in the domain of F. F is faithful if all of these functions are injective. A functor is thus full and faithful if it is a bijection on hom-sets (sets of the form C[A,B]). Because composition of functors is performed by composing functions on individual hom sets, and because the composite of surjective functions is surjective and likewise for injective functions, we immediately see that the composite of two full functors is full and the composite of two faithful functors is faithful.

Full and faithful functors only depend on the hom-sets, and not the functor's behaviour for objects. A functor is surjective if it is surjective on underlying sets of objects. However, in category theory, it is "evil" to look at properties which forget about the higher structure (in this case, the arrows). We will loosen the notion of a surjective functor to that of an essentially surjective functor: F:A->B is essentially surjective if for all objects Y in B, there is some X in A so that there exists an isomorphism f:F(X)->Y in B. This says that the entire set of objects need not be covered by an essentially surjective functor: just at least one object from each isomorphism class of objects in B.

Given two functors F,G:C->D, a natural transformation a:F->G is an assignment to each object c of C a component a_c:F(c)->G(c) in D, so that for all morphisms f:x->y in C, (a_y)∘F(f)=G(f)∘(a_x). A natural transformation is called a natural isomorphism if it has a (two-sided) inverse. If there is a natural isomorphism between two functors, we simply call them isomorphic. (Exercise: show that a natural transformation is an isomorphism if and only if each of its components is an isomorphism.)

If we have natural transformations a:F->G and b:G->H, the vertical composite b∘a is defined component-wise: (b∘a)_X=(b_X)∘(a_X). The associativity of vertical composition follows simply from the associativity of the composition in the codomain of F, G, and H. (Exercise: construct the identity natural transformation for a functor. With this, conclude that the set of functors from C to D (assume both are locally small) forms a category. We will denote this category D^C, analogous to the set of functions between two sets. We will refer to such categories as functor categories.)

There is also a notion of horizontal composition of functors, but we will address this when needed later on.

Suppose F,G:C->D. If we are given a natural transformation a:F->G and a functor H:D->E, we may form a composite natural transformation H∘a:H∘F->H∘G by again composing component-wise: (H∘a)_X=H(a_X).

A functor F:C->D is an equivalence of categories if there exists a functor G:D->C so that F∘G is naturally isomorphic to Id(D) and G∘F is naturally isomorphic to Id(C).

A functor is an equivalence if and only if it is full and faithful (fully faithful for short) and also essentially surjective. This will probably be useful down the line; in general it is easier to prove two categories are equivalent (ie, that there exists an equivalence) by simply providing an essentially surjective, fully faithful functor in either direction.

Let L:C->D and R:D->C be functors. We say that L is left adjoint to R, written L-|R, if D[Lx,y] is in bijection with C[x,Ry], and the bijections are natural in both arguments x and y. We call the entire system an adjunction between C and D.

Equivalently, an adjunction may be characterized by a pair of natural transformations e:L∘R->Id(D) and n:Id(C)->R∘L. n is called the unit of the adjunction, and e is called the counit. They are required to satisfy the so-called triangle identities: (L∘n)∘(e∘L)=Id(L) and (n∘R)∘(R∘e)=Id(R). I will omit the lengthy-ish proof that this is equivalent to the first definition for an adjunction, but both the nLab and Mac Lane have proofs of this. (Exercise: prove that left and right adjoints are unique up to natural isomorphism.)

If L-|R and S-|T, and S∘L and T∘R are well-defined, then (S∘L)-|(T∘R). This is easily see be composing the bijections between hom sets.

Let C be a category. The dual of C, denoted C*, has for objects the objects of C (although we will adjoin an asterisk to clarify that it is an object of C*), and for arrows, C*[A*,B*]=C[B,A]. Composition is defined in the opposite direction, so that if f∘g=h in C, then g*∘f*=h*. C* is clearly a category since identity morphisms are always two-sided and associativity is as well. In general, C* is not equivalent to C in the sense that we have already introduced. Next we will see how they are related, however.

The functors that we have introduced are called covariant functors. A contrafunctor (in the literature, a contravariant functor) from C to D is either a covariant functor from C to D* or from D* to C. (Exercise: show that (D*)^C is equivalent to D^(C*) for any categories C and D.)

A contrafunctor is an equivalence if there is a contrafunctor antiparallel to it, so that again the composites are isomorphic to the identities on the domain and codomain (just like our previous definition of equivalences of categories). (Exercise: show that a category and its dual are contravariantly equivalent under the functor (-)*, where (A)*=A* and (f)*=f*. In particular, show that (A*)*=A and (f*)*=f always.)

An important class of functor categories that we will be concerned with are presheaf categories. The presheaf category of a locally small category C, Psh(C), is the functor category Set^(C*). It is the category of set-valued contrafunctors on C. To see why they are important, let us first define the contravariant hom functors.

Let C be a locally small category, and X an object of C. Then the (contravariant) hom functor at X is the functor C[-,X]:C*->Set which assigns Y* to the set C[Y,X] (this set is U-small since we require C to be locally small). A morphism f:Y->Z is assigned the function (-∘f):C[Z,X]->C[Y,X], which takes each g:Z->X to the map g∘f:Y->X. It is important to keep in mind that this hom functor reverses the direction of arrows. A functor isomorphic to some hom functor is called representable, and the object at which the hom functor is defined is said to represent it.

Now, what use are these to us? Well, we can define a functor called the Yoneda embedding, denoted y:C->Psh(C), which takes each object X to C[-,X] and takes each morphism f:X->Y to the obvious natural transformation, which assigns each object of C* to the component (f∘-):C[-,X]->C[-,Y]. The statement of the Yoneda lemma is that y is full and faithful (such functors are called embeddings occasionally). To see why, we only need to see what y does to hom sets: it takes f in C[X,Y] to the composition natural transformation (f∘-):C[-,X]->C[-,Y]. Clearly every such assignment is injective, but it is also surjective because of the definition of a natural transformation and what it means between hom functors.

If J is a small category, a diagram in the shape of J in a category C is simply a functor J->C. A functor is a way to specify data in C in the shape of the category J (which is generally relatively small, but certainly not always). For an object X of C, write J_X for the constant diagram on X which takes all objects in J to X and all arrows to Id(X) (this is clearly a functor). This assignment defines a functor (J_-):C->(C^J), taking every object X to J_X. When a left adjoint to this functor exists, we call it colim. The left adjoint takes a diagram F to its colimit colim(F). The right adjoint to (J_-), lim, takes a diagram to its limit, lim(J). If the left adjoint exists, we say that C has all colimits over J-shaped diagrams, and if the right adjoint exists we say C has all limits over J-shaped diagrams.

Because composing adjoints yields more adjoints, left adjoints preserve colimits and right adjoints preserve limits. This is very useful.

Suppose J consists of four objects 1,2,3,4, arrows f:1->2 and g:1->3, and i:2->4 and j:3->4, with i∘f=j∘g. We call a diagram shaped like this a commutative square. (Exercise: show that if F and G are two commutative squares where F(2)=G(1) and F(4)=G(3), then the square on F(1), G(2), F(3), G(4), with composite morphisms from F and G, is also commutative. This is called the pasting law. The proof technique used here is useful in general, and lets one paste arbitrary commutative diagrams to get new ones.)

When J is the category with just two objects and only identity arrows (we call these categories discrete), then a colimit of a J-shaped diagram is called the coproduct of the two objects in the C. The limit is called their product. This language carries over to larger discrete diagrams.

When J is just a pair of parallel arrows between two objects, a limit over this diagram is called the equalizer of the arrows, and the colimit is called their coequalizer.

J is called a span if it consists of objects a, b, and c, and only two nontrivial arrows f:a->b and g:a->c. The limit of a span-shaped diagram is called the pullback of the two arrows mapped two, and also called the fiber product of the image of the two outer objects in homotopical contexts. The colimit of a J*-shaped diagram (called a cospan diagram) is called the pushout of the two arrows.

A limit of the empty diagram is called an initial object in the category

Because adjoints are unique up to isomorphism, so also are limits and colimits, being determined by adjoint functors.

(Exercise: show that a limit lim(F) of a diagram F:J->C determines a family of morphisms p_j: lim(F)->F(j) for each object j in J, so that, for every morphism f:j->k in J, F(f)∘(p_j)=p_k. A dual argument will show that there are similar morphisms i_j: F(j)->colim(F) so that for all f:j->k in J, (i_k)∘F(f)=i_j.)

In the last exercise we found that there are projections (p_j) out of the limit of a diagram into each object so that the entire diagram commutes. Furthermore, by the uniqueness of adjoints, any other object admitting such projections must admit a morphism into the limit that makes all of the proejctions commute with one another, and this morphism is unique with this property. Dually, a colimit admits a morphism into any other object with the proper injections (i_j), so that everything commutes. These properties are called universal.

A limit in a category is the colimit of the dual diagram in the dual category.

A category with all limits for all small diagrams is called complete. One with all such colimits is called cocomplete. Examples of complete and cocomplete categories include Set, Grp, Top, and Cat (the category of small categories).

Products in Set are the Cartesian products normally encountered in set theory. Coproducts are given by the disjoint union. Disjoint union of topological spaces again yields their coproduct, and their product is the product of underlying sets endowed with the product topology. The product of categories C and D, written CxD, has for objects pairs (c,d) in (C_0)x(D_0), and CxD[(a,b),(c,d)]=C[a,c]xD[b,d]. Composition is performed component-wise. The disjoint union of two categories is their coproduct.

This concludes this lecture. If I missed any major points, or if anybody has any questions, feel free to comment below! (A forewarning: I am going to bed right after posting this, but I will reply to all questions when I wake.)

Fuckin based OP

Anyone have a link to yesterday's lecture thread?

Here, it's literally 1 page away you lazy shit

My knowledge of sets are entirely from my course in Discrete Mathematics, while I am able to fairly understand the stuff you wrote in Set Theory, I find this one to be beyond me. What prerequisite knowledge should I have to be able to grasp this? Also, wouldn't a couple of diagram helps?

sounds like overly formalized graph theory to me

So you defined some system and its properties, but whats the point? Like, show some practical applications as motivation to care about all this

Sorry for the lack of diagrams. You are definitely right, but it took longer than I had planned to type it out and I was tired. I can upload some diagrams pertaining to specific questions.

The secret spice is the composition. Category theory is essentially graph theory with composition. A groupoid is a category such that all arrows are isomorphisms, and a groupoid with a single object is essentially a group. The group operation is given by arrow composition, which is already associative and has an inverse. Technically, we call the groupoid corresponding to a group its delooping, but this will get touched on when we get to homotopy theory.

Now, an application of the Yoneda lemma: every group G, regarded as a category, is canonically embedded in the category of sets equipped with a G-action (and equivariant maps). Furthermore, the natural transformations from G[b,b] to G[b,b] (b is the single object in the category version of G) form a group which is isomorphic to G. This entire construction gives us a stronger version of Cayley's theorem, which says that we can embed a group into the symmetric group acting on it.

Since you brought up graph theory, let's look at this one: a multi digraph consists of a set V of vertices and a set E of edges, with source and target functions from E to V saying which vertex is the source and target for each edge E. But, this is just a diagram in the category of Sets, consisting of two parallel arrows... so, we can easily check that the category of functors from the category with just two objects and two parallel arrows into the category of sets is the category of multi digraphs with adjacency-preserving functions between. Why is this useful? I didn't mention the theorem in the lecture, but every presheaf category is complete and cocomplete, with limits and colimits calculated component-wise. This tells us that the category of multi digraphs has all limits and colimits, in particular products and coproducts.

Continuing with that last point, there is an adjunction between the category of multigraphs and the category of multi digraphs, where the left adjoint takes a directed graph and forgets the direction on edges. This functor is essentially surjective, and some adjoint-foo tells us that the right adjoint will be fully faithful. Recall that left adjoints preserve colimits: therefor the category of multigraphs has all colimits. Some more work in this vein also shows that it has all limits, and they are calculated as you would expect.

Any other fields that interest you? Category theory touches on everything pretty much.

It can feel that way. There are things that can be naturally understood from a categorical viewpoint, however. I have profs who are fond of saying things like "well this is simply a statement that X is a natural transformation of..." Even simple things -- when I realized that group representations were just functors from a group to Vec_k, the subject started to feel a little more complete early on.

>a variety of great textbooks
Projective variety? Affine variety? Need more info on how to treat textbooks in algebraic geometry.

...

I'm on my phone and wanted to have a link in the thread in case I don't find time to read it before it's only on 3rd party archives.

Meme books. Maclane is all you need for classical category theory (except foundations.)

>I use a Grothendieck universe and no reflection principles
What's it like being a low IQ sperg?

>Technically, we call the groupoid corresponding to a group its delooping,
Technically, you only do this if you're speaking of infinity groupoids. In the classical case you just call it the same thing as the group.

That's just incorrect. If we have any pointed (∞,1)-topos, then taking suspension (deloopings) and loop spaces form an adjunction. Since we can construct the tower of cohesive subcategories on n-connected objects and because suspensions move strictly up this tower, it's perfectly reasonable to look at the delooping taking a group just to its delooping, without mentioning ∞-groupoids yet.

>I will be fixing a suitable Grothendieck universe U for this discussion
Because there are so many people here who know what a Grothendieck universe is but not what a category is... douchebag

last lecture here

Yeah, ...I agree that nobody has the slightest chance of learning e.g. what an adjunction is from the above.
Op just filtern out the peiple who can't talk to him.
I'd say don't call it "lectures" or go staight to the algebra you wanna talk about. Then again, I suppose the intro is pretty much over. This lecture wasn't necessary, as there are not many other ways to set up cats

Is fixing a set with four basic properties too advanced for you or something?

Yes. Please take into account that I only learned yesterday in OP's first lecture what a set is.

In the context of just considering a group as a groupoid, it is not standard terminology to call it the delooping of the group: it's just the group.

this is rood but I do agree that this lecture doesnt really have an audience

I understand that. However, these lectures are moving right into homotopy theory, where the language is standard. Plus, after the debacle with my careless handling of set theory, I figured if I didn't include the caveat, people would be like
>hurr OHP a group is a set with structure not a category
>muh contradiction
>useless lol

But now when I am careful apparently this is still an issue. I do recognize that there are people on this board that disapprove of the project and just want to grief. No biggy.

I apologize to those for whom this lecture is of "no use," but you must understand that if I did not go over the basics, and just jumped into talking about higher algebra, people would then complain that they don't have the prerequisites.

My hope was that these discussions after lectures would be where people ask questions and where I can give interesting examples of things. As you see in the original posts, there was not much room to include many examples. It took me a few hours to go through and make sure everything was correct and then to post it as is.

Anyways. Are people still interested in me continuing these lectures? If not, I am more than willing to stop. I just wanted to share knowledge with people, but that is useless if there is no audience.

Stop crying mate, go on. I'll try to understand stuff and ask questions when I have them.

>If not, I am more than willing to stop.
I stopped with all my "unload information and make discussion" projects after 2 weeks. Hope you're stronger than me.

Not really related, but where are you from and what is your background and what's your motivation? What do you want to do.?

I'm from Michigan, I'm a twenty-year-old who grew obsessed with Grothendieck's approach to mathematics as a senior in high school and now spend five to seven hours a day studying and researching. I am going into my second year of undergrad at a mediocre community college, with plans to transfer into either University of Michigan or University of Chicago to pursue a PhD in pure mathematics, specializing in higher categories and abstract homotopy theory.

I really really love math, philosophy, and recently physics. I think everybody is really fucking cool, and reality is really fucking cool, and I try to get people to think of things in new and exciting ways. I try to bolster wisdom.

I'm technically underqualified to be trying to teach this stuff, but even if my lectures do nothing more than to get people a little more interested in topics they were not interested in prior, then mission accomplished, right?

I make money playing music in the streets of Ann Arbor for tips, and am putting myself through college. I am the bastard son of a drug addict. My name is Jake if you care.

Just another human, doing their thing, I guess.

Very romantic.
I take it OHP doesn't stand for Overhead Press?

I follow the nforum for one, two years now, but right now I'm not so interested in what they care for. I think we talked about the physics of some of it before. PS I'm the guy who said you should emphasize a motivation for looking into E-infty-algebras and I repeat it. I wanna learn some math I will use. Bra

Okay, Univalence Bro. I will continue for sure. I will never reveal what OHP stands for, at least not on this forum (because Byronicism is cool). Yeah, Urs Schreiber's stuff really interests me. I like his ideas on formalizing quantization in categorical terms, and his treatment of gauge equivalences as homotopies (I'm not sure if he came up with that approach, but I learned it from the nCafé from him). Also, his view of homotopy being about covariant hom functors and cohomology being about contravariant hom functors has had a huge influence on how I study things, and led to my general formalization of the ideas of local and global properties. I don't actually go on the nForum very often, but the nLab is an integral part of how I learn stuff.

Keep on keeping on, friend.

Going to higher equivalences for gauge theories was part of his PhD and so I assume someone else brought it to him.
I'm not sure to what extend you can claim he's reformalizing quantization. He's more extending the classical gauge theory to all n, with some tweaks so he can call it pre-quantization, but he doesn't really have proper results that are looked for in QFT. And who needs those anyway, tbqh.
The promise of the n-stuff to have cohomology theories pop out as cases of a general clean perspective on math itself is very appealing, I agree.

You would certainly know better than me regarding his physics work. I just try to pick up what I can.

I think the general yoga of the nPOV is going to be the hallmark of 21st century math. We went from examining objects by their properties, to examining objects by their relationship to other objects, and now to examining objects and relationships by putting them in sufficiently highly-structured settings. This is a great time to be a mathematician I think, and it is a time where theory-crafting has a lot of nice tools and overall potential. I love it!

Neat idea OP
Please continue

Doubt it. The learning curve for this is too steep and it's too far removed from problems people know understand.
Proving stuff like Beaz conjecture and whatnot that only exists because this field (formulation) exists ... nobody cares for that

That's as far as my perspective goes and why I'm interested in "interesting" (for many people) problems. If n-cats help with with approaching stuff like this, that's cool, because algebra is a clean thing.

>Meme books. Maclane is all you need for classical category theory (except foundations.)
This tbħ. Shaves in Geometry and Logic is also nice if you want to go deeper into toposes.

maclane is utter shit fucking pleb undergrad