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.

This seems obvious but I wanted to check, since I don't see it mentioned anywhere.

If we define a boolean algebra as having at least two elements, then that algebra has a minimal element (0) and a maximal element (1). Since each element has a unique complement, 0* = 1 and 1* = 0. If I add a third element x which is distinct from 0 and 1, it has to have a complement x*. And of course x* is not equal to 0 or 1, since x isn't. And x* is not equal to x, since if it were we would not have (x v x* = 1). So this algebra has 4 elements.

So no boolean algebra has 3 elements. -- This seems to generalize to: any boolean algebra which has a finite number of elements has an even number of elements. I suppose any finite boolean algebra is isomorphic to a field of sets, where the basis set S has n elements so the field contains 2 to the n sets, which is an even number.

Does that sound right?

share|improve this question
    
A finite Boolean algebra is, in particular, a finite group (under symmetric difference). With this, we check that each element has additive order $2$, hence Cauchy's theorem implies that the order of the group is a power of $2$. –  A Walker Nov 8 '11 at 17:00
add comment

2 Answers

up vote 6 down vote accepted

Yes, a finite boolean algebra with $0\neq 1$ must have an even number of points.

The fact that involution has no fixed points follows from complementation: if $x=x^*$, then $x = x\lor x = x\lor x^* = 1$ and $x=x\land x = x\land x^* = 0$, so $0=1$; hence if $0\neq 1$, then $x\neq x^*$ for all $x$. Since $(x^*)^* = x$, you can partition the algebra into equivalence classes, each with two elements (define $x\sim y$ if and only if $x=y$ or $x=y^*$). So the cardinality of the set, if finite, is even.

Your other conclusion is stronger: you are asserting that every boolean algebra is isomorphic to the full boolean algebra of subsets of a given set $S$, which would mean the number of elements is a power of $2$.

You are also correct that every finite boolean algebra is in fact isomorphic to the boolean algebra of all subsets of a given set $S$, and therefore the number of elements is a power of $2$; but that's a stronger conclusion and does not follow directly merely from the fact that complementation has no fixed points when the algebra has $0\neq 1$.

Here's one way of proving that every finite boolean algebra $B$ is isomorphic to one of the form $2^S$, where $S$ is a set (that is, all subsets of $S$, under $\lor=\cup$, $\land=\cap$, $0=\emptyset$, $1=S$, and ${}^*$ being complementation); the key is to note that in a finite lattice you have certain "minimal elements", and that in a finite boolean lattice, each element is completely determined by the set of minimal elements that are smaller than it.

Let $B$ be a boolean algebra. We define an order on $B$ by $x\leq y$ if and only if $x\land y = x$, or equivalently $x\lor y = y$. With this ordering, $\land$ becomes the greatest lower bound, and $\lor$ the least upper bound.

An element $b\in B$ is called an atom if and only if $b\neq 0$, but if $0\leq x\leq b$, then either $0=x$ or $x=b$; that is, $b$ is an atom if and only if it is a minimal element of $B-\{0\}$.

Now let $x\in B$. I claim that $$x = \lor\{b\in B\mid b\text{ is an atom and }b\leq x\}.$$ Call the least upper bound on the right $a$. Since $x$ is an upper bound for each element of the set, $x\geq a$. Now assume that we do not have $x\leq a$. Then $x\land a^*\neq 0$ (if $x\land a^*=0$, then $x^* = x^*\lor 0 = x^*\lor (x\land a^*) = (x^*\lor x)\land (x^*\lor a^*) = x^*\lor a^*$, and taking complements we get $x = x\land a$, hence $x\leq a$). So there exists an atom $b$ such that $b\leq x\land a^*$. But then $b\leq a$ (since $b$ is an atom and $b\leq x$) and $b\leq a^*$ by assumption, so $b\leq (a\land a^*) = 0$, which is impossible (since $b\neq 0$). This contradiction arises from the assumption that $x\not\leq a$, so $x\leq a$; since $x\geq a$, we conclude that $x=a$.

Thus, each element is characterized by the set of atoms that are less than or equal to it. We can define a boolean algebra homomorphism $$f\colon B \to \mathcal{P}(A(B)),$$ where $A(B) = \{b\in B\mid a \text{ is an atom}\}$, by $$f(x) = \{b\in A(B)\mid x\leq b\}.$$ and using the fact above it is straightforward now to show that $f$ is indeed a bijective boolean algebra isomorphism.

The more general statement that every boolean algebra is isomorphic to a subalgebra of the field of subsets of some $X$ depends on your Set Theory; it follows from the Boolean Prime Ideal Theorem (every ideal in a boolean algebra can be extended to a prime ideal), which is known to be strictly weaker than the Axiom of Choice, but not provable in ZF. (It is considered a weak form of the Axiom of Choice). (Note that you have to specify "subalgebra"; you cannot hope for every boolean algebra to be the full algebra of subsets of a given $X$, because that would imply that there are no infinite countable boolean algebras, which is false.)

share|improve this answer
add comment

Yes, any finite Boolean algebra is isomorphic to a field of sets, so has $2^n$ elements for some $n$. You can prove the latter fact using the fact that any Boolean algebra is in particular a vector space over the finite field $\mathbb{F}_2$ (vector addition is given by XOR). Any finite-dimensional such vector space is isomorphic to $\mathbb{F}_2^n$, hence has $2^n$ elements.

In fact, any Boolean algebra is isomorphic to a field of sets. This is a consequence of Stone's representation theorem.

(Also, there's no reason to exclude the trivial Boolean algebra. It's the collection of subsets of the empty set!)

share|improve this answer
    
It is worth noting (even if in this comment) that a Boolean algebra is not a vector space over $\mathbb F_2$ with its own addition, but rather with a whole other operation (definable within the structure, of course.) –  Asaf Karagila Oct 7 '11 at 21:40
    
I don't claim to know whether this or the following is the "better" answer. I clicked the following as my "accepted" answer because it doesn't require me to learn about vector spaces. But thanks for both of them. –  MikeC Oct 7 '11 at 22:32
add comment

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.