# Abstract Nonsense

## 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 $S$ along with an associative binary operation $\mu:S\times S\to S$ is called a semigroup. As with all algebraic structures we omit writing $\mu$ 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 $\left(S,\mu\right)$ be a semigroup then if $S_\infty$ is defined to be the set $S\cup\{\infty\}$ (where $\infty$ is a formal symbol–compare to Alexandroff Compactification) with the operation $\mu_\infty:S_\infty\times S_\infty\to S_\infty$ by $\mu_\infty(x,y)=\mu(x,y)$ for all $x,y\in S$ and $\mu_\infty(x,\infty)=\mu_\infty(\infty,x)=x$ for every $x\in S_\infty$. Then, $\left(S_\infty,\mu_\infty\right)$ is a monoid.

Proof: We first claim that $\mu_\infty$ is associative. But, since $\mu$ itself is associative it suffices to check that $x(yz)=(xy)z$ (where we’ve supressed $\mu_\infty$ in lieu of concatenation) for every $x,y,z\in S_\infty$ where one of $x,y,z$ is equal to $\infty$. But, this is clear. Indeed, if $x=\infty$ then this reduces, by definition to $x(yz)=yz=(xy)z$. If $y=\infty$ we see similarly that $x(yz)=xz=(xy)z$. Lastly, if $z=\infty$ then $x(yz)=xy=(xy)z$. Thus, $S_\infty$ has an associative binary operation, and since it has an identity element the conclusion follows. $\blacksquare$

Exotic Monoid

We recall then from basic number theory the notion of the greatest common divisor. To review, for $a\in\mathbb{N}$ we define $D(a)=\left\{d\in\mathbb{N}:d\mid a\right\}$. We note then that $D(a)$ is bounded since $d\leqslant a$ for every $d\in D(a)$ and so in particular $D(a)$ is finite. With this in mind we define the greatest common divisor function to be the mapping $(\cdot,\cdot):\mathbb{N}\times\mathbb{N}\to\mathbb{N}$ by $(a,b)=\max\left(D(a)\cap D(b)\right)$.

It is a trivial fact from basic number theory that the greatest common divisor function is associative and thus $\left(\mathbb{N},(\cdot,\cdot)\right)$ is a semigroup, and thus by our preliminary result we know that the completion of this semigroup, $\mathbb{N}_\infty$, is a monoid.

Recall the definition of the Fibonacci numbers, namely $F_0=0$, $F_1=1$ and $F_{n+1}=F_n+F_{n-1}$ for $n\geqslant 1$. Note in particular that $F(1)=F(2)=1$ and for distinct $m,n$ one has that $F(n)\ne F(m)$ if $\{m,n\}\ne\{1,2\}$. But, in the post I linked to above Pablo showed that $\left(F(a),F(b)\right)=F\left((a,b)\right)$ from where we get the following very interesting result:

Theorem: Let $\mathcal{F}=\left\{F_n:n\in\mathbb{N}\right\}\cup\{\infty\}$. Then, $\mathcal{F}$ is a submonoid of $\mathbb{N}_\infty$, and moreover $\mathcal{F}\cong \mathbb{N}_{\infty}/\{1,2\}$ where $\cong$ denotes monoid isomorphism and $\mathbb{N}/\{1,2\}$ denotes the quotient monoid obtained by identifying $1$ and $2$ and leaving all other elements of $\mathbb{N}_\infty$ in equivalence classes of their own.

Proof: Define $F:\mathbb{N}_\infty\to\mathbb{N}_\infty$ by $F(\infty)=\infty$ and $F(n)=F_n$ for every $n\in\mathbb{N}$. Then, since $\left(F(a),F(b)\right)=F\left((a,b)\right)$ for all $a,b\in\mathbb{N}$ and the same is clearly true if either $a$ or $b$ is $\infty$ we have, by first principles and the first isomorphism theorem for monoids, that $\text{im}(F)$ is a submonoid of $\mathbb{N}_\infty$ isomorphic to $\mathbb{N}_\infty/\ker F$. But, a quick check shows that $\text{im}(F)=\mathcal{F}$ and $\ker F=\{1,2\}$. The conclusion follows. $\blacksquare$