Every Boolean Algebra is a Group
an alternative approach to counting the elements
of a finite Boolean Algebra
A group G is a set with a law of combination (so any two elements
a and b may be combined into a third, written a⋅b) satisfying
the three conditions of associativity, identity and invertibility.
Explicitly, these conditions are
 for all a, b, c in G, a⋅(b⋅c) = (a⋅b)⋅c (associativity)
 there exists an element e of G such that for all a in G e⋅a = a (identity)
 to every a in G there corresponds an inverse element (also in G), denoted
a^{1}, such that a^{1}⋅a = e (where e is the 'identity element' mentioned in 2) (invertibility)
Exercise for the reader: prove
 (i) that if a^{1} is determined as in 3 then also a⋅a^{1} = e;
 (ii) that a⋅e is equal to a, for all a, (as well as e⋅a);
 (iii) that the identity element is unique; and
 (iv) that the inverse of any given element is unique.
(Clue: prove first that a⋅a=a implies a=e.)
Now, a CLalgebra is certainly not a group if one uses the usual law of combination
as the group law. It passes the test of associativity; and has an identity element (the
empty expression); but hardly any elements have an inverse. In fact ab=_ implies
b = _b = abb = ab = _ and therefore a = _ ; so the identity element is the only element
to have an inverse (itself).
However, if we use instead what we have called the 'equivalence expression involving
a and b' for the combination of a and b, we find, somewhat miraculously, that we have a group
on our hands. Recall the definition
[ab] = (a(b))((a)b).
When a and b stood for circleandletter expressions, [ab] was a third expression, fashioned out
of a and b, with the property that if it was equivalent to _ , then a and b must be mutually equivalent (and conversely, if a = b, then [ab] = _ ).
In the present context, [ab] is simply a third element of the algebra (the result of
performing a sequence of operations on a and b, as determined by the definition of [ab]). The same argument as before 
just reinterpreted in the new context  tells us that
if [ab]= _ , then a=b.
(i) the group law is associative, as already shown in 'Development of the Equivalence Expression'. We recall
[a[bc]] = (ab(c)) (a(b)c) ((a)bc) ((a)(b)(c)),
an expression that is symmetrical in the three letters.
(ii) the group law is commutative, into the bargain (a⋅b=b⋅a).
(iii) _ serves as the identity (i.e. the same element that plays the role of 1 in the
Boolean Algebra). For
[ a] = ( (a)) (( )a) = a _ = a .
(iv) Every element a serves as its own inverse:
[aa] = (a(a)) ((a)a) = _ .
The order of a group element a is the least integer n such that
a^{n} = a⋅a ... ⋅a (n times) = a.
In the group made out of the CLalgebra, every element apart from _ has order 2.
The order of the group itself, written G, is the number of elements in G.
The following is a theorem of group theory:
Cauchy's theorem: If G is finite, and if a prime number p is a divisor of G, then G has at least one element
of order p.
Proof: see below
Applying the theorem to the group made out of the CLalgebra, we see that no prime number apart
from 2 can divide G: therefore G is a power of 2, in other words
G = 2^{N}
for some N.
Proof of Cauchy's Theorem [1]
Let X be the set of ptuples of Gelements, such that the product of the components equals the identity element. That is,
X = {(a_{1},a_{2},...a_{p}) with a_{i} in G, i=1...p, such that a_{1}a_{2}...a_{p}=e}.
How many such ptuples are there? We note that the first p1 components may be freely chosen, then a_{p} is determined by the condition
(a_{1}a_{2}...a_{p1})a_{p} = e
In other words, a_{p} must be the right inverse of a_{1}a_{2}...a_{p1}. So
X = number of elements in X = G^{p1}.
Given an element x of X, let Rx stand for the ptuple
(a_{p},a_{1},a_{2},...a_{p1}).
That is, Rx is obtained from x by shifting each component to the right, except the last component, which is recycled back to the first place.
Let R^{2}x stand for R(Rx), the result of applying the operation R twice to x. This will have the effect of shifting each component of x two places to the right, with components going back to the beginning when they fall off the end. The same with R^{n}x, for any integer n; but we note that R^{p}x = x, and in general
R^{n}x = R^{n(mod p)}x.
We make the important observation that Rx is a member of X, as
a_{p}(a_{1}a_{2}...a_{p1}) = 1
because a_{p}, being the right inverse of a_{1}a_{2}...a_{p} also works as its left inverse (see the exercise for the reader, just after the statement
of the group axioms, above).
This implies, further, that R^{n}x belongs to X for all n.
Lemma: The Xelements x, Rx, R^{2}x, ... R^{p1}x are either all the same or all different.
Proof: Suppose that R^{i}x = R^{j}x, with 0≤j<i<p. Then acting by R^{pi} on both sides of the equation, we obtain
R^{p}x = R^{pi+j}x,
so
x = R^{k}x
with k=p(ij). Acting on both sides of this equation by R^{k}, repeatedly, we get
x = R^{k}x = R^{2k}x = R^{3k}x = ... = R^{(p1)k}x.
But when reduced modulo p the indices {k,2k,3k,4k...(p1)k} are transformed into a permutation of the set {1,2,3,... p1}, therefore,
R^{i}x=R^{j}x implies x = Rx = R^{2}x = ... = R^{p1}x,
which proves the lemma ◊
We note that x=Rx implies
a_{1}=a_{2}, a_{2}=a_{3}, ... a_{p}=a_{1},
In other words, x has the form
(a,a,a...a),
for some a in G. For x to belong to X, it must be the case that a^{p}=e.
Next, define an equivalence relation ∼ on X, as follows:
x∼y iff y can be obtained from x by a rotation (i.e. y=R^{n}x for some n, 0≤n<p).
By the Lemma, each equivalence class has either p members or just one.
Now, suppose that G contains no element of order p. Then the only Gelement whose p^{th} power is e, is e itself. Therefore there is just one equivalence class with only one member, that one member being
(e,e,e...e).
All the other equivalence classes have p members. Suppose there are m of these classes. Then
X = 1 + pm.
Therefore p does not divide X, and a fortiori p does not divide G (since X=G^{p1}).
Therefore, if p does divide G, then G must contain at least one element of order p. (In fact, the number of elements of order p must be one less than a multiple of p.) ◊
Note: If G is a commutative group (as it is in the case of a CLAlgebra with group law []),
the proof can be slightly shortened. For now, if x belongs to X, so does any ptuple
that is the result of permuting the components of x =
(a_{1}, a_{2}, ... a_{p}).
For our equivalence relation we may now take x∼y iff y arises as a permutation of x.
If all the components of x are different, then the number of elements in the equivalence class,
to which x belongs is p!. If some of the components are the same, the number of elements is fewer,
as some permutations lead to repeats. If a_{1} appears m_{1} times
in the ptuple; and a_{2} appears m_{2} times; and so on up
to a_{k}, appearing m_{k} times; with
m_{1}+m_{2}+ ... +m_{k} = p ,
then the number of elements in the equivalence class is
p!/(m_{1}!×m_{2}! ... ×m_{k}!) ;
an integer, which will always be divisible by p (because p cannot be a factor of the
denominator), except
in the case that the ptuple consists of just one Gelement, repeated p times.
Therefore, the cardinality of each equivalence class is either 1, or a multiple of p.
From here the argument proceeds as before.
Reference
[1] The proof of Cauchy's theorem given here is
essentially a rehash of the proof to be found at
ProofWiki.
on to Huntington's Axiom
back to The number of elements in a finite Boolean Algebra
home 
Table of Contents
