a human-friendly proof

A Robbins Algebra is defined to be an algebra A with a binary operation . and a unary operation ' such that for any elements x, y and z

x.y = y.x

x.[y.z] = [x.y].z

x = [[x.y]'.[x.y']']'

The first two axioms say that the binary operation is commutative and associative, implying that any n elements of A may be combined into an n-fold 'combination' where neither the order of the elements, nor the manner in which they are bracketed together, makes any difference to the final result.

The third axiom is similar to Huntington's third axiom for a Boolean algebra, which would read:

x = [x'.y]'.[x'.y']'

If it were known that x'' must equal x, the two conditions would indeed be equivalent. Not knowing that, the question, whether or not Robbins' three axioms imply that A is a Boolean algebra, is a more subtle one. Indeed, the question remained open for many years after Robbins first posed it, and was in the end settled (affirmatively) only with the help of a computer that was able to seek out algebraic proofs in a mechanical fashion (McCune, 1997).

Various people got the proof into a more human-friendly form; Kauffman (c.2001) did so using Laws of Form notation. These pages are based on Kauffman's work, but considerably simplified. No very complicated expressions arise in the course of the proof.

For present purposes, 'Laws of Form notation' means that the n-fold product is written simply by juxtaposing the elements, thus:

abcd....hij represents a.b.c.d. ... h.i.j

and the unary operation is indicated by brackets, thus:

(a) represents a'.

Any pair of brackets should be thought of synecdochically as representing a circle, enclosing the contents of the brackets. Henceforth brackets will not be used merely for grouping elements together, or for indicating the order in which elements are to be combined. There is no need for either of these functions. Brackets will always signify that the unary operation is to be performed on a combination of elements; those elements, namely, that are enclosed by the brackets.

We will use exponents as follows:

a^{n} = aaa ... a = a.a.a. ... a (n times).

Another bit of notation will be useful: let a + b stand for the expression

((a)(b)) ;

then the Robbins axiom says that for all a and b

a = ab + a(b).

We will refer to this equation as R.

If (b) = (c), then a+b = a+c ; we don’t have to know that b = c (a stronger premise).

Our goal is to prove the following

Every Robbins Algebra is a Boolean Algebra.

We will break down the proof into easy stages, making use of three lemmas. Both of the first two are due, essentially, to Winker (Winker, 1992), although only the first was stated by him. The third is based on the original computer-aided work of McCune as transcribed by Kauffmann. Thanks to the use of Lemma 2 this part of the proof is much shorter than in the original work. There is no great obstacle to human understanding of it; perhaps, given enough time, an unaided human might have been able to find it - although that must remain a matter of the purest speculation!

If an element e of A is idempotent (that is to say, ee = e), then A is Boolean.

(based on Winker (1992), but shorter)

1. ee = e (premise)

2. Let z = e(e), and let u = (z) = (e(e))

3. ez = ee(e) by 2

= e(e) by 1

= z by 2

4. e = ee + e(e) by R

= e + z

= ((e)(z)) by definition of +

= ((e)u)

5. (e) = (e)z + (e)u by R

=(((e)z)e) by 4

6. e = e(e)z + e((e)z)

= (e)z + e by 3 and 5, and using the remark after the definition of +

= (((e)z)(e))

7. ((e)z) = ((e)z)e + ((e)z)(e)

= e + ((e)z)(e) by 4

= ((e)e) by 6

= u

8. By 5 and 7,

(e) = (((e)z)e) = (ue)

9. eu = eue + eu(e)

= eu + eu(e) by 1

= e + eu(e) by 8, and using remark after definition of a + b

= ee + eu(e) by 1

= e(u(e)) + eu(e) by 5

= e by R

10. By 9 and 4,

ue = e = (u(e))

11. Let x be any element of A; then

xu = xue + xu(e)

= x(u(e)) + xu(e) by 10

= x by R

Thus u has the unit property, and may therefore be represented by the void expression: that is to say, we may write

(e(e)) = _ .

But that is only the beginning! Let x be any element of A; then there exists a y such that x = (y). For instance, we may take y = (xx)(x(x)), for by R

x = xx + x(x) = ((xx)(x(x))) = (y) .

Now again by R

_ = _ y + _ (y) = y + (y) = ((y)((y))) = (x(x)) ;

and this is true for any element x.

We now prove the ‘wrap axiom’: for all x,

((x)) = x.

We first note

x = x(x) + x((x))

= ( _ (x((x))) = ((x((x))));

secondly,

((x)) = ((x))x + ((x))(x)

= ( ( ((x))x ) ( ((x))(x) ) )

= (( ((x))x ) _ ))

= x.

'Wrap' allows us to convert the Robbins axiom into the Huntington axiom:

x = ((x)) = ( (x)y + (x)(y) ) = ( (((x)y))((x)(y))) ) = ((x)y)((x)(y)).

The Huntington axiom implies that A is Boolean; therefore, so does the Robbins axiom.

In summary, if e is idempotent, then (e(e)) has the unit property, and the algebra A is Boolean.

Alternatively, having established the wrap axiom, we may proceed more directly [1]. We note firstly that

x = xx + x(x) = ((xx)(x(x))) = ((xx)_) = xx,

so all elements are idempotent.

Next, if x is any element,

O = ( ) = ((x(x))) = x(x);

therefore,

Ox = x(x)x = x(x) = O.

This is the ‘delete’ axiom. Note also:

x + O = ((x)(O)) = ((x)_) = ((x)) = x .

We may prove ‘copy’ in three steps, as follows:

1. ab = aba(b) + ab(a(b))

= O + ab(a(b))

= ab(a(b))

2. (a(b)) = (a(b))ab + (a(b))(ab)

= ab + (a(b))(ab) by 1

= ( (ab) ((a(b))(ab)) ) by definition of +

= ((ab)a) by R

3. a(b) = a(ab) by wrap.

‘Wrap’, ‘delete’, and ‘copy’ (together with existence of a unit) suffice to establish that the algebra is Boolean.

For the statement of Lemma 2 it is convenient to make a new definition. We will say that two elements a and b are *conjugate through c* (where c is a third element), if and only if

a = (b(c)) and b = (a(c)).

If elements a and b are conjugate through c, then

a^{2}b^{2}c = a^{3}b^{3}c.

The proof is essentially a reworking of material in Winker (1992). We proceed by proving first a useful rule, or couple of rules, then a series of smaller lemmas.

If a = (b(c))

then a = (b(abc)).

We expand a using bc:

a = abc + a(bc)

= abc + (b(c))(bc) by the premise

= ((abc)b) by definition of +, and by R.

If a = (bc)

then a = (b(ab(c))).

The proof is similar to the proof just given.

If a and b are conjugate through c, then, for any non-negative integer k,

(c) = (a^{k}b^{k}c).

Since a = (b(c)), the ABC-rule may be applied, giving

a = (b(abc)).

Now the rule may be applied again (with abc playing the role of c), giving

a = (b(a^{2}b^{2}c)).

Plainly the step may be repeated as often as is desired, so that

a = (b(a^{k}b^{k}c))

for any positive integer k.

Similarly, from

b = (a(c))

we may deduce

b = (a(a^{k}b^{k}c)).

Now let j be another non-negative integer, and let us introduce the notation

c_{j} = a^{j}b^{j}c.

Then

(c_{j}) = (c_{j})a(c_{k}) + (c_{j})(a(c_{k}))

= (c_{j})a(c_{k}) + (c_{j})b , by the above

= (((c_{j})a(c_{k}))((c_{j})b)) by definition of +

= (((c_{j})a(c_{k}))a) by the above.

But (c_{k}) can be turned into exactly the same expression, symmetrical in j and k, therefore

(c_{j}) = (c_{k}).

In particular, (c_{k}) = (c), which proves the lemma.

Suppose (c) = (cd^{j}), for all non-negative j. Let m,n be integers with
m > n > 0. Then

(c) = (cd^{m}((c)d^{n})).

Let g_{n} = (d^{n}(c)).
Then

d^{n} = d^{n}c + d^{n}(c)

= ((d^{n}c)g_{n})

= (g_{n}(c)) by the premise of the lemma.

Therefore d^{n} and g_{n} are conjugate through c; and indeed conjugate through cd^{j}, for any j. Applying Lemma 2.1, with k=1,

(cd^{j}) = (cd^{j} d^{n} g_{n})

= (cd^{j+n} ((c)d^{n})).

The left-hand side of the equation is just (c), and j may be chosen to be equal to m-n, giving

(c) = (cd^{m} ((c)d^{n})),

as required.

Suppose (c) = (cd^{k}) for all non-negative k. Then

cd^{2} = cd^{3}.

Let i,j,k be positive integers. Then

cd^{i} = cd^{i} (c)d^{k-i} + cd^{i} ((c)d^{k-1})

= c(c)d^{k} + c,

by Lemma 2.2, provided a) that k is greater than i, and b) that i is greater than or equal to k-i, which will be the case if and only if i ≥ k/2. Thus for the equation to hold, we require

k/2 ≤ i < k.

If j satisfies the same condition, then also

cd^{j} = c(c)d^{k} + c

and so

cd^{i} = cd^{j}.

For there to be two integers (i and j) satisfying the condition, k must be sufficiently large. In case k=2, only i=1 satisfies the condition; in case k=3, only i=2; but in case k=4 we have i=2 and j=3. Thus

cd^{2} = c(c)d^{4} + c = cd^{3} ,

and the lemma is proved.

Putting Lemmas 2.1, 2.2 and 2.3 together, we have a proof of Lemma 2.

If a and b are conjugate through c, and if it so happens that c is of the form a^{i}b^{j}, where i and j are any non-negative integers, then a^{n}b^{n} is idempotent, where n is 2 more than the greatest of i and j.

If c has the given form,

cd^{2} = a^{i}b^{j}a^{2}b^{2} = a^{i+2}b^{j+2}

cd^{3} = a^{i+3}b^{j+3}.

By the lemma,

a^{i+2}b^{j+2} = a^{i+3}b^{j+3}.

If i is greater than j, multiply each side by b^{i-j}, obtaining

a^{i+2}b^{i+2} = a^{i+3}b^{i+3};

if j is greater than i, obtain the same expression with i replaced by j. In either case

a^{n}b^{n} = a^{n+1}b^{n+1} = ab a^{n}b^{n}.

Clearly, the step may be repeated, so

a^{n}b^{n} = a^{N}b^{N}

where N is any integer greater than n. Choosing N=2n, we obtain

a^{n}b^{n} = a^{n}b^{n} a^{n}b^{n},

as required.

By putting together Lemma 1 and the corollary to Lemma 2, we see that to prove that a Robbins algebra A is Boolean, it suffices to come up with elements a, b and c such that a and b are conjugate through c, and c has the form a^{i}b^{j}. In the final lemma we show that A always has such elements.

Let A be a Robbins algebra, with an element x. Let y=(x(x)). Then x and y are conjugate through x^{3}y.

We make repeated use of the ABC-rule (as introduced in stage two, above), and its modification.

1. x = xx + x(x) = ((xx)y) by R and definition of y

2. x = (y(xyxx)) = (y(xxxy)) by 1 and the ABC-rule

3. (xx) = (x(y(xxxy))) by 2

= (x((xx)y(xxxy))) by the ABC-rule

4. (xxxy) = (xy xx)

= (xy((xxxy)xy(xx))) by the modified ABC-rule

5. Let g = x((xx)y(xxxy)); we see that

(xx) = (g) by 3

(xxxy) = (gy) by 4.

6. y = yg + y(g) by R

= xxxy + y(xx) by 5 and by the remark following the definition of +

= ((xxxy)x) by definition of + and by 1

7. Putting 2 and 6 together, we see that x and y are conjugate through x^{3}y.

By Lemma 3, and the corollary to Lemma 2, x^{5}y^{5} is idempotent. Therefore, by Lemma 1, A is a Boolean algebra. But there was never anything special about A: it could have been *any* Robbins Algebra. All we needed was a single element x, along with the operations, satisfying the Robbins axioms. Therefore any Robbins Algebra is in fact a Boolean Algebra. Q.E.D.

W.McCune (1997), "Solution of the Robbins Problem", Journal of Automated Reasoning 19(3), 263-276 (1997)

Preprint available for download here:

www.cs.unm.edu/~mccune/old-ftp/www-misc/robbins-jar-final.ps.gz

[To open a file of this kind (compressed PostScript) go to view.samurajdata.se]

S.Winker (1992), "Absorption and idempotency criteria for a problem in near-Boolean algebras", J. Algebra, 153(2):414-423, 1992

The article can be found in the Open Archive of the Journal of Algebra

L.H.Kauffman (c.2001), "The Robbins Problem - Computer Proofs and Human Proofs", homepages.math.uic.edu/~kauffman/Robbins.htm

See also

L.H.Kauffman (1990), "Robbins Algebra", Proceedings of the twentieth international symposium on multiple-valued logic, Charlotte, North Carolina, May 23-25, 1990

Reprint available here:

homepages.math.uic.edu/~kauffman/RobbinsAlgebra.pdf

[1] Wrap, delete and copy are my names for the three axioms

((x)) = x

O x = O

x(y) = x(xy)

which, when added to commutativity, associativity and the existence of a unit guarantee a Boolean algebra (see on this website Boolean Algebras). In the world of Laws of Form, or what I call 'the calculus of circles and letters', commutativity, associativity and unit are 'not an issue'/taken for granted. In this context the three equations are known as the Bricken Initials. They are built into the Flash program 'Circle-and-letter expression transformer'.

The Markable Mark home | contents

© George Burnett-Stuart 2014

URL of this page: http://www.markability.net/robbins.htm