Equational Theories

6 Selected magmas

Each magma can be used to establish anti-implications: if \(\Gamma \) is the set of all laws obeyed by a magma \(G\), then we have \(\neg E \leq E'\) whenever \(E \in \Gamma \) and \(E' \not\in \Gamma \). Large numbers of implications can already be obtained from

  • All magmas of order at most \(4\), up to isomorphism (of which there are \(178,985,294\));

  • All commutative magmas of order \(5\), up to isomorphism determine their count;

  • Cyclic groups \(\mathbb {Z}/N\mathbb {Z}\) with \(2 \leq N \leq 12\) and \(x \diamond y = ax^2+bxy+cy^2+dx+ey\) for randomly chosen \(a,b,c,d,e\).

  • There are only \(1410\) distinct cancellative magmas of order \(5\) (up to isomorphism), and Mace4 can generate all of them in under 20 seconds. A shell script to do this is available here. A magma is cancellative if \(xy=xz\) implies \(y=z\) and \(yx=zx\) implies \(y=z\).

Some other magmas have been used to establish counterexamples:

  • The cyclic group \(\mathbb {Z}/6\mathbb {Z}\) with the addition law.

  • The natural numbers with law \(x \diamond y = x+1\).

  • The natural numbers with law \(x \diamond y = xy+1\).

  • The reals with \(x \diamond y = (x+y)/2\).

  • The natural numbers with \(x \diamond y\) equal to \(x\) when \(x=y\) and \(x+1\) otherwise.

  • The set of strings with \(x \diamond y\) equal to \(y\) when \(x=y\) or when \(x\) ends with \(yyy\), or \(xy\) otherwise (see this Zulip thread).

  • Vector spaces \({\mathbb F}_2^n\) over \({\mathbb F}_2\), which obey Definition 2.32 (and hence all the subsequent laws mentioned in Theorem 5.6).

  • Knuth’s construction [ 6 ] of a central groupoid (Definition 2.23) as follows. Let \(S\) be a (finite) set with a distinguished element \(0\), and a binary operation \(*\) such that \(x*0=0\) and \(0*x=x\) for all \(x\), and for each \(x,y\) there is a unique \(z\) with \(x*z=y\). One can then define a central groupoid on \(S \times S\) by defining \((a,b) \diamond (c,d)\) to equal \((b,c)\) if \(c,d \neq 0\); \((b,e)\) if \(b*e=c\) is non-zero and \(d=0\); and \((a*b,0)\) if \(c=0\). One such example in [ 6 ] is when \(S = \{ 0,1,2\} \) with \(1*1=2*1=2\) and \(1*2=2*2=1\).

  • Cancellative magmas of orders 7 to 9, found by hand-guided search using various solvers.

  • Two magmas of cardinality \(8\) were constructed by Z3.

  • A large number of ad-hoc finite magmas were constructed using the Vampire theorem prover. In some cases, inputting theoretical information is useful: see this discussion.

  • Linear magmas \(x\diamond y = ax+by\) on various fields, such as \({\mathbb F}_p\) for small primes \(p\), have also been used to establish counterexamples. One such choice is \((p,a,b) = (11,1,7)\). See this discussion. For a noncommutative example, see this discussion.

  • A variation of the translation-invariant magma construction which resolved the Asterix / Obelix anti-implication is used to show that Definition 2.36 does not imply Definition 2.34.