14 Equation 854

In this chapter we study magmas that obey Definition 2.28, thus

x = x ⋄ ((y ⋄ z) ⋄ (x ⋄ z))

for all $x, y, z$ . In particular we have

x = x ⋄ (x ⋄ z)^{2};

substituting $z = (x ⋄ x)^{2}$ we have in particular that

x = x ⋄ x^{2} .

We then have

\begin{aligned} y & = y ⋄ ((x ⋄ y) ⋄ y^{2}) \\ = (y ⋄ y^{2}) ⋄ ((x ⋄ y) ⋄ y^{2}) \end{aligned}

and thus by another application of Equation 1 we conclude the useful law

(x ⋄ y) ⋄ y = x ⋄ y

(equation 378). We introduce the notation $y \to x$ to denote the relation that $x = z ⋄ y$ for some $z$ , then from Equation 3 we see that

y \to x ⟺ x = x ⋄ y .

From Equation 1 we have

(y ⋄ z) ⋄ (x ⋄ z) \to x

for all $x, y, z$ .

Now let $X$ be an alphabet, and $M_{X}$ the free magma. We let $Γ$ 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 $Γ ⊨ w ≃ w^{'}$ , then $M_{X} / \sim$ is a free magma for $Γ$ . We can then also define a directed graph on $M_{X}$ by declaring $w^{'} \to w$ if $w \sim w^{″} ⋄ w^{'}$ for some $w^{″}$ , or equivalently (by applying Equation 4 to $M_{X} / \sim$ ) that $w \sim w ⋄ w^{'}$ .

Call a word $w$ irreducible if it is not of the form $w = w_{1} ⋄ w_{2}$ with $w_{2} \to w_{1}$ , and reducible otherwise. Clearly if a word $w = w_{1} ⋄ 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} ↛ w_{1}$ .

We can describe the words equivalent to an irreducible word as follows.

Theorem 14.1 Description of equivalence

Let $w$ be an irreducible word, and let $w^{'}$ be a word equivalent to $w$ .

If $w$ is a product $w = w_{1} ⋄ w_{2}$ , then $w^{'}$ takes the form

$w^{'} = (((w_{1}^{'} ⋄ w_{2}^{'}) ⋄ v_{1}) ⋄ \dots ⋄ 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 < n$ , $v_{i + 1}$ is of the form

$v_{i + 1} \sim (y_{i} ⋄ z_{i}) ⋄ (x_{i} ⋄ z_{i})$

for some $x_{i}, y_{i}, z_{i}$ with

$x_{i} \sim (((w_{1}^{'} ⋄ w_{2}^{'}) ⋄ v_{1}) ⋄ \dots ⋄ v_{i}) .$

In particular, $v_{i + 1} \to x_{i}$ .
Similarly, if $w$ is a generator, then $w^{'}$ takes the form

$w^{'} = ((w ⋄ v_{1}) ⋄ \dots ⋄ v_{n})$

for some $n \geq 0$ , and some words $v_{1}, \dots, v_{n}$ such that for all $0 \leq i < n$ , $v_{i + 1}$ is of the form

$v_{i + 1} \sim (y_{i} ⋄ z_{i}) ⋄ (x_{i} ⋄ z_{i})$

for some $x_{i}, y_{i}, z_{i}$ with

$x_{i} \sim ((w ⋄ v_{1}) ⋄ \dots ⋄ v_{i}) .$

In particular, $v_{i + 1} \to x_{i}$ .

Conversely, any word of the above forms is equivalent to $w$ .

Proof ▶

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

x_{i} = (((w_{1}^{'} ⋄ w_{2}^{'}) ⋄ v_{1}) ⋄ \dots ⋄ v_{i}) .

If $i > 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} ⋄ w_{2}$ and hence $w_{1}^{'} ⋄ w_{2}^{'}$ . Finally, we can rewrite $x_{i}$ to $x_{i} ⋄ v$ where $v$ is of the form

v_{i} = (y ⋄ z) ⋄ (x_{i} ⋄ z),

and after some relabeling we are again of the required form (now incrementing $n$ by one).

We have two useful corollaries:

Corollary 14.2 Unique factorization

✓

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} ⋄ w_{2}$ , $w^{'} = w_{1}^{'} ⋄ w_{2}^{'}$ with $w_{1} \sim w_{1}^{'}$ and $w_{2} \sim w_{2}^{'}$ .

Proof ▶

Corollary 14.3 Description of graph

If $w, w^{'}$ are words, then $w^{'} \to w$ holds if and only if $w^{'} \sim (Y ⋄ Z) ⋄ (w ⋄ Z)$ for some words $Y, Z$ .

Proof ▶

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 ⋄ w^{'}$ . The claim now follows from Theorem 14.1.

We can now prove some anti-implications.

Theorem 14.4 854 does not imply 3316, 3925

The laws

x ⋄ y = x ⋄ (y ⋄ (x ⋄ y))

and

x ⋄ y = (x ⋄ (y ⋄ x)) ⋄ y

are not implied by Definition 2.28.

Proof ▶

We work in the free group $M_{X}$ on two generators $X = {x, y}$ . It suffices to show that

x ⋄ y ≁ x ⋄ (y ⋄ (x ⋄ y))

and

x ⋄ y ≁ (x ⋄ (y ⋄ x)) ⋄ y .

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 ⋄ (x ⋄ y)) \to x$

.
(iii)

$y ⋄ (x ⋄ y) \sim y .$

If (i) holds, then we have $x ⋄ 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 ⋄ (x ⋄ 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

x ⋄ y \sim x ⋄ (y ⋄ (x ⋄ y))

to refute simplifies to

x ⋄ y \sim x

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 ⋄ (y ⋄ x)$

.
(vi)

$x \sim x ⋄ (y ⋄ 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

x ⋄ y \sim x ⋄ (y ⋄ x)

and using Corollary 14.2 we reduce to either $y \sim y ⋄ x$ , $y \to x$ , or $y ⋄ 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 ⋄ y$ .

Lemma 14.5 854 equivalences, I

For $x, y$ in a 854 magma, the following are equivalent.

(i) $y \to x$ .
(ii) $x = x ⋄ y$ .
(iii) $x = z ⋄ y$ for some $z$ .
(iv) $z, x ⋄ z \to y$ for some $z$ .
(v) $x ⋄ y^{2} \to y$ .
(vi) $y ⋄ (x ⋄ y^{2}) = y$ .
(vii) $y = (w ⋄ z) ⋄ (x ⋄ z)$ for some $w, z$ .
(viii) $y \to x ⋄ y^{2}$ .

Proof ▶

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 ⋄ z) ⋄ (x ⋄ z)$ , giving (vii). From Equation 1 we see that (vii) implies (ii). If (ii) is true, then $y ⋄ (x ⋄ y^{2}) = y ⋄ ((x ⋄ y) ⋄ (y ⋄ 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 ⋄ y^{2}) ⋄ y^{2} = x ⋄ y^{2}$ .

Introduce the notation $y \leq x$ for $x ⋄ y \to y$ .

Lemma 14.6 854 equivalences, II

For $x, y$ in a 854 magma, the following are equivalent.

(i) $y \leq x$ .
(ii) $x ⋄ y \to x$ .
(iii) For all $z$ , $y \to z$ implies $x \to z$ .
(iv) $x \to x ⋄ y$ .

Proof ▶

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 ⋄ (x ⋄ y)$ and $z = v ⋄ y$ for some $u, v$ , hence

z ⋄ x = z ⋄ (x ⋄ ((v ⋄ y) ⋄ (x ⋄ y))) = z ⋄ ((u ⋄ (x ⋄ y)) ⋄ (z ⋄ (x ⋄ y))) = z,

giving the desired claim $x \to z$ . Now if (iii) holds, note from Lemma 14.5 that $y \to x ⋄ y$ , hence $x \to x ⋄ y$ by (iii), so that $(x ⋄ y) ⋄ x = x ⋄ y$ , giving (iv). Finally, if (iv) holds, note that

\begin{aligned} x ⋄ ((x ⋄ y) ⋄ x) & = x ⋄ (((x ⋄ y) ⋄ ((y ⋄ y) ⋄ ((x ⋄ y) ⋄ y))) ⋄ x) \\ = x ⋄ (((x ⋄ y) ⋄ ((y ⋄ y) ⋄ (x ⋄ y))) ⋄ (x ⋄ ((y ⋄ y) ⋄ (x ⋄ y)))) \\ = x \end{aligned}

and hence by (iv) $x ⋄ (x ⋄ y) = x$ , giving (ii).

Corollary 14.7

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 $⋄ : N \times N \to N$ obeying the following axioms:

(Equation 854) If $x, y, z \in N$ are such that $(y ⋄ z) ⋄ (x ⋄ z)$ is well-defined, then $x ⋄ ((y ⋄ z) ⋄ (x ⋄ z))$ is well-defined and equal to $x$ .
(Equation 8) If $x \in N$ are such that $x ⋄ x$ is well-defined, then $x ⋄ (x ⋄ x)$ is well-defined and equal to $x$ .
(Equation 101) If $x, y \in N$ are such that $(x ⋄ y) ⋄ x$ is well-defined, then $x ⋄ ((x ⋄ y) ⋄ x)$ is well-defined and equal to $x$ .
(Equation 46155) If $x, y \in N$ are such that $x ⋄ (x ⋄ y)$ is well-defined, then $(x ⋄ y) ⋄ (x ⋄ (x ⋄ y))$ is well-defined and equal to $x ⋄ y$ .
(Equation 378) If $x, y \in N$ is such that $x ⋄ y$ is well-defined, then $(x ⋄ y) ⋄ y$ is well-defined and equal to $x ⋄ y$ .
(No idempotence) If $x \in N$ is such that $x ⋄ x$ is well-defined, then $x ⋄ x \neq x$ .
(Auxiliary law) If $x, y \in N$ are such that $x ⋄ (x ⋄ y)$ is well-defined and equal to $x$ , then $x = y$ .
(Unique factorization) If $x, y, x^{'}, y^{'} \in N$ are such that $x ⋄ y$ , $x^{'} ⋄ y^{'}$ are well-defined and equal to each other, then at least one of the assertions $x ⋄ y = x$ , $x^{'} ⋄ y^{'} = x^{'}$ , or $(x, y) = (x^{'}, y^{'})$ is true.
(Monotonicity) If $x, y \in N$ is such that $x ⋄ y$ is defined, then either $x ⋄ y = x$ or $x ⋄ y > 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 $Z / 3 Z$ with law $x ⋄ 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.

Proposition 14.8 Greedy construction

Suppose one has a partial 854 magma on $N$ that is only finitely defined, and let $a, b \in G$ be such that $a ⋄ b$ is currently undefined. Then it is possible to extend the magma to a larger partial 854 magma, such that $a ⋄ b$ is now defined.

Proof ▶

Define a directed graph by writing $x \to y$ if $y ⋄ x$ is defined and equal to $y$ . By Equation 378, we see that $x \to y$ if and only if $z ⋄ 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} ⋄ b_{2}$ with $b_{1} \neq b$ , or equivalently $b_{2} ↛ 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} ↛ b_{1}$ . Also, if $b_{1}, b_{2}$ exist, we see from monotonicity that $b = b_{1} ⋄ b_{2} > 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 ⋄ b = c$ , $b ⋄ c = b$ , and $c ⋄ b = c$ . If $b_{1}$ exists and is relevant, we also define $b_{1} ⋄ c = b_{1}$ . Finally, if $b_{1}$ exists and is relevant, and additionally $b \to b_{1}$ , then we also define $c ⋄ b_{1} = c$ . We remark that all new entries added are of the left absorptive form $x ⋄ y = x$ , except for $a ⋄ 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 ⋄ 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 ⋄ y = x^{'} ⋄ y^{'}$ with neither $x ⋄ y$ nor $x^{'} ⋄ y^{'}$ a left absorptive product. Since the only non-left-absorptive product introduced is $a ⋄ 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 ⋄ x$ that could be introduced here is $a ⋄ b$ if $x = a = b$ , but in that case $x ⋄ x = a ⋄ b = c$ is clearly not equal to $x$ , so the no idempotence property is preserved.
Equation 8: If $x ⋄ x$ were already defined in the previous magma, the claim would already be established, so $x ⋄ x$ must be one of the new products $a ⋄ b$ , $b ⋄ c$ , $c ⋄ b$ , $b_{1} ⋄ c$ , or $c ⋄ b_{1}$ . As $c \neq a, b, b_{1}$ , the only option is $x = a = b$ , but then $x ⋄ (x ⋄ x) = b ⋄ c = b = x$ , as required.
Equation 101: By Equation 8, we may assume $x ⋄ y \neq x$ , which implies $y \neq c$ since $x ⋄ c = x$ whenever the left-hand side is defined. We can also assume $x \neq c$ , since we have $c ⋄ z = c$ whenever the left-hand side is defined. If $x ⋄ y = c$ , then $(x, y) = (a, b)$ ; as $(x ⋄ y) ⋄ x = c ⋄ 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 ⋄ ((x ⋄ y) ⋄ x) = b ⋄ (c ⋄ b) = b = x$ , giving the claim. So we may assume $x ⋄ y \neq c$ . If $(x ⋄ y, x) \neq (a, b)$ , then $(x ⋄ y) ⋄ x$ was already defined in the original partial magma, and the claim follows from Equation 101; hence we may assume $(x ⋄ y, x) = (a, b)$ , then $x ⋄ ((x ⋄ y) ⋄ x) = b ⋄ c = b = x$ , giving the claim.
Equation 46155: By Equation 8, we may assume $x ⋄ y \neq x$ and hence $y \neq c$ as before. The case $x = c$ is not possible, as this forces $x ⋄ y = c$ and then $x ⋄ (x ⋄ y)$ is undefined. If $x ⋄ y = c$ , then $(x, y) = (a, b)$ ; in order for $x ⋄ (x ⋄ y) = a ⋄ 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 ⋄ y) ⋄ (x ⋄ (x ⋄ y)) = c ⋄ (b ⋄ c) = c = (x ⋄ y)$ , giving the claim. Thus we may assume $x ⋄ y \neq c$ . If $(x, x ⋄ y) \neq (a, b)$ then $x ⋄ (x ⋄ y)$ was already defined in the original partial magma, and the claim follows from Equation 46155; hence we may assume $(x, x ⋄ y) = (a, b)$ , and we have $(x ⋄ y) ⋄ (x ⋄ (x ⋄ y)) = b ⋄ c = b = x ⋄ y$ , giving the claim.
Equation 378: We can assume $x ⋄ 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 ⋄ y = c$ , but forces $(x, y) = (a, b)$ , and then $(x ⋄ y) ⋄ y = c ⋄ b = c = x ⋄ y$ , giving the claim.
Auxiliary law: if $x = c$ , then the only possible value for $x ⋄ y$ is $c$ , and $c ⋄ c$ is undefined, contradiction; thus $x \neq c$ . If $y = c$ , then the only possible value for $x ⋄ y$ is $x$ , and then $x ⋄ (x ⋄ y)$ cannot equal $x$ by the no idempotence law. Thus $y \neq c$ . Since $x ⋄ (x ⋄ y) = x$ is not equal to $c$ , $(x, x ⋄ y)$ is not equal to $(a, b)$ . If $(x, y) \neq (a, b)$ , then both $x ⋄ y$ and $x ⋄ (x ⋄ 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 ⋄ 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 ⋄ c = b_{1} ⋄ 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 ⋄ z$ can only equal $c$ , hence $z$ equals $b$ or $b_{1}$ ; and $y ⋄ z$ can also only equal $b$ or $b_{1}$ , and $(y ⋄ z) ⋄ (x ⋄ z)$ is equal to $y ⋄ z$ . If $y ⋄ z = b$ , then we are done since $c ⋄ b = c$ . If $y ⋄ z = b_{1}$ , then $b_{1} ⋄ c$ needs to be defined, so $b_{1}$ is relevant. Furthermore, from equation 378 we have $b_{1} ⋄ z = b_{1}$ , hence by the no idempotence property $z$ must equal $b$ , so $b \to b_{1}$ , and hence $c ⋄ b_{1} = c$ , giving the claim.
Case 2: $x \neq c$ , $z = c$ . This forces $x, y = b, b_{1}$ with $y ⋄ z = y$ and $x ⋄ z = x$ , thus $y ⋄ x$ is well-defined and we need $x ⋄ (y ⋄ x)$ well-defined and equal to $x$ . If $x = y$ , this follows from Equation 8; otherwise, either $x = b_{1} ⋄ b_{2}$ and $y = b_{1}$ or $x = b_{1}$ and $y = b_{1} ⋄ 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 ⋄ z$ must equal $c$ , and $x ⋄ z$ must equal $b$ or $b_{1}$ , and $(y ⋄ z) ⋄ (x ⋄ z)$ must equal $c$ , with the $b_{1}$ options only available if $b_{1}$ is relevant. If $x ⋄ z = z$ then by equation 378, $z ⋄ z = z$ , contradicting the no idempotence law. Thus we either have $z = b_{1}, x ⋄ z = b$ or $z = b, x ⋄ 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 ⋄ c = x$ as required. So we may assume $z ↛ x$ . In the case $z = b_{1}, x ⋄ z = b = b_{1} ⋄ b_{2}$ we may then apply unique factorization to conclude that $z = b_{2}$ and $x = b_{1}$ , thus $x ⋄ c = x$ as required. In the opposite case $z = b$ , $x ⋄ z = b_{1}$ with $z ↛ x$ , we see from monotonicity that $b_{1} = x ⋄ z > z = b$ ; but from monotonicity again $b = b_{1} ⋄ b_{2} > b_{1}$ , a contradiction.
Case 4: $x, y, z \neq c$ , $(y, z) = (a, b)$ . Here, $y ⋄ z$ and $(y ⋄ z) ⋄ (x ⋄ z)$ must equal $c$ , and $x ⋄ z$ must then equal $b$ or $b_{1}$ , with the latter an option only if $b_{1}$ is relevant. If $x ⋄ z = b$ , then by Equation 378, $b ⋄ b = b$ , contradicting idempotence, thus $x ⋄ 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} ⋄ c = c$ , so we may assume $z ↛ x$ . By monotonicity, this forces $b_{1} = x ⋄ z > z = b$ and $b = b_{1} ⋄ b_{2} > b_{1}$ , a contradiction.
Case 5: $x, y, z \neq c$ , $(y, z) \neq (a, b)$ , $(x, z) = (a, b)$ . Now $x ⋄ z = c$ , and $y ⋄ z$ must equal $b$ or $b_{1}$ . If $y ⋄ z = b$ , then by Equation 378, $b ⋄ b = b$ , contradicting idempotence, thus $y ⋄ z = b_{1}$ and $b_{1}$ is relevant, and then $b \to b_{1}$ by Equation 378 again, so $b_{1} ⋄ (b_{1} ⋄ 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} ⋄ c = b_{1}$ .
Case 6: $x, y, z \neq c$ , $(y, z), (x, z) \neq (a, b)$ , $(y ⋄ z, x ⋄ z) = (a, b)$ . Here $x ⋄ z = b$ and $(y ⋄ z) ⋄ (x ⋄ z) = c$ . If $z \to x$ , then $x = b$ and we are done since $b ⋄ c = b$ . If $z ↛ x$ , then by unique factorization applied to $x ⋄ z = b_{1} ⋄ b_{2}$ we have $(x, z) = (b_{1}, b_{2})$ . By Equation 378, we have $z \to y ⋄ z$ , hence $b_{2} \to a$ , so $b_{1}$ is relevant. We are now done since $b_{1} ⋄ c = b_{1}$ .
Case 7: $x, y, z \neq c$ , $(y, z), (x, z) \neq (a, b), (y ⋄ z, x ⋄ z) \neq (a, b)$ . In this case $x ⋄ ((y ⋄ z) ⋄ (x ⋄ 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

Corollary 14.9 854 extension

Suppose one has a partial 854 magma on $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.

Proof ▶

Corollary 14.10 854 does not not imply 413

There is an 854 magma which does not obey the 413 law $x = x ⋄ (x ⋄ (x ⋄ (y ⋄ x)))$ .

Proof ▶

Create a partial magma by imposing the laws $1 ⋄ 0 = 2$ , $0 ⋄ 2 = 3$ , $2 ⋄ 0 = 2$ , $3 ⋄ 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

0 ⋄ (0 ⋄ (0 ⋄ (1 ⋄ 0))) = 0

or equivalently

0 ⋄ (0 ⋄ 3) = 0.

Indeed this is immediate from the auxiliary law.

Corollary 14.11 854 does not not imply 1045

There is an 854 magma which does not obey the 1045 law $x = x ⋄ ((y ⋄ (y ⋄ x)) ⋄ x)$ .

Proof ▶

Similar to previous, but start with the seed

0 ⋄ 0 = 2; 0 ⋄ 1 = 0 ⋄ 2 = 0; 1 ⋄ 2 = 3; 2 ⋄ 0 = 2 ⋄ 1 = 2 ⋄ 3 = 2; 3 ⋄ 2 = 3

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 $⋄$ . Recall that every word $w$ in $M_{X}$ has a length in $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_{R L}$ is the left-component of $w_{R}$ (if it exists), thus $w = w_{L} * (w_{R L} * w_{R R})$ 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:

Lemma 14.12 The 854 relation

Let $M$ be an $854$ magma, and let $\to$ be the associated operation, thus $x \to y$ if $y ⋄ x = y$ . Then $x \to y$ holds under any of the following assumptions:

(i) $y = a ⋄ x$ for some $a$ .
(ii) $x = a ⋄ (y ⋄ b)$ for some $a, b$ with $b \to a$ .
(iii) $y = a ⋄ (x ⋄ b)$ for some $a, b$ with $b \to a$ and $x ⋄ b \to x$ .
(iv) $x = a ⋄ y$ for some $a, z$ with $z \to a, y$ .
(v) $x = a ⋄ y$ for some $a$ , with either $a = y$ , $a = y ⋄ z$ , or $y = a ⋄ z$ for some $z$ .

Proof ▶

Case (i) follows from Equation 3. For (ii), we observe

y ⋄ x = y ⋄ ((a ⋄ b) ⋄ (y ⋄ b)) = y

as required. For (iii), we see from (ii) that $y \to x$ , and from (i) we have $x ⋄ b \to y$ , and then

y ⋄ x = y ⋄ ((x ⋄ (x ⋄ b)) ⋄ (y ⋄ (x ⋄ b))) = y

as required. For (iv), we have

y ⋄ x = y ⋄ ((a ⋄ z) ⋄ (y ⋄ z)) = y

as required. Finally, for (v), in the $a = y$ case we have from Equation 2 that

y ⋄ x = y ⋄ ((y ⋄ y^{2}) ⋄ (y ⋄ y^{2})) = y,

in the $a = y ⋄ z$ case we have from Equation 2 that

y ⋄ x = y ⋄ (((y ⋄ z) ⋄ (y ⋄ z)^{2}) ⋄ (y ⋄ (y ⋄ z)^{2})) = y,

and finally in the $y = a ⋄ z$ case we have from Equation 2 that

y ⋄ x = y ⋄ ((a ⋄ (a ⋄ z)^{2}) ⋄ ((a ⋄ z) ⋄ (a ⋄ z)^{2})) = y,

so the claim follows in all cases.

Now we define the operation $\to$ on $M_{X}$ by the following rule.

Definition 14.13 Relation on the free group

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_{R L}$ and $x_{R R} \to x_{L}$ .
(iii) $x = y_{R L}$ , $y_{R R} \to y_{L}$ , and $y_{R} \to y_{R L}$ .
(iv) $y = x_{R}$ , and there exists $z \in {x_{L R}, x_{L R L}, x_{R R}, x_{R R L}}$ 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_{R L}$ , or $x_{R} = x_{L L}$ 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_{R L}$ 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

x = y_{R}, x = y_{R L}, y = x_{R}, y = x_{R L}

hold; in particular, we cannot have $x \to x$ for any $x$ .

We then define a new operation $⋄$ on $M_{X}$ by the rule $x ⋄ y = x$ if $y \to x$ , and $x ⋄ y = x * y$ otherwise. Thus, by definition, $y \to x$ if and only if $x ⋄ y = x$ . We then define $M_{X, 854}$ to be the magma generated by $X$ with the operation $⋄$ ; 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} ↛ w_{L}$ .

Theorem 14.14 Free 854 magma

The magma $M_{X, 854}$ is a free 854 magma on $X$ .

Proof ▶

Let $f : X \to M$ be a function from $X$ to an $854$ magma $M$ , then $φ_{f}$ is a homomorphism from $M_{X}$ (with the operation $*$ ) to $M$ . We claim that the restriction of $φ_{f}$ to $M_{X, 854}$ is a homomorphism from $M_{X, 854}$ (with operation $⋄$ ) to $M$ . Since $φ_{f}$ was already a homomorphism for $*$ , it suffices to show that $φ_{f}$ preserves $\to$ : that is to say, for any $x, y \in M_{X, 854}$ , that $x \to y$ implies $φ_{f} (x) \to φ_{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

(y ⋄ z) ⋄ (x ⋄ z) \to x

for all $x, y, z \in M_{854}$ . Writing $w = y ⋄ z$ , we have $z \to w$ by Definition 14.13(i), and we need to show that $w ⋄ (x ⋄ z) \to x$ . We divide into four cases.

Case 1: $x ⋄ z \to w$ , $z \to x$ . Here we have $x ⋄ z = x$ and $w ⋄ (x ⋄ 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

z = x_{R}, z = x_{R L}, x = z_{R}, x = z_{R L}

holds, one of

z = w_{R}, z = w_{R L}, w = z_{R}, w = z_{R L}

holds, and one of

x = w_{R}, x = w_{R L}, w = x_{R}, w = x_{R L}

holds.

We split into subcases using Equation 11.

If $x = w_{R}$ then the claim follows from Definition 14.13(i).
If $w = x_{R L}$ then from Definition 14.13(iii) we have $x_{R R} \to x_{L}$ , and then the claim follows from Definition 14.13(ii).
If $x = w_{R L}$ , then $w_{R R} \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_{R L}$ . If $z = w_{R}$ then this follows from $z \to x$ . The claim $z = w_{R L}$ is not compatible with Equation 9, since $z = x$ in that case. If $w = z_{R}$ then $x = z_{R R L}$ , and this is only compatible with Equation 9 if $x = z_{R L}$ , thus $z = a * (x * (x * b))$ and $w = x * (x * b)$ for some $a, b$ . In order to have $x = w_{R L}$ 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_{R L} = w_{L}$ then $x_{R R} \to x_{L}$ by Definition 14.13(ii), and the only available options from Equation 10 are $z = w_{R}$ and $z = w_{R L}$ . 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_{R R}$ , we obtain $w \to x$ as required from Definition 14.13(iv).

Case 2: $x ⋄ z \to w$ , $z ↛ 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

w = (x * z)_{R}, w = (x * z)_{R L}, x * z = w_{R}, x * z = w_{R L}

holds, and that one of

w = z_{R}, w = z_{R L}, z = w_{R}, z = w_{R L}

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)_{R L}$ 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_{R L}$ , 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_{R L}$ , then $w = a * ((x * z) * b)$ for some $a, b$ . Then $w$ , $w_{R}$ , and $w_{R L}$ are all longer than $z$ and none of the options in Equation 13 can hold, a contradiction.

Case 3: $x ⋄ z ↛ 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_{R L}, x_{R}, x_{R L}}$ , 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

x = z_{R}, x = z_{R L}

holds, and also one of

w = z_{R}, w = z_{R L}

holds. Thus, we either have one of

w = x, w = x_{L}, x = w_{L} .

But in any of these three cases the claim follows from Definition 14.13(v).

Case 4: $x ⋄ z ↛ w$ , $z ↛ x$ . Then $x = (w ⋄ (x ⋄ z))_{R L}$ 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) ↛ x$ (by Equation 8), so $x * (x * (y * x))$ lies in $M_{X, 854}$ ; finally, $x * (x * (y * x)) ↛ x$ (this follows from Definition 14.13(ii) since $y * x ↛ 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.