Total Semilattice has Unique Total Ordering

From ProofWiki
Jump to navigation Jump to search

Theorem

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


There exists a unique total ordering $\preccurlyeq$ on $S$ such that:

$x \vee y = \max \set {x, y}$

where:

$\max \set {x, y} := \begin {cases} b & : a \preccurlyeq b \\ a & : b \preccurlyeq a \end {cases}$


Proof

Recall the definition of total semilattice:

A total semilattice $\struct {S, \odot}$ is a semilattice which has the property that every subset of $\struct {S, \odot}$ is a subsemilattice.

That is, such that every subset of $\struct {S, \odot}$ is closed under $\odot$.


Let us define a relation $\RR$ on $S$ as:

$\forall x, y \in S: x \mathrel \RR y \iff x \vee y = y$

It is to be shown that $\RR$ is a total ordering.


From Semilattice Induces Ordering, we have that $\RR$ is an ordering.

$\Box$


Connectedness

Let $a, b \in S$ be arbitrary such that $a \ne b$.

We have by hypothesis that:

$\forall x, y \in \set {a, b}: x \vee y \in \set {a, b}$

That is, either:

$a \vee b = a$

or:

$a \vee b = b$

Hence, by definition of $\RR$, either:

$a \mathrel \RR b$

or:

$b \mathrel \RR a$

That is, $\RR$ is a connected relation.


Summarising:

$\RR$ is an ordering

and

$\RR$ is connected.

Hence by definition $\RR$ is a total ordering.


Let us denote this total ordering by $\preccurlyeq$.


We have:

\(\ds x \vee y\) \(=\) \(\ds y\)
\(\ds \leadsto \ \ \) \(\ds x\) \(\preccurlyeq\) \(\ds y\)

and:

\(\ds x \vee y\) \(=\) \(\ds x\)
\(\ds \leadsto \ \ \) \(\ds y\) \(\preccurlyeq\) \(\ds x\)

Hence by definition:

$x \vee y = \max \set {x, y}$

$\Box$


Uniqueness

It remains to be proved that the total ordering $\preccurlyeq$, with the property that:

$x \vee y = \max \set {x, y}_\preccurlyeq$

is unique.


Indeed, suppose there exists another total ordering $\preccurlyeq'$ such that:

$x \vee y = \max \set {x, y}_{\preccurlyeq'}$

We have:

\(\ds \max \set {x, y}_{\preccurlyeq'}\) \(=\) \(\ds x \vee y\)
\(\ds \) \(=\) \(\ds \max \set {x, y}_\preccurlyeq\) as $x \vee y$ is uniquely defined

The proof is complete.

$\blacksquare$


Sources

Retrieved from "https://proofwiki.org/w/index.php?title=Total_Semilattice_has_Unique_Total_Ordering&oldid=567548"