De Morgan's Laws imply Uniquely Complemented Lattice is Boolean Lattice

Theorem

Let $\struct {S, \wedge, \vee, \preceq}$ be a uniquely complemented lattice.

Then the following are equivalent:

$(1):\quad \forall p, q \in S: \neg p \vee \neg q = \neg \paren {p \wedge q}$

$(2):\quad \forall p, q \in S: \neg p \wedge \neg q = \neg \paren {p \vee q}$

$(3):\quad \forall p, q \in S: p \preceq q \iff \neg q \preceq \neg p$

$(4):\quad \struct {S, \wedge, \vee, \preceq}$ is a distributive lattice.

This article, or a section of it, needs explaining. In particular: So we're equivalencing a distributive lattice, but the page title says Boolean Lattice -- needs to be resolved You can help $\mathsf{Pr} \infty \mathsf{fWiki}$ by explaining it. To discuss this page in more detail, feel free to use the talk page. When this work has been completed, you may remove this instance of {{Explain}} from the code.

Proof

$(1)$ implies $(2)$

Suppose:

$\forall p, q \in S: \neg p \vee \neg q = \neg \paren {p \wedge q}$

Then applying this to $\neg p$ and $\neg q$:

$\neg \neg p \vee \neg \neg q = \neg \paren {\neg p \wedge \neg q}$

By Complement of Complement in Uniquely Complemented Lattice:

$\neg \neg p = p$ and $\neg \neg q = q$

Thus:

$p \vee q = \neg \paren {\neg p \wedge \neg q}$

Taking complements of both sides:

$\neg \paren {p \vee q} = \neg \neg \paren {\neg p \wedge \neg q}$

Again applying Complement of Complement in Uniquely Complemented Lattice:

$\neg \paren {p \vee q} = \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 \paren {q \wedge p}$

So:

$\neg q \preceq \neg p \iff \neg \paren {q \wedge p} = \neg p$

Taking the complements of both sides of the equation on the right hand side, and applying Complement of Complement in Uniquely Complemented Lattice:

$\neg q \preceq \neg p \iff q \wedge p = p$

But the right hand side is equivalent to $p \preceq q$.

This article, or a section of it, needs explaining. In particular: We define the ordering on a lattice (definition 3) based on joins. We need an equivalent one based on meets, or maybe we have it somewhere already. You can help $\mathsf{Pr} \infty \mathsf{fWiki}$ by explaining it. To discuss this page in more detail, feel free to use the talk page. When this work has been completed, you may remove this instance of {{Explain}} from the code.

Therefore:

$\neg q \preceq \neg p \iff p \preceq q$

$\Box$

$(3)$ implies $(1)$

Although this article appears correct, it's inelegant. There has to be a better way of doing it. In particular: This is ugly You can help $\mathsf{Pr} \infty \mathsf{fWiki}$ by redesigning it. To discuss this page in more detail, feel free to use the talk page. When this work has been completed, you may remove this instance of {{Improve}} from the code. If you would welcome a second opinion as to whether your work is correct, add a call to {{Proofread}} the page.

This article needs to be linked to other articles. You can help $\mathsf{Pr} \infty \mathsf{fWiki}$ by adding these links. To discuss this page in more detail, feel free to use the talk page. When this work has been completed, you may remove this instance of {{MissingLinks}} from the code.

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 \paren {\neg p \vee \neg q} \preceq p, q$

By the definition of meet:

$\neg \paren {\neg p \vee \neg q} \preceq p \wedge q$

Thus:

$\neg \paren {p \wedge q} \preceq \neg \neg \paren {\neg p \vee \neg q}$

By Complement of Complement in Uniquely Complemented Lattice:

$*\quad \neg \paren {p \wedge q} \preceq \neg p \vee \neg q$

Dually:

$\neg x \wedge \neg y \preceq \neg \paren {x \vee y}$

Letting $x = \neg p$ and $y = \neg q$:

$\neg \neg p \wedge \neg \neg q \preceq \neg \paren {\neg p \vee \neg q}$

By Complement of Complement in Uniquely Complemented Lattice:

$p \wedge q \preceq \neg \paren {\neg p \vee \neg q}$

By the premise and Complement of Complement in Uniquely Complemented Lattice:

$**\quad \neg p \vee \neg q \preceq \neg \paren {p \wedge q}$

By $*$ and $**$:

$\quad \neg \paren {p \wedge q} = \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 \paren {b \vee c}$

$a \wedge c \preceq a \wedge \paren {b \vee c}$

By the definition of join:

$\paren {a \wedge b} \vee \paren {a \wedge c} \preceq a \wedge \paren {b \vee c}$

This needs considerable tedious hard slog to complete it. To discuss this page in more detail, feel free to use the talk page. When this work has been completed, you may remove this instance of {{Finish}} from the code. If you would welcome a second opinion as to whether your work is correct, add a call to {{Proofread}} the page.

Sources

• This article incorporates material from Uniquely Complemented Lattice on PlanetMath, which is licensed under the Creative Commons Attribution/Share-Alike License.