0
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ I think it's more a $U$, which is the usual letter for forgetful functors. Here according to the context U would assume that $S$ is a set of sorts or types, and $\Omega$ a set of function symbols, each with prescribed arities, input and output sorts/types. $Set^S$ is the category of functors $S\to Set$ when $S$ is seen as the discrete category with object set $S$, or you can also see it as the category of $S$-indexed families of sets. $\endgroup$ – Max Aug 4 '17 at 9:03
  • $\begingroup$ I would be really delighted if you gave an example. I have edited the question heavily to include the definition of algebraic signature he intends, whose component $\Omega$ I don't understand at all (why the $S^* \times S$?). So is $S$ an initial object of $Set^S$ (given all arrows go from it to objects of $Set$? Is $S$ therefore a category consisting simply of the set $S$? $\endgroup$ – user65526 Aug 4 '17 at 9:18
  • $\begingroup$ Maybe these other slides can shed some lights : mimuw.edu.pl/~tarlecki/teaching/ct/slides/algebras.pdf (especially the slides 6 and 8). $\endgroup$ – Arnaud D. Aug 4 '17 at 9:19
  • $\begingroup$ The discrete category $\mathcal{S}$ of a set of sorts $S$, would be the category whose only morphisms are identity morphisms taking any sort in $Obj_{\mathcal{S}}$ to itself. Suppose the sorts are the sorts of individuals and the sorts of characteristic functions. So the discrete category consist of the two sorts with identity morphisms on them. But then how is the functor $S \rightarrow Set$ acting on this category consisting of individuals and characteristic functions, and identity morphisms. This is what I don't understand. $\endgroup$ – user65526 Aug 4 '17 at 10:25
  • $\begingroup$ Also, where does it say that $S$ in $Set^S$ is a discrete category? $\endgroup$ – user65526 Aug 4 '17 at 10:27
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ I don't really understand your answer yet (but I may do in the future), simply because I cannot connect what you are saying specifically to the definition of $\Omega$ as $S^* \times S$ (which makes no sense to me). Furthermore, I've never really studied rings, so the example is difficult for me to process (a type theoretic example would really help though). I'll try and understand what you wrote again! Thanks :) $\endgroup$ – user65526 Aug 4 '17 at 9:30
  • 1
    $\begingroup$ $\Omega$ isn't $S^*\times S$; it's an $S^*\times S$ sorted set. One way of representing this is as a set a function $O \to S^*\times S$ where $O$ is a set of names of operations. So if $f\in O$ is an operation name, then $\Omega(f) = ([X,Y,Z,X],Y)$ in my second example. $\endgroup$ – Derek Elkins left SE Aug 4 '17 at 9:35
  • $\begingroup$ Ok. So $\Omega$ consists of ordered pairs of operation inputs, and their outputs. So if we have $O:= \{f, g, h \}$ with $f: X \times Y \times Z \times X \rightarrow Y, g: X \times X \times X \times Z \rightarrow Y, h: Y \times Y \times Z \times Y \rightarrow X$, then $\Omega = ([X,Y,Z,X],Y), ([X, X, X, Z], Y), ([Y, Y, Z, Y], X)$, right? But then the definition he offers is odd, since there are no names of operations in this set. $\endgroup$ – user65526 Aug 4 '17 at 9:44
  • $\begingroup$ I now understand the notation. I still don't understand the functor. Is $S$ in $Set^S$ our beloved set of sorts $S$ in the signature, or is it any arbitrary set? $\endgroup$ – user65526 Aug 4 '17 at 9:47
  • $\begingroup$ It's the set of sorts. $\endgroup$ – Derek Elkins left SE Aug 4 '17 at 9:50
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.