Equivalence of Definitions of Lattice

From ProofWiki
Jump to navigation Jump to search

Theorem

The following definitions of the concept of Lattice are equivalent:

Definition 1

Let $\left({S, \preceq}\right)$ be an ordered set.

Suppose that $S$ admits all finite non-empty suprema and finite non-empty infima.

Denote with $\vee$ and $\wedge$ the join and meet operations on $S$, respectively.


Then the ordered structure $\left({S, \vee, \wedge, \preceq}\right)$ is called a lattice.

Definition 2

Let $\left({S, \vee, \wedge, \preceq}\right)$ be an ordered structure.


Then $\left({S, \vee, \wedge, \preceq}\right)$ is called a lattice iff:

$\left({S, \vee, \preceq}\right)$ is a join semilattice
$\left({S, \wedge, \preceq}\right)$ is a meet semilattice

Definition 3

Let $\left({S, \vee}\right)$ and $\left({S, \wedge}\right)$ be semilattices on a set $S$.

Suppose that $\vee$ and $\wedge$ satisfy the absorption laws, that is, for all $a, b \in S$:

$a \vee \left({a \wedge b}\right) = a$
$a \wedge \left({a \vee b}\right) = a$

Let $\preceq$ be the ordering on $S$ defined by:

$\forall a, b \in S: a \preceq b$ if and only if $a \vee b = b$

as on Semilattice Induces Ordering.


Then the ordered structure $\left({S, \vee, \wedge, \preceq}\right)$ is called a lattice.


Proof

1 implies 2

Let $\left({S, \vee, \wedge, \preceq}\right)$ adhere to Definition 1.

Then since all finite non-empty suprema exist, we have:

$a \vee b = \sup \left\{{a, b}\right\} \in S$

for all $a, b \in S$, where $\vee$ denotes join.

Hence $\left({S, \vee, \preceq}\right)$ is a join semilattice.


Similarly, since all finite non-empty infima exist, we have:

$a \wedge b = \inf \left\{{a, b}\right\} \in S$

for all $a, b \in S$, where $\wedge$ denotes meet.

Thus $\left({S, \wedge, \preceq}\right)$ is a meet semilattice.


In conclusion, $\left({S, \vee, \wedge, \preceq}\right)$ satisfies Definition 2.

$\Box$


2 implies 1

Let $\left({S, \vee, \wedge, \preceq}\right)$ adhere to Definition 2.

We will prove that:

$\left({S, \vee, \preceq}\right)$ is a join semilattice

implies that:

$\left({S, \preceq}\right)$ admits all finite non-empty suprema


From Supremum of Singleton, $\left({S, \preceq}\right)$ admits suprema of singletons.

By definition of join, it also admits suprema of doubletons.


Suppose now inductively that $\sup T \in S$ for all subsets $T$ of $S$ that have $n$ elements, where $n \ge 2$ is a natural number.

Let now $V \subseteq S$ have $n + 1$ elements.

Then $V = T \cup \left\{{s}\right\}$ for some $s \in S$ and $T \subseteq S$ with $n$ elements.

By Supremum of Suprema, we have that:

$\sup V = \sup \left\{{ \sup T, \sup \left\{{s}\right\} }\right\}$

By definition of join, this means $\sup V = \sup T \vee s$.

Therefore, since $\left({S, \vee, \preceq}\right)$ is a join semilattice, $\sup V \in S$.

By induction, $\sup T \in S$ for all finite non-empty $T \subseteq S$.

That is, $S$ admits all finite non-empty suprema.


By the Global Duality Principle and Dual Pairs (Order Theory), it follows that if:

$\left({S, \wedge, \preceq}\right)$ is a meet semilattice

then it also true that:

$\left({S, \preceq}\right)$ admits all finite non-empty infima


Hence $\left({S, \vee, \wedge, \preceq}\right)$ satisfies Definition 1.

$\Box$


2 implies 3

Suppose that $\left({S, \vee, \wedge, \preceq}\right)$ adheres to Definition 2.

By virtue of Join Semilattice is Semilattice and Meet Semilattice is Semilattice, $\left({S, \vee}\right)$ and $\left({S, \wedge}\right)$ are semilattices.

From Ordering Induced by Join Semilattice, the ordering mentioned in Definition 3 coincides with $\preceq$.


The absorption laws stated are proved on Join Absorbs Meet and Meet Absorbs Join.


Hence $\left({S, \vee, \wedge, \preceq}\right)$ adheres to Definition 3.

$\Box$


3 implies 2

Suppose that $\left({S, \vee, \wedge, \preceq}\right)$ adheres to Definition 3.

Then $\preceq$ is thus defined by, for all $a, b \in S$:

$a \preceq b$ if and only if $a \vee b = b$


Suppose now that $a \vee b = b$.

Then by absorption:

$a = a \wedge \left({a \vee b}\right) = a \wedge b$

Conversely, if $a \wedge b = a$, then by the other absorption law:

$a \vee b = \left({a \wedge b}\right) \vee b = b$

We conclude that also $a \preceq b$ if and only if $a \wedge b = a$.


Next, to prove $a \vee b$ is a supremum for $\left\{{a, b}\right\}$.

We have by absorption that $a = a \wedge \left({a \vee b}\right)$ so that $a \preceq a \vee b$, and similarly for $b$.

Thus $a \vee b$ is an upper bound for $\left\{{a, b}\right\}$.


Suppose that $c$ is an upper bound for $\left\{{a, b}\right\}$.

Then:

\(\displaystyle c\) \(=\) \(\displaystyle a \vee c\) because $a \preceq c$
\(\displaystyle \) \(=\) \(\displaystyle a \vee \left({b \vee c}\right)\) because $b \preceq c$
\(\displaystyle \) \(=\) \(\displaystyle \left({a \vee b}\right) \vee c\) $\vee$ is associative

whence $a \vee b \preceq c$.

Thus $a \vee b \in S$ is a supremum for $\left\{{a, b}\right\}$.


Finally, we will show that $a \wedge b$ is an infimum for $\left\{{a, b}\right\}$.

By Local Duality, $a \wedge b$ must be shown to be a supremum for $\left\{{a, b}\right\}$ with respect to the dual ordering $\succeq$ of $\preceq$.


Since we have established that $a \succeq b$ if and only if $a \wedge b = b$, this directly follows from the above by interchanging $\wedge$ and $\vee$.

Thus we have demonstrated $\left({S, \vee, \wedge, \preceq}\right)$ satisfies Definition 2.

$\blacksquare$


Also see