Lecture 2: Richard Southwell - Category Theory For Beginners: Functors And The Category Of Categories

16 May 2019

In this video I introduce more categories of structured sets (the category of graphs, and Mon the category of monoids, and Pre, the category of preordered sets). I also define isomorphisms in category theory. I also define functors between categories, and discuss the category of categories which is called Cat. I was going to define categorical products in this video, but I will save that for the next video.

Transcript

0:02

so today is going to be a pretty wild one because we're going to look at lots

0:08

of extremely interesting categories we've already talked about this category set which has objects representing sets

0:17

arrows representing functions between sets and we're going to see that other

0:23

kinds of mathematical objects also naturally live in categories for example

0:28

there's going to be a category of graphs directed networks so the objects there

0:34

are going to be graphs all graphs represented and there's going to be some arrows natural sort of ways that we can

0:43

compare these graphs and there's lots of other very important categories which

0:50

basically consists of these infinite families of mathematical objects is a category of modes there's a category

0:58

although there's many of them and we're going to discuss some today but I think maybe the best thing that we're going to

1:04

do is we're going to discuss this notion of a functor so just like a function can

1:13

be used to compare two sets a functor can be used to compare two categories

1:19

and it's basically maybe the second most important definition in category theory

1:25

after the notion of a category itself and essentially this allows us to get to

1:33

why maybe one of the most mind-blowing

1:38

ideas in category theory which is the notion that there is a category of

1:43

categories so we can have a category where every object represents a category

1:51

and we have these functors which I'm going to define as the arrows so this

1:57

really lifts a lot to a whole new level of abstraction I mean it's like it's

2:04

pretty crazy thinking about this category set which has every object in

2:11

it represents a set and you know that's an immense truck anyway but from the perspective from

2:18

this new perspective that's just a category so that's just going to be an object in this category of categories so

2:27

we're going to get there and we're going to discuss that we're also going to talk

2:32

about the idea of isomorphism so if you have two mathematical objects which are

2:40

similar looking how do you know that and how do you use category theory to

2:45

understand that for example if you have two sets which have the same number of elements can we express that in

2:53

categorical terms that's what we're going to do okay so a lot of objects in

3:02

mathematics can be thought of as structured sets so we've already talked

3:08

quite a lot about sets and how to think of them in terms of category theory so

3:16

let's now think about some other kinds of objects so for example a directed

3:24

graph also known as a directed Network is a set of vertices but there's some

3:32

extra structure in particular we have arrows from one vertex to another and

3:40

they can be thought of as extra structure which we kind of imposed onto

3:48

the sets in particular we can represent these arrows as pairs of vertices okay

3:56

so we have this set of elements with set of vertices and then we also have some extra information yeah we have a sorts

4:03

of mean say one one is Pedro two the three is paired with two and so on so we

4:10

have this set plus extra structure a structured sets and then we can do the

4:17

same trick as we did before we can say well what about all graphs what about all directed graphs we can think of

4:26

those as objects in a big category but then we have to think of some kind

4:32

of arrows to have between those objects and a natural choice is going to be

4:39

functions between these sets between these vertex sets which preserve the

4:45

structure which we have so in this case the structure is these edges these

4:53

directed edges that we have in our graphs and so we're going to define a

5:00

type of function a special kind of function which respects the graph

5:07

structure and that's called a graph homomorphism mathematicians for some

5:16

reason like to use this word morphism

5:22

sometimes instead of a word arrow

5:27

personally I prefer the word arrow because it's clear more clear what it means when when you first hear about it

5:35

anyhow these graph homomorphisms are functions which preserve the graph

5:42

structure and the exact definition is that it's a function from the vertex set

5:49

of one graph to the vertex sets of another graph which has the property this if u is linked to V in the original

5:58

graph then the image of you should be linked to the image of V so this forms

6:05

another category and these definitions which we are talking about can all be

6:12

applied equally well to this category of graphs as they can to this category of

6:21

sets which we've been discussing another

6:27

important category is the category of

6:32

monoliths so remember a mono ate can be

6:38

thought of as a category which just has one object so let's call

6:47

this object a and there's going to be

6:52

this identity arrow I da and this mano

6:58

it may have more arrows as well going from this object to itself and we can

7:07

compose those arrows with each other and it's really in this arrow composition

7:12

that the interesting things in moments happen this isn't so this isn't usually

7:20

the way that mathematicians think about monoids usually they think of a monolid as a sort of structured set so the elements

7:30

will be corresponding to arrows in in our point of view but you know normally

7:35

they'd think for example an example of the mono Eid would be where the elements

7:41

in the set are the whole numbers and we

7:53

can we have some kind of operation that we can do on a pair of elements in our

7:58

set which gives us another one for example addition so they'd say oh well

8:04

that's an example of a mono way so this is another type of structured set that

8:09

we can have we can have some kind of sets with some kind of operation by which we can take a pair of elements and

8:15

produce a new one and that's another kind of structured set and again we can

8:22

come up with a good idea of what should be considered an arrow for those kind of

8:29

objects you can make a category of mono eights where the arrows are functions

8:34

which respect this kind of structure of this operation I'm going to define the

8:41

category of MA nodes properly later okay so now I want to introduce this idea of

8:50

isomorphism and that's a special kind of arrow that can be in a cat

8:55

and when there's an isomorphism from one

9:01

object to another in some sense it means that the first object kind of looks the

9:06

same as the second one so before I get into that I just wanted to recap a

9:12

little bit about what we did last time to do with this terminal object or final

9:18

object so we're talking about this category set which has objects as sets

9:26

and arrows as functions so this category

9:31

set has a what's called a final object or a terminal object and that's an

9:40

object which has the property that for any object there's just going to be one

9:45

arrow into it and recall that the terminal objects in this category set

9:53

are just singleton sets okay so from

9:58

this set here there's just going to be one mapping into this singleton sets

10:06

similarly here there's just one mapping

10:14

but the interesting thing is that from this singleton set to this sets there

10:22

are two mappings mapping is just another

10:29

word for function okay and similarly

10:38

there are three mappings here

10:59

okay so this is very nice because we're essentially able to identify these sets

11:06

by mm how many arrows they have coming into them from this terminal object now

11:17

this is what it looks like when we're allowed to look inside these objects but in this category set what the picture

11:24

really looks like is this and we also

11:34

have these identity arrows but I'm not going to draw those okay so the

11:42

remarkable thing as I was discussing last time is that we can basically say

11:48

things about what these objects represents just by looking at the arrows and sometimes we have to think about the

11:57

composition of which arrows make which arrows but nevertheless really we can gets the information from just looking

12:06

at the relationships between these objects and now we're going to define

12:11

this idea of isomorphism and we're going to do pretty much exactly the same trick

12:17

so suppose you have a set here with two

12:24

elements true and vice and here's

12:32

another set this has two elements one

12:40

and two so let's call this sets capsule a capital B well we can ask how do we

12:50

know that these two sets are the same size how do we know that they look the

12:55

same how do we know that one set can be obtained by relabeling the other one

13:01

well the presence of certain functions between them indicates this so in

13:09

particular there is going to be a function like this which is what's

13:24

called one-to-one mapping from this set on to this set

13:29

it's called one-to-one because it doesn't send distinct elements to the

13:36

same element and it's called on to because it covers the whole sets that is

13:42

the target okay and that is an

13:47

isomorphism so the important thing about

13:55

this function is that there's another function which undoes it and that

14:09

property of it having a sort of inverse is what makes it's an isomorphism okay

14:18

so the important thing then is that if we compose these functions together so

14:25

if we do F and then we do G the results

14:30

doesn't change anything so the composition of F followed by G is the

14:37

identity arrow of this so it's the

14:44

identity function just sends everything to itself

15:03

okay then and similarly if we go from

15:09

here and we apply G and then we apply F the result is just the identity function

15:15

happening on this set B and that is the full definition of the isomorphism in

15:22

the categorical terms so in terms of category theory this picture looks like

15:28

this so we're going to do our trick

15:33

again we're going to take this thing that's happening in set theory and we're

15:38

going to express it in categorical terms so we're going to get a a definition of

15:44

what's an isomorphism is for between objects in any category okay so what I'm

15:55

saying here is that an arrow F is going to be called an isomorphism if there's

16:02

another arrow jeanny which goes in the opposite direction and they have the property

16:09

that if we start here and we do F and then G and compose them the result is

16:15

the identity arrow on a and similarly if we starts at B and then we go along G

16:21

and then along F and we compose them but then the result is the identity arrow on

16:28

B and you can see that that same thing is what's happening in set theory indeed

16:34

we just looked at what was happening in set theory and just lifted the just

16:42

translated what was going on into category theory terms but it turns out that this is very fruitful because this

16:49

same definition of isomorphism can be applied to loads of other categories and

16:55

it usually gives quite sensible results so for example if we think about this

17:02

other category of directed graphs the objects of directed graphs and happies

17:09

homomorphisms as arrows then if we just use this same definition

17:15

we get that this does indeed tell us that you know if we just apply this same

17:22

definition we find that it makes a lot of sense because in this case an

17:29

isomorphism is a special kind of function that sends the vertices on one

17:37

graph to the vertices of an ova graph which is essentially just relabeling the vertices it it preserves the graph

17:43

structure exactly so when we use this definition in the category of graphs

17:49

it's called a graph isomorphism an isomorphic graphs it's basically just the same structure but perhaps labeled

17:58

differently and we can use this idea of

18:05

isomorphism to understand more about what's going on in category theory as well so recall the terminal objects is

18:19

an object that just has one incoming arrow from every other object well we've

18:27

already seen that this is an important definition in category theory but what

18:34

happens if there are multiple terminal objects that may well be

18:53

I mean if

19:10

I mean if this notion of being a terminal object means some importance

19:17

then if there's multiple ones how do we know so if it's important to focus on a

19:24

terminal object in order to build some definition in category theory then how

19:32

do we know which one we should pick should we focus on this one or should we

19:37

focus on this one well the thing is that it turns out that any two terminal

19:43

objects are isomorphic and you can see that in a quite straightforward way

19:50

because we know that there's just one incoming arrow into this terminal

19:56

objects from any other objects and similarly there's just one incoming

20:02

arrow from this terminal object from any object so if we that means there's going

20:08

to be arrows between them this one here and this one here now what happens if we

20:16

compose those arrows together well if we

20:21

compose this arrow with this arrow that must result in some arrow which starts

20:26

at this object here and goes back to itself but there's only one such arrow

20:32

because it's a terminal object that's the definition and we also know that

20:37

because this is a category this has to have an arrow which is the identity

20:44

arrow so we know that composing this with this make some arrow from itself to

20:50

itself we know that there's only one and we know that it has an identity arrow so

20:56

that means that composing this with this must be the identity arrow similarly for here so it turns out that

21:04

these arrows between terminal objects are isomorphisms so what that means for

21:11

example in set theory is that the only terminal objects are these singleton sets okay now we've had a look at lots

21:20

of categories it's time to talk about how to compared it maybe isn't too much of a

21:27

stretch to say that a category really is the sort of quintessential

21:35

representation of structure or pattern I mean whenever you have a structure or a

21:40

pattern very often somehow a category represents it and a functor if you by

21:49

this metaphor then a functor is really a

21:54

sort of it's the basic idea of pattern recognition okay how do you see one

22:01

pattern inside another and essentially it just corresponds to a sort of mapping

22:09

and sort of function sending the objects and arrows in one category to the object

22:15

scenarios in another category which preserves structure okay so now it's

22:23

time to define maybe the second most important notion in category theory and

22:29

that's the idea of a functor from one category to another so a

22:35

function goes from one set to another a functor goes from one category to

22:41

another and it preserves the structure of the category okay so I'll start with

22:48

an example here we have a category C and a category D and I want to illustrate a

22:55

functor which goes from this category to this category so a category consists of

23:02

objects and arrows so a functor is really two functions one that sends the

23:10

objects in this category to the objects in this category and a little one that

23:15

sends the arrows in C to the arrows in D and so what we're defining here is

23:30

I thought f-from

23:38

categories from a category C to a category D so the first part of the idea

23:47

is there's going to be a function that sends the arrow the objects of c2 the

23:53

objects of deep sellers let's draw that in so then the image of a and this map

24:09

will call F a this is going to be F of B

24:19

and this is going to be F of C now the

24:26

second part of the definition is we want to send the arrows of C to the arrows of

24:31

D but we want to do that in such a way that the source and destination of

24:37

arrows is preserved and also the composition is preserved okay so for

24:51

example we want to send this arrow F here to this arrow here which we can

25:03

call capital F of F so let's start to

25:09

write down the definition of the function so firstly we're saying that it

25:16

sends objects in seeds of objects in d and we're noting the image of an object

25:21

a is capital F of a

25:29

okay then the second thing we're setting is that the image of an arrow which

25:34

we're also using this capital F so we're sort overloading the usage of capital F

25:41

but that's just more convenience but anyway the image capital F of this rof

25:51

is going to be an arrow in D and it's going to start the image of the source

26:01

of F and it's going to end at the image of the destination of F so in a way the

26:07

source of source and destination of these arrows has got preserved and we

26:13

also want composition to be preserved so

26:23

we have this extra condition I mean think about this arrow in category C

26:31

this is the composition of F and the composition of P so where do we want this to get sent to in category D well

26:39

we want it to get sent to the composition of where F got sent to and

26:45

where G got sent to

26:59

okay so we can write this by saying that

27:16

f of G so the image of our energy after

27:23

the image of our F in this category D better be equal to F of G of F for any

27:34

composable arrows G and F so what we're basically saying here is that the

27:40

composition of the image of arrows is the image of the composition of the

27:45

arrows one more condition my simple one is that we want the functor to preserve

27:52

these identity arrows so the final thing we need is that F of ID a is equal to ID

28:14

of F of a so for example we want to be

28:22

sending well we want to send each identity arrow of a to the identity

28:32

arrow of F of a so if you think about it this really is the kind of natural way

28:37

you'd want to define a functor and

28:43

there's going to be lots of functors in category theory and they're very useful

28:48

notions extremely useful and I mean this

28:53

functor here notice that it doesn't it

29:00

doesn't send things to everything in this category D nothing gets sent to these these objects and arrows over here

29:11

and that's okay has to be just like a function doesn't have to cover all of its target sets

29:17

these functors don't have to cover all at the target category and similarly

29:23

functions can send things to like

29:29

distinct things to the same thing and so can functors okay so an extreme example

29:35

of this consider this category here that just has one object and an identity

29:42

arrow well there's a functor from c2 this category here where we simply

29:48

collapse everything down so we send every object to this object here and we

30:01

send every arrow this identity our own

30:06

etc and that's going to be a properly defined functor so functors really give

30:15

you the main way to compare categories

30:23

so the thing is we're focuses they also act like arrows in a category where the

30:31

objects themselves are categories so we can compose formatives together so I

30:38

have three categories here I haven't drawn the identity arrows and we should

30:44

have a we can have a thought

30:56

like this and then there will be a little functor like this and so if we

31:09

call this one F and this one G then we

31:14

can compose those together just by composing the maps and we get the G

31:20

after F is going to be a functor from this category on the left to this category on the right so we can compose

31:26

our functors and we can show you that this functor composition is associative

31:31

and we also have a kind of identity arrow a functor where we just send every

31:38

object to itself and every arrow to itself okay so now it's time for a

31:44

really wild idea we've seen that there are these large-scale structures we have

31:51

this one set that represents what's going on in set theory we have one that represents what's going on in graph

31:57

theory there's a category of mono leads which represents what's going on to do

32:04

with mono AIDS and now we're going to think of each of those immense

32:11

structures as a little object in a new category a category of categories so in

32:20

this category the objects are categories and the arrows are form tools because

32:29

you can compose functors together they are associative we have identity folders

32:37

that just send every object and themselves and every arrow to themselves and so we have a category of categories

32:45

and this has a special name it's usually called cats and it really is an

32:55

extremely interesting thing to think about in my opinion I mean a lot of

33:01

what's going on in mathematics can be thought of in terms of sort of wandering around in

33:08

but this is like a whole nother level of abstraction above that because this is

33:13

you know thinking about this category cats we have all the different

33:19

categories so that you and we can think about how to go between them and how

33:24

they're related to each other and all the rest of it so yeah I think this is

33:30

an interesting idea I should say that in addition to this thing having objects

33:36

and folders there's also something else in this category well there's something

33:43

else in this structure it's actually more than just a regular category because there are also things called

33:52

natural transformations which I'm going to introduce later essentially a natural

34:00

transformation would be a sort of arrow

34:05

between parallel functors okay but I'm going to discuss that later but you

34:12

don't need to know about that to appreciate this structure I mean it's

34:18

you can think about it now you have the you know about what categories are and

34:24

what forces are and yeah it's a very interesting thing okay so now we know

34:33

about functors I can properly define another couple of interesting categories

34:40

of the structured sets so one of them is called bomb and the objects in mom are

34:49

MA nodes so normally when people talk

34:54

about MA nodes they they give this kind

35:01

of set theoretic definition that oh you know we have assets and we have an operation that takes a pair of elements

35:08

and makes another element and it's associative and it has identity elements but we don't really need to talk about

35:14

that because we know category theory so we can just think of a monoid as a

35:19

category of one objects so we have lots of different modes I'd say all the different modes and these are our

35:29

objects now in this category Mon and

35:42

then the arrows between these modes are filters and that's the definition of a

35:54

this monolid category if you look up this definition of what people consider to be a Monroy tum' it's nothing more

36:02

than a functor defined on this type of thing it sends this single objects as

36:08

single objects and it sends these self looped arrows which we think of as our

36:13

elements in the Monroy to self looped arrows in the other category and it

36:18

preserves composition and it sends the identity arrows the identity arrow so

36:25

that's that's a this category mom okay

36:30

so another one of these big large-scale categories that we can define is called

36:37

pre and this one has pre ordered sets as objects and it has some arrows which

36:46

preserve the structure of those so a pre ordered sets I gave a definition of them

36:53

in the previous in the previous in a previous video but essentially an

37:00

equivalent definition is it's just a category where you don't have any parallel arrows and it turns out that

37:08

the natural type of morphism people think of between pre ordered sets this

37:16

kind of structure preserving map the arrows again just correspond to functors

37:22

okay so this category pre order has the pre orders as objects and

37:32

falters as arrows okay so a functor like

37:42

this sorry I mean an arrow like this from this pre-ordered set to this pre-ordered set since the objects adhere

37:49

to the objects in here and normally when most people think about pre-ordered sets

37:55

they would expressed that there's an arrow from A to B by writing a less than

38:01

or equal to B we don't do that so much because you like to think of things in terms of arrows categories and so on but

38:10

you know an equivalent way to define these type of arrows it's say that when

38:15

a is less than or equal to B we want our

38:20

athlete to F our so our arrow F to be a functor or to be a if we like mean think

38:27

of it as a map from these objects these objects such that when a is less than or equal to B we have F of a is less than

38:37

or equal to F of B which is just a fancy way of saying that it preserves the

38:44

source and destination of the arrows in this pre ordered set and indeed that's all we have to do when we're comparing

38:51

pre ordered sets because when there's no parallel arrows it doesn't really matter what the composition of what arrow is

38:59

with what because you know there's only there's only one arrow say from A to C

39:05

so we know that's automatically the composition of the area from A to B in the area of B to C we don't have to

39:12

worry about saying specifically you know giving these arrows labels and saying on

39:17

you know this one is the composition of this one and this one because if we know this is a pre ordered set then that has

39:24

to be that confident okay so I've actually I want to say more about the

39:31

definition of functors because I've actually only told you half of the story in a way there's another type of functor

39:39

I have to tell you about it's not a lot more detail but it is important

39:46

so the critical thing is that if we have any category we can just reverse for

39:52

directions of all that the arrows and we get to another category that's called the opposite so we naturally have this

39:59

type of duality happening in category theory and the type of functor I've told

40:07

you about so far is called a covariant functor it preserves the direction of arrows so if we have a category like

40:15

this then this type of functor i've

40:24

already told you about this so-called it's actually called a covariant functor

40:39

would look something like this might look something like this

40:53

obviously sends the objects to objects and it sends an arrow F to the arrow

41:07

which goes between the image of its source and the image of its destination

41:21

so these covariant functor zahra characterized by saying that if if F is

41:29

a covariant functor then F of F is going

41:35

to go from F of a to F of B that's the

41:45

image of an arrow in this original category that goes from A to B and we

41:53

also have this property with its F of

42:00

the composition of a pair of arrows will be the composition of F of that the

42:13

image of the composition is the composition of the images now a contravariant functor is the same kind

42:24

of idea but we reverse the arrow directions okay so we still send the

42:36

identity arrows to identity arrows but the difference for these contravariant

42:41

functors there's two differences one

42:48

difference is that F of this arrow F is

42:53

going to go from its destination the

43:00

image of its destination to the image of its source

43:06

and also we now have to sort of reverse

43:12

the order of composition because we want this thing here now to get sent to this

43:19

thing here and this is obtained by composing in the other direction so we

43:25

want now F of G after F to equal F of F

43:37

after F of G so this defines our so

43:45

called contravariant functor

44:05

so this arrow here is going to get sent

44:12

to this arrow here the objects are still going to get mapped in the same way it's

44:19

just that we're reversing the directions of the arrows okay and so yeah we have

44:25

these two different types of functors when someone doesn't say they're usually

44:32

talking about a covariant functor i've been talking about covariant functor x' all the time today okay so I just want

44:39

to add a couple of footnotes so that this is more logically consistent I

44:45

wanted to say is about the sort of size

44:52

of these categories and things I mean I've purposefully been playing a

44:57

little bit silly with the terminology I've been referring to things as sets

45:04

which may be actually larger than sets and I've just been doing that because I

45:13

wanted to sort of sidestep this this

45:18

extra complication of saying well okay so the collection of all sets is that a

45:24

set no it's not a set mm-hmm it's something sort of larger than a set

45:31

basically to define things properly you define the sorts of universe of sets that you're interested in and that's a

45:38

universe of sets and every set in that universe is a is an object in this

45:49

category set and that universe itself is not a set it's something it's something

45:54

greater than that and similarly so we'll

46:00

say a category is small when it does actually have when it when the

46:06

collection of objects it has is actually a set and all these little categories

46:12

I've been drawing as small if you have category that has an object for every

46:17

natural number that's small because the set of natural numbers is just a set of

46:23

course but when you start talking about the collection of all sets or the

46:29

collection of all graphs or the collection of all mono AIDS or the collection of all categories those

46:36

collections are not technically sets they're they're something greater so you

46:44

call such categories large categories