# Semilattice Induces Ordering

## Theorem

Let $\struct {S, \circ}$ be a semilattice.

Let $\preceq$ be the relation on $S$ defined by, for all $a, b \in S$:

$a \preceq b$ if and only if $a \circ b = b$

Then $\preceq$ is an ordering.

## Proof

Let us verify that $\preceq$ satisfies the three conditions for an ordering.

### Reflexivity

Since $\circ$ is idempotent, for all $a \in S$:

$a \circ a = a$

hence $a \preceq a$.

Thus $\preceq$ is reflexive.

$\Box$

### Antisymmetry

Suppose that $a \preceq b$ and $b \preceq a$.

Then from the first relation:

$a \circ b = b$

and from the second:

$b \circ a = a$

Since $\circ$ is commutative, it follows that $a = b$.

Hence $\preceq$ is antisymmetric.

$\Box$

### Transitivity

Suppose that $a \preceq b$ and $b \preceq c$.

Then:

 $\displaystyle a \circ c$ $=$ $\displaystyle a \circ \paren {b \circ c}$ Since $b \preceq c$ $\displaystyle$ $=$ $\displaystyle \paren {a \circ b} \circ c$ $\circ$ is associative $\displaystyle$ $=$ $\displaystyle b \circ c$ Since $a \preceq b$ $\displaystyle$ $=$ $\displaystyle c$ Since $b \preceq c$

Hence, $a \preceq c$.

Thus $\preceq$ is transitive.

$\Box$

Having verified all three conditions, it follows that $\preceq$ is an ordering.

$\blacksquare$