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)

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

aⁿ = 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| = 2^N

for some N.

Proof of Cauchy's Theorem [1]

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 = {(a₁,a₂,...a_p) with a_i in G, i=1...p, such that a₁a₂...a_p=e}.

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

(a₁a₂...a_p-1)a_p = e

In other words, a_p must be the right inverse of a₁a₂...a_p-1. So

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

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

(a_p,a₁,a₂,...a_p-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 R²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ⁿx, for any integer n; but we note that R^px = x, and in general

Rⁿx = R^{n(mod p)}x.

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

a_p(a₁a₂...a_p-1) = 1

because a_p, being the right inverse of a₁a₂...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ⁿx belongs to X for all n.

Lemma: The X-elements x, Rx, R²x, ... R^p-1x are either all the same or all different.

Proof: Suppose that Rⁱx = R^jx, with 0≤j<i<p. Then acting by R^p-i on both sides of the equation, we obtain

R^px = R^p-i+jx,

so

x = R^kx

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

x = R^kx = R^2kx = R^3kx = ... = 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,

Rⁱx=R^jx implies x = Rx = R²x = ... = R^p-1x,

which proves the lemma ◊

We note that x=Rx implies

a₁=a₂, a₂=a₃, ... a_p=a₁,

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ⁿ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 G-element 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|^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 = (a₁, a₂, ... 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₁ appears m₁ times in the p-tuple; and a₂ appears m₂ times; and so on up to a_k, appearing m_k times; with

m₁+m₂+ ... +m_k = p ,

then the number of elements in the equivalence class is

p!/(m₁!×m₂! ... ×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 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

[1] The proof of Cauchy's theorem given here is essentially a re-hash 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