Answer to Question #275069 in Discrete Mathematics for Devas

Question

Define Semigroup and Monoid. Show that the set of positive Integer is a monoid for the operation

defined by aOb = max{ a,b}

Answer 1

A semigroup is a pair $(S,\circ),$ where $S$ is a non-empty set and $\circ:S\times S\to S$ is an associative binary operation on $S.$ A monoid is a semigroup $(S,\circ)$ with identity element $e\in S$ in the sence that $e\circ s=s\circ e=s$ for any $s\in S.$

Let us show that the set of positive Integer $\N$ is a monoid for the operation defined by $a\circ b = \max\{ a,b\}.$

If $a,b\in \N$ then $a\circ b = \max\{ a,b\}\in\N,$ and hence the operation is defined on the set $\N.$

Since

$a\circ(b\circ c)=a\circ\max\{b, c\}=\max\{a,\max\{b, c\}\}=\max\{a,b, c\} \\=\max\{\max\{a,b\}, c\}=\max\{a\circ b, c\}=(a\circ b)\circ c$

for any $a,b,c\in\N,$ we conclude that operation $\circ$ is associative, and hence $(\N,\circ)$ is a semigroup.

Taking into account that $a\circ 1=\max\{a,1\}=a=\max\{1,a\}=1\circ a$ for each $a\in\N,$ we conclude that $1$ is the identity of the semigroup $(\N,\circ),$ and consequently $(\N,\circ)$ is a monoid.