Upper Semilattice on Classical Set is Semilattice

 It has been suggested that this page or section be merged into Join Semilattice is Semilattice. (Discuss)

Theorem

Let $\struct {S, \vee}$ be an upper semilattice on a classical set $S$.

Then $\struct {S, \vee}$ is a semilattice.

Proof

To show that the algebraic structure $\struct {S, \vee}$ is a semilattice, the following need to be verified:

Closure
Associativity
Commutativity
Idempotence

In order:

Closure

By definition of an upper semilattice:

$\forall x, y \in S: \sup \set {x, y} \in S$

Since $x \vee y = \sup \set {x, y} \in S$ for all $x, y \in S$:

$\struct {S, \vee}$ is closed.

$\Box$

Associativity

Let $x, y, z \in S$.

By definition of $\vee$:

 $\displaystyle \paren {x \vee y} \vee z$ $=$ $\displaystyle \sup \set {x, y} \vee z$ $\displaystyle$ $=$ $\displaystyle \sup \set {\sup \set {x, y}, z}$ $\displaystyle$ $=$ $\displaystyle \sup \set {x, y, z}$ $\displaystyle$ $=$ $\displaystyle \sup \set {x, \sup set {y, z} }$ $\displaystyle$ $=$ $\displaystyle x \vee \sup \set {y, z}$ $\displaystyle$ $=$ $\displaystyle x \vee \paren {y \vee z}$

Hence $\struct {S, \vee}$ is associative.

$\Box$

Commutativity

Let $x, y \in S$.

By definition of $\vee$:

 $\displaystyle x \vee y$ $=$ $\displaystyle \sup \set {x, y}$ $\displaystyle$ $=$ $\displaystyle \sup \set {y, x}$ Definition of Supremum of Set $\displaystyle$ $=$ $\displaystyle y \vee x$

Hence $\struct {S, \vee}$ is commutative.

$\Box$

Idempotence

For all $x \in S$:

 $\displaystyle x \vee x$ $=$ $\displaystyle \sup \set {x, x}$ $\displaystyle$ $=$ $\displaystyle x$

Hence $\vee$ is idempotent.

$\Box$

Having explicitly verified all prerequisites, it follows that $\struct {S, \vee}$ is a semilattice.

$\blacksquare$