14 Equation 854
In this chapter we study magmas that obey Definition 2.28, thus
for all \(x,y,z\). In particular we have
substituting \(z = (x \diamond x)^2\) we have in particular that
We then have
and thus by another application of Equation 1 we conclude the useful law
(equation 378). We introduce the notation \(y \to x\) to denote the relation that \(x = z \diamond y\) for some \(z\), then from Equation 3 we see that
From Equation 1 we have
for all \(x,y,z\).
Now let \(X\) be an alphabet, and \(M_X\) the free magma. We let \(\Gamma \) be the theory consisting just of the law Equation 1, then as in Theorem 10.2 we have the equivalence relation \(\sim \) on \(M_X\) defined by setting \(w \sim w'\) iff \(\Gamma \models w \simeq w'\), then \(M_X/\sim \) is a free magma for \(\Gamma \). We can then also define a directed graph on \(M_X\) by declaring \(w' \to w\) if \(w \sim w'' \diamond w'\) for some \(w''\), or equivalently (by applying Equation 4 to \(M_X/\sim \)) that \(w \sim w \diamond w'\).
Call a word \(w\) irreducible if it is not of the form \(w = w_1 \diamond w_2\) with \(w_2 \to w_1\), and reducible otherwise. Clearly if a word \(w = w_1 \diamond w_2\) is reducible, then it is equivalent to the shorter word \(w_1\). Iterating, we conclude that every word is equivalent to an irreducible word. Such a word is either a generator in \(X\), or else a product \(w_1 \to w_2\) with \(w_2 \not\to w_1\).
We can describe the words equivalent to an irreducible word as follows.
Let \(w\) be an irreducible word, and let \(w'\) be a word equivalent to \(w\).
If \(w\) is a product \(w = w_1 \diamond w_2\), then \(w'\) takes the form
\[ w' = (((w'_1 \diamond w'_2) \diamond v_1) \diamond \dots \diamond v_n) \]for some \(w'_1 \sim w_1\), \(w'_2 \sim w_2\), some \(n \geq 0\), and some words \(v_1, \dots , v_n\) such that for all \(0 \leq i {\lt} n\), \(v_{i+1}\) is of the form
\[ v_{i+1} \sim (y_i \diamond z_i) \diamond (x_i \diamond z_i) \]for some \(x_i, y_i, z_i\) with
\[ x_i \sim (((w'_1 \diamond w'_2) \diamond v_1) \diamond \dots \diamond v_i). \]In particular, \(v_{i+1} \to x_i\).
Similarly, if \(w\) is a generator, then \(w'\) takes the form
\[ w' = ((w \diamond v_1) \diamond \dots \diamond v_n) \]for some \(n \geq 0\), and some words \(v_1, \dots , v_n\) such that for all \(0 \leq i {\lt} n\), \(v_{i+1}\) is of the form
\[ v_{i+1} \sim (y_i \diamond z_i) \diamond (x_i \diamond z_i) \]for some \(x_i, y_i, z_i\) with
\[ x_i \sim ((w \diamond v_1) \diamond \dots \diamond v_i). \]In particular, \(v_{i+1} \to x_i\).
Conversely, any word of the above forms is equivalent to \(w\).
We just verify claim (i), as claim (ii) is similar. The converse direction is clear from Equation 5 (after quotienting down to \(M_X/\sim \)), so it suffices to prove the forward claim. By Theorem 1.8, it suffices to prove that the class of words described by (i) is preserved by any term rewriting operation, in which a term in the word is replaced by an equivalent term using Equation 1. Clearly the term is in \(w'_1\) or \(w'_2\) then the form of the word is preserved, and similarly if the term is in one of the \(v_i\). The only remaining case is if we are rewriting a term of the form
If \(i{\gt}0\) we can rewrite this term down to \(x_{i-1}\), and this still preserves the required form (decrementing \(n\) by one). If \(i=0\) then we cannot perform such a rewriting because of the irreducibility of \(w_1 \diamond w_2\) and hence \(w'_1 \diamond w'_2\). Finally, we can rewrite \(x_i\) to \(x_i \diamond v\) where \(v\) is of the form
and after some relabeling we are again of the required form (now incrementing \(n\) by one).
We have two useful corollaries:
Two irreducible words \(w, w'\) are equivalent if and only if they are either the same generator of \(X\), or are of the form \(w = w_1 \diamond w_2\), \(w' = w'_1 \diamond w'_2\) with \(w_1 \sim w'_1\) and \(w_2 \sim w'_2\).
Immediate from Theorem 14.1.
If \(w,w'\) are words, then \(w' \to w\) holds if and only if \(w' \sim (Y \diamond Z) \diamond (w \diamond Z)\) for some words \(Y,Z\).
By replacing \(w,w'\) with irreducible equivalents, we may assume without loss of generality that \(w,w'\) are irreducible. By hypothesis, \(w\) is equivalent to \(w \diamond w'\). The claim now follows from Theorem 14.1.
We can now prove some anti-implications.
The laws
and
are not implied by Definition 2.28.
We work in the free group \(M_X\) on two generators \(X = \{ x,y\} \). It suffices to show that
and
We begin with the first claim. Suppose this were not the case, then by Corollary 14.2 one of the following statements must hold:
(i)
\[ y \to x \].
(ii)
\[ (y \diamond (x \diamond y)) \to x \].
(iii)
\[ y \diamond (x \diamond y) \sim y. \]
If (i) holds, then we have \(x \diamond y = x\) (Equation 4) in \(M_X/\sim \), hence in every magma obeying Definition 2.28. But we have examples of such magmas in which this fails.
Similarly, if (iii) holds, then \(y \diamond (x \diamond y) = y\) (Equation 10) holds in \(M_X/\sim \), hence in every magma obeying Definition 2.28. But we have examples of such magmas in which this fails.
Finally, if (ii) holds, then the claim
to refute simplifies to
and we are back to (i), which we already know not to be the case.
For the latter equation, we similarly have the cases
(iv)
\[ y \to x \].
(v)
\[ y \to x \diamond (y \diamond x) \].
(vi)
\[ x \sim x \diamond (y \diamond x). \]
(iv) is (i), which was already ruled out, and (vi) is similarly a relabeled version of (iii). In case (v) holds, the claim to refute simplifies to
and using Corollary 14.2 we reduce to either \(y \sim y \diamond x\), \(y \to x\), or \(y \diamond x \to x\), and each of these is already known to fail.
14.1 Some further properties of 854 magmas
As in the previous section, we write \(y \to x\) if \(x = x \diamond y\).
For \(x, y\) in a 854 magma, the following are equivalent.
(i) \(y \to x\).
(ii) \(x = x \diamond y\).
(iii) \(x = z \diamond y\) for some \(z\).
(iv) \(z, x \diamond z \to y\) for some \(z\).
(v) \(x \diamond y^2 \to y\).
(vi) \(y \diamond (x \diamond y^2) = y\).
(vii) \(y = (w \diamond z) \diamond (x \diamond z)\) for some \(w,z\).
(viii) \(y \to x \diamond y^2\).
The equivalence of (i) and (ii), or (v) and (vi), is by definition. (iii) trivially implies (ii), and the converse comes from Equation 3. Using Equation 2 we see that (v) implies (iv). If (iv) is true, then \(y = (y \diamond z) \diamond (x \diamond z)\), giving (vii). From Equation 1 we see that (vii) implies (ii). If (ii) is true, then \(y \diamond (x \diamond y^2) = y \diamond ((x \diamond y) \diamond (y \diamond y)) = y\), giving (vi). Finally, to show the equivalence of (i) and (viii), use the already established equivalence of (i) and (v), together with Equation 3 which gives \((x \diamond y^2) \diamond y^2 = x \diamond y^2\).
Introduce the notation \(y \leq x\) for \(x \diamond y \to y\).
For \(x,y\) in a 854 magma, the following are equivalent.
(i) \(y \leq x\).
(ii) \(x \diamond y \to x\).
(iii) For all \(z\), \(y \to z\) implies \(x \to z\).
(iv) \(x \to x \diamond y\).
The equivalence of (i) and (ii) is by definition. If (ii) holds and \(y \to z\), then by Lemma 14.5 we have \(x = u \diamond (x \diamond y)\) and \(z = v \diamond y\) for some \(u,v\), hence
giving the desired claim \(x \to z\). Now if (iii) holds, note from Lemma 14.5 that \(y \to x \diamond y\), hence \(x \to x \diamond y\) by (iii), so that \((x \diamond y) \diamond x = x \diamond y\), giving (iv). Finally, if (iv) holds, note that
and hence by (iv) \(x \diamond (x \diamond y) = x\), giving (ii).
The relation \(\leq \) is a pre-order, and for each \(z\), the sets \(\{ x: x \to z \} \) are upward closed in this preorder.
14.2 Running a greedy algorithm
Define a partial 854 magma to be a partial function \(\diamond : \mathbb {N}\times \mathbb {N}\to \mathbb {N}\) obeying the following axioms:
(Equation 854) If \(x,y,z \in \mathbb {N}\) are such that \((y \diamond z) \diamond (x \diamond z)\) is well-defined, then \(x \diamond ((y \diamond z) \diamond (x \diamond z))\) is well-defined and equal to \(x\).
(Equation 8) If \(x \in \mathbb {N}\) are such that \(x \diamond x\) is well-defined, then \(x \diamond (x \diamond x)\) is well-defined and equal to \(x\).
(Equation 101) If \(x,y \in \mathbb {N}\) are such that \((x \diamond y) \diamond x\) is well-defined, then \(x \diamond ((x \diamond y) \diamond x)\) is well-defined and equal to \(x\).
(Equation 46155) If \(x,y \in \mathbb {N}\) are such that \(x \diamond (x \diamond y)\) is well-defined, then \((x \diamond y) \diamond (x \diamond (x \diamond y))\) is well-defined and equal to \(x \diamond y\).
(Equation 378) If \(x,y \in \mathbb {N}\) is such that \(x \diamond y\) is well-defined, then \((x \diamond y) \diamond y\) is well-defined and equal to \(x \diamond y\).
(No idempotence) If \(x \in \mathbb {N}\) is such that \(x \diamond x\) is well-defined, then \(x \diamond x \neq x\).
(Auxiliary law) If \(x,y \in \mathbb {N}\) are such that \(x \diamond (x \diamond y)\) is well-defined and equal to \(x\), then \(x=y\).
(Unique factorization) If \(x,y,x',y' \in \mathbb {N}\) are such that \(x \diamond y\), \(x' \diamond y'\) are well-defined and equal to each other, then at least one of the assertions \(x \diamond y = x\), \(x' \diamond y' = x'\), or \((x,y) = (x',y')\) is true.
(Monotonicity) If \(x,y \in \mathbb {N}\) is such that \(x \diamond y\) is defined, then either \(x \diamond y = x\) or \(x \diamond y {\gt} x, y\).
The first five laws are known consequences of 854. The no idempotence law was known for the free magma \(M_{854}\) because it maps to finite magmas without idempotents, such as \(\mathbb {Z}/3\mathbb {Z}\) with law \(x \diamond y = x - 1_{x=y}\). The unique factorization law is also known for the free magma by Corollary 14.2. The auxiliary law is a “leap of faith” that helped close the greedy argument, and the monotonicity property is a technical consequence of the greedy construction that will also help close the argument.
The following observation is key.
Suppose one has a partial 854 magma on \(\mathbb {N}\) that is only finitely defined, and let \(a,b \in G\) be such that \(a \diamond b\) is currently undefined. Then it is possible to extend the magma to a larger partial 854 magma, such that \(a \diamond b\) is now defined.
Define a directed graph by writing \(x \to y\) if \(y \diamond x\) is defined and equal to \(y\). By Equation 378, we see that \(x \to y\) if and only if \(z \diamond x\) is well-defined and equal to \(y\) for some \(z\).
From unique factorization, we see that \(b\) has at most one representation of the form \(b = b_1 \diamond b_2\) with \(b_1 \neq b\), or equivalently \(b_2 \not\to b_1\). We define \(b_1, b_2\) accordingly if such a representation exists, otherwise we leave \(b_1, b_2\) undefined. We say that \(b_1\) is relevant if \(b_2 \to a\). Note that this forces \(a \neq b_1\) since \(b_2 \not\to b_1\). Also, if \(b_1,b_2\) exist, we see from monotonicity that \(b = b_1 \diamond b_2 {\gt} b_1, b_2\).
Let \(c\) be a natural number that is larger than any number appearing in anywhere in the partial 854 magma multiplication table (in particular it is larger than \(a,b\), as well as \(b_1,b_2\) if they are defined). We then extend the multiplication table by defining \(a \diamond b = c\), \(b \diamond c = b\), and \(c \diamond b = c\). If \(b_1\) exists and is relevant, we also define \(b_1 \diamond c = b_1\). Finally, if \(b_1\) exists and is relevant, and additionally \(b \to b_1\), then we also define \(c \diamond b_1 = c\). We remark that all new entries added are of the left absorptive form \(x \diamond y = x\), except for \(a \diamond b = c\).
We now verify that all of the axioms of a partial 854 magma continue to hold. We begin with all the axioms except for 854:
Monotonicity: Observe that all the new values \(x \diamond y\) of the multiplication table introduced are either equal to \(x\), or larger than both \(x\) and \(y\), so the monotonicity property is preserved.
Unique factorization: the only way unique factorization breaks is if there is an element \(z\) that has two distinct factorizations \(z = x \diamond y = x' \diamond y'\) with neither \(x \diamond y\) nor \(x' \diamond y'\) a left absorptive product. Since the only non-left-absorptive product introduced is \(a \diamond b = c\), and \(c\) has no prior representation as a product, we see that the unique factorization property is preserved.
No idempotence: The only possible product \(x \diamond x\) that could be introduced here is \(a \diamond b\) if \(x=a=b\), but in that case \(x \diamond x = a \diamond b = c\) is clearly not equal to \(x\), so the no idempotence property is preserved.
Equation 8: If \(x \diamond x\) were already defined in the previous magma, the claim would already be established, so \(x \diamond x\) must be one of the new products \(a \diamond b\), \(b \diamond c\), \(c \diamond b\), \(b_1 \diamond c\), or \(c \diamond b_1\). As \(c \neq a,b,b_1\), the only option is \(x = a = b\), but then \(x \diamond (x \diamond x) = b \diamond c = b = x\), as required.
Equation 101: By Equation 8, we may assume \(x \diamond y \neq x\), which implies \(y \neq c\) since \(x \diamond c = x\) whenever the left-hand side is defined. We can also assume \(x \neq c\), since we have \(c \diamond z = c\) whenever the left-hand side is defined. If \(x \diamond y = c\), then \((x,y) = (a,b)\); as \((x \diamond y) \diamond x = c \diamond x\) is well-defined, \(x=a\) is then either equal to \(b\), or equal to \(b_1\) if the latter exists and is relevant. But the second case cannot occur since \(a \neq b_1\), so we have \(x = b\), and then \(x \diamond ((x \diamond y) \diamond x) = b \diamond (c \diamond b) = b = x\), giving the claim. So we may assume \(x \diamond y \neq c\). If \((x \diamond y, x) \neq (a,b)\), then \((x \diamond y) \diamond x\) was already defined in the original partial magma, and the claim follows from Equation 101; hence we may assume \((x \diamond y, x) = (a,b)\), then \(x \diamond ((x \diamond y) \diamond x) = b \diamond c = b = x\), giving the claim.
Equation 46155: By Equation 8, we may assume \(x \diamond y \neq x\) and hence \(y \neq c\) as before. The case \(x=c\) is not possible, as this forces \(x \diamond y = c\) and then \(x \diamond (x \diamond y)\) is undefined. If \(x \diamond y = c\), then \((x,y) = (a,b)\); in order for \(x \diamond (x \diamond y) = a \diamond c\) to be defined, either \(a=b\) or \(a=b_1\) with \(b_1\) relevant, but the latter is impossible since \(a \neq b_1\); thus \(x=y=a=b\) and \((x \diamond y) \diamond (x \diamond (x \diamond y)) = c \diamond (b \diamond c) = c = (x \diamond y)\), giving the claim. Thus we may assume \(x \diamond y \neq c\). If \((x, x \diamond y) \neq (a,b)\) then \(x \diamond (x \diamond y)\) was already defined in the original partial magma, and the claim follows from Equation 46155; hence we may assume \((x, x \diamond y) = (a,b)\), and we have \((x \diamond y) \diamond (x \diamond (x \diamond y)) = b \diamond c = b = x \diamond y\), giving the claim.
Equation 378: We can assume \(x \diamond y \neq x\), since the claim is trivial otherwise. This rules out the \(y=c\) and \(x=c\) cases. The only new case is then if \(x \diamond y = c\), but forces \((x,y) = (a,b)\), and then \((x \diamond y) \diamond y = c \diamond b = c = x \diamond y\), giving the claim.
Auxiliary law: if \(x=c\), then the only possible value for \(x \diamond y\) is \(c\), and \(c \diamond c\) is undefined, contradiction; thus \(x \neq c\). If \(y = c\), then the only possible value for \(x \diamond y\) is \(x\), and then \(x \diamond (x \diamond y)\) cannot equal \(x\) by the no idempotence law. Thus \(y \neq c\). Since \(x \diamond (x \diamond y) = x\) is not equal to \(c\), \((x,x \diamond y)\) is not equal to \((a,b)\). If \((x,y) \neq (a,b)\), then both \(x \diamond y\) and \(x \diamond (x \diamond y)\) were already defined in the original partial magma, and the claim follows from the auxiliary law for that magma. Thus we may assume \((x,y) = (a,b)\), in which case \(a \diamond c = a\), hence by construction either \(a=b\) or \(a=b_1\). If \(a=b\) then we are done. If \(a = b_1\), then \(b_1\) cannot be relevant, and then \(a \diamond c = b_1 \diamond c\) remains undefined, a contradiction.
Now we tackle the most difficult verification, which is 854. This splits into a large number of cases.
Case 1: \(x=c\). Then \(x \diamond z\) can only equal \(c\), hence \(z\) equals \(b\) or \(b_1\); and \(y \diamond z\) can also only equal \(b\) or \(b_1\), and \((y \diamond z) \diamond (x \diamond z)\) is equal to \(y \diamond z\). If \(y \diamond z = b\), then we are done since \(c \diamond b = c\). If \(y \diamond z = b_1\), then \(b_1 \diamond c\) needs to be defined, so \(b_1\) is relevant. Furthermore, from equation 378 we have \(b_1 \diamond z = b_1\), hence by the no idempotence property \(z\) must equal \(b\), so \(b \to b_1\), and hence \(c \diamond b_1 = c\), giving the claim.
Case 2: \(x \neq c\), \(z = c\). This forces \(x,y=b,b_1\) with \(y \diamond z = y\) and \(x \diamond z = x\), thus \(y \diamond x\) is well-defined and we need \(x \diamond (y \diamond x)\) well-defined and equal to \(x\). If \(x=y\), this follows from Equation 8; otherwise, either \(x = b_1 \diamond b_2\) and \(y = b_1\) or \(x = b_1\) and \(y = b_1 \diamond b_2\), and the claim follows from Equation 101 or Equation 46155 respectively.
Case 3: \(x, z \neq c\), \(y = c\). Then \(z\) must equal \(b\) or \(b_1\), \(y \diamond z\) must equal \(c\), and \(x \diamond z\) must equal \(b\) or \(b_1\), and \((y \diamond z) \diamond (x \diamond z)\) must equal \(c\), with the \(b_1\) options only available if \(b_1\) is relevant. If \(x \diamond z = z\) then by equation 378, \(z \diamond z = z\), contradicting the no idempotence law. Thus we either have \(z=b_1, x \diamond z = b\) or \(z = b, x \diamond z = b_1\), and in either case \(b_1\) must be relevant. If \(z \to x\), then either have \(x=b\), or \(x = b_1\) and \(b_1\) is relevant, and in either case we have \(x \diamond c = x\) as required. So we may assume \(z \not\to x\). In the case \(z = b_1, x \diamond z = b = b_1 \diamond b_2\) we may then apply unique factorization to conclude that \(z = b_2\) and \(x = b_1\), thus \(x \diamond c = x\) as required. In the opposite case \(z = b\), \(x \diamond z = b_1\) with \(z \not\to x\), we see from monotonicity that \(b_1 = x \diamond z {\gt} z = b\); but from monotonicity again \(b = b_1 \diamond b_2 {\gt} b_1\), a contradiction.
Case 4: \(x,y,z \neq c\), \((y,z) = (a,b)\). Here, \(y \diamond z\) and \((y \diamond z) \diamond (x \diamond z)\) must equal \(c\), and \(x \diamond z\) must then equal \(b\) or \(b_1\), with the latter an option only if \(b_1\) is relevant. If \(x \diamond z = b\), then by Equation 378, \(b \diamond b = b\), contradicting idempotence, thus \(x \diamond z = b_1\) and \(b_1\) is relevant, and then \(b \to b_1\) by Equation 378 again. If \(z \to x\), then \(x = b_1\), and the claim follows since \(b_1 \diamond c = c\), so we may assume \(z \not\to x\). By monotonicity, this forces \(b_1 = x \diamond z {\gt} z = b\) and \(b = b_1 \diamond b_2 {\gt} b_1\), a contradiction.
Case 5: \(x,y,z \neq c\), \((y,z) \neq (a,b)\), \((x,z) = (a,b)\). Now \(x \diamond z = c\), and \(y \diamond z\) must equal \(b\) or \(b_1\). If \(y \diamond z = b\), then by Equation 378, \(b \diamond b = b\), contradicting idempotence, thus \(y \diamond z = b_1\) and \(b_1\) is relevant, and then \(b \to b_1\) by Equation 378 again, so \(b_1 \diamond (b_1 \diamond b_2) = b_1\). By the auxiliary law, this forces \(b_1 = b_2\), so \(x = b_1\), and then we are done since \(b_1 \diamond c = b_1\).
Case 6: \(x,y,z \neq c\), \((y,z), (x,z) \neq (a,b)\), \((y \diamond z, x \diamond z) = (a,b)\). Here \(x \diamond z = b\) and \((y \diamond z) \diamond (x \diamond z) = c\). If \(z \to x\), then \(x=b\) and we are done since \(b \diamond c = b\). If \(z \not\to x\), then by unique factorization applied to \(x \diamond z = b_1 \diamond b_2\) we have \((x,z) = (b_1,b_2)\). By Equation 378, we have \(z \to y \diamond z\), hence \(b_2 \to a\), so \(b_1\) is relevant. We are now done since \(b_1 \diamond c = b_1\).
Case 7: \(x,y,z \neq c\), \((y,z), (x,z) \neq (a,b), (y \diamond z, x \diamond z) \neq (a,b)\). In this case \(x \diamond ((y \diamond z) \diamond (x \diamond z))\) would already have been defined and equal to \(x\) in the previous partial magma, thanks to Equation 854.
Iterating this in the usual fashion, we obtain
Suppose one has a partial 854 magma on \(\mathbb {N}\) that is only finitely defined. Then it can be extended to a complete 854 magma that additionally obeys the no idempotence law, the monotonicity law, the auxiliary law, and the unique factorization law.
Apply the usual greedy algorithm.
There is an 854 magma which does not obey the 413 law \(x = x \diamond (x \diamond (x \diamond (y \diamond x)))\).
Create a partial magma by imposing the laws \(1 \diamond 0 = 2\), \(0 \diamond 2 = 3\), \(2 \diamond 0 = 2\), \(3 \diamond 2 = 3\). One can check that this is a partial magma. We then extend it to a global magma using Corollary 14.9. We claim that we have the 413 violation
or equivalently
Indeed this is immediate from the auxiliary law.
There is an 854 magma which does not obey the 1045 law \(x = x \diamond ((y \diamond (y \diamond x)) \diamond x)\).
Similar to previous, but start with the seed
which already violates the law with \(x=1,y=0\), and can be verified to be a partial 854 magma.
14.3 The free 854 magma
In this section we explicitly describe the free magma \(M_{X, 854}\) on some set \(X\) of generators relative to the 854 law.
We recall the free magma \(M_X\) from Definition 1.2, though to avoid confusion we will denote the magma operation on \(M_X\) by \(*\) rather than \(\diamond \). Recall that every word \(w\) in \(M_X\) has a length in \(\mathbb {N}\), which is zero if \(w\) is a generator in \(X\), and is the sum of the lengths of \(w_L\) and \(w_R\) plus one if instead \(w\) is of the form \(w_L * w_R\) for the left and right components \(w_L, w_R\) of \(w\) (which are uniquely defined by \(w\)). We iterate this notation, for instance \(w_{RL}\) is the left-component of \(w_R\) (if it exists), thus \(w = w_L * (w_{RL} * w_{RR})\) in this case.
We shall shortly define a relation \(\to \) on \(M_X\). To motivate this relation, we make the following observation about 854 magmas:
Let \(M\) be an \(854\) magma, and let \(\to \) be the associated operation, thus \(x \to y\) if \(y \diamond x = y\). Then \(x \to y\) holds under any of the following assumptions:
(i) \(y = a \diamond x\) for some \(a\).
(ii) \(x = a \diamond (y \diamond b)\) for some \(a,b\) with \(b \to a\).
(iii) \(y = a \diamond (x \diamond b)\) for some \(a,b\) with \(b \to a\) and \(x \diamond b \to x\).
(iv) \(x = a \diamond y\) for some \(a,z\) with \(z \to a, y\).
(v) \(x = a \diamond y\) for some \(a\), with either \(a=y\), \(a = y \diamond z\), or \(y = a \diamond z\) for some \(z\).
Case (i) follows from Equation 3. For (ii), we observe
as required. For (iii), we see from (ii) that \(y \to x\), and from (i) we have \(x \diamond b \to y\), and then
as required. For (iv), we have
as required. Finally, for (v), in the \(a=y\) case we have from Equation 2 that
in the \(a = y \diamond z\) case we have from Equation 2 that
and finally in the \(y = a \diamond z\) case we have from Equation 2 that
so the claim follows in all cases.
Now we define the operation \(\to \) on \(M_X\) by the following rule.
For \(x,y \in M_X\), we have \(x \to y\) if and only if one of the following holds:
(i) \(x = y_R\).
(ii) \(y = x_{RL}\) and \(x_{RR} \to x_L\).
(iii) \(x = y_{RL}\), \(y_{RR} \to y_L\), and \(y_R \to y_{RL}\).
(iv) \(y = x_R\), and there exists \(z \in \{ x_{LR}, x_{LRL}, x_{RR}, x_{RRL} \} \) such that \(z \to x_L\) and \(z \to x_R\).
(v) \(y = x_R\), and one of the claims \(x_L = x_R\), \(x_L = x_{RL}\), or \(x_R = x_{LL}\) holds.
Here we adopt the convention that a claim can only hold if all terms in it are well-defined, for instance claim (ii) can only hold if \(x_{RL}\) is well-defined.
If we define the “max-length” of a claim \(x \to y\) to be the maximum of the length of \(x\) and the length of \(y\), we see that the verification of a claim \(x \to y\) only involves claims \(x' \to y'\) of strictly smaller max-length. Thus this definition is well-defined. We also see that if \(x \to y\), then exactly one of
hold; in particular, we cannot have \(x \to x\) for any \(x\).
We then define a new operation \(\diamond \) on \(M_X\) by the rule \(x \diamond y = x\) if \(y \to x\), and \(x \diamond y = x*y\) otherwise. Thus, by definition, \(y \to x\) if and only if \(x \diamond y = x\). We then define \(M_{X,854}\) to be the magma generated by \(X\) with the operation \(\diamond \); thus, \(w \in M_{X,854}\) if and only if either \(w \in X\), or else \(w_L, w_R \in M_{X,854}\) and \(w_R \not\to w_L\).
The magma \(M_{X,854}\) is a free 854 magma on \(X\).
Let \(f: X \to M\) be a function from \(X\) to an \(854\) magma \(M\), then \(\varphi _f\) is a homomorphism from \(M_X\) (with the operation \(*\)) to \(M\). We claim that the restriction of \(\varphi _f\) to \(M_{X,854}\) is a homomorphism from \(M_{X,854}\) (with operation \(\diamond \)) to \(M\). Since \(\varphi _f\) was already a homomorphism for \(*\), it suffices to show that \(\varphi _f\) preserves \(\to \): that is to say, for any \(x,y \in M_{X,854}\), that \(x \to y\) implies \(\varphi _f(x) \to \varphi _f(y)\). By definition, one of the five scenarios (i)-(v) in Definition 14.13 holds, and in each case one can establish the claim from the corresponding claim of Lemma 14.12 and an induction on the max-length of the claim \(x \to y\).
It remains to show that \(M_{854}\) actually obeys 854, that is to say that
for all \(x,y,z \in M_{854}\). Writing \(w = y \diamond z\), we have \(z \to w\) by Definition 14.13(i), and we need to show that \(w \diamond (x \diamond z) \to x\). We divide into four cases.
Case 1: \(x \diamond z \to w\), \(z \to x\). Here we have \(x \diamond z = x\) and \(w \diamond (x \diamond z) = w\). We now have \(z \to x,w\) and \(x \to w\), and we need to show that \(w \to x\).
From Equation 8 we know that one of
holds, one of
holds, and one of
holds.
We split into subcases using Equation 11.
If \(x = w_R\) then the claim follows from Definition 14.13(i).
If \(w = x_{RL}\) then from Definition 14.13(iii) we have \(x_{RR} \to x_L\), and then the claim follows from Definition 14.13(ii).
If \(x = w_{RL}\), then \(w_{RR} \to w_L\) by Definition 14.13(ii) and from Definition 14.13(iii) we will be done if we can show that \(w_R \to w_{RL}\). If \(z = w_R\) then this follows from \(z \to x\). The claim \(z = w_{RL}\) is not compatible with Equation 9, since \(z=x\) in that case. If \(w = z_R\) then \(x = z_{RRL}\), and this is only compatible with Equation 9 if \(x = z_{RL}\), thus \(z = a * (x * (x * b))\) and \(w = x * (x * b)\) for some \(a,b\). In order to have \(x = w_{RL}\) in Equation 11, we must have \(b \to x\) by Definition 14.13(iii), but then \(x*b\) would not lie in \(M_{854}\), a contradiction.
If \(w = x_R\), then we cannot then have \(z = x_R\) as then \(z=w\) which is incompatible with Equation 10. If \(z = x_{RL} = w_L\) then \(x_{RR} \to x_L\) by Definition 14.13(ii), and the only available options from Equation 10 are \(z = w_R\) and \(z = w_{RL}\). For \(z=w_R\) we have \(w = z * z\) and \(x = a * (z * z)\) for some \(a\) with \(z \to a = x_L\). Since \(z \to z*z = x_R\) as well by Definition 14.13(i), and \(z = x_{RR}\), we obtain \(w \to x\) as required from Definition 14.13(iv).
Case 2: \(x \diamond z \to w\), \(z \not\to x\). We now have \(x * z, z \to w\), and we need to show that \(w \to x\). From Equation 8 we know that one of
holds, and that one of
holds.
We split into cases depending on Equation 12.
If \(w = (x*z)_R\) then \(w=z\), which is incompatible with Equation 13.
If \(w = (x*z)_{RL}\) then \(w = z_L\) and \(z_R \to x\) by Definition 14.13(ii). Only the first two possibilities of Equation 13 are compatible with \(w=z_L\). In the first case we are done since \(z_R \to x\) and \(w = z_R\). In the second case, we have \(z = w * (w * a)\) for some \(a\) with \(a \to w\) (from Definition 14.13(ii) and \(z \to w\)), but then \(w * a\) will not lie in \(M_{854}\), contradiction.
If \(x*z = w_R\) then \(w\) is longer than \(z\) and \(z \neq w_R\). Comparing this with Equation 13 we see that the only compatible option is \(z = w_{RL}\), thus \(x=z\), and then \(w = a * (x * x)\) and \(x \to a\) by Definition 14.13(iii), and the claim follows from Definition 14.13(ii).
If \(x * z = w_{RL}\), then \(w = a * ((x *z) * b)\) for some \(a,b\). Then \(w\), \(w_R\), and \(w_{RL}\) are all longer than \(z\) and none of the options in Equation 13 can hold, a contradiction.
Case 3: \(x \diamond z \not\to w\), \(z \to x\). We now have \(z \to x, w\), and we need to show that \(w * x \to x\).
If \(z \in \{ w_R, w_{RL}, x_R, x_{RL} \} \), then the claim follows from Definition 14.13(iv), so we may assume that this is not the case. By Equation 8, we then know that one of
holds, and also one of
holds. Thus, we either have one of
But in any of these three cases the claim follows from Definition 14.13(v).
Case 4: \(x \diamond z \not\to w\), \(z \not\to x\). Then \(x = (w \diamond (x \diamond z))_{RL}\) and \(z \to w\), so the claim follows from Definition 14.13(ii).
With the explicit description of \(M_{X,854}\) we can now refute various laws. Suppose for instance that \(x,y\) are generators in \(X\). We cannot have \(y \to x\) (as none of Equation 8 hold), so \(y * x \in M_{X,854}\). We also cannot have \(y * x \to x\) (by inspection of the cases in Definition 14.13(iv), Definition 14.13(v)), so \(x * (y * x)\) lies in \(M_{X,854}\). Then \(x * (y * x) \not\to x\) (by Equation 8), so \(x * (x * (y * x))\) lies in \(M_{X,854}\); finally, \(x * (x * (y * x)) \not\to x\) (this follows from Definition 14.13(ii) since \(y * x \not\to x\)), so \(x * (x * (x * (y * x)))\) lies in \(M_{X,854}\). This gives an alternate proof of Corollary 14.10. One can similarly establish Corollary 14.11.