### 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

1. for all a, b, c in G, a⋅(b⋅c) = (a⋅b)⋅c (associativity)
2. there exists an element e of G such that for all a in G e⋅a = a (identity)
3. 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)

• (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 CL-algebra 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

[a|b] = (a(b))((a)b).

When a and b stood for circle-and-letter expressions, [a|b] 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 [a|b] = _ ). In the present context, [a|b] 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 [a|b]). The same argument as before - just reinterpreted in the new context - tells us that if [a|b]= _ , then a=b.

(i) the group law is associative, as already shown in 'Development of the Equivalence Expression'. We recall

[a|[b|c]] = (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:

[a|a] = (a(a)) ((a)a) = _ .

The order of a group element a is the least integer n such that

an = a⋅a ... ⋅a (n times) = a.

In the group made out of the CL-algebra, 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 CL-algebra, we see that no prime number apart from 2 can divide |G|: therefore |G| is a power of 2, in other words

|G| = 2N

for some N.

Proof of Cauchy's Theorem 

Let X be the set of p-tuples of G-elements, such that the product of the components equals the identity element. That is,

X = {(a1,a2,...ap) with ai in G, i=1...p, such that a1a2...ap=e}.

How many such p-tuples are there? We note that the first p-1 components may be freely chosen, then ap is determined by the condition

(a1a2...ap-1)ap = e

In other words, ap must be the right inverse of a1a2...ap-1. So

|X| = number of elements in X = |G|p-1.

Given an element x of X, let Rx stand for the p-tuple

(ap,a1,a2,...ap-1).

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 R2x 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 Rnx, for any integer n; but we note that Rpx = x, and in general

Rnx = Rn(mod p)x.

We make the important observation that Rx is a member of X, as

ap(a1a2...ap-1) = 1

because ap, being the right inverse of a1a2...ap 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 Rnx belongs to X for all n.

Lemma: The X-elements x, Rx, R2x, ... Rp-1x are either all the same or all different.

Proof: Suppose that Rix = Rjx, with 0≤j<i<p. Then acting by Rp-i on both sides of the equation, we obtain

Rpx = Rp-i+jx,

so

x = Rkx

with k=p-(i-j). Acting on both sides of this equation by Rk, repeatedly, we get

x = Rkx = R2kx = R3kx = ... = R(p-1)kx.

But when reduced modulo p the indices {k,2k,3k,4k...(p-1)k} are transformed into a permutation of the set {1,2,3,... p-1}, therefore,

Rix=Rjx implies x = Rx = R2x = ... = Rp-1x,

which proves the lemma ◊

We note that x=Rx implies

a1=a2, a2=a3, ... ap=a1,

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 ap=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=Rnx 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 G-element whose pth 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|p-1).

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 CL-Algebra with group law [|]), the proof can be slightly shortened. For now, if x belongs to X, so does any p-tuple that is the result of permuting the components of x = (a1, a2, ... ap).

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 a1 appears m1 times in the p-tuple; and a2 appears m2 times; and so on up to ak, appearing mk times; with

m1+m2+ ... +mk = p ,

then the number of elements in the equivalence class is

p!/(m1!×m2! ... ×mk!) ;

an integer, which will always be divisible by p (because p cannot be a factor of the denominator), except in the case that the p-tuple consists of just one G-element, 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

 The proof of Cauchy's theorem given here is essentially a re-hash of the proof to be found at ProofWiki.