# Semilattice Induces Ordering

Jump to navigation
Jump to search

## 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$

## Sources

- 1982: Peter T. Johnstone:
*Stone spaces*... (previous) ... (next): Chapter $\text I$: Preliminaries, Definition $1.3$