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.
(From MathOverflow). By E387, one has the law
Specializing to \(y=x \diamond x\), we conclude
and hence by another application of E387 we see that \(x \diamond x\) is idempotent:
Now, replacing \(x\) by \(x \diamond x\) in Equation 1 and then using Equation 2 we see that
so in particular \(x \diamond x\) commutes with \(y \diamond y\):
Also, from two applications of Equation 1 one has
Thus Equation 3 simplifies to \(x \diamond y = y \diamond x\), which is E43.
This result was posed as Problem A1 from Putnam 2001.
This result was posed as Problem A1 from Putnam 2001.
The following result was Problem A4 on Putnam 1978.
By hypothesis, one has
for all \(x,y,z,w\). Various specializations of this give
5 gives E3722, while Equation 4, 5, 6 gives
which is E381.
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
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
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
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}\))
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
The following result was established in [ 11 ] .
Suppose that a magma \(G\) satisfies E1571, thus
and
whence
which is E2662. This gives
while from Equation 12 one has
whence
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\):
From Equation 12 the magma operation is surjective, hence
which gives E40. Applying Equation 12 with \(x=y=z\) we conclude
while if we instead take \(y=z=e\) we have
hence
and then also
from which we readily conclude E23, E8; thus \(e\) is an identity element. From Equation 12 with \(z=e\) we now have
which is E16. If instead we take \(y=e\) we have
which is E14. So if we substitute \(z = x \diamond y\) and use Equation 14 we obtain
and hence
thanks to Equation 15. This gives E43, thus \(G\) is now commutative. From Equation 12 once more one has
which one can simplify using commutativity and Equation 14 (or Equation 15) to eventually obtain
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.
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
If we then apply E953 with \(z=1\) we conclude that
for all \(x,y\), from which one concludes \(x=x'\) for any \(x,x' \in G\), giving E2.
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.
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
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
These are examples of central groupoids, E168 \((x = (y \diamond x) \diamond (x \diamond z))\).
E26302 \((x = (y \diamond ((z \diamond x) \diamond w)) \diamond (x \diamond w))\) characterizes natural central groupoids.
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
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
Using the notation
we then have
A lengthy computer-assisted argument then gave the dual identity
Together, these give
Multiplying on the left by \(x = x^{(1)}\diamond x^{(2)}\), one can conclude that
One then has
and a similar argument gives
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.