Category Theory 1.2: What Is a Category? (Definitions & Examples)

[00:00:06]So that was the philosophical part of my talk, and I will be slowly moving towards more practical I mean, practically in the sense of mathematical stuff not so much philosophy But from all this talk about how our brains work The important part is that we want to be able to – the major tools in our Arsenal, right, are: Abstraction, Composition, and i'm going to add one more thing to this, Identity So as I said "abstraction" means we want to get rid of the details we want to like forget about the assembly language or machine language of what we are doing and that's not only in programming it's also in mathematics or physics we want to get rid of unnecessary details ok so once we get rid of unnecessary details then suddenly what happens is that things that were different, but they were different because of unnecessary details, they suddenly become identical. Like if you have let's say two billiard balls of the same colour, they are not really identical if you look under the microscope, they have different maybe scratches maybe they have different configuration of atoms, right but you can replace one with another when you're playing billiards So once you abstract, things that used to be different now become identical. this is why we have this notion of identity and this notion of identity because of abstraction is always nontrivial. So there are things that are strictly identical, so like you can replace one with another and you won't notice any difference but then there are things that are identical for all intents and purposes ok and in mathematics is this is like a very very important thing, that there is this distinction between "it's really the same" or "it's not really the same, but we will look at it as if it were the same". And there is even a whole foundation theory that's being now developed that's based on distinguishing between what's identical and what's not identical it's called Homotopy Type Theory, it's a very hot topic right now in mathematics that just tries to solve this, just this one problem of what things, what are things that are equal and what are things that are almost equal, or as they say "isomorphic" is isomorphism and equality the same thing? Or not? Should it be treated the same way or not?

[00:04:07]So composition and identity, these two things, they just define category theory This is all there is in category theory, it just encompasses composition and identity So you are now ready for the first definition: the definition of category. ok and I wish I could define category – what a category is very precisely but I can't Ok so I will be using terms like a bunch Ok, a category is a bunch of objects and like, you would want me to say it's a set of objects, right? Because a set has a precise mathematical meaning, right? But it's not! Okay so you have categories that have sets of objects and it's fine, but not all categories have sets of objects.

[00:05:23]It turns out that there are things that are bigger than sets.

[00:05:29]and you might think like "What can be bigger than a set?" I mean what's a set?

[00:05:32]A set is something that has a bunch of elements, right?

[00:05:38]A set is defined by membership. "Is this element a member of the set or not?"

[00:05:45]But then you know, you can build sets with sets, you can say "I have a set of sets that are two elements sets" and "I have a set of all sets that are of this particular shape" right, so elements of a set can also be sets, right? It's like, from a set theorist's point of view everything is a set right? They have a set-hammer and everything is a set-nail.

[00:06:16]So sets are built from sets and so on and and then you can say "So how do i define a set? Ok I will specify what kind of elements it has." right, so I can say okay "I have a set of sets", and there are some sets that are members of themselves and there are some sets that are not, like a set of dogs is not a dog, so that's one. Well let's think of an example of a set that is a member of itself Yeah?

[00:07:00]A set that only contains itself. Okay yeah. So now if you can define a set that – so you can also define a set of sets that are not members of itself and then you can ask "is this set a member of itself, or not?"

[00:07:29]And if it is a member of itself then should not belong to the set and if it's not, then it should belong. It's like, you know, the Barber's Paradox if he shaves himself then he should not shave himself he doesn't shave himself- so you get into these paradoxes in set theory, right? So if I say a category is a set of objects, then I immediately get into this problem and in particular you cannot define a set of all sets for some other reason, right?

[00:08:07]Because it's too big, it's like a power set, it would have to contain all its subsets as well so it's a set that contains all sets including its subsets and so on and so forth these are the mind-blowing things that set theorists are thinking about and they cannot sleep at night. So category theorists say "let's not to worry about this" well, they do worry about it but they have ways of doing this.

[00:08:38]So I will say it's a bunch of objects, ok?

[00:08:43]So a category consists of objects without specifying further whether they form a set or a bunch or a class – sometimes it's called a class which is like less precise than a set.

[00:09:08]And these objects I will just draw as dots.

[00:09:18]And these arrows are called morphisms. I'll sometimes be saying "morphisms" sometimes I'll be saying "arrows" So a morphism or an arrow is something that goes between two objects So you have an object a, then you have an object b, then you have an arrow between them and you call it f And now you might want to ask "but what's an object?"

[00:09:55]And I can't tell you!

[00:09:59]An object is a primitive in this theory, it has no properties it has no structure, internal structure, it's nothing. It's like the atom, it's a point, it has no properties Ok, what's a morphism? Well a morphism is also a primitive. It has no properties well except that every arrow has a beginning and an end ok so that's an important thing so in fact the reason for having objects is so that you can mark the ends of arrows They don't serve any other purpose as just being names for the ends of arrows.

[00:11:01]We're identifying the ends of arrows and notice that this is really funny that we are using arrows here, it's like going back to what I talked about the primitive human beings hunting mammoths with bows and arrows, right? This is really a very interesting thing that we perceive the universe through these notions that were developed by hunter-gatherers, right?

[00:11:45]They described the world in terms of spatial relationships, right?

[00:11:59]So like, when I'm talking about category theory and when mathematicians talk about it, they will put things in space. Maybe with their hands – manipulate it – so we know how to manipulate things, right? We know how to position things in space. We talk about spatial relationships: something is above, something is below. Higher level of abstraction, lower level of abstraction these are all spatial relationships, right?

[00:12:31]Hunter-gatherers also understand movement. It comes from here, it goes here.

[00:12:37]This is movement this is an arrow from A to B, right? It has this little thing here with barbs, so when you when you hit the animal it can't just pull it And of course we have social language we are hunter-gatherers, we're social animals so they talk about you know relationships between things in terms of this guy points at this guy and and by movement going from this place to that place through this place and so on. So we'll be using this language all the time and I want you to like realize what kind of language we are using and how it actually constrains us Ok? But anyway, we have objects and objects we draw in some kind of spatial relationship usually, because we are using the spatial part of our brain, we have morphisms which are arrows so they suggest movement and relationship.

[00:14:05]So, what kind of things can happen? I mean we can have, let's say, multiple arrows going between objects so we could have object A and B, you can have zero or more arrows going between them. So every time you define the category you specify "what are the objects of this category?" and for each pair of objects you specify the arrows that go between these objects.

[00:14:43]Some objects are not connected with arrows, other objects are connected with one arrow, other objects are connected with infinitely many arrows, it could be an uncountable number of arrows going between two objects So, like, if you have an idea that the category is sort of like a graph that's a good idea, right, except that you have to be open-minded about what the graph is it might have infinitely many nodes and can have infinitely many arrows between between two nodes or you have zero or, you know.

[00:15:25]But you have to expand your mind around this And of course you can have arrows going from B to A as well, and you can have arrows going from B back to B, or from A back to A, or you can have multiple arrows going from A to A, and so on. So all these are possibilities – sometimes people get stuck and I get questions like "How is it possible that you can have more than one arrow? Aren't they all the same?" no, they are different you know? You can have infinitely many or an uncountable number of arrows going from A back to A, it's okay, you just give them different names This is f, this is g, this is h. So this is what a category is.

[00:16:22]Now that's not all, because that just tells us about what are the elements of a category.

[00:16:32]We haven't talked about these two.

[00:16:37]So composition is the property, a very simple property that if you have an arrow from A to B, and you have another arrow from B to C, so we have object A, object B and object C and you have these two arrows, then there always must exist an arrow that's a composition of these. So if I call this one f call this one g, I'm using these names f and g that suggests functions, right? Because at some point this will be one of our models for a category. So this is called "g after f".

[00:17:24]"After" is this little circle. So this arrow is called "g after f". And here we have this idea that going from A to B using f and going from B to C using g is identical to going from A to C using this path called g after f. Ok, so this arrow is identical to the composition of these arrows ok? It's very important to understand that there might be multiple arrows going from A to C, right? But this one is a composition of these two and it must exist.

[00:18:13]So for every composable pair of arrows, composable means the end of one is the same as the beginning of the other. And here it's important that we have these objects to identify the ends and the beginnings, right? So the end of this is B, the beginning of this B, so they are composable. And if they are composable then there must be a composition, there must be an arrow going from here to here.

[00:18:48]So this is called composition; check.

[00:18:55]Now when we are defining a category, the category is defined by giving us objects, saying what the objects and arrows are, and then defining composition which is sort of like a multiplication table for arrows. So for every two arrows you have to define what is their composition. It's a humongous multi-dimensional multiplication table or infinitely dimensional multiplication table for every three objects you have to define all possible combinations in which you you can compose arrows going between these objects and so on right? so it's a humongous multiplication table and the whole information about the category is in this multiplication table So remember this is the multiplication table for a category, it's a composition table - how you compose morphisms.

[00:20:02]And different composition tables will give you different categories Because since objects don't have structure, since arrows don't have structure they don't contain any information. But the composition contains the information and we just want to encode everything, everything, within this composition.

[00:20:34]Now Identity. For every object – let's call it A – there is an identity arrow Which we will call "id". And sometimes id with a subscript "a", meaning this an identity for the object A. So there is this arrow that we call identity. There's one per object, for every object in a category there is an identity for this object. Now why am I calling this identity?

[00:21:11]Because of composition. So if i have an arrow going from, well let's call it A and let's call it B, okay, if I compose this arrow f with id_b I get back arrow f. In this sense this is an identity, right? If you think of this is a multiplication table, f times id is again f. So this is like a 1 in terms of composition.

[00:21:52]So I can write it using this notation that id_b after f (so first I go f, then I go id_b) is the same as f.

[00:22:12]Equal. Ok? This is one morphism, this is another morphism. They are equal, it's the same morphism, ok?

[00:22:23]And of course there is this symmetric thing where I have id_a and have some, lets call it g, from A to B. So if I start with an id (id_a) and follow it with g, I will get g.

[00:22:52]Ok so these two things, they are not the same, right? I mean this is the left identity, this is the right identity. Sometimes they are well maybe I shouldn't say that "sometimes they're the same" but its just that you have to have a left identity and you have to have a right identity So this is one of the axioms of a category, or laws of the category, that in every category – so if you think of the category as a graph, this graph has to have some special properties. For instance it has to have an arrow going back to the object, for every object there has to be this little loop.

[00:23:37]Ok. Must!

[00:23:41]So that's one law, or actually two laws, left identity, right-identity.

[00:23:47]And there is a third law, and that's associativity. So if you have three objects (well here you have three arrows). Lets have three arrows.

[00:23:59]Ok so we have object A, an arrow f to object B, then an arrow g to object C. You can combine these to have g after f. but if you have another one going to D, then you can combine these. We have three arrows (f g h), three arrows can be composed in two different ways. So this one composition, I could compose f with g first (g after f), and then I compose this with h. So I have h after g after f.

[00:24:55]Ok? Now I can also compose g with h first. Right, so I'll have h after g.

[00:25:08]Ok, now I can compose this arrow with this arrow, right, and i will get h after g after f Ok? The difference between these two is where I put the parentheses Now if I had to remember where to put parentheses every time I draw a diagram it would become extremely complex and probably my brain would just give up okay therefore the axiom of the category is that this and this is the same So h after g after f must always be equal to h after g after f.

[00:26:14]So this is called associativity, right? Normal thing. You can associate it this way or this way, you get the same result and that's extremely important in order to make this manageable for us humans. Now you might think "what if we didn't do this, is it possible still to have a theory in which this is not true?"

[00:26:42]Well it is possible and of course there are mathematicians who are working with stuff that's maybe not completely false, the associativity is not completely false, but they make associativity weak, meaning that these two ways of combining things are not really identical but they are isomorphic Ok, yes. > But what about in the real world, stuff like finite precision arithmetic > is that the kind of thing you're alluding to? Like, you're multiplying floats and the order in which you > multiply them, you may end up with a slightly different result.

[00:27:28]Well then they would not form a category in this sense.

[00:27:37]The category has to have associativity. Yes?

[00:27:40]> So what do you mean by the two ways of composition are isomorphic?

[00:27:48]It means that there is a transformation that turns this into this, that is not an identity.

[00:28:03]So morphisms can also, ok so this is a separate thing, you can have identity between morphisms that's not identity, it's weak identity, right? Here i'm assuming – well okay disclosure right now okay – I said objects don't form a set in general if they form a set then a category is called small – if they can form a set.

[00:28:40]If they don't form a set it's a large category. And morphisms on the other hand, between any two objects they form a set. So that's okay right? Now is there a category theory in which they don't form a set? Of course there is.

[00:29:04]These are the higher-order categories in which arrows don't form sets, they form objects in a category.

[00:29:11]But we are not going to talk about that.

[00:29:18]So that's it, that's all, that's the category. That's the definition of category. Yes?

[00:29:26]> In terms of definition, when you say that two arrows are isomorphic does that mean they have the same beginning and ending?

[00:29:36]What is isomorphic? > Two arrows, would they be isomorphic if they have the same beginning and ending?

[00:29:43]No, no they are different No Yes?

[00:29:53]> Is this so much different from a group?

[00:30:02]So the question is "is that different from a group?" and it has some similarities to a group, actually it has similarities to something that's called a monoid, right. Because a group is a monoid that also has an inverse, right?

[00:30:25]So there are two ways in which you can impose further conditions on this and say "what if every arrow has an inverse?" right, you can define an inverse, say if arrow f and g, if they combine, compose to an identity then one is the inverse of another. That's the definition of an inverse, right. So if you do this, then you end up with something that's called a groupoid. A groupoid is a category in which every arrow has an inverse. It's still not a group, it's more than a group, because a group is really a category in which there's only one object and arrows between them we'll be talking about a monoid as a category and in particular a group. But this is more because now you have you know you have transformations going between objects so you cannot, in a group you can compose anything with anything right? Here you can't, they have to be composable, the end of one has to be the beginning of another right you cannot compose anything with anything right that's the biggest distinction Ok, now.

[00:31:59]So let me give you an example, ok, and this is the example that we'll be studying a lot because this is an example from programming, right, we have a basic useful category that we use in programming and this is the category in which objects are types and arrows are functions. Right? Like if any single argument function takes an argument of a type A and returns a result of type B alright so in that sense, a function is an arrow or a morphism between two types so that's the category in which this is – actually in Haskell it's almost exactly – well maybe in ML this is almost exactly the category which you are working with, right. Types are your objects, functions are your morphisms.

[00:33:17]In Haskell it's a little bit more complicated because of laziness.

[00:33:28]Haskell is a lazy language so the trick is that in Haskell every type also contains this undefined value, the bottom value which means like if you try to evaluate it you will get into an infinite loop, it will take you forever because categories don't really take into account time, its like time really is really hard to describe in mathematics right whereas in computation we worry about time, right? I mean if something takes too long to calculate that's useless for us right? And in particular if it takes infinite time to calculate which means it never terminates, ok, it's a calculation so if you have a function that goes forever what's the return type for the function? It's a function that's supposed to return an integer, but it never does because it goes into an infinite loop. So in this case in Haskell you say it returns an Int type but Int type contains this special value called bottom which means it never terminates. And that's the digression I'll make once and maybe from time to time I will say "well of course except for bottoms and we are ignoring bottoms or we are ignoring never-ending calculations and so on" right so there's a lot of caveats you're in the beginning and I just want to get rid of them and later we can think of them in simpler terms. But of course you might ask but "what are types?"

[00:35:29]Types in a programming language what are they?

[00:35:39]Sets of values ok. So there is a model, a kind of simplistic model maybe this works in ML it won't work in Haskell because of the bottoms right but the simplest model for types is that data they are just sets. Sets of values right and so we can model programming as "in a category of sets" we can say okay so instead of types we will be saying sets of values, right? And functions are just functions between sets, so you can define functions on sets, functions from one set to another set. And that's a good model too. So sometimes I'll be talking about sets and functions sometimes i'll be talking about types and functions. And of course when I say functions I'm talking about mathematical functions, right? So a mathematical function is defined between sets so the function is just, you know, you take a value from one set and it gives you a value from another set So I can even draw a picture of what I mean by "function" with a set I hope you memorised the definition of a category. It's so simple, it's very elementary.

[00:37:17]So I can erase this now. So it's like you have one set, you have another set, you have elements of this set, elements of this set, and a function sort of takes elements of this set to elements of this set. And again I'm using arrows, but these are different arrows, these aren't morphisms.

[00:37:39]So one function corresponds to one morphism.

[00:37:45]But this is another thing that you have to be very careful with, this schizophrenic view of a category; that every category – well not every category, a lot of categories – come from some model.

[00:38:08]for instance you take sets, set theory. And you say "I'm going to represent these sets as object in my category" this category by the way is called Set capital.

[00:38:29]this is the category of sets and functions, right, we'll be using it quite often. So I'll be talking about the category of sets and the origin of this category is that I started with sets, right, and I know what sets are: they have structure, every set has elements and there are functions and functions in sets, they just the map elements to elements okay? So I know all this stuff, I'm looking under a microscope and I say I know it has elements, I know that the function are actually a bunch of mappings, it's a mapping from one set to another, right? Now when I build a category on top of this, I have to forget about the structure I get amnesia and I say "this is set A what's inside of the set? I have no idea."

[00:39:37]it's an atom, it has no structure, because now I'm putting on my category glasses. No structure.

[00:39:49]What are the arrows between these sets?

[00:39:53]Well, I look at what what kind of sets these are, right, I know elements of the set I know what kind of functions are possible right so I know how many arrows, how many functions are from this set to this set and I build my category based on this. I say, okay this set corresponds to an object A, this set correspond to an object B and there are 10 arrows between these objects. Fine!

[00:40:26]What are these arrows? I don't know! I forgot! I just know there are 10 of them.

[00:40:32]Ok, and I call them ABCD or fgh, okay and the next thing is, ok so if I have functions from this set to this, and I have other functions from this set to this set.

[00:40:47]Oh! I can compose them, right?

[00:40:51]What does it mean to compose functions? Well you apply a function to an argument, right you get a result you take this result you apply the second function to this result and you get a third, another result, right? So you combine this you start at here, you ended up here you get a function that goes... ok so starting from X here it produces a Y here and Y goes into Z here and there is a function that just takes X directly to Z, and that's the composition of these two functions So I know how to compose functions on sets using this, right? So I use this information to create my big infinite-dimensional multiplication table composition table for my category Set. And then I forget!

[00:42:00]And of course there is an identity function that just takes an x into x, there's another x into x, this is an identity function, right? So every set has an identity function that just doesn't move this set, it just maps the set into itself by mapping every element to itself. It's like a trivial function, right?

[00:42:30]Thats how we do it in Haskell, right? Yes? > But it doesn't have to map every element to itself though, rig ht?

[00:42:39]> it just needs to map the set to itself.

[00:42:42]No, because you can map the set to itself in many different ways, right?

[00:42:47]You can interchange elements if you want.

[00:42:51]that's also a mapping that is a set to itself, right?

[00:42:54]> Well, from a categoric point of view Ok so what we are doing here, we are studying this set and we find out that there are many functions going from this set to itself, right? One of them is the identity function, This will become our identity morphism, right?

[00:43:19]And, by the way, an identity function, when composed with any other function will give you back the function, right? So it's a good identity function, I know, from set theory.

[00:43:31]Ok so I know that I will get, in my multiplication table that I'm building, when I take this function as my identity morphism, it will be an identity in my big multiplication table. So I'm abstracting, I'm just slashing information left and right, I'm forgetting about what's inside the object, what these functions do, and I end up with this category Set. And in this category Set I have these objects that now I forgot where they came from, I have these arrows, I forgot where they came from, but I have the multiplication table, the composition table for them, right? And this composition fulfils my axioms of category theory right? I mean this composition is obviously associative, right? Composition of functions is associative, so I get a good category. I have identity, I have associativity, I have everything. So I got this huge multiplication table now I can forget about where it came from, and now i have the category Set. And in this category Set, I don't care about the structure of my object or the structure of my functions or my morphisms I forget that morphisms are really functions, I forgot all this. And now we can start thinking about, you know, what can I say about these objects just by looking at the morphisms? And it turns out I can say a lot of things. And then we'll see later you know how you can identify just by looking at morphisms, how you can identify "Oh, this set is actually empty." Right? How do you know its empty?

[00:45:38]I mean if, if you forgot the information that it has no elements, you only have morphisms. Well it turns out that an empty set has this property that can be expressed just in terms of morphisms, nothing else. And I can identify an empty set, I can identify a single element set using just morphisms, nothing else.

[00:46:09]It's not easy but it's possible.

[00:46:14]So the thing is that you can identify a lot of properties of sets just by looking at the multiplication table, you don't really have to know what's inside these sets. And that gives you a completely new way of looking at things, a more abstract way of looking at things.

[00:46:37]It's like if you think about what's inside a set, you're thinking "assembly language of sets" Thinking about elements, how they are mapped you know? That's the assembly language.

[00:46:52]Category theory gives you this higher-level language in which you don't have to look inside this set, you just look at how they are connected with arrows. And this is like the ultimate in data hiding, right? You have an object it's a it's a data type, its a set, but you cannot look inside of it. It shrunk to a point. All you have is its interface, its interface is how it connects to other objects, all these arrows coming out of this object and into this object. They define the interface. So like, if you take this idea of data hiding and abstraction this is where it leads you eventually. This is the end of the road for abstraction, right? This is the end of the road for data hiding. This is it. Like the most abstract language that we can think of.

[00:48:07]And we can stop now.