# Semilattice Induces Ordering

Jump to navigation
Jump to search

## Theorem

Let $\left({S, \circ}\right)$ 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 \left({b \circ c}\right)\) | Since $b \preceq c$ | ||||||||||

\(\displaystyle \) | \(=\) | \(\displaystyle \left({a \circ b}\right) \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$