Boolean Algebra is Equivalent to Boolean Lattice

From ProofWiki
Jump to navigation Jump to search


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$

Retrieved from "https://proofwiki.org/w/index.php?title=Boolean_Algebra_is_Equivalent_to_Boolean_Lattice&oldid=673959"