Counterexamples of algebraic theories

2020-01-21

Tags: category theory, algebra

An algebraic theory $T$ is given by a collection of operations with given arities, and a number of equations of the form $\Gamma \mid t = s$ between terms of $T$. Here $t$ and $s$ can contain free variables from $\Gamma$. A model $M$ for an algebraic theory $T$ is an underlying set (call it $M$ as well) which interprets all the operations, and for which all the equations of $T$ hold. A morphism of $T$-models is a function of the underlying sets that presevres the interpretation of all the operations.

The category $Mod_T$ of $T$-models comes with a forgetful functor $U : Mod_T \to Set$. It has a left adjoint $F : Set \to Mod_T$ which constructs a free $T$-model on the underlying set.

The category $Mod_T$ and the functor $U$ always satisfies a number of properties that can be used for showing that certain theories are not algebraic, i.e. that certain categories do not arise as models of algebraic theories.

Conservativity of the forgetful functor

One of the properties of $U$ is that it reflects isomorphisms: if $f : M \to M'$ is a morphism of $T$-models, and $f$ has a set-theoretic inverse $g$ (i.e. $g : M' \to M$ such that $U(f) \circ g = 1$ and $g \circ U(f) = 1$), then $f$ is an isomorphism of models.

This can be easily observed for monoids: let $f$ be a group homomorphism and let $g$ be it's set theoretic inverse. Then $g(ab) = g(f(g(a)) f(g(b))) = g (f (g(a)g(b))) = g(a)g(b)$.

Posets. A discrete two-element poset $X = \{0,1\}$ can be embedded into the poset $Y = \{0, 1\}$ with $0 \leq_Y 1$. Moreover, on a set-theoretic level, this injection is just an identity function and hence is an isomorphism. If the theory of posets were algebraic, then $X$ and $Y$ were isomorphic as posets, which is not the case.

Lattice of submodels

Up to isomorphism, a subobject of a $T$-model $M$ is a $T$-model $M'$ such that $M' \subseteq M$ and the interpretation of all the operations on $M'$ coincides with the interpretations in $M$.

Like in many categories, subobjects for a given model form a lattice. The meet of submodels is just a set-theoretic intersection (can be computed from the pullback of one submodel along the other). However, the join of two submodels may not coincide with the set-theoretic union: if we have two submodels $M_1, M_2$, and a binary operation $f$ in the theory, then the set-theoretic union $M_1 \cup M_2$ will not contain $\bar{f}(x, y)$ for $x \in M_1, y \in M_2$ and $\bar{f}$ the interpretation of $f$ in $M$.

Given a set $X \subseteq M$ we define the closure of $X$ to be the smallest submodel $\bar{X} \subseteq M$ that contains $X$. Explicitly, $$ \bar{X} = \{ \bar{f}(x_1, \dots, x_n) \in M \mid x_1, \dots, x_n \in X, f \in T \} $$ where $\bar{f}$ is a $M$-interpretation of an $n$-ary operation $f$ from $T$. $\bar{X}$ behaves like the closure operation and satisfies all the expected properties.

Using the closure operation we can define the join of two submodels $M_1, M_2 \subseteq M$ as $$M_1 \vee M_2 = \overline{M_1 \cup M_2}$$. This can be generalized to unions over arbitrary families $\bigvee_{i \in \mathcal{I}} M_i$.

Finally, note the following: if $M_i, i \in \mathcal{I}$ is a directed family, then $\bigvee_{i \in \mathcal{I}} M_i = \bigcup_{i \in \mathcal{I}} M_i$. If at some point we add $\bar{f}(a, b)$ to the join, with $a \in M_a, b \in M_b$, then there is some $M_c$ that includes both $M_a$ and $M_b$; this submodel $M_c$ already contains $\bar{f}(a, b)$.

Now we are ready to give another counterexample.

Complete lattices. The theory of complete lattices in not algebraic. Consider the completion $\omega+1$ of $\omega$ with the top element $\infty$. Consider a directed family $D = \{ \{ 0, \dots, n \} \mid n \in \mathbb{N} \}$. The set-theoretic union $\bigcup D$ is just the natural numbers (not a complete lattice), but the join $\bigvee D$ is $\omega+1$.