5.2: Props and Presentations

Just as the wiring diagrams for symmetric monoidal preorders did not require labels on the boxes, this means that wiring diagrams for props do not require labels on the wires. This makes props particularly suited for describing diagrammatic formalisms such as signal flow graphs, which only have wires of a single type.

Finally, many systems behave in what is called a linear way, and linear systems form a foundational part of control theory, a branch of engineering that works on cyber-physical systems. Similarly, linear algebra is a foundational part of modern mathematics, both pure and applied, which includes not only control theory, but also the practice of computing, physics, statistics, and many others. As we analyze signal flow graphs, we shall see that they are in fact a way of recasting linear algebra—more specifically, matrix operations in graphical terms. More formally, we shall say that signal flow graphs have functorial semantics as matrices.

Props: definition and first examples

Recall the definition of symmetric strict monoidal category from Definition 4.45 and Re- mark 4.46.

Definition: 5.2.

A prop is a symmetric strict monoidal category (C,0,+) for which Ob(C) = \(\mathbb{N}\), the monoidal unit is 0 \(\in\) \(\mathbb{N}\), and the monoidal product on objects is given by addition.

Note that each object n is the n-fold monoidal product of the object 1; we call 1 the generating object. Since the objects of a prop are always the natural numbers, to specify a prop P it is enough to specify five things:

1. a set C(m,n) of morphisms m → n, for m, n \(\in\) \(\mathbb{N}\).
2. for all n \(\in\) \(\mathbb{N}\), an identity map idn : n → n.
3. for all m, n \(\in\) \(\mathbb{N}\), a symmetry map σ\(_{m,n}\) : m + n → n + m.
4. a composition rule: given f :m → n and g : n → p, a map (f ; g): m → p.
5. a monoidal product on morphisms: given f : m → m′ and g: n → n′, a map (f + g): m + n → m′ + n′.

Once one specifies the above data, he should check that his specifications satisfy the rules of symmetric monoidal categories (see Definition 4.45).\(^{2}\)

Example 5.3.

There is a prop FinSet where the morphisms f : m → n are functions from \(\underline{m}\) = {1, . . . m} to \(\underline{n}\) = {1, . . . , n}. (The identities, symmetries, and composition rule are obvious.)

The monoidal product on functions is given by the disjoint union of functions: that is, given f : m → m′ and g : n → n′,

we define f + g : m + n → m′ + n′ by

Exercise 5.5.

In Example 5.3 we said that the identities, symmetries, and composition rule in FinSet “are obvious.” In math lingo, this just means “we trust that the reader can figure them out, if she spends the time tracking down the definitions and fitting them together.”

1. Draw a morphism f : 3 → 2 and a morphism g : 2 → 4 in FinSet.
2. Draw f + g.
3. What is the composition rule for morphisms f : m → n and g : n → p in FinSet? 4. What are the identities in FinSet? Draw some.
5. Choose m, n \(\in\) \(\mathbb{N}\), and draw the symmetry map σ\(_{m,n}\) in FinSet? ♦

Example 5.6.

Recall from Definition 1.22 that a bijection is a function that is both surjective and injective. There is a prop Bij where the morphisms f : m → n are bijections \(\underline{m}\) → \(\underline{n}\).

Note that in this case morphisms m → n only exist when m = n; when m \(\neq\) n the homset Bij(m, n) is empty. Since Bij is a subcategory of FinSet, we can define the monoidal product to be as in Eq. (5.4).

Example 5.7.

The compact closed category Corel, in which the morphisms f : m → n are partitions on \(\underline{m}\) ⊔ \(\underline{n}\) (see Example 4.61), is a prop.

Example 5.8.

There is a prop Rel for which morphisms m → n are relations, R \(\subseteq\) \(\underline{m}\) × \(\underline{n}\).

The composition of R with S \(\subseteq\) \(\underline{n}\) × \(\underline{p}\) is

\(R \text { ; } S:=\{(i, k) \in \underline{m} \times p \mid \exists(j \in \underline{n}) \cdot(i, j) \in R \text { and }(j, k) \in S\}\)

The monoidal product is relatively easy to formalize using universal properties, but one might get better intuition from pictures:

Exercise 5.9.

A posetal prop is a prop that is also a poset. That is, a posetal prop is a symmetric monoidal preorder of the form (\(\mathbb{N}\), ≼), for some poset relation ≼ on \(\mathbb{N}\), where the monoidal product on objects is addition. We’ve spent a lot of time discussing order structures on the natural numbers. Give three examples of a posetal prop. ♦

Definition: 5.11.

Let C and D be props. A functor F : C → D is called a prop functor if

(a) F is identity-on-objects, i.e. F(n) = n for all n \(\in\) Ob(C) = Ob(D) = \(\mathbb{N}\), and

(b) for all f : m\(_{1}\) → m\(_{2}\) and g : n\(_{1}\) → n\(_{2}\) in C, we have F( f ) + F( g ) = F( f +g ) in D.

Example 5.12.

The inclusion i : Bij → FinSet is a prop functor. Perhaps more interestingly, there is a prop functor F: FinSet → Rel\(_{Fin}\). It sends a function f : m → n to the relationF(f) := { ( i, j ) | f (i ) = j } \(\subseteq\) \(\underline{m}\) × \(\underline{n}\).

The prop of port graphs

An important example of a prop is the one in which morphisms are open, directed, acyclic port graphs, as we next define. We will just call them port graphs.

Definition: 5.13.

For m, n \(\in\) N, an (m, n)-port graph (V, in, out, i) is specified by

1. a set V, elements of which are called vertices,
2. functions in,out: V → \(\mathbb{N}\), where in(v) and out(v) are called the in degree and out degree of each v \(\in\) V, and
3. a bijection i : \(\underline{m} \sqcup O \stackrel{\cong}{\rightarrow} I \sqcup \underline{n}, \text { where } I=\{(v, i) \mid v \in V, 1 \leq i \leq \operatorname{in}(v)\}\) is the set of vertex inputs, and O = {(v, i) | v \(\in\) V, 1 ≤ i ≤ out(v)} is the set of vertex outputs.

This data must obey the following acyclicity condition. First, use the bijection ι to construct the graph with vertices V and with an arrow \(e_{v, j}^{u, i}: u \rightarrow v\) for every i, j \(\in\) N such that ι(u, i) = (v, j); call it the internal flow graph. If the internal flow graph is acyclic that is, if the only path from any vertex v to itself is the trivial path then we say that (V, in, out, ι) is a port graph.

This seems quite a technical construction, but it’s quite intuitive once you unpack it a bit. Let’s do this.

Example 5.14.

Here is an example of a (2, 3)-port graph, i.e. with m = 2 and n = 3:

Since the port graph has type (2, 3), we draw two ports on the left hand side of the outer box, and three on the right. The vertex set is V = {a, b, c} and, for example in(a) = 1 and out(a) = 3, so we draw one port on the left-hand side and three ports on the right-hand side of the box labelled a. The bijection ι is what tells us how the ports are connected by wires:

The internal flow graph—which one can see is acyclic—is shown below:

As you might guess from (5.15), port graphs are closely related to wiring diagrams for monoidal categories, and even more closely related to wiring diagrams for props.

A category PG whose morphisms are port graphs. Given an (m,n)-port graph (V, in, out, ι) and an (n, p)-port graph (V′, in′, out′, ι′), we may compose them to produce an (m, p) port graph (V ⊔ V′, [in, in′], [out, out′], ι′′). Here [in, in′] denotes the function V ⊔ V′ → N which maps elements of V according to in, and elements of V′ according to in′, and similarly for [out, out′]. The bijection ι′′ : \(\underline{m}\) ⊔ O ⊔ O′ → I ⊔ I′ ⊔ \(\underline{p}\) is defined as follows:

Exercise 5.16.

Describe how port graph composition looks, with respect to the visual representation of Example 5.14, and give a nontrivial example. ♦

We thus have a category PG, whose objects are natural numbers Ob(PG) = \(\mathbb{N}\), whose morphisms are port graphs PG(m, n) = {(V, in, out, ι) | as in Definition 5.13}. Composition of port graphs is as above, and the identity port graph on n is the (n, n) port graph (Ø, !, !, idn ), where ! : Ø → \(\mathbb{N}\) is the unique function. The identity on an object, say 3, is depicted as follows:

The monoidal structure structure on PG. This category PG is in fact a prop. The monoidal product of two port graphs G := (V, in, out, ι) and G′:= (V′, in′, out′, ι′) is given by taking the disjoint union of ι and ι′:

\(G+G^{\prime}:=\left(\left(V \sqcup V^{\prime}\right),\left[\text { in }, \text { in }^{\prime}\right],\left[\text { out }, \text { out }^{\prime}\right],\left(\iota \sqcup \iota^{\prime}\right)\right)\) (5.17)

The monoidal unit is (Ø, !, !, !).

Exercise 5.18.

Draw the monoidal product of the morphism shown in Eq. (5.15) with itself. It will be a (4, 6)-port graph, i.e. a morphism 4 → 6 in PG. ♦

Free constructions and universal properties

Given some sort of categorical structure, such as a preorder, a category, or a prop, it is useful to be able to construct one according to your own specification. (This should not be surprising.) The minimally-constrained structure that contains all the data you specify is called the free structure on your specification: it’s free from unneccessary constraints! We have already seen some examples of free structures; let’s recall and explore them.

Example 5.19 (The free preorder on a relation).

For preorders, we saw the construction of taking the reflexive, transitive closure of a relation. That is, given a relation R \(\subseteq\) P×P, the reflexive, transitive closure of R is the called the free preorder on R. Rather than specify all the inequalities in the preorder (P, ≤), we can specify just a few inequalities p ≤ q, and let our “closure machine” add in the minimum number of other inequalities necessary to make P a preorder. To obtain a preorder out of a graph, or Hasse diagram, weconsideragraph(V, A, s, t) as defining a relation {(s (a),t (a)) | a \(\in\) A} \(\subseteq\) V × V, and apply this closure machine.
But in what sense is the reflexive, transitive closure of a relation R \(\subseteq\) P × P really the minimally-constrained preorder containing R? One way of understanding this is that the extra equalities impose no further constraints when defining a monotone map out of P. We are claiming that freeness has something to do with maps out! As strange as an asymmetry might seem here (one might ask, “why not maps in?”), the reader will have an opportunity to explore it for herself in Exercises 5.20 and 5.21.

A higher-level justification understands freeness as a left adjoint (see Example 3.74), but we will not discuss that here.

Exercise 5.20.

Let P be a set, let R \(\subseteq\) P × P a relation, let (P, ≤\(_{P}\) ) be the preorder obtained by taking the reflexive, transitive closure of R, and let (Q, ≤\(_{Q}\)) be an arbitrary preorder. Finally, let f : P → Q be a function, not assumed monotone.

1. Suppose that for every x, y \(\in\) P, if R(x, y) then f (x) ≤ f (y). Show that f defines a monotone map f : (P, ≤\(_{P}\)) → (Q, ≤\(_{Q}\)).

2. Suppose that f defines a monotone map f : (P, ≤\(_{P}\)) → (Q, ≤\(_{Q}\)). Show that for every x, y \(\in\) P, if R(x, y) then f(x) ≤\(_{Q}\) f(y). We call this the universal property of the free preorder (P, ≤\(_{P}\) ). ♦

Exercise 5.21.

Let P, Q, R, etc. be as in Exercise 5.20. We want to see that the universal property is really about maps out of and not maps in to the reflexive, transitive closure (P, ≤). So let g : Q → P be a function.

1. Suppose that for every a, b \(\in\) Q, if a ≤ b then (g(a), g(b)) \(\in\) R. Is it automatically true that g defines a monotone map g : (Q , ≤Q ) → (P, ≤P )?

2. Suppose that g defines a monotone map g :(Q, ≤\(_{Q}\)) → (P, ≤\(_{P}\)).

Is it automatically true that for every a, b \(\in\) Q, if a ≤ b then (g(a), g(b)) \(\in\) R?

The lesson is that maps between structured objects are defined to preserve constraints. This means the domain of a map must be somehow more constrained than the codomain. Thus having the fewest additional constraints coincides with having the most maps out every function that respects our generating constraints should define a map. ♦

Example 5.22 (The free category on a graph).

There is a similar story for categories. Indeed, we saw in Definition 3.7 the construction of the free category Free(G) on a graph G. The objects of Free(G) and the vertices of G are the same nothing new here but the morphisms of Free(G) are not just the arrows of G because morphisms in a category have stricter requirements: they must compose and there must be an identity. Thus morphisms in Free(G) are the closure of the set of arrows in G under these operations. Luckily (although this happens often in category theory), the result turns out to already be a relevant graph concept: the morphisms in Free(G) are exactly the paths in G. So Free(G) is a category that in a sense contains G and obeys no equations other than those that categories are forced to obey.Solution

Add text here.

Exercise 5.23.

Let G = (V, A, s, t) be a graph, and let G be the free category on G. Let C be another category whose set of morphisms is denoted Mor(C).

1. Someone tells you that there are “domain and codomain” functions dom, cod: Mor(C)→ Ob(C); interpret this statement.

2. Show that the set of functors G → C are in one-to-one correspondence with the set of pairs of functions (f,g), where f : V → Ob(C) and g: A → Mor(C) for which dom (g(a)) = f (s(a)) and cod(g(a)) = f (t(a)) for all a.

3. Is (Mor(C), Ob(C), dom, cod) a graph? If so, see if you can use the word “adjunc- tion” in a sentence that describes the statement in part 2. If not, explain why not. ♦

Exercise 5.24 (The free monoid on a set).

Recall from Example 3.13 that monoids are one-object categories. For any set A, there is a graph Loop(A) with one vertex and with one arrow from the vertex to itself for each a \(\in\) A. So if A = {a, b} then Loop(A) looks like this:

The free category on this graph is a one-object category, and hence a monoid; it’s called the free monoid on A.

1. What are the elements of the free monoid on the set A = {a}?

2. Can you find a well-known monoid that is isomorphic to the free monoid on {a}?

3. What are the elements of the free monoid on the set A = {a, b}? ♦

The free prop on a signature

We have been discussing free constructions, in particular for preorders and categories. A similar construction exists for props. Since we already know what the objects of the prop will be—the natural numbers—all we need to specify is a set G of generating morphisms, together with the arities,4 that we want to be in our prop. This information will be called a signature. Just as we can generate the free category from a graph, so too can we generate the free prop from a signature.

We now give an explicit construction of the free prop in terms of port graphs (see Definition 5.13).

Definition: 5.25.

A prop signature is a tuple (G, s, t), where G is a set and s, t : G → \(\mathbb{N}\) are functions; each element g \(\in\) G is called a generator and s(g), t(g) \(\in\) \(\mathbb{N}\) are called its in-arity and out-arity. We often denote (G, s, t ) simply by G, taking s, t to be implicit.

A G-labeling of a port graph Γ = (V,in,out,ι) is a function l: V → G such that the arities agree: s(l(v)) = in(v) and t(l(v)) = out(v) for each v \(\in\) V.

Define the free prop on G, denoted Free(G), to have as morphisms m → n all G labeled (m, n) port graphs. The composition and monoidal structure are just those for port graphs PG (see Eq. (5.17)); the labelings (the l’s) are just carried along.

The morphisms in Free(G) are port graphs (V, in, out, ι) as in Definition 5.13, that are equipped with a G-labeling. To draw a port graph, just as in Example 5.14, we draw each vertex v \(\in\) V as a box with in(v)-many ports on the left and out(v) many ports on the right. In wiring diagrams, we depict the labeling function l : V → G by using l to add labels (in the usual sense) to our boxes. Note that multiple boxes can be labelled with the same generator. For example, if G = { f : 1 → 1, g : 2 → 2, h : 2 → 1}, then the following is a morphism 3 → 2 in Free(G):

Note that the generator g is used twice, while the generator f is not used at all in Eq. (5.26). This is perfectly fine.

Example 5.27.

The free prop on the empty set Ø is Bij.

This is because each morphism must have a labelling function of the form V → Ø, and hence we must have V = Ø; see Exercise 1.25. Thus the only morphisms (n, m) are those given by port graphs (Ø, !, !, σ), where σ : n → m is a bijection.

Exercise 5.28.

Consider the following prop signature:

\(G:=\left\{\rho_{m, n} \mid m, n \in \mathbb{N}\right\}, \quad s\left(\rho_{m, n}\right):=m, \quad t\left(\rho_{m, n}\right):=n\)

i.e. having one generating morphism for each (m, n) \(\in\) N\(^{2}\). Show that Free(G) is the prop PG of port graphs from Section 5.2.2. ♦

Just like free preorders and free categories, the free prop is characterized by a universal property in terms of maps out. The following can be proved in a manner similar to Exercise 5.23.

Proposition 5.29.

The free prop Free(G) on a signature (G, s, t) has the property that, for any prop C, the prop functors Free(G) → C are in one-to-one correspondence with functions G → C that send each g \(\in\) G to a morphism s(g) → t(g) in C.

An alternate way to describe morphisms in Free(G). Port graphs provide a conve- nient formalism of thinking about morphisms in the free prop on a signature G, but there is another approach which is also useful. It is syntactic, in the sense that we start with a small stock of basic morphisms, including elements of G, and then we inductively

build new morphisms from them using the basic operations of props: namely composition and monoidal product. Sometimes the conditions of monoidal categories e.g. associativity, unitality, functoriality, see Definition 4.45 force two such morphisms to be equal, and so we dutifully equate them. When we are done, the result is again the free prop Free(G). Let’s make this more formal.

First, we need the notion of a prop expression. Just as prop signatures are the analogue of the graphs used to present categories, prop expressions are the analogue of paths in these graphs.

Definition: 5.30.

Suppose we have a set G and functions s,t: G → N. We define a G-generated prop expression, or simply expression e : m → n, where m, n \(\in\) N, inductively as follows:

• The empty morphism \(id_{0}\) : 0 → 0, the identity morphism \(id_{1}\) : 1 → 1, and the symmetry σ : 2 → 2 are expressions.\(^{5}\)

• the generators g \(\in\) G are expressions g : s(g) → t(g).

• if α: m → n and β: p → q are expressions, then α + β: m + p → n + q is an expression.

• if α: m → n and β: n → p are expressions, then α ; β:m→p is an expression.

We write Expr(G) for the set of expressions in G. If e : m → n is an expression, we refer to (m, n) as its aritty.

Example 5.31.

Let G = {f :1 → 1, g : 2 → 2, h : 2 → 1}. Then

• id\(_{1}\) : 1 → 1,

• f :1 → 1,

• f ; id\(_{1}\): 1 → 1,

• h + id\(_{1}\): 3 → 2, and

• (h + id\(_{1}\)) ; σ ; g ; σ: 3 → 2

are all G-generated prop expressions.

Both G-labeled port graphs and G-generated prop expressions are ways to describe morphisms in the free prop Free(G). Note, however, that unlike for G-labeled port graphs, there may be two G-generated prop expressions that represent the same mor- phism. For example, we want to consider f ; id\(_{1}\) and f to be the same morphism, since the unitality axiom for categories says f ; id\(_{1}\) = f . Nonetheless, we only consider two G-generated prop expressions equal when some axiom from the definition of prop requires that they be so; again, the free prop is the minimally-constrained way to take G and obtain a prop.

Since both port graphs and prop expressions describe morphisms in Free(G), you might be wondering how to translate between them. Here’s how to turn a port graph into a prop expression: imagine a vertical line moving through the port graph from left to right. Whenever you see “action”—either a box or wires crossing write down the sum (using +) of all the boxes g, all the symmetries σ, and all the wires id\(_{1}\) in that column. Finally, compose all of those action columns. For example, in the picture below we see four action columns:

Here the result is (g + id\(_{1}\)) ; (id\(_{1}\) +σ) ; (id\(_{1}\) +g) ; (h + id\(_{1}\)).

Exercise 5.32.

Consider again the free prop on generators G = { f : 1 → 1, g : 2 → 2, h : 2 → 1}.

Draw a picture of ( f + id\(_{1}\) + id\(_{1}\)) ; (σ + id\(_{1}\)) ; (id\(_{1}\) + h) ; σ ; g, where σ : 2 → 2 is the symmetry map.

Another way of describing when we should consider two prop expressions equal is to say that they are equal if and only if they represent the same port graph. In either case, these notions induce an equivalence relation on the set of prop expressions. To say that we consider these certain prop expressions equal is to say that the morphisms of the free prop on G are the G-generated prop expressions quotiented by this equivalence relation (see Definition 1.21).

Props via presentations

In Section 3.2.2 we saw that a presentation for a category, or database schema, consists of a graph together with imposed equations between paths. Similarly here, sometimes we want to construct a prop whose morphisms obey specific equations. But rather than mere paths, the things we want to equate are prop expressions as in Definition 5.30.

Rough Definition 5.33.

A presentation (G, s, t, E) for a prop is a set G, functions s , t : G → N, and a set E \(\subseteq\) Expr(G) × Expr(G) of pairs of G-generated prop expressions, such that e1 and e2 have the same arity for each (e1, e2) \(\in\) E. We refer to G as the set of generators and to E as the set of equations in the presentation.\(^{6}\)

The prop G presented by the presentation (G, s, t, E) is the prop whose morphisms are elements in Expr(G), quotiented by both the equations e1 = e2 where (e1, e2) \(\in\) E, and by the axioms of symmetric strict monoidal categories.

Remark 5.34. Given a presentation (G, s, t, E), it can be shown that the prop G has a universal property in terms of “maps out.” Namely prop functors from G to any

other prop C are in one-to-one correspondence with functions f from G to the set of morphisms in C such that

• for all g \(\in\) G, f (g) is a morphism s(g) → t(g), and

• for all (e1,e2) \(\in\) E, we have that f(e1) = f(e2) in C, where f(e) denotes the morphism in C obtained by applying f to each generators in the expression e, and then composing the result in C.

Exercise 5.35.

Is it the case that the free prop on generators (G, s, t), defined in Definition 5.25, is the same thing as the prop presented by (G, s, t, Ø), having no relations, as defined in Definition 5.33? Or is there a subtle difference somehow? ♦