This seminar by _llll_ took place on 6th July 2008 20:00 UTC, in #mathematics channel of

The timestamps displayed in the IRC text are UTC+1.
Any explanation or errors regarding this seminar should be recorded in the discussion page.

Topic Edit

The aim was a gentle introduction to Category theory, although in the end only the definition of "Category" and a few examples were presented.

Seminar Edit

21:00:10 ChanServ changed the topic of #mathematics to: SEMINAR IN PROGRESS:
         Introduction to Category Theory by _llll_ | If you want to ask a question,
         type "!" and wait till be asked

21:00:37 _llll_: so, um, yeah, everyone shuts up now and i begin
21:01:02 _llll_: right
21:01:19 _llll_: welcome everyone to the first, of potentially a few seminars on various topics
21:01:31 _llll_: this is kind of a learning process for everyone so it may go horribly wrong
21:01:54 _llll_: so im going to give a very basic introduction to category theory, not assuming any prior knowledge
21:02:09 _llll_: so this means that there wont be anything particularly advanced in it
21:02:28 _llll_: in particular im not really going to answer quetions such as "why should i study catgeory theory?"
21:02:55 _llll_: because category theory is just like any other part of mathematics --
                 if you dont know why you are studying it, you probably dont need to be
21:03:01 _llll_: so, onwards
21:03:14 _llll_: So the first section is a definition of "a category
21:03:36 _llll_: often people call categories by single script letters, so \mathcal{C} in latex
21:03:55 _llll_: so im going to call my category "CC" which stands for "C in script"
21:04:17 _llll_: so a category CC consists of a few different things
21:04:25 _llll_: the first are called "objects"
21:04:38 _llll_: im going to use A,B,C,... to refer to the objects
21:05:06 _llll_: these things are just some sort of mathamtical ojects, so sets or whatever --
                 it's not so important, you just need to know that a category Cc has a collection
                 of objects
21:05:45 _llll_: people write things like Ob(CC) for the collection of all objects in CC, and say
                 things like "A is in CC" to mean "A is one of the objects in CC"
21:06:23 _llll_: As well as objects, CC also has "morphism" (also called "maps", or "arrows")
21:06:39 _llll_: im going to use lower case letters like a,b,c,f,g,h to refer to maps
21:06:56 _llll_: and we can write Arrows(CC) to mean "the collection of all maps in CC"
21:07:19 _llll_: every map has to have a "start" (or "domain") and an "end" (or "codomain") object
21:07:44 _llll_: so if f is a map, the domain of f is an object and the codomain is another object
                 (or maybe even the same object)
21:08:03 _llll_: we write f:A-->B to mean "f is a map that starts at A and ends at B"
21:08:13 _llll_: there are likely many maps that start at A and end at B
21:08:32 _llll_: we write Hom_CC(A,B) to be "the set of all maps going from A to B"
21:08:41 _llll_: you also see notation like CC(A,B)
21:09:25 _llll_: it's best if we assume that these sets CC(A,B) are all disjoint -- so if f is an
                 arrow then f is in CC(A,B) for precisely one pair A,B of objects
21:09:41 kommodore: !
21:09:44 _llll_: so Arrows(CC) is the union of all the different CC(A,B)
21:09:49 _llll_: kommodore: go ahead
21:10:09 kommodore: Is it necessary that CC(A,B) is a set?
21:10:35 _llll_: it's not strictly necessary, but it is usually the case that it is
21:10:44 kommodore: thanks
21:10:51 _llll_: generally CC(A,B) is a set but Ob(CC) is not a set
21:10:58 invariable: _llll_, when you use the term "map" here do you mean a function ?
21:11:05 _llll_: the categories where all the CC(A,B) are sets are called "locally small"
21:11:06 invariable: or some more specific meaning
21:11:19 _llll_: no, "map" is something that is being defined along with CC
21:11:40 invariable: thanks
21:11:48 _llll_: so CC has a bunch of things called "map"s, but these things are not necessarily functions
21:12:05 _llll_: just like the "objects" are not necessarily sets
21:12:18 Lapper: Oh, thanks. I thought I was missing something when I had no idea what a map was. :P
21:12:45 Manyfold: !
21:12:51 _llll_: go ahead Manyfold 
21:13:25 Manyfold: you wrote there are many maps between A and B but aren't these maps identical?
21:13:35 _llll_: no, definitely not
21:13:51 _llll_: ill come to some examples in a bit, it may make things clearer
21:14:07 _llll_: ok, so so far ive said that CC has a load of "objects" and "maps", and that every
                 map has a starting object and an ending object
21:14:50 _llll_: suppose that f:A-->B and g:B-->C are two maps in CC.  then to continue the
                 definition, we have to have a "composite"
21:15:17 _llll_: this means that whenever f:A-->B and g:B-->C there is a new map which i'll write
                 (f#g) which goes from A to C
21:15:32 _llll_: think of this as "f followed by g"
21:15:57 _llll_: if you like sets and functions, then # is a function from CC(A,B)xCC(B,C) --> CC(A,C)
21:16:34 _llll_: we can only compose two maps if one ends where the second starts
21:16:51 _llll_: so if y:D-->E then we cant form f#y unless D=B
21:16:55 ~zachk: !
21:17:00 _llll_: go ahead zachk 
21:17:07 ~lxuser: !
21:17:18 ~zachk: in the sets and function example is x cartesianProduct?
21:17:27 _llll_: yes, (sorry)
21:17:42 _llll_: lxuser: what was your question?
21:17:49 ~lxuser: is the (f#g) notation standard?
21:18:14 _llll_: no, not really.  actually there are a million different notations in category theory
21:18:30 ~lxuser: iirc, one usually sees (g . f) for function composition
21:18:36 _llll_: somtimes people call it "g o f" (which is what you use in set theory for  "composition of functions")
21:18:49 ~dtog: or just gf
21:18:53 _llll_: i prefer f#g because f happens first
21:19:04 _llll_: and it emphasises that these things arent necessarily functions
21:19:48 ~lxuser: _llll_, yes, following paths is a better intuition perhaps. thanks
21:20:35 _llll_: ok, so quick recap: to specify a category CC we have to give: a collection of
                 objects (A,B,C,...), a collection of maps (f,g,h,....), such that every map has
                 a start and end object, and whenever 2 maps are composable (A--f-->B---g-->C),
                 we can compose these into a (f#g):A-->C
21:20:41 _llll_: we're still not finished
21:20:49 _llll_: this composition has to be "associative"
21:21:10 _llll_: this means that if we have three maps A--f-->B--g-->C--h-->D
21:21:25 _llll_: then the maps (f#g)#h and f#(g#h) have to be equal
21:21:39 _llll_: ie it doesnt matter what order we join the three maps f,g,h
21:21:54 _llll_: there's one last part of the definition then we can look at some examples
21:22:11 vixey: !
21:22:16 _llll_: go ahead vixey 
21:22:34 vixey: Do you define equality of maps per category or how?
21:22:49 _llll_: well, we assume that we can tell when things are equal or not
21:23:01 vixey: (what does it mean for one map to be equal to another?)
21:23:10 _llll_: basically, jsut assume that you can always tell
21:23:23 _llll_: im trying not to go too far into overly-technical foundational issues
21:24:05 _llll_: the last part of the definition is that for all objects A in CC, there has to
                 be a designated map A-->A called "the identity on A", which we write as id_A
21:24:17 _llll_: and this has to satisfy the following conditions
21:24:37 _llll_: if a:A-->B is any map, then id_A # a has to be equal to a
21:24:54 _llll_: and if c:C-->A is any map, then c#id_A =c
21:25:16 ~zachk: !
21:25:20 _llll_: go ahead zachk 
21:25:34 ~zachk: is id_A the "identity map"?
21:25:43 _llll_: yeah, it's "the identity on A"
21:26:04 _llll_: so if b is another object we'll have "the identity on B", which is written id_B
                 and it goes id_B:B-->B
21:26:11 _llll_: so id_A=id_B iff A=B
21:27:08 ~DWarrior-: !
21:27:16 _llll_: go ahead DWarrior- 
21:27:25 ~DWarrior-: is id_A unique?
21:27:39 _llll_: yes, i was just coming to that :)
21:27:51 ~DWarrior-: ok
21:28:03 _llll_: so i should probably say at this point, that there is a uniqueness property here:
                 if x:A-->A is any map which has the proeprties that x#a=a and b#x=b for all a and b
                 as above, then necessarily x=id_A
21:28:37 _llll_: the proof is exactly the same way that you prove that the identity is unique in
                 a group or ring or any other algebriac sturcture you've studied before
21:28:51 _llll_: so i'll leave that as an exercise
21:29:13 _llll_: let's look at some examples, as it may make things clearer
21:29:51 _llll_: The first example is the category called "Set".  objects of Set are sets,
                 maps in Set are functions, so f:A-->B means f is a function A to B
21:30:31 _llll_: composition is what you expect -- just composition of functions, and the identity
                 on A sends a to a
21:31:11 _llll_: so obviosuly we'd need to show that composition is associative and identities have
                 the required properties, but that's not hard to do, so i wont go through that here
21:32:10 _llll_: i'll just say that this is why we dont demand that Ob(CC) is a set, since Ob(Set) is not a set
21:32:36 _llll_: there are a bunch of simialr examples, eg the category of groups
                 (it's often written as "Grp" for some reason).  here the objects are groups,
                 and the maps are group homomorphisms
21:32:52 Manyfold: does Ob(set) include itself?
21:32:55 bwr: !
21:33:04 _llll_: go ahead bwr 
21:33:20 bwr: is Ob(Set) not a set because it is not well defined or for some other reason?
21:33:46 _llll_: basically the definition of "set" means that you have to construct sets out
                 of other, previously constructed sets
21:34:02 bwr: ah ok, thanks
21:34:05 _llll_: this is what i referred to as a "technical foundational issue" before
21:34:19 Manyfold: !
21:34:26 _llll_: we'll just assume that Ob(Set) is a "collection" (or "proper class")
21:34:29 _llll_: go ahead Manyfold 
21:34:34 Manyfold: does Ob(set) include itself?
21:34:54 _llll_: no, becayse Ob(Set) is the collection of all sets, and Ob(Set) is not a set
21:35:04 Manyfold: k
21:35:26 _llll_: these are good questions to ask, but i kind of want to ignore them --
                 for a proper answer you can look up "Grothendieck universe" on wikipedia
21:36:18 _llll_: so anyway, as i was saying, we can get a category Grp where the objects are groups
                 and the maps are group homomorphisms
21:37:09 _llll_: or more generally, if you have some algebriac structure (like a
                 ring/monoid/semigroup/magma/module) there is likely a category where those
                 structures are the objectsm and the structure preserving homomorphisms are
                 the maps
21:37:19 _llll_: but i wont say too much about that
21:37:26 _llll_: for a "smaller" example
21:37:42 _llll_: suppose G is any single, fixed group.  
21:38:08 _llll_: so that means G is a set with a mutliplication and the multiplication is associative
                 and admits a unit
21:38:42 _llll_: we can build a category GG where we take one single object (say {*} )
21:39:07 _llll_: and for every element g of the group GG, we will take one map [g] :{*}-->{*}
21:40:01 _llll_: we need to say how to compose these things, and since there is only one object,
                 every pair of maps are composable, as we have {*} -- [g] --> {*} -- [h] --> {*}
                 where g and h are elements of G
21:40:14 _llll_: the composition is defied as [g]#[h]=[gh]
21:40:29 _llll_: where gh is "g multiplied by h" using the multiplication in G
21:40:45 _llll_: this is associative because multiplication in G is associative
21:41:25 _llll_: there is only one object, so we only need to define one identity, namely id_{*}.
                 and we define id_{*} to be [1] the map corresponding to the unit in the group G
21:41:57 _llll_: you can check that "1 is a unit in the group G" means exactly that [1] is the
                 identity on {*} in GG
21:42:34 _llll_: so what im saying here, is that a group can be regarded as a category with one object
21:43:27 _llll_: actually, in a group, every element must be invertible but we never used that --
                 a "monoid" is defined the same way as "group", but without the requirement that
                 everything be invertible
21:43:37 _llll_: so the natural numbers under addition are a monoid but not a group
21:44:00 _llll_: and given a monoid M, we can defome a category MM with one object.
21:44:16 _llll_: and it is not hard to see that *every* category with one object gives us a monoid
21:44:38 _llll_: (the elements are the maps from the category.. i'll leave the rest as an exercise)
21:45:03 _llll_: so "monoids" are exactly the same as "categories with one object"
21:45:24 ~zachk: !
21:45:29 _llll_: go ahead zachk 
21:45:54 ~zachk: did monoids get 'discovered' in category theory, or are they from some other
                 branch of mathematics?
21:46:07 _llll_: monoids were known well before categories
21:47:21 _llll_: (oh, and you can turn this on its head, and say that a category is a
                 "monoid with many objects")
21:47:32 _llll_: so a different kind of "small" example comes from partially ordered sets
21:47:55 _llll_: a partially ordered set is a set P and a relation "<=" on P
21:48:42 _llll_: this has to be reflexive, meaning that x<=x for all x in P
21:48:58 _llll_: and transitive meaning that if x,y,z are in P with x<=y<=z then x<=z
21:49:15 _llll_: we can build a category corresponding to P as follows
21:49:25 _llll_: for objects take the elements of P
21:49:41 _llll_: (so if we call the partially ordered set P, and the category PP, then Ob(PP)=P)
21:49:51 ~lxuser: !
21:49:58 _llll_: go ahead lxuser 
21:50:54 ~lxuser: by a "monoid with many objects" do you mean a monoid action on the set of objects?
21:51:21 _llll_: no, i just mean that you can think of a category as a generalisation of
                 the notion of monoid
21:52:00 _llll_: so if you understand something about monoids, you can likely apply that
                 understanding to categories.  it's an analagy basically
21:52:47 _llll_: ok, so to continue with PP, we had Ob(PP)=P, so we are going to have lots of
                 objects, one for each element of P
21:53:07 _llll_: and for maps, if x<=y in P, we will add exactly one map x-->y to PP
21:53:40 _llll_: so we can only have a pair of compsoable maps x-->y-->z if x<=y<=z
21:54:04 _llll_: but then x<=z by transitivity, so we define the composite of the maps to be the
                 unique map x-->z in PP
21:54:46 _llll_: (since there's at most one map between every pair of objects in PP, im not giving
                 these things names. we culd call the map x-->y "(x,y)" if we liked)
21:55:28 _llll_: associativity is easy, and the identity map on the object x is the map correspondng
                 to the statement that x<=x
21:56:13 _llll_: so this shows that partially ordered sets give another example of categories.
                 so category theory is a generalisation of the notion of "one partially ordered
                 set" *and* of "a group"
21:57:21 _llll_: ok, so it's now about an hour in.  i was going to talk about products, but
                 probably it's best to leave that for another time, since 60mins of mathematics
                 is enough for anyone. instead do people have any questions?
21:57:36 ~zachk: !
21:57:45 _llll_: go ahead
21:57:58 ~zachk: if i kind of get monoids, how far am I from monads?
21:58:06 _llll_: not very actually
21:58:25 ~steven__: !
21:58:28 _llll_: to define monad you need to define "functor" and "natural transformation" which
                 take a while
21:58:40 _llll_: there is a sense in which a monad is a special kind of monoid
21:58:57 ~lxuser: zachk, monoids are easy in that elements of a monoid can be represented by
                  "strings" in the formal language sense.
21:59:08 _llll_: steven__: go ahead
21:59:12 ~steven__: can you give another example, where objects aren't sets like in the last example
22:00:04 _llll_: ok, for objects take points on a plane (ie elements of R^2)
22:00:17 _llll_: and a map from one point to another is a path on the plane
22:00:29 _llll_: composition means "join paths together"
22:00:47 _llll_: and the identity is the "path of length zero", ie the "do nothing" path
22:01:42 _llll_: if you know what topological spaces are, then you can replace "the plane" with
                 any topological space, X, and "paths on the plane" with continuous maps
                 from the inverval [0,1] to X
22:01:57 _llll_: this is called the "fundamental infinity groupoid on X"
22:02:45 kommodore: I suppose the category Top of topological spaces and continuous maps
                    is another example
22:03:18 _llll_: usually people have preferred to identify homotopyic paths, and then you
                 get "the fundamental groupoid on X", and even more usually you pick a point
                 x in X and require the paths to start and end at x, so there's just one object -- 
                 so we have a monoid (and in fact a group, since you can reverse paths --
                 it's the "fundamental group" at x)
22:04:34 _llll_: i guess people who like programming in ML or haskell like the example of the
                 "category of types", where the objects are types and maps A to B are functions
                 that take one variable of type A and give an output of type B
22:05:52 ~DWarrior-: !
22:05:56 _llll_: go ahead
22:05:59 vixey: is there any analogue of a category for dependent types?
22:06:07 ~DWarrior-: I must have missed it, because I still don't know if id_A is unique
22:06:32 ~DWarrior-: if I think of it as path from point A to point A, it doesn't have to be unique
22:07:15 kommodore: id_A=id_A#id'_A=id'_A
22:07:20 _llll_: if x:A-->A has the properties (1) and (2) where 1) is  that whenever a:B-->A
                 then a#x=a and 2) is that whenever y:A-->C then x#y=y, then x=id_A
22:07:38 _llll_: with the path example, the identity is the path that has length zero, ie "do nothing"
22:08:10 _llll_: other paths are just maps A-->A only the identity has the properties (1) and (2)
22:08:33 ~DWarrior-: ah, ok
22:09:18 _llll_: maybe next week i will talk about how to do "cartesian products" in a general
                 category, and talk about "universal properties"
22:10:48 Manyfold: so next week your seminar will continue?
22:11:06 ~DWarrior-: is the seminar over officially?
22:11:06 _llll_: yeah, unless anyone else has a burning desire to talk about something else
22:11:53 ~lxuser: wouldn't it be better to  define functors and natural transformations first?
22:12:00 bwr: _llll_: thanks, i enjoyed the seminar
22:12:03 _llll_: hmm, possibly
22:12:36 _llll_: i guess there's two options, one is to talk about universal proeprties,
                 one is to tlak about natural transformations and the yoneda lemma

22:41:43 ChanServ changed the topic of #mathematics to: NEXT SEMINAR: Sunday 13 July
         at 20:00 UTC Functors and Natural Transformations by _llll_

22:43:27 * ~zachk thanks _llll_ for the seminar
22:43:47 _llll_: then the week agfter i will try and get something different
22:46:25 ~DWarrior-: thanks for the seminar
22:46:26 _llll_: thanks for everyone for coming, especially people who asked questions
22:47:26 _llll_: if anyone has any suggestions on how to improve things, im listening
22:47:32 shminux: when is the transcript going to be posted?
22:47:40 shminux: if at all
22:47:43 _llll_: oh, good point