Set-sets
Abstract
An introduction to endofunctors on Set. Algebras and coalgebras of endofunctors model basic objects of study in mathematics, computer science, and logic. This post explains how to interpret algebras and coalgebras of endofunctors on Set as sets equipped with operations or “co-operations”. We also briefly explore the connection between coalgebra and topology. This is intended as a primer for an upcoming paper about comonads on Set with Kevin Carlson and David Spivak.
Background assumed: categories, functors, (pre)sheaves, monads, algebraic theories, topological spaces.
1 Algebra vs. coalgebra
Algebra is about operations that take multiple inputs and yield one output. For example, the usual addition operation + takes two inputs (say 3 and 5) and produces one output (say 8).
Dually, coalgebra is about co-operations, which take one input and yield multiple outputs. These multiple outputs are produced in a bunch, possibly without order. For example, in an undirected graph, each edge is assigned an unordered pair of vertices.
To put it another way: in algebra, a unique element is assigned to each operation filled with elements, whereas in coalgebra, a unique co-operation filled with elements is assigned to each element.
Before giving some examples of coalgebraic structures in more detail, first let’s discuss what “(co)operation” means.
2 Encoding (co)operations
Both operations and co-operations are expressions with slots capable of being filled with elements. This will be made precise by the concept of a functor \mathbf{Set} \to \mathbf{Set}. It may not be obvious at first, but such a functor is essentially equivalent to some expressions that can be filled with elements, subject to equations.
This is easiest to illustrate with an example. Suppose we are interested in a binary expression x + y, subject to the equation x + y = y + x.
This determines a functor \mathcal{X} \colon \mathbf{Set} \to \mathbf{Set} as follows. Given any set S, we obtain a set \mathcal{X}(S) of expressions filled with elements of S (modulo equations obtained from the given one by substitution). In this example, \mathcal{X}(S) amounts to unordered pairs of elements in S.
\begin{align*} \mathcal{X}(\emptyset) &= \emptyset \\[.5em] \mathcal{X}(\{x\}) &= \left\{\boxed{x + x}\right\} \\[.5em] \mathcal{X}(\{x, y\}) &= \left\{\boxed{x + x},\, \substack{\boxed{x + y}\\ =\\ \boxed{y + x}},\, \boxed{y + y}\right\} \\[.5em] \mathcal{X}(\{x, y, z\}) &= \left\{\boxed{x + x},\, \substack{\boxed{x + y}\\ =\\ \boxed{y + x}},\, \boxed{y + y},\, \substack{\boxed{y + z}\\ =\\ \boxed{z + y}},\, \boxed{z + z},\, \substack{\boxed{x + z}\\ =\\ \boxed{z + x}}\right\} \end{align*}
Expressions can be re-filled: given any \phi \in \mathcal{X}(S) (an expression filled with elements of S) and a map of sets f \colon S \to T, define \mathcal{X}(f)(\phi) \in \mathcal{X}(T) (an expression filled with elements of T) by relabeling/substitution.
This indeed amounts to a functor \mathcal{X} \colon \mathbf{Set} \to \mathbf{Set}. Formally,
a binary expression x + y, subject to the equation x + y = y + x
translates to a presentation of this functor by generators and relations. That is, \mathcal{X} is the functor \mathbf{Set} \to \mathbf{Set} presented by
a generator \boxed{x + y} \in \mathcal{X}(\{x,y\}) and a relation \boxed{x + y} = \boxed{y + x}
where \boxed{y + x} \in \mathcal{X}(\{x,y\}) denotes the term derived from \boxed{x + y} \in \mathcal{X}(\{x,y\}) by applying the function f sending x \mapsto y, y \mapsto x, that is, \boxed{y + x} \coloneqq \mathcal{X}(f)(\boxed{x + y}).
Just like any other kind of algebraic structure, all functors \mathbf{Set} \to \mathbf{Set} may similarly be presented by generators and relations. (In more jargon, this is the “co-Yoneda lemma”: every \mathbf{Set}-valued functor is a colimit of functors free on one generator.) That means any functor \mathbf{Set} \to \mathbf{Set} may be viewed in this way as some expressions subject to some equations.
A functor \mathbf{C} \to \mathbf{Set} is sometimes called a \mathbf{C}-set for short. From here on, a functor \mathbf{Set} \to \mathbf{Set} will be called a \mathbf{Set}-set for short.
2.1 Example: polynomial functors
Especially simple are expressions subject to no equations, which correspond to freely generated \mathbf{Set}-sets (presented by generators and no relations).
For instance, suppose we are interested in a binary expression x + y, a binary expression x \times y, a binary expression x \div y, and a unary expression -x, together satisfying no equations.
This corresponds to a \mathbf{Set}-set \mathcal{X} \colon \mathbf{Set} \to \mathbf{Set} where, as always, \mathcal{X}(S) is the set of expressions filled with elements of S.
\begin{align*} \mathcal{X}(\emptyset) &= \emptyset \\[.5em] \mathcal{X}(\{x\}) &= \left\{\boxed{x + x},\, \boxed{x \times x},\, \boxed{x \div x},\, \boxed{-x}\right\} \\[.5em] \mathcal{X}(\{x, y\}) &= \left\{\boxed{x + x},\, \boxed{x + y},\, \boxed{y + x},\, \boxed{y + y},\right.\\ & \qquad\left.\boxed{x \times x},\, \boxed{x \times y},\, \boxed{y \times x},\, \boxed{y \times y},\right.\\[.25em] & \qquad\left.\boxed{x \div x},\, \boxed{x \div y},\, \boxed{y \div x},\, \boxed{y \div y},\right.\\ & \qquad\left.\boxed{-x},\, \boxed{-y}\,\right\} \end{align*}
In this example, \mathcal{X} may be described by the formula \mathcal{X}(S) = S^2 + S^2 + S^2 + S^1 = 3S^2 + S. Here S^N is the set of N-tuples of elements of S, that is, the set of functions \mathbf{Set}(N, S), counting the possible ways of filling an N-ary expression with S elements. The functor with formula S^N itself is the \mathbf{Set}-set presented by a single N-ary generator and no relations.
(This is the Yoneda lemma: representable \mathbf{Set}-valued functors are free on one generator.)
In general, such freely generated \mathbf{Set}-sets are called polynomials, since they are described by formulas \mathcal{X}(S) = \sum_{i \in I} S^{N_i}.
2.2 Technical aside: support
Suppose \mathcal{X} is a \mathbf{Set}-set and \phi \in \mathcal{X}(S). If as usual we interpret \phi as an expression filled with elements of S, a simple question to ask is: which elements of S appear in \phi?
For instance, in either of the earlier examples, the expression \boxed{x + x} \in \mathcal{X}(\{x, y\}) features only the element x. The expression \boxed{y + y} \in \mathcal{X}(\{x, y\}) on the other hand features only the element y, and the expression \boxed{x + y} \in \mathcal{X}(\{x, y\}) features both elements x and y. This seems to be a simple idea, but it is actually subtle.
This means that \phi can be expressed such that it only features elements of U. Above, \{x\} \subseteq \{x, y\} is a strong support of \boxed{x + x} but neither \boxed{y + y} nor \boxed{x + y}.
Perhaps counterintuitively, it is not necessary for \phi to have a smallest strong support. In fact, strong supports are not in general even closed under finite intersections. Consider a unary expression \phi(x) subject to the equation \phi(x) = \phi(y), effectively eliminating the dependence of the expression on x. This corresponds to a \mathbf{Set}-set \mathcal{X} such that \mathcal{X}(S) is empty if S is empty and otherwise has one element.
\begin{align*} \mathcal{X}(\emptyset) &= \emptyset \\[.5em] \mathcal{X}(\{x\}) &= \left\{\boxed{\phi(x)}\right\} \\[.5em] \mathcal{X}(\{x, y\}) &= \left\{\boxed{\phi(x)} = \boxed{\phi(y)}\right\} \\[.5em] \mathcal{X}(\{x, y, z\}) &= \left\{\boxed{\phi(x)} = \boxed{\phi(y)} = \boxed{\phi(z)}\right\} \end{align*}
Although the subsets \{x\} and \{y\} of \{x, y\} are both strong supports of the expression \boxed{\phi(x)} = \boxed{\phi(y)} \in \mathcal{X}(\{x, y\}), their intersection, the empty subset, is not.
A slightly different definition can partially resolve this defect. To aid readability we use the “action” notation f \cdot \phi to denote \mathcal{X}(f)(\phi) where \phi \in \mathcal{X}(S) and f \colon S \to T.
This means whenever f and g agree on U, their relabeling actions agree on \phi, i.e. \phi only “depends on” elements in U. With this definition, one can show that any finite intersection of supports of \phi is again a support of \phi.
(The two definitions are extremely close: strong support implies support, and conversely support implies strong support for all subsets U that are nonempty.)
However, it is still not necessary for \phi to have a smallest support, if we consider infinite expressions. Consider an expression \phi(x_0, x_1, x_2, \ldots) involving a sequence of infinitely many elements, subject to the infinitely many equations \phi(x_0, x_1, x_2, \ldots) = \phi(y, x_1, x_2, \ldots) = \phi(x_0, y, x_2, \ldots) = \phi(x_0, x_1, y, \ldots) = \;\cdots
effectively eliminating the dependence of the expression on any single x_i. In the corresponding \mathbf{Set}-set \mathcal{X}, the set \mathcal{X}(S) consists of “sequences in S modulo eventual agreement”: two sequences \mathbb{N} \to S are equivalent if they agree on all but finitely many indices. Here a sequence with infinitely many distinct elements has no smallest support, because a support is a subset including all but finitely many of the elements in the sequence, and there is no smallest such subset.
Although \phi may not have a smallest support, it does have a filter of supports. That is, supports are closed under supersets and finite intersections, analogous to the neighborhoods of a point in a topological space. (Conversely, for any filter \mathcal{F} on a set N, one can construct a \mathbf{Set}-set on an N-ary generator whose supports are the subsets of N in \mathcal{F}, via appropriate relations.)
In summary, an infinite expression (modulo equality) may have no particular smallest set of elements it depends on. Thus an operation may only depend on ever-shrinkingly small subsets of its inputs. Dually, a co-operation might output an “infinitesimal neighborhood”, in the sense that only elements within ever-shrinkingly small subsets of its outputs have assigned values. For this reason there is a close relationship between topological spaces and coalgebraic structures.
3 Examples of (co)algebras
The following seems a reasonable way of making precise the previously informal terms “operation” and “co-operation”: a (co)operation is a generator for a presentation of a \mathbf{Set}-set. (It is an expression \phi \in \mathcal{X}(S) with S many slots that can be filled with elements.) Whether we call this an operation or a co-operation depends on whether we are interested in algebra or coalgebra.
Given a \mathbf{Set}-set \mathcal{X}, an algebra is a map \mathcal{X}(S) \to S (assigning to each operation filled with elements a unique element). A coalgebra is a map S \to \mathcal{X}(S) (assigning to each element a unique co-operation filled with elements). In the context of an algebra, the elements that fill the expressions act as inputs, whereas in the context of a coalgebra, the elements that fill the expressions act as outputs.
For example, an algebra \mathcal{X}(S) \to S for the \mathbf{Set}-set \mathcal{X} described earlier presented by an x + y subject to the equation x + y = y + x is a set with a commutative binary operation, whereas a coalgebra S \to \mathcal{X}(S) is a set with a “commutative binary co-operation”, assigning each element an unordered pair of elements.
Likely most readers are more familiar with algebra/operations than coalgebra/co-operations, so here are some examples of the latter.
3.1 Directed multigraphs
Directed multigraphs (a.k.a. quivers) can be modeled as coalgebras, using an edge co-operation and a vertex co-operation.
The edge co-operation e has two outputs (s and t), and the vertex co-operation v has zero outputs. Together these two expressions e(s, t) \in \mathcal{X}(\{s, t\}) and v() \in \mathcal{X}(\emptyset) generate a polynomial (i.e. freely generated) \mathbf{Set}-set:
\mathcal{X}(S) = S^2 + S^0 = S^2 + 1. Pictured below is a directed multigraph with four edges and four vertices, providing an example of a coalgebra S \to \mathcal{X}(S). In this case the set S has ten elements, four of which are assigned the edge co-operation, each thus outputting two elements, and six of which are assigned the vertex co-operation, each thus outputting no elements.
Not all coalgebras of this \mathbf{Set}-set \mathcal{X} cohere as directed multigraphs: it is necessary to impose the additional condition that the two outputs of each edge are vertices, not edges. The the ability to specify such conditions on coalgebras is provided by the concept of a comonad.
Note that a directed multigraph may be equivalently described as a functor \mathbf{C}-set (a functor \mathbf{C} \to \mathbf{Set}) where \mathbf{C} is the category:
In general, \mathbf{C}-sets for any category \mathbf{C} can be modeled as coalgebras of a polynomial \mathbf{Set}-set. Namely, there is a co-operation for each object, whose outputs are all the arrows out of the object.
(In the directed graph example above, the identity arrows were omitted from the co-operations for simplicity. If they were included, then e would become an operation with three outputs s, t, and \mathrm{id}_e, and v would become an operation with one output \mathrm{id}_v. The corresponding polynomial \mathbf{Set}-set has formula \mathcal{X}(S) = S^3 + S^1.)
Additional associativity and unit constraints are needed to ensure the elements and assigned co-operations cohere as a \mathbf{C}-set. For any category \mathbf{C}, there is a comonad on \mathbf{Set} whose coalgebras are \mathbf{C}-sets. In fact, it was noticed only relatively recently (Ahman and Uustalu 2016) that comonads on \mathbf{Set} given by polynomial formulas are precisely the same as (small) categories.
Viewing a \mathbf{C}-set as a coalgebra, the co-operation assigned to an element specifies the type of the element and produces at once all elements derived from that type. The same intuition may be applied to more general coalgebras of \mathbf{Set}-sets.
3.2 Undirected multigraphs
There are coalgebraic structures besides \mathbf{C}-sets, for example undirected multigraphs.
In this case the two vertices output by the edge co-operation are unordered pair instead of an ordered pair. The generating co-operations e(s,t) and v() are as before, but this time with the relation e(s,t) = e(t,s). The undirected multigraph below is an example of a coalgebra for the presented endofunctor.
As in the case of directed multigraphs, there is a comonad on \mathbf{Set} whose coalgebras are undirected multigraphs. Perhaps it is reasonable to call this a “generalized category” \mathbf{C}, for which “\mathbf{C}-sets” are undirected multigraphs.
3.3 Sheaves
This final example is intended to whet your appetite, so do not be disturbed if some aspects remain puzzling.
A sheaf is a way of gluing regions of a topological space \mathbf{X} together into a larger space that locally resembles the original space. It can be modeled as a coalgebra, using a co-operation for each point of \mathbf{X}, outputting the points in its “infinitesimal neighborhood”.
That is, sheaves over \mathbf{X} are coalgebras for a \mathbf{Set}-set \mathcal{X} generated by a co-operation in \mathcal{X}(|\mathbf{X}|) for each point x\in \mathbf{X} whose supports (see earlier section) are exactly the neighborhoods of x. More specifically,
\mathcal{X}(S) \; = \;\sum_{x \in \mathbf{X}}\; \mathop{\mathrm{colim}}_{U \in \mathcal{N}_x} \; S^U where \mathcal{N}_x is the neighborhood filter of x. In terms of generators and relations, this \mathbf{Set}-set is defined as follows: for each point x, there is a U-ary generator for each neighborhood U, all of which are identified so as to only retain dependence on the elements that are within arbitrarily small neighborhoods of x. This determines a co-operation that essentially outputs an infinitesimal neighborhood’s worth of elements.
Again, additional associativity and unit constraints on a coalgebra are needed to ensure that the coalgebra coheres as a sheaf, and again this is captured via comonad structure. For any topological space \mathbf{X}, there is a comonad on \mathbf{Set}, with the above formula, whose coalgebras are sheaves over \mathbf{X}, and the topological space can be recovered from the comonad. In this way, like categories, topological spaces are identified with a certain class of comonads on \mathbf{Set}.
In fact, topological spaces play the same role in relation to general comonads on \mathbf{Set} as preorders do to categories. To learn about this analogy and related curiosities, stay tuned for the upcoming paper
COMONADS ON SET
by Kevin Carlson, Aaron David Fairbanks, and David Spivak
where we will push as far as we can the perspective that comonads on \mathbf{Set} are a common generalization of both categories and topological spaces.
References
Adamek, Jiri, and Hans-E. Porst. 2003. “On Varieties and Covarieties in a Category.” Mathematical Structures in Computer Science 13 (2): 201–32. https://doi.org/10.1017/S0960129502003882.
Ahman, Danel, and Tarmo Uustalu. 2016. “Directed Containers as Categories.” EPTCS 207, 2016, Pp. 89-98.
Mac Lane, Saunders. 1998. Categories for the Working Mathematician. 2nd ed. Graduate Texts in Mathematics 5. New York: Springer-Verlag.
Riehl, Emily. 2017. Category Theory in Context. Courier Dover Publications.