Upper Semilattice on Classical Set is Semilattice

Theorem

Let $\left({S, \vee}\right)$ be an upper semilattice on a classical set $S$.

Then $\left({S, \vee}\right)$ is a semilattice.

Proof

To show that the algebraic structure $\left({S, \vee}\right)$ 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 \left\{{x, y}\right\} \in S$

Since $x \vee y = \sup \left\{{x, y}\right\} \in S$ for all $x,y \in S$, $\left({S, \vee}\right)$ is closed.

$\Box$

Associativity

Letting $x,y,z \in S$, by definition of $\vee$ it follows that:

	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \left({x \vee y}\right) \vee z\)	\(=\)	\(\displaystyle \sup \left\{ {x, y}\right\} \vee z\)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)
	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(=\)	\(\displaystyle \sup \left\{ {\sup \left\{ {x, y}\right\}, z}\right\}\)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)
	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(=\)	\(\displaystyle \sup \left\{ {x, y, z}\right\}\)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)
	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(=\)	\(\displaystyle \sup \left\{ {x, \sup \left\{ {y, z}\right\} }\right\}\)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)
	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(=\)	\(\displaystyle x \vee \sup \left\{ {y, z}\right\}\)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)
	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(=\)	\(\displaystyle x \vee \left({y \vee z}\right)\)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)

Hence $\left({S, \vee}\right)$ is associative.

$\Box$

Commutativity

Let $x,y \in S$. Then by definition of $\vee$:

	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle x \vee y\)	\(=\)	\(\displaystyle \sup \left\{ {x, y}\right\}\)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)
	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(=\)	\(\displaystyle \sup \left\{ {y, x}\right\}\)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	Definition of supremum
	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(=\)	\(\displaystyle y \vee x\)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)

Hence $\left({S, \vee}\right)$ is commutative.

$\Box$

Idempotence

Lastly, for all $x \in S$:

	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle x \vee x\)	\(=\)	\(\displaystyle \sup \left\{ {x, x}\right\}\)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)
	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(=\)	\(\displaystyle x\)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)

Hence $\vee$ is idempotent.

$\Box$

Having explicitly verified all prerequisites, it follows that $\left({S, \vee}\right)$ is a semilattice.

$\blacksquare$

Sources

• Stanford handout on Lattice theory
• Stanley Burris and H. P. Sankappanavar: A Course in Universal Algebra (1981): $\text {II} \ \S 1$ Example $(7)$