Max Operation on Woset is Monoid

From ProofWiki
Jump to navigation Jump to search

Theorem

Let $\left({S, \preceq}\right)$ be a well-ordered set.

Let $\max \left({x, y}\right)$ denote the max operation on $x, y \in S$.


Then $\left({S, \max}\right)$ is a monoid.


Its identity element is the smallest element of $S$.


Proof

From Well-Ordering is Total Ordering, we have that $\left({S, \preceq}\right)$ is a totally ordered set.

Thus, by Max Operation on Toset is Semigroup, $\left({S, \max}\right)$ is a semigroup.


By definition, a well-ordered set has a smallest element.

So:

$\exists m \in S: \forall x \in S: m \preceq x$

where $m$ is that smallest element.

It follows by definition of the max operation that:

$\forall x \in S: \max \left({m, x}\right) = x$

Thus $m$ is the identity element of $\left({S, \max}\right)$.

Hence the result, by definition of monoid.

$\blacksquare$