# Counterexamples of algebraic theories

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