Category Theory
Zulip Server
Archive

You're reading the public-facing archive of the Category Theory Zulip server.
To join the server you need an invite. Anybody can get an invite by contacting Matteo Capucci at name dot surname at gmail dot com.
For all things related to this archive refer to the same person.

Stream: learning: questions

Topic: Algebraic theories

Jan Pax (Nov 03 2023 at 10:24):

I would like to understand in this book by Rosicky Adamek Vitale: Algebraic Theories_ A categorical introduction to general algebra (2009), on the page 7 what do the morphisms in $\cal T$ correspond to in the sense of universal algebra in the sense of Birkhoff. I understand though that $\mathbb{Set}^{S^*}$ are $S$-sorted sets, but I do not understand it for a more general $\cal T$. What are the objects and morphisms in $\cal T$ send to by finite product preserving functors to $Set$ (and correspond to) ?

Ralph Sarkis (Nov 03 2023 at 11:01):

The name they give to $\mathcal{T}$ is algebraic theory. That name is used in universal algebra to refer to a signature $\Sigma$ coupled with a set of equations between $\Sigma$-terms. So you should think of $\mathcal{T}$ as describing the operations allowed in your algebras as well as their constraints. It can be difficult to see how exactly these are represented in the objects and morphisms of $\mathcal{T}$.

Ralph Sarkis (Nov 03 2023 at 11:01):

Sometimes, people restrict their attention to theories $\mathcal{T}$ which are generated by a single object, meaning the objects of $\mathcal{T}$ are natural numbers and the product is addition. This makes it easier to see because a finite product preserving functor $\mathcal{T} \to \mathbf{Set}$ will send $1$ to some set $A$, and the rest will be completely determined as $n = 1 + \stackrel{n}{\cdots} + 1$ means $n$ is sent to $A \times \stackrel{n}{\cdots} \times A = A^n$.

Now, a morphism $t: n \to m$ in $\mathcal{T}$ will be interpreted as a function $t : A^n \to A^m$, and you should understand this as an $m$ -tuple of terms with $n$ variables. Indeed, $t$ takes a choice of n inputs in A and computes m outputs in A, and by some properties of the product, you can check this done by $m$ unrelated computations (this is not necessarily the case in monoidal theories).

Ralph Sarkis (Nov 03 2023 at 11:01):

When $\mathcal{T}$ is not generated by a single-object it can be more complicated to see. I find it easier to think of theories as signatures with equations, but I am sure this depends on what kind of algebras you are trying to present. There are "classical" theories that are disgusting and yet present some simple things (I remember an example that I cannot find right now).

These notes by Awodey and Bauer are way more gentle than Algebraic Theories.

Ralph Sarkis (Nov 03 2023 at 11:02):

Now, a morphism $t: n \to m$ in the theory $\mathcal{T}$ will be sent to a function $\llbracket t \rrbracket : A^n \to A^m$, and you understand this as an $m$ tuple of terms with $n$ variables. Indeed, $\llbracket t \rrbracket$ takes any assignment of $n$ variables into $A$ (i.e. a function $n\to A$) to $m$ elements of $A$. So it tells you how to compute $m$ different outputs out of $n$ inputs from $A$. Thanks to the properties of products, you can show that these $m$ different computations are unrelated so it is actually $m$ different terms (this is not the case when looking at monoidal theories).

Ralph Sarkis (Nov 03 2023 at 11:02):

There is a missing message that could not compile for some reason, let me try again. OK kinda fixed it. But there is a sentence where I cannot put dollar signs around 'n' for some reason. It should be: $t$ takes a choice of $n$ inputs in $A$ and computes $m$ outputs in $A$
Why this compiles here but not in my earlier message I don't know.

Ralph Sarkis (Nov 03 2023 at 11:21):

Well now my older paragraph has reappeared without my doing anything. This is really confusing...

Jan Pax (Nov 03 2023 at 15:51):

@Ralph Sarkis Yes, I'm aware of what you say, but my questions was exactly about what you claim that can "be more complicated to see". Could you come up with an example of a $\cal T$ that would give to me a feeling what some strange morphism in $\cal T$ could mean in the interpretation of $\cal T$,i.e. a functor $A$ to $\mathbb {Set}$ ? In particular $\cal T$ should not be a single object generated, so try $A$ and $B$ generated and the interpretation of a morphism in question in it should be somehow self-explanatory for my question.

Kenji Maillard (Nov 03 2023 at 16:05):

For an exemple of a simple theory, yet not generated by asingle sort, what about the theory of a ring together with a module ?
It's a theory $\mathcal{T}_{\text{mod}}$ whose models are pairs $(\mathcal{R}, \mathcal{M})$ of a ring $\mathcal{R}$ and an $\mathcal{R}$-module $\mathcal{M}$. In terms of signature, it is generated by two sorts $r$ and $m$, operations $0,1 : \top \to r$, $+,* : (r,r) \to r$, $\rho : (r,m) \to m$ together with the ring and modules equations. I guess an explicit presentation of $\mathcal{T}_{\text{mod}}$ can be worked out using freely generated rings and modules.

Kevin Arlin (Nov 03 2023 at 16:05):

The simplest typical example of a $\mathcal T$ that isn't generated by a single object is the theory of "A monoid and a set it acts on." This is generated under finite products by two objects, call them $M$ and $S.$ As in any finite product category with object generators the only interesting morphisms are those with codomain $M$ and $S.$ There are morphisms $M^k\to M$ comprising a full subcategory of $\mathcal T$ isomorphic to the usual theory of monoids, while there are no morphisms $S^k\to S$ or $M^k\to S$ other than those built from product projections and diagonals. The most interesting part of the theory, then, is the class of morphisms $\mu:M^k\times S\to S$ which, in a model, correspond to the action on an element of $S$ by $k$ elements of the monoid $M.$

Anyway, that's my suggested example. If you feel comfortable with the categorical interpretation of single-sorted algebraic theories I hope this gets across how the multi-sorted variant is not really so different. Now, if $\mathcal T$'s objects weren't freely generated under finite products by any class of objects at all then you'd have something quite unusual-feeling, but that's not a case you're particularly likely to meet in practice.

Kevin Arlin (Nov 03 2023 at 16:06):

Ah, @Kenji Maillard, I see we've given basically the same answer across the abelian/non-abelian divide--just a note that Zulip annoyingly insists on double dollar signs for Latex.

Ralph Sarkis (Nov 03 2023 at 21:17):

Letting $\mathcal{T}$ be the category of non-empty finite sets, you find that $\mathbf{Alg}\mathcal{T}$ is the category of Boolean algebras. Todd nicely explained this in his answer on MO.

Jan Pax (Nov 06 2023 at 19:06):

I have 2 more problems with the notion of algebraic theory. Why the requirement of being finite product complete is exactly the right one for this notion ? Second question is in the snippet below in the example 1.10: why the right morphisms in $S$-sorted sets go contravariantly: $a:k\to n$ ?
Snímek-obrazovky-2023-11-06-195900.png

Ralph Sarkis (Nov 06 2023 at 19:45):

I find it hard to answer your first question intelligently (I am not even convinced of what I am saying).

Functorial semantics (defining algebras as functors) is a very cool idea (thanks Lawvere) and the list of examples in this chapter shows you it encapsulates what lots of people consider to be algebraic. It led to many advances in categorical algebra and categorical logic, so I don't think anyone would say it is not the right notion.

Now, for why it is exactly right, one way I like to think of it is via [[Fox theorem]]. Informally, this theorem says that categories with finite products are preciely the places where you can copy and delete variables without problems. If you think about algebra as manipulating operation symbols and variables on paper (in a 1-dimensional syntax), in particular, copying and deleting variables as it pleases you, then you would expect the categories that embody the syntax for algebra are categories with finite products.

Ralph Sarkis (Nov 06 2023 at 20:11):

For the second question, there many ways to see this, I think unrolling what a product-preserving functor $\mathcal{T}_S \rightarrow \mathbf{Set}$ is and seeing it corresponds to a $S$-sorted set would be the most enlightening. In particular, you need to decompose any morphism in $\mathcal{T}_S$ as a composition of projections and pairings (what are they in $\mathcal{T}_S$) because these you know are preserved by the functor.

Ralph Sarkis (Nov 06 2023 at 20:11):

If you only look at the case $S= \{\ast\}$, hence $\mathcal{T}_S = \mathcal{N}$, you see that a morphism $t: n = \ast_0\cdots \ast_{n-1} \rightarrow \ast_0\cdots\ast_{m-1} = m$ is sent to a function $A^n \to A^m$ that takes $(a_0,\dots, a_{n-1}) \rightarrow (a'_0, \dots, a'_{m-1})$ where each $a'_j$ is equal to some $a_i$. You can see this morphism $t$ as $m$ terms in the empty signature over $n$ variables, so each of the $m$ term is a single variable and $a'_j = a_i$ if the $j$ th term is the $i$ th variable.

John Baez (Nov 06 2023 at 20:25):

Jan Pax said:

I have 2 more problems with the notion of algebraic theory. Why is the requirement of being finite product complete exactly the right one for this notion?

Because otherwise you get a different notion! :upside_down: If you want to use infinite products that's fine, but you get a different concept, sometimes called an infinitary algebraic theory. It can be very useful to restrict to products of order at most some cardinal $\kappa$. If you want to use finite limits that's fine too, but you get yet another notion, sometimes called a finite limits theory or essentially algebraic theory. If you want to use arbitrary limits, or limits of diagrams whose cardinality is at most some cardinal, that's also good. All these different notions are important and well-studied.

Chris Grossack (they/them) (Nov 07 2023 at 06:08):

Jan Pax said:

Why the requirement of being finite product complete is exactly the right one for this notion ?

The operations we require in our categories tell us what the (co)domains of our function symbols are allowed to be. (For now, let's only allow equational axioms).

So for instance, finite product theories have some basic sorts, and then we allow function symbols from the products of those sorts to each other! For instance with groups multiplication is defined on $G \times G$, and for the 2-sorted theory of (ring, module) pairs, the action $R \times M \to M$ is defined on $R \times M$. So the finite product structure is precisely what's used for the domains of our function symbols.

Contrast this with the finite limit theories (read: essentially algebraic theories) which allow partial operations, defined only on "nice" subsets of products of the basic sorts. For instance, in the definition of a category, composition is defined on $\{ (f,g) \mid \text{dom}(f) = \text{cod}(g) \} \subseteq A \times A$ (where $A$ is the set of arrows). Notice we need products and equalizers in order to build this domain, so we're using the full finite limit structure!

This story gets more complicated once we start adding relation symbols, but the basic premise that the operations on our (base) category correspond to allowable operations on our basic sorts remains useful intuition

Jan Pax (Nov 07 2023 at 10:40):

@Ralph Sarkis Is it correct to say that your $(a_0,...,a_{n-1})$ are exactly the standard variables $(x_{\sigma(0)},...,x_{\sigma(n-1)})$ where each $x_i$ appears only once so that $\sigma$ is a permutation ? Otherwise there might occur some ambiguity in defining the morphism $t$. If there were more than 1 variable/term $j$ th which is the more than 1 $i$ th variable then $t$ will not be defined uniquely or correctly or undefined at all ? What is mind-boggling is this sentence: each $a'_j$ is equal to some $a_i$ and there might go something wrong in defining $t$ ? I cannot resolve this.

Ralph Sarkis (Nov 07 2023 at 11:00):

These $a_i$ and $a'_j$ are elements of $A$, so the function defined by $(a_0,\dots, a_{n-1}) \mapsto (a'_0, \dots, a'_{m-1})$ is $\llbracket t \rrbracket$, i.e. the semantics of $t$ for some particular algebra $\mathcal{N} \to \mathbf{Set}$.

Ralph Sarkis (Nov 07 2023 at 11:00):

One way people represent terms is $t : n \to m = \langle t_0,\dots, t_{m-1} \rangle$ where each $t_j$ is a term over $n$ variables (we can call them $x_0, \dots, x_{n-1}$ ). Then the semantics of $t$ takes an element of $(a_0,\dots, a_{n-1}) \in A^n$ to the $m$ -tuple whose $j$ th coordinate is the value of $t_j$ when the variables $x_i$ are assigned value $a_i$.

Ralph Sarkis (Nov 07 2023 at 11:00):

Since terms are over the empty signature, they will be really simple. For instance $\langle x_0, x_0 \rangle : 3 \to 2$ will be interpreted (in some algebra) as the function sending $(a_0,a_1,a_2)$ to $(a_0,a_0)$.

Tom Hirschowitz (Nov 07 2023 at 11:32):

Jan Pax said:

Why the requirement of being finite product complete is exactly the right one for this notion ?

To complement John's answer, my naive intuition is that, compared to finite limit theories, finite product theories have the nice property that reflexive coequalisers of algebras are well-behaved. To take the monad perspective (and restricting to nice categories), you probably know that forgetful functors from $T$-algebras to the base category create limits, but not colimits in general.
The colimits that are created are in fact the ones that $T$ preserves (this is easy to prove).
In particular:

• When $T$ is finitary (which corresponds to finite limit theories, essentially because finite limits commute with filtered colimits), then all filtered colimits are created.
• When $T$ furthermore preserves reflexive coequalisers (which corresponds to finite product theories, essentially because finite products commute with sifted colimits, i.e., filtered colimits + reflexive coequalisers in nice categories), then reflexive coequalisers are also created.