Settheoretic models of algebraic theories: I
(Part 3 of a series.)
We have seen how to present a mathematical structure as an algebraic theory, but have been vague about precisely which structures are denoted by any particular collection of rules.
Last time, we wrote down the group laws as an algebraic theory (with signature \(\mathord{\sf{\text{e}}}\), \({}^{1}\), \(\circ\), and axioms for identity, inverses, and associativity) and said that we had defined groups.
Our signature mentions only one base term, \(\mathord{\sf{\text{e}}}\), so in some sense we have defined only the oneelement group. On the other hand, we could get more mileage out of our theory by using it to describe all groups, in the sense that any group will be compatible with the given signature and axioms—although it may have additional rules (terms and equations) not enforced by the base theory itself.
As a more damning example, consider the natural numbers, which consist of

the zero number \(\mathord{\sf{\text{z}}}\), and

a successor function \(\mathord{\sf{\text{s}}}\) which sends a number to itself plus one.
We might say the natural numbers are an algebraic theory whose signature has an arity zero constant \(\mathord{\sf{\text{z}}}\) and an arity one constant \(\mathord{\sf{\text{s}}}\):
It is easy to see this theory must contain the terms \(\mathord{\sf{\text{s}}}(\mathord{\sf{\text{s}}}(\cdots\mathord{\sf{\text{s}}}(\mathord{\sf{\text{z}}})))\). We add no axioms, because
by reflexivity, and we would like
when \(n\neq m\), since different numbers are always nonequal.
If we allow a group to have elements besides \(\mathord{\sf{\text{e}}}\), then the natural numbers, defined this way, might have elements besides the \(\mathord{\sf{\text{s}}}^n(\mathord{\sf{\text{z}}})\). Worse yet, they might have additional equalities—the axiom \(n\vdash n=\mathord{\sf{\text{z}}}\) is compatible with the theory, and causes all numbers to equal zero!
To better understand these issues, we introduce the notion of a settheoretic model of an algebraic theory. Intuitively, a theory is modeled by a set \(M\) if we can map terms in the theory to elements of \(M\) in such a way that equal terms (in the sense of the theory’s equality) are sent to the same element of \(M\). This will eventually let us make precise ideas like:

a set has a group structure if and only if it is a settheoretic model of the algebraic theory of groups;

the oneelement group is the smallest possible group (for some precise notion of ‘smallest’); and

the natural numbers are exactly the smallest model of the algebraic theory of natural numbers.
Next time, we will examine each rule in a theory—corresponding to signatures, structural rules, and axioms—and mirror each settheoretically.
But the core idea is simple enough: to model a signature in a set \(M\) is to interpret each constant \(c\) of arity \(a\) as a genuine function \([\![ c ]\!]:M^a\to M\), i.e., which takes an \(a\)tuple of elements of \(M\) to a single element. So if a set \(G\) models groups, then it is equipped with, in part, a multiplication function \([\![\circ ]\!]:G\times G\to G\) and an inverse function \([\![{}^{1} ]\!]:G\to G\). In other words, it is a group in the ordinary sense.
Do we require that unequal terms in the algebraic theory must be mapped to different elements of M? I would kind of assume that, based on the “if and only if” part of the first list item – otherwise I can map all terms to the neutral element and claim that any algebraic theory is a group.
January 23rd, 2013 at 4:52 amNo, and in fact, every theory is trivially modeled by the oneelement set. This implies that the oneelement set is a group, since it is a model of the theory of groups. Why do you say it implies any algebraic theory is a group? (And what do you mean by that, exactly? If you mean that any theory can be modeled by a group, this is true in the sense that the oneelement set can be equipped with group structure…)
January 23rd, 2013 at 5:19 pmInitially, I had taken “model” to mean something about bijections, so I thought that settheoretic models were unique for each algebraic theory; in that case, the statement “the set is a settheoretic model of the algebraic theory of groups” becomes equivalent to “the algebraic theory that the set models is the algebraic theory of groups”, which is obviously nonsensical.
The missing piece, for me, was the fact that every theory is modeled by the oneelement set.
January 24th, 2013 at 1:24 pm