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.