Despite dozens of "introductory" sources online (websites, video, pdfs, etc), this is the *first* source I've come across which introduces this topic with the assumption that the audience has no prior exposure to category theory OR its jargon. Introducing the jargon of a field of study without circularly relying on the field's jargon is a skill. Thank you for recording this lecture and making it available.
defintions: 8:50 Category /class , e.g. 14:30 9:28 morphism / arrow / primitive - has beginning+end 10:05 Object / primitive / point - identifies ends of arrows 11:05 15:15 graph .. 16:00 specificity of elements even self-refrerential 16:40 Composition - .. 17:20 g after f 18:15 composable "end of one is beginning of other" 20:39 Identity - for every object in a category is an identity -- loop back to self -- law 22:00 id b after f=f 23:10 left identity and right identity 23:50 associatitivty third law - axiom of category 26:00 isomorphism - associativity 28:30 small category 43:00 Identity Function morphism to "end of the road"
Coming back watching these again it's interesting how I originally had problems understanding how there could be more than one morphism between two objects but I never questioned how there could be more than one object. Anyway, I got a job with Haskell that I never would've gotten if it weren't for this series. I'm extremely happy at work now.
congratulations!!! one of my goals is to have a career in functional programming (with haskell), hopefully one day I can reach it. sadly, not that many workplaces here in lithuania offer the opportunity to work using haskell
I listened this lecture many times and what he is saying has an inherent depth I could not uncover for the first time. I highly recommend listening this fantastic course in a recurrent way...
So running through this again to refresh. This course changed who I am the first time I watched it. If you wonder whether this is worth it. It really is. I equate learning this to learning programming itself in value. Thanks again Bartosz
Love this man. He makes the subject a soothing and playful experiance with his relaxed hippy style. The occasional detour into philosophy makes you forget the dryness of the theory
now that is what I call an excellent lecturer and mentor!!! hip hip hurray!!! good use of my beer and coffee!! a super lecturer, how can a person become such a good lecturer! this is amazing!
4:30 definition of category 6:36 barber's paradox(Russell's paradox) 13:25 language constrains us 14:58 category is like a graph 15:54 "how is it possible that you can have more than one arrow? Aren't they all the same?" / "no, they are different ... you just give them different names" 18:18 definition of 'composable' 27:40 meaning of "two compositions are isomorphic" 33:19 bottom value for infinite loop 35:20 definition of types in programming 37:45 using category theory as a abstract and simplified(high-level) model for understanding programming language
Před 3 lety+3
I loved when he said: "(...) and this is associativity, right? Normal thing!" I'm burning my brain the hell out to understand at least something from it but clearly I'm not that smart enough - but to him it's a normal thing 😂 I can also relate a lot with the part "my brain would just give up" - mine did already and I'm watching I for the 6th time because I'm stubborn as hell 😂😂
Really thanks for your brilliant teaching. As a fresh PhD student in SE who wants to go into PL field, this is a really inspiring series to let me get familiar with tough PL related concepts and math.
thank you very mutch, you showed how math can be easy... I'm one of those programmers who are not very familiarized with math and you make this look really digestible. you're awesome.
The diagram he draws to explain associativity of arrow composition is amazing. I wish I had seen it when I was taking my earlier math courses, it makes a rather abstract/complex concept visually obvious.
problem at 28:50. the aggregate of morphisms from object A to object B forms a class indeed, but not necessarily forms a set. a class is a "bigger" collection than set. if the morphisms constitute sets as well, then it's called "locally small". this has been implied in the setup of the definition of category itself.
10:19 I over-extrapolated the word "atomic" and thereby reached an impasse when the category-based definition of epimorphism was introduced in the next video. According to Steve Awodey's text, in category theory objects are the domains and codomains of functions. This definition provided the breathing-space I needed to understand the utility of defining 'epimorphism' and (more importantly) to grasp the possibility of a function being non-epimprphic. For if the objects were atomic in a sense beyond being a catagory-theory-language primitive then the question of whether or not the 'b' produced by the function (f : a -> b) is somehow different than the one used to define the function (g : b -> c) becomes vapid. B is b is b is b. On the other hand, calling it the codomain of f and calling it the domain of g allows one to entertain the possibility gradatio. Please understand that I greatly appreciate this series. As you can tell, I'm literally paying attention to and trying to understand every syllable. My passion is to write world-class computer code and I'm very optimistic that your teachings will help me greatly in that endeavor. Thanks for taking the time to share what you know with the world.
I'm also a student so my opinion has no authority more than yours, but I wonder if you are confusing the elements of a set with the objects of a category. Every object of the category of sets is an *entire set;* it is simple to find functions (morphisms of this category) mapping between the same two sets (objects if this category) that are very different. The definition of epimorphism equates *morphisms,* not *objects.* (not the target or result of a morphism.) Also it seems very important to me that morphisms are not functions (except in some specific categories). For example the dual of SET has the same set objects but obviously can't use functions as the morphisms. I wish you luck in your quest of self-improvement! Even though we have slightly different goals, I'm struggling to improve too!
Thank you for these great videos! Trivial question: Let's suppose I have a category with one single element. I must draw the identity morphism. But I am forced to draw all the composition morphism (if any), so I have to draw the (id º id) morphism. And I could keep exponentially adding infinite morphisms... The question is: Are these redundant morphism implicit in my draws?
Notice that id is identity, so composed with any other morhpism it will produce that same morphism. id º f = f. In this case, the other morphism is id, so you get back id. id º id = id.
Here are some notes: drive.google.com/file/d/0B0pnKqoCaQxdVjBYNUJfOG81Z0U/view I think in the associativity diagram has the names of the morphisms swapped, so I changed them. I could very well be wrong about that.
"Objects have no properties": I would rephrase this slightly. There's (only) one thing you can do with objects: check if two of them are the same (I.e., equal). One might say that equality is the intrinsic property of objects. ("Intrinsic" because whether two objects are equal is determined by the objects themselves, and has nothing to do with external things, like the arrows attached to them.)
(@ 20:00 aprox) Re Composition Tables: In 2 dimensions (like the multiplication table), if the objects are points on a number line, (rather than integers) you would have 2** Aleph Null arrows, correct? For a 3D structure, you would have 2**2** Aleph Null arrows, no? Etc... Is this permitted or defined in Category Theory (BTW, *THANKS* for the series!).
What do you mean by "Schizophrenic view of a category"? That you always have to differentiate between categories as abstractions and the models where they came from?
Hi Bartosz! A quick question regarding identity function. As I understood, in Category Theory every object MUST have an identity morphism. What about Set category where we can have an empty set (let's call it Void like we do in Haskell). No morphisms is draw from and to Void as it has no values. So how can an identity morphism exist where there are no elements? Am I just overthinking it and it is simple { } -> { }, but there exist no implementation in Haskell for this case? Thanks in advance!
Actually, id x = x works for Void, in the sense that, if you call me with an element of Void (which you will never do) I'll return it back to you. Even stranger, absurd::Void->a works based on the same premise. You'll never call it, so who cares how it's implemented.
So basic id function theoretically works for every element of Void type (which has no elements) which concludes that Void type itself has identity morphisms 🤔 Thanks a lot for quick explanation!
If a morphism is defined by which two objects they connect and contain no inner structure, how could there be more than a single arrow between two objects?
This is an interesting question that a lot of people are asking. We are so used to identifying things by their internal structure. In category theory things don't have internal structure. Their identity is defined by the way they interact with other things. In this case, a particular morphism is not only defined by its endpoints, but also by how it composes with all the morphisms around it. Tell me how you compose and I'll tell you who you are.
Milligram reminds me of some of the QFT lectures. That the “morphisms” are more-so excitations in a field connecting one object to another, than discrete mappings. Very interesting question.
I'm by no means an expert in the area (not even an apprentice, actually), but here's how I see it. Imagine one object is the set of Natural numbers and another object is the set of Booleans. There are infinitely many ways (or functions, or mappings, or morphism) to go from natural numbers to true/false values: isPair, isOdd, isOne, isTwo, isThree, isLessThanTen, .... All these are arrows between the two objects.
@@DavidAguileraMoncusi It's funny to me because the reasoning that led me to be confused about the arrows DID NOT lead me to be confused about there being multiple objects in a category - I mean how are the objects distinguished? haha When I realised that my brain unconsciously just distinguished the objects by their positions in the graph I realised the same applies for the arrows; just draw several arrows between two objects, boom done lol
So could there be two arrows from a to b in a (locally small) category that compose the same way with all other arrows, and yet are not the same(equal). I think so. So knowing how an arrow composes is not enough to tell what it is.
So, It's interesting, each area of mathematics tends to have a visual-spatial base using metaphor (in this case the objects and the morphisms) and a verbal part on top of that (the formulae and expressions etc).
Can you have an object in a category that is also a morphism between two other objects?. For example, there are objects a,b,c and d. Also, there is a morphism "f" between a and b. It is possible for b to act as a morphism between c and d?
Really nice. Your presentation takes away from me some basic doubts about Category Theory. I've come from a philosophy máster degree about group theoretical foundations for relativity theory and i'm thinking about look the subject from the more abstract point of view of categories, and making a PhD on that.
Thank's for you lessons! I have some questions: 1. Can we have category where there are elements without morhpism (has only id's). I mean, for example we have a, b, c objects f::a - > b, g::b - >c, h::a- > c and we added an object d. Should this object has morphisms to other exists objects? 2. There is somewhere tutorial about how we should build category, more specifically. For instance, we have some objects and try to build category from them. As I realized we should start to looking for morphism beetwen this objects which will be satisfy category's rules? Or no?
What did u mean that a composition is a multiplication table? In the table on the sides do we put the arrows or the end points? What goes in the cells?
I think you are right. In some OOP languages like Java, "this" is basically an invisible function parameter, while in others like Python "self" is explicitly passed. So if you think in Java: "this" is basically a way to access the implicit parameter for each type in the same way. When you make the implicit parameter explicit in "this" then "this" will start looking like the identity function.
In ZF(C) set theory, the axiom of foundation prevents a set from being a member of itself. Ostensibly one could remove that axiom, and "in practice" it's fine...but ostensibly we could run into exotic and strange sets. (Edit: darg, I see others have commented the very thing! My apologies for re-hashing the same, old, tired remarks. Next time I'll say something more exciting...)
In the set category, I understood that the objects are sets and the morphisms are functions. Now take, e.g., the set of integers and a function f(x) = x * -1. Is f an identity morphism then? The source and the target of this morphism is the same set, so it should be. Or am I misunderstanding something?
No, there are many morphisms from Int to Int, but only one of them is the identity. Try composing your morphism with something else and you'll see that it's not an identity.
Thanks for the reply! I actually didn't fully get the definition of the identity morphism before. So it is defined in terms of composition. I.e. if f(x) = x * -1 would an identity morphism on the set of integers (Int), for every function g : Int → Int, f ∘ g = g = g ∘ f would have to be true. It is trivial to find a function g such that this does not hold for my proposal of f. Can there be two identity morphisms of the same object inside a category that are not the same? Thanks a lot for putting these lectures on the internet!
What is the definition of equality for arrows? I.e. if we say h . (g . f) is equal to (h . g) . f, what do we mean? Do both labels describe the same arrow? Or do both labels describe "an arrow" that is not nessicarely the same arrow, but both starting and ending at the same points? Edit: just saw a similar question, answered "On no, there maybe many (even infinitely many) morphisms between two endpoints -- in fact they form a set. So two morphisms are equal if they are the same element of this set." So then in this case, it would be my "two labels describing the same arrow" case, right? But then how do left and right identity work? How can g . id = g, if one is the composition of two arrows, and the other only a part of it? Or is this just part of our definition? I.e. composition only "creates" a new arrow if neither of them are the identity? Because otherwise, if g = a -> b, we would "create" a new arrow for g . id_a, such that g . id_a = a -> b. But then why are these the same arrow? How are they not two arrows that have common begin- and endpoints?
sounds like category theory lifts the details of objects into the relationship between objects. the relationship is called a morphism. in defining the morphism the properties of the objects are implicitly defined. so, although Bartosz says we don't care about the details, invariably we do because they appear in the relationship between objects. Is this an appropriate characterisation?
Does the associativity (h.g).f=h.(g.f) stem from having composition and right & left Id? or can there be something that is not a category because it doesn't have associativity though it has composition and right & left id?
You can easily construct a counterexample. Define a category with four objects, four identity arrows, and arrows f g h, h.g, g.f as in the associativity diagram. Make the arrow (h.g).f different from h.(g.f).
Bartosz Milewski but it would not be a category right, if there is no associativity? Also if associativity is not derivative of compositionality than how can we tell we have it in the category of types and functions? Frankly I don't even understand what the parenthesize means if function application must be from right to left. Thank you for carrying enough to share your knowledge and understanding. Be warned that I might keep asking until I'll understand it or until you'll get tired from answering, so feel free to answer only if you think this issues may confuse others as well.
Correct, it wouldn't be a category, even though composition and identity are well defined. As for function composition: you can define a function c = h . g. You can compose this function after f. You get c . f. You can also define a function d = g . f. You can compose this function before h. You get h . d. It turns out these two are equal: c . f = h . d. That proves associativity.
Bartosz Milewski if I understand correctly you relay on compositionality for associativity to hold and I fail to see how c. f = h. d would not always hold as long as you are guaranteed to have compositionality and you said that you can have compositionality and not have associativity.
In your category theory video 1.2 you define a left identity on an arrow f that has a as the source and b as the target. You say that id b after f equals f. If the range of f does not cover the full codomain, Id b must select from the codomain to arrive at the range of f. Is this what you intend, or does the left identity only work when the range covers the codomain? (I asked this question before in a wrong spot of your blog. Might you please answer? I am trying to get beyond basic questions like this). Thanks regardless
I'm not sure I understand the question (whose range, whose codomain?). You are apparently thinking of the category of sets and functions. The identity works for any function from a to b.
Bartosz Milewski I am referring to 21:40 or so in video 1.2 when you say “If I compose Idb with f, I get back f.” You called this the left identity when there’s a function, morphism, f with source object a and target object b. Therefore the codomain of f is in b. What happens if the range of f is smaller than the codomain? In order for left identity to work, when we, as you say “compose Idb with f” we must skip somehow the parts of the codomain not in b. Am I correct in thinking that this is what f is doing for us? This seems much different than the right identity, for a morphism g from a to b, where the right identity is expressed as g after Ida, and we simply apply g to every element in the domain a of g. In the left identity, it seems we must be ready to skip parts of the codomain should the morphism not reach them, whereas in the right identity no parts of the domain are ever skipped. Trying to avoid confusion here. Thanks for your great lectures.
Bartosz Milewski, sorry, I reread my question and spotted an error, which I will now fix: I am referring to 21:40 or so in video 1.2 when you say “If I compose Idb with f, I get back f.” You called this the left identity when there’s a function, morphism, f with source object a and target object b. Therefore the codomain of f is in b. What happens if the range of f is smaller than the codomain? In order for left identity to work, when we, as you say “compose Idb with f” we must skip somehow the parts of the codomain not in THE RANGE OF f. Am I correct in thinking that this is what f is doing for us? This seems much different than the right identity, for a morphism g from a to b, where the right identity is expressed as g after Ida, and we simply apply g to every element in the domain a of g. In the left identity, it seems we must be ready to skip parts of the codomain should the morphism not reach them, whereas in the right identity no parts of the domain are ever skipped. Trying to avoid confusion here. Thanks for your great lectures. Is there an assumption that f is a bijection?
Abstraction, composition, identity. Not abstraction, but finding similarities and differences. And by focusing on the similarities, you abstract away the differences. This gives you a category. As for identity... 1-11/∞ ? Perhaps you will say something equivalent. 1-1=1/∞=0. But a cube placed outside the ball is 0 cubes in the ball. And a cube inscribed in a ball, which (the cube) was divided into ∞, along one of the axes. This is the size of a part of the cube. And in our case, a square plane. Which was not moved anywhere, as well as the steel parts. Therefore, 0 obtained by subtraction and 0 obtained by division are different zeros. But at the level of symbolic abstraction - "0", they do not differ.
Just this sentence "forget structure", counter intuitive proposition, we are going to describe a thing by less than analogy with a toolset of only a few properties describing relation and similarity. I need to think 🤔 and imagine.
Interesting that it begins with "Abstraction, Composition & Identity" I know another series of 20 videos (called SICP) that starts with "Primitives, abstraction & composition" seems to be a connection somehow.
Categories: Differences, exclusion, interfaces, boundaries, limits, parameters = Duality. Points are dual to lines, the principle of duality. Sets within sets within sets within sets = scale invariance Scale invariance is the same or equal for all observers = objective democracy, a target or goal, teleology. The laws of physics are independent of the observer's perspective, they are therefore objective and the same and equal for all observers hence they are conforming to a principle of objective democracy.
Is that really true? I honestly don't know, but have heard that Category Theory could be a substitute foundation for mathematics, such that sets are constructed in terms of categories rather than the other way around.
On no, there maybe many (even infinitely many) morphisms between two endpoints -- in fact they form a set. So two morphisms are equal if they are the same element of this set.
Ok. So it is a necessary but not sufficient condition that the two endpoints be the same, correct? So, if someone hands me two morphisms, and without knowing anything about how they came to be, how do I test to see if they are in fact equal? I can't simply apply them to the same object A and see if I end up at the same object B. It would seem I need something stronger.
It's like saying that somebody gave you an element of a set without specifying which set it belongs to. Can't be done. Also, don't assume that morphisms are always functions. You don't "apply" morphisms to objects.
Ug. Ok. I am a bit confused. I don't want to go further until I get this straight in my head then. How does one determine if two morphisms are equal? Does it equality have to either follow from other facts about the morphisms under discussion + axioms or from diving down into the specific category under discussion. Perhaps I am overthinking this. For example, when you discuss epics, you say that g1 . f = g2 . f => g1 = g2. I guess you are either going to (1) use this as a fact to prove some other point (i.e. "Assume f is an epimorphism" so now you can use g1.f = g2.f => g1=g2 in some fashion) or (2) prove it is true for the category you're talking about.
Great video! was wondering, an identity morphism just maps an object back to itself but apparently, it's not the only morphism that maps back to an object from the same object. Can anyone explain what the other morphisms that map back to the same object do? How are they different from identity? Can they return a different value and how would that be possible?
@@DrBartosz thanks for the reply. So the difference between the identity morphism and the others is that identity just returns itself while the others can contain more or less complex logic that eventually returns an object of the same type?
In the category Set, every permutation is a morphism from an object to itself. When a definition or theorem says two morphisms are equal, they don't just mean the target objects of those morphisms are equal.
If an object has no properties then how can we distinguish between the identity morphism versus other morphisms that point back at the same object? Don’t they all just return the same faceless object?
18:05 So if there is more than one arrow going from `a` to `c` , how do I know which one is the composition? Or are they all? In that case, are they all the same?
This is part of the specification of a particular category. A given category comes with rules for composing its arrows, just like numbers come with a multiplication table. How do you know which number is the product of 2 and 3?
But those are not numbers - those are arrows. We don't know what they represent, only how to compose them, right? They can be anything. (I thought cathegories were all about abstracting the details?) So I see a bunch of arrows from `a` to `c`. How can I know which one of them is the composition? Or are they all? All I see is that they make a shortcut from `a` to `c` without going through `b`.
Exactly! How do you know which number is the sum of 3 and 4? You take 3 apples, add 4 apples, and get 7 apples. So numbers represent apples. Now forget about apples and just remember that 3+4=7. When you construct a particular category you have a model for your objects and arrows. For instance, objects are sets and arrows are functions. You get certain composition laws. Now forget about sets and functions, but keep the composition table. You get the category Set.
Again with those numbers! And this is not the answer to my questions at all. If you don't know, just say you don't know, otherwise we'll both waste our time. I guess I have to ask someone else...
@@bonbonpony Show a little respect. If you were to read Dr Milewski's above comment he said "objects are sets", so you can have a set of integers, "a", and an arrow that takes integers and returns integers, "a"->"a", but these can have different mappings (be different functions), hence you can have more than one arrow because we **do** care that those mappings are different. If we were to abstract any further away than this, and no longer care whether functions have the same effects on their elements, then this would be an oversimplification that disables us from gaining any useful insights about composition.
A function between two sets can be thought of as an arrow, and I think in 1.2 you were warning not to think of the common picture of a function as using a set of arrows between preimage and image. But if one were interested,(which I am),I suppose the original arrow/function could be thought of as a bunch of a union of miniarrows...ordered pairs U(preimage,image) with certain constraints. (Kind of like the arrow is actually a blast from a shotgun and each pellet is a miniarrow/ordered pair. Or even better, a function is a volley of arrows from the tribe, and the volley/function is dignified as the Arrow,the union of all the arrows), anyway I went off track sorry. I want to ask if we can form a category from just a set, or from two sets, with the objects being set elements, with the morphisms being ordered pairs rather than functions, and also adjoin into the set of morphisms some unions of morphisms? Like if we wanted it to have funtions and partial functions but no other relations, one could say no unions of ordered pairs with the same preimage. And possibly be interested if the union of (a,b) and (b,a)={(a,b),(b,a)} were even adjoinable at all without breaking axioms of category theory....Thanks for a wonderful lecture!
@@DrBartosz In that category, the objects are setts and the morphisms are relations, that is, subsets of AxB, where A and B are two objects. Can we have something a bit more "messed up", where objects are sets and morphisms are subsets of the set (AxB U BxA)? One would be then allowing the adjoining of the ordered pair (a,b) with the ordered pair (b,a), for example. I was wondering especially if the associativity would work, because I can't see any way for any of the other axioms to fail. If the objects were set elements instead of sets and the morphisms were ordered pairs, I would in that case be asking which unions of ordered pairs could be morphisms.
My guess is that it's because we are used to a notation where function arguments appear on the right of the function name, as in f(x) or, in Haskell, f x. Composition of g after f, in components, is (g . f)(x) = g(f(x)).
if you have a map from "a" to "a" (call it NOTid_a) and it's not id_a then in what sense isn't it id_a? For example, if f goes from b to a then is it not the case that NOTid_a composed f= f
This amount of care, patience and attention to detail when teaching such a difficult subject is a rare thing.
It doesn't have to be difficult.
GU NB
This guy is an alien in disguise, just great
Despite dozens of "introductory" sources online (websites, video, pdfs, etc), this is the *first* source I've come across which introduces this topic with the assumption that the audience has no prior exposure to category theory OR its jargon. Introducing the jargon of a field of study without circularly relying on the field's jargon is a skill. Thank you for recording this lecture and making it available.
Sa galing ninyo
defintions:
8:50 Category /class , e.g. 14:30
9:28 morphism / arrow / primitive - has beginning+end
10:05 Object / primitive / point - identifies ends of arrows 11:05
15:15 graph ..
16:00 specificity of elements even self-refrerential
16:40 Composition - .. 17:20 g after f
18:15 composable "end of one is beginning of other"
20:39 Identity - for every object in a category is an identity -- loop back to self -- law
22:00 id b after f=f
23:10 left identity and right identity
23:50 associatitivty third law -
axiom of category 26:00 isomorphism - associativity
28:30 small category
43:00 Identity Function morphism to "end of the road"
You da goat!!!
Thanks!!!!!!!!
Thank you for the content list, but please include the answer given to the very good question at 30:00.
Coming back watching these again it's interesting how I originally had problems understanding how there could be more than one morphism between two objects but I never questioned how there could be more than one object. Anyway, I got a job with Haskell that I never would've gotten if it weren't for this series. I'm extremely happy at work now.
Wow. Good on you - and what a good incentive to keep watching these lectures!
congratulations!!! one of my goals is to have a career in functional programming (with haskell), hopefully one day I can reach it. sadly, not that many workplaces here in lithuania offer the opportunity to work using haskell
@@uzferry5524 yeah it's hard but it seems easier to find internationally than other languages.
I listened this lecture many times and what he is saying has an inherent depth I could not uncover for the first time. I highly recommend listening this fantastic course in a recurrent way...
After hearing one of his talks and catching on to this attribute I feel in love immediately...
So running through this again to refresh.
This course changed who I am the first time I watched it.
If you wonder whether this is worth it. It really is. I equate learning this to learning programming itself in value.
Thanks again Bartosz
Love this man. He makes the subject a soothing and playful experiance with his relaxed hippy style. The occasional detour into philosophy makes you forget the dryness of the theory
I liked the quick detour into hunter-gatherer spatial intelligence
and Physics!
By far the most enjoyable lectures I've ever seen.
The rare and truly motivated tutor to see. If you have such a tutor, you also get full of fuel from a feel, nothing is really hard to get through.
I like how, because nobody dares to ask, Bartosz makes up questions himself 😄
Socratic method
I have NEVER seen someone explain Mathematics so well!
"Category Theory is more about epistemology that ontology" (this is when the bio-evolutionary argument clicked for me).
Thanks for explaining CT in such an accessible way. Look forward to your next lecture!
simply awesome. Thank you for this great presentation.
now that is what I call an excellent lecturer and mentor!!! hip hip hurray!!! good use of my beer and coffee!! a super lecturer, how can a person become such a good lecturer! this is amazing!
4:30 definition of category
6:36 barber's paradox(Russell's paradox)
13:25 language constrains us
14:58 category is like a graph
15:54 "how is it possible that you can have more than one arrow? Aren't they all the same?" / "no, they are different ... you just give them different names"
18:18 definition of 'composable'
27:40 meaning of "two compositions are isomorphic"
33:19 bottom value for infinite loop
35:20 definition of types in programming
37:45 using category theory as a abstract and simplified(high-level) model for understanding programming language
I loved when he said: "(...) and this is associativity, right? Normal thing!" I'm burning my brain the hell out to understand at least something from it but clearly I'm not that smart enough - but to him it's a normal thing 😂 I can also relate a lot with the part "my brain would just give up" - mine did already and I'm watching I for the 6th time because I'm stubborn as hell 😂😂
Never give up!
Really thanks for your brilliant teaching. As a fresh PhD student in SE who wants to go into PL field, this is a really inspiring series to let me get familiar with tough PL related concepts and math.
thank you very mutch, you showed how math can be easy... I'm one of those programmers who are not very familiarized with math and you make this look really digestible. you're awesome.
Absolutely brilliant lecturer, so well put!!
The diagram he draws to explain associativity of arrow composition is amazing. I wish I had seen it when I was taking my earlier math courses, it makes a rather abstract/complex concept visually obvious.
Brandon Doyle
These are amazing lectures, and such an interesting subject. I can’t wait to watch more!
In Zermelo-Fraenkel set theory, no set can be an element of itself (easy implication of axiom of regularity).
Exactly. That's how ZF avoids the Russel's paradox. See: en.wikipedia.org/wiki/Russell%27s_paradox
Also known as the Axiom of Foundation
8
made me laugh at roughly around @0:17 "moving towards really more practical - I mean, 'practical' in the sense of mathematical stuff..."
M
making me fall in love with category theory :)
Thank you for educating us all!
problem at 28:50. the aggregate of morphisms from object A to object B forms a class indeed, but not necessarily forms a set. a class is a "bigger" collection than set. if the morphisms constitute sets as well, then it's called "locally small". this has been implied in the setup of the definition of category itself.
I came looking for copper and found gold.
likewise!
Thank you for putting these online!
You're such a great teacher!
I love your manner of teaching
Thanks! Can't stand for the next part of the talk.
Really awesome!
Hi from Brazil. You are a incredible teacher. Your videos are absolute perfects
You're an amazing teacher. Big fan.
What a great teacher!
This is awesome, thanks so much for your work sir!
Thank you for sharing your knowledge!
10:19 I over-extrapolated the word "atomic" and thereby reached an impasse when the category-based definition of epimorphism was introduced in the next video. According to Steve Awodey's text, in category theory objects are the domains and codomains of functions. This definition provided the breathing-space I needed to understand the utility of defining 'epimorphism' and (more importantly) to grasp the possibility of a function being non-epimprphic. For if the objects were atomic in a sense beyond being a catagory-theory-language primitive then the question of whether or not the 'b' produced by the function (f : a -> b) is somehow different than the one used to define the function (g : b -> c) becomes vapid. B is b is b is b. On the other hand, calling it the codomain of f and calling it the domain of g allows one to entertain the possibility gradatio. Please understand that I greatly appreciate this series. As you can tell, I'm literally paying attention to and trying to understand every syllable. My passion is to write world-class computer code and I'm very optimistic that your teachings will help me greatly in that endeavor. Thanks for taking the time to share what you know with the world.
I'm also a student so my opinion has no authority more than yours, but I wonder if you are confusing the elements of a set with the objects of a category. Every object of the category of sets is an *entire set;* it is simple to find functions (morphisms of this category) mapping between the same two sets (objects if this category) that are very different. The definition of epimorphism equates *morphisms,* not *objects.* (not the target or result of a morphism.)
Also it seems very important to me that morphisms are not functions (except in some specific categories). For example the dual of SET has the same set objects but obviously can't use functions as the morphisms.
I wish you luck in your quest of self-improvement! Even though we have slightly different goals, I'm struggling to improve too!
The set of all the things that are not dogs. (that set is not a dog, so it is a member of it self).
While it is a good example, this set violates the regularity axiom of ZFC.
yes, that was the idea, that is an example that allows the Russell paradoxes
How do you know it's not a dog?
@@bonsairobo yetdxow
it can be a dog, all the parts that dog is made out of can be in this set, so this set can be a dog ;)
Thank you for these great videos! Trivial question: Let's suppose I have a category with one single element. I must draw the identity morphism. But I am forced to draw all the composition morphism (if any), so I have to draw the (id º id) morphism. And I could keep exponentially adding infinite morphisms... The question is: Are these redundant morphism implicit in my draws?
Notice that id is identity, so composed with any other morhpism it will produce that same morphism. id º f = f. In this case, the other morphism is id, so you get back id. id º id = id.
+Bartosz Milewski bp
Here are some notes: drive.google.com/file/d/0B0pnKqoCaQxdVjBYNUJfOG81Z0U/view
I think in the associativity diagram has the names of the morphisms swapped, so I changed them. I could very well be wrong about that.
ok, I was wrong and have updated those notes.
thanks
"Objects have no properties": I would rephrase this slightly. There's (only) one thing you can do with objects: check if two of them are the same (I.e., equal). One might say that equality is the intrinsic property of objects. ("Intrinsic" because whether two objects are equal is determined by the objects themselves, and has nothing to do with external things, like the arrows attached to them.)
(@ 20:00 aprox) Re Composition Tables: In 2 dimensions (like the multiplication table), if the objects are points on a number line, (rather than integers) you would have 2** Aleph Null arrows, correct? For a 3D structure, you would have 2**2** Aleph Null arrows, no? Etc... Is this permitted or defined in Category Theory (BTW, *THANKS* for the series!).
What do you mean by "Schizophrenic view of a category"? That you always have to differentiate between categories as abstractions and the models where they came from?
Such a talented lecturer
You're a hero, thank you much :)
Thank you for these lectures ❤
Great teacher.
Enjoyed a lot, thank you!
Hi Bartosz!
A quick question regarding identity function.
As I understood, in Category Theory every object MUST have an identity morphism. What about Set category where we can have an empty set (let's call it Void like we do in Haskell). No morphisms is draw from and to Void as it has no values.
So how can an identity morphism exist where there are no elements? Am I just overthinking it and it is simple { } -> { }, but there exist no implementation in Haskell for this case?
Thanks in advance!
Actually, id x = x works for Void, in the sense that, if you call me with an element of Void (which you will never do) I'll return it back to you. Even stranger, absurd::Void->a works based on the same premise. You'll never call it, so who cares how it's implemented.
So basic id function theoretically works for every element of Void type (which has no elements) which concludes that Void type itself has identity morphisms 🤔
Thanks a lot for quick explanation!
Is it suffices for the identity be a one to one function or is it necessarily an identity function?
If a morphism is defined by which two objects they connect and contain no inner structure, how could there be more than a single arrow between two objects?
This is an interesting question that a lot of people are asking. We are so used to identifying things by their internal structure. In category theory things don't have internal structure. Their identity is defined by the way they interact with other things. In this case, a particular morphism is not only defined by its endpoints, but also by how it composes with all the morphisms around it. Tell me how you compose and I'll tell you who you are.
Milligram reminds me of some of the QFT lectures. That the “morphisms” are more-so excitations in a field connecting one object to another, than discrete mappings. Very interesting question.
I'm by no means an expert in the area (not even an apprentice, actually), but here's how I see it. Imagine one object is the set of Natural numbers and another object is the set of Booleans. There are infinitely many ways (or functions, or mappings, or morphism) to go from natural numbers to true/false values: isPair, isOdd, isOne, isTwo, isThree, isLessThanTen, .... All these are arrows between the two objects.
@@DavidAguileraMoncusi It's funny to me because the reasoning that led me to be confused about the arrows DID NOT lead me to be confused about there being multiple objects in a category - I mean how are the objects distinguished? haha When I realised that my brain unconsciously just distinguished the objects by their positions in the graph I realised the same applies for the arrows; just draw several arrows between two objects, boom done lol
So could there be two arrows from a to b in a (locally small) category that compose the same way with all other arrows, and yet are not the same(equal). I think so. So knowing how an arrow composes is not enough to tell what it is.
So, It's interesting, each area of mathematics tends to have a visual-spatial base using metaphor (in this case the objects and the morphisms) and a verbal part on top of that (the formulae and expressions etc).
Can you have an object in a category that is also a morphism between two other objects?. For example, there are objects a,b,c and d. Also, there is a morphism "f" between a and b. It is possible for b to act as a morphism between c and d?
This is epic, so much thanks!
This is so awesome
this is good stuff my main man Bartosz
Teaching in general form cannot make mind clear,if you give the most finest detail every one can understand
Really nice. Your presentation takes away from me some basic doubts about Category Theory. I've come from a philosophy máster degree about group theoretical foundations for relativity theory and i'm thinking about look the subject from the more abstract point of view of categories, and making a PhD on that.
i appreciate.. im also biganner to this subject. and i think from these lactures we can learn alot. even the comment aection is interesting
Thanks for this
Thank's for you lessons!
I have some questions:
1. Can we have category where there are elements without morhpism (has only id's). I mean, for example we have a, b, c objects f::a - > b, g::b - >c, h::a- > c and we added an object d. Should this object has morphisms to other exists objects?
2. There is somewhere tutorial about how we should build category, more specifically.
For instance, we have some objects and try to build category from them. As I realized we should start to looking for morphism beetwen this objects which will be satisfy category's rules? Or no?
Watch the part 3.1 for answers.
A category whose only morphisms are identity is called a “discrete category”.
Thank's for answers. Will watch further. :)
What did u mean that a composition is a multiplication table? In the table on the sides do we put the arrows or the end points? What goes in the cells?
Arrows. Note that most cells will be undefined, because you can only compose arrows whose endpoints match.
Well deserved applause
Would the 'identity morphism' be somewhat equivalent to the 'this' and 'self' we have in our progamming languages?
I think you are right. In some OOP languages like Java, "this" is basically an invisible function parameter, while in others like Python "self" is explicitly passed.
So if you think in Java: "this" is basically a way to access the implicit parameter for each type in the same way. When you make the implicit parameter explicit in "this" then "this" will start looking like the identity function.
Are infinite morphisms compositions allowed?
Best of CZcams!
In ZF(C) set theory, the axiom of foundation prevents a set from being a member of itself. Ostensibly one could remove that axiom, and "in practice" it's fine...but ostensibly we could run into exotic and strange sets. (Edit: darg, I see others have commented the very thing! My apologies for re-hashing the same, old, tired remarks. Next time I'll say something more exciting...)
thank you! thumbs up!
Can an arrow leave one point and arrive at two different points?
In the set category, I understood that the objects are sets and the morphisms are functions. Now take, e.g., the set of integers and a function f(x) = x * -1. Is f an identity morphism then? The source and the target of this morphism is the same set, so it should be. Or am I misunderstanding something?
No, there are many morphisms from Int to Int, but only one of them is the identity. Try composing your morphism with something else and you'll see that it's not an identity.
Thanks for the reply! I actually didn't fully get the definition of the identity morphism before. So it is defined in terms of composition.
I.e. if f(x) = x * -1 would an identity morphism on the set of integers (Int), for every function g : Int → Int, f ∘ g = g = g ∘ f would have to be true. It is trivial to find a function g such that this does not hold for my proposal of f.
Can there be two identity morphisms of the same object inside a category that are not the same?
Thanks a lot for putting these lectures on the internet!
If there were two, you'd have id1 = id1 . id2 = id2
OMG, I wish I could find this video earlier. Love from china
How is an uncountable composition of functions defined?
What is the definition of equality for arrows? I.e. if we say h . (g . f) is equal to (h . g) . f, what do we mean? Do both labels describe the same arrow? Or do both labels describe "an arrow" that is not nessicarely the same arrow, but both starting and ending at the same points?
Edit: just saw a similar question, answered "On no, there maybe many (even infinitely many) morphisms between two endpoints -- in fact they form a set. So two morphisms are equal if they are the same element of this set." So then in this case, it would be my "two labels describing the same arrow" case, right? But then how do left and right identity work? How can g . id = g, if one is the composition of two arrows, and the other only a part of it? Or is this just part of our definition? I.e. composition only "creates" a new arrow if neither of them are the identity?
Because otherwise, if g = a -> b, we would "create" a new arrow for g . id_a, such that g . id_a = a -> b. But then why are these the same arrow? How are they not two arrows that have common begin- and endpoints?
sounds like category theory lifts the details of objects into the relationship between objects. the relationship is called a morphism. in defining the morphism the properties of the objects are implicitly defined. so, although Bartosz says we don't care about the details, invariably we do because they appear in the relationship between objects. Is this an appropriate characterisation?
Does the associativity (h.g).f=h.(g.f) stem from having composition and right & left Id? or can there be something that is not a category because it doesn't have associativity though it has composition and right & left id?
You can easily construct a counterexample. Define a category with four objects, four identity arrows, and arrows f g h, h.g, g.f as in the associativity diagram. Make the arrow (h.g).f different from h.(g.f).
Bartosz Milewski but it would not be a category right, if there is no associativity? Also if associativity is not derivative of compositionality than how can we tell we have it in the category of types and functions? Frankly I don't even understand what the parenthesize means if function application must be from right to left. Thank you for carrying enough to share your knowledge and understanding. Be warned that I might keep asking until I'll understand it or until you'll get tired from answering, so feel free to answer only if you think this issues may confuse others as well.
Correct, it wouldn't be a category, even though composition and identity are well defined. As for function composition: you can define a function c = h . g. You can compose this function after f. You get c . f. You can also define a function d = g . f. You can compose this function before h. You get h . d. It turns out these two are equal: c . f = h . d. That proves associativity.
Bartosz Milewski if I understand correctly you relay on compositionality for associativity to hold and I fail to see how c. f = h. d would not always hold as long as you are guaranteed to have compositionality and you said that you can have compositionality and not have associativity.
I think your definition of compositionality includes associativity.
It said we don't have to look into structure of objects, but to find which function is Identity function we looked into structure to set
That was just to provide some intuition, but identity is totally defined by its composition with other morphisms.
fascinating
In your category theory video 1.2 you define a left identity on an arrow f that has a as the source and b as the target. You say that id b after f equals f. If the range of f does not cover the full codomain, Id b must select from the codomain to arrive at the range of f. Is this what you intend, or does the left identity only work when the range covers the codomain? (I asked this question before in a wrong spot of your blog. Might you please answer? I am trying to get beyond basic questions like this). Thanks regardless
I'm not sure I understand the question (whose range, whose codomain?). You are apparently thinking of the category of sets and functions. The identity works for any function from a to b.
Bartosz Milewski I am referring to 21:40 or so in video 1.2 when you say “If I compose Idb with f, I get back f.” You called this the left identity when there’s a function, morphism, f with source object a and target object b. Therefore the codomain of f is in b. What happens if the range of f is smaller than the codomain? In order for left identity to work, when we, as you say “compose Idb with f” we must skip somehow the parts of the codomain not in b. Am I correct in thinking that this is what f is doing for us? This seems much different than the right identity, for a morphism g from a to b, where the right identity is expressed as g after Ida, and we simply apply g to every element in the domain a of g. In the left identity, it seems we must be ready to skip parts of the codomain should the morphism not reach them, whereas in the right identity no parts of the domain are ever skipped. Trying to avoid confusion here. Thanks for your great lectures.
Bartosz Milewski, sorry, I reread my question and spotted an error, which I will now fix: I am referring to 21:40 or so in video 1.2 when you say “If I compose Idb with f, I get back f.” You called this the left identity when there’s a function, morphism, f with source object a and target object b. Therefore the codomain of f is in b. What happens if the range of f is smaller than the codomain? In order for left identity to work, when we, as you say “compose Idb with f” we must skip somehow the parts of the codomain not in THE RANGE OF f. Am I correct in thinking that this is what f is doing for us? This seems much different than the right identity, for a morphism g from a to b, where the right identity is expressed as g after Ida, and we simply apply g to every element in the domain a of g. In the left identity, it seems we must be ready to skip parts of the codomain should the morphism not reach them, whereas in the right identity no parts of the domain are ever skipped. Trying to avoid confusion here. Thanks for your great lectures. Is there an assumption that f is a bijection?
Abstraction, composition, identity.
Not abstraction, but finding similarities and differences. And by focusing on the similarities, you abstract away the differences. This gives you a category.
As for identity...
1-11/∞ ?
Perhaps you will say something equivalent.
1-1=1/∞=0.
But a cube placed outside the ball is 0 cubes in the ball.
And a cube inscribed in a ball, which (the cube) was divided into ∞, along one of the axes. This is the size of a part of the cube. And in our case, a square plane. Which was not moved anywhere, as well as the steel parts.
Therefore, 0 obtained by subtraction and 0 obtained by division are different zeros. But at the level of symbolic abstraction - "0", they do not differ.
Which's the next one? Is there a 1.3 or is it 2.1?
It's 2.1, watch it using the playlist. :)
Just this sentence "forget structure", counter intuitive proposition, we are going to describe a thing by less than analogy with a toolset of only a few properties describing relation and similarity. I need to think 🤔 and imagine.
Interesting that it begins with "Abstraction, Composition & Identity" I know another series of 20 videos (called SICP) that starts with "Primitives, abstraction & composition" seems to be a connection somehow.
Categories: Differences, exclusion, interfaces, boundaries, limits, parameters = Duality.
Points are dual to lines, the principle of duality.
Sets within sets within sets within sets = scale invariance
Scale invariance is the same or equal for all observers = objective democracy, a target or goal, teleology.
The laws of physics are independent of the observer's perspective, they are therefore objective and the same and equal for all observers hence they are conforming to a principle of objective democracy.
soo cool :))!!
Just a small correction. In a small category, both the objects and morphisms should be sets.
Is that really true? I honestly don't know, but have heard that Category Theory could be a substitute foundation for mathematics, such that sets are constructed in terms of categories rather than the other way around.
25:33 we're talking about Lisp, right?
What is the ML he keeps referring to?
Dumb question time: when you say two morphisms are "equal", what do you mean? The have the same objects as endpoints?
On no, there maybe many (even infinitely many) morphisms between two endpoints -- in fact they form a set. So two morphisms are equal if they are the same element of this set.
Ok. So it is a necessary but not sufficient condition that the two endpoints be the same, correct? So, if someone hands me two morphisms, and without knowing anything about how they came to be, how do I test to see if they are in fact equal? I can't simply apply them to the same object A and see if I end up at the same object B. It would seem I need something stronger.
It's like saying that somebody gave you an element of a set without specifying which set it belongs to. Can't be done. Also, don't assume that morphisms are always functions. You don't "apply" morphisms to objects.
Ug. Ok. I am a bit confused. I don't want to go further until I get this straight in my head then. How does one determine if two morphisms are equal? Does it equality have to either follow from other facts about the morphisms under discussion + axioms or from diving down into the specific category under discussion. Perhaps I am overthinking this. For example, when you discuss epics, you say that g1 . f = g2 . f => g1 = g2. I guess you are either going to (1) use this as a fact to prove some other point (i.e. "Assume f is an epimorphism" so now you can use g1.f = g2.f => g1=g2 in some fashion) or (2) prove it is true for the category you're talking about.
Yes, that's correct.
Great video! was wondering, an identity morphism just maps an object back to itself but apparently, it's not the only morphism that maps back to an object from the same object. Can anyone explain what the other morphisms that map back to the same object do? How are they different from identity? Can they return a different value and how would that be possible?
In Set, you have identity on Bool, but you also have the function not :: Bool->Bool, which is not identity. Try composing it with some other function.
@@DrBartosz thanks for the reply. So the difference between the identity morphism and the others is that identity just returns itself while the others can contain more or less complex logic that eventually returns an object of the same type?
@@skmuiruri I think so. One example I can think of is the abs function. It's not an identity function, but abs of any positive value is itself.
In the category Set, every permutation is a morphism from an object to itself.
When a definition or theorem says two morphisms are equal, they don't just mean the target objects of those morphisms are equal.
If an object has no properties then how can we distinguish between the identity morphism versus other morphisms that point back at the same object? Don’t they all just return the same faceless object?
18:05 So if there is more than one arrow going from `a` to `c` , how do I know which one is the composition? Or are they all? In that case, are they all the same?
This is part of the specification of a particular category. A given category comes with rules for composing its arrows, just like numbers come with a multiplication table. How do you know which number is the product of 2 and 3?
But those are not numbers - those are arrows. We don't know what they represent, only how to compose them, right? They can be anything. (I thought cathegories were all about abstracting the details?)
So I see a bunch of arrows from `a` to `c`. How can I know which one of them is the composition? Or are they all? All I see is that they make a shortcut from `a` to `c` without going through `b`.
Exactly! How do you know which number is the sum of 3 and 4? You take 3 apples, add 4 apples, and get 7 apples. So numbers represent apples. Now forget about apples and just remember that 3+4=7. When you construct a particular category you have a model for your objects and arrows. For instance, objects are sets and arrows are functions. You get certain composition laws. Now forget about sets and functions, but keep the composition table. You get the category Set.
Again with those numbers!
And this is not the answer to my questions at all.
If you don't know, just say you don't know, otherwise we'll both waste our time.
I guess I have to ask someone else...
@@bonbonpony Show a little respect. If you were to read Dr Milewski's above comment he said "objects are sets", so you can have a set of integers, "a", and an arrow that takes integers and returns integers, "a"->"a", but these can have different mappings (be different functions), hence you can have more than one arrow because we **do** care that those mappings are different. If we were to abstract any further away than this, and no longer care whether functions have the same effects on their elements, then this would be an oversimplification that disables us from gaining any useful insights about composition.
The best.
A function between two sets can be thought of as an arrow, and I think in 1.2 you were warning not to think of the common picture of a function as using a set of arrows between preimage and image. But if one were interested,(which I am),I suppose the original arrow/function could be thought of as a bunch of a union of miniarrows...ordered pairs U(preimage,image) with certain constraints. (Kind of like the arrow is actually a blast from a shotgun and each pellet is a miniarrow/ordered pair. Or even better, a function is a volley of arrows from the tribe, and the volley/function is dignified as the Arrow,the union of all the arrows), anyway I went off track sorry. I want to ask if we can form a category from just a set, or from two sets, with the objects being set elements, with the morphisms being ordered pairs rather than functions, and also adjoin into the set of morphisms some unions of morphisms? Like if we wanted it to have funtions and partial functions but no other relations, one could say no unions of ordered pairs with the same preimage. And possibly be interested if the union of (a,b) and (b,a)={(a,b),(b,a)} were even adjoinable at all without breaking axioms of category theory....Thanks for a wonderful lecture!
There is a category of relations, which are ordered pairs of elements.
@@DrBartosz In that category, the objects are setts and the morphisms are relations, that is, subsets of AxB, where A and B are two objects. Can we have something a bit more "messed up", where objects are sets and morphisms are subsets of the set (AxB U BxA)? One would be then allowing the adjoining of the ordered pair (a,b) with the ordered pair (b,a), for example. I was wondering especially if the associativity would work, because I can't see any way for any of the other axioms to fail. If the objects were set elements instead of sets and the morphisms were ordered pairs, I would in that case be asking which unions of ordered pairs could be morphisms.
I believe this spatial meaning of arrows is purely based on culture and not on anything inherent to us. Just like a floppy icon for saving.
Whats a good example of a set that is a member of itself?
See: math.stackexchange.com/questions/253818/example-of-set-which-contains-itself
great
It looks like the morphisms form a non abelian group under composition.. is it true?
Oops I didn’t reach the end before asking..
When you don't want to call something a set and be committed to Set Theory, don't we usually say "collection" or "family"?
Why is the composition notation backwards?
My guess is that it's because we are used to a notation where function arguments appear on the right of the function name, as in f(x) or, in Haskell, f x. Composition of g after f, in components, is (g . f)(x) = g(f(x)).
this is cool
if you have a map from "a" to "a" (call it NOTid_a) and it's not id_a then in what sense isn't it id_a? For example, if f goes from b to a then is it not the case that NOTid_a composed f= f