8.5: Solutions for Chapter 5

Exercise 5.5

1. Below we draw a morphism f : 3 → 2 and a morphism g : 2 → 4 in FinSet:

2. Here is a picture of f + g

3. The composite of morphisms f : m → n and g :n → p in FinSet is the function (f ; g) : m → p given by (f ; g)(i) = g(f (i)) for all 1 ≤ i ≤ m.
4. The identity id\(_{m}\) : m → m is given by id\(_{m}\)(i) = i for all 1 ≤ i ≤ m. Here is a picture of id\(_{2}\) and id\(_{8}\):

5. Here is a picture of the symmetry σ\(_{3,5}\) : 8 → 8 :

Exercise 5.9

We need to give examples posetal props, i.e. each will be a poset whose set of objects is N, whose order is denoted m \(\leq\) n, and with the property

that whenever m\(_{1}\) \(\leq\) n\(_{1}\) and m\(_{2}\) \(\leq\) n\(_{2}\) hold then m\(_{1}\) + m\(_{2}\) \(\leq\) n\(_{1}\) + n\(_{2}\) does too.

The question only asks for three, but we will additionally give a quasi-example and a non-example.

1. Take \(\leq\) to be the discrete order : m \(\leq\) n iff m = n.

2. Take \(\leq\) to be the usual order, m \(\leq\) n iff there exists d \(\in\) N with d + m = n.

3. Take \(\leq\) to be there verse of the usual order, m \(\leq\) n iff there exists d \(\in\) N with m = n + d.

4. Take \(\leq\) to be the co-discrete orderm \(\leq\) n for all m, n. Some may object that this is a preorder, not a poset, so we call it a quasi-example.

5. (Non-example.) Take \(\leq\) to be the division order, m \(\leq\) n iff there exists q \(\in\) N with m ∗ q = d. This is a perfectly good poset, but it does not satisfy the monotonicity property: we have 2 \(\leq\) 4 and 3 \(\leq\) 3 but not 5 \(\leq\)\(^{?}\) 7.

Exercise 5.10

Example5.6: The prop Bij has

1. Bij(m, n) := { f : \(\underline{m}\) → \(\underline{n}\) | f is a bijection}. Note that Bij(m, n) = Ø if m \(\neq\) n and it has n! elements if m = n.

2. The identity map n → n is the bijection \(\underline{n}\) → \(\underline{n}\) sending i → i.

3.The symmetry map m + \(\underline{n}\) → \(\underline{n}\) + m is the bijection σ\(_{m, n}\) : \(\underline{m + n}\) → \(\underline{n + m}\) given by

4. Composition of bijections m → n and n → p is just their composition as functions, which is again a bijection.

5. Given bijections f : m → m′ and g : n → n′, their monoidal product (f + g): (m + n) → (m′ + n′) is given by

Example 5.7: The prop Corel has

1. Corel(m,n) is the set of equivalence relations on m + n.
2. The identity map n → n is the smallest equivalence relation, which is the smallest reflexive relation, i.e. where i ∼ j iff i = j.
3. The symmetry map σm,n, as an equivalence relation on m + n + n + m is “the obvious thing,” namely “equating corresponding m’s together and also equating corresponding n’s together.” To be pedantic, i ∼ j iff either

• |i − j| = m + n + n, or

• m + 1 ≤ i ≤ m + n + n and m + 1 ≤ j ≤ m + n + n and |i − j| = n.

4. Composition of an equivalence relation ∼ on \(\underline{m + n}\) and an equivalence relation ∼ on \(\underline{n + p}\) is

the equivalence relation ≃ on \(\underline{m + p}\) given by i ≃ k iff there exists j \(\in\) n with i ∼ j and j∼ k.

5. Given equivalence relations ∼ on \(\underline{m + n}\) and ∼′on \(\underline{m' + n'}\), we need an equivalence relation (∼ + ∼′) on \(\underline{m + n + m' + n'}\). We take it to be “the obvious thing,” namely “using ∼ on the unprimed stuff and using ∼ on the primed stuff, with no other interaction.” To be pedantic, i ∼ j iff either

• i ≤ m + n and j ≤ m + n and i ∼ j, or

• m + n + 1 ≤ i and m + n + 1 ≤ j and i ∼′ j.

Example 5.8: The prop Rel has

1. Rel(m,n) is the set of relations on the set \(\underline{m}\) × \(\underline{n}\), i.e. the set of subsets of \(\underline{m}\) × \(\underline{n}\), i.e. its powerset
2. The identity map n → n is the subset {(i, j) \(\in\) \(\underline{n}\) × \(\underline{n}\) | i = j }.
3. The symmetry map m + n → n +m is the subset of pairs (i, j) \(\in\) (\(\underline{m + n}\)) × (\(\underline{n + m}\)) such that either

• i ≤ m and m + 1 ≤ j and i + m = j, or

• m + 1 ≤ i and j ≤ m and j + m = i.

4. Composition of relations is a sin Example 5.8.

5. Given a relation R \(\subseteq\) \(\underline{m}\) × \(\underline{n}\) and a relationR′ \(\subseteq\) \(\underline{m}\)′ × \(\underline{n}\) ′, we need a relation (R + R′) \(\subseteq\) \(\underline{m + m' x n + n'}\). As stated in the example (footnote), this can be given by a universal property: The monoidal product R\(_{1}\) + R\(_{2}\) of relations R\(_{1}\) \(\subseteq\) m\(_{1}\) × n\(_{1}\) and R\(_{2}\) \(\subseteq\) \(\underline{m_{2}}\) × \(\underline{n_{2}}\) is given by R\(_{1}\) ⊔ R\(_{2}\) \(\subseteq\) \(\underline{m_{1}}\) × \(\underline{n_{1}}\) ⊔ \(\underline{m_{2}}\) × \(\underline{n_{2}}\) \(\subseteq\) \(\underline{m_{1}}\) ⊔ \(\underline{m_{2}}\) × \(\underline{n_{1}}\) ⊔ \(\underline{n_{2}}\).

Exercise 5.16

Composition of an (m, n)-port graph G and an (n, p)-port graph H looks visually like sticking them end to end, connecting the wires in order, removing the two outer boxes, and adding a new outer box. For example, suppose we want to compose the following in the order shown:

The result is:

Exercise 5.18

The monoidal product of two morphisms is drawn by stacking the corresponding port graphs. For this problem, we just stack the left-hand picture on top of itself to obtain the righthand picture:

Exercise 5.20

We have a relation R \(\subseteq\) P × P which generates a preorder ≤\(_{P}\) on P, we have an arbitrary preorder (Q, ≤\(_{Q}\)) and a function f : P → Q, not necessarily monotonic.

1. Assume that for every x, y \(\in\) P, if R(x, y) thenf (x) ≤ f (y); we want to show that f is monotone, i.e. that for every x ≤\(_{P}\) y we have f (x) ≤\(_{Q}\) f (y). By definition of P being the reflexive, transitive closure of R, we have x ≤\(_{P}\) y iff there exists n \(\in\) \(\mathbb{N}\) and x\(_{0}\), ..., x\(_{n}\) in P with x\(_{0}\) = x and x\(_{n}\) = y and R(x\(_{i}\), x\(_{i + 1}\)) for each 0 ≤ i ≤ n − 1. (The case n = 0 handles reflexivity.) But then by assumption, R(x\(_{i}\), x\(_{i + 1}\)) implies f (x\(_{i}\)) ≤\(_{Q}\) f (x\(_{i + 1}\)) for each i. By induction on i we show that f (x\(_{0}\)) ≤\(_{Q}\) f (x\(_{i}\)) for all 0 ≤ i ≤ n, at which point we are done.
2. Suppose now that f is monotone, and take x, y \(\in\) P for which R(x, y) holds. Then x ≤\(_{P}\) y because ≤\(_{P}\) is the smallest preorder relation containing R. (Another way to see this based on the above description is with n = 1, x\(_{0}\) = x, and x\(_{n}\) = y, which we said implies x ≤\(_{P}\) y.) Since f is monotone, we indeed have f (x) ≤\(_{Q}\) f (y).

Exercise 5.21

Suppose that P, Q, and R are as in Exercise 5.20 and we have a function g : Q → P.

1. If R(g(a), g(b)) holds for all a ≤\(_{Q}\) b then g is monotone, because R(x, y) implies x ≤\(_{P}\) y.
2. It is possible for g : (Q, ≤\(_{Q}\)) → (P, ≤\(_{P}\)) to be monotone and yet have some a, b \(\in\) Q with a ≤\(_{Q}\) b and (g(a), g(b)) \(\not \in\) R. Indeed, take Q := {1} to be the free preorder on one element, and take P := {1} with R = Ø. Then the unique function g : Q → P is monotone (because ≤\(_{P}\) is reflexive even though R is empty), and yet (g(1), g(1)) \(\not \in\) R.

Exercise 5.23

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

1. To give a function Mor(C) → Ob(C) means that for every element Mor(C) we need to give exactly one element of Ob(C). So for dom we take any q \(\in\) Mor(C), view it as a morphism q: y → z, and send it to its domain y. Similarly for cod: we put cod(q) := z.

2. Suppose first that we are given a functor F : G → C. On objects we have a function Ob(G) → Ob(C), and this defines f since Ob(G) = V. On morphisms, first note that the arrows of graph G are exactly the length = 1 paths in G, whereas Mor(G) is the set of all paths in G, so we have an inclusion A \(\subseteq\) Mor(G). The functor F provides a function Mor(G) → Mor(C), which we can restrict to A to obtain g : A → Mor(C). All functors satisfy dom(F(r)) = F(dom(r)) and cod(F(r)) = F(cod(r)) for any r: w → x. In particular when r \(\in\) A is an arrow we have dom(r) = s(r) and cod(r) = t(r).

Thus we have found (f , g) with the required properties.

Suppose second that we are given a pair of functions (f, g) where f : V → Ob(C) and g : A → Mor(C) such that dom(g(a)) = f (s(a)) and cod(g(a)) = f (t(a)) for all a \(\in\) A. Define F : G → C on objects by f. An arbitrary morphism in G is a path p := (v\(_{0}\), a\(_{1}\), a\(_{2}\), ..., a\(_{n}\)) in G, where v\(_{0}\) \(\in\) V, a\(_{i}\) \(\in\) A, v\(_{0}\) = s(a\(_{1}\)), and t(a\(_{i}\)) = s(a\(_{i + 1}\)) for all 1 ≤ i ≤ n − 1. Then (a\(_{i}\)) is a morphism in C whose domain is f (v\(_{0}\)) and the morphisms (a\(_{i}\)) and (a\(_{i + 1}\)) are composable for every 1 ≤ i ≤ n − 1. We then take F(p) := id\(_{f(v0)}\) ; g(a\(_{1}\)) ; · · · ; g(a\(_{n}\)) to be the composite. It is easy to check that this is indeed a functor (preserves identities and compositions).

Third, we want to see that the two operations we just gave are mutually inverse. On objects this is straightforward, and on morphisms it is straightforward to see that, given (f , g), if we turn them into a functor F : G → C and then extract the new pair of functions (f ′,g′), then f = f′and g = g'. Finally, given a functor F : G → C, we extract the pair of functions (f , g) as above and then turn them into a new functor F ′ : G → C. It is clear that F and F ′ act the same on objects, so what about on morphisms. The formula says that F ′ acts the same on morphisms of length 1 in G (i.e. on the elements of A). But an arbitrary morphism in G is just a path, i.e. a sequence of composable arrows, and so by functoriality, both F and F ′ must act the same on arbitrary paths.

3. (Mor(C), Ob(C), dom, cod) is a graph; let’s denote it U(C) \(\in\) Grph. We have functors Free : Grph \(\rightleftharpoons\) Cat :U, and Free is left adjoint to U.

Exercise 5.24

1. The elements of the free monoid on the set {a} are:

a\(^{0}\), a\(^{1}\), a\(^{2}\), a\(^{3}\), ..., a\(^{2019}\),...

with monoid multiplication ∗ given by the usual natural number addition on the exponents, a\(^{i}\) ∗ a\(^{j}\) = a\(^{i + j}\).

2. This is isomorphic to \(\mathbb{N}\), by sending a\(^{i}\) \(\mapsto\) i.

3. The elements of the free monoid on the set {a, b} are ‘words in a and b,’ each of which we will represent as a list whose entries are either a or b. Here are some:

[ ], [a], [b], [a, a], [a, b], ..., [b, a, b, b, a, b, a, a, a, a], ...

Exercise 5.28

We have two props: the prop of port graphs and the free prop Free(G, s, t) where

G := {ρ\(_{m, n}\) : m → n | m, n \(\in\) \(\mathbb{N}\)}, s(ρ\(_{m, n}\) := m, t(ρ\(_{m, n}\) := n;

we want to show they are the same prop. As categories they have the same set of objects (in both cases,

N), so we need to show that for every m, n \(\in\) \(\mathbb{N}\), they have the same set of morphisms (and that their composition formulas and monoidal product formulas agree).

By Definition 5.25, a morphism m → n in Free(G) is a G-labeled port graph, i.e. a pair (Γ, l), where Γ = (V, in, out, ι) is an (m, n)-port graph and l : V → G is a function, such that the ‘arities agree.’ What does this mean? Recall that every vertex v \(\in\) V is drawn as a box with some left-hand ports and some right-hand ports an arity and l(v) \(\in\) G is supposed to have the correct arity; precisely, s(l(v)) = in(v) and t(l(v)) = out(v). But G was chosen so that it has exactly one element with any given arity, so the function l has only one choice, and thus contributes nothing: it neither increases nor decreases the freedom. In other words, a morphism in our particular Free(G) can be identified with an (m, n) port graph Γ, as desired.

Again by definition Definition 5.25, the ‘composition and the monoidal structure are just those for port graphs PG (see Eq. (5.17)); the labelings (the l’s) are just carried along.’ So we are done.

Exercise 5.32

Here is a picture of (f + id\(_{1}\) + id\(_{1}\)) ; (σ + id\(_{1}\)) ; (id\(_{1}\) + h) ; σ ; g, in the free prop on generators G = {f : 1 → 1, g : 2 → 2, h : 2 → 1}:

Exercise 5.35

The free prop on generators (G, s, t), defined in Definition 5.25, is for all intents and purposes the same thing as the prop presented by (G, s, t, Ø), having no relations. The only possible “subtle difference” we might have to admit is if someone said that a set S is “subtly different” than its quotient by the trivial equivalence relation. In the latter, the elements are the singleton subsets of S. So for example the quotient of S = {1, 2, 3} by the trivial equivalence relation is the set ({1}, {2}, {3}). It is subtly different than S, but the two are naturally isomorphic, and category-theoretically, the difference will never make a difference.

Exercise 5.41

1. If (R, 0, +, 1, ∗) is a rig, then the multiplicative identity 1 \(\in\) Mat\(_{n}\)(R) is the usual n-by-n identity matrix: 1’s on the diagonal and 0’s everywhere else (where by ‘1’ and ‘0’, we mean those elements of R). So for n = 4 it is:

2. We choose n = 2 and hence need to find two elements A, B \(\in\) Mat\(_{2}\)(\(\mathbb{N}\)) such that A ∗ B \(\neq\) B ∗ A.

One can calculate from the multiplication formula (recalled in Example 5.40) says (A ∗ B)(1, 1) = 0 ∗ 0 + 1 ∗ 1 = 1 and (B ∗ A)(1, 1) = 0 ∗ 0 + 0 ∗ 0 = 0, which are not equal.

Exercise 5.43

Semantically, if we apply the flow graph below to the input signal (x, y)

the resulting output signal is (16x + 4y, x + 4y).

Exercise 5.51

The monoidal product of A = \(\begin{pmatrix} 3 & 3 & 1 \\ 2 & 0 & 4 \end{pmatrix}\) and B = \(\begin{pmatrix} 2 & 5 & 6 & 1\end{pmatrix}\) is

A + B = \(\begin{pmatrix} 3 & 3 &1 & 0 & 0 & 0 & 0 \\ 2 & 0 & 4 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 2 & 5 & 6 & 1 \end{pmatrix}\)

Exercise 5.55

1. The signal flow graph on the left represents the matrix on the right:

2. The signal flow graph on the left represents the matrix on the right:

3. They are equal.

Exercise 5.58

1.

2.

3.

Exercise 5.59

• For the first layer g\(_{1}\), take the monoidal product of m copies of c\(_{n}\),

g\(_{1}\) := c\(_{n}\) + · · · + c\(_{n}\) : m → (m × n),

where c\(_{n}\) is the signal flow diagram that makes n copies of a single input:

c\(_{n}\) := ; (1+ ) ; (1 + 1+ ) ; ··· ; (1 + ··· + 1 + ) : 1 → n

• Next, define

g\(_{2}\) := s\(_{M(1,1)}\) + ··· + s\(_{M(1,n)}\)

+ s\(_{M(2,1)}\) + · · · + s\(_{M(2,n)}\)

+ ···

+ s\(_{M(m,1)}\) + · · · + s\(_{M(m,n)}\) : (m × n) → (m × n),

where s\(_{a}\) : 1 → 1 is the signal flow graph generator “scalar multiplication by a.” This layer amplifies each copy of the input signal by the relevant rig element.

• The third layer rearranges wires. We will not write this down explicitly, but simply say it is the signal flow graph g\(_{3}\) : m × n → m × n, that is the composite and monoidal product of swap and identity maps, such that the (i − 1)m + j th input is sent to the (j − 1)n + i th output, for all 1 ≤ i ≤ n and 1 ≤ j ≤ m.
• Finally, the fourth layer is similar to the first, but instead adds the amplified input signals. We define

g\(_{4}\) := a\(_{m}\) + · · · + a\(_{m}\) : (m × n) → n,

• where a\(_{m}\) is the signal flow graph that adds m inputs to produce a single output:

a\(_{m}\) := (1 + ··· + 1 + ) ; ··· ; (1 + 1 + ) ; (1 + ) ; :m→1

Using Proposition 5.54, it is a straightforward but tedious calculation to show that g = g\(_{1}\) ; g\(_{2}\) ; g\(_{3}\) ; g\(_{4}\) : m → n has the property that S(g) = M

Exercise 5.62

1. The matrices in Exercise 5.58 may also be drawn as the following signal flow graphs:

2. Here are graphical proofs that there presentations we chose in our solution to Exercise 5.58 agree with those chosen in Part 1 above.

Exercise 5.63

1. The signal flow graphs

cannot represent the same morphism because one has a path from a vertex on the left to one on the right, and the other does not. To prove this, observe that the only graphical equation in Theorem 5.60 that breaks a path from left to right is the equation

So a 0 scalar must within a path from left to right before we could rewrite the diagram to break that path. No such 0 scalar can appear, however, because the diagram does not contain any, and the sum and product of any two nonzero natural numbers is always nonzero.

2. Replacing each of the 3s with 0 allows us to rewrite the diagram to

Exercise 5.67

The three conditions of Definition 5.65 are

(a) (μ ⊗ id) ; μ = (id ⊗ μ) ; μ,

(b) (η ⊗ id) ; μ = id = (id ⊗ η) ; μ, and

(c) σ\(_{M,M}\) ; μ = μ.

where σ\(_{M,M}\) is the swap map on M in C.
1. Suppose μ : \(mathbb{R}\) × \(mathbb{R}\) → \(mathbb{R}\) is defined by μ(a, b) = a ∗ b and η \(\in\) \(mathbb{R}\) is defined to be η = 1. The conditions, written diagrammatically, say that starting in the upper left of each diagram below, the result in the lower right is the same regardless of which path you take:

and this is true for (\(mathbb{R}\), *, 1).

2. The same reasoning works for (\(mathbb{R}\), +, 0), shown below:

Exercise 5.69

The functor U: Mat(R) → Set is given on objects by sending n to the set R\(^{n}\), and on morphisms by matrix-vector multiplication. Here R\(^{n}\) means the set of n-tuples or n-dimensional vectors in R. In particular, R\(^{0}\) = {()} consists of a single vector of dimension 0.

1. U preserves the monoidal unit because 0 is the monoidal unit of any prop (Mat(R) is a prop), {1} is the monoidal unit of Set, and R\(^{0}\) is canonically isomorphic to {1}. U also preserves the monoidal product because there is a canonical isomorphism R\(^{m}\) × R\(^{n}\) \(\cong\) R\(^{m + n}\).

2. A monoid object in Mat(R) is a tuple (m, μ, η) where m \(\in\) \(\mathbb{N}\), μ : m + m → m, and η : 0 → m satisfy the properties μ(η, x) = x = μ(x, η) and μ(x, μ(y, z)) = μ(μ(x, y), z). Note that there is only one morphism 0 → m in Mat(R) for any m. It is not hard to show that for any m \(\in\) N there is only one monoid structure. For example, when m = 2, μ must be the following matrix

Anyway, for any monoid (m, μ, η), the morphism U(η): R\(^{0}\) → R\(^{m}\) is given by U(η)(1) := (0, . . . , 0), and the morphism U(μ): R\(^{m}\) × R\(^{m}\) → R\(^{m}\) is given by

U(μ)((a\(_{1}\), . . . , a\(_{m}\)), (b\(_{1}\), . . . , b\(_{m}\))) := (a\(_{1}\) + b\(_{1}\), . . . , a\(_{m}\) + b\(_{m}\)).

These give R\(^{m}\) the structure of a monoid.

3. The triple (1, , o-) corresponds to the additive monoid structure on \(\mathbb{R}\), e.g. with (5, 3) \(\mapsto\) 8.

Exercise 5.77

1. The behavior B() of the reversed addition icon : 1 →2 is the relation {(x, y, z) \(\in\) R\(^{3}\) | x = y + z}.

2. The behavior B() of the reversed addition icon : 1 →2 is the relation {(x, y, z) \(\in\) R\(^{3}\) | x = y + z}.

Exercise 5.80

If B \(\subseteq\) R\(^{m}\) ×R\(^{n}\) andC \(\subseteq\) R\(^{p}\) ×R\(^{q}\) are morphisms in Rel R, then take B + C \(\subseteq\) R\(^{m + p}\) ×R\(^{n + q}\) to be the set

B + C := {(w, y, x, z) \(\in\) R\(^{m + p}\) × R\(^{n + q}\) | (w, x) \(\in\) B and (y, z) \(\in\) C}.

Exercise 5.82

The behavior of g : m → n and h\(^{op}\) : n → l are respectively

B(g) = {(x, z) \(\in\) R\(^{m}\) × R\(^{n}\) | S(g)(x) = z}

B(h\(^{op}\)) = {(z, y) \(\in\) R\(^{n}\) × R\(^{l}\) | z = S(h)(y)}

and by Eq. (5.78), the composite B(g ; (h\(^{op}\))) = B(g) ; B(h\(^{op}\)) is:

{(x, y) | there exists z \(\in\) R\(^{n}\) such that S(g)(x) = z and z = S(h)(y)}.

Since S(g) and S(h) are functions, the above immediately reduces to the desired formula:

B(g ; (h\(^{op}\))) = {(x, y) | S(g)(x) = S(h)(y)}.

Exercise 5.83

The behavior of g\(^{op}\) : n → m and h : m → p are respectively

B(g\(^{op}\)) = {(y, x) \(\in\) R\(^{n}\) × R\(^{m}\) | y = S(g)(x)}

B(h) = {(x, z) \(\in\) R\(^{m}\) × R\(^{p}\) | S(h)(x) = z}

and by Eq. (5.78), the composite B(g\(^{op}\)) ; h) = B(g\(^{op}\)) ; B(h) is:

{(y, z) | there exists x \(\in\) R\(^{m}\) such that y = S(g)(x) and S(h)(x) = z}.

This immediately reduces to the desired formula:

B(g\(^{op}\)) ; h) = {(S(g)(x), S(h)(x)) | x \(\in\) R\(^{m}\) }.

Exercise 5.84

1. The behavior of the 0-reverse is the subset {y \(\in\) R | y = 0}, and its n-fold tensor is similarly {y \(\in\) R\(^{n}\) | y = 0}.

Composing this relation with S(g) \(\subseteq\) R\(^{m}\) × R\(^{n}\) gives {x \(\in\) R\(^{m}\) | S(g) = 0}, which is the kernel of S(g).

2. The behavior of the discard-inverse -o is the subset {x \(\in\) R}, i.e. the largest subset of R, and similarly its m-fold tensor is R\(^{n}\) \(\subseteq\) R\(^{n}\).

Composing this relation with S(g) \(\subseteq\) R\(^{m}\) × R\(^{n}\) gives {y \(\in\) R\(^{n}\) | there exists x \(\in\) R\(^{m}\) such that S(g)(x) = y}, which is exactly the image of S(g).

3. For any g : m → n, we first claim that the behavior B(g) = {(x, y) | S(g)(x) = y} is linear, i.e. it is closed under addition and scalar multiplication. Indeed, S(g) is multiplication by a matrix, so if S(g)(x) = y then S(g)(rx) = ry and S(g)(x\(_{1}\) + x\(_{2}\)) = S(g)(x\(_{1}\)) + S(g)(x\(_{2}\)).

Thus we con- clude that (x, y) \(\in\) B(g) implies (rx, ry) \(\in\) B(g), so it’s closed under scalar multiplication, and (x\(_{1}\), y\(_{1}\)), (x\(_{2}\), y\(_{2}\)) \(\in\) B(g) implies (x\(_{1}\) + x\(_{2}\), y\(_{1}\) + y\(_{2}\)) \(\in\) B(g) so it’s closed under addition. Similarly, the behavior B(g\(^{op}\)) is also linear; the proof is similar.

Finally, we need to show that the composite of any two linear relations is linear. Suppose that B \(\subseteq\) R\(^{m}\) × R\(^{n}\) and C \(\subseteq\) R\(^{n}\) × R\(^{p}\) are linear. Take (x\(_{1}\), z\(_{1}\)), (x\(_{2}\), z\(_{2}\)) \(\in\) B ; C and take r \(\in\) R.

By definition, there exist y\(_{1}\), y\(_{2}\) \(\in\) R\(^{n}\) such that (x\(_{1}\), y\(_{1}\)), (x\(_{2}\), y\(_{2}\)) \(\in\) B and (y\(_{1}\), z\(_{1}\)), (y\(_{2}\), z\(_{2}\)) \(\in\) C. Since B and C are linear, (rx\(_{1}\), ry\(_{1}\)) \(\in\) B and (ry\(_{1}\), rz\(_{1}\)) \(\in\) C, and also (x\(_{1}\) + x\(_{2}\), y\(_{1}\) + y\(_{2}\)) \(\in\) B and (y\(_{1}\) + y\(_{2}\), z\(_{1}\) + z\(_{2}\)) \(\in\) C.

Hence (rx\(_{1}\), rz\(_{1}\)) \(\in\) (B ; C) and (x\(_{1}\) + x\(_{2}\), z\(_{1}\) + z\(_{2}\)) \(\in\) (B ; C), as desired.

Exercise 5.85

Suppose that B \(\subseteq\) R\(^{m}\) × R\(^{n}\) and C \(\subseteq\) R\(^{n}\) × R\(^{p}\) are linear. Their composite is the relation (B ; C) \(\subseteq\) R\(^{m}\) × R\(^{p}\) consisting of all (x, z) for which there exists y \(\in\) R\(^{n}\) with (x, y) \(\in\) B and (y, z) \(\in\) C. We want to show that the set (B ; C) is linear, i.e. closed under scalar multiplication and addition.
For scalar multiplication, take an (x, z) \(\in\) (B ; C) and any r \(\in\) R.

Since B is linear, we have (r ∗ x, r ∗ y) \(\in\) B and since C is linear we have (r ∗ y, r ∗ z) \(\in\) C,so then (r ∗ x, r ∗ z) \(\in\) (B ; C). For addition, if we also have (x′, z′) \(\in\) (B ; C) then there is some y′ \(\in\) Rn with(x′,y′) \(\in\) B and(y′,z′) \(\in\) C, so since B and C are linear we have (x + x′, y + y′) \(\in\) B and (y + y′, z + z′) \(\in\) C, hence (x + x′, z + z′) \(\in\) (B ; C).