Equational theories

5 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 5.1 387 implies 43
Proof

(From MathOverflow). By Definition 2.24, 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 Definition 2.24 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 Definition 2.18.

Theorem 5.2 29 equivalent to 14

Definition 2.12 is equivalent to Definition 2.9.

This result was posed as Problem A1 from Putnam 2001.

Proof

By Lemma 4.5 it suffices to show that Definition 2.12 implies Definition 2.9. From Definition 2.12 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 Definition 2.9.

Theorem 5.3 14 implies 29

This result was posed as Problem A1 from Putnam 2001.

Proof

The following result was Problem A4 on Putnam 1978.

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 Definition 2.31, while Equation 4, 5, 6 gives

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

which is Definition 2.23.

Theorem 5.5 1689 is equivalent to 2

Definition 2.29 is equivalent to Definition 2.2.

Proof

The implication of Definition 2.29 from Definition 2.2 is trivial. The converse is a surprisingly long chain of implications; see pages 326–327 of [ 3 ] . The initial law

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

is used to obtain, in turn,

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

The following result was established in [ 8 ] .

Proof

Suppose that a magma \(G\) obeys Definition 2.27, thus

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

\[ 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 Definition 2.30. This gives

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

while from Equation 7 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 7 the magma operation is surjective, hence

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

which gives Definition 2.15. Applying Equation 7 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 Definition 2.11, Definition 2.8; thus \(e\) is an identity element. From Equation 7 with \(z=e\) we now have

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

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

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

which is Definition 2.9. So if we substitute \(z = x \diamond y\) and use Equation 9 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 10. This gives Definition 2.18, thus \(G\) is now commutative. From Equation 7 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 9 (or Equation 10) to eventually obtain

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

which is Definition 2.33. \(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 8, so \(G\) is an abelian group of exponent \(2\) as claimed. The converse is easily verified.

Theorem 5.7 953 is equivalent to 2

Definition 2.26 is equivalent to Definition 2.2.

Proof

It suffices to show that Definition 2.26 implies Definition 2.2. 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 Definition 2.26 with \(x=z=0\) we have

\[ 0 = y \diamond 2. \]

If we then apply Definition 2.26 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 Definition 2.2.

Some other notable equational laws are as follows.

Theorem 5.8 Sheffer stroke axiom

The law

\[ 0 \simeq (1 \diamond ((0 \diamond 1) \diamond 1)) \diamond (0 \diamond (2 \diamond 1)) \]

or in equation form

\[ 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. TODO: locate the equation number for this law.

Proof

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

A sketch of proof follows. One can easily verify that the Sheffer stroke operation obeys 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 [ 9 ] 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 (Definition 2.22).

Theorem 5.9 Natural central groupoid axiom

The law

\[ 0 \simeq (1 \diamond ((2 \diamond 0) \diamond 3)) \diamond (0 \diamond 3) \]

or in equation form

\begin{equation} \label{26302} x = (y \diamond ((z \diamond x) \diamond w)) \diamond (x \diamond w) \end{equation}
11

(Equation 26302) characterizes natural central groupoids.

Proof

See [ 5 , Theorem 5 ] . The proof is quite lengthy; a sketch is as follows. It is easy to see that natural central groupoids obey Equation 11. 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 Equation 11 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.