I too agree this example is well-tailored, not too simple and not too complex, and illustrates both non-invertibility and non-commutativity, and also it’s a glimpse into the world of effects.
I can't believe your videos haven't garnered more attention. The animation is simple and concise -- as it should be. Your explanation style is likewise, and exemplary. Keep it up, please.
@@AllAnglesMath The mini computer example is just out of this world. Well done. That's a clear connection to "computational theory". However what I found interesting was the part where you "mapped" the strings to the length of a string and named the function class of the mapping arrows. That is something that is of interest for monads isn't it? Being able to map the elements is a type of function class which is relevant for monads as I remember, which build it's own structure. I maybe would have liked a bit of content regarding that relationship.
I am nearly retired now and your explanations bring me back to a time when I first recognized something tantalizing about mathematics. I've always had the appetite to go deeper but was never exposed to this kind of lucidity that makes it so natural and satisfying, had I been, I'm pretty sure it would have changed many of the choices I made. Powerful stuff here.
This is quite frankly the best video and explanation on Monoids I have seen on the Internet. It has finally helped me understand this concept and link it to related mathematical fields, like vector spaces. I would really like to see a video explaining Monads, since they have always been a mistery to me, but I suspect they are very closely related and maybe one of the examples in this video was also a monad in addition to being a monoid? Thanks!
This is amazing content! Your channel really deserves to grow based on the quality of this video alone. I thought I finally understood what a monoid is (after pursuing the meaning of a monad from functional programming). I understood them to be flat list-like things where the associativity of their constructing/joining binary operation ensured the container object would have the nice properties of being "chunkable" to utilize fan-out-in parallel optimizations on the underlying elements (as compared to something with a nested or tree-like structure where it's no longer trivial to split the whole object and transform the smaller chunks). But the comparison to n-ary operations and how the existence of an identity element, and associativity allows the thing to span from nullary to as many parameters as you want was really eye opening! (I wonder what would be the case for an infinite arity for the operation? I guess that would require an extra property on the monoid to be closed under infinite series, aka having the limit of infinite arity operations still being similar Cauchy completeness. Maybe that steps over into analysis from algebra.)
Thank you so much for those encouraging words. The link to parallel optimizations is really fascinating, I hadn't looked at it that way before. Thanks for sharing!
man i love your content, great work! The programming examples for the neutral element of multiplication blew my mind a little, didnt really think about that before.
15:14 operating on one input, I argue that you actually have two inputs, the value and the identity. eg an empty set that you add your value to, an empty string that you concatenate with another string etc
Thank you for this video ! I was curious to exactly what groups and such where and I had no clue where to look, so I just looked it up on wikipedia but wikipedia is of course not a good place for learning. Your video was simple yet very clear
The next few videos will dive into groups specifically. Wikipedia is an excellent reference, but not a good "tutorial". It assumes that the reader already has a lot of background. I'm glad to offer an alternative with a lower threshold.
Around 7:00, what do you mean the triangles are not part of the monoid, but the natural numbers are? The two arrows rotating the triangle by 90° are the same element of the monoid as the triangle between them. The triangle at the end is the result of having transformed the original element by 90° twice, which is the same as rotating the middle triangle by 90°, which is the same as rotating the initial triangle 180°. Similarly, numbers are objects that can be added as a monoid, but the number 1 just as much represents the action of sliding the number line over by 1. Every element of a monoid can be described either as the object that results from applying the action to the identity element, or as the action that brings the identity element to the object. Another video called this "object-action duality," a term which I quite like. Similarly, for the small program, there is a 1-1 mapping between possible (equivalent) programs, and output states, so the entire program can be described entirely in terms of the output state. Just like how a sequence of addition can be described by where 0 ends up, or the sequence of rotations can be described by the final orientation of the triangle.
Is there a rule about the commutativity of the identity element ("1")? Specifically, does it matter whether you do 1*x or x*1 (where x is an element of the monoid and * is the binary operation)? At 18:47, it says that one can prove that the identity element is unique. Does the proof assume commutativity of the identity element? Or can it be proven that the identity element is unique even when 1*x != x*1?
There's a puzzling fragment at 10:00 proofing the closure property of colored cells monoid. Correct if my reasoning is wrong. Quote :"Every possible sequence of instructions must become an element of the set. We end up with infinite set containing programs of arbitrary length." But why would we keep the whole sequence of "and then" as an element if the juice is in reducing a result of the operation to something that's already in the set of elements. E.g. "rotate 90 + rotate 90 reduces to rotate 180". We need 81 (3^4) elements total in the format [cell1 color, cell2 color, cell3 color, cell4 color], where "color" can be "blue", "yellow" or "nothing" (e.g. nothing,blue,nothing,yellow), to reduce any sequence. Regarding this course, it feels like the author rediscovers and reinvents math from scratch. What seemed fundamental and carved in stone now looks more like a kit for fun.
This is very good remark. It all depends on what you're trying to model. If we're only interested in the final result (= the colors of the memory cells), then you might indeed consider many programs to be "the same". But here, I am interested in the programs themselves, and I treat them the same way as I treat the concatenation of strings/blocks. So each program is unique, regardless of its final effect on the memory cells.
@@AllAnglesMath One more observation. This "and then" operation formally looks binary, but it disregards the first operand and just sets the value of second. I.e no matter how many elements there are in a "program" only the last one defines the result. In general, if the operation is unary, does the whole object still count as Monoid?
@@markusm2538 The "and then" operation is definitely binary. It takes two programs and connects them into a single one. You have to think about the programs, not their effects on the memory cells.
The operation does depend on the previous state of the memory cells, just not the _entire_ state. (nothing,blue,nothing,yellow) ; make 2 yellow = (nothing,nothing,nothing,yellow) ; make 2 yellow ≠ (blue,blue,nothing,yellow) ; make 2 yellow. This is actually exactly why the operations don't have inverses, because knowing the output state and the prior action, there are 3 possible states that could've been there before. Also, there an idea of "object-action-duality." If you really cared about every step rather than just the output, then the program can just as easily be described by a list of states of the memory after each instruction. If we only cared about the output state, then technically there are at most 4! possible minimal programs that could've resulted in it, though given that give the same output, you could call them all equivalent. Since those 4! possible minimal programs are just different permutations of what are at that point commutative operations, you can commute them into a canonical ordering, giving a single program for every possible output state.
Hi @AllAnglesMath. I think the confusion is that you said the following about your Computer Monoid when determining that an inverse does not exist for it 20:48 “…if you paint the second cell group blue (then) you no longer know whether that cell was originally yellow or blue.” This statement (unintentionally) implies that the Computer Monoid’s elements are the combination of states of the four cells and not the actual programs and their concatenations. In fact, the way that you described your Computer Monoid elements at 10:10 seems ‘trivially’ homomorphic to string catenation where the ‘;’ operator just creates a string that is of equal length or longer: [assuming that we don’t display the ‘;’ and ‘nothing’ words in our concatenation] ‘Make 1 blue’ ; ‘Make 1 yellow’ becomes ‘Make 1 blue Make 1 yellow’ And thus you can use that fact to show that there are no inverses.
This is incredible content… thanks for putting it together! However, I’m somewhat troubled by the suggestion that the binary operator can be used with 0 or 1 arguments. Consider the 0-arg case: If you are “folding” the binary addition operation on an empty list, how many times do you actually invoke that binary operation? Zero times. I would assert that NOT invoking a binary operation is fundamentally different than invoking a binary operation on two NEUTRAL elements. The 1-arg case is similar. Again, it does not require invocation of the binary operation which is fundamentally different than invoking the binary operation against the one arg and a neutral element. Instead of saying “a monoid’s characteristics allow its binary op to be invoked on 0, 1, 2, or more args” wouldn’t it be better to say “the characteristics of a monoid make it possible to define ‘fold’, which can be invoked against an arbitrary number of elements”?
That might be a formally more correct way of putting it. Right know, I'm mostly concerned with providing strong intuition, not formal correctness. But I do like the depth of your analysis!
Man I loved this series! Can you share the source code for the animations that you use in these videos? What tools do you use to create the slides and add the voice over?
We're using a custom rendering library written in Python. It uses OpenCV to produce the video. I record the audio using audacity and then synchronize it in the code. Then ffmpeg combines the two streams, and the final video is ready.
Regarding the uniqueness of the neutral element in your example, what is the difference between: make 1 blue ; do_nothing And make 1 blue ; make 1 blue
Good question. The 2 programs in your example have the same effect in the end, but they do very different things. In the second program, the second "make 1 blue" is not a neutral element. Just apply it to a situation where cell 1 is yellow, and you will see that "make 1 blue" has a very clear effect. The reason it *seems* like a neutral element is just because cell 1 *happens* to be blue.
In the most commonly used number systems, zero does not have an inverse. A few possible remedies are hinted at on the wikipedia page: en.wikipedia.org/wiki/Division_by_zero
I didn't understand the proof that the set contains only one neutral element. I think you didn't explain this well. Why does the neutral element get this mini-commutativity, where the operation results in the same output if the neutral element is either input? Because associativity ore closedness doesn't prove it, it's not a result of the definition of the monoid like you said, unless you also put that property into the definition of what a neutral element is.
This is a really good observation. I found this short explanation online: planetmath.org/LeftIdentityAndRightIdentity Basically, a left or right identity isn't necessarily unique. But as soon as you have both, they are the same and "they" are unique.
@@Hans_Magnusson The problem with abstract algebra is that students lack examples in their head. They can understand the theorems and the proofs, but the ideas will not internalize without canonical examples of each algebraic object. The canonical example of a group is permutations of a set, every other group embeds in some permutation group. The canonical example of a "monoid" is "finite sequences of alphabetical letters". Given two such sequences, you can put them end to end, one way, or the other, so that "abx" "mellow" can be "mellowabx" or "abxmellow". The multiplication operation is just sticking the two objects end to end. This is "the most general monoid", in that, up to an equivalence relation, you can homomorph any other monoid into finite strings (you might need an uncountable alphabet).
Finally, someone who ACTUALLY explains group theory
Glad you like the video!
Best explanation of Monoids, ive heard! Thanks.
I wish all teaching material had this pace.
wow, single best explanation of monoids i've ever seen in under 3 minutes. thank you.
wow, the simplicity and understanding you conveyed was impressive. I finally feel traction in my learning journey through abstract algebra.
I'm a computer science student, so I can't help but appreciate the "simple computer" example. So simple yet raises soooo many questions
I's often harder to find simple examples than convoluted ones. Glad you appreciate, thanks for the feedback!
I too agree this example is well-tailored, not too simple and not too complex, and illustrates both non-invertibility and non-commutativity, and also it’s a glimpse into the world of effects.
The “simple computer” example is brilliant.
@@AdrianBoyko Thank you!
I can't believe your videos haven't garnered more attention. The animation is simple and concise -- as it should be. Your explanation style is likewise, and exemplary. Keep it up, please.
Thank you so much for your kind feedback. Really appreciate it!
that pause at 4:22 .. well done. You know what you are doing.
Thanks 🙂 It's always a balancing act between going too fast & too slow. It's good to know that it pays off.
@@AllAnglesMath The mini computer example is just out of this world. Well done. That's a clear connection to "computational theory". However what I found interesting was the part where you "mapped" the strings to the length of a string and named the function class of the mapping arrows. That is something that is of interest for monads isn't it? Being able to map the elements is a type of function class which is relevant for monads as I remember, which build it's own structure. I maybe would have liked a bit of content regarding that relationship.
@@deltapi8859 I don't know much about monads, so I can't really say if there is a connection or not.
@@AllAnglesMath oh ok, interesting. I thought this was an introduction to monads in functional programming :D
I am nearly retired now and your explanations bring me back to a time when I first recognized something tantalizing about mathematics. I've always had the appetite to go deeper but was never exposed to this kind of lucidity that makes it so natural and satisfying, had I been, I'm pretty sure it would have changed many of the choices I made. Powerful stuff here.
Thank you so much for those kind words. Glad to be giving you a good math vibe.
Absolutely outstanding work. Please, for the goodness of all of us on this planet, keep it up.
The best explanation of Monads and Monoids I have ever seen. Way to go!
Much appreciation for these videos. I never knew group theory was so beautiful and made so much sense!
This is quite frankly the best video and explanation on Monoids I have seen on the Internet. It has finally helped me understand this concept and link it to related mathematical fields, like vector spaces. I would really like to see a video explaining Monads, since they have always been a mistery to me, but I suspect they are very closely related and maybe one of the examples in this video was also a monad in addition to being a monoid? Thanks!
Thanks for the very nice comment!
Unfortunately, monads are not on our planning.
Very nice! I wish my abstract algebra class covered Monoids, the computer applications are especially cool
Great job!
i can't wait for the video on groups, this series is gonna be so awesome, thank you so much :>
Your channel is badass, this is amazing!
This is amazing content! Your channel really deserves to grow based on the quality of this video alone. I thought I finally understood what a monoid is (after pursuing the meaning of a monad from functional programming).
I understood them to be flat list-like things where the associativity of their constructing/joining binary operation ensured the container object would have the nice properties of being "chunkable" to utilize fan-out-in parallel optimizations on the underlying elements (as compared to something with a nested or tree-like structure where it's no longer trivial to split the whole object and transform the smaller chunks). But the comparison to n-ary operations and how the existence of an identity element, and associativity allows the thing to span from nullary to as many parameters as you want was really eye opening!
(I wonder what would be the case for an infinite arity for the operation? I guess that would require an extra property on the monoid to be closed under infinite series, aka having the limit of infinite arity operations still being similar Cauchy completeness. Maybe that steps over into analysis from algebra.)
Thank you so much for those encouraging words. The link to parallel optimizations is really fascinating, I hadn't looked at it that way before. Thanks for sharing!
This video is a wonderful introduction to abstract algebra. Subscribed and looking forward to what's coming next ;)
Nice! You do monoids justice.
Great work, thank you!
I've watched many an exposition of group theory and have never come across such a clear way of motivating the subject.
Thank you for your kind words. The more traditional explanations of group theory just start with lots of definitions, without explaining the "why".
@@AllAnglesMath So true and you're indeed a gem with great clarity and in depth explainations
Excellent presentation. Concise and great clarity.
man i love your content, great work! The programming examples for the neutral element of multiplication blew my mind a little, didnt really think about that before.
Thanks! I hope we can deliver many more unexpected insights with our videos.
You've got me so hyped up for the future videos! Really wish I could see them earlier but oh well, I am but a poor student for now:(
Another wonderful presentation!
15:14 operating on one input, I argue that you actually have two inputs, the value and the identity.
eg an empty set that you add your value to, an empty string that you concatenate with another string etc
Thank you for this video !
I was curious to exactly what groups and such where and I had no clue where to look, so I just looked it up on wikipedia but wikipedia is of course not a good place for learning. Your video was simple yet very clear
The next few videos will dive into groups specifically.
Wikipedia is an excellent reference, but not a good "tutorial". It assumes that the reader already has a lot of background. I'm glad to offer an alternative with a lower threshold.
Around 7:00, what do you mean the triangles are not part of the monoid, but the natural numbers are? The two arrows rotating the triangle by 90° are the same element of the monoid as the triangle between them. The triangle at the end is the result of having transformed the original element by 90° twice, which is the same as rotating the middle triangle by 90°, which is the same as rotating the initial triangle 180°. Similarly, numbers are objects that can be added as a monoid, but the number 1 just as much represents the action of sliding the number line over by 1. Every element of a monoid can be described either as the object that results from applying the action to the identity element, or as the action that brings the identity element to the object. Another video called this "object-action duality," a term which I quite like.
Similarly, for the small program, there is a 1-1 mapping between possible (equivalent) programs, and output states, so the entire program can be described entirely in terms of the output state. Just like how a sequence of addition can be described by where 0 ends up, or the sequence of rotations can be described by the final orientation of the triangle.
Thanks for the in-depth feedback. I really like this idea of object-action duality; I'm going to have to think about it more deeply.
Now i finally understand why we think of Monoids/Monads when programming, thank you
Love your explanations ❤
Thanks!
Is there a rule about the commutativity of the identity element ("1")? Specifically, does it matter whether you do 1*x or x*1 (where x is an element of the monoid and * is the binary operation)? At 18:47, it says that one can prove that the identity element is unique. Does the proof assume commutativity of the identity element? Or can it be proven that the identity element is unique even when 1*x != x*1?
By definition, the identity element must work on the left and on the right. If it doesn't, it's not a valid identity element.
very informative video. thank you very much for uploading.❤
This was amazing
Now I can digest group theory
Great 🎉🎉
There's a puzzling fragment at 10:00 proofing the closure property of colored cells monoid. Correct if my reasoning is wrong. Quote :"Every possible sequence of instructions must become an element of the set. We end up with infinite set containing programs of arbitrary length." But why would we keep the whole sequence of "and then" as an element if the juice is in reducing a result of the operation to something that's already in the set of elements. E.g. "rotate 90 + rotate 90 reduces to rotate 180". We need 81 (3^4) elements total in the format [cell1 color, cell2 color, cell3 color, cell4 color], where "color" can be "blue", "yellow" or "nothing" (e.g. nothing,blue,nothing,yellow), to reduce any sequence.
Regarding this course, it feels like the author rediscovers and reinvents math from scratch. What seemed fundamental and carved in stone now looks more like a kit for fun.
This is very good remark. It all depends on what you're trying to model. If we're only interested in the final result (= the colors of the memory cells), then you might indeed consider many programs to be "the same". But here, I am interested in the programs themselves, and I treat them the same way as I treat the concatenation of strings/blocks. So each program is unique, regardless of its final effect on the memory cells.
@@AllAnglesMath One more observation. This "and then" operation formally looks binary, but it disregards the first operand and just sets the value of second. I.e no matter how many elements there are in a "program" only the last one defines the result. In general, if the operation is unary, does the whole object still count as Monoid?
@@markusm2538 The "and then" operation is definitely binary. It takes two programs and connects them into a single one. You have to think about the programs, not their effects on the memory cells.
The operation does depend on the previous state of the memory cells, just not the _entire_ state. (nothing,blue,nothing,yellow) ; make 2 yellow = (nothing,nothing,nothing,yellow) ; make 2 yellow ≠ (blue,blue,nothing,yellow) ; make 2 yellow. This is actually exactly why the operations don't have inverses, because knowing the output state and the prior action, there are 3 possible states that could've been there before.
Also, there an idea of "object-action-duality." If you really cared about every step rather than just the output, then the program can just as easily be described by a list of states of the memory after each instruction. If we only cared about the output state, then technically there are at most 4! possible minimal programs that could've resulted in it, though given that give the same output, you could call them all equivalent. Since those 4! possible minimal programs are just different permutations of what are at that point commutative operations, you can commute them into a canonical ordering, giving a single program for every possible output state.
Hi @AllAnglesMath. I think the confusion is that you said the following about your Computer Monoid when determining that an inverse does not exist for it 20:48
“…if you paint the second cell group blue (then) you no longer know whether that cell was originally yellow or blue.”
This statement (unintentionally) implies that the Computer Monoid’s elements are the combination of states of the four cells and not the actual programs and their concatenations.
In fact, the way that you described your Computer Monoid elements at 10:10 seems ‘trivially’ homomorphic to string catenation where the ‘;’ operator just creates a string that is of equal length or longer:
[assuming that we don’t display the ‘;’ and ‘nothing’ words in our concatenation]
‘Make 1 blue’ ; ‘Make 1 yellow’ becomes ‘Make 1 blue Make 1 yellow’
And thus you can use that fact to show that there are no inverses.
This is incredible content… thanks for putting it together! However, I’m somewhat troubled by the suggestion that the binary operator can be used with 0 or 1 arguments.
Consider the 0-arg case: If you are “folding” the binary addition operation on an empty list, how many times do you actually invoke that binary operation? Zero times. I would assert that NOT invoking a binary operation is fundamentally different than invoking a binary operation on two NEUTRAL elements.
The 1-arg case is similar. Again, it does not require invocation of the binary operation which is fundamentally different than invoking the binary operation against the one arg and a neutral element.
Instead of saying “a monoid’s characteristics allow its binary op to be invoked on 0, 1, 2, or more args” wouldn’t it be better to say “the characteristics of a monoid make it possible to define ‘fold’, which can be invoked against an arbitrary number of elements”?
That might be a formally more correct way of putting it. Right know, I'm mostly concerned with providing strong intuition, not formal correctness. But I do like the depth of your analysis!
@@AllAnglesMath Fair enough! (:
I say you are using a binary operatior to an empty list ie the identity and the value
Man I loved this series! Can you share the source code for the animations that you use in these videos? What tools do you use to create the slides and add the voice over?
We're using a custom rendering library written in Python. It uses OpenCV to produce the video. I record the audio using audacity and then synchronize it in the code. Then ffmpeg combines the two streams, and the final video is ready.
Id love to see some category theory after introducing monoids
Regarding the uniqueness of the neutral element in your example, what is the difference between:
make 1 blue ; do_nothing
And
make 1 blue ; make 1 blue
Good question. The 2 programs in your example have the same effect in the end, but they do very different things.
In the second program, the second "make 1 blue" is not a neutral element. Just apply it to a situation where cell 1 is yellow, and you will see that "make 1 blue" has a very clear effect.
The reason it *seems* like a neutral element is just because cell 1 *happens* to be blue.
Ok, makes sense. The neutral element doesn't depend on the previous operation. Thanks for the explanation.
is there an inverse of multiplying by 0? how is that categorized ?
In the most commonly used number systems, zero does not have an inverse. A few possible remedies are hinted at on the wikipedia page: en.wikipedia.org/wiki/Division_by_zero
Thank you!
cool video
Love from India 🇮🇳
Thanks! Hope you enjoy the video.
11:03 NOP in assembly language, does exactly nothing (except for taking time to execute)…!
Can't get to see all ofthe vids
You can find all videos in the playlists. Which ones can't you see?
I didn't understand the proof that the set contains only one neutral element. I think you didn't explain this well.
Why does the neutral element get this mini-commutativity, where the operation results in the same output if the neutral element is either input? Because associativity ore closedness doesn't prove it, it's not a result of the definition of the monoid like you said, unless you also put that property into the definition of what a neutral element is.
This is a really good observation. I found this short explanation online: planetmath.org/LeftIdentityAndRightIdentity
Basically, a left or right identity isn't necessarily unique. But as soon as you have both, they are the same and "they" are unique.
7:55 Slava Ukraïni 🇺🇦
You're the first to notice.
@@AllAnglesMath Thank you for your subtle support! I’m sure that many others have also noticed.
Jjl
This is not a good introduction. The first monoid must always by "strings of letters under concatenation", everything else is too special.
?????????????????????????
Can you elaborate on the details please
@@Hans_Magnusson The problem with abstract algebra is that students lack examples in their head. They can understand the theorems and the proofs, but the ideas will not internalize without canonical examples of each algebraic object. The canonical example of a group is permutations of a set, every other group embeds in some permutation group. The canonical example of a "monoid" is "finite sequences of alphabetical letters". Given two such sequences, you can put them end to end, one way, or the other, so that "abx" "mellow" can be "mellowabx" or "abxmellow". The multiplication operation is just sticking the two objects end to end. This is "the most general monoid", in that, up to an equivalence relation, you can homomorph any other monoid into finite strings (you might need an uncountable alphabet).
im confused, but only by why i would get an ad for math tutoring on a math video about group theory... target audience was missed on that one
I keep getting ads for cat food, even though we don't have pets 🤔