De Morgan's Laws imply Uniquely Complemented Lattice is Boolean Lattice
Theorem
Let $\left({S, \wedge, \vee, \preceq}\right)$ be a uniquely complemented lattice.
Then the following are equivalent:
$(1):\quad \forall p, q \in S: \neg p \vee \neg q = \neg \left({p \wedge q}\right)$
$(2):\quad \forall p, q \in S: \neg p \wedge \neg q = \neg \left({p \vee q}\right)$
$(3):\quad \forall p, q \in S: p \preceq q \iff \neg q \preceq \neg p$
$(4):\quad \left({S, \wedge, \vee, \preceq}\right)$ is a distributive lattice.
Proof
$(1)$ implies $(2)$
Suppose:
- $\forall p, q \in S: \neg p \vee \neg q = \neg \left({p \wedge q}\right)$
Then applying this to $\neg p$ and $\neg q$:
- $\neg \neg p \vee \neg \neg q = \neg \left({\neg p \wedge \neg q}\right)$
By Complement of Complement in Uniquely Complemented Lattice, $\neg \neg p = p$ and $\neg \neg q = q$.
Thus:
- $p \vee q = \neg \left({\neg p \wedge \neg q}\right)$.
Taking complements of both sides:
- $\neg \left({p \vee q}\right) = \neg \neg \left({\neg p \wedge \neg q}\right)$
Again applying Complement of Complement in Uniquely Complemented Lattice:
- $\neg \left({p \vee q}\right) = \neg p \wedge \neg q$
$\Box$
$(2)$ implies $(1)$
By Dual Pairs (Order Theory), $\wedge$ and $\vee$ are dual.
Thus this implication follows from the above by Duality.
$\Box$
$(1)$ implies $(3)$
By the definition of a lattice:
- $p \preceq q \iff p \vee q = q$
Applying this to $\neg q$ and $\neg p$:
- $\neg q \preceq \neg p \iff \neg q \vee \neg p = \neg p$
By $(1)$:
- $\neg q \vee \neg p = \neg \left({q \wedge p}\right)$
So:
- $\neg q \preceq \neg p \iff \neg \left({q \wedge p}\right) = \neg p$
Taking the complements of both sides of the equation on the right, and applying Complement of Complement in Uniquely Complemented Lattice:
- $\neg q \preceq \neg p \iff q \wedge p = p$
But the right side is equivalent to $p \preceq q$
Therefore:
- $\neg q \preceq \neg p \iff p \preceq q$
$\Box$
$(3)$ implies $(1)$
Suppose that $p \preceq q \iff \neg q \preceq \neg p$
By the definition of join:
- $\neg p, \neg q \preceq \neg p \vee \neg q$
Thus $\neg \left({\neg p \vee \neg q}\right) \preceq p, q$.
By the definition of meet:
- $\neg \left({\neg p \vee \neg q}\right) \preceq p \wedge q$
Thus:
- $\neg\left({p \wedge q}\right) \preceq \neg\neg \left({\neg p \vee \neg q}\right)$
By Complement of Complement in Uniquely Complemented Lattice: $*\quad \neg\left({p \wedge q}\right) \preceq \neg p \vee \neg q$
Dually:
- $\neg x \wedge \neg y \preceq \neg \left({x \vee y}\right)$
Letting $x = \neg p$ and $y = \neg q$:
- $\neg \neg p \wedge \neg \neg q \preceq \neg \left({\neg p \vee \neg q}\right)$
By Complement of Complement in Uniquely Complemented Lattice:
- $p \wedge q \preceq \neg \left({\neg p \vee \neg q}\right)$
By the premise and Complement of Complement in Uniquely Complemented Lattice, then: $**\quad \neg p \vee \neg q \preceq \neg \left({p \wedge q}\right)$
By $*$ and $**$: $\quad \neg\left({p \wedge q}\right) = \neg p \vee \neg q$
$\Box$
$(1)$, $(2)$, and $(3)$ together imply $(4)$
$b, c \preceq b \vee c$, so
- $a \wedge b \preceq a \wedge \left({b \vee c}\right)$
- $a \wedge c \preceq a \wedge \left({b \vee c}\right)$
By the definition of join:
- $\left({a \wedge b}\right) \vee \left({a \wedge c}\right) \preceq a \wedge \left({b \vee c}\right)$
Sources
This article incorporates material from Uniquely Complemented Lattice on PlanetMath, which is licensed under the Creative Commons Attribution/Share-Alike License.