Wow this is composition where «Bob Ross» have an arrow to «happy little trees» and where «Bartosz Milewski» have an arrow to «morphisms» you did «Bartosz Milewski» → «Bob Ross» and «happy little trees» → «morphisms» which means to say something like: «Bartosz Milewski» → «Bob Ross» → «happy little trees» → «morphisms» that is exactly compatible with what it is indeed: «Bartosz Milewski» → «morphisms»
1:25 operational semantics 1:51 denominational semantics 2:47 function 3:09 pure function 3:20 partial functions 4:11 purity test - memoizable - idempotent 6:20 what are building blocks of composability ? 7:36 expanding on functions 8:00 category sets 8:30 relation - subset of pairs of [set]elements, a subset of cartesian product. 10:20 cartesian product of pairs 11:40 discriminating functions from relations 12:35 this one is bad for function -- cannot be mapped to relation 13:16 total functions - all elements must be mapped into from set1 into set2 14:00 domain of function - starting set. 14:20 codomain - subset ussually called image of the function 18:07 isomorphism 19:30 elevation from element language to categorical language expressed in terms of composition and identity 23:30 (2) reasons disqualifiying isomporphism a. set f[a,b] -> same element -- not inveritble b. image does not fill whole codomain 26:30 invertable ? counter-image 27:07 "fibration" 27:50 non-isomorphic sets increase entropy 31:09 mathemeticians language divergence " injective function does not collapse things" "monic" or monomorphic 32:32 surjective - covers the whole set b from set a "epic" "epimorphism" if something injective and surjective both they are isomorphic 38:30 define an epimorphism without talking about elements
This is amazing. I have very little experience in set theory aside from the very basics, and also no experience in computer science (I am a beginner in programming) but I was able to understand this lecture clearly. I take that to mean you are very thorough and very good at simplifying/explaining things! I appreciate that you don’t just assume knowledge and instead go over every detail with examples! Thank you for posting this on TH-cam for free. I’m someone who is curious about mathematics but has no time or money to enroll in a course right now, so things like this are truly a blessing.
32:50 A good way to think about injectivity and surjectivity is that for an injective function, each element in the codomain is mapped to by *at most one* element in the domain (i.e. zero or one). For a surjective function, each element in the codomain is mapped to by *at least one* element in the domain. If both of these are true (for a bijection / isomorphism), each element in the codomain must be mapped to by *exactly one* element in the domain, since that is the overlap of those two inequalities. (This also assumes that there are no elements in the domain that do not map to at least one element in the codomain, which is the other condition required by injectivity / "1-to-1 mapping" that is not covered by the statement "each element in the codomain is mapped to by at most one element in the domain".)
Thanks a ton for these, Bartosz. A comment about non-injective functions representing abstraction and non-surjective functions representing model was particularly insightful.
Bartosz - I've been binging on your videos after been a reader of your blog for a couple of months. I've taught Neuroanatomy to medical school students at McGill and Harvard; you are an amazing speaker and thinker. I look forward to your book bringing together Haskell, Category theory and the meaning of life! :-) Merci beaucoup! - E
43:00 so "g1 after f = g2 after f" means that they are the same in the sense that they both end up in the same set? because i cant see how its true otherwise
I took a few days to understand the last part about why Epimorphism make this statement true [G1oF = G2oF -> G1 = G2] . For those who still struggling like me, I hope this explanation can help you. If function is not Epimorphism then f(a) will cover only some part of b. Example: "a" is set of Integer, "b" is set of integer and let f be f(x) = 2x. In this case f(a) will map only from "integer"(a) to "even number"(some part of b).
Thanks! But a doubt: how can you prove some function is an epimorphism in some cathegory? For instance, in the category of types it looks like isEven(int) is an epimorphism because it covers all bools, and xModY is not because it doesn’t covers all integers. But this is only a refference to surjective logic, how can this fact be extracted from cathegory theory?
@@Bflatful The following is my understanding and I am by no means an expert in the field: If you know a category, then that means all objects and arrows are known! I think that is very important to remember, since when this is the case you are able to actually check the definition for an epimorphism. When we are talking about a specific category, e.g. the category of types, then we would use surjective logic since it is easier than arguing over all objects and arrows. Example: Assuming isEven :: Int -> Bool is NOT an epimorphism then that means there exists a type C and two functions g1,g2(:: Bool -> C) s.t. (1) g1°f != g2°f or (2) g1°f = g2°f and g1 != g2 (that's all we can say with category theory). But since we are in the category of types we can say (assuming case (2)): there exists b in Bool and c1 != c2 in C s.t. g1(b) = c1 and g2(b) = c2. It follows from g1°f = g2°f that b is NOT in the image of f, which is a contradiction, since the image of isEven has to contain b. For xModY we would simply state a counter-example to the statement (aka two functions where g1(Y) = c1 and g2(Y) = c2 where c1 != c2 in some appropriate type C). On the other hand, let's say we are in the category with 3 objects a1,a2,a3, and arrows f::a1->a2, h::a1->a3, and g1,g2::a2->a3 (now we also know that g1 != g2, even though we don't know, assuming the arrows were abstracted from "functions", how the arrows look like in terms of arguments!!!; also let all other necessary arrows be defined e.g. id arrows). Now we check if f is an epimorphism: first, we find h = f°g1 = f°g2, but then we actually find that g1 != g2 which means that f is not an epimorphism. If f were an epimorphism then either there would not have existed two different arrows g1 and g2 or there would have been e.g. two different arrows for the compositions h1 != h2 with h1 = f°g1 and h2 = f°g2.
Bartosz, I really enjoy your lectures. It's so good, when people are passionate about what they're doing and talking. Certainly, it holds true for your case. I'm C++, Java, Python engineer learning Haskell and I stopped my Haskell readings for a moment to watch your lectures before, to have better comprehension. Thanks a lot!
10:07 it will never be "symmetric" in that sense unless we're working with homogeneous relations (subsets of X x X), since pairs are ordered - the first element from the left set, and the second element from the right set. And for the same reason, relations *do* have directionality since A x B != B x A.
I had been studying functional programming and was led here by The Algorithms! I have a few days to mess around before I have to get back to studying less abstract stuff, but these are some powerful models of composition and I'm really glad I found these lectures!
2:44 pure function 8:48 definition of relation 10:11 definition of relation, cartesian product 11:32 comparison between relation and function 34:34 if I can't tell about the internals(elements), how can I talk about morphism's properties? (in terms of category theory)
Guys, I've read the comments and it's seems to me the epimorphisms explanation confused some of us. The trick is in 42:56 . Professor Bartosz reverses(negates) what he just explained until that point to show what would be an epimorphisms. I think the reason some of us were confused was due to english not being our first lang or maybe just missing this crucial part of the explanation. Someone to give a second opinion ?
I think you're right, and that it's just confusing to define something by defining its negation. I'm wondering if there are more conditions for epimorphism to indicate surjectivity, though. Here's a comment I left, let me know what you think: It seems that for the definition of epimorphism to indicate surjectivity in the case of SET, there must exist morphisms with domain b other than the identity id_b. Because if this is the only morphism in the whole category with domain b, then f will satisfy the epimorphic condition even if it is not surjective. Are there specific conditions under which epimorphisms are surjective? Or am I misunderstanding something?
Bartosz you just blow my mind. I get a course few years ago on university about abstract algebra's. Was so complex to understand it at that time that I just past it with out understanding anything. But your video about category theory bring a light to me on abstract algebras. Thank you.
21:10 Why is a one to one correspondence between natural numbers and even numbers? I mean natural numbers contain odd numbers so we don't have a correspondence for them in even numbers.
@@DrBartosz , think you very much. So this works only for infinite domains because expression y=2x will always have a solution, where in a finite domain this expression or it's reverse may endup being null? PS: Anyway, the course is awesome. I started watching it few times, but my math knowledge is too low so I'm starting the course over and over again, because every time I get new things, that I wasn't able to listen previous time. I have the fear that I will get to the monads series and I will not understand a lot of staff because I skipped to much on basics.
Wrt. the epimorphism definition, I needed to understand that f is epimorphism _only if_ the following holds: "∀ g1,g2, g1￮f=g2￮f => g1=g2". Not sure if it should be _if and only if_ though. The definition of epimorphism _is not_ just the statement "∀ g1,g2 g1￮f=g2￮f => g1=g2" in itself, which didn't make any sense to me. In the video it is said correctly, but somehow missed it. To show that f is not surjective / epimorphism in the category Set, - Find such g1,g2 that - g1￮f=g2￮f - g1(a)!=g2(a), where a ∈ B, a ∉ Image(f) - Thus it follows that "∀g1,g2 g1￮f=g2￮f => g1=g2" does not hold, and f is not surjective. On the other and, if for all g1,g2 that have g1￮f=g2￮f, you cannot find any value b for which g1(b)!=g2(b), where b ∈ B, b ∉ Image(f), then f is surjective/epimorphic. Makes sense to me, but not 100% confident about this. I think the implication (=>) in "∀g1,g2 g1￮f=g2￮f => g1=g2" means that if composition of g1 with f and composition of g2 with f are not the same, then it does not help in determining whether f is surjective. I wonder what happens if there are no morphisms from B to C. Doesn't that mean that the for all statement holds true, and f is surjective by that definition, while it certainly doesn't have to be if f is chosen not to be?
Hello Bartosz, I'm going through your entire course, I absolutely love it, thank you very much! I'm just struggling a bit with my understanding of epimorphisms connection to surjectivity. (Funnily enough, I seem to understand monomorphisms connection to injectivity better). - == (after, eg. apply g after f == g - f) Is this the correct thinking?: If I take all possible functions g1 and g2 (:: Y --> Z) , if g1 - f is the same as g2 - f, and if this knowledge alone tells me that g1 is equal to g2, then I can be sure that f is an epimorphism. I don't really understand though what it means that g1 == g2, as we specifically define g1 != g2 (you said for the same points they go to different values). Unless we are saying here that g1 == g2 over the domain that the image of `f` is exposing on Y (your diagram at 45:01). -- spends 10 more minutes thing -- Or wait is this the idea: If I take any function g1, g2, if g1 - f is the same as g2 - f, and if this knowledge alone tells me that g1 is equal to g2, then f must be surjective because g1 doesn't have to be equal to g2 in general but in our case they are equal which MUST imply that f is surjective because it must be not mapping to outputs where g1 and g2 would not be equal? So how exactly are defining the equality of g1 and g2, they are clearly different functions, so are we saying equal as in "these functions are the same over the inputs we will give them", which in this case is the image of `f`? I guess I'm struggling in understanding what the statement: "=> g1 = g2" even means. Thanks, hopefully you can help me understand. Great lectures, thanks again so much :D
g1 = g2 means they are equal for all inputs. But if f is not surjective, it can't feed all possible inputs to them. Consider some examples. Like two functions that are the same for all positive numbers but different for negative ones. Compose them after f(x)=x*x (wich is not surjective) and the results will be equal.
Thank you for your fast response Bartosz! So I think I understand this logic, we take *different* functions g1 and g2, if over the outputs of f g1 == g2, then f MUST be surjective because we had different functions that acted the same, we must have been giving them the sub-set of their inputs for which they have the same output. I hope I'm understanding correctly. Follow up question: What if I don't even have 2 functions g1 and g2 which are different? What if all I had in my entire hom-set from Y -> Z was 2 functions, g1 and g2, and they were the same for all inputs. Now it seems that this reasoning would lead me to believe that f was surjective, because for all g1 - f == g2 - f ==> g1 == g2, when indeed f need not be surjective, it simply only has 2 functions g1 and g2 and they are actually equivalent over the their entire domains. So this again leaves me confused, hopefully you see my counter example and can explain why I am saying BS :) Thanks again!
Ok maybe I think I finally got it.... Basically we're saying, if I have 2 functions and I feed them an input, let's say the number 1, and they both produce 5, are they the same function? Well I don't know! When do you know? When you've tested every single input. So, if the fact that 2 functions are the same after feeding them some input (the result of f) implies that they are the same, then f MUST map to everything and hence be surjective. Does that explanation make sense? Sorry for the confusion, thanks again Bartosz
They are only the same function if they are equal on ALL inputs. Suppose I design g1 and g2 in the following way. For all elements in the image of f, I make g1 and g2 map to the same places. This is _not_ enough to say that g1 == g2 in general, because the elements _outside_ Im(f) might still be mapped differently. On the other hand, it _is_ enough to tell you that g1 . f == g2 . f. That's because those two compositions never go "through" any elements outside of Im(f). So we have a situation where g1.f == g2.f but g1 != g2. This situation only happened because we found elements outside of Im(f) where we could make g1 and g2 differ. If there are no such elements, then we can't have this situation: instead, g1.f == g2.f MUST mean that g1 == g2.
I think there is a mistake in the shown "definition" for categorical surjectiveness or epimorphism (might be that I'm too used to a Gries & Schnider's syntax and I'm missing the "if f is surjective then the for-all quantification holds" but correct me if I'm wrong): consider: a={1,3,5}, b={2,4,6,8,10}, c={-2,-4,-6,-8,-10} and functions f :: a->b such as f(x) = 2x g1:: b->c such as g1(x) = -x g2::b->c such as g2(x) = {-x if (x not in ), -4 if (x = 8), -8 if (x = 4)} Now g1.f == g2.f for c but g1 is not the same as g2 and f is obviously not a surjection
f is an epi if _for every_ c, g1, and g2, (if g1.f = ge2.f then g1=g2). I know, the quantifiers are often confusing. You picked some particular g1 and g2, but there are other choices you havent't tried. For instance g1 that maps 4 to -2 and g2 that maps 4 to -10.
so if i understand this correctly: g1 and g2 differ only for elements outside of the image of f, that's the key point here. so if g1.f == g2.f is true for all elements in c (mapped by g1 or g2), then f is epimorphic. that's because this couldn't be true if the image of f wasn't matching all elements in b.
13:10 Isn't it by definition always the case that all elements of set A have a mapping to an element of a subscert of set B. If it didn't it would not be part of set A to begin with right?
Hello, with regards to the definition of epimorphisms: We are basically describing what it means to be surjective but via a composition, right? So is it possible to say, in metaphorical terms that due to the image of f not being equal to the co-domain we cannot see (from the vantage point of f) whether g1 and g2 would actually be different, so they are effectively the same? It's like a non-constructive proof of sorts? Is this a good way to see it, or does it miss the point? Cheers for the vid.
Bartosz in a definiiton of epimorphism you compose f with g1 and g2 whereas codomain of f is not a domain for g1 and g2. How is it possible to compose it?
The codomain of f is b. You are probably thinking of the image of f, which does not cover the whole domain of g1 and g2. Example: f x = x^2. Codomain is Int, image is positive Int. You are free to compose it with a function whose domain is Int, say g x = x+1. You'll get a function h x = x^2+1.
I was a bit confused, but I hope I got it: in the last example with sets a,b and c it was shown that we cannot say that f is surjective (since it isn't) because g1 and g2 are not equal (for example according to the "composition table" of the category). Is this correct?
At around 42:49 you mention that the compositions g1 after f and g2 after f are the same even though the morphisms g1 and g2 are different - they map the same point to two different points. Is there something am missing that explains why they are the same?
Take f x = x^2. The result is always positive. g1 and g2 are the same for positive numbers, but differ for negative. Say g1 x = x and g2 x = abs x (absolute value).
Thanks in advance for your patience, I'll figure this out eventually. So, say you have the morphisms g1 x = x=/2 and g2 x = x * x, even though they start from the same point they obviously end up in different points in the corresponding category. So what does the statement "g1 is equal to g2" mean? Is it sufficient, for both to result in positive integers for it to be said that they are the same?
@@skmuiruri : You have to find g1 and g2 that are equal after you compose them with f. Yours aren't. For instance, take x=2. f x = 4. g1 4 = 2. g2 4 = 16. Try this with my g1 and g2. There is no such x that g1(f x) is not equal to g2(f x).
@@BartoszMilewski f is an epimorphism from a → b if for every other object c in the whole category and for every pair of morphism that goes from b → c if the composition g1 ° f is the same as g2 ° f. It follows then that g1 equals g2. So the underlying premise of this statement is "IF you can find morphisms g1 and g2 that are equal after composing them with f then the above statement holds". Is that the point you're making that I can't seem to grasp?
Something that confuses me, when you have a function that is not surjective, meaning there are elements in the codomain that are not mapped to by any element in the domain, then why do we not say that the function's codomain is just that subset? Is any superset of the image of a function also considered a codomain?
Specifying a codomain is part of the definition of a function. A function that doubles integers produces even numbers only, so its codomain can be specified as the set of even numbers, and then it's surjective. If you specify the codomain as integers, then it's not surjective. These are two different functions. They are related, because you can inject even numbers into integers, so the second function is a composition of the first followed by the injection.
Simply excellent, for a remote student with a minimum resources u just make an enlightenment tower, like a light house ,for a lost direction student in a vast ocean
~ 27:00 Using entropy as a metaphor for the information loss from non-invertible functions is cute. I too, was a physicist in a past life (now doing software and control systems engineering).
Regarding injectivity does this mean if we get a solution vector as the output then the function is injective but if we get a scalar as the output then the function is not injective? Since we aren't converging to zero or one value but potentially many values.
I have a feeling (vector, scalar, converging) that you are currently dealing with machine learning, so I'm going to use some programmer-friendly examples. Remember all along that f is injective if and only if for x₁ ≠ x₂, f(x₁) ≠ f(x₂), which can be stated as "if the inputs are different, the outputs must be different too". Let's try f₁ : uint8 → uint8 × uint8 × uint8, such that x → (x mod 2, x mod 3, x mod 6). You can see very quickly that for x₁ = 0 and x₂ = 12, we have x₁ ≠ x₂ but f₁(0) = f₁(12) = (0, 0, 0). So even though f returns a vector (of length 3), it is not injective. Now let's try f₂ : uint8 × uint8 → uint32, such that (a, b) → a*256 + b. Here I'm doing the opposite, reducing from a vector to a scalar, but in such a way that you cannot find two different inputs that will give you the same output. So the function is injective.
22:30 You can definitely stabelish a bijective function between the sets of natural numbers and even numbers. But you don't work division, but with the operation of doubling. Every number in ℕ has a double in the Even set and every even number has a half in ℕ. the function doubling::ℕ a → E b is the inverse of halving::E b →ℕ a doubling.halving = id in ℕ; halving.doubling = id in E
This is the trick of the function, right? if the function was from N -> N than you cannot invert, but if it's from N -> E, where E is the set of even numbers then you can :)
Thx for this video series, awesome! I think I understand the definition of an epimorphism. But I don't understand what can be said about f if g1 and g2 differ also under the image of f. So this means g1 =! g2 and also g1.f != g2.f. Isn' it true that in this case f can also be a surjective function? That would imply that in this case some surjective functions cannot be determined with the defintion in the video?
Totality is only defined for sets, and here we're talking about morphisms. But the argument is valid for sets, too, in which case g1 is total. It's defined for all argument values.
Bartosz, these lectures are great! I have a question on epimorphisms and surjectivity (44:22). It seems that for the definition of epimorphism to indicate surjectivity in the case of SET, there must exist morphisms with domain b other than the identity id_b. Because if this is the only morphism in the whole category with domain b, then f will satisfy the epimorphic condition even if it is not surjective. Are there specific conditions under which epimorphisms are surjective? Or am I misunderstanding something?
@@BartoszMilewski Thanks for your response. "Epimorphism is surjective in Set" is exactly what I want to verify, though, so I'm considering edge cases. Isn't it the case that when the only morphism with domain b is the identity, the definition of epimorphism is trivially satisifed? Because id_b = id_b, and id_b after f = id_b after f. So f could be any function (surjective or not) from a to b, and Category theory will see it as an epimorphism in this case. Where is my error?
Here's a concise counterexample. Consider the following Category: Objects: A, B Morphisms: all identities, along with f:A->B and the required compositions It follows that f is an epimorphism, for the only morphism with domain B is id_B, and id_B∘f = id_B∘f and id_B = id_B. Now we may instantiate this category with sets and functions. Let: A = 2Z (all even integers) B = {0, 1} f:A->B is such that f(x) = 1 if x is even, f(x) = 0 if x is odd. f is clearly not surjective, but in the category defined above it is classified as epimorphic. The problem is that the category lacks the resources (e.g. other morphisms) with which to sufficiently probe f. So, for epimorphisms to indicate surjective functions in Set, these other morphisms must exist, which to my knowledge has not been stated. What is inaccurate here?
@@BartoszMilewski For anyone with the same confusion as I had: Set refers to THE category of ALL sets and ALL functions. In this category, it is guaranteed that epimorphisms correspond to surjective functions. Other categories with set objects and function morphism may be defined where this is not the case, as in my example
for your example of odd and even numbers and isomorphism, can't it be isomorphic? there are multiple ways to create a one to one correspondence right? i understand natural numbers and reals do not based on infinity theory stuff, but sort of confused about the odd and even one.
I am trying to use ChatGPT to understand but he got confused more than I was: (1:13) _«The statement "There are very few of them, none of the major ones" is incorrect. It is not true that none of the major programming languages have formal operational semantics. In fact, several major programming languages do have formally defined operational semantics or formal specifications that describe their behavior»._
You have to use GPT4 to discuss category theory and you kinda need to know it already, otherwise ChatGPT will lead you to nonsense and will make many mistakes that you will not notice. That said, it can really help clarifying some things indeed.
Is the condition for epimorphism a necessary condition; in that it includes morphisms that are not epimorphisms but all epimorphisms satisfy it? If so is a sufficient condition required?
But isn't it the case that epimorphism follows only if g1 and g2 and any other g differ only outside the image? Or in other words, if any pair of g's differ within the f's image, the definition of epimorphism would break because it would not be considering that pair.
Hi Maybe you talk about it later, but I have to ask now, before I forget: isn't every function surjective if you just define the codomain precisely enough? I mean, it's just for the lack of a strong enough type system in most programming languages, that we define the return type of f(x:Int) -> x*2 as Int. If we could create types with functions (I think Idris is going that way), then we could just say that Even = Int*2, and f :: Int -> Even
@@DrBartosz Why? The compiler could figure out that Even is a sub-type of Int because the operation on it was multiplication with Int, which doesn't lead out of Int. Anyway, it's an implementation detail, I just don't really understand why the codomain for x*2 is necessarily given as Int, by the same accord we could say it's Real, or any type that contains the even numbers, and technically we would be right. But maybe I just look at it from a programming point of view, where arguments of subtypes are automatically cast to the type of a function parameter.
Excuse me. I didn't understand surjection equivalent in categorical therms. After you explained it: which function is surjective? f? g? f.g? f.g1 or f . g2?
Vectors are dual to co-vectors (forms) in General Relativity. Syntropy is dual to increasing entropy Syntropy is the integration or convergence of information into predictions, expectations or priors. Entropy is the differentiation or divergence of information into new states. Integration is dual to differentiation Convergence is dual to divergence Functions have targets or goals, teleology = non-isomorphic, the arrow of time or increasing entropy.
Real-world analogy: Like in a security camera system. An epimorphism is like having cameras that cover every part of a building. Two people claiming to know what happened in the building (like our functions g1 and g2) must agree if they're both telling the truth, because the cameras see everything. A non-epimorphism is like having blind spots in the camera coverage. Two people could give different accounts of what happened in the blind spots while agreeing on everything the cameras saw.
Maybe negating the definition of epimorphism might help some of you: If f is not surjective, then we can always find a pair of functions that map at least one of the elements in B \ Image(f) differently to C. If we cannot find such a pair, f must be surjective.
I love your videos! However, I think that it is not completely clear about one thing, is a category an algebraic structure? Like a generalized group/graph/set thingy? It seems already that it is not completely generalized, i.e. there are many assumptions about objects, existence of morphisms, enumeration, and truth value. I am now wondering if logic systems are static within all categories. Like we can derive all of our usual theorems from axioms using propositional logic, but under a different logic system, the same theorems do not hold. If categories all rely on assumed logic, then a category is essentially another algebraic structure
Maybe it's an obvious question, but long into the course and I still don't get how we can compare morphisms with our "category glasses" still on. Because to define equality we need to see what morphisms exactly do with each element inside of a category. And if they do the same thing, then they are equal. For example we may have three functions Int -> Int: f1 = (+2) f2 = (2+) f3 = (2*) And to say that f1 is equal to f2 (and I'm not sure they are actually equal) we need to compare all elements in a look-up table, which we don't have with our glasses still on. I tried to google it and the first thing I found is that we actually can't compare functions at all. stackoverflow.com/a/4328965 So how exactly does this part of a proof work? g1 . f = g2 . f => g1 = g2
No, it's not an obvious thing, and it's sort of a meta-question. If you're already in a category, morphisms between two objects form a set, so one composition produces an element, another composition produces an element, and they are both from the same set. If they produce the same element, they are equal. But how we construct this category in the first place is a different issue. The sets of morphisms and their composition are extracted from the programming language, and during this extraction we might legitimately ask the question: do these two functions correspond the same morphism? This might be, in general, undecidable within a given language. The operative definition is that two functions are equal if they produce the same output for the same input (extensional equality), but how do you check that?
@@DrBartosz Oh, I see. But everything starts to look sketchy if we want to compare functions by their internal addresses in memory. If we do this then "g1 . f = g2 . f => g1 = g2" still holds just because there is no equal functions-each function has its own address in memory-and we won't be able to pick out these faulty functions from "the universe" of functions, and if we can't do that then each and every function should be surjective. Which is not exactly what we wanted.
Really enjoying this series! A question in the surjectivity proof: At this point I'm not certain that we've explicitly defined arrow equality, have we? How do we define it if we can't look inside the objects? Because we can have many arrows from one object, how do we know that these two are equal?
Depends. Either you have "no idea" what the morphisms are, but you have some table defining the composition for them, or you have know to what your category actually is. In the first case you just look at the table and see what morphisms have this property and thus are epimorphisms. In the second case you can prove it depending on your category. Lets say we talk about the category of all sets and morphisms are functions. For every function, you can show whether it is injective or surjective. Then you can prove that a function is surjective if and only if it is an epimorphism and a function is injective if and only if it is an monomorphism. This gives you a tool to say about any function whether it is a mono- or epimorphism.
Are two morphisms g,h equal (i.e "g = h") if the Image of g and h are the same? Otherwise the definition of the epic morphism makes little sense to me, because I can think of counter examples. For example let f :: A -> B; g1, g2 :: B -> C such that Im(f) = B then f is clearly surjective, but I can find two functions g1, g2 such that Im(g1) = Im(g2) which map elements differently to C. Let A = B = C = {1,2} and g1(1) = 2 and g1(2) = 1 and g2(1) = 1 and g2(2) = 2. then g1 and g2 are different, at least out of the perspective I am used to, but they produce the same Image, namely C.
there is no such thing as the concept of "the image" of a morphism in a category. they just have a codomain, but the codomain is an object and objects are atomic and have no internal structure.
He said ∀g₁, g₂, f∘g₁ = f∘g₂ means that f is an epimorphism, and that epimorphism in Set is a surjective function. But I still can imagine some f∘gₙ ≠ f∘g₂ (which means f is not an epimorpshism), whilst f is a surjective function. So, in Set, though epimophism is a surjective function, but not every surjective function is an epimorphism, right?
Never mind, I was confused by the fact Bartosz pictured an epimorphism not covering its whole codomain. However a surjective function must cover whole codomain, by definition. That relocates my confusion though to a question why he thinks epimorphisms in Set are surjective functions.
You have to be careful when negating such complex statements. f is not surjective if there exist g1 and g2 such that f.g1=f.g2 and g1 is not equal to g2. The negation of implication a=>b is: a and not b.
Thank you! To any who reading these comments: f∘g₁ should've been g₁∘f, but Bartosz in reply somehow figured it. I am so embarrassed, my only justification is a reference to Jeremy-kun who said that mathematicians are chronically lost and confused, that's their natural state of being¹ 😛 I do have questions, but I think I should rewatch the video before writing them down. 1: j2kun.svbtle.com/mathematicians-are-chronically-lost-and-confused
Thank you so much. I have been struggling with epimorphisms for some time now. And only after watching above I realised that if g1 ∘ f = g2 ∘ f is true then g1 = g2 must be verified to be true as well. I fell into the trap thinking if A then we can conclude B. The correct statement is if the implication is true then f is an epi (and surjective under set).
Thank you for this lesson, what about "random" function which returns random numbers, I think it maps one value from the first set to many values on the other set?
"Random" is not a function from strict classical mathematical point of view. Traditional approach for randomness in mathematics is via Lebesgue-Rokhlin probability space that effectively models randomness via hidden variables.
First of all, thanks for these great lectures! :) One question remains though. Am I right when saying that: We model a function as a subset of the morphisms of a category?
Really nice to have a good and very passionated lesson on categories ... Gonna eat the whole in one night hehe Just wondering : Why isn't it enough to define epimorphisms like this : f beetween objects a and b is epic if for every morphism g1, g2 from b to b, g1 after f = g2 after f implies g1=g2 ? Why do you need to check this property for all objects c ? If you're able, via f, to completely determine any permutations on elements of g, it seems epimorphic-enough (for the set theory intuition at least ..) Also would have the feeling that if g is an epimorphism from b to b and that for all epimorphism h from b to b we can simplify via the property with f, then f is an epimorphism ?
he doesn't, the thing with category theory is that we can define the whole thing without using the elements (it's just helpful to visualize the elements because most of the students will be familiar with university Analysis aka ZF set theory) and make use of other morphisms to describe something "equivalent" to surjectiveness.
Oh, I misunderstood your question. We need to map g1 and g2 from B to C because they are functions. I don't think the "For all C" is necessary, because looking at epimorphisms on Wikipedia, it does without it. de.wikipedia.org/wiki/Epimorphismus
Now this probably isn't a perfect substitute for a proper book but Bartosz Milewski also has a blog on which he goes through similar material (along with other things). Check it out if you like: bartoszmilewski.com/2014/10/28/category-theory-for-programmers-the-preface/
28:00 A little point on entropy - pure functions can only decrease entropy. Entropy is related to the number of ways a system could be in, and a function can only decrease this. Applied to computer science, a hash function should be hard to inverse, but if you do too many non-invertible operations, you reduce the size of the image.
As with every analogy, it only goes so far. My analogy is that a process that increases entropy is irreversible. A computer that evaluated a lossy function lost some information and dissipated some heat. A function took a piece of paper with some numbers and burnt it to ashes.
Regarding the subjective argument, this is how I made myself understand it: Given : If f is not subjective -> (There exists some g1, g2 such that, g1 /= g2 and g1.f = g2.f ) This is of form p -> q thus, ~q -> ~p is also true. Hence above statement can be written as: ~ (There exists some g1, g2 such that, g1 /= g2 and g1.f = g2.f ) -> ~ (f is not subjective) => (For all g1,g2 such that, g1.f /= g2.f or g1 = g2) -> f is subjective Further (g1.f /= g2.f or g1 = g2) is of form ~p or q which can be written as p -> q Hence final statement becomes => (For all g1,g2 such that, g1.f = g2.f -> g1 = g2) -> f is subjective
Thanks, this is the only explanation that finally made it click for me. Specifically the part: for all g1,g2 such that g1.f ≠ g2.f -> f is surjective. Which makes sense since if every unique pair of g1,g2 the composition g1.f ≠ g2.f, f has to be surjective. Because the only way g1.f ≠ g2.f is not true (I.e. g1.f = g2.f) is for some objects to be outside the image of f (meaning that f is not surjective)
Pure gold. Thank for explaining this so clearly! some more terms injective, surjective, isomprphism, monomorphism, monic, epic, epimorphism, it's presented so clearly, so I feel I passed this one but beginning to get sweatful, it's beginning to strain my mind but I hope to be able to keep on. Not practicing anything so just watching for now! I hope I'll make it to the end! :) epimorphism if for all c for all g1,g2 we get g1*f=g2*f g1 == g2 then we have epimorphism, difficult to understand still struggling with it. not sure I got it but I think we said that if it is nessesary for g1==g2 so that g1*f==g2*f this must be then the case that we are surjective(epimorphism) otherwise we would if it was not nessasary for g1=g2 then its "allowed" for f not to be epimorhpism(surjective) because we could satify g1*f==g2*f wihtout the need to have g1==g2 hopefully I get it man!!
I understand the reasoning personnaly but I've been taught in classical logic than: A => B 7A V B Then there is hole if we consider g1=g2 then the NECESSITY is no more there. But I think my answer is much more a debate of logic and different logic referential. Or I just mistake?
Thank you for such a good lecture! I have a question about identity. The function identity return the same type not the same value, am I right? Because I have seen some times the the functions like this: function id(a) { return a; } Thank you
this course is shaping up to be really nice! I'm also really glad that you are much more careful now with your viewable bounds than in the beginning of your first series. Generally, this is put together really well. Have you considered combining the two approaches you seem to have thus far, that is your blog and these lecture-length videos, into something more like Khan Academy, with just roundabout 10min spent on individual points of topics? It might be difficult to rethink all the material in that manner but the advantage is that you can much more easily focus on just bite-sized amounts of information that you currently don't quite understand. And from the perspective of the actual lecturer, it's easier to just expand on a topic almost on a whim, say whenever lots of questions come up about a specific point; or perhaps to, once the scaffolding of all the basic information stands, provide more and more short examples that serve as a deep-dive applications of it all. Errata also are easier/possible to deal with: An hour worth of video takes a long time to make and redo and stuff, and with lecture recordings like this, that's downright infeasible - you can hardly reinvite all the people to attend that same lecture just because of some errors you made, but you can realistically revisit or replace 10-is minute long videos.
"most" could mean here, that if you take a random function between two categories - that is, if you just pick any possible mapping from objects in A to objects in B, the probability that the mapping happens to be an isomorphism will be less than 50%. If A and B are infinite, possibly it will even be 0, meaning that it "almost never" happens. With countable infinities, that would probably mean it only happens in a finite number of cases. With uncountable infinities it might mean that the number of cases is at most countable? Not quite sure. With multidimensional cases it could mean that there is a submanifold of lower dimensionality than the embedding space on which it happens or something like that.
furthermore, I think it would be really helpful for people if you added a link to your blog in the description. If you want to go the extra mile you could even put in sources/further reading/relevant blog posts of yours through the new-ish (i)nfo feature of TH-cam.
It appears to me, probably incorrectly, that you’ve proven that g1 = g2 only in the realm of f. G1 o f = g2 o f is still true, even if g1(some point outside of f’s image) != g2(same point outside of f’s image).
A relation is a subset of a Cartesian product. A function is a relation from X to Y if and only if any x in X appears in the relation once. A bijective function is a relation from X to Y if and only if any element z in (X+Y) appears in the relation once and only once
If the image of a function is not the whole codomain then there is no inverse. But if you use the functor “Optional” on the domain, then you CAN have an inverse - all the accidental elements (in codomain but not image) can simply map to None. Well, there’s no Functor that maps the codomain to a category with a functor to the Domain.
An injective function is a relation from X to Y if and only if any x in X appears in the relation once, and any y in Y appears in the relation at most once
A surjective relationship is a relation from X to Y if and only if any element y in Y appears in the relation at least once A surjective function is a relationship from X to Y if and only if any element x in X appears in the relationship once, and any element y in Y appears in the relationship at least once
Functions are uninvertible? What if you created a programming language in which every single variable/expression had "metadata" about its history (I tried doing this once for Clojure BTW). Then you could invert the value by just looking at its history metadata (and yes this includes functional languages not just procedural). This means that all functions are invertible even fold. You could save space by limiting which variables keep their history and by having some variables only store "key frames" and to invert the variable it would go back to a key frame and then re-do the code. This will help me debug code a lot : (.
Thanks prof. Milewski, thanks for your lessons. My critic: From minute 39, your drawing and explanation could have been cleaner. Beyond that, honestly, it looks like a veeeery cumbersome way to defining a property of a function f..resorting to other 2 functions g1, g2, and to a third set or object.. damn ! Anyway, thank you very much.
Indeed, if this definition were only applicable to functions between sets, it would be very cumbersome. The point is, though, that this can be applied to any category, in which morphism are not functions.
44:49 I think this is a less convoluted way of saying it: ∀ g₁ ≠ g₂ . g₁∘f ≠ g₂∘f ⟹ f is epic If for all pairs of gs that are unequal, the composition with f is still not equal, then f must be epic, since the composition can only be equal for unequal gs, if the part that makes them unequal is not hit by f.
An isomorphism is a morphism ƒ: a → b that has an inverse morphism g: b → a, i.e. ƒg = 1b and gƒ = 1a. f is said to be injective provided that for all a and b in X, whenever f(a) = f(b), then a = b; that is, f(a) = f(b) implies a = b. Equivalently, if a ≠ b, then f(a) ≠ f(b). A function f (from set A to B) is surjective if and only if for every y in B, there is at least one x in A such that f(x) = y, in other words f is surjective if and only if f(A) = B.
I don't think so. Even though there's a universal quantification over two things in both cases (that's what you mean by symbolically isomorphic, right?), you still have function *application* for injection whereas it's morphism *composition* for epimorphism. If you lump these together under "symbolically isomorphic" as well then you can subsume pretty much anything under that term, which essentially makes it meaningless.
So i came here for learning functional programming, functors and monads and holy fucknuckles is this math or what! I love it! I don’t know when or if i will get to know wht i wanted but i am hooked on to this instructors video!
I lost all logic after: g1 * f = g2 * f then g1 = g2 . f is defined for subset a' (image of a on b) but outside image is undefined. This blows my mind.
Hm, I find your explanation of epimorphism very confusing. Also not very comprehensible I find the wiki article, but after trying to understand what it and you try to say, what I arrived at is this: If any two morphisms g1 and g2 were equal on their own they also have to be equal composed with f for f to be epic. And thsi is in fact sufficient for f to be epic. so to state this with my procedural brain: for some f : X --> Y: for all g1, g2 : Y --> Z: if g1 == g2 and g1 o f != g2 o f: return f is not epic return f is epic Have I got this right?
If g1 and g2 were equal, than they would automatically be equal composed with f, so that's not it. The way to think about it is to try to find a counterexample using sets. If f is not epic, it means that it doesn't cover the whole of its codomain. There is at least one element that's not in the image of f. Think f(x)=x^2 as a function from real numbers to real numbers. It only maps to positive numbers. You can easily find two functions that are the same on all positive numbers, and if you apply them to the results of f they will be equal. But these two function may differ on negative numbers -- they are not equal on their own. So f is not epic.
Thank you so much for these lectures, they are really interesting, and thank you for taking your time to answer in the comments. I have a question about the epimorphism definition. I understand that if you have some element in the set B, that is not part of the image of A under f, then you are free to choose where g1 will take that element in C, and likewise for g2, and so you can always construct functions g1 and g2 such that they are equal on the image of f, but not equal in general. And if you can't find any functions that are identical on the image of f but not on B in general, then that's proof that the function is surjective. But I don't understand, why you need it to work for all objects. Is it not enough, that you have a single set C, that you can get to from B via g. If there is an element in B that's not part of the image of f, then you don't need to search all the objects, wouldn't any set C suffice as a target that g1 and g2 can differ on, using the excluded element in B? Is it a strengthening of the criteria, that category theory makes, that is not required in the Set category, but which makes the definition more general? Or does it have to do with empty or singleton target sets C, where there are actually no other elements that g1 and g2 can differ on? Again thanks for the presentation, they are really good :)
"if you can't find any functions that are identical on the image of f but not on B in general, then that's proof that the function is surjective." Boris, thank you for phrasing it this way (different from the lecture). I was confused with the last part of the lecture and you helped me understand.
Here's one thing I haven't yet understood: if this is the theory that unites math, and is thus its foundation, why the hell isn't yet it being taught to everybody? Why is math right now a bazillion silos of incomprehensible abstractions?
For example when we say a function (morphism) of a defined category is an epimorphism, do we mean the definition holds for all c's and g's that exist in the category or do we mean all c's and g's that are possible? For example if our category is only: a=Z, b=Z, c=N, f=abs|x| [a->b], g=x [b->c] (plus the necessary composition and identities to make this a category) and only these objects and morphisms, then is f epic?
I'm not sure I understand the question. Do functions have actual existence somewhere outside of our imagination? Or are you thinking of some particular program where you implement a few functions? In the latter case, you'd have to show that they form a category (e.g,. all their compositions exist -- in the same sense they exist -- and there is a polymorphic identity function).
Thanks @tuber12321 You say "in the category Set, the morphisms are all possible functions between two sets." But its only total functions right? Another question: But you can have other categories that are subcategories of Set which only contain specific functions between two arbitrary sets, right?
These videos are so fun and relaxing. Bartosz Milewski is my Bob Ross and morphisms are my happy little trees.
OMG this is almost exactly what I thought :)
Wow this is composition where «Bob Ross» have an arrow to «happy little trees» and where «Bartosz Milewski» have an arrow to «morphisms» you did
«Bartosz Milewski» → «Bob Ross» and «happy little trees» → «morphisms»
which means to say something like:
«Bartosz Milewski» → «Bob Ross» → «happy little trees» → «morphisms»
that is exactly compatible with what it is indeed:
«Bartosz Milewski» → «morphisms»
1:25 operational semantics
1:51 denominational semantics
2:47 function
3:09 pure function
3:20 partial functions
4:11 purity test - memoizable - idempotent
6:20 what are building blocks of composability ?
7:36 expanding on functions
8:00 category sets
8:30 relation - subset of pairs of [set]elements, a subset of cartesian product.
10:20 cartesian product of pairs
11:40 discriminating functions from relations
12:35 this one is bad for function -- cannot be mapped to relation
13:16 total functions - all elements must be mapped into from set1 into set2
14:00 domain of function - starting set.
14:20 codomain - subset ussually called image of the function
18:07 isomorphism
19:30 elevation from element language to categorical language expressed in terms of composition and identity
23:30 (2) reasons disqualifiying isomporphism
a. set f[a,b] -> same element -- not inveritble
b. image does not fill whole codomain
26:30 invertable ? counter-image
27:07 "fibration"
27:50 non-isomorphic sets increase entropy
31:09 mathemeticians language divergence
" injective function does not collapse things" "monic" or monomorphic
32:32 surjective - covers the whole set b from set a "epic" "epimorphism"
if something injective and surjective both they are isomorphic
38:30 define an epimorphism without talking about elements
I think he meant "denotational semantics".
This is amazing. I have very little experience in set theory aside from the very basics, and also no experience in computer science (I am a beginner in programming) but I was able to understand this lecture clearly. I take that to mean you are very thorough and very good at simplifying/explaining things! I appreciate that you don’t just assume knowledge and instead go over every detail with examples! Thank you for posting this on TH-cam for free. I’m someone who is curious about mathematics but has no time or money to enroll in a course right now, so things like this are truly a blessing.
thank you thank you , utterly brilliant, it feels like ive been waiting for this level of explanation for a very long time.
32:50 A good way to think about injectivity and surjectivity is that for an injective function, each element in the codomain is mapped to by *at most one* element in the domain (i.e. zero or one). For a surjective function, each element in the codomain is mapped to by *at least one* element in the domain. If both of these are true (for a bijection / isomorphism), each element in the codomain must be mapped to by *exactly one* element in the domain, since that is the overlap of those two inequalities. (This also assumes that there are no elements in the domain that do not map to at least one element in the codomain, which is the other condition required by injectivity / "1-to-1 mapping" that is not covered by the statement "each element in the codomain is mapped to by at most one element in the domain".)
Thanks a ton for these, Bartosz. A comment about non-injective functions representing abstraction and non-surjective functions representing model was particularly insightful.
28:00
Bartosz - I've been binging on your videos after been a reader of your blog for a couple of months. I've taught Neuroanatomy to medical school students at McGill and Harvard; you are an amazing speaker and thinker. I look forward to your book bringing together Haskell, Category theory and the meaning of life! :-) Merci beaucoup! - E
Thanks Edmund. I appreciate that.
The meaning of life is the ultimate abstraction maybe
By far the most intuitive explanation I’ve come across, appreciate it!
43:00 so "g1 after f = g2 after f" means that they are the same in the sense that they both end up in the same set? because i cant see how its true otherwise
I took a few days to understand the last part about why Epimorphism make this statement true [G1oF = G2oF -> G1 = G2] .
For those who still struggling like me, I hope this explanation can help you.
If function is not Epimorphism then f(a) will cover only some part of b.
Example: "a" is set of Integer, "b" is set of integer and let f be f(x) = 2x.
In this case f(a) will map only from "integer"(a) to "even number"(some part of b).
You mean, "if a function is NOT and epimorphism then f(a) will cover only some part of b."
Ah, yes I mistakenly dropped NOT word. Thank you.
Thanks! But a doubt: how can you prove some function is an epimorphism in some cathegory?
For instance, in the category of types it looks like isEven(int) is an epimorphism because it covers all bools, and xModY is not because it doesn’t covers all integers.
But this is only a refference to surjective logic, how can this fact be extracted from cathegory theory?
@@Bflatful The following is my understanding and I am by no means an expert in the field:
If you know a category, then that means all objects and arrows are known! I think that is very important to remember, since when this is the case you are able to actually check the definition for an epimorphism.
When we are talking about a specific category, e.g. the category of types, then we would use surjective logic since it is easier than arguing over all objects and arrows.
Example: Assuming isEven :: Int -> Bool is NOT an epimorphism then that means there exists a type C and two functions g1,g2(:: Bool -> C) s.t. (1) g1°f != g2°f or (2) g1°f = g2°f and g1 != g2 (that's all we can say with category theory). But since we are in the category of types we can say (assuming case (2)): there exists b in Bool and c1 != c2 in C s.t. g1(b) = c1 and g2(b) = c2. It follows from g1°f = g2°f that b is NOT in the image of f, which is a contradiction, since the image of isEven has to contain b.
For xModY we would simply state a counter-example to the statement (aka two functions where g1(Y) = c1 and g2(Y) = c2 where c1 != c2 in some appropriate type C).
On the other hand, let's say we are in the category with 3 objects a1,a2,a3, and arrows f::a1->a2, h::a1->a3, and g1,g2::a2->a3 (now we also know that g1 != g2, even though we don't know, assuming the arrows were abstracted from "functions", how the arrows look like in terms of arguments!!!; also let all other necessary arrows be defined e.g. id arrows). Now we check if f is an epimorphism: first, we find h = f°g1 = f°g2, but then we actually find that g1 != g2 which means that f is not an epimorphism. If f were an epimorphism then either there would not have existed two different arrows g1 and g2 or there would have been e.g. two different arrows for the compositions h1 != h2 with h1 = f°g1 and h2 = f°g2.
Thanks, this clears my mind
Bartosz, I really enjoy your lectures. It's so good, when people are passionate about what they're doing and talking. Certainly, it holds true for your case. I'm C++, Java, Python engineer learning Haskell and I stopped my Haskell readings for a moment to watch your lectures before, to have better comprehension. Thanks a lot!
21:35 "Tak"?
Tak
Selv tak.
tak
10:07 it will never be "symmetric" in that sense unless we're working with homogeneous relations (subsets of X x X), since pairs are ordered - the first element from the left set, and the second element from the right set. And for the same reason, relations *do* have directionality since A x B != B x A.
I like how watching the course a second time makes you to look at things at different angle, knowing already material of next lections
I had been studying functional programming and was led here by The Algorithms! I have a few days to mess around before I have to get back to studying less abstract stuff, but these are some powerful models of composition and I'm really glad I found these lectures!
Thank you so much Mr. Milewski for everything, the haskell videos and now category theory.. THANK YOU :)
2:44 pure function
8:48 definition of relation
10:11 definition of relation, cartesian product
11:32 comparison between relation and function
34:34 if I can't tell about the internals(elements), how can I talk about morphism's properties? (in terms of category theory)
Guys, I've read the comments and it's seems to me the epimorphisms explanation confused some of us. The trick is in 42:56 . Professor Bartosz reverses(negates) what he just explained until that point to show what would be an epimorphisms. I think the reason some of us were confused was due to english not being our first lang or maybe just missing this crucial part of the explanation. Someone to give a second opinion ?
I think you're right, and that it's just confusing to define something by defining its negation. I'm wondering if there are more conditions for epimorphism to indicate surjectivity, though. Here's a comment I left, let me know what you think:
It seems that for the definition of epimorphism to indicate surjectivity in the case of SET, there must exist morphisms with domain b other than the identity id_b. Because if this is the only morphism in the whole category with domain b, then f will satisfy the epimorphic condition even if it is not surjective. Are there specific conditions under which epimorphisms are surjective? Or am I misunderstanding something?
WOW, just wow. I watch these lectures after the first chapter of Aluffi (algebra chapter 0) and your lectures are a great follow up!
Bartosz you just blow my mind. I get a course few years ago on university about abstract algebra's. Was so complex to understand it at that time that I just past it with out understanding anything. But your video about category theory bring a light to me on abstract algebras. Thank you.
21:10 Why is a one to one correspondence between natural numbers and even numbers? I mean natural numbers contain odd numbers so we don't have a correspondence for them in even numbers.
We make room for them by spreading the even numbers. 0 -> 0, 1->2, 2->4, 3->6, 4->8, and so on.
@@DrBartosz , think you very much. So this works only for infinite domains because expression y=2x will always have a solution, where in a finite domain this expression or it's reverse may endup being null?
PS: Anyway, the course is awesome. I started watching it few times, but my math knowledge is too low so I'm starting the course over and over again, because every time I get new things, that I wasn't able to listen previous time. I have the fear that I will get to the monads series and I will not understand a lot of staff because I skipped to much on basics.
Wrt. the epimorphism definition, I needed to understand that f is epimorphism _only if_ the following holds: "∀ g1,g2, g1￮f=g2￮f => g1=g2". Not sure if it should be _if and only if_ though.
The definition of epimorphism _is not_ just the statement "∀ g1,g2 g1￮f=g2￮f => g1=g2" in itself, which didn't make any sense to me. In the video it is said correctly, but somehow missed it.
To show that f is not surjective / epimorphism in the category Set,
- Find such g1,g2 that
- g1￮f=g2￮f
- g1(a)!=g2(a), where a ∈ B, a ∉ Image(f)
- Thus it follows that "∀g1,g2 g1￮f=g2￮f => g1=g2" does not hold, and f is not surjective.
On the other and, if for all g1,g2 that have g1￮f=g2￮f, you cannot find any value b for which g1(b)!=g2(b), where b ∈ B, b ∉ Image(f),
then f is surjective/epimorphic.
Makes sense to me, but not 100% confident about this.
I think the implication (=>) in "∀g1,g2 g1￮f=g2￮f => g1=g2" means that if composition of g1 with f and composition of g2 with f are not the same, then it does not help in determining whether f is surjective.
I wonder what happens if there are no morphisms from B to C. Doesn't that mean that the for all statement holds true, and f is surjective by that definition, while it certainly doesn't have to be if f is chosen not to be?
"g1=g2 => g1￮f=g2￮f" holds for any f with the matching domain/codomain, not a very interesting assertion
Hello Bartosz,
I'm going through your entire course, I absolutely love it, thank you very much!
I'm just struggling a bit with my understanding of epimorphisms connection to surjectivity. (Funnily enough, I seem to understand monomorphisms connection to injectivity better).
- == (after, eg. apply g after f == g - f)
Is this the correct thinking?: If I take all possible functions g1 and g2 (:: Y --> Z) , if g1 - f is the same as g2 - f, and if this knowledge alone tells me that g1 is equal to g2, then I can be sure that f is an epimorphism.
I don't really understand though what it means that g1 == g2, as we specifically define g1 != g2 (you said for the same points they go to different values). Unless we are saying here that g1 == g2 over the domain that the image of `f` is exposing on Y (your diagram at 45:01).
-- spends 10 more minutes thing --
Or wait is this the idea: If I take any function g1, g2, if g1 - f is the same as g2 - f, and if this knowledge alone tells me that g1 is equal to g2, then f must be surjective because g1 doesn't have to be equal to g2 in general but in our case they are equal which MUST imply that f is surjective because it must be not mapping to outputs where g1 and g2 would not be equal? So how exactly are defining the equality of g1 and g2, they are clearly different functions, so are we saying equal as in "these functions are the same over the inputs we will give them", which in this case is the image of `f`?
I guess I'm struggling in understanding what the statement: "=> g1 = g2" even means.
Thanks, hopefully you can help me understand.
Great lectures, thanks again so much :D
g1 = g2 means they are equal for all inputs. But if f is not surjective, it can't feed all possible inputs to them. Consider some examples. Like two functions that are the same for all positive numbers but different for negative ones. Compose them after f(x)=x*x (wich is not surjective) and the results will be equal.
Thank you for your fast response Bartosz!
So I think I understand this logic, we take *different* functions g1 and g2, if over the outputs of f g1 == g2, then f MUST be surjective because we had different functions that acted the same, we must have been giving them the sub-set of their inputs for which they have the same output.
I hope I'm understanding correctly.
Follow up question: What if I don't even have 2 functions g1 and g2 which are different? What if all I had in my entire hom-set from Y -> Z was 2 functions, g1 and g2, and they were the same for all inputs.
Now it seems that this reasoning would lead me to believe that f was surjective, because for all g1 - f == g2 - f ==> g1 == g2, when indeed f need not be surjective, it simply only has 2 functions g1 and g2 and they are actually equivalent over the their entire domains. So this again leaves me confused, hopefully you see my counter example and can explain why I am saying BS :)
Thanks again!
g1 and g2 don't have to be different.
Ok maybe I think I finally got it....
Basically we're saying, if I have 2 functions and I feed them an input, let's say the number 1, and they both produce 5, are they the same function? Well I don't know! When do you know? When you've tested every single input. So, if the fact that 2 functions are the same after feeding them some input (the result of f) implies that they are the same, then f MUST map to everything and hence be surjective.
Does that explanation make sense? Sorry for the confusion, thanks again Bartosz
They are only the same function if they are equal on ALL inputs.
Suppose I design g1 and g2 in the following way. For all elements in the image of f, I make g1 and g2 map to the same places. This is _not_ enough to say that g1 == g2 in general, because the elements _outside_ Im(f) might still be mapped differently. On the other hand, it _is_ enough to tell you that g1 . f == g2 . f. That's because those two compositions never go "through" any elements outside of Im(f). So we have a situation where g1.f == g2.f but g1 != g2. This situation only happened because we found elements outside of Im(f) where we could make g1 and g2 differ. If there are no such elements, then we can't have this situation: instead, g1.f == g2.f MUST mean that g1 == g2.
I think there is a mistake in the shown "definition" for categorical surjectiveness or epimorphism (might be that I'm too used to a Gries & Schnider's syntax and I'm missing the "if f is surjective then the for-all quantification holds" but correct me if I'm wrong):
consider: a={1,3,5}, b={2,4,6,8,10}, c={-2,-4,-6,-8,-10}
and functions
f :: a->b such as f(x) = 2x
g1:: b->c such as g1(x) = -x
g2::b->c such as g2(x) = {-x if (x not in ), -4 if (x = 8), -8 if (x = 4)}
Now g1.f == g2.f for c but g1 is not the same as g2 and f is obviously not a surjection
f is an epi if _for every_ c, g1, and g2, (if g1.f = ge2.f then g1=g2). I know, the quantifiers are often confusing. You picked some particular g1 and g2, but there are other choices you havent't tried. For instance g1 that maps 4 to -2 and g2 that maps 4 to -10.
I believe at the end he is saying IF "g1 f == g2 f implies g1 = g2" THEN f is an epimorphism
so if i understand this correctly: g1 and g2 differ only for elements outside of the image of f, that's the key point here. so if g1.f == g2.f is true for all elements in c (mapped by g1 or g2), then f is epimorphic. that's because this couldn't be true if the image of f wasn't matching all elements in b.
So it must be Surjective and Unglued 😅😅😅 27:00 or we can then decide to consider the fibers only to have the isomorphisms???
13:10 Isn't it by definition always the case that all elements of set A have a mapping to an element of a subscert of set B. If it didn't it would not be part of set A to begin with right?
Hello, with regards to the definition of epimorphisms: We are basically describing what it means to be surjective but via a composition, right? So is it possible to say, in metaphorical terms that due to the image of f not being equal to the co-domain we cannot see (from the vantage point of f) whether g1 and g2 would actually be different, so they are effectively the same? It's like a non-constructive proof of sorts? Is this a good way to see it, or does it miss the point? Cheers for the vid.
If f is not surjective then it doesn't probe the whole domain of gs.
@@DrBartosz Sorry, yes, I understand. What I described is how we know if something is not surjective?
These lectures are amazing :)
Our engineering team goes through them one by one on a weekly basis :)
Thanks Bartosz!
Your team sounds like it sucks.
Bartosz in a definiiton of epimorphism you compose f with g1 and g2 whereas codomain of f is not a domain for g1 and g2. How is it possible to compose it?
The codomain of f is b. You are probably thinking of the image of f, which does not cover the whole domain of g1 and g2. Example: f x = x^2. Codomain is Int, image is positive Int. You are free to compose it with a function whose domain is Int, say g x = x+1. You'll get a function h x = x^2+1.
yeap, I thought that we have to use image of f as a domain for g1 and g2 during composition. That's why I'm asking. Thanks for clarification
I was a bit confused, but I hope I got it: in the last example with sets a,b and c it was shown that we cannot say that f is surjective (since it isn't) because g1 and g2 are not equal (for example according to the "composition table" of the category). Is this correct?
At around 42:49 you mention that the compositions g1 after f and g2 after f are the same even though the morphisms g1 and g2 are different - they map the same point to two different points. Is there something am missing that explains why they are the same?
Take f x = x^2. The result is always positive. g1 and g2 are the same for positive numbers, but differ for negative. Say g1 x = x and g2 x = abs x (absolute value).
Thanks in advance for your patience, I'll figure this out eventually. So, say you have the morphisms g1 x = x=/2 and g2 x = x * x, even though they start from the same point they obviously end up in different points in the corresponding category. So what does the statement "g1 is equal to g2" mean? Is it sufficient, for both to result in positive integers for it to be said that they are the same?
@@skmuiruri : You have to find g1 and g2 that are equal after you compose them with f. Yours aren't. For instance, take x=2. f x = 4. g1 4 = 2. g2 4 = 16. Try this with my g1 and g2. There is no such x that g1(f x) is not equal to g2(f x).
@@BartoszMilewski f is an epimorphism from a → b if for every other object c in the whole category and for every pair of morphism that goes from b → c if the composition g1 ° f is the same as g2 ° f. It follows then that g1 equals g2.
So the underlying premise of this statement is "IF you can find morphisms g1 and g2 that are equal after composing them with f then the above statement holds". Is that the point you're making that I can't seem to grasp?
Excellent, and a great gift to all who want to learn, Thank You !!!
Something that confuses me, when you have a function that is not surjective, meaning there are elements in the codomain that are not mapped to by any element in the domain, then why do we not say that the function's codomain is just that subset? Is any superset of the image of a function also considered a codomain?
Specifying a codomain is part of the definition of a function. A function that doubles integers produces even numbers only, so its codomain can be specified as the set of even numbers, and then it's surjective. If you specify the codomain as integers, then it's not surjective. These are two different functions. They are related, because you can inject even numbers into integers, so the second function is a composition of the first followed by the injection.
@@BartoszMilewski thanks for the reply! The part I wasn't getting was that those are two different functions, that makes a lot of sense
Simply excellent, for a remote student with a minimum resources u just make an enlightenment tower, like a light house ,for a lost direction student in a vast ocean
How does Category Theory relate to Poly-Contextual Logic developed mainly by Gotthard Günther?
~ 27:00 Using entropy as a metaphor for the information loss from non-invertible functions is cute. I too, was a physicist in a past life (now doing software and control systems engineering).
Regarding injectivity does this mean if we get a solution vector as the output then the function is injective but if we get a scalar as the output then the function is not injective? Since we aren't converging to zero or one value but potentially many values.
I have a feeling (vector, scalar, converging) that you are currently dealing with machine learning, so I'm going to use some programmer-friendly examples. Remember all along that f is injective if and only if for x₁ ≠ x₂, f(x₁) ≠ f(x₂), which can be stated as "if the inputs are different, the outputs must be different too".
Let's try f₁ : uint8 → uint8 × uint8 × uint8, such that x → (x mod 2, x mod 3, x mod 6). You can see very quickly that for x₁ = 0 and x₂ = 12, we have x₁ ≠ x₂ but f₁(0) = f₁(12) = (0, 0, 0). So even though f returns a vector (of length 3), it is not injective.
Now let's try f₂ : uint8 × uint8 → uint32, such that (a, b) → a*256 + b. Here I'm doing the opposite, reducing from a vector to a scalar, but in such a way that you cannot find two different inputs that will give you the same output. So the function is injective.
22:30 You can definitely stabelish a bijective function between the sets of natural numbers and even numbers. But you don't work division, but with the operation of doubling. Every number in ℕ has a double in the Even set and every even number has a half in ℕ.
the function doubling::ℕ a → E b is the inverse of halving::E b →ℕ a
doubling.halving = id in ℕ; halving.doubling = id in E
This is the trick of the function, right? if the function was from N -> N than you cannot invert, but if it's from N -> E, where E is the set of even numbers then you can :)
Thx for this video series, awesome!
I think I understand the definition of an epimorphism.
But I don't understand what can be said about f if g1 and g2 differ also under the image of f.
So this means g1 =! g2 and also g1.f != g2.f.
Isn' it true that in this case f can also be a surjective function?
That would imply that in this case some surjective functions cannot be determined with the defintion in the video?
Such function say nothing about f being epi or not. It just means: keep looking. If you exhaust all options, then you know f is epi.
How do you compose g1 . f ? g1 is not total therefore it is not a morphism that can compose with f.
Totality is only defined for sets, and here we're talking about morphisms. But the argument is valid for sets, too, in which case g1 is total. It's defined for all argument values.
@@DrBartosz Thank you very much for all your classes. I will think hard about this epimorphism proof for the next few days :)
These videos are amazing. Thank you so much for sharing.
19:28 i think you inverted id_a and id_b (?)
if g goes from b to a, and f from a to b, then starting frmo b, it goes back to b, so id_b
Bartosz, these lectures are great! I have a question on epimorphisms and surjectivity (44:22). It seems that for the definition of epimorphism to indicate surjectivity in the case of SET, there must exist morphisms with domain b other than the identity id_b. Because if this is the only morphism in the whole category with domain b, then f will satisfy the epimorphic condition even if it is not surjective. Are there specific conditions under which epimorphisms are surjective? Or am I misunderstanding something?
Epimorphism is surjective in Set. There is no definition of surjectivity outside of Set.
@@BartoszMilewski Thanks for your response. "Epimorphism is surjective in Set" is exactly what I want to verify, though, so I'm considering edge cases. Isn't it the case that when the only morphism with domain b is the identity, the definition of epimorphism is trivially satisifed? Because id_b = id_b, and id_b after f = id_b after f. So f could be any function (surjective or not) from a to b, and Category theory will see it as an epimorphism in this case. Where is my error?
Here's a concise counterexample.
Consider the following Category:
Objects: A, B
Morphisms: all identities, along with f:A->B and the required compositions
It follows that f is an epimorphism, for the only morphism with domain B is id_B, and id_B∘f = id_B∘f and id_B = id_B.
Now we may instantiate this category with sets and functions. Let:
A = 2Z (all even integers)
B = {0, 1}
f:A->B is such that f(x) = 1 if x is even, f(x) = 0 if x is odd.
f is clearly not surjective, but in the category defined above it is classified as epimorphic. The problem is that the category lacks the resources (e.g. other morphisms) with which to sufficiently probe f. So, for epimorphisms to indicate surjective functions in Set, these other morphisms must exist, which to my knowledge has not been stated. What is inaccurate here?
@@BartoszMilewski For anyone with the same confusion as I had: Set refers to THE category of ALL sets and ALL functions. In this category, it is guaranteed that epimorphisms correspond to surjective functions. Other categories with set objects and function morphism may be defined where this is not the case, as in my example
for your example of odd and even numbers and isomorphism, can't it be isomorphic? there are multiple ways to create a one to one correspondence right? i understand natural numbers and reals do not based on infinity theory stuff, but sort of confused about the odd and even one.
I am trying to use ChatGPT to understand but he got confused more than I was: (1:13) _«The statement "There are very few of them, none of the major ones" is incorrect. It is not true that none of the major programming languages have formal operational semantics. In fact, several major programming languages do have formally defined operational semantics or formal specifications that describe their behavior»._
You have to use GPT4 to discuss category theory and you kinda need to know it already, otherwise ChatGPT will lead you to nonsense and will make many mistakes that you will not notice. That said, it can really help clarifying some things indeed.
try claude
Is the condition for epimorphism a necessary condition; in that it includes morphisms that are not epimorphisms but all epimorphisms satisfy it? If so is a sufficient condition required?
But isn't it the case that epimorphism follows only if g1 and g2 and any other g differ only outside the image? Or in other words, if any pair of g's differ within the f's image, the definition of epimorphism would break because it would not be considering that pair.
Hi Maybe you talk about it later, but I have to ask now, before I forget: isn't every function surjective if you just define the codomain precisely enough? I mean, it's just for the lack of a strong enough type system in most programming languages, that we define the return type of f(x:Int) -> x*2 as Int. If we could create types with functions (I think Idris is going that way), then we could just say that Even = Int*2, and f :: Int -> Even
You could, but then you wouldn't be able to compose it with another function that takes and Int.
@@DrBartosz Why? The compiler could figure out that Even is a sub-type of Int because the operation on it was multiplication with Int, which doesn't lead out of Int. Anyway, it's an implementation detail, I just don't really understand why the codomain for x*2 is necessarily given as Int, by the same accord we could say it's Real, or any type that contains the even numbers, and technically we would be right. But maybe I just look at it from a programming point of view, where arguments of subtypes are automatically cast to the type of a function parameter.
You have just discovered that any function can be decomposed into a surjection and an injection. The cast from Even to Int is the injection.
Excuse me. I didn't understand surjection equivalent in categorical therms. After you explained it: which function is surjective? f? g? f.g? f.g1 or f . g2?
Oh. The explanation continued in the next lecture. If all given conditions are true, then a is an epimorfism from a to b.
f : : a -> b
Vectors are dual to co-vectors (forms) in General Relativity.
Syntropy is dual to increasing entropy
Syntropy is the integration or convergence of information into predictions, expectations or priors.
Entropy is the differentiation or divergence of information into new states.
Integration is dual to differentiation
Convergence is dual to divergence
Functions have targets or goals, teleology = non-isomorphic, the arrow of time or increasing entropy.
Real-world analogy:
Like in a security camera system. An epimorphism is like having cameras that cover every part of a building. Two people claiming to know what happened in the building (like our functions g1 and g2) must agree if they're both telling the truth, because the cameras see everything.
A non-epimorphism is like having blind spots in the camera coverage. Two people could give different accounts of what happened in the blind spots while agreeing on everything the cameras saw.
Maybe negating the definition of epimorphism might help some of you: If f is not surjective, then we can always find a pair of functions that map at least one of the elements in B \ Image(f) differently to C. If we cannot find such a pair, f must be surjective.
But what if there is no such pair and B\Image(f) /= empty set?
As an undergraduate computer scientist, I'm loving this series
Thanks for this content, professor!
Your didactics is really great!
I love your videos!
However, I think that it is not completely clear about one thing, is a category an algebraic structure? Like a generalized group/graph/set thingy? It seems already that it is not completely generalized, i.e. there are many assumptions about objects, existence of morphisms, enumeration, and truth value. I am now wondering if logic systems are static within all categories.
Like we can derive all of our usual theorems from axioms using propositional logic, but under a different logic system, the same theorems do not hold. If categories all rely on assumed logic, then a category is essentially another algebraic structure
Maybe it's an obvious question, but long into the course and I still don't get how we can compare morphisms with our "category glasses" still on. Because to define equality we need to see what morphisms exactly do with each element inside of a category. And if they do the same thing, then they are equal.
For example we may have three functions Int -> Int:
f1 = (+2)
f2 = (2+)
f3 = (2*)
And to say that f1 is equal to f2 (and I'm not sure they are actually equal) we need to compare all elements in a look-up table, which we don't have with our glasses still on.
I tried to google it and the first thing I found is that we actually can't compare functions at all.
stackoverflow.com/a/4328965
So how exactly does this part of a proof work?
g1 . f = g2 . f => g1 = g2
No, it's not an obvious thing, and it's sort of a meta-question. If you're already in a category, morphisms between two objects form a set, so one composition produces an element, another composition produces an element, and they are both from the same set. If they produce the same element, they are equal.
But how we construct this category in the first place is a different issue. The sets of morphisms and their composition are extracted from the programming language, and during this extraction we might legitimately ask the question: do these two functions correspond the same morphism? This might be, in general, undecidable within a given language. The operative definition is that two functions are equal if they produce the same output for the same input (extensional equality), but how do you check that?
@@DrBartosz Oh, I see. But everything starts to look sketchy if we want to compare functions by their internal addresses in memory. If we do this then "g1 . f = g2 . f => g1 = g2" still holds just because there is no equal functions-each function has its own address in memory-and we won't be able to pick out these faulty functions from "the universe" of functions, and if we can't do that then each and every function should be surjective. Which is not exactly what we wanted.
Really enjoying this series! A question in the surjectivity proof: At this point I'm not certain that we've explicitly defined arrow equality, have we? How do we define it if we can't look inside the objects? Because we can have many arrows from one object, how do we know that these two are equal?
Arrows between two objects form a set. So it's just equality of set elements.
"If *g1 . f = g2 . f* always implies *g1 = g2* , then *f* is an epimorphism." How would we prove that *g1 . f = g2 . f* always implies *g1 = g2* ?
Depends. Either you have "no idea" what the morphisms are, but you have some table defining the composition for them, or you have know to what your category actually is. In the first case you just look at the table and see what morphisms have this property and thus are epimorphisms. In the second case you can prove it depending on your category. Lets say we talk about the category of all sets and morphisms are functions. For every function, you can show whether it is injective or surjective. Then you can prove that a function is surjective if and only if it is an epimorphism and a function is injective if and only if it is an monomorphism. This gives you a tool to say about any function whether it is a mono- or epimorphism.
Are two morphisms g,h equal (i.e "g = h") if the Image of g and h are the same? Otherwise the definition of the epic morphism makes little sense to me, because I can think of counter examples. For example let f :: A -> B; g1, g2 :: B -> C such that Im(f) = B then f is clearly surjective, but I can find two functions g1, g2 such that Im(g1) = Im(g2) which map elements differently to C. Let A = B = C = {1,2} and g1(1) = 2 and g1(2) = 1 and g2(1) = 1 and g2(2) = 2. then g1 and g2 are different, at least out of the perspective I am used to, but they produce the same Image, namely C.
Part of the definition is that you are supposed to pick g1 and g2 such that g1.f = g2.f.
there is no such thing as the concept of "the image" of a morphism in a category. they just have a codomain, but the codomain is an object and objects are atomic and have no internal structure.
He said ∀g₁, g₂, f∘g₁ = f∘g₂ means that f is an epimorphism, and that epimorphism in Set is a surjective function. But I still can imagine some f∘gₙ ≠ f∘g₂ (which means f is not an epimorpshism), whilst f is a surjective function. So, in Set, though epimophism is a surjective function, but not every surjective function is an epimorphism, right?
Never mind, I was confused by the fact Bartosz pictured an epimorphism not covering its whole codomain. However a surjective function must cover whole codomain, by definition. That relocates my confusion though to a question why he thinks epimorphisms in Set are surjective functions.
You have to be careful when negating such complex statements. f is not surjective if there exist g1 and g2 such that f.g1=f.g2 and g1 is not equal to g2. The negation of implication a=>b is: a and not b.
Thank you! To any who reading these comments: f∘g₁ should've been g₁∘f, but Bartosz in reply somehow figured it. I am so embarrassed, my only justification is a reference to Jeremy-kun who said that mathematicians are chronically lost and confused, that's their natural state of being¹ 😛 I do have questions, but I think I should rewatch the video before writing them down.
1: j2kun.svbtle.com/mathematicians-are-chronically-lost-and-confused
I feel so damn privileged to be able to watch this
Thank you so much. I have been struggling with epimorphisms for some time now.
And only after watching above I realised that if g1 ∘ f = g2 ∘ f is true then g1 = g2 must be verified to be true as well.
I fell into the trap thinking if A then we can conclude B. The correct statement is if the implication is true then f is an epi (and surjective under set).
Incredible lecture, professor!
Thank you for this lesson, what about "random" function which returns random numbers, I think it maps one value from the first set to many values on the other set?
"Random" is not a function from strict classical mathematical point of view. Traditional approach for randomness in mathematics is via Lebesgue-Rokhlin probability space that effectively models randomness via hidden variables.
@@dmitriykorolevich2208 Thank you for answering my question
First of all, thanks for these great lectures! :) One question remains though. Am I right when saying that: We model a function as a subset of the morphisms of a category?
Oh, I think the definition you proposed will also work just fine if g1 and g2 are just single morphisms. But what about f?
Really nice to have a good and very passionated lesson on categories ... Gonna eat the whole in one night hehe
Just wondering : Why isn't it enough to define epimorphisms like this : f beetween objects a and b is epic if for every morphism g1, g2 from b to b, g1 after f = g2 after f implies g1=g2 ? Why do you need to check this property for all objects c ? If you're able, via f, to completely determine any permutations on elements of g, it seems epimorphic-enough (for the set theory intuition at least ..) Also would have the feeling that if g is an epimorphism from b to b and that for all epimorphism h from b to b we can simplify via the property with f, then f is an epimorphism ?
he doesn't, the thing with category theory is that we can define the whole thing without using the elements (it's just helpful to visualize the elements because most of the students will be familiar with university Analysis aka ZF set theory) and make use of other morphisms to describe something "equivalent" to surjectiveness.
Oh, I misunderstood your question. We need to map g1 and g2 from B to C because they are functions. I don't think the "For all C" is necessary, because looking at epimorphisms on Wikipedia, it does without it. de.wikipedia.org/wiki/Epimorphismus
Thanks for the clear explanations. Is there a book you would recommend?
Now this probably isn't a perfect substitute for a proper book but Bartosz Milewski also has a blog on which he goes through similar material (along with other things). Check it out if you like:
bartoszmilewski.com/2014/10/28/category-theory-for-programmers-the-preface/
28:00 A little point on entropy - pure functions can only decrease entropy. Entropy is related to the number of ways a system could be in, and a function can only decrease this.
Applied to computer science, a hash function should be hard to inverse, but if you do too many non-invertible operations, you reduce the size of the image.
As with every analogy, it only goes so far. My analogy is that a process that increases entropy is irreversible. A computer that evaluated a lossy function lost some information and dissipated some heat. A function took a piece of paper with some numbers and burnt it to ashes.
Regarding the subjective argument, this is how I made myself understand it:
Given : If f is not subjective -> (There exists some g1, g2 such that, g1 /= g2 and g1.f = g2.f )
This is of form p -> q thus, ~q -> ~p is also true. Hence above statement can be written as:
~ (There exists some g1, g2 such that, g1 /= g2 and g1.f = g2.f ) -> ~ (f is not subjective)
=> (For all g1,g2 such that, g1.f /= g2.f or g1 = g2) -> f is subjective
Further (g1.f /= g2.f or g1 = g2) is of form ~p or q which can be written as p -> q
Hence final statement becomes
=> (For all g1,g2 such that, g1.f = g2.f -> g1 = g2) -> f is subjective
Thanks, this is the only explanation that finally made it click for me. Specifically the part: for all g1,g2 such that g1.f ≠ g2.f -> f is surjective.
Which makes sense since if every unique pair of g1,g2 the composition g1.f ≠ g2.f, f has to be surjective. Because the only way g1.f ≠ g2.f is not true (I.e. g1.f = g2.f) is for some objects to be outside the image of f (meaning that f is not surjective)
Thank you, Bartosz!!
Can someone explain to me how you could compose g1 and g2 with f, when none of the functions had a point in the image of f?
Oh, f is NOT an epimorphism, I think I understand now.
g1 and g2 were assumed to be total on b.
Pure gold. Thank for explaining this so clearly! some more terms injective, surjective, isomprphism, monomorphism, monic, epic, epimorphism, it's presented so clearly, so I feel I passed this one but beginning to get sweatful, it's beginning to strain my mind but I hope to be able to keep on. Not practicing anything so just watching for now! I hope I'll make it to the end! :) epimorphism if for all c for all g1,g2 we get g1*f=g2*f g1 == g2 then we have epimorphism, difficult to understand still struggling with it. not sure I got it but I think we said that if it is nessesary for g1==g2 so that g1*f==g2*f this must be then the case that we are surjective(epimorphism) otherwise we would if it was not nessasary for g1=g2 then its "allowed" for f not to be epimorhpism(surjective) because we could satify g1*f==g2*f wihtout the need to have g1==g2 hopefully I get it man!!
I understand the reasoning personnaly but I've been taught in classical logic than: A => B 7A V B
Then there is hole if we consider g1=g2 then the NECESSITY is no more there.
But I think my answer is much more a debate of logic and different logic referential. Or I just mistake?
Thank you for such a good lecture!
I have a question about identity. The function identity return the same type not the same value, am I right?
Because I have seen some times the the functions like this:
function id(a) {
return a;
}
Thank you
It returns the same value.
@@DrBartosz, thank you!
13:50 - Naming domains, co-domains and image
How to describe function max? It has more than one element (list).
You represent a list as a data structure. This involves algebras, which are discussed in later lectures.
this course is shaping up to be really nice! I'm also really glad that you are much more careful now with your viewable bounds than in the beginning of your first series. Generally, this is put together really well.
Have you considered combining the two approaches you seem to have thus far, that is your blog and these lecture-length videos, into something more like Khan Academy, with just roundabout 10min spent on individual points of topics?
It might be difficult to rethink all the material in that manner but the advantage is that you can much more easily focus on just bite-sized amounts of information that you currently don't quite understand.
And from the perspective of the actual lecturer, it's easier to just expand on a topic almost on a whim, say whenever lots of questions come up about a specific point; or perhaps to, once the scaffolding of all the basic information stands, provide more and more short examples that serve as a deep-dive applications of it all.
Errata also are easier/possible to deal with: An hour worth of video takes a long time to make and redo and stuff, and with lecture recordings like this, that's downright infeasible - you can hardly reinvite all the people to attend that same lecture just because of some errors you made, but you can realistically revisit or replace 10-is minute long videos.
22:08 may be x is a set of all naturals and y is set of even? Thank you for great lecture, by the way)
x is set of all integers in that case not naturals.
"most" could mean here, that if you take a random function between two categories - that is, if you just pick any possible mapping from objects in A to objects in B, the probability that the mapping happens to be an isomorphism will be less than 50%. If A and B are infinite, possibly it will even be 0, meaning that it "almost never" happens. With countable infinities, that would probably mean it only happens in a finite number of cases. With uncountable infinities it might mean that the number of cases is at most countable? Not quite sure. With multidimensional cases it could mean that there is a submanifold of lower dimensionality than the embedding space on which it happens or something like that.
furthermore, I think it would be really helpful for people if you added a link to your blog in the description. If you want to go the extra mile you could even put in sources/further reading/relevant blog posts of yours through the new-ish (i)nfo feature of TH-cam.
It appears to me, probably incorrectly, that you’ve proven that g1 = g2 only in the realm of f. G1 o f = g2 o f is still true, even if g1(some point outside of f’s image) != g2(same point outside of f’s image).
But that's exactly the point. If there is a point outside of the f's image, f is not an epimorphism.
@@DrBartosz I stumbled upon the same thing, thanks for the clarification
A relation is a subset of a Cartesian product.
A function is a relation from X to Y if and only if any x in X appears in the relation once.
A bijective function is a relation from X to Y if and only if any element z in (X+Y) appears in the relation once and only once
If the image of a function is not the whole codomain then there is no inverse. But if you use the functor “Optional” on the domain, then you CAN have an inverse - all the accidental elements (in codomain but not image) can simply map to None.
Well, there’s no Functor that maps the codomain to a category with a functor to the Domain.
An injective function is a relation from X to Y if and only if any x in X appears in the relation once, and any y in Y appears in the relation at most once
A surjective relationship is a relation from X to Y if and only if any element y in Y appears in the relation at least once
A surjective function is a relationship from X to Y if and only if any element x in X appears in the relationship once, and any element y in Y appears in the relationship at least once
Thanks so much for these videos, it's so helpful. Also thanks for the caption as well.
Functions are uninvertible? What if you created a programming language in which every single variable/expression had "metadata" about its history (I tried doing this once for Clojure BTW). Then you could invert the value by just looking at its history metadata (and yes this includes functional languages not just procedural). This means that all functions are invertible even fold. You could save space by limiting which variables keep their history and by having some variables only store "key frames" and to invert the variable it would go back to a key frame and then re-do the code. This will help me debug code a lot : (.
But those are not pure functions then. Because the history you're keeping is state and to add to the history you're adding side-effects.
try inverting isEven ;)
Thanks prof. Milewski, thanks for your lessons. My critic: From minute 39, your drawing and explanation could have been cleaner. Beyond that, honestly, it looks like a veeeery cumbersome way to defining a property of a function f..resorting to other 2 functions g1, g2, and to a third set or object.. damn ! Anyway, thank you very much.
Indeed, if this definition were only applicable to functions between sets, it would be very cumbersome. The point is, though, that this can be applied to any category, in which morphism are not functions.
44:49 I think this is a less convoluted way of saying it:
∀ g₁ ≠ g₂ . g₁∘f ≠ g₂∘f ⟹ f is epic
If for all pairs of gs that are unequal, the composition with f is still not equal, then f must be epic, since the composition can only be equal for unequal gs, if the part that makes them unequal is not hit by f.
An isomorphism is a morphism ƒ: a → b that has an inverse morphism g: b → a, i.e. ƒg = 1b and gƒ = 1a.
f is said to be injective provided that for all a and b in X, whenever f(a) = f(b), then a = b; that is, f(a) = f(b) implies a = b. Equivalently, if a ≠ b, then f(a) ≠ f(b).
A function f (from set A to B) is surjective if and only if for every y in B, there is at least one x in A such that f(x) = y, in other words f is surjective if and only if f(A) = B.
The definition of "categorical surjection"/epimorphism is symbolically isomorphic to the set theoretic definition of injection. That's odd.
I don't think so. Even though there's a universal quantification over two things in both cases (that's what you mean by symbolically isomorphic, right?), you still have function *application* for injection whereas it's morphism *composition* for epimorphism.
If you lump these together under "symbolically isomorphic" as well then you can subsume pretty much anything under that term, which essentially makes it meaningless.
So i came here for learning functional programming, functors and monads and holy fucknuckles is this math or what! I love it! I don’t know when or if i will get to know wht i wanted but i am hooked on to this instructors video!
This kind of video turns people into Hokages.
You are an amazing person Sir
35:51 与主体本质相关的对象是主体固有而有客观的本质.
In 14m50 I would say domain/codomain, preimage/image
I lost all logic after: g1 * f = g2 * f then g1 = g2 . f is defined for subset a' (image of a on b) but outside image is undefined. This blows my mind.
Every function is defined on the whole set (these are total functions)
Bartosz Milewski Thank you😁
Hm, I find your explanation of epimorphism very confusing. Also not very comprehensible I find the wiki article, but after trying to understand what it and you try to say, what I arrived at is this:
If any two morphisms g1 and g2 were equal on their own they also have to be equal composed with f for f to be epic. And thsi is in fact sufficient for f to be epic.
so to state this with my procedural brain:
for some f : X --> Y:
for all g1, g2 : Y --> Z:
if g1 == g2 and g1 o f != g2 o f:
return f is not epic
return f is epic
Have I got this right?
If g1 and g2 were equal, than they would automatically be equal composed with f, so that's not it. The way to think about it is to try to find a counterexample using sets. If f is not epic, it means that it doesn't cover the whole of its codomain. There is at least one element that's not in the image of f. Think f(x)=x^2 as a function from real numbers to real numbers. It only maps to positive numbers. You can easily find two functions that are the same on all positive numbers, and if you apply them to the results of f they will be equal. But these two function may differ on negative numbers -- they are not equal on their own. So f is not epic.
Thanks a lot, now I get it.
Very well explained!
Thank you so much for these lectures, they are really interesting, and thank you for taking your time to answer in the comments.
I have a question about the epimorphism definition. I understand that if you have some element in the set B, that is not part of the image of A under f, then you are free to choose where g1 will take that element in C, and likewise for g2, and so you can always construct functions g1 and g2 such that they are equal on the image of f, but not equal in general. And if you can't find any functions that are identical on the image of f but not on B in general, then that's proof that the function is surjective.
But I don't understand, why you need it to work for all objects. Is it not enough, that you have a single set C, that you can get to from B via g. If there is an element in B that's not part of the image of f, then you don't need to search all the objects, wouldn't any set C suffice as a target that g1 and g2 can differ on, using the excluded element in B?
Is it a strengthening of the criteria, that category theory makes, that is not required in the Set category, but which makes the definition more general? Or does it have to do with empty or singleton target sets C, where there are actually no other elements that g1 and g2 can differ on?
Again thanks for the presentation, they are really good :)
I think you answered your own question.
"if you can't find any functions that are identical on the image of f but not on B in general, then that's proof that the function is surjective." Boris, thank you for phrasing it this way (different from the lecture). I was confused with the last part of the lecture and you helped me understand.
Here's one thing I haven't yet understood: if this is the theory that unites math, and is thus its foundation, why the hell isn't yet it being taught to everybody? Why is math right now a bazillion silos of incomprehensible abstractions?
Cool..really cool
In our definitions and proofs, do we talk about all functions that CAN exist or all functions that DO exist?
For example when we say a function (morphism) of a defined category is an epimorphism, do we mean the definition holds for all c's and g's that exist in the category or do we mean all c's and g's that are possible?
For example if our category is only: a=Z, b=Z, c=N, f=abs|x| [a->b], g=x [b->c] (plus the necessary composition and identities to make this a category) and only these objects and morphisms, then is f epic?
I'm not sure I understand the question. Do functions have actual existence somewhere outside of our imagination? Or are you thinking of some particular program where you implement a few functions? In the latter case, you'd have to show that they form a category (e.g,. all their compositions exist -- in the same sense they exist -- and there is a polymorphic identity function).
What are c and g here? In your example, f cannot be epic because we know that abs is not surjective (from Z to Z).
BTW, in the category Set, the morphisms are all _possible_ functions between two sets.
Thanks @tuber12321
You say "in the category Set, the morphisms are all possible functions between two sets." But its only total functions right?
Another question: But you can have other categories that are subcategories of Set which only contain specific functions between two arbitrary sets, right?
37:50 ok, this is epic
An epiclaritism
Good stuff.