Why Lawvere theories have finite products? and more

Remember to vote up questions/answers you find interesting or helpful (requires 15 reputation points)

According to Wikipedia, a Lawvere theory consists of a small category $L$ with (strictly associative) finite products and a strict identity-on-objects functor $I:\aleph_0^\text{op}\rightarrow L$ preserving finite products.

Why a Lawvere theory have n-products for any n finite? For example, why isn't a Lawvere theory for monoids a category T with four elements: $1$, $T$, $T^2$ and $T^3$, and morphisms $e:1 \to T$ and $*:T^2 \to T$ making the appropiate diagrams commute and such that they are products of each other as expected? ($T^3$ is needed in order to state these diagrams)

Also, why do they usually use the 'free' maps between the desired objects to model and not just the operators that the desired family of algebras has?

-

1
If you only had $1, T, T^2, T^3$, how would you describe a product of four things? – Qiaochu Yuan Jul 12 2011 at 19:05
I think this is the point where I get confused. Why would I need a product of four things? If model for $T$ would be a functor $F$ from $T$ to $Set$, then the product would be $F * : F T^2 \to F T$. For example if $F T = \mathbb{Z}_n$, then $F * : \mathbb{Z}_n^2 \to \mathbb{Z}_n$ would be the product (+) of my monoid (Z_n, +, 0) in Set, wouldn't it? – tryingotounderstand Jul 12 2011 at 19:46
If you want your theory to describe monoids, that is, sets equipped with a multiplication $m(a, b)$ satisfying some axioms, and that theory cannot even describe $m(m(m(a, b), c), d)$, then it is not a very good theory. – Qiaochu Yuan Jul 12 2011 at 20:12
But isn't the monoid described just by the functor that tells what's the set ($F T$), the operation ($F *$) and the neuter ($F e$)? – tryingotounderstand Jul 12 2011 at 20:25
I don't think so. If you want to consider models in categories other than $\text{Set}$, then I think it is possible to find a functor (model) $F$ such that $F(T)^4$ doesn't exist in the target category, and so one can't talk about the map $m(m(m(a, b), c), d)$ in the target category, which would just be silly. – Qiaochu Yuan Jul 12 2011 at 21:56

2 Answers

I think you must have misunderstood how Lawvere theories are supposed to work. Let me try to motivate them from an algebraist point of view, and answer your question in passing.

An algebraic structure such as a group or a ring is usually described in terms of operations and equations they satisfy. But why do we choose certain operations and certain equations? There are many ways of axiomatizing any given algebraic structure. For example, in a ring we could take the unary operation negation $-x$ as basic, or the binary operation subtraction $x - y$ as basic. And why not both? Why is multiplication taken as basic in the theory of groups, rather than division?

Can we describe an algebraic structure in a canonical way, so that no preference is made about which operations and equations count as "basic"? If we are not allowed to prefer any particular choice of operations and axioms, then we must favor them all equally! So, a "canonical" description should include all operations and all equations.

Let us consider the theory of groups to see how this works. We customarily start with three basic operations: a nullary operation (constant) unit $1$, a unary operation inverse ${}^{-1}$, and a binary operation multiplication $\cdot$. There are five axioms:

• $x \cdot (y \cdot z) = (x \cdot y) \cdot z$
• $x \cdot 1 = x$
• $1 \cdot x = x$
• $x \cdot x^{-1} = 1$
• $x^{-1} \cdot x = 1$

To get a canonical theory of groups which does not prefer the above operations and axioms, we should generate all possible operations and equations out of the basic ones, and then take them all as basic. Some generated operations will have names, e.g., division $x/y = x \cdot y^{-1}$, squaring $x^2 = x \cdot x$, etc., but others will not. An example of such an operation might be a ternary operation $p(x_1,x_2,x_3) = ((x_1 \cdot 1) \cdot x_2^{-1}) \cdot (x_3 \cdot x_2)$. In fact, for each $n$ there will be infinitely many $n$-ary operations, represented by expressions built from basic operations and variables $x_1, \ldots, x_n$. As new "axioms" we will simply take all equations that follow logically from the above five axioms. If we now "forget" that we started with the three basic operations and five axioms, we will get a somewhat unusual theory with infinitely many operations and infinitely many axioms, which nevertheless still describes what a group is.

This all sounds very messy. Are we supposed to invent notation for infinitely many operations? And what use is there in having so many axioms that they already are closed under logical deduction? If we truly are algebraists at heart, we must free ourselves of the shackles of syntax.

Let us make a category $\mathcal{T}$ out of the messy description of groups we generated above. Remember that we are not trying to construct the category of groups, but rather a category which nicely organizes the infinitely many operations and equations. The idea is simple enough. The morphisms of $\mathcal{T}$ should correspond to the operations of the theory. The equations should correspond to the fact that certain morphisms are equal.

An $n$-ary operation can be thought of as a map $G^n \to G$ where $G$ is the carrier set of a group and $G^n$ is the $n$-fold product of $G$'s. Thus, for each $n$ there should be an object $\mathtt{G}^n$ in $\mathcal{T}$ and the morphisms $\mathtt{G}^n \to \mathtt{G}^1$ should correspond to the $n$-ary operations. We therefore posit that the objects of $\mathcal{T}$ are $$\mathtt{G}^0, \mathtt{G}^1, \mathtt{G}^2, \ldots$$ where you must not think of $\mathtt{G}^n$ as any kind of set, or an $n$-fold product of anything. We formally write $\mathtt{G}^0, \mathtt{G}^1, \mathtt{G}^2, \ldots$, but we could have as well declared that the objects of $\mathcal{T}$ are the natural numbers and write them simply but confusingly as $0, 1, 2, \ldots$.

The morphisms $\mathtt{G}^n \to \mathtt{G}^1$ are expressions built from $n$ variables $x_1, \ldots, x_n$ and the operations $1$, $\cdot$, and ${}^{-1}$. Two such expressions $p(x_1, \ldots, x_n)$ and $q(x_1, \ldots, x_n)$ are considered to be the same morphism if the theory of groups proves $p(x_1, \ldots, x_n) = q(x_1, \ldots, x_n)$. What about the morphisms $\mathtt{G}^n \to \mathtt{G}^m$? Since we expect that $\mathtt{G}^m$ will in fact end up being the $m$-fold product of $\mathtt{G}^1$'s, a morphism $\mathtt{G}^n \to \mathtt{G}^m$ corresponds uniquely to an $m$-tuple of morphisms $\mathtt{G}^n \to \mathtt{G}^1$. In other words, the morphisms $\mathtt{G}^n \to \mathtt{G}^m$ are $m$-tuples of expressions in variables $x_1, \ldots, x_n$, where again two such $m$-tuples represent the same morphism if the theory of groups proves them equal.

Composition in $\mathcal{T}$ is performed by substitution. For example, the composition of $(x_1^{-1}, x_2 \cdot x_1) : \mathtt{G}^2 \to \mathtt{G}^2$ and $(x_1 \cdot x_1 \cdot x_2) : \mathtt{G}^2 \to \mathtt{G}^1$ is $(x_1^{-1} \cdot x_1^{-1} \cdot (x_2 \cdot x_1) : \mathtt{G}^2 \to \mathtt{G}^1$. The identity morphism from $\mathtt{G}^n \to \mathtt{G}^n$ is the $n$-tuple $(x_1, x_2, \ldots, x_n)$.

You might think that a better $\mathcal{T}$ would contain just three objects $\mathtt{G}^0, \mathtt{G}^1, \mathtt{G}^2$ and morphisms corresponding to the basic operations $1$, ${}^{-1}$ and $\cdot$. But that would not even be a category, and if somehow you managed to make one, you would still have to make sure that $\mathtt{G}^2 = \mathtt{G}^1 \times \mathtt{G}^1$ and that $\mathtt{G}^0$ is the terminal object. It would not really be any prettier.

We can now actually show that $\mathtt{G}^m$ is the $m$-fold product of $\mathtt{G}^{1}$'s. The $k$-th projection $\pi_k : \mathtt{G}^m \to \mathtt{G}^1$ is (represented by) the expression $x_k$. I leave the rest as an exercise. Another exercise is to show that $\mathcal{T}$ has finite products computed as $\mathtt{G}^n \times \mathtt{G}^m = \mathtt{G}^{n + m}$.

We are still doing a lot of syntax disguised as category theory, but that is a necessary step that allows us to see what sort of category $\mathcal{T}$ is. We are ready to define when a category in general is the description of an algebraic theory. I am phrasing the following definition a bit imprecisely without the technical distraction of requiring a "strict identity on objects functor from $\aleph_0^\mathrm{op}$ ...":

Definition [Lawvere]: An algebraic theory is a category with distinct objects $\mathtt{A}^0, \mathtt{A}^1, \mathtt{A}^2, \ldots$ such that $\mathtt{A}^n$ is the $n$-fold product of $\mathtt{A}^1$'s.

It turns out that the models of such a theory/category $\mathcal{T}$ are precisely those functors $F : \mathcal{T} \to \mathsf{Set}$ which preserve finite products. Every such functor is already determined by how it maps $\mathtt{A}^1$ and morphisms $\mathtt{A}^n \to \mathtt{A}^1$, which of course correspond to the $n$-ary operations. In a particular case $F$ might be determined by even fewer pieces of information. For example, if $\mathcal{T}$ is the category which describes the theory of groups, $F$ will be determined already by how it maps the morphisms $1 : \mathtt{G}^0 \to \mathtt{G}^1$, $(x_1 \cdot x_2) : \mathtt{G}^2 \to \mathtt{G}^1$, and $(x_1^{-1}) : \mathtt{G}^1 \to \mathtt{G}^1$, because these generate all other morphisms (except projections and pairings, but $F$ preserves products).

The whole point of the exercise was to arrive at a non-syntactic notion of "algebraic theory". The next step is to look for examples which really are non-syntactic in nature. Here is one: the category whose objects are Euclidean spaces $\mathbb{R}^n$ and the morphisms are smooth maps. This theory describes what is known as smooth algebras.

-
Thank you, very clear. I was misunderstanding it all, not thinking in syntax at all, just thinking about the models. – tryingotounderstand Jul 13 2011 at 6:38
Great answer! I knew nothing about Lewver theories and now I have a very decent grasp at their heuristic motivation! – Qfwfq Jul 13 2011 at 11:19
Andrej, I quote from nLab article on Lawvere theories: "Remark. For T a Lawvere theory, we are to think of the hom-set T(n,1) as the set of n-ary operations defined by the theory. For instance for T the theory of abelian groups, we have T(2,1)={+,−} and T(0,1)={0}." Why is T(2,1) just {+,-},? Wouldn't it include other 'unnamed' operations as well? – tryingotounderstand Jul 13 2011 at 16:31

2
It's a mistake on nLab, if you ask me. – Andrej Bauer Jul 14 2011 at 4:53
I just saw these comments. Ugh. I won't say who pulled that boner, but the nLab article has now been corrected. – Todd Trimble Feb 5 2012 at 17:40

You can accept an answer to one of your own questions by clicking the check mark next to it. This awards 15 reputation points to the person who answered and 2 reputation points to you.

This began as a comment but got too long. I agree with Andrej's answer, but let me add a few remarks. (1) The requirement, in the quoted definition, that the objects `$A^n$` be distinct is, I think, a red herring. Usually they'll be distinct because they won't even be isomorphic, but in those unusual algebraic theories where two of them can be isomorphic, it would do no harm to allow them to be equal. (2) Although Lawvere's definition said that the `$A^n$` should be the only objects in an algebraic theory, this amounts to requiring algebras to be single-sorted. It does no harm to allow multi-sorted theories. So one can take (and I'd be inclined to take) algebraic theories to be just categories with finite products. (Maybe I should say small categories here.) (3) I think one can give a technical foundation to the question about using only a few of the powers of $A$. The fact that, for example, monoids can be defined by means of operations taking at most 2 arguments and equations involving at most 3 variables manifests itself in the category-theoretic approach as follows. Consider the algebraic theory $M$ of monoids and the full subcategory $N$ whose objects are `$A^0,A^1,A^2,A^3$`. Then, if I'm not overlooking something, $M$ is the universal example of an algebraic theory equipped with a functor from $N$ preserving all the finite products that exist in $N$. So the subcategory $N$ suggested in the question suffices to generate, in a fairly natural way, the algebraic theory $M$.

-

1
I think you're right about $N$ and $M$. But tryingtounderstand should be warned that the "official" definition has all $A^n$'s, not just the generating ones, and this is why a Lawvere theory has products. – Andrej Bauer Jul 13 2011 at 5:00
Thanks, after reading Andrej's post, now (3) makes sense. – tryingotounderstand Jul 13 2011 at 6:41

1
Well, that's a minor niggle. Even without the distinctness requirement, given a single-sorted Lawvere theory, there is no ambiguity about what the n-ary operations are, for any n (they're the morphisms from $A^n$ into $A^1$). And if a morphism should happen to encode simultaneously operations of different arities, what of it? We may then think of "operations (with a definite arity)" as not merely identified with morphisms into $A^1$, but rather, as pairs of an arity n and a morphism from $A^n$ into $A^1$, and all is well. – Sridhar Ramesh Jul 13 2011 at 7:58

1
Suppose we have $A^2 = A^3$ and $f : A^2 \to A^1$. Then in the theory we would have a binary operation $(f,2)$ and a ternary operation $(f,3)$. We should also have an equation saying that $(f,2)$ and $(f,3)$ are equal. But such an equation cannot be written down. (In what context, with two or with three variables?) Can we really get away without the equation? I think not, because then the resulting theory will have different models than the category we started with. – Andrej Bauer Jul 13 2011 at 8:09

1
I suppose the real concern is that we do not want functors/models to have to preserve the equality between $A^2$ and $A^3$, only the isomorphism. So, you're right; if what we want to do is faithfully model algebraic theories as given by operations of finite arities and universal equations between them, then we basically want the objects to be (in correspondence with) the finite arities. [That, or, just as well (I think), the objects can be whatever, we'll use anafunctors for models, and no one will ever speak about equality...] – Sridhar Ramesh Jul 13 2011 at 9:59
show 3 more comments
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 146, "mathjax_display_tex": 1, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0}, "config": {"markdown_headings": false, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.18, "absolute_threshold": 10, "end_threshold": 15, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "github"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "english_confidence": 0.9579852819442749, "perplexity_flag": "head"}