Boolean Algebra is Equivalent to Boolean Lattice
This article, or a section of it, needs explaining. In particular: But a boolean lattice is defined as a boolean algebra with an ordering of the type given, so this page is proving what is already defined? 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. |
It has been suggested that this page be renamed. In particular: A boolean algebra is not the same as a boolean lattice so how can they be equivalent? To discuss this page in more detail, feel free to use the talk page. |
Theorem
Let $\struct {S, \vee, \wedge, \neg}$ be a Boolean algebra.
Let $\preceq$ be the ordering on $S$ defined as:
- $a \preceq b \iff a \vee b = b$
for all $a, b \in S$.
Then, $\struct {S, \vee, \wedge, \preceq}$ is a Boolean lattice.
Proof
By definition 2 of Boolean Lattice, it suffices to show that:
- $\preceq$ is an ordering
- $\preceq$ is compatible with $\vee$ and $\wedge$
- For all $a, b \in S: a \wedge b \preceq a \vee b$
Ordering of $\preceq$
By Operations of Boolean Algebra are Idempotent:
- $a \vee a = a$
for all $a \in S$.
Therefore, $\forall a \in S: a \preceq a$.
Thus, $\preceq$ is reflexive.
$\Box$
Let $a, b, c \in S$ be arbitrary, and suppose $a \preceq b$ and $b \preceq c$.
By definition, that is:
- $\paren 1 \quad a \vee b = b$
- $\paren 2 \quad b \vee c = c$
By substitution of $\paren 1$ into $\paren 2$ we have:
- $\paren {a \vee b} \vee c = c$
By Operations of Boolean Algebra are Associative:
- $a \vee \paren {b \vee c} = c$
By substitution of $\paren 2$:
- $a \vee c = c$
Therefore, $a \preceq c$ by definition.
Since $a, b, c \in S$ were arbitrary, it follows that $\preceq$ is transitive.
$\Box$
Let $a, b \in S$ be arbitrary, and suppose $a \preceq b$ and $b \preceq a$.
By definition, that is:
- $a \vee b = b$
- $b \vee a = a$
By Boolean Algebra Axiom $(\text {BA}_1 1)$: Commutativity, it follows that $a \vee b = b \vee a$.
It immediately follows that $a = b$ from the assumptions.
Since $a, b \in S$ were arbitrary, it follows that $\preceq$ is antisymmetric.
$\Box$
From the above, $\preceq$ is an ordering by definition.
$\Box$
Compatibility of $\preceq$ with $\wedge$
By Boolean Algebra Axiom $(\text {BA}_1 1)$: Commutativity, it suffices to show that, for any $a, b, c \in S$:
- $a \preceq b \implies \paren {c \wedge a} \preceq \paren {c \wedge b}$
Let $a, b, c \in S$ be arbitrary, and suppose $a \preceq b$.
By definition of $\preceq$:
- $a \vee b = b$
Then:
\(\ds \paren {c \wedge a} \vee \paren {c \wedge b}\) | \(=\) | \(\ds c \wedge \paren {a \vee b}\) | Boolean Algebra Axiom $(\text {BA}_1 2)$: Distributivity | |||||||||||
\(\ds \) | \(=\) | \(\ds c \wedge b\) | by hypothesis |
But, by definition of $\preceq$:
- $\paren {c \wedge a} \preceq \paren {c \wedge b}$
Since $a, b, c \in S$ were arbitrary, it follows that $\preceq$ is compatible with $\wedge$.
$\Box$
Compatibility of $\preceq$ with $\vee$
By Boolean Algebra Axiom $(\text {BA}_1 1)$: Commutativity, it suffices to show that, for any $a, b, c \in S$:
- $a \preceq b \implies \paren {c \vee a} \preceq \paren {c \vee b}$
Let $a, b, c \in S$ be arbitrary, and suppose $a \preceq b$.
By definition of $\preceq$:
- $a \vee b = b$
Then:
\(\ds \paren {c \vee a} \vee \paren {c \vee b}\) | \(=\) | \(\ds \paren {c \vee c} \vee {a \vee b}\) | Boolean Algebra Axiom $(\text {BA}_1 1)$: Commutativity, as well as Operations of Boolean Algebra are Associative | |||||||||||
\(\ds \) | \(=\) | \(\ds c \vee b\) | Operations of Boolean Algebra are Idempotent, as well as by hypothesis |
Therefore, $c \vee a \preceq c \vee b$.
Since $a, b, c \in S$ were arbitrary, it follows that $\preceq$ is compatible with $\vee$.
$\Box$
Ordering of $\wedge$ and $\vee$
Let $a, b \in S$ be arbitrary.
Then:
\(\ds \paren {a \wedge b} \vee \paren {a \vee b}\) | \(=\) | \(\ds \paren {a \vee \paren {a \vee b} } \wedge \paren {b \vee \paren {a \vee b} }\) | Boolean Algebra Axiom $(\text {BA}_1 2)$: Distributivity | |||||||||||
\(\ds \) | \(=\) | \(\ds \paren {a \vee \paren {a \vee b} } \wedge \paren {\paren {a \vee b} \vee b}\) | Boolean Algebra Axiom $(\text {BA}_1 1)$: Commutativity | |||||||||||
\(\ds \) | \(=\) | \(\ds \paren {\paren {a \vee a} \vee b} \wedge \paren {a \vee \paren {b \vee b} }\) | Operations of Boolean Algebra are Associative | |||||||||||
\(\ds \) | \(=\) | \(\ds \paren {a \vee b} \wedge \paren {a \vee b}\) | Operations of Boolean Algebra are Idempotent | |||||||||||
\(\ds \) | \(=\) | \(\ds a \vee b\) | Operations of Boolean Algebra are Idempotent |
Therefore, by definition:
- $a \wedge b \preceq a \vee b$
$\Box$
All of the conditions listed above have been satisfied.
By inspecting the relevant definitions, it follows that $\struct {S, \vee, \wedge, \preceq}$ is a Boolean lattice by definition 2.
$\blacksquare$