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)

  • 1
    $\begingroup$ You mean finite Boolean lattices. $\endgroup$
    – joriki
    Nov 28, 2012 at 19:13
  • $\begingroup$ Oops, you are right. $\endgroup$ Nov 29, 2012 at 0:38

1 Answer 1


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\;. $$

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.