1
$\begingroup$

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)

  • 0
    Oops, you are right.2012-11-29

1 Answers 1

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

  • 0
    @skymountain: You're welcome!2012-11-29