Category Theory II 3.2: Free Monoids

[@sodadinsight9495]

Hello, thanks for your video courses and for you blog on categories. rt the example of (N,+) as a monoid (at the beginning of the video, where it is noted that (1,2) and (2,1) are mapped by the addition to the same element and so on), isn't (N,+) indeed a free monoid with two generators, [] and [1], and 2 being a shortcut for [1, 1], 3 a shortcut for [1,1,1], ... and the addition obviously being equivalent to (++) ? if so, may be (N, x) would have been a preferable example of a monoid in general ... Bests, Thierry Delbecque.

[@BartoszMilewski]

Good point. Also addition modulo would be a good example.

[@burnytech]

25:05 If p embeds set of all possible generators into monoid and monoid is just all possible generators, does it mean x and Um is the same set, the same object, because they're the same size and all sets with the same size are isomorphic, so the functions that go from and to x also go from and to Um and vice versa?

[@burnytech]

they are not the same set, x is for example {a} and Um is {e,a,aa,aaa,...}

[@adamyin2537]

Based on that commutative triangle at the end, my speculation for the next video should be on adjunctions?

[@TheAmazingMooCow2]

Interesting! So starting with a generator set of some alphabet Σ we essentially get a set Um containing all possible strings Σ* from that alphabet?

[@adamyin2537]

Could U be used as the forgetful functor because of the word "Underlying" from underlying set?

[@jmgimeno]

Wolfram MathWordl supports your hypothesis (mathworld.wolfram.com/ForgetfulFunctor.html): Forgetful Functor A forgetful functor (also called underlying functor) is defined from a category of algebraic gadgets (groups, Abelian groups, modules, rings, vector spaces, etc.) to the category of sets. A forgetful functor leaves the objects and the arrows as they are, except for the fact they are finally considered only as sets and maps, regardless of their algebraic properties.

[@pexoto5093]

I guess i really could be used that way since i am very forgetful

[@tdgalappaththi]

Thanks for the very helpful video series. I have a question. Monoid is a category of a single object. But the generator set for a monoid can have many elements. How does these two things relates to each other? How does the generator set attributes to the single element of the Monoid? Does the function p and q discards elements from the generator set and leave a single element which becomes the only element in the Monoid ?

[@DrBartosz]

The only mapping between monoids and sets is the forgetful functor. There is no mapping from a set to a monoid (they live in different categories) so there is no direct relation between set elements and the monoid. But the whole idea of a category is that we trade information about elements for information about morphisms. So the fact that a set of generators has elements is cleverly encoded in morphisms that connect the monoid object to itself and to all other monoids in Mon. We extract this information using the universal construction.

[@tdgalappaththi]

Thanks for the quick response. I read your blog article related to this video : bartoszmilewski.com/2013/12/21/understanding-free-monoids-and-universal-constructions/ It makes sense now.

[@qseep]

When a monoid is represented as a category of a single object, the elements of the monoid are represented by the morphisms.

[@LiamC328]

How would you write down every monoid generated by one single letter?

[@MrRobot-pv6mo]

You can use Kleene star for that.

[@hujason4944]

not sure i got the end part. shouldn't p :: x -> m instead, i.e. being a functor? then it really makes p sound like a generator. otherwise why would we like to look into a function that turns one set into another, without providing specific structure?

[@DrBartosz]

We need a function because we want to talk about elements of sets. We are embedding elements of one set (the generators) into another set, U m. A functor, on the other hand, treats objects as atoms. If p were a functor it would map the whole set x to the whole monoid m without looking at its elements. And anyway, a monoid m has no structure. It's an opaque object. It has no elements. The only way to look at its "elements" is to look at the elements of the underlying set, which is U m.

[@hujason4944]

you are right. i keep thinking in terms of sets. i have to twist my mind to think in morphisms.

[@TheSidyoshi]

Why does h have to be unique? If the monoid m has no symmetries, and h can collapse different generators into n, then I can make h1, h2, h3 ... and so on, by just collapsing different generators together. Each of these would work equally well to satisfy the commutation condition, because you automatically get (U h) from the forgetful functor, and the composition (U h) . p will yield q. This works the same for h1, h2, h3. Since there are no symmetries in the monoids, it doesn't matter which generators you collapse. I've always struggled with the uniqueness condition of the universal construction. It's hard to intuitively understand what it's saying... I would guess: we want the minimal set of generators for the monoid, so we don't include the redundant elements like (a * b). But, how does the uniqueness constraint get you there? It seems sufficient that there is at least one h. If you have a set of generators S = {a, b, c}. I can define h1 as {a -> a, b -> a, c -> c}, and h2 as {a -> a, b -> c, c -> c}. The monoid structure is preserved in both cases. You still get (U h), and you still get q = (U h) . p. Assuming p maps x, one-to-one, into the set S, you have two different h. Just by the existence of h (one or more), why can't I just claim that S is our best candidate? Maybe, I'm missing some fundamental category theory magic... or I'm just plain wrong.

[@DrBartosz]

Notice that your h1 and h2 are functions, so they are already in Set. You are actually defining U h1 and U h2. If you compose them with p you'll get different qs.

[@TheSidyoshi]

Sorry, you're right. I defined (U h1), and (U h2). h1, and h2 would map the unit and the multiplication across. I knew you get different qs for different hs. After re-reading, I can see that I didn't get that across in my question (sorry). I didn't mean to say that they are the same q. Just a respective q for each h. Still... having different qs doesn't tell you anything about why S is not the best set of generators...? You still have two different h1 and h2, each with their respective (U h1) and (U h2), and q1 and q2. So then ... h doesn't have to be unique? I'm not trying to be a pain, I'm just trying to get at the heart of this uniqueness constraint. Also, since the unit (in the free monoid) is sort of like the empty list, it doesn't seem like it belongs in the set of generators... so I omitted it. Is this correct?

[@jmgimeno]

From what I understand, every universal construction works by defining a category in which objects are the patters and morphisms are the "better than" relation. The best pattern is then the initial (or terminal) object in this category. The uniqueness constraint, if I remember correctly, is needed to prove that the initial (terminal) object is unique upto isomorphism. If not, one could have two objects whiah are the "best ones" but that they're not isomorph between them.

[@ShimshonDI]

I'd have to also admit that I don't really understand how universal construction works in general. It seems like voodoo magic to me, very cool that it works, but I hope I eventually get a deeper understanding of why.

[@yokilewis4894]

From my understanding, it's the problem of what “same objects” means in a given category. Following your example, you will have two different h to get the n for the Un to be {a, c, aa, ac, cc, …}. But since the morphisms from m to n are different, they are different ns. So in the construction, you will have a unique morphism to each of them. Maybe you consider the two ns to be the same, because they all generate the same Un. But sameness of objects in a category is determined by the morphisms between them and other objects. You have two hs, so you have two ns. Their difference are noted not from themselves, but from we get to them with different ways. So they are not same, but same up to a morphism, even if the morphism acts very like id. That is: objects are mapped to the same objects, arrows are unchanged as well. The difference between the morphism and id is that it doesn't link the same object in the category of Mon. That's my best guess, it maybe wrong. I'm open to further discussion :)

[@jvranstify]

Best ever...

[@francescos7361]

Thanks .