8
$\begingroup$

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?

$\endgroup$
1
  • 1
    $\begingroup$ 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$. $\endgroup$
    – awwalker
    Commented Nov 8, 2011 at 17:00

2 Answers 2

16
$\begingroup$

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.)

$\endgroup$
12
$\begingroup$

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!)

$\endgroup$
2
  • 1
    $\begingroup$ 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.) $\endgroup$
    – Asaf Karagila
    Commented Oct 7, 2011 at 21:40
  • $\begingroup$ 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. $\endgroup$
    – MikeC
    Commented Oct 7, 2011 at 22:32

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .