1 Basic theory of magmas

Definition 1.1 Magma

✓

A magma is a set $G$ equipped with a binary operation $⋄ : G \times G \to G$ . A homomorphism $φ : G \to H$ between two magmas is a map such that $φ (x ⋄ y) = φ (x) ⋄ φ (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, 1, 16, 19683, 4294967296, 298023223876953125, \dots

(OEIS A002489). Up to isomorphism, the number of finite magmas of cardinality $n$ up to isomorphism is the slightly slower growing sequence

1, 1, 10, 3330, 178981952, 2483527537094825, 14325590003318891522275680, \dots

(OEIS A001329).

Definition 1.2 Free Magma

✓

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 $⋄$ . An element of $M_{X}$ will be called a word with alphabet $X$ . The order of a word is the number of $⋄$ 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 $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 ⋄ 0$ , $0 ⋄ 1$ , $1 ⋄ 0$ , $1 ⋄ 1$ (the words of order $1$ );
$0 ⋄ (0 ⋄ 0)$ , $0 ⋄ (0 ⋄ 1)$ , $0 ⋄ (1 ⋄ 0)$ , $0 ⋄ (1 ⋄ 1)$ , $1 ⋄ (0 ⋄ 0)$ , $1 ⋄ (0 ⋄ 1)$ , $1 ⋄ (1 ⋄ 0)$ , $1 ⋄ (1 ⋄ 1)$ , $(0 ⋄ 0) ⋄ 0$ , $(0 ⋄ 0) ⋄ 1$ , $(0 ⋄ 1) ⋄ 0$ , $(0 ⋄ 1) ⋄ 1$ , $(1 ⋄ 0) ⋄ 0$ , $(1 ⋄ 0) ⋄ 1$ , $(1 ⋄ 1) ⋄ 0$ , $(1 ⋄ 1) ⋄ 1$ (the words of order $2$ );
etc.

Lemma 1.3

✓

For a finite alphabet $X$ , the number of words of order $n$ is $C_{n} | X |^{n + 1}$ , where $C_{n}$ is the $n^{th}$ Catalan number and $X$ is the cardinality of $X$ .

Proof ▶

The first few Catalan numbers are

1, 1, 2, 5, 14, 42, 132, \dots

(OEIS A000108).

Definition 1.4 Induced homomorphism

Given a function $f : X \to G$ from an alphabet $X$ to a magma $G$ , the induced homomorphism $φ_{f} : M_{X} \to G$ is the unique extension of $f$ to a magma homomorphism. Similarly, if $π : X \to Y$ is a function, we write $π_{*} : M_{X} \to M_{Y}$ for the unique extension of $π$ to a magma homomorphism.

For instance, if $f : {0, 1} \to G$ maps $0, 1$ to $x, y$ respectively, then

φ_{f} (0 ⋄ 1) = x ⋄ y

φ_{f} (1 ⋄ (0 ⋄ 1)) = y ⋄ (x ⋄ y)

and so forth. If $π : N \to N$ is the map $π (n) := n + 1$ , then

π_{*} (0 ⋄ 1) = 1 ⋄ 2

π_{*} (1 ⋄ (0 ⋄ 1)) = 2 ⋄ (1 ⋄ 2)

and so forth.

Definition 1.5 Law

✓

Let $X$ be a set. A law with alphabet $X$ is a formal expression of the form $w ≃ 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 ≃ w^{'}$ if we have $φ_{f} (w) = φ_{f} (w^{'})$ for all $f : X \to G$ , in which case we write $G ⊨ w ≃ w^{'}$ .

Thus, for instance, the commutative law

0 ⋄ 1 ≃ 1 ⋄ 0

is satisfied by a magma $G$ if and only if

x ⋄ y = y ⋄ x

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”).

Definition 1.6 Models

✓

A theory is a set $Γ$ of laws. Given a theory $Γ$ , a magma $G$ is a model of $Γ$ with the (overloaded) notation $G ⊨ Γ$ if $G ⊨ w ≃ w^{'}$ for every $w ≃ w^{'}$ in $Γ$ ; we also say that $G$ obeys $Γ$ . Given a law $E$ , we write $Γ ⊨ E$ if every magma $G$ that models $Γ$ , also models $E$ .

Definition 1.7 Derivation

✓

Given a theory $Γ$ and a law $w ≃ w^{'}$ over a fixed alphabet $X$ , we say that $Γ$ derives $w ≃ w^{'}$ , and write $Γ ⊢ w ≃ w^{'}$ , if the law can be obtained using a finite number of applications of the following rules:

if $w ≃ w^{'} \in Γ$ , then $Γ ⊢ w ≃ w^{'}$ .
$Γ ⊢ w ≃ w$ for any word $w$ .
if $Γ ⊢ w ≃ w^{'}$ , then $Γ ⊢ w^{'} ≃ w$ .
if $Γ ⊢ w ≃ w^{'}$ and $Γ ⊢ w^{'} ≃ w^{″}$ , then $Γ ⊢ w ≃ w^{″}$ .
if $Γ ⊢ w ≃ w^{'}$ , then $Γ ⊢ φ_{f} (w) ≃ φ_{f} (w^{'})$ for every $f : X \to M_{X}$ .
if $Γ ⊢ w_{1} ≃ w_{2}$ and $Γ ⊢ w_{3} ≃ w_{4}$ , then $Γ ⊢ w_{1} ⋄ w_{3} ≃ w_{2} ⋄ w_{4}$ .

This definition is useful because of the following theorem:

Theorem 1.8 Birkhoff’s completeness theorem

✓

For any theory $Γ$ and words $w, w^{'}$ over a fixed alphabet

Γ ⊢ w ≃ w^{'} iff Γ ⊨ w ≃ w^{'} .

Proof ▶

(Sketch) The ‘only if’ component is soundness, and follows from verifying that the rules of inference in Definition 1.7 holds for $⊨$ . The ‘if’ part is completeness, and is proven by constructing the magma of words, quotiented out by the relation $Γ ⊢ w ≃ w^{'}$ , which is easily seen to be an equivalence relation respecting the magma operation.

Corollary 1.9 Compactness theorem

Let $Γ$ be a theory, and let $E$ be a law. Then $Γ ⊨ E$ if and only if there exists a finite subset $Γ^{'}$ of $Γ$ such that $Γ^{'} ⊨ E$ .

Proof ▶

The claim is obvious for $⊢$ , and the claim then follows from Theorem 1.8.

Lemma 1.10 Pushforward

Let $w ≃ w^{'}$ be a law with some alphabet $X$ , $G$ be a magma, and $π : X \to Y$ be a function. If $G ⊨ w ≃ w^{'}$ , then $G ⊨ π_{*} (w) ≃ π_{*} (w^{'})$ . In particular, if $π$ is a bijection, the statements $G ⊨ w ≃ w^{'}$ and $G ⊨ π_{*} (w) ≃ π_{*} (w^{'})$ are equivalent.

Proof ▶

If $π$ is a bijection, we will call $π_{*} (w) ≃ π_{*} (w^{'})$ a relabeling of the law $w ≃ w^{'}$ . Thus for instance

5 ⋄ 7 ≃ 7 ⋄ 5

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.

Lemma 1.11 Equivalence

Let $G$ be a magma and $X$ be an alphabet. Then the relation $G ⊨ w ≃ w^{'}$ is an equivalence relation on $M_{X}$ .

Proof ▶

Define the total order of a law $w ≃ w^{'}$ to be the sum of the orders of $w$ and $w^{'}$ .

Lemma 1.12 Counting laws up to relabeling

Up to relabeling, the number of laws $w ≃ w^{'}$ of total order $n$ is $C_{n + 1} B_{n + 2}$ .

Proof ▶

The first few Bell numbers are

1, 1, 2, 5, 15, 52, 203, \dots

(OEIS A000110).

The sequence in Lemma 1.12 is

2, 10, 75, 728, 8526, 115764, \dots

(OEIS A289679).

Now we would also like to count laws up to relabeling and symmetry.

Lemma 1.13 Counting laws up to relabeling and symmetry

Up to relabeling and symmetry, the number of laws $w ≃ w^{'}$ of total order $n$ is

C_{n + 1} B_{n + 2} / 2

when $n$ is odd, and

(C_{n + 1} B_{n + 2} + C_{n / 2} (2 D_{n + 2} - B_{n + 2})) / 2

when $n$ is even, where $D_{n}$ is the number of partitions of $[n]$ up to reflection.

Proof ▶

The sequence $D_{n}$ is

1, 1, 2, 4, 11, 32, 117, \dots

(OEIS A103293), and the sequence in Lemma 1.13 is

2, 5, 41, 364, 4294, 57882, 888440, \dots

(OEIS A376620).

We can also identify all laws of the form $w ≃ w$ with the trivial law $0 ≃ 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:

Lemma 1.14 Counting laws up to relabeling, symmetry, and triviality

Up to relabeling, symmetry, and triviality, the number of laws of total order $n$ is

C_{n + 1} B_{n + 2} / 2

if $n$ is odd, $2$ if $n = 0$ , and

(C_{n + 1} B_{n + 2} + C_{n / 2} (2 D_{n + 2} - B_{n + 2})) / 2 - C_{n / 2} B_{n / 2 + 1}

if $n \geq 2$ is even.

Proof ▶

This sequence is

2, 5, 39, 364, 4284, 57882, 888365, \dots

(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 with placeholder variables $*$ (such as $* ⋄ (* ⋄ *)$ ):

(i) Expressions of lower order come before expressions of higher order.
(ii) Expressions $w_{L} ⋄ 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.

For instance, $* ⋄ *$ is less than $* ⋄ (* ⋄ *)$ , which is less than $(* ⋄ *) ⋄ *$ .

Then, we order placeholder equations such as $* ⋄ (* ⋄ *) ≃ (* ⋄ *) ⋄ *$ , where both sides are given placeholder variables:

(i) Equations of lower total order come before equations of higher total order.
(ii) Equations $w ≃ 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.

For instance, $* ⋄ * ≃ * ⋄ (* ⋄ *)$ is less than $* ⋄ * ≃ (* ⋄ *) ⋄ *$ .

Finally, we order (and reduce) equations of the form $w ≃ w^{'}$ as follows. Define the shape of an equation to be the equation in which all variables are replaced by placeholders $*$ .

(i) Equations of lower shape will be of lower order. For instance, any equation of shape $* ⋄ * ≃ * ⋄ (* ⋄ *)$ is less than any equation $* ⋄ * ≃ (* ⋄ *) ⋄ *$ .
(ii) Among equations of equations of equal shape, equations whose variables are first in the lexicographical ordering will be lower. For instance, $0 * 0 ≃ 0 ⋄ (0 ⋄ 0)$ is less than $0 * 0 ≃ 1 ⋄ (1 ⋄ 1)$ , which is in turn less than $0 * 1 ≃ 0 ⋄ (0 ⋄ 0)$ .
(iii) Only the arrangement 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 ⋄ 2 ≃ 1$ because it can be replaced by $0 ≃ 0 ⋄ 1$ , which is earlier in the ordering.
(iv) Any trivial equation $w ≃ w$ , other than the order zero law $0 ≃ 0$ , is discarded.

1.0.1 Alternate formula

For integers $0 \leq a \leq b$ let $E(a,b)$ be the number of magma equations $t_{1} = t_{2}$ with $t_{1}$ of order $a$ , $t_{2}$ of order $b$ , counting up to relabelling, up to switching terms, and only allowing the equation $x = x$ of the form $t = t$ . Then one has

$E (0, 0) = 2$ .
If $a \neq b$ :

$E (a, b) = \frac{1}{2} T (a) (T (a) - 1) \cdot \sum_{\begin{matrix} 1 \leq p \leq a + 1 \\ 1 \leq q \leq b + 1 \\ 0 \leq s \leq min (p, q) \end{matrix}} {\binom{a + 1}{p}} {\binom{b + 1}{q}} (\binom{p}{s}) (\binom{q}{s}) s! .$
If $a = b > 0$ :

$Unknown environment 'bgroup'$

Here the Stirling numbers ${\binom{n}{m}}$ of the second kind count the number of ways to partition a set of $n$ elements into $m$ non-empty subsets,

T (n) \coloneq \frac{1}{n + 1} \cdot (\binom{2 n}{n})

counts the number of plane binary trees of order $n$ , and.

I d e m (n) = \sum_{0 \leq k \leq ⌊ n / 2 ⌋} (\binom{n}{2 k}) (2 k - 1)!!

counts the number of idempotent bijections on $n$ elements.

The number of magma equations of order $n$ (under the given constraints) is then equal to

\sum_{0 \leq a \leq ⌊ n / 2 ⌋} E (a, n - a) .

For further details, as well as Maple calculations for $E (a, b)$ , see this folder.