Set-theoretic 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 one-element 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

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

  2. 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 set-theoretic 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:

  1. a set has a group structure if and only if it is a set-theoretic model of the algebraic theory of groups;

  2. the one-element group is the smallest possible group (for some precise notion of ‘smallest’); and

  3. 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 set-theoretically.

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.

Posted January 22nd, 2013 in Academic. Tagged: .

3 comments:

  1. Mathias Rav:

    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.

  2. Carlo:

    No, and in fact, every theory is trivially modeled by the one-element set. This implies that the one-element 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 one-element set can be equipped with group structure…)

  3. Mathias Rav:

    Initially, I had taken “model” to mean something about bijections, so I thought that set-theoretic models were unique for each algebraic theory; in that case, the statement “the set is a set-theoretic 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 one-element set.

Leave a response: