Join with Complement is Top

From ProofWiki
Jump to navigation Jump to search

Theorem

Let $\struct {S, \vee, \wedge, \neg}$ be a Boolean algebra, defined as in Definition 2.


Then:

$\exists \top \in S: \forall a \in S: a \vee \neg a = \top$

where $\wedge$ denotes the meet operation in $S$.


This element $\top$ is unique for any given $S$, and is named top.


Proof

Let $\exists r, s \in S: r \vee \neg r = a, \ s \vee \neg s = b$

Then:

\(\displaystyle a\) \(=\) \(\displaystyle r \vee \neg r\) by hypothesis
\(\displaystyle \) \(=\) \(\displaystyle \paren {s \vee \neg s} \wedge \paren {r \vee \neg r}\) Boolean Algebra: Axiom $(BA_2 \ 5)$
\(\displaystyle \) \(=\) \(\displaystyle \paren {r \vee \neg r} \wedge \paren {s \vee \neg s}\) Boolean Algebra: Axiom $(BA_2 \ 1)$
\(\displaystyle \) \(=\) \(\displaystyle s \vee \neg s\) Boolean Algebra: Axiom $(BA_2 \ 5)$
\(\displaystyle \) \(=\) \(\displaystyle b\) by hypothesis


Thus, whatever $r$ and $s$ may be:

$r \vee \neg r = s \vee \neg s$

This unique element can be assigned the symbol $\top$ and named top as required.

$\blacksquare$


Sources