Birkhoff HSP Through Lawvere Theories

Birkhoff HSP Through Lawvere Theories

An algebra determines more than a collection of operations: it also determines which expressions in those operations are equal. In the language of Lawvere theories, this equational information forms a quotient theory.

Birkhoff's HSP theorem identifies the models of that quotient. Starting with an algebra $A$$A$, we can either impose every identity valid in $A$$A$ and take all models, or construct algebras from $A$$A$ using products, subalgebras, and homomorphic images. Both procedures give the same class.

The mechanism becomes particularly transparent through free models: their elements can be represented as functions obtained by evaluating terms in $A$$A$.

Equations as morphisms

Let $\mathbb{T}$$\mathbb T$ be a finitary Lawvere theory. Its objects are the natural numbers, with $n$$n$ the designated $n$$n$-fold power of $1$$1$. A morphism

$$t:n⟶1$$

is an abstract operation in $n$$n$ variables. Composition expresses substitution, while the product structure supplies projections, repeated variables, and tuples of operations.

A model is a finite-product-preserving functor

$$A:\mathbb{T}⟶\mathbf{Set}.$$

Writing $|A|=A(1)$$|A|=A(1)$, we identify $A(n)$$A(n)$ with $|A{|}^n$$|A|^n$. The operation $t$$t$ becomes a function

$$A(t):|A{|}^n⟶|A|.$$

For parallel morphisms $s,t:n\to 1$$s,t:n\to 1$, the equation $s=t$$s=t$ holds in $A$$A$ precisely when $A(s)=A(t)$$A(s)=A(t)$ as functions: the equality must hold under every assignment of the variables.

We write $\mathrm{Mod}(\mathbb{T})$$\operatorname{Mod}(\mathbb T)$ for the category of models and natural transformations. These natural transformations are exactly the usual algebra homomorphisms.

The theory detected by a model

Fix a model $A$$A$. On each hom-set of $\mathbb{T}$$\mathbb T$, define

$$f{\sim }_{A}g⟺A(f)=A(g).$$

This relation is compatible with composition and finite products, so it defines a quotient Lawvere theory

$$q:\mathbb{T}⟶{\mathbb{T}}_A,{\mathbb{T}}_A=\mathbb{T}/{\sim }_A.$$

The quotient keeps the objects and identifies exactly those parallel operations that $A$$A$ cannot distinguish. Concretely,

$${\mathbb{T}}_A(n,m)\cong \mathrm{im}(\mathbb{T}(n,m)⟶\mathbf{Set}(|A{|}^n,|A{|}^m)).$$

Thus ${\mathbb{T}}_A$$\mathbb T_A$ consists of the term operations of $A$$A$ arising from the original theory. Its construction depends on the specified algebraic structure on $A$$A$.

The original model factors as

$$\mathbb{T}\stackrel{q}{\to }{\mathbb{T}}_A\stackrel{\bar{A}}{\to }\mathbf{Set},$$

where $\bar{A}$$\overline A$ is faithful. The quotient has made every equality visible in $A$$A$ into an equality in the theory itself.

Models of the quotient theory

A model $B:\mathbb{T}\to \mathbf{Set}$$B:\mathbb T\to\mathbf{Set}$ factors through $q$$q$ exactly when

$$A(f)=A(g)⟹B(f)=B(g)$$

for every pair of parallel morphisms.

In other words, $B$$B$ must satisfy every identity satisfied by $A$$A$. Restriction along $q$$q$ therefore gives a fully faithful functor

$$q^{\ast }:\mathrm{Mod}({\mathbb{T}}_A)\hookrightarrow \mathrm{Mod}(\mathbb{T}),$$

whose essential image is precisely that class of models. The morphisms remain the original algebra homomorphisms.

This describes the models logically. Birkhoff's theorem gives a construction of all of them.

The HSP theorem

Here $H$$H$, $S$$S$, and $P$$P$ stand for homomorphic images, subalgebras, and arbitrary set-indexed products. We include the empty product and work up to isomorphism.

For a single algebra $A$$A$, membership in $\mathrm{HSP}(A)$$\operatorname{HSP}(A)$ means that, for some set $I$$I$, there is a subalgebra $C$$C$ of $A^I$$A^I$ and a surjective homomorphism from $C$$C$ onto the given algebra $B$$B$:

$$C\hookrightarrow A^I,C\twoheadrightarrow B.$$

The Lawvere theory formulation of Birkhoff's theorem is

$$\mathrm{Mod}({\mathbb{T}}_A)\simeq \mathrm{HSP}(A),$$

where the right-hand side is the full subcategory of $\mathrm{Mod}(\mathbb{T})$$\operatorname{Mod}(\mathbb T)$ on these algebras.

The easy direction follows from preservation of equations. Equations hold coordinatewise in products, remain true on subalgebras, and descend along surjective homomorphisms. Hence every algebra constructed by HSP satisfies every identity valid in $A$$A$.

The substantive direction is that these constructions produce every such model.

Free models as evaluation functions

Put $\mathbb{S}={\mathbb{T}}_A$$\mathbb S=\mathbb T_A$, and regard $A$$A$ as the faithful $\mathbb{S}$$\mathbb S$-model $\bar{A}$$\overline A$.

For a finite number $n$$n$ of generators, the free $\mathbb{S}$$\mathbb S$-model is the representable functor

$$F_{\mathbb{S}}(n)=\mathbb{S}(n,-).$$

Indeed, Yoneda gives

$${\mathrm{Hom}}_{\mathrm{Mod}(\mathbb{S})}(F_{\mathbb{S}}(n),A)\cong A(n)\cong |A{|}^n.$$

Thus homomorphisms from the free model to $A$$A$ are exactly assignments of its generators.

Taking all of these evaluation homomorphisms together gives

$$F_{\mathbb{S}}(n)⟶A^{|A{|}^n}.$$

On underlying sets, this sends an abstract term to its term function:

$$\begin{array}{rl}\mathbb{S}(n,1)& ⟶|A{|}^{|A{|}^n},\\ t& ⟼(a⟼A(t)(a)).\end{array}$$

This map is injective because $A$$A$ is faithful. It is a homomorphism because each coordinate is an evaluation homomorphism. We have therefore embedded the free model into a power of $A$$A$.

The same construction works for an arbitrary set $X$$X$ of generators:

$$e_X:F_{\mathbb{S}}(X)\hookrightarrow A^{|A{|}^X}.$$

Every term uses only finitely many variables, so distinct elements of the free model are separated by an assignment into $A$$A$. The image is the subalgebra of the function algebra generated by the coordinate functions

$${\pi }_x:|A{|}^X⟶|A|,{\pi }_x(v)=v(x).$$

Now let $B$$B$ be any $\mathbb{S}$$\mathbb S$-model. The free model on its underlying set has a canonical surjective homomorphism

$${\epsilon }_B:F_{\mathbb{S}}(|B|)\twoheadrightarrow B,$$

sending the generator labelled by $b$$b$ to $b$$b$.

Consequently,

$$F_{\mathbb{S}}(|B|)\hookrightarrow A^{|A{|}^{|B|}},F_{\mathbb{S}}(|B|)\twoheadrightarrow B.$$

This is exactly an HSP presentation of $B$$B$. Products collect all evaluations; the embedding realizes the free model as a subalgebra; the quotient imposes the relations defining $B$$B$.

Faithfulness and generation

The quotient map $q$$q$ is an isomorphism precisely when the original model $A:\mathbb{T}\to \mathbf{Set}$$A:\mathbb T\to\mathbf{Set}$ is faithful. Birkhoff's theorem therefore yields

$$A\text{ is faithful}⟺{\mathbb{T}}_A\cong \mathbb{T}\text{ via }q⟺\mathrm{HSP}(A)=\mathrm{Mod}(\mathbb{T}).$$

A faithful model detects every distinction between abstract operations. The theorem turns this ability to distinguish operations into a statement about constructing models: every model is a quotient of a subalgebra of a power of $A$$A$.

This also explains why checking an identity in a faithful model is sufficient. Faithfulness reflects it back to an equality in the theory, and every other model preserves that equality.

Here generation means generation under HSP. It is distinct from being a generator object in the categorical sense.

Modules and annihilators

Let $R$$R$ be an associative unital ring, and let $M$$M$ be a left $R$$R$-module. The Lawvere theory of left $R$$R$-modules is the matrix theory

$${\mathbb{T}}_R(n,m)={\mathrm{Mat}}_{m\times n}(R).$$

Set $I={\mathrm{Ann}}_R(M)$$I=\operatorname{Ann}_R(M)$. Two matrices induce the same function on $M^n$$M^n$ exactly when their corresponding entries differ by elements of $I$$I$: testing vectors with just one nonzero coordinate detects each entry.

Consequently,

$$({\mathbb{T}}_R{)}_M\cong {\mathbb{T}}_{R/I}.$$

Birkhoff's theorem now reads

$$\mathrm{HSP}(M)=\{N\in R\text{-}\mathbf{Mod}:IN=0\}\simeq (R/I)\text{-}\mathbf{Mod}.$$

In particular, an ordinary faithful module generates all left $R$$R$-modules under HSP. The familiar condition ${\mathrm{Ann}}_R(M)=0$$\operatorname{Ann}_R(M)=0$ is exactly the faithfulness of its model functor.

Commutative rings and rational evaluation

For commutative unital rings, including the zero ring,

$${\mathbb{T}}_{\mathrm{CRing}}(n,m)=\mathbb{Z}[x_1,\dots ,x_n{]}^m.$$

Distinct integer polynomials define distinct functions on ${\mathbb{Q}}^n$$\mathbb Q^n$. This follows by induction on the number of variables from the fact that a nonzero univariate polynomial over a field has only finitely many roots.

Thus $\mathbb{Q}$$\mathbb Q$, regarded as a commutative ring, is a faithful model, and

$$\mathrm{HSP}(\mathbb{Q})=\mathbf{CRing}.$$

The construction is explicit. Every commutative ring $B$$B$ is a quotient of a polynomial ring $\mathbb{Z}[X]$$\mathbb Z[X]$, and evaluation gives an embedding

$$\mathbb{Z}[X]\hookrightarrow {\mathbb{Q}}^{{\mathbb{Q}}^X}.$$

Hence

$$\mathbb{Z}[X]\hookrightarrow {\mathbb{Q}}^{{\mathbb{Q}}^X},\mathbb{Z}[X]\twoheadrightarrow B.$$

The quotient step explains how torsion and nilpotents can appear. For example, the subring $\mathbb{Z}\subseteq \mathbb{Q}$$\mathbb Z\subseteq\mathbb Q$ has quotients $\mathbb{Z}/p\mathbb{Z}$$\mathbb Z/p\mathbb Z$, while the embedded polynomial ring $\mathbb{Z}[t]\subseteq {\mathbb{Q}}^{\mathbb{Q}}$$\mathbb Z[t]\subseteq\mathbb Q^{\mathbb Q}$ has the quotient $\mathbb{Z}[t]/(t^2)$$\mathbb Z[t]/(t^2)$.

For each fixed matrix size, the adjugate identities and the Cayley–Hamilton identity are equations in this same theory. Proving them over $\mathbb{Q}$$\mathbb Q$ therefore proves them over every commutative ring.

A class of models

The construction extends to a class $\mathcal{K}$$\mathcal K$ of $\mathbb{T}$$\mathbb T$-models. Define

$$f{\sim }_{\mathcal{K}}g⟺A(f)=A(g)\text{for every }A\in \mathcal{K},$$

and form

$${\mathbb{T}}_{\mathcal{K}}=\mathbb{T}/{\sim }_{\mathcal{K}}.$$

The general theorem is

$$\mathrm{Mod}({\mathbb{T}}_{\mathcal{K}})\simeq \mathrm{HSP}(\mathcal{K}).$$

The evaluation proof now uses products of possibly different models from $\mathcal{K}$$\mathcal K$. Only a set-sized product is needed: for each pair of distinct elements of the relevant free model, choose a model and an evaluation that distinguish them.

The corresponding faithfulness statement is

$$\mathcal{K}\text{ is jointly faithful}⟺\mathrm{HSP}(\mathcal{K})=\mathrm{Mod}(\mathbb{T}).$$

This is the classical finitary, single-sorted HSP theorem expressed through Lawvere theories. The quotient theory records the identities shared by the chosen models, and HSP describes exactly the models those identities permit.

Further reading

• S. Burris and H. P. Sankappanavar, A Course in Universal Algebra, Chapter II, Sections 9–11, for the classical HSP theorem.

• R. B. B. Lucyshyn-Wright, Convex spaces, affine spaces, and commutants for algebraic theories, Sections 1–2, for Lawvere theories, faithful representations, and the matrix theory of modules.