What is the carrier set functor?

Question

In https://www.mimuw.edu.pl/~tarlecki/teaching/ct/slides/fnats.pdf , page 5, the carrier set functor is defined thus:

Carrier set functors: |_| : $Alg(Σ) → Set^S$, for any algebraic signature $Σ = \thinspace \langle \thinspace S, Ω \thinspace \rangle$, yielding the algebra carriers and homomorphisms as functions between them.

Here the author of the slides is defining "algebraic signature" as follows (I presume he is using the definition in p.18 of his book here: https://www.mimuw.edu.pl/~tarlecki/teaching/ct/papers/chap1.pdf):

$\textbf{Definition 1.2.1 (Many-sorted signature)}$. A (many-sorted) signature is a pair $Σ = \langle S,Ω \rangle$, where:

• $S$ is a set (of sort names); and

• $Ω$ is an $S* × S$-sorted set (of operation names)

where $S^∗$ is the set of finite (including empty) sequences of elements of $S$. We will sometimes write $sorts(Σ)$ for $S$ and $ops(Σ)$ for $Ω$. $\textit{Many-sorted signatures will be referred to as algebraic signatures}$ $\textit{when it is necessary to distinguish them from other kinds of signatures}$ $\textit{to be introduced later.}$

Three questions:

(1) What does |_| mean?

(2) I don't intuitively understand the definition of a many-sorted signature he is using? Could anyone help explain it. Is this a non-standard definition of the signature of an algebra? (I thought the signature of an algebra was a list of the arities of the operations of the algebra)

(3) Is $Set^S$ the category of functions from some (arbitrary?) set $S, \textit{considered as a category in its own right}$, to the category of sets?

Could anyone give an example that illustrates how this functor works?

Answer 1

Most descriptions of universal algebra or algebraic structures occur in a single-sorted context. This description is in a multi-sorted context. $S$ is the set of sorts. In the single-sorted case, all operations are of the form $f : X^n \to X$ where $X$ is the single sort, so all you need to record for each operation is $n$. In the multi-sorted case, you can have operations like $f : X\times Y\times Z\times X \to Y$, where $X,Y,Z \in S$, so for each operation you now need to record a list of input sorts, $[X,Y,Z,X]$, and the output sort, $Y$. For example, if we want to talk about the algebraic theory of modules over commutative rings, we have a 2-sorted signature, i.e. $S=\{R,M\}$, and operations like $+_R : R\times R \to R$, $+_M : M \times M \to M$, $\cdot : R\times M \to M$ and others.

When we consider the algebras for these signatures, we now need a set for each sort and a function for each operation. In the above example, we need a commutative ring for $R$ and a module over that ring for $M$. This $S$-indexed family of sets can be represented by a functor $DS \to \mathbf{Set}$ where $D : \mathbf{Set}\to\mathbf{Cat}$ is the discrete category functor that takes a set to a category whose class of objects is that set and otherwise only has identity arrows. This is basically the same thing as a function $S \to \mathsf{Ob}(\mathbf{Set})$. The algebra also implies that the functions are homomorphic, but that is what $|\_|$ forgets.

Answer 2

Definition 1. For $S$ a set, a $S$-sorted set is the data of a set $X$ together with a map $\sigma: X \to S$.

It seems like a weird way to talk just about map. But you have to think of $X$ as a big bag of elements, and of $\sigma(x)$ as a "label/color" for the element $x$ that tells you what kind of element is $x$.

A very dumb example: the set $\mathbb N$ is naturally $\{e,o\}$-sorted by defining $\sigma(n) = e$ whenever $n$ is even and $\sigma(n) = o$ whenever $n$ is odd.

Another one: if $G$ is a graph with set of vertices $V$, for which each vertex is colored in blue, red of green, then $V$ is naturally $\{r,b,g\}$-sorted by defining $\sigma(v) = r$ if $v$ is colored red, $\sigma(v) = b$ if $v$ is colored blue and $\sigma(v)=g$ if $v$ is colored green.

A last one: in a multi-edge directed graph the set $E$ of edges is $V\times V$-sorted (every edge can be labeled by its source and target).

Fact. A $S$-sorted set $X$ is exactly the same as an $S$-indexed family of sets $(X_s)_{s\in S}$.

(From $\sigma: X \to S$, we get the family $(\sigma^{-1}(s))_{s\in S}$; and from $(X_s)_{s\in S}$ we can craft $X = \coprod_{s\in S} X_s$ and $\sigma: X \to S$ by mapping $\sigma(x)$ to $s$ when $x$ is in the part $X_s$.)

Notation. For a $S$-sorted set $X$ with map $\sigma: X \to S$, I will denote $X_s = \sigma^{-1}(s)$ for simplicity.

Last, for a fixed $S$, there is a category of $S$-sorted sets where the maps from $(X,\sigma)$ to $(Y,\tau)$ are the maps $\varphi:X\to Y$ such that $\tau \varphi = \sigma$. I let you convince yourself that, under the identification with $S$-indexed families, those maps are just the families of maps $(\varphi_s: X_s\to Y_s)_{s\in S}$. Now stare at those definitions for several minutes and you should see that this category is just $\mathrm{Set}^S$.

---

Let's continue with signatures (this is basically the same definition as in your post). Fix some set $S$. We will call the elements the sorts. They are some kind of labels/colors for elements to come.

Definition 2. A $S$-sorted signature is the data of a set $\mathcal O$, whose elements are called operations, together with a map $a: \mathcal O \to S^\ast \times S$ called the arity map.

Hence a signature is just a bunch of operations, for each of which you know the type of its inputs and ouput: if $f\in \mathcal O$ and $a(f) = (s_1\dots s_n, s)$, you can think of $f$ as an operation that takes arguments labelled $s_1,\dots,s_n$ and gives back an element labelled $s$.

An example $\Sigma_{\rm vect}$: $S=\{\kappa,\nu\}$ has two sorts and $\mathcal O = \{z_v,i_v,a_v,m_s,a_s,i_s,z_s,e_s,m\}$ with $a(z_v) =(,\nu)$, $a(i_v) = (\nu,\nu)$, $a(a_v)=(\nu\nu,\nu)$, $a(z_s) =(,\kappa)$, $a(e_s) =(,\kappa)$, $a(i_s) = (\kappa,\kappa)$, $a(a_s)=(\kappa\kappa,\kappa)$, $a(m_s)=(\kappa\kappa,\kappa)$, $a(m)=(\kappa\nu,\nu)$. This is a good signature to talk about vector spaces: there is two sorts, $\kappa$ for the scalars, and $\nu$ for the vectors; $z_v,i_v,a_v$ stands for the zero, inverse and addition of vectors; $z_s,e_s,i_s,a_s,m_s$ stands for the zero, neutral, inverse, adddition and multiplication of the field of scalars; and $m$ represents the multiplication of vectors by scalars.

Of course, for now I say "operations" and "arguments" and "arity" etc., but this is just vocabulary to give some intuition. In order to make those words concrete, we have to define algebras.

Definition 3. Given a $S$-signature $\Sigma$, a $\Sigma$-algebra $\mathcal A$ is an $S$-sorted set $A$ together with a map $f^{\mathcal A}: A_{s_1}\times\dots\times A_{s_n} \to A_s$ for each $f\in \mathcal O$ such that $a(f) = (s_1\dots s_n,s)$

(I use the term "algebra" to match your document, but this is usually called a $\Sigma$-structure and the word algebra is usually reserved to the structures that satify the axioms of a theory.)

Following our previous example, a $\Sigma_{\rm vect}$-algebra is the data of two sets $A_\kappa$ and $A_\nu$ with operations $z_v:1 \to A_\nu$, $i_v:A_\nu\to A_\nu$, $a_v:A_\nu\times A_\nu \to A_\nu$, $m_s: A_\kappa\times A_\kappa \to A_\kappa$, $a_s: A_\kappa\times A_\kappa \to A_\kappa$, $i_s: A_\kappa\to A_\kappa$, $z_s:1\to A_\kappa$, $e_s:1\to A_\kappa$, $m: A_\kappa\times A_\nu \to A_\nu$. This is all the structure you need to make $A_\nu$ a vector space over $A_\kappa$. (Of course you would also need to add some axioms to make $A_\kappa$ a field, and $A_\nu$ an abelian group and finally $A_\nu$ a vector space over $A_\kappa$. But you have the structure, the rest is properties.)

Definition 3'. A homomorphism $\mathcal A\to \mathcal B$ of algebra is a family of maps $\varphi_s: A_s \to B_s$ such that: for all $f\in \mathcal O$ such that $a(f) = (s_1\dots s_n,s)$, $$ \varphi_s(f^{\mathcal A}(x_1,\dots,x_n)) = f^{\mathcal B}(\varphi_{s_1}(x_1),\dots,\varphi_{s_n}(x_n)) $$

I won't go into detail but for our example, you retrieve the notion of homomorphism between vector spaces (over different fields).

---

Now let us go to the categorical stuff: there is a category $\operatorname{Alg}(\Sigma)$ whose objects are algebras and arrows are the homomorphisms of algebras as just defined. We can craft a functor as follow: $$ \operatorname{Alg}(\Sigma) \to \mathrm{Set}^S,\, \mathcal A \mapsto A $$ The functor is trivial on the arrows, because a homomorphism of algebra is already defined as a $S$-indexed family of maps.