# The cardinality of finite Boolean lattice

A book (Introduction to Lattices and Order) says that we can prove that the cardinality of any finite Boolean lattice $B$ is a power of 2 by induction on $|B|$ with the following lemma:

If a lattice $L$ is distributive and has the top and the bottom element, and $a \in L$, then $f_a : L \rightarrow \downarrow{a} \mathop{\times} \uparrow a = x \mapsto (x \wedge a,x \vee a)$ is an isomorphism if and only if $a$ has a complement in $L$.

However, I don't know how I can do. Could you give me a solution for this problem?

(Of course, I know $B$ is by following Birkhoff's representation theorem)

-
You mean finite Boolean lattices. –  joriki Nov 28 '12 at 19:13
Oops, you are right. –  skymountain Nov 29 '12 at 0:38

## 1 Answer

If $B$ has one or two elements, $|B|$ is a power of $2$. Assume that $|B|$ is a power of $2$ for all Boolean lattices $B$ with $|B|\lt n$ for some $n\gt2$, and consider a Boolean lattice $B'$ with $|B'|=n$. Pick any element $a$ other than $0$ and $1$ in $B'$. Since $B'$ is a complemented lattice, by the lemma, $B'$ is isomorphic to $\downarrow a\times\uparrow a$, and since $a$ is neither $0$ nor $1$ both $\downarrow a$ and $\uparrow a$ have more than one element. Thus they are both Boolean lattices of size less than $n$. The size of $B'$ is the product of their sizes, which by the induction hypothesis are powers of $2$, so $|B'|$ is also a power of $2$. It follows by complete induction that the cardinality of all finite Boolean lattices is a power of $2$.

[Edit in response to comment:]

$\downarrow a$ and $\uparrow a$ are Boolean lattices because they are closed under the lattice operations,

$$(x\lor a)\lor(x\lor b)=x\lor(a\lor b)\;,\\ (x\lor a)\land(x\lor b)=x\lor(a\land b)\;,\\ (x\land a)\lor(x\land b)=x\land(a\lor b)\;,\\ (x\land a)\land(x\land b)=x\land(a\land b)\;,$$

they inherit distributivity from $B'$, and they are complemented:

$$(x\lor a)\land 1=x\lor a\;,\\ (x\lor a)\lor x=x\lor a\;,\\ (x\land a)\land x=x\land a\;,\\ (x\land a)\lor 0=x\land a\;,$$ $$(x\lor a)\lor(x\lor\bar a)=1\;,\\ (x\lor a)\land(x\lor\bar a)=x\;,\\ (x\land a)\lor(x\land\bar a)=x\;,\\ (x\land a)\land(x\land\bar a)=0\;.$$

-
Why are $\downarrow a$ and $\uparrow a$ finite Boolean lattices? In particular, what is a compliment for each element in them? –  skymountain Nov 29 '12 at 0:49
@skymountain: Sorry, that should have been part of the answer; I added it. –  joriki Nov 29 '12 at 4:40
Great, thank you very much! –  skymountain Nov 29 '12 at 5:08
@skymountain: You're welcome! –  joriki Nov 29 '12 at 5:12