10 Some abstract nonsense
This is an alternate presentation of the material of the previous section, where we use the “abstract nonsense” of free magmas in the presence of a theory as the conceptual foundation.
Let \(\Gamma \) be a theory with an alphabet \(X\). A free magma with alphabet \(X\) subject to the theory \(\Gamma \) is a magma \(M_{X,\Gamma }\) together with a function \(\iota _{X,\Gamma } : X \to M_{X,\Gamma }\), with the following properties:
\(M_{X,\Gamma }\) obeys the theory \(\Gamma \): \(M_{X,\Gamma } \models \Gamma \).
For any magma \(M\) obeying the theory \(\Gamma \) and any function \(f: X \to M\), there exists a unique magma homomorphism \(\tilde{f}: M_{X,\Gamma } \to M\) such that \(\tilde{f} \circ \iota _{X,\Gamma } = f\).
Such magmas exist and are unique up to a suitable isomorphism:
Let \(\Gamma \) be a theory with alphabet \(X\).
There exists a free magma \(M_{X,\Gamma }\) with alphabet \(X\) subject to the theory \(\Gamma \).
If \(M_{X,\Gamma }\) and \(M'_{X,\Gamma }\) are two free magmas with alphabet \(X\) subject to the theory \(\Gamma \), then there exists a unique magma isomorphism \(\phi : M_{X,\Gamma } \to M'_{X,\Gamma }\) such that \(\phi \circ \iota _{X,\Gamma } = \iota '_{X,\Gamma }\).
We remark that the ordinary free magma \(M_X\) corresponds to the case when \(\Gamma \) is the empty theory.
For (i), we define \(M_{X,\Gamma } = M_X / \sim \), where the equivalence relation \(\sim \) is defined by requiring \(w \sim w'\) if and only if \(\Gamma \models w \simeq w'\); this is an equivalence relation thanks to Lemma 1.11, and from Theorem 1.8 we see that this relation respects the magma operations, so that \(M_{X,\Gamma }\) is a magma. The map \(\iota _{X,\Gamma }: X \to M_{X,\Gamma }\) is defined by setting \(\iota _{X,\Gamma }(x)\) to be the equivalence class of \(x\) in \(M_{X,\Gamma }\) for each \(x \in X\).
We first check that \(M_{X,\Gamma }\) obeys \(\Gamma \). Let \(w \simeq w'\) be a law in \(\Gamma \), and let \(f: X \to M_{X,\Gamma }\) be a function. We may lift this function to a function \(\tilde{f}: X \to M_X\). From Definition 1.7, we have \(\Gamma \vdash w \simeq w'\) and hence \(\Gamma \vdash \varphi _{\tilde{f}}(w) \simeq \varphi _{\tilde{f}}(w')\). By Theorem 1.8, we conclude \(\Gamma \models \varphi _{\tilde{f}}(w) \simeq \varphi _{\tilde{f}}(w')\). Quotienting by \(\sim \), we conclude that \(\varphi _f(w) = \varphi (w')\), giving the claim by Definition 1.6.
Now we check the universal property (ii). Let \(M\) be a magma obeying the theory \(\Gamma \), and let \(f: X \to M\) be a function, then we have a magma homomorphism \(\varphi _f: M_X \to M\). If \(w, w' \in M_X\) are such that \(w \sim w'\), then \(\Gamma \models w \simeq w'\) and hence \(\varphi _f(w) = \varphi _f(w')\). Hence \(\varphi _f\) descends to a map \(\tilde{f}: M_{X,\Gamma } \to M\), which one can check to be a magma homomorphism with \(\tilde{f} \circ \iota _{X,\Gamma } = f\). By construction, \(M_{X,\Gamma }\) is generated by \(\iota _{X,\Gamma }(X)\), and so this homomorphism is unique.
Let \(\Gamma \) consist solely of the associative law, Definition 2.33 (so \(X\) contains \(0,1,2\)). Then one can take \(M_{X,\Gamma }\) to be the set of nonempty strings with alphabet \(X\), with magma operation given by concatenation, and \(\iota _{X,\Gamma }(x)\) being the length one string \(x\). It is a routine matter to verify that this obeys the axioms of a free magma subject to \(\Gamma \).
Let \(\Gamma \) consist of the associative law (Definition 2.33) and the commutative law (Definition 2.18). Then one can take \(M_{X,\Gamma }\) to be the free abelian monoid \(\mathbb {N}_0^X \backslash 0\) of tuples \((n_x)_{x \in X}\) with the \(n_x\) natural numbers, not all zero, with all but finitely many of the \(n_x\) vanishing, with the magma operation given by vector addition, and with \(\iota _{X,\Gamma }(x)\) being the standard generator of \(\mathbb {N}^X\) associated to \(x \in X\); one can think of this space as the space of formal non-empty commuting associating sums of \(X\). It is a routine matter to verify that this obeys the axioms of a free magma subject to \(\Gamma \).
Let \(\Gamma \) consist of the left absorptive law (Definition 2.4). Then one can take \(M_{X,\Gamma }\) to be \(X\) with the law \(x \diamond y = x\), and \(\iota _{X,\Gamma }\) to be the identity map. It is easy to see that this is indeed a free magma subject to \(\Gamma \).
Let \(\Gamma \) consist of the constant law (Definition 2.20). Then one can take \(M_{X,\Gamma }\) to be the disjoint union \(X \uplus \{ 0\} \) of \(X\) and another object \(0\), with \(\iota _{X,\Gamma }\) being the identity embedding, and with the zero magma law \(x \diamond y = 0\) for all \(x,y \in X \uplus \{ 0\} \).
Free magmas can be used to characterize entailment by \(\Gamma \) in terms of a canonical invariant.
Let \(\Gamma \) be a theory with some alphabet \(X\), and let \(M_{X,\Gamma }\) be a free magma with alphabet \(X\) subject to \(\Gamma \), with associated map \(\iota _{X,\Gamma }: X \to M_{X,\Gamma }\). Then for any \(w,w' \in M_X\), we have
By Theorem 10.2 we may take \(M_{X,\Gamma }\) to be the canonical free magma constructed in the proof of that theorem. The claim is then clear from expanding out definitions.
Every theory \(\Gamma \) then gives a metatheorem about anti-implication:
Let \(\Gamma \) be a theory with some alphabet \(X\), and let \(M_{X,\Gamma }\) be a free magma with alphabet \(X\) subject to \(\Gamma \), with associated map \(\iota _{X,\Gamma }: X \to M_{X,\Gamma }\). Let \(w \simeq w'\) and \(w'' \simeq w'''\) be laws with alphabet \(X\). If one has
but
then the law \(w \simeq w'\) cannot imply the law \(w'' \simeq w'''\).
By Theorem 10.3, the hypothesis \(\iota _{X,\Gamma }(w) = \iota _{X,\Gamma }(w')\) is equivalent to \(\Gamma \models w \simeq w'\), and the hypothesis \(\iota _{X,\Gamma }(w'') \neq \iota _{X,\Gamma }(w''')\) is equivalent to \(\Gamma \not\models w'' \simeq w'''\). The claim follows.
Let \(\Gamma \) be the associative and commutative law, so that we can take \(M_{X,\Gamma } = \mathbb {N}_0^X \backslash 0\) as in Example 4. One can then check that for any word \(w \in M_X\), that \(\varphi _{\iota _{X,\Gamma }}(w)\) is the tuple that assigns to each letter \(x\) of the alphabet, the number of times \(x\) appears in \(w\). We conclude that if \(w,w'\) have the same number of occurrences of each letter of the alphabet, but \(w'', w'''\) do not, then \(w \simeq w'\) cannot imply \(w'' \simeq w'''\). This recovers Theorem 4.8.
Let \(\Gamma \) consist of the left absorption law, so we can take \(M_{X,\Gamma } = X\) as in Example 5. Then \(\varphi _{\iota _{X,\Gamma }}(w)\) is the first letter of \(w\). We conclude that if \(w,w'\) have the same first letter, but \(w'', w'''\) do not, then \(w \simeq w'\) cannot imply \(w'' \simeq w'''\).
Let \(\Gamma \) consist of the constant law, so we can take \(M_{X,\Gamma } = X \uplus \{ 0\} \) as in Example 6. Then \(\varphi _{\iota _{X,\Gamma }}(w)\) is \(x\) if \(w\) is just a letter \(x\) of the alphabet, and \(0\) otherwise. We conclude that if \(w,w', w'''\) have order at least one, but \(w''\) has order zero, then \(w \simeq w'\) cannot imply \(w'' \simeq w'''\); this is basically Theorem 4.7.
Let \(\Gamma \) be the theory consisting of the commutative and associative laws, and an additional law \(x^n \simeq y^n\) for a fixed \(n\), where \(x^n\) denotes the magma operation applied to \(n\) copies of \(x\) (the order is irrelevant thanks to associativity), then one can check (for finite \(X\)) that the free magma \(M_{X,\Gamma }\) can be taken to be \((\mathbb {Z}/n\mathbb {Z})^X\) with the addition operation, and \(\iota _{X,\Gamma }(x)\) being the standard generator associated to \(x\). Then for any word \(w\), \(\varphi _{\iota _{X,\Gamma }}(w)\) corresponds to a tuple that assigns to each letter \(x\) of the alphabet, the number of times \(x\) occurs in \(w\) modulo \(n\). We conclude that if \(w,w'\) have the same number of occurrences modulo \(n\) of each letter of the alphabet, but \(w'', w'''\) do not, then \(w \simeq w'\) cannot imply \(w'' \simeq w'''\). This is a stronger version of Theorem 4.8.
10.1 Confluent theories
One promising source of theories \(\Gamma \) for which the free magma \(M_{X,\Gamma }\) can be understood are the confluent theories.
Let \(\Gamma \) be a theory. A word \(w\) can be reduced to another \(w'\) if one can get from \(w\) to \(w'\) by a series of substitutions of laws in \(\Gamma \), where no substitution increases the length of the word this is a working definition, might not be the best one to keep.. A theory \(\Gamma \) is confluent if whenever a word \(w\) can be reduced to both \(w'\) and \(w''\), then both \(w'\) and \(w''\) can be reduced further to a common reduction \(\tilde w\). As such, each word \(w \in M_X\) should have a unique simplification to a reduced word \(w_\Gamma \) in some normal form, for instance the shortest reduction that is minimal with respect to some suitable ordering such as lexicographical ordering.
The associative law, Definition 2.33, appears to be confluent check this.
The theory consisting of both the associative and commutative laws, Definition 2.33, Definition 2.18, appears to be confluent check this.
The idempotent law, Definition 2.3, appears to be confluent check this.
The significance of confluent theories lies in
Let \(\Gamma \) be a confluent theory. Then the free magma \(M_{X,\Gamma }\) subject to this theory can be described as the space of reduced words in \(M_X\) in normal form, where the operation \(w \diamond _\Gamma w'\) on this magma is defined as the normal form reduction of \(w \diamond w'\), and \(\iota _{X,\Gamma }\) is the identity embedding (note that every single-letter word is already in normal form).
Should just be a matter of expanding definitions properly.
Let \(\Gamma \) be a confluent theory. Then a law \(w \simeq w'\) is a consequence of \(\Gamma \) if and only if \(w,w'\) have the same normal form reduction. In particular, a law with this property cannot imply a law without this property.
Follows from Corollary 10.4.
It is thus of interest to locate some confluent laws. Here is a non-trivial example:
Definition 2.25 is confluent.
See the notes here. A sketch of proof is as follows.
We induct on the length of the term. As before we consider terms of the form \(XY\). Also, in both sequences if a simplification is applied to the whole term, then we can assume the sequence is simply final.
By Lemma 10.9, if any of the two sequences is final, then right before the last step, the two factors of the outermost product are both simple. This is also true for the result of the non-final sequence. By the induction hypothesis, they can be identified correspondingly, so the two sequences are either both final or both non-final, and in the first case, the same simplification is applied to give the same result.
If \(Z\) and \(W\) are simple, then \(Z(W\cdots (WW))\) is simple.
Assume the contrary. Then we have 2 cases.
Case 1: \(W\cdots (WW)\) matches the pattern \(y(x(y\cdots (yy)))\), with \(k\) occurrences of \(W\) (\(k \le n\)). Since \(|x(y\cdots (yy))| {\gt} n|y|\), but \(|\cdots (WW)| \le (n-1)|W|\), this is impossible.
Case 2: \(Z(W\cdots (WW))\) matches the pattern \(y(x(y\cdots (yy)))\). Since \(n \ge 3\), we have \(Z = y = W\), so \(|W\cdots (WW)| = n|W| = n|Z|\), contradicting \(|x(y\cdots (yy))| {\gt} n|y|\).