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.

Definition 10.1 Free magma relative to a theory

✓

Let $Γ$ be a theory with an alphabet $X$ . A free magma with alphabet $X$ subject to the theory $Γ$ is a magma $M_{X, Γ}$ together with a function $ι_{X, Γ} : X \to M_{X, Γ}$ , with the following properties:

(i): $M_{X, Γ}$ obeys the theory $Γ$ : $M_{X, Γ} ⊨ Γ$ .
(ii): For any magma $M$ obeying the theory $Γ$ and any function $f : X \to M$ , there exists a unique magma homomorphism $\tilde{f} : M_{X, Γ} \to M$ such that $\tilde{f} \circ ι_{X, Γ} = f$ .

Such magmas exist and are unique up to a suitable isomorphism:

Theorem 10.2 Existence and uniqueness of free magmas

✓

Let $Γ$ be a theory with alphabet $X$ .

(i): There exists a free magma $M_{X, Γ}$ with alphabet $X$ subject to the theory $Γ$ .
(ii): If $M_{X, Γ}$ and $M_{X, Γ}^{'}$ are two free magmas with alphabet $X$ subject to the theory $Γ$ , then there exists a unique magma isomorphism $ϕ : M_{X, Γ} \to M_{X, Γ}^{'}$ such that $ϕ \circ ι_{X, Γ} = ι_{X, Γ}^{'}$ .

We remark that the ordinary free magma $M_{X}$ corresponds to the case when $Γ$ is the empty theory.

Proof ▶

For (i), we define $M_{X, Γ} = M_{X} / \sim$ , where the equivalence relation $\sim$ is defined by requiring $w \sim w^{'}$ if and only if $Γ ⊨ w ≃ 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, Γ}$ is a magma. The map $ι_{X, Γ} : X \to M_{X, Γ}$ is defined by setting $ι_{X, Γ} (x)$ to be the equivalence class of $x$ in $M_{X, Γ}$ for each $x \in X$ .

We first check that $M_{X, Γ}$ obeys $Γ$ . Let $w ≃ w^{'}$ be a law in $Γ$ , and let $f : X \to M_{X, Γ}$ be a function. We may lift this function to a function $\tilde{f} : X \to M_{X}$ . From Definition 1.7, we have $Γ ⊢ w ≃ w^{'}$ and hence $Γ ⊢ φ_{\tilde{f}} (w) ≃ φ_{\tilde{f}} (w^{'})$ . By Theorem 1.8, we conclude $Γ ⊨ φ_{\tilde{f}} (w) ≃ φ_{\tilde{f}} (w^{'})$ . Quotienting by $\sim$ , we conclude that $φ_{f} (w) = φ (w^{'})$ , giving the claim by Definition 1.6.

Now we check the universal property (ii). Let $M$ be a magma obeying the theory $Γ$ , and let $f : X \to M$ be a function, then we have a magma homomorphism $φ_{f} : M_{X} \to M$ . If $w, w^{'} \in M_{X}$ are such that $w \sim w^{'}$ , then $Γ ⊨ w ≃ w^{'}$ and hence $φ_{f} (w) = φ_{f} (w^{'})$ . Hence $φ_{f}$ descends to a map $\tilde{f} : M_{X, Γ} \to M$ , which one can check to be a magma homomorphism with $\tilde{f} \circ ι_{X, Γ} = f$ . By construction, $M_{X, Γ}$ is generated by $ι_{X, Γ} (X)$ , and so this homomorphism is unique.

Example 5 Free associative magma

Let $Γ$ consist solely of the associative law, Definition 2.46 (so $X$ contains $0, 1, 2$ ). Then one can take $M_{X, Γ}$ to be the set of nonempty strings with alphabet $X$ , with magma operation given by concatenation, and $ι_{X, Γ} (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 $Γ$ .

Example 6 Free associative commutative magma

Let $Γ$ consist of the associative law (Definition 2.46) and the commutative law (Definition 2.18). Then one can take $M_{X, Γ}$ to be the free abelian monoid $N_{0}^{X} ∖ 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 $ι_{X, Γ} (x)$ being the standard generator of $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 $Γ$ .

Example 7 Free left absorptive magma

Let $Γ$ consist of the left absorptive law (Definition 2.4). Then one can take $M_{X, Γ}$ to be $X$ with the law $x ⋄ y = x$ , and $ι_{X, Γ}$ to be the identity map. It is easy to see that this is indeed a free magma subject to $Γ$ .

Example 8 Free constant magma

Let $Γ$ consist of the constant law (Definition 2.20). Then one can take $M_{X, Γ}$ to be the disjoint union $X ⊎ {0}$ of $X$ and another object $0$ , with $ι_{X, Γ}$ being the identity embedding, and with the zero magma law $x ⋄ y = 0$ for all $x, y \in X ⊎ {0}$ .

Free magmas can be used to characterize entailment by $Γ$ in terms of a canonical invariant.

Theorem 10.3 Canonical invariant

Let $Γ$ be a theory with some alphabet $X$ , and let $M_{X, Γ}$ be a free magma with alphabet $X$ subject to $Γ$ , with associated map $ι_{X, Γ} : X \to M_{X, Γ}$ . Then for any $w, w^{'} \in M_{X}$ , we have

Γ ⊨ w ≃ w^{'} if and only if φ_{ι_{X, Γ}} (w) = φ_{ι_{X, Γ}} (w^{'}) .

Proof ▶

By Theorem 10.2 we may take $M_{X, Γ}$ to be the canonical free magma constructed in the proof of that theorem. The claim is then clear from expanding out definitions.

Every theory $Γ$ then gives a metatheorem about anti-implication:

Corollary 10.4 Criterion for anti-implication

Let $Γ$ be a theory with some alphabet $X$ , and let $M_{X, Γ}$ be a free magma with alphabet $X$ subject to $Γ$ , with associated map $ι_{X, Γ} : X \to M_{X, Γ}$ . Let $w ≃ w^{'}$ and $w^{″} ≃ w^{‴}$ be laws with alphabet $X$ . If one has

φ_{ι_{X, Γ}} (w) = φ_{ι_{X, Γ}} (w^{'})

but

φ_{ι_{X, Γ}} (w^{″}) \neq φ_{ι_{X, Γ}} (w^{‴}),

then the law $w ≃ w^{'}$ cannot imply the law $w^{″} ≃ w^{‴}$ .

Proof ▶

By Theorem 10.3, the hypothesis $ι_{X, Γ} (w) = ι_{X, Γ} (w^{'})$ is equivalent to $Γ ⊨ w ≃ w^{'}$ , and the hypothesis $ι_{X, Γ} (w^{″}) \neq ι_{X, Γ} (w^{‴})$ is equivalent to $Γ ⊭ w^{″} ≃ w^{‴}$ . The claim follows.

Example 9

Let $Γ$ be the associative and commutative law, so that we can take $M_{X, Γ} = N_{0}^{X} ∖ 0$ as in Example 6. One can then check that for any word $w \in M_{X}$ , that $φ_{ι_{X, Γ}} (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 ≃ w^{'}$ cannot imply $w^{″} ≃ w^{‴}$ . This recovers Theorem 4.8.

Example 10

Let $Γ$ consist of the left absorption law, so we can take $M_{X, Γ} = X$ as in Example 7. Then $φ_{ι_{X, Γ}} (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 ≃ w^{'}$ cannot imply $w^{″} ≃ w^{‴}$ .

Example 11

Let $Γ$ consist of the constant law, so we can take $M_{X, Γ} = X ⊎ {0}$ as in Example 8. Then $φ_{ι_{X, Γ}} (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 ≃ w^{'}$ cannot imply $w^{″} ≃ w^{‴}$ ; this is basically Theorem 4.7.

Example 12

Let $Γ$ be the theory consisting of the commutative and associative laws, and an additional law $x^{n} ≃ 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, Γ}$ can be taken to be $(Z / n Z)^{X}$ with the addition operation, and $ι_{X, Γ} (x)$ being the standard generator associated to $x$ . Then for any word $w$ , $φ_{ι_{X, Γ}} (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 ≃ w^{'}$ cannot imply $w^{″} ≃ w^{‴}$ . This is a stronger version of Theorem 4.8.

10.1 Confluent theories

One promising source of theories $Γ$ for which the free magma $M_{X, Γ}$ can be understood are the confluent theories.

Definition 10.5 Confluent theory

Let $Γ$ 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 $Γ$ , where no substitution increases the length of the word this is a working definition, might not be the best one to keep.. A theory $Γ$ 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_{Γ}$ in some normal form, for instance the shortest reduction that is minimal with respect to some suitable ordering such as lexicographical ordering.

Example 13

The associative law, Definition 2.46, appears to be confluent check this.

Example 14

The theory consisting of both the associative and commutative laws, Definition 2.46, Definition 2.18, appears to be confluent check this.

Example 15

The idempotent law, Definition 2.3, appears to be confluent check this.

The significance of confluent theories lies in

Theorem 10.6 Free magma of a confluent theory

Let $Γ$ be a confluent theory. Then the free magma $M_{X, Γ}$ subject to this theory can be described as the space of reduced words in $M_{X}$ in normal form, where the operation $w ⋄_{Γ} w^{'}$ on this magma is defined as the normal form reduction of $w ⋄ w^{'}$ , and $ι_{X, Γ}$ is the identity embedding (note that every single-letter word is already in normal form).

Proof ▶

Corollary 10.7 Criterion for anti-implication

Let $Γ$ be a confluent theory. Then a law $w ≃ w^{'}$ is a consequence of $Γ$ 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.

Proof ▶

It is thus of interest to locate some confluent laws. Here is a non-trivial example:

Theorem 10.8 477 confluent

Definition 2.27 is confluent.

Proof ▶

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 $X Y$ . 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.

Lemma 10.9 477 lemma

If $Z$ and $W$ are simple, then $Z (W \dots (W W))$ is simple.

Proof ▶

Assume the contrary. Then we have 2 cases.

Case 1: $W \dots (W W)$ matches the pattern $y (x (y \dots (y y)))$ , with $k$ occurrences of $W$ ( $k \leq n$ ). Since $| x (y \dots (y y)) | > n | y |$ , but $| \dots (W W) | \leq (n - 1) | W |$ , this is impossible.

Case 2: $Z (W \dots (W W))$ matches the pattern $y (x (y \dots (y y)))$ . Since $n \geq 3$ , we have $Z = y = W$ , so $| W \dots (W W) | = n | W | = n | Z |$ , contradicting $| x (y \dots (y y)) | > n | y |$ . □