## Interesting Example of a Monoid

**Point of post: **In this post we imbue the natural numbers with a non-usual binary operation in such a way that makes it into a very interesting monoid.

*Motivation*

Very often because of their generality one can create very exotic types of monoids. In this post we derive a very interesting one involving the ‘extended’ natural numbers (to be defined below), namely the binary operation will be the greatest common divisor function. The most fascinating part (the fact of which was brought to my attention by my friend Pablo on his blog) is the fact that the mapping which sends each natural number to the element of the Fibonacci sequence is a monoid endomorphism.

*Preliminaries*

A set along with an associative binary operation is called a *semigroup***. **As with all algebraic structures we omit writing in lieu of concatenation. Our first result is that there is a natural way one can extend a semigroup to make it into a monoid–we call this the *natural completion of the semigroup*. Indeed:

**Theorem: ***Let be a semigroup then if is defined to be the set (where is a formal symbol–compare to Alexandroff Compactification) with the operation by for all and for every . Then, is a monoid.*

**Proof: **We first claim that is associative. But, since itself is associative it suffices to check that (where we’ve supressed in lieu of concatenation) for every where one of is equal to . But, this is clear. Indeed, if then this reduces, by definition to . If we see similarly that . Lastly, if then . Thus, has an associative binary operation, and since it has an identity element the conclusion follows.

** **

**Exotic Monoid**

We recall then from basic number theory the notion of the greatest common divisor*. *To review, for we define . We note then that is bounded since for every and so in particular is finite. With this in mind we define the *greatest common divisor function* to be the mapping by .

It is a trivial fact from basic number theory that the greatest common divisor function is associative and thus is a semigroup, and thus by our preliminary result we know that the completion of this semigroup, , is a monoid.

Recall the definition of the Fibonacci numbers, namely , and for . Note in particular that and for distinct one has that if . But, in the post I linked to above Pablo showed that from where we get the following very interesting result:

**Theorem: ***Let . Then, is a submonoid of , and moreover where denotes monoid isomorphism and denotes the quotient monoid obtained by identifying and and leaving all other elements of in equivalence classes of their own.*

**Proof:** Define by and for every . Then, since for all and the same is clearly true if either or is we have, by first principles and the first isomorphism theorem for monoids, that is a submonoid of isomorphic to . But, a quick check shows that and . The conclusion follows.

No comments yet.

## Leave a Reply