Boolean Algebra and Lattices - Key Proof

The uniqueness of complements in Boolean algebras ensures that negation is well-defined and enables many important results.

DefinitionUniqueness of Complements

In a Boolean algebra, each element has a unique complement. That is, if $b$ and $c$ both satisfy $a \land b = 0$ , $a \lor b = 1$ , $a \land c = 0$ , and $a \lor c = 1$ , then $b = c$ .

Proof:

Assume $b$ and $c$ are both complements of $a$ . We show $b = c$ .

Since $b$ is a complement of $a$ : $a \land b = 0 \quad \text{and} \quad a \lor b = 1$

Since $c$ is a complement of $a$ : $a \land c = 0 \quad \text{and} \quad a \lor c = 1$

We compute $b$ using these properties:

$b = b \land 1 \quad \text{(identity law)}$ $= b \land (a \lor c) \quad \text{(since } a \lor c = 1\text{)}$ $= (b \land a) \lor (b \land c) \quad \text{(distributive law)}$ $= (a \land b) \lor (b \land c) \quad \text{(commutative law)}$ $= 0 \lor (b \land c) \quad \text{(since } a \land b = 0\text{)}$ $= b \land c \quad \text{(identity law)}$

Similarly, we compute $c$ :

$c = c \land 1 = c \land (a \lor b) = (c \land a) \lor (c \land b)$ $= (a \land c) \lor (c \land b) = 0 \lor (c \land b) = c \land b$

By commutativity: $b \land c = c \land b$ .

Therefore: $b = b \land c = c \land b = c$ .

This proves uniqueness. $\square$

Alternative Proof:

We can also use symmetry more directly:

$b = b \lor 0 = b \lor (a \land c)$ (using $a \land c = 0$ )

$= (b \lor a) \land (b \lor c)$ (distributive law)

$= (a \lor b) \land (b \lor c) = 1 \land (b \lor c)$ (using $a \lor b = 1$ )

$= b \lor c$

Similarly: $c = c \lor 0 = c \lor (a \land b) = (c \lor a) \land (c \lor b)$ $= (a \lor c) \land (c \lor b) = 1 \land (c \lor b) = c \lor b = b \lor c$

Therefore $b = b \lor c = c$ . $\square$

Remark

This uniqueness justifies writing $\neg a$ for the complement of $a$ without ambiguity. In non-Boolean lattices (without the complement axioms), elements may have multiple complements or no complement. For example, in the lattice of divisors of 12, the element 2 has no complement: there's no divisor $d$ of 12 with $\gcd(2,d) = 1$ and $\text{lcm}(2,d) = 12$ simultaneously. The complement axioms distinguish Boolean algebras from general lattices, giving Boolean algebras their powerful logical structure.