Equational Theories

4 Implications between selected laws

We collect here some notable implications between the the selected laws in Chapter 2. By Theorem 1.8, every implication can basically be established by a finite number of rewrites. In most cases, the sequence of rewrites is quite straightforward, and the implication is very easy, but we record some less obvious examples.

Theorem 4.1 387 implies 43

E387 \((x \diamond y = (y \diamond y) \diamond x)\) implies E43 \((x \diamond y = y \diamond x)\).

Proof

(From MathOverflow). By E387, one has the law

\begin{equation} \label{387-again} (x \diamond x) \diamond y = y \diamond x. \end{equation}
1

Specializing to \(y=x \diamond x\), we conclude

\[ (x \diamond x) \diamond (x \diamond x) = (x \diamond x) \diamond x \]

and hence by another application of E387 we see that \(x \diamond x\) is idempotent:

\begin{equation} \label{idem} (x \diamond x) \diamond (x \diamond x) = x \diamond x. \end{equation}
2

Now, replacing \(x\) by \(x \diamond x\) in Equation 1 and then using Equation 2 we see that

\[ (x \diamond x) \diamond y = y \diamond (x \diamond x) \]

so in particular \(x \diamond x\) commutes with \(y \diamond y\):

\begin{equation} \label{op-idem} (x \diamond x) \diamond (y \diamond y) = (y \diamond y) \diamond (x \diamond x). \end{equation}
3

Also, from two applications of Equation 1 one has

\[ (x \diamond x) \diamond (y \diamond y) = (y \diamond y) \diamond x = x \diamond y. \]

Thus Equation 3 simplifies to \(x \diamond y = y \diamond x\), which is E43.

Theorem 4.2 29 equivalent to 14

E29 \((x = (y \diamond x) \diamond y))\) is equivalent to E14 \((x = y \diamond (x \diamond y)))\).

This result was posed as Problem A1 from Putnam 2001.

Proof

By Lemma 3.5 it suffices to show that E29 implies E14. From E29 one has

\[ x = ((x \diamond y) \diamond x) \diamond (x \diamond y) \]

and also

\[ y = (x \diamond y) \diamond x \]

giving \(x = y \diamond (x \diamond y)\), which is E14.

Theorem 4.3 14 implies 29

E14 implies E29.

This result was posed as Problem A1 from Putnam 2001.

Proof

The following result was Problem A4 on Putnam 1978.

E3744 \((x \diamond y = (x \diamond z) \diamond (w \diamond y))\) implies E3722 \((x \diamond y = (x \diamond y) \diamond (x \diamond y))\) and E381 \((x \diamond y = (x \diamond z) \diamond y)\).

Proof

By hypothesis, one has

\[ x \diamond y = (x \diamond z) \diamond (w \diamond y) \]

for all \(x,y,z,w\). Various specializations of this give

\begin{align} x \diamond y & = (x \diamond z) \diamond (y \diamond y) \label{381-1} \\ x \diamond z & = (x \diamond z) \diamond (x \diamond z) \label{381-2} \\ (x \diamond z) \diamond y & = ((x \diamond z) \diamond (x \diamond z)) \diamond (y \diamond y) \label{381-3}. \end{align}

5 gives E3722, while Equation 4, 5, 6 gives

\[ x \diamond y = (x\diamond z) \diamond y \]

which is E381.

Theorem 4.5 1689 is equivalent to 2

E1689 \((x = (y \diamond x) \diamond ((x \diamond z) \diamond z))\) is equivalent to E2.

Proof

The implication of E1689 from E2 is trivial. The converse is a surprisingly long chain of implications; see pages 326–327 of [ 5 ] . With some computer assistance, we found the following human-readable proof. We denote \(y^1=y\) and \(y^{n+1}=y^n\diamond y\) for \(n\geq 1\). We also introduce the notation

\begin{equation} f(x,y) = (x \diamond y) \diamond y , \qquad g(x,y) = x\diamond f(x,y) = x \diamond ((x \diamond y) \diamond y) . \end{equation}
7

The initial equation states \(x = (y \diamond x) \diamond f(x,z)\). Our main step will be to prove that for all \(t\in M\) there exists \(w\in M\) such that \(f(t,w) = t\). The rest of the proof is then straightforward. Indeed, the initial equation gives \(t = (y \diamond t) \diamond f(t,w) = (y \diamond t) \diamond t = f(y,t)\) for any \(t,y\in M\). With such a simple expression of \(f\) the initial equation becomes \(x = (y \diamond x) \diamond z\), which easily implies the singleton law, for instance by writing \(x = ((y \diamond w) \diamond x) \diamond z = w \diamond z\) for any \(w,x,y,z \in M\).

There remains to prove \(f(t,w) = t\) for a well-chosen \(w \in M\), explicitly, \(w=g(t,t^5)=t\diamond t^7\). For any \(t,u,v \in M\), the combinations \(x = f(t,u)\) and \(y = v \diamond t\) satisfy \(y \diamond x = t\). Inserting these values into the initial equation yields the identity

\begin{equation} \label{Kisielewicz-tfftuz} f(t,u) = t \diamond f(f(t,u),z) . \end{equation}
8

Specialize to \(z=f(u,v)\) and note that \(f(t,u) \diamond z = (\cdots \diamond u) \diamond f(u,v) = u\) by the initial equation so that \(f(f(t,u),z) = (f(t,u) \diamond z) \diamond z = u \diamond z = g(u,v)\). Inserting this into 8 yields

\begin{equation} \label{Kisielewicz-ftg} f(t,u) = t \diamond g(u,v) . \end{equation}
9

On the one hand, 8 with \(z=u=t\) states that \(t^3 = t \diamond t^5\), so (using \(f(t^n,t)=t^{n+2}\))

\begin{equation} f(t,t^5) = (t \diamond t^5) \diamond t^5 = t^3 \diamond t^5 = t^3 \diamond f(t^3,t) = g(t^3,t) , \end{equation}
10

and 9 with \((u,v)=(t^3,t)\) then implies \(f(t,t^3) = t \diamond g(t^3,t) = t \diamond f(t,t^5) = g(t,t^5)\). On the other hand, 9 with \((u,v)=(t,t^5)\) implies \(t^3 = t \diamond g(t,t^5)\). We deduce

\begin{equation} f(t,g(t,t^5)) = (t \diamond g(t,t^5)) \diamond g(t,t^5) = t^3 \diamond f(t, t^3) = (\cdots \diamond t) \diamond f(t,\dots ) = t . \end{equation}
11

The following result was established in [ 11 ] .

Magmas satisfying E1571 \((x = (y \diamond z) \diamond (y \diamond (x \diamond z)))\) also satisfy E2662, E40, E23, E8, E16, E14, E43, and E4512, and are in fact abelian groups of exponent two. Conversely, all abelian groups of exponent two satisfy E1571.

Proof

Suppose that a magma \(G\) satisfies E1571, thus

\begin{equation} \label{1571-again} x = (y \diamond z) \diamond (y \diamond (x \diamond z)). \end{equation}
12

\[ x = ((x \diamond y) \diamond (x \diamond y)) \diamond ((x \diamond y) \diamond (x \diamond (x \diamond y))) \]

and

\[ x = (x \diamond y) \diamond (x \diamond (x \diamond y)) \]

whence

\[ x = ((x \diamond y) \diamond (x \diamond y)) \diamond x \]

which is E2662. This gives

\[ y = ((y \diamond z) \diamond (y \diamond z)) \diamond y \]

while from Equation 12 one has

\[ (y \diamond z) \diamond (y \diamond z) = (x \diamond y) \diamond (x \diamond ((y \diamond z) \diamond (y \diamond z) \diamond y)) \]

whence

\[ (x \diamond y) \diamond (x \diamond y) = (y \diamond z) \diamond (y \diamond z). \]

This implies that \((x \diamond y) \diamond (x \diamond y)\) does not depend on \(x\), or on \(y\), hence is equal to some constant \(e\):

\[ (x \diamond y) \diamond (x \diamond y) = e. \]

From Equation 12 the magma operation is surjective, hence

\begin{equation} \label{xxe} x \diamond x = e \end{equation}
13

which gives E40. Applying Equation 12 with \(x=y=z\) we conclude

\[ x = e \diamond (x \diamond e) \]

while if we instead take \(y=z=e\) we have

\[ x = e \diamond (e \diamond (x \diamond e)) \]

hence

\[ x = e \diamond x \]

and then also

\[ x = x \diamond e \]

from which we readily conclude E23, E8; thus \(e\) is an identity element. From Equation 12 with \(z=e\) we now have

\begin{equation} \label{16-again} x = y \diamond (y \diamond x) \end{equation}
14

which is E16. If instead we take \(y=e\) we have

\begin{equation} \label{14-again} x = z \diamond (x \diamond z) \end{equation}
15

which is E14. So if we substitute \(z = x \diamond y\) and use Equation 14 we obtain

\[ x = (x \diamond y) \diamond y \]

and hence

\[ y \diamond x = y \diamond ((x \diamond y) \diamond y) = x \diamond y \]

thanks to Equation 15. This gives E43, thus \(G\) is now commutative. From Equation 12 once more one has

\[ x \diamond (y \diamond z) = (y \diamond x) \diamond (z \diamond ((x \diamond (y \diamond z)) \diamond x)) \]

which one can simplify using commutativity and Equation 14 (or Equation 15) to eventually obtain

\[ x \diamond (y \diamond z) = (x \diamond y) \diamond z \]

which is E4512. \(G\) is now commutative and associative, and every element is its own inverse and of exponent \(2\), hence is an abelian group thanks to Equation 13, so \(G\) is an abelian group of exponent \(2\) as claimed. The converse is easily verified.

Theorem 4.7 953 is equivalent to 2

E953 \((x = y \diamond ((z \diamond x) \diamond (z \diamond z)))\) is equivalent to E2.

Proof

It suffices to show that E953 implies E2. Pick an element \(0\) of \(G\) and define \(1 = 0 \diamond 0\) and \(2 = 1 \diamond 1\) (we do not require \(0,1,2\) to be distinct). From E953 with \(x=z=0\) we have

\[ 0 = y \diamond 2. \]

If we then apply E953 with \(z=1\) we conclude that

\[ x = y \diamond 0 \]

for all \(x,y\), from which one concludes \(x=x'\) for any \(x,x' \in G\), giving E2.

Theorem 4.8 Sheffer stroke axiom
#

Definition E345169 \((x = (y \diamond ((x \diamond y) \diamond y)) \diamond (x \diamond (z \diamond y)))\) axiomatizes the Sheffer stroke operation \(x \diamond y = \overline{xy}\) in a Boolean algebra.

Proof

See [ 10 ] . In fact this is the shortest law with this property.

A sketch of proof follows. One can easily verify that the Sheffer stroke operation satisfies this law. Conversely, if this law holds, then automated theorem provers can show that the three Sheffer axioms

\[ (x \diamond x) \diamond (x \diamond x) = x \]
\[ x \diamond (y \diamond (y \diamond y)) = x \diamond x \]
\[ (x \diamond (y \diamond z)) \diamond (x \diamond (y \diamond z)) = ((y \diamond y) \diamond x) \diamond ((z \diamond z) \diamond x) \]

are satisfied. A classical result of Sheffer [ 12 ] then allows one to conclude.

A natural central groupoid is, up to isomorphism, a magma with carrier \(S \times S\) for some set \(S\) and operation

\[ (a,b) \diamond (c,d) = (b,c). \]

These are examples of central groupoids, E168 \((x = (y \diamond x) \diamond (x \diamond z))\).

Theorem 4.9 Natural central groupoid axiom

E26302 \((x = (y \diamond ((z \diamond x) \diamond w)) \diamond (x \diamond w))\) characterizes natural central groupoids.

Proof

See [ 7 , Theorem 5 ] . The proof is quite lengthy; a sketch is as follows. It is easy to see that natural central groupoids satisfy E26302. Conversely, if this law holds, then

\begin{align*} (y \diamond z) \diamond (z \diamond w) & = (( x \diamond ((w \diamond (y \diamond z)) \diamond w)) \diamond ((y \diamond z) \diamond w)) \diamond (z \diamond w)\\ & = z \end{align*}

so we have a central groupoid. Setting \(y = (t \diamond t) \diamond t\), \(z = t \diamond (t \diamond t)\), \(w = t \diamond t\) in E26302 we also obtain

\[ (x \diamond t) \diamond t = (t \diamond t) \diamond t. \]

Using the notation

\[ x^{(1)} := (x \diamond x) \diamond x, \quad x^{(2)} := x \diamond (x \diamond x) \]

we then have

\begin{align*} x \diamond t & = ((x \diamond x) \diamond (x \diamond t)) \diamond ((x \diamond t) \diamond t) \\ & = x \diamond t^{(1)}. \end{align*}

A lengthy computer-assisted argument then gave the dual identity

\[ t^{(2)} \diamond x = t \diamond x \]

Together, these give

\[ x^{(2)} \diamond y^{(1)} = x \diamond y. \]

Multiplying on the left by \(x = x^{(1)}\diamond x^{(2)}\), one can conclude that

\[ x^{(2)} = x \diamond (x \diamond y). \]

One then has

\begin{align*} (x \diamond y)^{(1)} & = ((y \diamond x) \diamond (x \diamond y)) \diamond (x \diamond y) \\ & = x \diamond (x \diamond y) \\ & = x^{(2)} \end{align*}

and a similar argument gives

\[ (x \diamond y)^{(2)} = y^{(1)}. \]

Since \((x \diamond x)^{(1)} = x^{(2)}\) and \((x \diamond x)^{(2)} = x^{(1)}\), we conclude that \(x^{(1)}\) and \(x^{(2)}\) are idempotent. Since \(x = x^{(1)} \diamond x^{(2)}\), we see that every \(x\) is the product of two idempotents. One can show that this representation is unique, and gives a canonical identification with a natural central groupoid.