Basic theory of magmas
DefinitionMagma#
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.
Used by 54
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 (All sequences start from \(n=0\) unless otherwise specified.)
(OEIS A002489). Up to isomorphism, the number of finite magmas of cardinality \(n\) up to isomorphism is the slightly slower growing sequence
(OEIS A001329). As there are \(n!\) ways to rearrange the elements of a set of cardinality \(n\), the number of non-isomorphic magmas on a set of cardinality \(n\) is at least \(n^{n^2}/n!\); as it turns out, most magmas are idemprimal (which implies in particular that there are no non-trivial isomorphisms), so the number of non-isomorphic magmas is fairly close to this lower bound.
DefinitionFree 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 \(\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\).
Uses 1
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.
LemmaLemma: For a finite alphabet \(X\), the number of…#
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\).
Proof
Follows from standard properties of Catalan numbers.
Lean
Formalized as FreeMagma.elementsOfNumNodesEq_card_eq_catalan_mul_pow.
Sources
The first few Catalan numbers are
(OEIS A000108).
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.
DefinitionLaw#
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'\).
Used by 2
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 (2) as the equation associated to the law (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 (2) as “the commutative law” (rather than “the commutative equation”).
DefinitionModels#
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\) satisfies \(\Gamma\). Given a law \(E\), we write \(\Gamma \models E\) if every magma \(G\) that models \(\Gamma\), also models \(E\).
Uses 1 · Used by 8
DefinitionDerivation#
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\).
Uses 1 · Used by 1
This definition is useful because of the following theorem:
TheoremBirkhoff's completeness theorem#
For any theory \(\Gamma\) and words \(w, w'\) over a fixed alphabet
Proof
(Sketch) The ‘only if’ component is soundness, and follows from verifying that the rules of inference in Derivation 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.
Lean
Formalized as Completeness.
Sources
Uses 2 · Used by 1
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 (1). By the above lemma, relabeling does not affect whether a given magma satisfies a given law.
Define the total order of a law \(w \simeq w'\) to be the sum of the orders of \(w\) and \(w'\).
The first few Bell numbers are
(OEIS A000110).
The sequence in Counting laws up to relabeling is
(OEIS A289679).
Now we would also like to count laws up to relabeling and symmetry.
The sequence \(D_n\) is
(OEIS A103293), and the sequence in Counting laws up to relabeling and symmetry 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.
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 with placeholder variables \(\ast\) (such as \(\ast \diamond (\ast \diamond \ast)\)):
- (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.
For instance, \(\ast \diamond \ast\) is less than \(\ast \diamond (\ast \diamond \ast)\), which is less than \((\ast \diamond \ast) \diamond \ast\).
Then, we order placeholder equations such as \(\ast \diamond (\ast \diamond \ast) \simeq (\ast \diamond \ast) \diamond \ast\), where both sides are given placeholder variables:
- (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.
For instance, \(\ast \diamond \ast \simeq \ast \diamond (\ast \diamond \ast)\) is less than \(\ast \diamond \ast \simeq (\ast \diamond \ast) \diamond \ast\).
Finally, we order (and reduce) equations of the form \(w \simeq w'\) as follows. Define the shape of an equation to be the equation in which all variables are replaced by placeholders \(\ast\).
- (i) Equations of lower shape will be of lower order. For instance, any equation of shape \(\ast \diamond \ast \simeq \ast \diamond (\ast \diamond \ast)\) is less than any equation \(\ast \diamond \ast \simeq (\ast \diamond \ast) \diamond \ast\).
- (ii) Among equations of equal shape, equations whose variables are first in the lexicographical ordering will be lower. For instance, \(0 \diamond 0 \simeq 0 \diamond (0 \diamond 0)\) is less than \(0 \diamond 0 \simeq 1 \diamond (1 \diamond 1)\), which is in turn less than \(0 \diamond 1 \simeq 0 \diamond (0 \diamond 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 \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.
Loading dependency explorer…
The dependency explorer needs JavaScript and its graph data.