Re: [pl-seminar] Talk on Monday at noon in CS 4310

[JOHN CYPHERT <jcyphert@xxxxxxxx>]

Hi, all,

I'd like to follow up on a few questions I got during the last category theory talk:

One point that got brought up is whether I could produce a simple proof using category theorem to prove a theorem that would be complicated to prove otherwise, and then this point moved in the direction about why learn category theory in the first place.

As to providing a simple proof using category theory, I don't think this is going to happen for us. These examples would mostly come from algebraic topology, which I would imagine we don't have the background in nor the category theory definitions to explore. For some specific examples where category theory has been used see this math stackexchange thread and the work of Alexander Grothendieck.

As to general motivation for learning category theory, I would say that with these lectures I am not trying to advocate that this is something that you need to know or something that will definitely be useful. Instead, I am doing these to gain some general lecture practice for myself, as well as present a topic/language that you might here other PL people and mathematicians talk about. I see the exercise as trying to increase that bandwidth of communication between ourselves and some other parts of the field, as opposed to giving you tools that you will use to prove something that you have been struggling with for a long time. For a better explanation of some of the usefulness of category theory see this math stackexchange thread.

With that general question out of the way, there was a technical question about natural transformations that came up. I didn't quite understand the question at the time, but I thought about it as I was getting ready this morning and I am now prepared to answer it.

The question was an observation that functors can collapse objects and morphisms from the source category to the target category. If such a thing occurs, is there a relationship between the components of the natural transformation at the "smushed" objects? If I am interpreting the question correctly the answer is no. The components can be different.

Let me illustrate with an example, and then I will go deeper and give a very specific example of functors and a natural transformation to refute the claim.

Consider a category C, with two objects: a and b, and three morphisms: the identity at a, the identity at b, and a morphism f : a -> b. Now consider two functors F : C -> D, and G : C -> D, where F a = F b = G a = G b. That is both F and G collapse both a and b to the same object in D. Call this object in D, d. Now, consider a natural transformation alpha : F -> G. The question then becomes is the morphism alpha_a : d - > d equal to the morphism alpha_b : d -> d? The answer is not necessarily.

For alpha to be a natural transformation, we must have two components alpha_a : d -> d and alpha_b : d -> d, and three naturality conditions:

alpha_a . (F id_a) = (G id_a) . alpha_a

alpha_b . (F id_b) = (G id_b) . alpha_b

These conditions are satisfied, so long F and G are functors, because F id_a = id_{F a} = id_{G a} = G id_a. The above statements reduce to alpha_a = alpha_a and alpha_b = alpha_b

Then we have the naturality condition for f.

alpha_b . (F f) = (G f) . alpha_a

This is the only condition we have that relates alpha_a and alpha_b, and so long as (F f) and (G f) are not the identity (Note there is nothing saying that it this can't be the case) we don't necessarily have that alpha_a = alpha_b.

Now I will further this examples. Consider the source category, C, for F and G be the same category described above, but let the target category D be Set. This means, to define the functors F and G, as well as alpha, I will need to give a set d, and functions F f, G f, alpha_a, alpha_b from d -> d

- Let F a = F b = G a = G b = d = {1, 2}. That is the set consisting of the integers 1 and 2.

- Let F f be the function {1, 2} -> {1, 2} with (F f)(1) = 2 and (F f)(2) = 1. That is F f, permutes 1 and 2.

- Let G f be the identity function {1, 2} -> {1, 2}

- Let alpha_a be the identity function {1, 2} -> {1, 2}

- Let alpha_b = F f : {1, 2} -> {1, 2}. That is alpha_b (1) = 2 and alpha_b (2) = 1.

(Note we also have F id_a = id_{F a} = F id_b = id_{F b} = G id_a = id_{G a} = G id_b = id_{G b} = id_{1, 2} for F and G to be functors)

The first thing to do is then check that F and G are functors as I have defined them. Identity is satisfied, and composition is satisfied, because we can only compose with identities.

Then we check alpha is indeed a natural transformation. The components are given, so we just need to check the same naturality conditions as above:

alpha_a . (F id_a) = (G id_a) . alpha_a

alpha_b . (F id_b) = (G id_b) . alpha_b

For the other naturality condition alpha_b . (F f) = (G f) . alpha_a observe, based on the above definitions, alpha_b . (F f) = alpha_b . alpha_b and (G f) . alpha_a = id_d . id_d = id_d. Note that since alpha_b is just a simple permutation it is its own inverse. Thus, alpha_b . alpha_b = id_d and naturality is satisfied. Therefore, alpha is a natural transformation between F and G, but alpha_a does not equal alpha_b.

If anyone has any questions, just let me know.

John

---

From: Pl-seminar <pl-seminar-bounces@xxxxxxxxxxx> on behalf of Calvin Smith <cjsmith@xxxxxxxxxxx>
Sent: Sunday, May 5, 2019 9:09:22 PM
To: pl-seminar@xxxxxxxxxxx
Subject: Re: [pl-seminar] Talk on Monday at noon in CS 4310

 

Due to scheduling conflicts, this talk is now at noon on Tuesday the 7th in CS 3310. 

On May 5, 2019 at 8:33:05 PM, Calvin Smith (cjsmith@xxxxxxxxxxx) wrote:

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