Theorem: Let K be a set with unary operation ' ; and binary operation ∧ which is
associative and commutative; suppose the operations are
constrained by the following rule:
for all a, b in K, a = (a'∧b)' ∧ (a'∧b')'.
Then K is a CL-algebra.
Proof: Since ∧ is associative and commutative, it can be converted into
a (permutable, dissociative)
law of combination which is applicable to any finite set of K-elements.
We may adopt the circle-and-letter notation for combination and complementation,
so the axiomatic equation becomes
a = ((a)b) ((a)(b)).
The step from left to right we may term expand (with accessory element b);
the step from right to left, contract.
Note that Huntington does not assume the existence of a unit-element 1 (such that 1∧a=a for all
a), so we cannot assume at this stage that the empty expression corresponds to an
element of K. The
existence of 1 is something that must be proved.
The first, crucial step is the following:
Lemma 1: Let a and b be any two elements of K. Then
a(a) = b(b).
Proof: We expand a and (a), using (b) as the accessory element, each time. This is the result:
The resulting expression can be contracted in a different way, yielding the result
Corollary: Choose any K-element a; then a(a) is also a K-element; let it be
denoted Z. Then if b
is any K-element,
b(b) = Z .
Z(Z) = Z
ZZ(ZZ) = Z ,
for ZZ, the combination of Z with Z, is also an element of K.
Lemma 2: for all a in K, ((a)) = a .
Proof: We expand a, using ((a)) as accessory, and ((a)), using (a) as accessory. The result:
a = ( (a)((a)) ) ( (a)(((a))) ) = Z ( (a)(((a))) )
((a)) = ( (((a))) (a) ) ( (((a))) ((a)) ) = ( (((a))) (a) ) Z .
Thus a and ((a)) are equal to the same element; so are themselves equal ◊
Corollary: we have the following variant of expand/contract:
(a) = (ab) (a(b)).
Proof: expand (a) using b as accessory; then use Lemma 2 to turn ((a)) into a,
Lemma 3: (Z) = (Z)(Z).
Proof: Expand (Z), using Z as accessory:
(Z) = (ZZ) (Z(Z))
Reduce (Z(Z)) to (Z), by example 1, and combine each side with ZZ
(this is an example of embedding):
ZZ(Z) = ZZ(ZZ) (Z)
= Z (Z) [by example 2]
= Z [by example 1].
The left hand side can be replaced by ZZ, by example 1, so we have
ZZ = Z.
Now return to the expansion of (Z):
(Z) = (ZZ) (Z(Z)) = (Z)(Z)
Lemma 4: For all a in K, a(Z) = a. Thus (Z) has the unit-property.
Proof: Expand (a(Z)), using Z as accessory:
(a(Z)) = (a(Z)Z) (a(Z)(Z))
= (aZ) (a(Z)) [by example 1, and by Lemma 3]
= (a) [by contraction] .
The result follows by embedding each side of the equation in a circle ◊
Lemma 5: For all a in K, aa = a.
Proof: expand (a), using a as accessory:
(a) = (aa) (a(a))
= (aa) (Z)
= (aa) [by Lemma 4].
Therefore, circling both sides,
a = aa.
Lemma 6: for all a in K, aZ = Z. Thus, Z has the zero property.
aZ = aa(a) = a(a) = Z ◊
Lemma 7: for all a and b in K, a(b) = a(ab).
Proof: expand a, using b as accessory; and (b), using a as accessory:
a(b) = ((a)b) ((a)(b)) (ba) (b(a)).
The term ((a)b) occurs twice; by Lemma 5, the second occurrence may be blanked out. So
a(b) = ((a)b) ((a)(b)) (ba)
= a (ab) ,
by contraction ◊
Now, by Lemma 4, (Z) has the unit-property, which implies that the empty expression
may be taken to represent the element (Z).
It will be seen that Lemmas 2, 6 and 7, respectively, are the wrap
, delete and copy
constraints. Therefore K with its operations may be converted into a CL-algebra ◊
Corollary: K may be further converted into a Boolean Algebra.
Huntington’s equation used to initialize
Theorem: Within the world of circle-and-letter expressions, let the following
equation be granted
A = ((A)B) ((A)(B)) .
Here any expression can be substituted for A; any expression can be substituted for B;
including, naturally, in both cases the empty expression. (The effect of substituting _
for a letter is the same as the effect of taking a rubber and rubbing out that letter,
everywhere it appears in the equation.) The resulting calculus of expressions is identical
with the CL-calculus generated by the three initial equations of Bricken.
Proof: As above, we prove a series of lemmas.
Lemma 1: from the axiom, it follows that for all A and B
The proof is formally identical to the proof of Lemma 1 above.
Corollary: A(A) = O
Proof: just substitute _ for B in Lemma 1.
Lemma 2: for all expressions A, ((A)) = A ; proof as above.
Instance: substituting _ for A, (O) = _ .
Corollary: (A(A)) = (O) = _ .
We may now go straight to
Lemma 5: Let A be any expression. Then AA=A .
Proof: In the expression ((A)) expand (A), with A as accessory:
A = ((A)) = ( (AA) (A(A)) ) = ((AA)) = AA.
Lemma 6: AO = AA(A) = A(A) = O ◊
Lemma 7: A(B) = A(AB) ; proof as above.
Thus all three Bricken initials follow from Huntington’s equation; we already know
that the converse is true, therefore the calculus generated by Huntington's equation
is identical with the usual calculus of circles and letters◊
It is worth contemplating the similar, but distinct tasks accomplished in the
two parts of this page. In the first part, we started with a set and two
operations, combination and complementation, mapping the set to itself. Huntington's
as a constraint on the operations. Our concern
was to prove that Huntington's constraint implied the usual ones that lead to a
Boolean Algebra. In the second part,
we started with a world of CL expressions. Again there was an operation of combination (i.e.
write the expressions side by side); and an operation of complementation (i.e. encircle
the expression). But the operations were unconstrained. The axiomatic equation
constrain them, but introduced something new, namely an equivalence relation between
expressions. This time, our task was to prove
that the equivalence relation arising out of Huntington's equation was
the same as the equivalence relation arising out of the usual Bricken initials.
Shortly after Huntington proved that his axiom led to Boolean Algebra, in 1933, the mathematician Herbert
Robbins conjectured that the somewhat similar equation (also true in Boolean Algebras)
a = ((ab)(a(b))
would do instead. Huntington and Robbins soon found that the conjecture was not at all easy
Huntington's proof is no good because the right-hand side of the equation does not split into the
combination of two factors. The problem was later taken up by Tarski and his students (according to
William McCune's web page
'Robbins Algebras are Boolean'
) - but continued to prove intractable, until
automatic theorem-proving computer programs were brought to bear on it, starting in the 1980's. Various
additional conditions were discovered, by S.Winker, which together with the Robbins axiom (and
commutativity and associativity) would ensure that the Boolean axioms followed as a consequence.
So henceforth the task was to prove that one of these additional conditions was itself a consequence
of the Robbins axiom. But this was easier said than done, even with the help of machines, and it
was not until 1997 that McCune succeeded. (In fact his machine could even do it without resort
to Winker's conditions - for details follow the link given above.)
Various people have worked to transform the machine-generated proofs into human-friendly proofs.
My own attempt at this task is here:
'A human-friendly proof of the Robbins Conjecture'.
I have made use here of the article
Robbins Algebra by Louis H. Kauffman, as well as the original articles by
Trans. Amer. Math. Soc. 5 (1904), 288-309
Trans. Amer. Math. Soc. 35 (1933), 274-304
Trans. Amer. Math. Soc. 35 (1933), 557-558
The calculus of circles and letters
Table of Contents