# Max Operation on Woset is Monoid

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$