Monoids | Group theory episode 1

Подписаться 10 тыс.

Просмотров 9 тыс.

50% 1

#monoids #grouptheory #computerscience #abstractalgebra
What are monoids, why are they so abstract, and how do you calculate an empty product? In this video, we explain the exact purpose for each of the rules of monoids, with specific focus on the neutral element. We show many examples such as string concatenation and computer programs. And we already foreshadow the videos about group theory by looking at inverses.
Please support our channel on Patreon, and get early access to new videos: www.patreon.com/user?u=86649007
We only have a single link for you today, and it may look familiar:
[AA1] • What is a monoid? | #S...
This is the very first video we ever made, for the 2021 Summer of Math Exposition. It explains monoids by stacking books on top of each other, which is really just a fancy way of concatenating strings vertically instead of horizontally ;-)
0:00 Introduction
1:30 What is a monoid?
3:36 Example: blocks
4:58 Homomorphisms
6:30 Elements are active
7:42 Example: Computer programs
11:09 Associativity
12:36 Commutativity
13:51 Why these specific rules?
16:13 The neutral element
18:30 Abstraction = power
19:30 Inverses
This video is published under a CC Attribution license
( creativecommons.org/licenses/... )

Опубликовано:

1 июл 2024

Ссылка:

Скачать:

Готовим ссылку...

Добавить в:

Мой плейлист

Посмотреть позже

Комментарии : 79

@deltapi8859 Год назад

I wish all teaching material had this pace.

@Yeb3.22 3 месяца назад

Finally, someone who ACTUALLY explains group theory

@AllAnglesMath 3 месяца назад

Glad you like the video!

@jamiepond Месяц назад

Absolutely outstanding work. Please, for the goodness of all of us on this planet, keep it up.

@cdellio Год назад

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 11 месяцев назад

Thank you so much for your kind feedback. Really appreciate it!

@alegian7934 Год назад

I'm a computer science student, so I can't help but appreciate the "simple computer" example. So simple yet raises soooo many questions

@AllAnglesMath Год назад

I's often harder to find simple examples than convoluted ones. Glad you appreciate, thanks for the feedback!

@05degrees Год назад

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.

@AdrianBoyko 10 месяцев назад

The “simple computer” example is brilliant.

@AllAnglesMath 10 месяцев назад

@@AdrianBoyko Thank you!

@genecat Год назад

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.

@AllAnglesMath Год назад

Thank you so much for those kind words. Glad to be giving you a good math vibe.

@EricKolotyluk 2 месяца назад

The best explanation of Monads and Monoids I have ever seen. Way to go!

@deltapi8859 Год назад

that pause at 4:22 .. well done. You know what you are doing.

@AllAnglesMath Год назад

Thanks 🙂 It's always a balancing act between going too fast & too slow. It's good to know that it pays off.

@deltapi8859 Год назад

@@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.

@AllAnglesMath Год назад

@@deltapi8859 I don't know much about monads, so I can't really say if there is a connection or not.

@deltapi8859 Год назад

@@AllAnglesMath oh ok, interesting. I thought this was an introduction to monads in functional programming :D

@pra. Год назад

Very nice! I wish my abstract algebra class covered Monoids, the computer applications are especially cool

@chineduecheruo8872 6 месяцев назад

Best explanation of Monoids, ive heard! Thanks.

@lih3391 Год назад

Much appreciation for these videos. I never knew group theory was so beautiful and made so much sense!

@05degrees Год назад

Nice! You do monoids justice.

@beatboxanimationnandan 5 месяцев назад

Now I can digest group theory Great 🎉🎉

@SciStone Год назад

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.

@AllAnglesMath Год назад

Thanks! I hope we can deliver many more unexpected insights with our videos.

@pmmeurcatpics Год назад

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:(

@jaopredoramires Год назад

Now i finally understand why we think of Monoids/Monads when programming, thank you

@Hans_Magnusson 7 месяцев назад

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

@TehFingergunz 7 месяцев назад

Great job!

@TrollFunMineMafia Год назад

i can't wait for the video on groups, this series is gonna be so awesome, thank you so much :>

@kquat7899 Год назад

Excellent presentation. Concise and great clarity.

@StratosFair Год назад

This video is a wonderful introduction to abstract algebra. Subscribed and looking forward to what's coming next ;)

@alipourzand6499 26 дней назад

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

@AllAnglesMath 25 дней назад

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.

@alipourzand6499 25 дней назад

Ok, makes sense. The neutral element doesn't depend on the previous operation. Thanks for the explanation.

@swag_designs5470 9 месяцев назад

This was amazing

@christosgeorgiadis7462 7 месяцев назад

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.

@AllAnglesMath 7 месяцев назад

Thank you for your kind words. The more traditional explanations of group theory just start with lots of definitions, without explaining the "why".

@SupraManiam 3 месяца назад

@@AllAnglesMath So true and you're indeed a gem with great clarity and in depth explainations

@sleepysnekk Год назад

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

@AllAnglesMath Год назад

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.

@AdrianBoyko 10 месяцев назад

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”?

@AllAnglesMath 10 месяцев назад

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!

@AdrianBoyko 10 месяцев назад

@@AllAnglesMath Fair enough! (:

@Hans_Magnusson 7 месяцев назад

I say you are using a binary operatior to an empty list ie the identity and the value

@georgelaing2578 Год назад

Another wonderful presentation!

@146fallon9 Год назад

very informative video. thank you very much for uploading.❤

@HatimCyclewala 8 месяцев назад

Love your explanations ❤

@AllAnglesMath 7 месяцев назад

Thanks!

@korigamik 2 месяца назад

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?

@AllAnglesMath 2 месяца назад

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.

@visualgebra Год назад

Love from India 🇮🇳

@AllAnglesMath Год назад

Thanks! Hope you enjoy the video.

@angeldude101 11 месяцев назад

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.

@AllAnglesMath 11 месяцев назад

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.

@markusm2538 Год назад

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.

@AllAnglesMath Год назад

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.

@markusm2538 Год назад

@@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?

@AllAnglesMath Год назад

@@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.

@angeldude101 11 месяцев назад

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.

@Weeksmistro 11 месяцев назад

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.

@Hans_Magnusson 7 месяцев назад

11:03 NOP in assembly language, does exactly nothing (except for taking time to execute)…!

@Skiddla Год назад

is there an inverse of multiplying by 0? how is that categorized ?

@AllAnglesMath Год назад

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

@arslanrozyjumayev8484 8 месяцев назад

Can't get to see all ofthe vids

@AllAnglesMath 8 месяцев назад

You can find all videos in the playlists. Which ones can't you see?

@mattetis 7 месяцев назад

Jjl

@AdrianBoyko 10 месяцев назад

7:55 Slava Ukraïni 🇺🇦

@AllAnglesMath 10 месяцев назад

You're the first to notice.

@AdrianBoyko 10 месяцев назад

@@AllAnglesMath Thank you for your subtle support! I’m sure that many others have also noticed.

@annaclarafenyo8185 Год назад

This is not a good introduction. The first monoid must always by "strings of letters under concatenation", everything else is too special.

@declandougan7243 Год назад

?????????????????????????

@Hans_Magnusson 7 месяцев назад

Can you elaborate on the details please

@annaclarafenyo8185 7 месяцев назад

@@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).