Category Theory Basics: Objects, Morphisms, and Functors

[00:00:00][Music] about half a year ago i published a video titled 27 unhelpful facts about category theory a silly spur of the moment kind of thing i neglected to realize that making a thumbnail which simply featured a coconut next to the word nut would make me the darling of the youtube algorithm for the next week and so it was that much of the internet's first introduction to my channel was a 9 minute long your mum joke including several people i knew in real life who weren't aware i even had a youtube channel still not sure how to process that in an effort to recover some respectability i've decided to remain faithful and full and essentially subjective and objects by fulfilling my obligation to a serious follow-up today i'll be teaching you the very basics of category theory properly ideally i'd like anyone at any level of mathematical education to come away from this video feeling like they learned something so i'll be keeping jargon and technicalities to a minimum pretty much everything i say will thus have a giant implicit asterisk attached proclaiming that yes things are more complicated than i've made them seem but if i stop to clarify everything will be here forever i'll also be focusing a lot on intuition and in particular my own intuition i'm nowhere near an expert even if the almighty algorithm disagrees so if you find my explanations lacking i've linked some more authoritative perspectives below i'd also like to give a shout out to metamaths a channel currently working through a parallel introduction to the field so go check that out if you want more right let's begin then with the obvious question what is category theory [Music] mathematicians work with a large variety of mathematical constructions each has properties specific to a particular area of study properties that make each area distinct topology studies topological spaces group theory studies groups linear algebra studies vector spaces and so on these disciplines all care about different structures and they've all built different machinery to deal with each of them even so more often than not such structures have an awful lot in common they may look and feel different but the foundations are more alike than you might think there appears to be a standard way of building contexts in which we do mathematics category theory is all about formalizing this observation if we make precise the notion of a mathematical context we have the tools in place to examine contexts as a whole and in particular translations between contexts we get a bird's-eye view of the whole subject to understand what category theory is it might help to understand what it is not firstly it's not really about categorizing things i know a lot of people saw the coconut in my previous videos thumbnail and assumed category theory was a way to classify real world objects or something but no it's a mathematical theory about mathematical structure coconuts involved only for comedic purposes second it's not some new age third eye opening secret of the universe type of thing you laugh but i have actually seen people claim this third and related category theory is not a theory of everything granted it definitely looks like it sometimes if category theory subsumes every mathematical framework is it not the ultimate language of the universe i mean i know i was drawn to category theory on a quest to know everything and i somehow managed to make brief mentions of general relativity quantum mechanics russell's paradox and linguistics in my master's dissertation about moving brackets around more on that later but category theory on its own is in fact rather limited in scope some have said it's merely scaffolding surrounding buildings made of actual maths but my preferred analogy is that if maths is a story category theory is the setting essential but far from the full picture some stories are all about the setting while others don't give it a second thought preferring to focus on characters or plot instead the details a bird's eye view might ignore to tell certain stories you can get away with only one approach to tell every story though you need both the high level abstraction and the low level details plus as we'll see shortly not everything is a category while the idea covers most frameworks we consider useful or interesting there are plenty of exceptions speaking of which if we're about to talk about category theory we need to know what a category is let's meet the definition that's responsible for all of this a category which we might name curly c consists of four things objects morphisms composition and identities subject to two requirements the identity and associativity laws let's look at each of these in turn every category has a collection of objects in principle objects can be anything though we generally take them to be mathematical things like numbers or collections of numbers or collections of numbers with extra structure we generally specify the objects of a category by writing them in a set a set for those unaware is a collection of things called elements written between curly brackets where we don't care about the order and we don't care about duplicates so for instance these sets are the same and these sets are the same there you go you now know set theory categories also have morphisms for any two objects a and b the category has a set of morphisms from a to b morphisms are such a general idea that it can be hard to intuitively pin down what we mean by this i like to think of morphisms as relationships with a direction there is a morphism from a to b if a is related to b but b doesn't have to be related to a in return it could be a one-way connection it could be the case that the set of morphisms from a to b is empty so a is not related to b or we could have more than one morphism from a to b so a is related to b in multiple different ways morphisms are commonly some kind of function and we'll see an example shortly but they don't have to be they can be much more abstract once you have morphisms you can compose them if f is a morphism from a to b and g is a morphism from b to c the definition of a category says there must be some way of combining them to produce amorphism from a to c in other words we can stick compatible morphisms end to end to make new ones and the composition operation in the category gives a recipe for making them we usually write composition with a small circle like this so g composed with f here is a morphism from a to c a category also requires certain special morphisms to exist called identities identities are morphisms from one object to itself in a category we must have one identity for each and every object which in particular means that the set of morphisms from any object to itself is not empty these identities are then subject to the identity law composing any morphism with an identity on either side does nothing to that morphism it's a bit like how one times any number equals that number unless you're terence howard finally we require the composition operation to satisfy the associativity law this one's a bit more complicated if you haven't met associativity before but i'll do my best most operations we use in day-to-day maths are binary this means they take two inputs and produce one output but we often use them as if they can take any number of inputs strictly speaking we should choose an order in which we evaluate such expressions luckily for us it often doesn't matter which order we choose no matter our choice we get the same answer so we ignore order entirely and write the expression without brackets this is shorthand for choose any order you like and successively evaluates the binary operation if a binary operation has this property we say it's associative addition and multiplication are the most familiar examples but some operations are not associative the most obvious is subtraction bracketing in different ways produces different outputs but my favorite non-associative operation is rock paper scissors ponder this if you wish in a category we require composition which is a binary operation to be associative we can therefore write any number of compositions in a row without brackets hurrah putting these all together you have yourself a category tell me what its objects are what its morphisms are how you compose morphisms and what its identities are and if the stuff you've given me satisfies the identity and associativity laws the category is well defined but all this is so far extremely abstract categories are meant to be general so we can apply them to lots of different scenarios but that approach has its drawbacks when you come to understand them for the first time let's make it a bit more concrete before i lose you let's build one of the most fundamental categories set the category of sets and set functions objects in set are done surprisingly sets morphisms in set are set functions again for those unaware a set function is a way of assigning to each element in one set one element in the second we can define a function by writing down its effect on every element or if there's an easier shorthand we could use that composition of functions is pretty straightforward for each element the composite function applies the first function then applies the second and for any set we can create a function that does nothing to each element these will be our identities we can then check that composition is associative and the proposed identities do act as identities to verify that set is indeed a category many of the most common and most useful categories follow the model of set that is their objects are sets with extra structure and their morphisms are special functions which respect that structure take the category group for instance a group is a set equipped with a binary operation which follows certain rules this operation adds a certain structure to the set we can then consider specialized set functions which respect the binary operation combining two elements then applying such a function is the same as applying the function to each element then combining functions with this property are called group homomorphisms in the category group objects are groups and morphisms are group homomorphisms composition and identities are exactly the same as in set since everything in group is a specialized version of something in set but the power of categories becomes apparent when you move outside this model of structured sets and structure-preserving functions let's look at an example that's somehow both more down to earth and more confusing construct a category as follows define its objects to be all the numbers you can place on a number line which mathematicians call real numbers for numbers x and y define a unique morphism from x to y if and only if x is less than or equal to y the difficulty here compared to set is that we can't really say what a morphism is it's not a thing you can write out like a function and it doesn't seem to do anything other than representing the fact that one number is less than or equal to another how then do we compose such porphisms well let's work through it if we have morphisms x to y and y to z this means x is less than or equal to y and y is less than or equal to z thus x is less than or equal to z but we know what that means it means there is a unique morphism from x to z we're looking for a morphism from x to z to be the composition of our two original morphisms so we can just define it to be this one since such morphisms are unique this definition uniquely determines the composition what about identities though we need amorphism from x to itself since x equals x x is in particular less than or equal to x so there is a unique morphism from xx and ta-da we have found our identities as before one can then follow through the definitions to see this proposed category abides by the identity and associativity laws so we have ourselves another category at this point it might help to consider a few constructions which aren't categories what if we modify the last example to be real numbers with less than instead of less than or equal to well then we can't have identities we would need every number to be strictly less than itself which of course isn't possible so this isn't a category what if we try to build a category where objects are numbers and there is a unique morphism from x to y if and only if x equals y plus one again identities don't work here no number equals itself plus one all right you might say let's adjust that to say there's a morphism from x to y if and only if x equals y or x equals y plus one this fixes the identity issue so maybe it works as a category but consider composition if we have morphisms x to y and y to z which aren't identities then x equals y plus one and y equals z plus one so x equals z plus two hence there cannot be a morphism from x to z according to our definition so we can't define the composition of these two morphisms alas this isn't a category either even though the definition of a category is highly general it's still pretty restrictive the fact that it nonetheless applies to so much of our mathematical landscape highlights just how much we're drawn to this kind of structure and how useful it can be categories are even more useful when we depict them visually i've already been using a load of arrows to help communicate these ideas but we can make things a bit more formal from here we can take some objects from a category and arrange them in a diagram then draw morphisms as arrows between them we can then compose morphisms by joining their corresponding arrows nose to tail thanks to the associativity law we can do this multiple times without brackets tracing out a root through the diagram this alone is helpful but certain diagrams have an extra property which means we don't have to write out reams of equations to prove things a diagram is commutative if for any two objects all routes between them are equal for instance this diagram commutes if and only if h is equal to g composed with f now commutative diagrams are infamous for being overly elaborate but you have to remember that under the hood a commutative diagram is simply a list of equations each pair of roots between two objects corresponds to one equation no matter how convoluted the roots may be so in fact despite their complexity commutative diagrams are stunningly efficient imagine writing down every single pair of paths in a diagram like this not fun instead we can translate the problem of solving multiple equations into the problem of gluing shapes together along shared morphisms much more satisfying one important commutative diagram to consider is this one suppose we have objects a and b in a category and morphism's f from a to b and g from b to a such that this diagram commutes in other words f composed with g and g composed with f are equal to identities in this case f is known as an isomorphism isomorphisms are morphisms with inverses which act as a kind of undo button for the morphism doing both does the same thing as doing neither if there exists an isomorphism between two objects we say those objects are isomorphic written like this if you've done any university level maths you'll be well acquainted with isomorphism in some guys isomorphisms of groups isomorphisms of vector spaces whatever these are all the result of applying the definition of isomorphism in the category setup for each of these contexts in our set example for instance an isomorphism is a set function that can be reversed using another set function equivalently two sets are isomorphic if they contain the same elements labeled in different ways the actual names of the elements and any extra structure aren't important in set only the set theoretic perspective is isomorphism captures the idea that objects are functionally the same where the meaning of functionally depends on the working category to the category itself the objects look the same because they share the only properties the category actually cares about so we've defined categories we've represented them visually and we've looked at an important concept you can find inside them but there's a lot more to category theory than categories first let's take a quick look at functors a functor is in some sense a translation between categories we can turn one category into another look at what's changed and draw conclusions about how the categories themselves are related i like to think of functors as rotations in perspective we value different properties of objects and morphisms in different contexts and functors provide a way of changing these priorities rotating your worldview let c and d be categories a functor f from c to d consists of two things a function on objects and a function on morphisms subject to two requirements functors respect identities and functors respect composition again let's look at these one by one a functor takes objects from c and turns them into objects in d usually written like this similarly a functor takes morphisms from c and turns them into morphisms in d with the endpoints determined by the function on objects by respecting identities we mean the functor takes identities to identities as for respecting composition this means that f applied to a composition in c is the composition in d of f applied to each morphism hey that kinda looks like a group homomorphism i wonder if there's a reason for that and that's all you need to make a functor two functions which do sensible things to identities and composition as before however all rather abstract let's see some examples to bring it all back down to earth one notorious type of functor is the forgetful functor these do nothing to objects and morphisms except forget some of the properties we cared about in the original category take the forgetful functor from group to set as we saw earlier any group is a set with extra structure the forgetful functor forgets that structure as the name might imply a group homomorphism is similarly a set function with extra structure ignoring that structure still leaves a normal set function i.e a morphism in set since we're doing nothing to morphisms identity and composition preservation follow immediately demonstrating that u is a well-defined functor it's also possible to construct a functor going the other way this is called the free group functor which builds a group out of any set you give it i'll spare you the details here though we can also build a functor out of our less than or equal to example consider a category whose objects are real numbers with a unique morphism from x to y if and only if x is greater than or equal to y i'll leave you to dot the eyes and cross the t's to verify that this is a category how can we translate between these two contexts in a way that preserves composition of morphisms how can we rotate our perspective oh well that was easy because we've flipped the direction of the order to preserve the right stuff we merely need to flip the sign of the objects that is map everything to its negative and the rest falls out at their core functors are maps between categories which respect categorical structure hopefully there are some bells ringing in your head right now because we've met that sort of thing before remember i said many categories are structured objects and functions respecting their structure well what if we just move this around a bit and add a few more and whoops i i appear to have created the category of categories yep category theory has gone full meta everything we've looked at so far applies not only to things inside categories but to categories themselves here we begin to glimpse the true power of category theory now that our morphisms are functors if we have two functors which compose to produce identity functors we found ourselves some isomorphic categories categories which differ in decoration alone unfortunately isomorphism of categories tends to be too strong a requirement for anything useful it's a bit like comparing strings of text and saying they're only equal if both are written in the same font when really we care about something more fundamental but there is a way to fix this the category of categories comes prepared with a weakened form of isomorphism called equivalence for equivalence we don't require the composite functors to equal identity functors they need only be naturally isomorphic now i'm not going to rigorously define natural isomorphisms here because lord knows i've been going too long already and i can tell some of you are drifting off put simply just as functors are translations between categories natural transformations are translations between functors and natural isomorphisms are natural transformations with inverses natural isomorphisms are then isomorphisms in the category where objects are functions between two fixed categories and morphisms are natural transformations between such functors is your head hurting yet miners point is you already know the most important takeaway if g composed with f and the identity functor are naturally isomorphic then they may not be equal but they're close enough to equal for most things that matter equivalence of categories turns out to be much more common and much more informative than isomorphism if two categories are equivalent then they encode essentially the same information in different ways for example i wrote my dissertation on the equivalence between the category of minority categories and the category of representable multicategories try saying that five times fast monodual categories and multi categories are category-like structures which emerged somewhat independently until one day someone noticed all minority categories were multi-categories in disguise and a certain subset of multi-categories representable ones were monogal categories in disguise what's more the categories containing each had matching structure in their morphisms or in more precise terms there is an equivalence of categories people were looking at two perspectives on the same thing all along and if equivalence isn't enough for you it's possible to generalize further to adjunction two categories connected by adjoint functors might not be equal they might not be almost equal and they might not be almost almost equal but they are almost almost almost equal kind of like evil twins i guess i don't know i i've honestly never read a description of a junction that makes real intuitive sense to me and that i think is the signal i've reached the limits of what's explainable in a casual quippy youtube video believe me there are many many more advanced topics i could talk about from limits and co-limits to the yena dilemma but i think i've made good on my promise to fill in the most prominent gaps in my previous overview category theory is a deep and diverse subject and if you've made it this far i'm sure you'd enjoy reading into it further as i said there are several sources in the description and there's plenty of other interesting content to find out there i just hope i've managed to add something worthwhile to that list all this does however leave one question i'm sure some of you have been itching to write a snarky comment about the whole time what's all this actually for even compared to other subjects in pure maths category theory has a reputation for being unadulterated abstract nonsense despite the memes however there are some concrete applications functional programming is the best known any time you use a lambda expression in your programming language of choice you are in fact paying homage to among others category theory the subject has also had minor impacts in fields as disparate as quantum mechanics mathematical modelling and linguistics as the subject has grown ever trendier in the past few years there have even been conferences dedicated to applied category theory the essence of category theory is an organizing principle it's a formalized method to recognize patterns in the way we structure our problem-solving machinery wherever that turns up while we do have to avoid the traps of romanticizing it or asking too much of it there's no denying a categorical approach is a powerful one providing you're willing to melt your brain a bit in the process for those curious i've put a link to my dissertation which is a journey from the basics of category theory to a long and painful proof in the description i haven't yet received final feedback so i can't guarantee correctness but it might be an interesting read if you'd like to see category theory in action