Howdy yâall,
On Monday the 6th, John will be giving talk number three in his series on category theory for computer scientists. If you want to learn about natural transformations, come on by CS 4310 at 12pm. Below
is a combination abstract/summary, provided by John, if youâve missed a talk or are curious about the expected context. Hope to see yâall there.
- Calvin
Abstract: Intro to Category Theory 3
So far we have talked about categories and functors. In this lecture we will define and try and get some intuitions about natural transformations. It is often said that category theory was developed to really study natural transformations.
In fact Mac Lane writes:
As Eilenberg-Mac Lane first observed, "category" has been defined in order to be able to define "functor" and "functor" has been defined in order to be able to define "natural transformation".
I'm also going to take this time to give a quick recap of topics that we have approached so far.
Lecture 1 (Categories)
A category has
- objects
- morphisms
Morphisms compose, composition is associative, and each object has an identity morphism.
Many equations in category theory can be represented via commuting diagrams:
Nodes of the diagram are objects in the category, edges are morphisms. The property of a commuting diagram is that every directed path with the same source and ending object yield the same morphism.
We use category theory as a generalization of algebra. That is we understand mathematical objects as objects in a category and morphisms are structure preserving transformations of those objects. Even though it is possible to do so,
we don't embed elements of a group, for example, as objects or morphisms in a category. Instead, we study groups through the category of all groups Grp, where objects are groups and morphisms are group homomorphisms. We then learn about groups not through
the elements of a groups, which is opaque in the category, instead we understand groups relationships through the morphisms.
We briefly talked about a smalle list of some examples of categories
Set - Objects sets, morphisms total functions
Set_{\bottom} - Objects sets with bottom, morphisms are partial functions
Grp - Objects groups, morphism group homomorphisms
Partial order (P, <=) - Objects elements of P, morphism between a and b if a<=b.
Cat - Objects (small) categories, morphisms functors
We talked about small vs large categories.
Small categories are ones which objects and morphisms form a set as opposed to a proper class.
Large categories are not small.
I also mentioned locally small categories. A category is locally small if for every pair of objects the class of morphisms between them form a set.
For the above examples only the partial order is a small category. All the other categories are large.
I also want people to make the connection between category theory and functional programming. We talked about the category Hask (which may not be a real category due to some programming constructs). We want to think of objects in this
category as types, and morphisms as functions between these types. We will try and use many examples from programming to understand category theory. We may see later how deep this connections goes.
To get in the spirit of category theory we then talked about some patterns of objects and morphisms. I will list them here
Initial object Terminal Object Product Co-product
Set {} Singleton Set Cartesian Product Disjoint Union
Hask void () (,) Sum Type
Partial Order \bottom \top meet join
Grp Singleton Group Singleton Group Group Product Free Product
Lecture 2 (Functors)
In the next lecture we talked about functors. A functor is a structure preserving transformation.
A functor F : C -> D maps objects in C to objects in D, and morphisms f : c -> d of C to morphisms F f : F c -> F d of D with
- (unit) F (id_x) = id_{F x}
- (composition) F (g . f) = F(g) . F(f) for morphisms g and f of C.
Intuitively, a functor embeds the category C in the category D. They can smash objects and morphisms together but they cannot break any connections. Functors also preserve commuting diagrams.
The above definition defines a covariant functor. A contra-variant functor G : C -> D maps objects of C to objects of D and morphisms f : c -> d of C to a morphism G f : G d -> G c with
- (unit) G (id_x) = id_{G x}
- (composition) G (g . f) = (G f) . (G g)
A contravariant functor reverses the arrows of C. We can equivalently say a contravariant functor G is just a covariant functor G : C^{op} -> D, where C^{op} is the opposite category of C.
A functor F : C -> C is called an endo-functor.
In programming we only have one category, say Hask. Thus, all functors are endo-functors. In programming, functors are containers, such as Maybe, List, Stream, etc. These functors give a new type for any other type, such as [a] for
a type a, and they also provide an fmap :: (a -> b) -> (f a -> f b) for functor f. fmap for lists is just map. A good intuition is that endo-functors are containers.
Finally, we talked about a particular functor in category theory the hom functor, denoted Hom( - , =) or C( - , -), which maps a locally small category C to Set. This functor is actually a bi-functor which maps pairs of objects in
C to the set of morphisms between those objects. Remember a bi-functor is a functor from a product category C x D, where objects are pairs of objects and morphisms are pairs of morphisms. The hom functor is covariant in the second argument and contravariant
in the first. Equivalently the hom functor is a functor C(-, -) : C^{op} x C -> Set.
If anyone has any questions, just let me know.
_______________________________________________
Pl-seminar mailing list
Pl-seminar@xxxxxxxxxxx
https://lists.cs.wisc.edu/mailman/listinfo/pl-seminar
![[Computer Systems Lab]](http://www.cs.wisc.edu/pics/csl_logo.gif){kind=logo}