1 Basic theory of magmas
A magma is a set \(G\) equipped with a binary operation \(\diamond : G \times G \to G\). A homomorphism \(\varphi : G \to H\) between two magmas is a map such that \(\varphi (x \diamond y) = \varphi (x) \diamond \varphi (y)\) for all \(x,y \in G\). An isomorphism is an invertible homomorphism.
Groups, semi-groups, and monoids are familiar examples of magmas. However, in general we do not expect magmas to have any associative properties. In some literature, magmas are also known as groupoids, although this term is also used for a slightly different object (a category with inverses).
A magma is called empty if it has cardinality zero, singleton if it has cardinality one, and non-trivial otherwise.
The number of magma structures on a set \(G\) of cardinality \(n\) is of course \(n^{n^2}\), which is 1
(OEIS A002489). Up to isomorphism, the number of finite magmas of cardinality \(n\) up to isomorphism is the slightly slower growing sequence
(OEIS A001329).
The free magma \(M_X\) generated by a set \(X\) (which we call an alphabet) is the set of all finite formal expressions built from elements of \(X\) and the operation \(\diamond \). An element of \(M_X\) will be called a word with alphabet \(X\). The order of a word is the number of \(\diamond \) symbols needed to generate the word. Thus for instance \(X\) is precisely the set of words of order \(0\) in \(M_X\).
For sake of concreteness, we will take the alphabet \(X\) to default to the natural numbers \(\mathbb {N}\) if not otherwise specified.
For instance, if \(X = \{ 0,1\} \), then \(M_X\) would consist of the following words:
\(0\), \(1\) (the words of order \(0\));
\(0 \diamond 0\), \(0 \diamond 1\), \(1 \diamond 0\), \(1 \diamond 1\) (the words of order \(1\));
\(0 \diamond (0 \diamond 0)\), \(0 \diamond (0 \diamond 1)\), \(0 \diamond (1 \diamond 0)\), \(0 \diamond (1 \diamond 1)\), \(1 \diamond (0 \diamond 0)\), \(1 \diamond (0 \diamond 1)\), \(1 \diamond (1 \diamond 0)\), \(1 \diamond (1 \diamond 1)\), \((0 \diamond 0) \diamond 0\), \((0 \diamond 0) \diamond 1\), \((0 \diamond 1) \diamond 0\), \((0 \diamond 1) \diamond 1\), \((1 \diamond 0) \diamond 0\), \((1 \diamond 0) \diamond 1\), \((1 \diamond 1) \diamond 0\), \((1 \diamond 1) \diamond 1\) (the words of order \(2\));
etc.
For a finite alphabet \(X\), the number of words of order \(n\) is \(C_n |X|^{n+1}\), where \(C_n\) is the \(n^{\mathrm{th}}\) Catalan number and \(X\) is the cardinality of \(X\).
Follows from standard properties of Catalan numbers.
The first few Catalan numbers are
(OEIS A000108).
Given a function \(f: X \to G\) from an alphabet \(X\) to a magma \(G\), the induced homomorphism \(\varphi _f: M_X \to G\) is the unique extension of \(f\) to a magma homomorphism. Similarly, if \(\pi \colon X \to Y\) is a function, we write \(\pi _* \colon M_X \to M_Y\) for the unique extension of \(\pi \) to a magma homomorphism.
For instance, if \(f : \{ 0,1\} \to G\) maps \(0,1\) to \(x,y\) respectively, then
and so forth. If \(\pi \colon \mathbb {N}\to \mathbb {N}\) is the map \(\pi (n) := n+1\), then
and so forth.
Let \(X\) be a set. A law with alphabet \(X\) is a formal expression of the form \(w \simeq w'\), where \(w, w' \in M_X\) are words with alphabet \(X\) (thus one can identify laws with alphabet \(X\) with elements of \(M_X \times M_X\)). A magma \(G\) satisfies the law \(w \simeq w'\) if we have \(\varphi _f( w ) = \varphi _f ( w' )\) for all \(f: X \to G\), in which case we write \(G \models w \simeq w'\).
Thus, for instance, the commutative law
is satisfied by a magma \(G\) if and only if
for all \(x, y \in G\). We refer to Equation 2 as the equation associated to the law Equation 1. One can think of equations as the “semantic” interpretation of a “syntactic” law. However, we shall often abuse notation and identify a law with its associated equation. In particular, we shall (somewhat carelessly) also refer to Equation 2 as “the commutative law” (rather than “the commutative equation”).
A theory is a set \(\Gamma \) of laws. Given a theory \(\Gamma \), a magma \(G\) is a model of \(\Gamma \) with the (overloaded) notation \(G\models \Gamma \) if \(G\models w\simeq w'\) for every \(w\simeq w'\) in \(\Gamma \); we also say that \(G\) obeys \(\Gamma \). Given a law \(E\), we write \(\Gamma \models E\) if every magma \(G\) that models \(\Gamma \), also models \(E\).
Given a theory \(\Gamma \) and a law \(w\simeq w'\) over a fixed alphabet \(X\), we say that \(\Gamma \) derives \(w\simeq w'\), and write \(\Gamma \vdash w\simeq w'\), if the law can be obtained using a finite number of applications of the following rules:
if \(w\simeq w' \in \Gamma \), then \(\Gamma \vdash w\simeq w'\).
\(\Gamma \vdash w\simeq w\) for any word \(w\).
if \(\Gamma \vdash w\simeq w'\), then \(\Gamma \vdash w'\simeq w\).
if \(\Gamma \vdash w\simeq w'\) and \(\Gamma \vdash w'\simeq w''\), then \(\Gamma \vdash w\simeq w''\).
if \(\Gamma \vdash w\simeq w'\), then \(\Gamma \vdash \varphi _f(w) \simeq \varphi _f(w')\) for every \(f: X \to M_X\).
if \(\Gamma \vdash w_1\simeq w_2\) and \(\Gamma \vdash w_3\simeq w_4\), then \(\Gamma \vdash w_1 \diamond w_3\simeq w_2\diamond w_4\).
This definition is useful because of the following theorem:
For any theory \(\Gamma \) and words \(w, w'\) over a fixed alphabet
(Sketch) The ‘only if’ component is soundness, and follows from verifying that the rules of inference in Definition 1.7 holds for \(\models \). The ‘if’ part is completeness, and is proven by constructing the magma of words, quotiented out by the relation \(\Gamma \vdash w \simeq w'\), which is easily seen to be an equivalence relation respecting the magma operation.
Let \(\Gamma \) be a theory, and let \(E\) be a law. Then \(\Gamma \models E\) if and only if there exists a finite subset \(\Gamma '\) of \(\Gamma \) such that \(\Gamma ' \models E\).
The claim is obvious for \(\vdash \), and the claim then follows from Theorem 1.8.
Let \(w \simeq w'\) be a law with some alphabet \(X\), \(G\) be a magma, and \(\pi : X \to Y\) be a function. If \(G \models w \simeq w'\), then \(G \models \pi _*(w) \simeq \pi _*(w')\). In particular, if \(\pi \) is a bijection, the statements \(G \models w \simeq w'\) and \(G \models \pi _*(w) \simeq \pi _*(w')\) are equivalent.
Trivial.
If \(\pi \) is a bijection, we will call \(\pi _*(w) \simeq \pi _*(w')\) a relabeling of the law \(w \simeq w'\). Thus for instance
is a relabeling of the commutative law Equation 1. By the above lemma, relabeling does not affect whether a given magna satisfies a given law.
Let \(G\) be a magma and \(X\) be an alphabet. Then the relation \(G \models w \simeq w'\) is an equivalence relation on \(M_X\).
Trivial.
Define the total order of a law \(w \simeq w'\) to be the sum of the orders of \(w\) and \(w'\).
Up to relabeling, the number of laws \(w \simeq w'\) of total order \(n\) is \(C_{n+1} B_{n+2}\).
Follows from the properties of Catalan and Bell numbers.
The first few Bell numbers are
(OEIS A000110).
The sequence in Lemma 1.12 is
(OEIS A289679).
Now we would also like to count laws up to relabeling and symmetry.
Up to relabeling and symmetry, the number of laws \(w \simeq w'\) of total order \(n\) is
when \(n\) is odd, and
when \(n\) is even, where \(D_n\) is the number of partitions of \([n]\) up to reflection.
Elementary counting.
The sequence \(D_n\) is
(OEIS A103293), and the sequence in Lemma 1.13 is
(OEIS A376620).
We can also identify all laws of the form \(w \simeq w\) with the trivial law \(0 \simeq 0\). The number of such laws of total order \(n\) is zero if \(n\) is odd, and \(C_{n/2} B_{n/2+1}\) if \(n\) is even. We conclude:
Up to relabeling, symmetry, and triviality, the number of laws of total order \(n\) is
if \(n\) is odd, \(2\) if \(n = 0\), and
if \(n \geq 2\) is even.
Routine counting.
This sequence is
(OEIS A376640).
In particular, up to relabeling, symmetry, and triviality, there are exactly \(2+5+39+364+4284=4694\) laws of total order at most \(4\). A list can be found here. A script for generating them may be found here. The ordering of these equations is according to the following rules. First, an ordering on expressions (such as \(0 \diamond (1 \diamond 0)\)):
(i) Expressions of lower order come before expressions of higher order.
(ii) Expressions \(w_L \diamond w_R\) of a given total order that is at least one are ordered lexicographically first by the ordering on the left component \(w_L\), and then by the ordering on the right component \(w_R\) if the left components agree.
(iii) Among single variables, \(0, 1, \dots \), we order numerically.
Then, we order equations such as \(w \simeq w'\):
(i) Equations of lower total order come before equations of higher total order.
(ii) Equations \(w \simeq w'\) of a given total order are ordered lexicographically first by the ordering on the left-hand side \(w\), and then by the ordering on the right hand side \(w'\) if the left-hand sides agree.
(iii) Only the form of the equation (up to relabeling and symmetry) which is minimal in this ordering is retained in the list. For instance, we do not retain \(1 \diamond 2 \simeq 1\) because it can be replaced by \(0 \simeq 0 \diamond 1\), which is earlier in the ordering.
(iv) Any trivial equation \(w \simeq w\), other than the order zero law \(0 \simeq 0\), is discarded.