7 Infinite magma constructions

The need to construct infinite magmas primarily arises in the context of Austin laws and Austin pairs. An Austin law admits infinite models but no nontrivial finite ones, while an Austin pair consists of laws \(P\) and \(Q\) such that every finite model obeying the law \(P\) also obeys \(Q\), but some infinite magma obeys \(P\) without also obeying \(Q\). Examples are given in Chapter 3.

Here we survey techniques for constructing infinite magmas that serve as counterexamples for implications between laws. Many of the techniques presented trace their origins to the first analysis of the Asterix equation (Definition 2.22), reviewed in Section 7.2.

7.1 Translation-invariant magmas

A translation-invariant magma is a magma whose carrier \(G\) is an Abelian group \(G = (G,+)\), and whose magma operation takes the form

for some function \(f: G \to G\). Thus the translations on \(G\) become magma isomorphisms.

Note that if an example of the latter sort suffices to refute the implication between \(P\) and \(Q\) then by the Lefschetz principle one can construct a counterexample where the field \(\mathbb {F}\) is finite. Consequently, \(P\) and \(Q\) cannot constitute an Austin pair. However, these linear magmas can still serve as starting points for the modified translation-invariant models studied in Section 7.5.

7.2 The Asterix equation

Over translation-invariant magmas, equational laws simplify to univariate functional equations.

For instance, writing \(x = y+h\), we have

where \(f^2 = f \circ f\), so the Asterix equation (Definition 2.22) for such magmas simplifies to the univariant functional equation

for \(h \in G\).

This equation has some degenerate solutions, for instance we can take \(f(h) = c\) for any constant \(c\) of order \(3\) in \(G\). It is challenging to construct more interesting solutions to this equation; however, we can do this if \(G=\mathbb {Z}\) by a greedy algorithm. We need the following technical definition.

We have the following iterative construction, that lets us add arbitrary elements to the core domain \(E_0\):

On the other hand, for finite magmas the situation is different:

A very similar argument shows that a finite magma that obeys the Obelix law has \(z \mapsto y \diamond z\) injective, hence surjective, and then obeys the Asterix law.

7.3 Obelix

Obelix magmas are those obeying equation 1491, Definition 2.31:

Obelix is not particularly structurally similar to an Asterix, besides their shared resistance to small counterexamples. A related set of ideas can be used to construct an Obelix that does not obey some given other equations. The common idea is to define the magma operation

on some underlying Abelan group. For the case of Obelix, the resulting functional equation is

What differs is how we must proceed in order to satisfy this equation. We again start with a partial function \(f\), picking some initial support that will suffice to invalidate the other equation we want to show a nonimplication for. We will progressively add more elements to the support (assuming our group is countable) until the function is total, and we will maintain some invariants:

It’s easiest to work over the group of finitely supported functions from \(\mathbb {N}\) (or any other countable set) to \(\mathbb {Z}\). When picking fresh elements, it’s important not only to take something outside of the group closure of the elements already in \(f\), but actually out of their \(\mathbb {Q}\)-span, because we need guarantees that the fresh element \(g\) doesn’t obey relations like \(2g = x\) as well.

Any partial solution can be extended to a complete solution.

The actual mechanical proof requires checking roughly a few dozen statements of the form "the fresh element is not related linearly to the existing elements". Each is individually obvious, and easily discharged.

By picking an appropriate partial solution, we can then show that there are Obelix magmas that are not Asterix.

7.4 Greedy algorithm constructions

In Section 7.2 a magma obeying one law and refuting another was obtained by using the fact that over translation-invariant magmas, equational laws simplify to univariate functional equations, and solving the resulting equation using a greedy algorithm.

One way to construct infinite magmas obeying specific laws is via a greedy algorithm construction not on a one-variable functional equation, but on the operation table of the magma itself.

Here, it is best to work with partially defined magma operations on some carrier \(G\). These can be interpreted as ternary relations \(R(x,y,z)\) in three variables \(x,y,z \in G\) which pass the following “vertical line test”:

(VLT)

If \(R(x,y,z)\) and \(R(x,y,z')\) both hold for some \(x,y,z,z' \in G\), then \(z=z'\).

Such an operation is then associated (via a one-to-one correspondence) to a partially defined operation \(\diamond : S \to G\) for some \(S \subset G \times G\), with \(R(x,y,z)\) holding if and only if \(x \diamond y\) is well-defined (i.e., \((x,y) \in S\)) and equal to \(z\). By abuse of notation, we shall also refer to \(R\) as a partially defined magma operation. Genuine magmas then correspond to the special case where \(S = G \times G\), that is to say \(x \diamond y\) is well-defined for all \(x,y \in G\).

Given a word \(w(x_1,\dots ,x_n)\) in variables \(x_1,\dots ,x_n\) (so \(w\) is an element of the free magma on \(n\) generators), we can say that \(w(x_1,\dots ,x_n)\) is well-defined with respect to a partially defined magma operation \(R\) if it can be fully evaluated using \(R\). For instance, the word \((x \diamond y) \diamond z\) is well-defined if there exists \(w,u \in G\) such that \(R(x,y,w)\) and \(R(w,z,u)\) both hold, in which case \((x \diamond y) \diamond z\) evaluates to \(u\). Note from the axiom (VLT) that this evaluation is unique, if it exists. Of course, in a genuine magma, all expressions are well-defined. We say that an expression \(w(x_1,\dots ,x_n)\) is almost well-defined if all strict subexpressions of \(w\) are well-defined. For instance, \((x \diamond y) \diamond z\) is almost well-defined if there exists \(w \in G\) such that \(R(x,y,w)\) holds.

An equational law \(w_1 \simeq w_2\) involving some variables \(x_1,\dots ,x_n\) is said to be locally obeyed by \(R\) if, whenever \(w_1(x_1,\dots ,x_n)\), \(w_2(x_1,\dots ,x_n)\) are almost well-defined, and one of the two expressions is well-defined and evaluates to some output \(y\), then the other expression is also well-defined and evaluates to the same output \(y\). For instance, in order for \(R\) to locally obey the associative law \((x \diamond y) \diamond z = x \diamond (y \diamond z)\) (Definition 2.46), we require the following two axioms:

(4512-1)

If \(R(x,y,w)\), \(R(w,z,u)\), and \(R(y,z,v)\), then \(R(x,v,u)\).

(4512-2)

If \(R(y,z,w)\), \(R(x,w,u)\), and \(R(x,y,v)\), then \(R(v,z,u)\).

If a law involves a single variable on one side, then we only need one axiom. For instance, the Asterix law (Definition 2.22) is locally obeyed by \(R\) if and only if the following axiom holds:

(65)

If \(R(y,x,z)\) and \(R(x,z,u)\), then \(R(y,u,x)\).

Note that if the relation \(R\) is associated to a genuine magma operation \(\diamond \), then it locally obeys a law \(w_1 \simeq w_2\) if and only if the magma operation \(\diamond \) obeys the law \(w_1 \simeq w_2\). For instance, the relation \(R\) associated to a globally defined magma operation \(\diamond \) obeys (4512-1) and (4512-2) if and only if the magma is associative.

More generally, one can ask for a ternary relation \(R\) to obey some theory \(\Gamma \) of universal laws, using the language of one ternary relation \(R\), the equality symbol \(=\), and possibly some constants (we will shortly introduce three constants \(a,b,c\) for this purpose).

Suppose we have a relation \(R\) obeying some theory \(\Gamma \) (for instance, (VLT) together with (65)), but which is only finitely supported (there are only finitely many triples \((x,y,z)\) for which \(R(x,y,z)\) holds). Then one can find \(a,b \in G\) such that \(a \diamond b\) is currently undefined. If the carrier \(G\) is infinite (e.g., if \(G = \mathbb {N}\)), one can then find another element \(c\) which is novel: it is not equal to \(a, b\), or any of the \(x,y,z\) for which \(R(x,y,z)\) hold. In other words, the relation \(R\) and the constants \(a,b,c\) obey the following additional axioms:

(novel-1)

\(c \neq a\) and \(c \neq b\).

(novel-2)

If \(R(x,y,z)\), then \(c \neq x\), \(c \neq y\), and \(c \neq z\).

(undefined)

\(R(a,b,x)\) does not hold for any \(x\).

Let us say that a theory \(\Gamma \) is greedily extensible if, whenever \(R\) is a finitely supported ternary relation obeying \(\Gamma \), and \(a,b,c\) are constants obeying (novel-1), (novel-2), (undefined), then there exists an extension \(R'\) of \(R\), thus

(extend)

\(R(x,y,z) \implies R'(x,y,z)\) for all \(x,y,z\),

which is also finitely supported and obeys \(\Gamma \), and which also obeys the additional axiom

(define)

\(R'(a,b,c)\).

Informally, \(R'\) is formed from \(R\) by “forcing” \(a \diamond b = c\) and then adding other axioms as needed. (Indeed, our construction here can be viewed as a simple analogue of the forcing construction in set theory.)

Observe that if a theory \(\Gamma \) containing (VLT) is greedily extensible, then any finitely supported ternary relation \(R\) obeying \(\Gamma \) on a countably infinite carrier \(G\) can be extended to a globally defined relation obeying \(\Gamma \), by iteratively selecting the first \((a,b)\) (in some fixed enumeration of \(G \times G\)) for which \(a \diamond b\) is undefined, and then selecting a novel element \(c\) to define as \(a \diamond b\), and applying the greedily extensible property, and then taking a direct limit of the countable sequence of relations thus produced. This gives a flexible way to construct magmas that obey a given theory \(\Gamma \), but which violate some other law \(w_1 \simeq w_2\), as the task then reduces to just finding a partial solution \(R\) to \(\Gamma \) and some constants \(x_1,\dots ,x_n\) for which the expressions \(w_1(x_1,\dots ,x_n), w_2(x_1,\dots ,x_n)\) are already well-defined, but not equal to each other.

Unfortunately, most theories are not greedily extensible without further modification. Consider for instance the theory \(\Gamma \) consisting of (VLT) and the Asterix law (65). Given \(a,b,c\) and a finitely supported \(R\) obeying \(\Gamma \) as well as (novel-1), (novel-2), (undefined), we would like to construct a finitely supported \(R'\) obeying \(\Gamma \), (extend), (define). The naive guess would just be to take the minimal construction

This can work, but there is an obstruction: if \(R(w,a,b)\) for some \(w\), then (65) forces \(R'(w,c,a)\). So one would have to enlarge the definition of \(R'(x,y,z)\), to hold true if one of the following statements holds:

• \(R(x,y,z)\) holds.

• \((x,y,z) = (a,b,c)\).

• \((x,y,z) = (w,c,a)\) for some \(w\) with \(R(w,a,b)\).

This works more often, but there is then a second obstruction: if \(R(b,a,b)\), then we now have \(R'(b,c,a)\), and (65) then forces \(R'(a,a,b)\). So we need to add a fourth item to the above list defining \(R'\):

• \((x,y,z) = (a,a,b)\), assuming \(R(b,a,b)\) holds.

But now if we had \(R(a,a,z)\) for some \(z \neq b\), this would then create a violation of (VLT). To fix this, we need to extend \(\Gamma \) by adding an additional axiom:

• (65’) If \(R(y,x,y)\), then \(R(x,x,y)\).

With this modification to \(\Gamma \), if we run the above analysis, we now see that if \(R(b,a,b)\) hold (so that \(R(a,a,b)\) also holds), then (65) will force \(R'(a,c,a)\), \(R'(b,c,a)\), and \(R'(c,c,a)\). So now the modified definition of \(R'\) is that \(R'(x,y,z)\) holds if one of the following statements holds:

• \(R(x,y,z)\) holds.

• \((x,y,z) = (a,b,c)\).

• \((x,y,z) = (w,c,a)\) for some \(w\) with \(R(w,a,b)\).

• \((x,y,z) = (a,c,a)\), \((b,c,a)\), or \((c,c,a)\), assuming \(R(b,a,b)\) holds.

One can then finally (for instance, with the assistance of a automated theorem prover) verify that if \(R\) is finitely supported and obeys \(\Gamma = (VLT) + (65) + (65')\) and \(a,b,c\) obey (novel-1), (novel-2), (undefined), then the \(R'\) defined above is also finitely supported and obeys \(\Gamma \), (extend), (define). This shows that the theory \(\Gamma \) is greedily extensible.

Using this, one can for instance find a magma obeying Definition 2.22 that fails the left-cancellative property

or in terms of ternary relations

simply by starting with a partial solution, say on the natural numbers in which (e.g.) \(R(1,2,0)\), \(R(1,3,0)\) are the only situations in which \(R\) holds. One can easily verify that this obeys (VLT) and (65), (65’), but not 3, and so any magma constructed by the above greedy construction will not be left-cancellative. Since the Obelix law Definition 2.31 forces left-cancellativity, this gives an alternate proof of Corollary 7.5

7.5 A survey of examples

7.5.1 Translation-invariant models

The implication between the laws Definition 2.33 and Definition 2.24 can be refuted by a translation-invariant magma on the integers. Define the function \(f: \mathbb {Z} \to \mathbb {Z}\) by

and consider the translation-invariant magma on \(\mathbb {Z}\) given by the operation \(x \diamond y = x + f(y-x)\).

The resulting magma satisfies Equation 1648: one can show this by a case analysis on \(f(y-x)\). If \(f(y-x)=1\) we have \(x \diamond y = x + f(y-x) = x + 1\), so

Similar computations verify the other two cases.

However, setting \(x=0\) and \(y=-1\) in Equation 206, we get

so the magma does not obey Definition 2.24. We can conclude

There are variation of the translation-invariant constructions refuting implications: e.g. in some cases, similar constructions are carried out starting with a non-Abelian group. Translation-invariant models are also useful building blocks for the modified base model constructions explained below.

7.5.2 Modified base models

For some pairs of laws \(P\) and \(Q\), it is possible to start with an infinite model \((M,\diamond )\) obeying both \(P\) and \(Q\), then modify the operation \(\diamond \) in a limited way, resulting in a model \((M,\diamond ')\) of \(P\) that does not obey \(Q\).

This works especially well when this base model \((M,\diamond )\) is a translation-invariant magma in which the function \(f\) takes finitely many different values. This is common: e.g. the translation-invariant model refuting the implication above is of the required sort!

The strategy is to first modify the magma operation in a naive way, by introducing a counterexample to the consequent \(Q\). This generally yields one or more counterexamples to the antecedent \(P\), but one can trace the effects of this initial modification and make further adjustments which restore the antecedent.

A model refuting the implication between the laws Definition 2.35 and Definition 2.45 can be constructed using the modified base model technique. Start with the infinite model \((\mathbb {Z},\diamond )\) of Definition 2.35 given by the following operation:

A case analysis shows that the magma \((\mathbb {Z},\diamond )\) satisfies both Definition 2.35 and Definition 2.45. We will eventually modify it by setting

and checking that \((\mathbb {N}, \diamond ' )\) satisfies Definition 2.35 but refutes Definition 2.45.

One finds these modifications using the following strategy:

First, choose some element (tuple) of the carrier \(M\) that will constitute a counterexample to the consequent in the modified model. In this specific case, the consequent, Definition 2.45, can be written as

in equational form, which always holds when \(x = z\). So let’s choose the tuple \((0,0,1)\) to constitute the required counterexample. Computing \(0 \diamond (0 \diamond 0) = 0 \diamond 1 = -1\) and similarly \(0 \diamond (0 \diamond 1) = -1\) suggest that we could force this tuple to be a counterexample by defining a new operation \(\diamond ''\) and setting \(0 \diamond '' 1\) to something other than \(-1\). One seemingly has many choices here: should we take \(0 \diamond '' 1 =0\), \(0 \diamond '' 1 = 1\), \(0 \diamond '' 1 = 2\), or perhaps even \(0 \diamond '' 1 = -1\)?

It’s easy to rule out some of the possibilities. For instance, setting \(0 \diamond '' 1 = 1\) would yield \(0 \diamond '' (0 \diamond '' 0) = 0 \diamond '' 1 = 0 \diamond '' (0 \diamond '' 1)\) again. The simplest possibility which results in a counterexample to Definition 2.45 sets \(0 \diamond '' 1 = 0\) and \(x \diamond '' y = x \diamond y\) for any \(x \neq 0, y \neq 1\).

Unfortunately, the resulting \((M,\diamond '')\) would not then obey Definition 2.35. For any \(z \in M\), one would have

which equals \(0 \diamond '' 1 = 0\) as desired for even \(z\), but equals \(0 \diamond '' 3 = -1 \neq 0\) for odd \(z\).

However, since \(f\) takes finitely many values in the base model, the breakage is tightly controlled: by considering what happens if \(x \neq 0\) and \(y \neq 1\), we see that all new counterexamples to Definition 2.45 have this form. The calculation now suggests defining yet another \(\diamond '''\), where setting \(0 \diamond ''' 3 = 0\) would eliminate this counterexample. But doing that just moves the issue one level higher: one then has

which equals \(0 \diamond ''' 3 = 0\) as desired for even \(z\), but equals \(0 \diamond ''' 5 = -1 \neq 0\) for odd \(z\).

Instead, the infinitely many counterexamples arising from the iterated redefinition can be eliminated all at once by setting:

At this point one might as well truncate the model to \(\mathbb {N}\) since the result of the \(\diamond '\) operation is nonnegative whenever the operands are nonnegative. This finishes the construction and proves

The result of a modified base model construcblution can be a finite modification (when \(\diamond \) and \(\diamond '\) differ in finitely many inputs) or one in which they differ in infinitely many coefficients. Note that if the base model \((M,\diamond )\) was obtained by a greedy construction, and \((M,\diamond ')\) is a finite modification, then the modified model could also have been obtained using the same greedy construction. It is not surprising that more difficult refutations using this construction tend to require the latter sort of modification.

7.6 The Dupont equation

Now we consider the Dupont equation, Definition 2.21, which can be treated by a greedy translation invariant construction that is more complicated than the one considered for the Asterix law in Section 7.2.

If we adopt a translation-invariant model

on some abelian group \(G\), then with \(y = x+h\), we have

and so the Dupont law \(x = y \diamond (x \diamond (x \diamond y))\) becomes the functional equation

One way to solve this equation is to have an automorphism \(T: G \to G\) that obeys the identity

then one can just take \(f(h) = T(h)\). For instance, if \(G = \mathbb {Z}^3\), one can take the automorphism \(T: \mathbb {Z}^3 \to \mathbb {Z}^3\) defined by

We now extend this greedily to \(\mathbb {Z}^3 \times \mathbb {Z}\) as follows. Define a partial solution \((E_1,E_2,f)\) to be a pair \(\mathbb {Z}^3 \subset E_1 \subset E_2 \subset \mathbb {Z}^3 \times \mathbb {Z}\), and a function \(f: E_2 \to E_1\) obeying the following axioms.

(a)

The set \(E_2 \backslash \mathbb {Z}^3\) is finite.

(b)

For \(h \in \mathbb {Z}^3\), \(f(h) = Th\); in particular, \(f\) is a bijection on \(\mathbb {Z}^3\).

(c)

For \(h \in E_1 \backslash \mathbb {Z}^3\), \(f(h) \in E_1\). Also, \(-h + f^2(h) \in E_1\) and \(f(-h + f^2(h)) = -h\). Note that this (and (b)) implies that \(-h \in E_1\), thus \(E_1\) is symmetric around the origin.

(d)

For \(h \in E_2 \backslash E_1\), \(f(h) \in E_1\).

(e)

The elements \(-h\), \(h - f^2(h)\), and \(f^2(h) - h\) for \(h \in E_2 \backslash E_1\) are all distinct from each other, and all lie outside of \(E_2\). In particular this forces \(f^2(h) \neq 0\), hence \(f(h) \neq 0\). It also forces \(f^2(h) \neq h\), hence \(f(h) \neq h\).

Thus for instance one can take \((\mathbb {Z}^3,\mathbb {Z}^3,T)\) as a partial solution. We say that a partial solution \((E'_1, E'_2, f')\) is an extension of \((E_1,E_2,f)\) if \(E_1 \subset E'_1\), \(E'_2 \subset E_2\), and \(f'\) agrees with \(f\) on \(E_2\).

Informally, \(E_1\) represents the portion of \(\mathbb {Z}^3 \times \mathbb {Z}\) where we have completely resolved the Dupont equation; the set \(E_2 \backslash E_1\) represents the portion for which \(f\) (and all forward iterates of \(f\)) have been defined, but the Dupont equation has not yet been verified; and the elements \(-h\), \(h - f^2(h)\), and \(f^2(h) - h\) for \(h \in E_2 \backslash E_1\) are the portion where \(f\) is not yet defined, but for which one is ready to “promote” these elements to \(E_2\) or \(E_1\) by defining \(f\) appropriately.

The key lemmas are then

Iterating these lemmas in the usual fashion, we can conclude that any partial solution can be completed to a global model of Definition 2.21.

Among other things, this permits one to generate models in which the function \(f\) is not injective. To see this, let \(a\) be a non-zero element of \(\mathbb {Z}^3\), let \(x\) be an element of \(\mathbb {Z}^3 \times \mathbb {Z}\) outside of \(\mathbb {Z}^3\), and consider the partial solution \((\mathbb {Z}^3, \mathbb {Z}^3 \cup \{ x\} , f)\) where \(f(h) = Th\) for \(h \in \mathbb {Z}^3\) and \(f(x) = a\). One can check that this is a partial solution and is not injective, since \(f(x) = f(T^{-1} a)\). This non-injectivity implies in particular that the model is not left-cancellative, and hence does not obey the law

(equation 1692).

7.6.1 Second construction

We now give a second construction, with works on the integers \(G = \mathbb {Z}\).

We first define a seed solution \(f_0: E_0 \to \mathbb {Z}\) defined on the set \(E_0 := \{ -7, -3, -2, -1, 0, 1, 3, 4, 6 \} \) with

In this construction, we define a partial solution to be a function \(f: E \to \mathbb {Z}\) defined on a finite subset of \(E\) obeying the following axioms:

• \(E\) contains \(E_0\), and \(f\) agrees with \(f_0\) on \(E_0\).

• If \(h \in E\) and \(f(h) \in E\), then \(f^2(h)-h\) is also in \(E\), and \(f(f^2(h)-h) = -h\).

• If \(h \in E\) and \(h \neq 3\), then \(f(h) \neq 0\).

• If \(a \neq a'\) are distinct elements of \(E\) with \(f(a)=f(a')\), and \(-a \in E\), then \(a' \neq a + f(-a)\).

• If \(a \neq a'\) are distinct elements of \(E\) with \(f(a)=f(a')\), and \(-a, -a' \in E\), then \(a' + f(-a') \neq a + f(-a)\).

We say that a partial solution \(f': E' \to \mathbb {Z}\) extends another \(f: E \to \mathbb {Z}\) if \(E'\) contains \(E\) and \(f'\) agrees with \(f\) on \(E\).

Iterating this lemma, we conclude

7.7 An ad hoc model