Abstract Nonsense

Crushing one theorem at a time

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

Advertisements

March 25, 2011 - Posted by | Algebra, Group Theory | , , , ,

No comments yet.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: