Huntington's Axiom
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
b(b) ◊
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 .
Example 1:
Z(Z) = Z
Example 2:
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, twice ◊
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.
Proof:
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
the CL-Calculus
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
A(A)=B(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 equation acted 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 did not 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 to prove. 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'.
Note
I have made use here of the article
Robbins Algebra by Louis H. Kauffman, as well as the original articles by
Huntington:
Trans. Amer. Math. Soc. 5 (1904), 288-309
Trans. Amer. Math. Soc. 35 (1933), 274-304
Trans. Amer. Math. Soc. 35 (1933), 557-558
back to
The calculus of circles and letters
back to CL-Algebras