Equivalence of Definitions of Distributive Lattice

From ProofWiki
Jump to navigation Jump to search

Theorem

The following definitions of the concept of Distributive Lattice are equivalent:

Let $\left({S, \vee, \wedge, \preceq}\right)$ be a lattice.

\((1)\)   $:$     \(\displaystyle \forall x, y, z \in S:\) \(\displaystyle x \wedge \left({y \vee z}\right) = \left({x \wedge y}\right) \vee \left({x \wedge z}\right) \)             
\((1')\)   $:$     \(\displaystyle \forall x, y, z \in S:\) \(\displaystyle \left({x \vee y}\right) \wedge z = \left({x \wedge z}\right) \vee \left({y \wedge z}\right) \)             
\((2)\)   $:$     \(\displaystyle \forall x, y, z \in S:\) \(\displaystyle x \vee \left({y \wedge z}\right) = \left({x \vee y}\right) \wedge \left({x \vee z}\right) \)             
\((2')\)   $:$     \(\displaystyle \forall x, y, z \in S:\) \(\displaystyle \left({x \wedge y}\right) \vee z = \left({x \vee z}\right) \wedge \left({x \vee y}\right) \)             

Proof

1 is equivalent to 1'

By applying Meet is Commutative several times, we have:

\(\displaystyle x \wedge \left({y \vee z}\right)\) \(=\) \(\displaystyle \left({x \wedge y}\right) \vee \left({x \wedge z}\right)\)
\(\displaystyle \iff \ \ \) \(\displaystyle \left({y \vee z}\right) \wedge x\) \(=\) \(\displaystyle \left({y \wedge x}\right) \vee \left({z \wedge x}\right)\)

which (after renaming variables as appropriate) establishes the equivalence.

$\Box$


2 is equivalent to 2'

By applying Join is Commutative several times, we have:

\(\displaystyle x \vee \left({y \wedge z}\right)\) \(=\) \(\displaystyle \left({x \vee y}\right) \wedge \left({x \vee z}\right)\)
\(\displaystyle \iff \ \ \) \(\displaystyle \left({y \wedge z}\right) \vee x\) \(=\) \(\displaystyle \left({y \vee x}\right) \wedge \left({z \vee x}\right)\)

which (after renaming variables as appropriate) establishes the equivalence.

$\Box$


1 implies 2

Suppose that $(1)$ holds, and hence $(1')$ as well.

\(\displaystyle \left({x \vee y}\right) \wedge \left({x \vee z}\right)\) \(=\) \(\displaystyle \left({\left({x \vee y}\right) \wedge x}\right) \vee \left({\left({x \vee y}\right) \wedge z}\right)\) by $(1)$
\(\displaystyle \) \(=\) \(\displaystyle x \vee \left({\left({x \vee y}\right) \wedge z}\right)\) $\wedge$ absorbs $\vee$
\(\displaystyle \) \(=\) \(\displaystyle x \vee \left({\left({x \wedge z}\right) \vee \left({y \wedge z}\right)}\right)\) by $(1')$
\(\displaystyle \) \(=\) \(\displaystyle \left({x \vee \left({x \wedge z}\right)}\right) \vee \left({y \wedge z}\right)\) $\vee$ is associative
\(\displaystyle \) \(=\) \(\displaystyle x \vee \left({y \wedge z}\right)\) $\vee$ absorbs $\wedge$

$\Box$


2 implies 1

By inspection, aided by Dual Pairs (Order Theory), we see that $(2)$ is dual to $(1)$.

Thus by Global Duality, $(2)$ implies $(1)$ as soon as $(1)$ implies $(2)$.

That direction was already established above.

$\blacksquare$


Also see