Category Theory II 4.1: Representable Functors

[@henrituhola]

I was stuck here. I didn't understand C(a, -) by one sitting. I had to read Awodey's explanation and then think about it hard. Other than that these videos have been helpful. I finally understand things about HoTT, and once I'm finished I can probably combine this with my understanding of linear logic and then apply CT on programming language design.

[@igorsouza9813]

Your classes are always enlightening, thanks. Now, when I have a doubt about some idea, concept or theorem in Category Theory I look if there is some talk about it here.

[@TamasGToth]

Can we think of state as an object in a category, and morphisms as the transitions between states? The transition from the initial state to the final state can be seen as an enormous morphism, a composite of all morphism in the transformation chain? From a programmer view is this morphism just a pure function?

[@nilp0inter2]

I really enjoy these classes but I find this one particularly confusing. Can somebody explain to me, looking at the board at the minute 38:00. Why the functor C(a, -) contains an "a"?? Where is the "a" come from?

[@japper12321]

a in an object of some fixed category C. Basically, all the thing about representable functors is C(a, -) ~= F for some a from C, that is, you can get isomorphic functor to F if you have the object C to reassemble it using hom-functor. The representation of the functor F is encoded in the hom-functor C(a, -) and vice-versa.

[@henrituhola]

'a' is described by context. Usually means it's some specific object in C, or all of them. C(a, -) defines a functor from category C to sets category. Eg. You give it object, C(a, b), you get a set of arrows between a and b. It's a functor though, which means that you can give it arrow, C(a, f), f : b -> c, and it gives a function C(a, b) -> C(a, c).

[@rowanmorrison7645]

But what if we had not a stream with Integers as keys, but a stream with Ints as keys. Then we would have an infinite data structure with elements 2^32 onwards inaccessible to us. Does it still count? Now our transformation is not surjective, so it can't be natural.

[@meganbindra4095]

Thank you for these videos! They've been incredibly helpful. Is there any way we could get closed captions on your Category Theory II videos like you had in Category Theory I?

[@nbrader]

Brilliant series. -Just a minor correction: At --21:10-- I think you intended to say that "f is mapped to u after f" rather than "u is mapped to u after f".-

[@DrBartosz]

Maybe I wasn't clear enough, but if f::y->x then u::x->a is mapped to u'::y->a and u'=u.f (u after f).

[@nbrader]

So if I'm following, you were giving the way the functor maps morphisms, mapping f::Y->X to C(f,a)::C(X,a)->C(Y,a). To do this you constructed C(Y,a) elementwise from C(X,a) (where u is from C(X,a)) using f. Thank you for replying and promptly too!

[@nbrader]

I edited my reply because I put f::X->Y which is the wrong way around because this is a contravariant functor.

[@eastquack3342]

@18:27 so, C(a,f) is notation? It does not mean something nonsensical like the hom-set of morphisms from a (an object) to f (a morphism), right?

[@DrBartosz]

Correct! In category theory it's common to overload notation. If something doesn't make sense, then it must mean something else.

[@huylongpham8748]

Hello, I'm from Vietnam, I've finished watching playlist 1 of category theory, in playlist 2 there are some videos without subtitles, please add them. Thanks you so much !!!

[@bodesephiroth]

Thank you so much for these videos! There is something I found confusing with the examples at the end in Haskell. For example with List. The list functor is an endofunctor in the Hask category of types. Therefore it is not a functor from Hask to Set and cannot be representable. Thinking more about it though, I think there must be a hidden slight abuse that explains the example if one remembers that types are actually sets (a given type is a handle on the set of all its values). With that in mind, we can reframe the List functor as a functor from Hask to Set. For each type t in Hask, the corresponding set would be the set of all possible lists with elements of type t. The same would go for Stream. Saying that Stream is representable and represented by Int then means that a Stream of elements of type t is equivalent to being given functions from integers to elements of type t, which means a guven Stream is equivalent to being able to index any element in the stream with integers. Seems to makes sense!

[@DrBartosz]

Yes, there is a bit of cheating involved. The full story is based on the fact that we are dealing with a category enriched over itself. So hom-sets are really objects.

[@bodesephiroth]

@@DrBartosz Thank you for your quick reply!

[@derelbenkoenig]

So, for an object a in C, C(a, -) is called the hom-functor of a? Is there a similar name for C(-, a)? The co-hom functor, or something?

[@stevemao1368]

Why not using function types (or maybe something like category of morphisms) to introduce hom functors?

[@kinbolluck476]

THIS IS MAKING ME WANT TO LIFT MORPHISMS SOOO BAAAD RIGHT NOE

[@Intrebute]

I'm still trying to grok the basics of category theory, so I'm still trying to build the most basic of intuitions, but one picture that I really like when trying to imagine what natural transformations do, is very similar to what you explained in the beginning of this video. I just wanted to write it down here and see if it makes any sense. Think of the category, for imagination's sake, as a big blob, that's just full of objects and morphisms. A functor basically takes the source category and stuffs it into the target category. In a way, if you think of the source category as beads connected with string, and the target category as holes connected with grooves, a functor is just a way of fitting the net of beads and strings into the holes and grooves. So if you have two functors doing that, a natural transformation is essentially some system of grooves along the already mapped holes that essentially let you take the source category, stuff it into wherever the first functor tells you to, and then _sliding_ that net through the target category, so it reaches the holes and grooves of the second functor. Basically, it's a secret map of the inside of the target category that lets you _nicely_ and _all at once_ slide the category through the inside of the other. The "nicely" part being the actual naturality conditions. Does this seem to play nice with what a natural transformation actually is?

[@EvanZamir]

I just wish there was more consistency in using the terms morphisms, arrows, maps, and functions. They seem interchangeable. Maybe they are, but it adds to my confusion.

[@Intrebute]

As far as I can tell they are interchangeable, at least the first three. I know that they don't necessarily have to be functions, so I'm guessing when someone says functions they're just being more specific. I like "morphism", since it sounds more mathy and seems to be used when talking more abstractly about categories in general. "Map" always seemed to me like "specifics depend on context, but always is functions that preserve some structure". So like, functions with specific properties. That meaning seems nice because then you can say that "Functors are maps from a category to another", and it still fits :D Arrows feels like it went too far trying to go in the direction of "Okay when talking in the most abstract, let's just call them arrows since they can be _anything_" direction. Besides, I like using the word arrow for actual picture arrows, and it'd be confusing to both mean something informal like doodles and also try to mean something formal like the morphism part of a category at the same time D: okay now I'm just rambling

[@ShimshonDI]

I also think of a functor as a *collection* of maps, but maybe a map can map many things at once.

[@TheSidyoshi]

Is it always possible to find a homfunctor or an opposite homfunctor in a category?

[@meddelhed]

I haven't watched this entire series, but I'm guessing that he only uses small or locally small categories, so the answer to your question is *yes*. The general, correct answer is: No, only if the category is locally small. "Locally small" means that the morphisms between any two objects actually form a set, not a class.

[@agustinmazzei5529]

cuando charly te da una clase sobre teoría de la categoria:

[@timh.6872]

Maybe I've been writing too much c++ recently, but that definition of tabulate bothers me from a performance standpoint. Maybe haskell is smart enough to collapse n compositions of (+) 1 into a single (+) n, but I'd rather define it as so: tabulate f = tab_nth 0 f where tab_nth n f = Cons (f n) (tab_nth n+1 f) Yay for where clauses, tail allocation, and tail recursion. Of course, I'm working on a fully-dual type theory where infinite codata (like Stream) is defined by its projections instead of its constructors and must be constructed by considering all projections, so I'd have something more like: data Natural = Zero | S Natural codata Stream x = Head x, Tail Stream x instance Stream of Representable type Rep Stream = Natural tabulate f = tab_nth Zero f where Head tab_nth n f = f n Tail tab_nth n f = tab_nth (S n) f index Zero s = Head s index (S n) s = index n (Tail s) Notice how I can freely use (or ignore) the constructors of Natural in the definition of tabulate, but must handle each projection case because I'm constructing codata. Conversely, I can freely use the the projectors of stream to break apart s in the definition of index, but I have to handle each case of Natural's construction because I am projecting data. I'm still not super happy about having to write tabulate with a helper function, but that's the constraint given by Representable. A more concise definition would just take the anamorpism of f, Zero, and S, but that doesn't show off the syntactic duality of tab_nth and index.

[@martinhandley5095]

'Cons (f n) (tab_nth (n+1) f)' is not tail recursive because 'Cons' is the last function call (not 'tab_nth'). A similar case is 'n * fac (n − 1)', which is also not tail recursive for the same reason. In addition, your definition of 'tab_nth' does not force 'n' so Haskell will not evaluate it. Your nth call to 'tab_nth' will be 'Cons (f (0 + 1 + 1 ...)) (tab_nth (0 + 1 + 1 ... + 1) f) '. Bartosz' version will be 'Cons ((f . (+1) . (+1) ...) 0) (tabulate (f . (+1) . (+1) ... . (+1)))'. It isn't clear to me whether GHC will inline '(.)' in this instance. If it does, then your functions are equivalent. If not, then your version is marginally faster, but not because of tail recursion/allocation. In general, I think it is important to distinguish between finite and infinite data, and copatterns are a great way to do this (as you've shown). However, because languages like Haskell do not distinguish between data and codata, and it's possible to talk about representable functors without needing to fixate on that distinction, I think Bartosz' description is clearer in this instance.

[@jmgimeno]

When you say integer you mean natural, aren't you?

[@valvarexart]

I haven't watched the video yet but integers include negative integers, while natural numbers do not.

[@jmgimeno]

What I mean is that the index type for a Stream should be a natural number because Streams grow "to the future". If the index can be an Integer, we can ask for past values of the Stream.

[@BartoszMilewski]

Yes. Also, when I say "function" I often mean morphism. Years of programming will do that to you :-)

[@quant-trader-010]

I had the same question. Thank you for asking it.

[@marcusklaas4088]

🔥🔥🔥