Semilattice Induces Ordering

From ProofWiki
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$