Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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)

share|improve this question
1  
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 1

up vote 1 down vote accepted

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

share|improve this answer
    
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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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