Boolean Algebras

This is the standard uniqueness argument for complements, using only distributivity and the lattice axioms — no completeness or finiteness is needed. Compute:

by distributivity. Since $a \wedge b = 0$ (commutativity of $\wedge$ gives $b \wedge a = 0$), this becomes

Hence $b \le c$ (since $b \wedge c = b$ is exactly the order-theoretic definition of $b \le c$). By the symmetric computation swapping the roles of $b$ and $c$ (using $a \vee b = 1$ and $a \wedge c = 0$),

so $c \le b$. By antisymmetry of the partial order $\le$ on a lattice, $b = c$. $\blacksquare$

We prove $(a \vee b)' = a' \wedge b'$; the second identity is dual (obtained by exchanging the roles of $\vee$ and $\wedge$ throughout, which is legitimate because the Boolean algebra axioms are self-dual under swapping $\vee \leftrightarrow \wedge$ and $0 \leftrightarrow 1$). By the uniqueness lemma just proved, to show $a' \wedge b'$ is the complement of $a \vee b$ it suffices to verify the two defining equations

First equation. Using distributivity (axiom 3) twice:

Now $(a \vee b) \vee a' = (a \vee a') \vee b = 1 \vee b = 1$, using associativity/commutativity of $\vee$, the complement axiom $a \vee a'=1$, and $1 \vee b = 1$ (which follows from absorption: $1 = a\vee a' \le 1 \vee b$, and $1$ is the top element so $1 \vee b \le 1$ too, giving equality — or directly, $a \wedge 1 = a$ for all $a$ forces $1$ maximal, hence $1 \vee b=1$). Similarly $(a \vee b) \vee b' = 1$. So the right side is $1 \wedge 1 = 1$, proving the first equation.

Second equation. Using distributivity of $\wedge$ over $\vee$:

Now $a \wedge (a' \wedge b') = (a \wedge a') \wedge b' = 0 \wedge b' = 0$ (using $0 \wedge x = 0$, which holds since $0 \wedge x \le 0$ automatically and $0$ is the bottom element). Symmetrically $b \wedge (a' \wedge b') = (b \wedge b')\wedge a' = 0 \wedge a' = 0$. So the right side is $0 \vee 0 = 0$, proving the second equation. By the uniqueness lemma applied to the element $a \vee b$, since $a' \wedge b'$ satisfies both defining complement equations, $a' \wedge b' = (a\vee b)'$. This proves the first De Morgan law; the dual argument (swap $\vee, \wedge$ and $0,1$ throughout) gives $(a \wedge b)' = a' \vee b'$.

Remaining identities. $0' = 1$ and $1' = 0$ follow because $0 \vee 1 = 1$ and $0 \wedge 1 = 0$ automatically hold (as $0$ is bottom, $1$ is top), so $1$ satisfies the defining equations for the complement of $0$; by uniqueness $0' = 1$, and dually $1'=0$. For $(a')' = a$: the complement axioms for $a'$ read $a' \vee a = 1$ and $a' \wedge a = 0$ (commutativity), which are exactly the defining equations that make $a$ a complement of $a'$. By the uniqueness lemma applied to the element $a'$, its complement is unique, and $a$ satisfies the required equations, so $(a')' = a$. $\blacksquare$

Suppose $a \le b$, i.e. $a \vee b = b$. Apply complementation (a well-defined operation by the uniqueness lemma) and De Morgan's law: $b' = (a \vee b)' = a' \wedge b'$, which by definition of $\le$ means $b' \le a'$. Conversely if $b' \le a'$, the forward direction (applied to $b' \le a'$, using $(a')' = a$ and $(b')'=b$ from the previous theorem) gives $(a')' \le (b')'$, i.e. $a \le b$. $\blacksquare$

The proof combines an existence argument (every element is an atom-join), a uniqueness argument, and a verification that the resulting bijection is a lattice isomorphism respecting complements.

Step 1: Atoms exist below every nonzero element, and finiteness gives a decomposition. Fix $b \in B$, $b \neq 0$. Consider the set $S = \{x \in B : 0 < x \le b\}$; it is nonempty since $b \in S$. Because $B$ is finite, $S$ has a minimal element $a_1$ under $\le$ (any nonempty finite poset has minimal elements). Minimality of $a_1$ in $S$ means: there is no $x$ with $0 < x < a_1$ and $x \le b$; but if there were any $x$ with $0 < x < a_1$ at all (not requiring $x \le b$), then $x \le a_1 \le b$ gives $x \in S$ with $x < a_1$, contradicting minimality of $a_1$ in $S$. So no such $x$ exists, i.e. $a_1$ is an atom of $B$, and $a_1 \le b$. Now argue by strong induction on $|B|$ (finiteness makes this well-founded) that $b$ is a join of atoms below it. If $b$ is itself an atom, $b = \bigvee\{b\}$ and we are done. Otherwise, having found atom $a_1 \le b$ with $a_1 \ne b$, we use distributivity to "peel off" $a_1$: define $b_1 := b \wedge a_1'$. We claim $b = a_1 \vee b_1$ and $a_1 \wedge b_1 = 0$, and that the atoms $\le b$ other than possibly $a_1$ itself are exactly the atoms $\le b_1$, together with $a_1 \le b$. Indeed, $a_1 \vee b_1 = a_1 \vee (b \wedge a_1') = (a_1 \vee b) \wedge (a_1 \vee a_1') = (a_1 \vee b) \wedge 1 = a_1 \vee b = b$, the last equality because $a_1 \le b$. Also $a_1 \wedge b_1 = a_1 \wedge b \wedge a_1' = (a_1 \wedge a_1') \wedge b = 0 \wedge b = 0$. Since $a_1 \ne 0$ and $b_1 \wedge a_1 = 0$, and $b_1 \le b$ with $b_1 \ne b$ (else $a_1 \le b_1$ forces $a_1 = a_1 \wedge b_1 = 0$, contradiction), $b_1$ is a strictly smaller element than $b$ in the finite lattice $B$ (or $b_1=0$). If $b_1 = 0$ then $b = a_1$, an atom, done. Otherwise, by the inductive hypothesis applied to $b_1$ (which lies in the strictly smaller "world" of elements $\le b$, well-founded by finiteness), $b_1$ is the join of the atoms below it, and every such atom $a$ satisfies $a \le b_1 \le b$ so is an atom below $b$, distinct from $a_1$ since $a \wedge a_1 \le b_1 \wedge a_1 = 0 < a$ so $a \ne a_1$ (as $a$ is an atom, $a \wedge a_1=0$ forces $a\ne a_1$, else $a \wedge a_1 = a \ne 0$). Hence $b = a_1 \vee b_1 = a_1 \vee \bigvee\{\text{atoms} \le b_1\}$, and every atom appearing is $\le b$. Any atom $a \le b$ with $a\ne a_1$ satisfies $a \wedge a_1=0$ (distinct atoms in any lattice meet in $0$, since an atom has no elements strictly between $0$ and itself, so $a \wedge a_1 < a$ forces $a\wedge a_1 = 0$ when $a \ne a_1$), hence $a = a \wedge b = a \wedge(a_1 \vee b_1) = (a\wedge a_1)\vee(a \wedge b_1) = a \wedge b_1 \le b_1$, so $a$ is counted among the atoms below $b_1$. This shows $b$ is exactly the join of all atoms $\le b$, establishing existence.

Step 2: Uniqueness of the atom-join decomposition, and injectivity of $\varphi$. Suppose $b = \bigvee_{a \in T} a$ for some set $T$ of atoms. We show $T = \{a \in A(B): a \le b\} =: \varphi(b)$, which gives uniqueness. Certainly every $a \in T$ satisfies $a \le b$ (join is an upper bound), so $T \subseteq \varphi(b)$. Conversely suppose $a_0$ is an atom with $a_0 \le b$ but $a_0 \notin T$. For each $a \in T$, $a_0 \ne a$ are distinct atoms so $a_0 \wedge a = 0$ as noted above. By distributivity extended to finite joins (an easy induction on $|T|$ from the binary distributive law),

contradicting that $a_0 \ne 0$ is an atom. So no such $a_0$ exists, giving $\varphi(b) \subseteq T$, hence $T = \varphi(b)$. This proves uniqueness in part 1, and shows in particular that if $\varphi(b) = \varphi(c)$ then, applying Step 1's existence decomposition to both, $b = \bigvee \varphi(b) = \bigvee\varphi(c) = c$. So $\varphi$ is injective.

Step 3: $\varphi$ is surjective. Given any $T \subseteq A(B)$, if $T = \varnothing$ set $b = 0$, and $\varphi(0) = \varnothing$ since no atom is $\le 0$ (atoms are nonzero, and $a \le 0$ forces $a = a\wedge 0 = 0$). If $T \ne \varnothing$, set $b = \bigvee_{a\in T} a$ (a finite join in the finite lattice $B$, hence well-defined and lying in $B$). By Step 2's uniqueness argument applied to this very $b$, $\varphi(b) = T$. So $\varphi$ is surjective, hence a bijection $B \leftrightarrow \mathcal P(A(B))$.

Step 4: $\varphi$ is an isomorphism of the algebraic structure. We must check $\varphi$ respects $\vee, \wedge, {}', 0, 1$. Join: For $b, c \in B$, $\varphi(b \vee c) = \varphi(b) \cup \varphi(c)$. Indeed, an atom $a \le b \vee c$ iff $a \in \varphi(b)\cup \varphi(c)$: if $a \le b$ or $a \le c$ then clearly $a \le b \vee c$ (upper bound property), giving $\supseteq$. Conversely if $a \le b\vee c$, write $b \vee c = \bigvee(\varphi(b)\cup\varphi(c))$ by Step 1 applied to both $b$ and $c$ and the fact that a join of joins is the join of the union (associativity of $\vee$); Step 2's uniqueness (applied to $b\vee c$, whose atom-set below it is by definition $\varphi(b\vee c)$, matched against the explicit join $\bigvee(\varphi(b)\cup\varphi(c))$) forces $\varphi(b\vee c) = \varphi(b)\cup\varphi(c)$. Meet: For $b,c\in B$, an atom $a \le b \wedge c$ iff $a \le b$ and $a \le c$ (standard property of meet as greatest lower bound: $a \le b\wedge c$ iff $a\le b$ and $a \le c$, for $a \le b\wedge c \Rightarrow a\wedge b = a \wedge(b\wedge c)\wedge b=a\wedge (b\wedge c)=a$ so $a\le b$, similarly $a\le c$; conversely $a\wedge b=a,a\wedge c=a \Rightarrow a\wedge(b\wedge c) = (a\wedge b)\wedge c=a\wedge c=a$). Hence $\varphi(b\wedge c) = \varphi(b)\cap\varphi(c)$. Bounds: $\varphi(0) = \varnothing$ as shown; $\varphi(1) = A(B)$ since every atom satisfies $a \le 1$ (as $1$ is the top element, $a \wedge 1 = a$ for all $a$). Complement: We must show $\varphi(b') = \varphi(b)^c = A(B)\setminus \varphi(b)$. First, $\varphi(b) \cap \varphi(b') = \varphi(b\wedge b') = \varphi(0) = \varnothing$, so $\varphi(b')$ and $\varphi(b)$ are disjoint subsets of $A(B)$. Second, $\varphi(b)\cup \varphi(b') = \varphi(b \vee b') = \varphi(1) = A(B)$, so together they cover $A(B)$. A pair of disjoint subsets of a finite set covering it are complementary, so $\varphi(b') = A(B)\setminus\varphi(b) = \varphi(b)^c$. Since $\varphi$ is a bijection preserving $\vee,\wedge,{}',0,1$, it is an isomorphism of Boolean algebras $B \cong \mathcal P(A(B))$. Labeling the $n$ atoms $a_1,\dots,a_n$ gives an evident further isomorphism $\mathcal P(A(B)) \cong \mathcal P([n]) = 2^{[n]}$ (send $a_i \mapsto i$), so $B \cong 2^n$, and in particular $|B| = |\mathcal P([n])| = 2^n$. $\blacksquare$