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.
Definition 2.26 implies Definition 2.18.
(From MathOverflow). By Definition 2.26, one has the law
Specializing to \(y=x \diamond x\), we conclude
and hence by another application of Definition 2.26 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 Definition 2.18.
Definition 2.12 is equivalent to Definition 2.9.
This result was posed as Problem A1 from Putnam 2001.
By Lemma 4.5 it suffices to show that Definition 2.12 implies Definition 2.9. From Definition 2.12 one has
and also
giving \(x = y \diamond (x \diamond y)\), which is Definition 2.9.
Definition 2.9 implies Definition 2.12.
This result was posed as Problem A1 from Putnam 2001.
The following result was Problem A4 on Putnam 1978.
Definition 2.43 implies Definition 2.42 and Definition 2.25.
By hypothesis, one has
for all \(x,y,z,w\). Various specializations of this give
5 gives Definition 2.42, while Equation 4, 5, 6 gives
which is Definition 2.25.
Definition 2.37 is equivalent to Definition 2.2.
The implication of Definition 2.37 from Definition 2.2 is trivial. The converse is a surprisingly long chain of implications; see pages 326–327 of [ 4 ] . The initial law
is used to obtain, in turn,
The following result was established in [ 10 ] .
Magmas obeying Definition 2.32 also obey Definition 2.39, Definition 2.15, Definition 2.11, Definition 2.8, Definition 2.10, Definition 2.9, Definition 2.18, and Definition 2.46, and are in fact abelian groups of exponent two. Conversely, all abelian groups of exponent two obey Definition 2.32.
Suppose that a magma \(G\) obeys Definition 2.32, thus
and
whence
which is Definition 2.39. This gives
while from Equation 7 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 7 the magma operation is surjective, hence
which gives Definition 2.15. Applying Equation 7 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 Definition 2.11, Definition 2.8; thus \(e\) is an identity element. From Equation 7 with \(z=e\) we now have
which is Definition 2.10. If instead we take \(y=e\) we have
which is Definition 2.9. So if we substitute \(z = x \diamond y\) and use Equation 9 we obtain
and hence
thanks to Equation 10. This gives Definition 2.18, thus \(G\) is now commutative. From Equation 7 once more one has
which one can simplify using commutativity and Equation 9 (or Equation 10) to eventually obtain
which is Definition 2.46. \(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.
Definition 2.29 is equivalent to Definition 2.2.
It suffices to show that Definition 2.29 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.29 with \(x=z=0\) we have
If we then apply Definition 2.29 with \(z=1\) we conclude that
for all \(x,y\), from which one concludes \(x=x'\) for any \(x,x' \in G\), giving Definition 2.2.
Definition 2.55 axiomatizes the Sheffer stroke operation \(x \diamond y = \overline{xy}\) in a Boolean algebra.
See [ 9 ] . 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
are satisfied. A classical result of Sheffer [ 11 ] 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 (Definition 2.23).
Definition 2.53 characterizes natural central groupoids.
See [ 6 , Theorem 5 ] . The proof is quite lengthy; a sketch is as follows. It is easy to see that natural central groupoids obey Definition 2.53. 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 Definition 2.53 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.