8.5: Рішення для глави 5

Last updated
Save as PDF

Page ID: 66325

$ \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } $ $ \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} $$\newcommand{\id}{\mathrm{id}}$ $ \newcommand{\Span}{\mathrm{span}}$ $ \newcommand{\kernel}{\mathrm{null}\,}$ $ \newcommand{\range}{\mathrm{range}\,}$ $ \newcommand{\RealPart}{\mathrm{Re}}$ $ \newcommand{\ImaginaryPart}{\mathrm{Im}}$ $ \newcommand{\Argument}{\mathrm{Arg}}$ $ \newcommand{\norm}[1]{\| #1 \|}$ $ \newcommand{\inner}[2]{\langle #1, #2 \rangle}$ $ \newcommand{\Span}{\mathrm{span}}$ $\newcommand{\id}{\mathrm{id}}$ $ \newcommand{\Span}{\mathrm{span}}$ $ \newcommand{\kernel}{\mathrm{null}\,}$ $ \newcommand{\range}{\mathrm{range}\,}$ $ \newcommand{\RealPart}{\mathrm{Re}}$ $ \newcommand{\ImaginaryPart}{\mathrm{Im}}$ $ \newcommand{\Argument}{\mathrm{Arg}}$ $ \newcommand{\norm}[1]{\| #1 \|}$ $ \newcommand{\inner}[2]{\langle #1, #2 \rangle}$ $ \newcommand{\Span}{\mathrm{span}}$

Вправа 5.5

1. Нижче ми намалюємо морфізм f: 3 → 2 і морфізм g: 2 → 4 в FinSet:

$Знімок екрана 2021-02-09 о 2.45.51 PM.png$

2. Ось картинка f + g

$Знімок екрана 2021-02-09 о 2.46.31 PM.png$

Складом морфізмів f: m → n та g: n → p у FinSet є функція (f; g): m → p задана (f; g) (i) = g (f (i)) для всіх 1 ≤ i ≤ m.
Ідентифікатор$_{m}$: m → m задається ідентифікатором$_{m}$ (i) = i для всіх 1 ≤ i ≤ m. Ось картинка id$_{2}$ та id$_{8}$:

$Знімок екрана 2021-02-09 о 2.47.12 PM.png$

5. Ось картина симетрії σ$_{3,5}$: 8 → 8:

$Знімок екрана 2021-02-09 о 2.47.40 PM.png$

Вправа 5.9

Потрібно навести приклади posetal props, тобто кожен буде poset, набір об'єктів якого дорівнює N, порядок якого позначається m$\leq$ n, а з властивістю

що всякий раз, коли м$_{1}$$\leq$$_{2}$$\leq$ н$_{1}$ і м н$_{2}$ утримувати, то m$_{1}$ + m$_{2}$$\leq$ n$_{1}$ + n$_{2}$ робить теж.

Питання задає лише три, але ми додатково наведемо квазі-приклад і неприклад.

1. Прийняти$\leq$ до дискретного порядку: m$\leq$ n iff m = n.

2. Візьміть,$\leq$ щоб бути звичайним порядком, m$\leq$ n, якщо існує d$\in$ N з d + m = n.

3. Візьмемо,$\leq$ щоб бути там вірш звичайного порядку, m$\leq$ n, якщо існує d$\in$ N з m = n + d.

4. $\leq$Прийняти співдискретний порядок m $\leq$n для всіх m, n. Деякі можуть заперечити, що це попередній порядок, а не poset, тому ми називаємо це квазі-прикладом.

5. (Не-приклад.) Прийняти$\leq$ до порядку ділення, m$\leq$ n, якщо існує q$\in$ N з m ∗ q = d. Це абсолютно хороший пост, але він не задовольняє властивість монотонності: у нас 2$\leq$ 4 і 3$\leq$ 3, але не 5$\leq$$^{?}$ 7.

Вправа 5.10

Приклад 5.6: Проп Bij має

1. Бідж (m, n) := {f:$\underline{m}$ →$\underline{n}$ | f - це біекція}. Зверніть увагу, що Bij (m, n) = Ø якщо m$\neq$ n і він має n! елементи, якщо m = n.

2. Карта ідентичності n → n - це біекція$\underline{n}$ →$\underline{n}$ відправка i → i.

3. Карта симетрії m +$\underline{n}$ →$\underline{n}$ + m - це біекція σ$_{m, n}$:$\underline{m + n}$ →,$\underline{n + m}$ задана

$Знімок екрана 2021-02-09 о 6.30.10 PM.png$

4. Склад бієкцій m → n і n → p - це лише їх склад як функції, який знову є біекцією.

5. Задані бі'єкції f: m → m ′ і g: n → n ′, їх моноїдальний добуток (f + g): (m + n) → (m ′ + n ′) задається шляхом

$Знімок екрана 2021-02-09 о 6.31.57 PM.png$

Приклад 5.7: Проп Corel має

Corel (m, n) - множина співвідношень еквівалентності на m + n.
Карта ідентичності n → n є найменшим співвідношенням еквівалентності, яке є найменшим рефлексивним відношенням, тобто де i j iff i = j.
Карта симетрії σ m, n, як відношення еквівалентності на m + n + n + m є «очевидною річчю», а саме «прирівнюючи відповідні m разом, а також прирівнюючи відповідні n разом». Щоб бути педантичним, я j, якщо або

• | i − j | = m + n + n, або

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

4. Склад співвідношення еквівалентності on$\underline{m + n}$ та співвідношення еквівалентності$\underline{n + p}$

відношення еквівалентності на$\underline{m + p}$ заданому i k, якщо існує j$\in$ n з i j і j ‰ k.

5. З огляду на співвідношення еквівалентності ‰ на$\underline{m + n}$ і ′on$\underline{m' + n'}$, нам потрібно співвідношення еквівалентності (+ ′) на$\underline{m + n + m' + n'}$. Ми вважаємо, що це «очевидна річ», а саме «використання» на негрунтованому матеріалі та використання «на грунтованому матеріалі, без іншої взаємодії». Щоб бути педантичним, я j, якщо або

• i ≤ m + n і j ≤ m + n і i j, або

• m + n + 1 ≤ i i m + n + 1 ≤ j і i ′ j.

Приклад 5.8: Проп Rel має

Rel (m, n) - множина відносин на множині$\underline{m}$ ×$\underline{n}$, тобто множина підмножин$\underline{m}$ ×$\underline{n}$, тобто його потужність
Карта ідентичності n → n є підмножиною {(i, j)$\in$$\underline{n}$ ×$\underline{n}$ | i = j}.
Карта симетрії m + n → n + m є підмножиною пар (i, j)$\in$ ($\underline{m + n}$) × ($\underline{n + m}$) така, що

• i ≤ m і m + 1 ≤ j і i + m = j, або

• m + 1 ≤ i і j ≤ m і j + м = i.

4. Склад відносин гріх Приклад 5.8.

5. З огляду на відношення R$\subseteq$$\underline{m}$ ×$\underline{n}$ і відношення R ′$\subseteq$$\underline{m}$ ′ ×$\underline{n}$ ′, нам потрібно відношення (R + R ′)$\subseteq$$\underline{m + m' x n + n'}$. Як зазначено в прикладі (виноска), це може бути дано універсальним властивістю: Моноїдальний $_{1}$добуток R + R$_{2}$ відносин R$_{1}$$\subseteq$ m$_{1}$ × n$_{1}$ і R$_{2}$ $\subseteq$$\underline{m_{2}}$×$\underline{n_{2}}$ задається $_{1}$R 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}}$.

Вправа 5.16

Композиція (m, n) -портового графа G і (n, p) -портового графа H виглядає візуально як приклеювання їх кінець до кінця, з'єднання проводів по порядку, видалення двох зовнішніх коробок і додавання нової зовнішньої коробки. Наприклад, припустимо, що ми хочемо скласти наступне у порядку, показаному:

$Знімок екрана 2021-02-09 о 6.52.53 PM.png$

Результатом є:

$Знімок екрана 2021-02-09 о 6.53.23 PM.png$

Вправа 5.18

Моноїдальний добуток двох морфізмів малюється шляхом укладання відповідних портових графіків. Для цієї проблеми ми просто складаємо ліву картинку поверх себе, щоб отримати зображення праворуч:

$Знімок екрана 2021-02-09 о 7.03.41 PM.png$

Вправа 5.20

У нас є відношення R$\subseteq$ P × P, яке генерує попереднє замовлення ≤$_{P}$ на P, ми маємо довільне попереднє замовлення (Q, ≤$_{Q}$) та функцію f: P → Q, не обов'язково монотонну.

Припустимо, що для кожного x, y$\in$ P, якщо R (x, y) то f (x) ≤ f (y); ми хочемо показати, що f є монотонним, тобто що для кожного х ≤$_{P}$ у нас є f (x) ≤$_{Q}$ f (y). За визначенням P, що є рефлексивним, перехідним замиканням R, ми маємо x ≤$_{P}$ y, якщо$_{n}$ в P існує n$\in$$\mathbb{N}$ та x$_{0}$,..., x з x$_{0}$ = x і x$_{n}$ = y та R (x$_{i}$, x$_{i + 1}$) для кожного 0 ≤ i ≤ n − 1. (Справа n = 0 обробляє рефлексивність.) Але тоді, за припущенням, R (x$_{i}$, x$_{i + 1}$) має на увазі f (x$_{i}$) ≤$_{Q}$ f (x$_{i + 1}$) для кожного i. За допомогою індукції на i ми показуємо, що $_{Q}$f (x$_{0}$) ≤ f (x$_{i}$) для всіх 0 ≤ i ≤ n, в якій точці ми закінчили.
Припустимо тепер, що f є монотонним, і візьміть x, y$\in$ P, для яких R (x, y) тримає. Тоді x ≤$_{P}$ y, оскільки ≤$_{P}$ є найменшим співвідношенням попереднього порядку, що містить R. (Інший спосіб побачити це на основі наведеного вище опису - з n = 1, x$_{0}$ = x та x$_{n}$ = y, що ми говорили, означає x ≤$_{P}$ y.) Оскільки f є монотонним, у нас дійсно є f (x) ≤$_{Q}$ f (y).

Вправа 5.21

Припустимо, що P, Q і R є такими, як у вправі 5.20 і ми маємо функцію g: Q → P.

Якщо R (g (a), g (b)) тримає для всіх a ≤$_{Q}$ b, то g є монотонним, оскільки R (x, y) означає x ≤$_{P}$ y.
Можливо, що g: (Q, ≤$_{Q}$) → (P, ≤$_{P}$) бути монотонним і мати деякі a, b$\in$ Q з a ≤$_{Q}$ b і (g (a), г (б))$\not \in$ Р. Дійсно, візьміть Q: = {1}, щоб бути вільним попереднім порядком на одному елементі, і візьміть P: = {1} з R = Ø. Тоді унікальна функція g: Q → P є монотонною (тому що ≤$_{P}$ є рефлексивною, навіть якщо R порожній), а ще (g (1), g (1))$\not \in$ R.

Вправа 5.23

Нехай G = (V, A, s, t) - граф, нехай G - вільна категорія на G, а нехай C - інша категорія, чий набір морфізмів позначається Мор (С).

1. Щоб дати функцію Mor (C) → Ob (C) означає, що для кожного елемента Mor (C) нам потрібно дати рівно один елемент Ob (C). Отже, для dom ми беремо будь-який q$\in$ Mor (C), розглядаємо його як морфізм q: y → z, і відправляємо його до свого домену y. Аналогічно для тріски: ставимо cod (q) := z.

2. Припустимо спочатку, що нам дано функтор F: G → C. На об'єктах у нас є функція Ob (G) → Ob (C), і це визначає f, оскільки Ob (G) = V. На морфізмах спочатку зауважте, що стрілки графа G - це саме довжина = 1 шляхи в G, тоді як Mor (G) - це набір всіх шляхів у G, тому ми маємо включення A$\subseteq$ Mor (G). Функтор F надає функцію Mor (G) → Mor (C), яку ми можемо обмежити A для отримання g: A → Mor (C). Усі функтори задовольняють dom (F (r)) = F (dom (r)) і код (F (r)) = F (код (r)) для будь-якого r: w → x. Зокрема, коли r$\in$ A є стрілкою, ми маємо dom (r) = s (r) і код (r) = t (r).

Таким чином ми знайшли (f, g) з необхідними властивостями.

Припустимо, по-друге, нам дано пару функцій (f, g) де f: V → Ob (C) і g: A → Mor (C) такі, що dom (g (a)) = f (s (a)) і код (g ( а)) = f (t (a)) для всіх $\in$А. Визначити F: G → C на об'єктах по f. Довільний морфізм в G - це шлях p: = (v$_{0}$, a$_{1}$, a$_{2}$,..., a$_{n}$) в G, де v$_{0}$$\in$ V, a$_{i}$ $\in$A, v$_{0}$ = s (a$_{1}$) і t (a$_{i}$) = s (a$_{i + 1}$) для всіх 1 ≤ i ≤ n − 1. Тоді (a$_{i}$) - це морфізм у C, область якого дорівнює f (v$_{0}$), а морфізми (a$_{i}$) та (a$_{i + 1}$) компонуються для кожного 1 ≤ i ≤ n − 1. Потім ми приймаємо F (p) := id$_{f(v0)}$; g (a$_{1}$); · · · ·; g (a$_{n}$) бути складовим. Легко перевірити, що це дійсно функтор (зберігає ідентичності та композиції).

По-третє, ми хочемо бачити, що дві операції, які ми тільки що дали, взаємно обернені. На об'єктах це просто, а на морфізмах можна просто побачити, що, задано (f, g), якщо ми перетворимо їх у функтор F: G → C і потім витягуємо нову пару функцій (f ′, g ′), то f = f ′і г = г'. Нарешті, задавши функтор F: G → C, ми витягуємо пару функцій (f, g), як зазначено вище, а потім перетворюємо їх у новий функтор F ′: G → C. Зрозуміло, що F і F ′ діють однаково на об'єктах, так як щодо морфізмів. Формула говорить, що F ′ діє однаково на морфізми довжини 1 в G (тобто на елементи A). Але довільний морфізм в G - це всього лише шлях, тобто послідовність компонуваних стрілок, і так по функціональності, як F, так і F ′ повинні діяти однаково на довільних шляхах.

3. (Мор (C), Ob (C), dom, cod) - це графік; давайте позначимо його U (C)$\in$ Graph. У нас є функтори Free: Grph$\rightleftharpoons$ Cat: U, а Free залишається прилеглим до U.

Вправа 5.24

1. Елементами вільного моноїда на множині {a} є:

а$^{0}$, а$^{1}$, а$^{2}$, а$^{3}$,..., а$^{2019}$,...

з моноїдним множенням ∗, задане звичайним додаванням натурального числа на експоненти,$^{i}$ a∗ a$^{j}$ = a$^{i + j}$.

2. Це ізоморфний до$\mathbb{N}$, надіславши$^{i}$ $\mapsto$i.

3. Елементи вільного моноїда на множині {a, b} - це «слова в a та b», кожне з яких ми представлятимемо як список, записи якого є або a, або b. Ось деякі з них:

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

Вправа 5.28

У нас є два реквізити: реквізит портових графіків і вільний реквізит Free (G, s, t) де

G: = {ρ$_{m, n}$: м → n | м, п$\in$$\mathbb{N}$}, s (ρ$_{m, n}$ := м, т (ρ$_{m, n}$ := п;

ми хочемо показати, що вони є одним і тим же опором. Як категорії вони мають однаковий набір об'єктів (в обох випадках

N), тому нам потрібно показати, що для кожного m$\in$$\mathbb{N}$, n вони мають однаковий набір морфізмів (і що їх формули складу та формули моноїдального добутку узгоджуються).

За визначенням 5.25 морфізм m → n у вільному (G) - це портовий граф з міткою G, тобто пара (γ, l), де γ = (V, in, out) - граф (m, n) -порт і l: V → G - це функція, така, що «раритети згодні». Що це означає? Нагадаємо, що кожна вершина v$\in$ V малюється у вигляді коробки з деякими лівими портами, а деякі праві порти arity і l (v)$\in$ G повинні мати правильну рідність; точно, s (l (v)) = in ( v) і t (л (v)) = поза (v). Але G був обраний так, щоб він мав рівно один елемент з будь-якою заданою рідністю, тому функція l має тільки один вибір, і при цьому нічого не сприяє: вона ні збільшує, ні зменшує свободу. Іншими словами, морфізм у нашому конкретному вільному (G) може бути ідентифікований за допомогою (m, n) портового графа γ, за бажанням.

Знову ж таки, за визначенням визначення 5.25, «склад та моноїдальна структура - це лише ті, що для портових графіків PG (див. Eq. (5.17)); маркування (l) просто переносяться разом». Ось ми і зробили.

Вправа 5.32

Ось картинка (f + id$_{1}$ + id$_{1}$); (σ + id$_{1}$); (id$_{1}$ + h); σ; g, у вільному пропі на генераторах G = {f: 1 → 1, g: 2 → 2, h: 2 → 1}:

$Знімок екрана 2021-02-09 о 9.01.08 PM.png$

Вправа 5.35

Вільний проп на генераторах (G, s, t), визначений у Визначенні 5.25, для всіх намірів і цілей є тим самим, що і проп, представлений (G, s, t, Ø), не маючи відносин. Єдина можлива «тонка різниця», яку ми, можливо, повинні визнати, це якщо хтось сказав, що набір S «тонко відрізняється», ніж його частка за тривіальним співвідношенням еквівалентності. В останньому елементами є одноелементні підмножини S. Так, наприклад, частка S = {1, 2, 3} за тривіальним співвідношенням еквівалентності є множина ({1}, {2}, {3}). Це тонко відрізняється від S, але вони, природно, ізоморфні, і категорія-теоретично, різниця ніколи не матиме значення.

Вправа 5.41

1. Якщо (R, 0, +, 1, ∗) є ригом, то мультиплікативна ідентичність 1$\in$ Mat$_{n}$ (R) є звичайною матрицею ідентичності n -by- n: 1 на діагоналі та 0 скрізь (де під '1' і '0' ми маємо на увазі ці елементи R). Отже, для n = 4 це:

$Знімок екрана 2021-02-09 о 9.18.44 PM.png$

2. Вибираємо n = 2 і, отже, потрібно знайти два елементи A, B$\in$ Mat$_{2}$ ($\mathbb{N}$) такі, що A ∗ $\neq$B B∗ A.

$Знімок екрана 2021-02-09 о 9.19.19 PM.png$

Можна обчислити за формулою множення (згадується в прикладі 5.40) говорить (A ∗ B) (1, 1) = 0 ∗ 0 + 1 ∗ 1 = 1 і (B ∗ A) (1, 1) = 0 ∗ 0 + 0 ∗ 0 = 0, які не рівні.

Вправа 5.43

Семантично, якщо застосувати графік потоку нижче до вхідного сигналу (x, y)

$Знімок екрана 2021-02-09 о 9.32.25 PM.png$

отриманий вихідний сигнал дорівнює (16 х + 4 у, х + 4 у).

Вправа 5.51

Моноїдальний добуток A =$\begin{pmatrix} 3 & 3 & 1 \\ 2 & 0 & 4 \end{pmatrix}$ і B =$\begin{pmatrix} 2 & 5 & 6 & 1\end{pmatrix}$ дорівнює

А + Б =$\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}$

Вправа 5.55

1. Графік потоку сигналу зліва представляє матрицю праворуч:

$Знімок екрана 2021-02-09 в 9.39.38 PM.png$

2. Графік потоку сигналу зліва представляє матрицю праворуч:

$Знімок екрана 2021-02-09 о 9.41.20 PM.png$

3. Вони рівні.

Вправа 5.58

1. $Знімок екрана 2021-02-09 о 9.46.12 PM.png$

2. $Знімок екрана 2021-02-09 о 9.46.55 PM.png$

3. $Знімок екрана 2021-02-09 о 9.49.57 PM.png$

Вправа 5.59

• Для першого шару г$_{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:

$Screen Shot 2021-02-09 at 10.00.56 PM.png$

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.

$Screen Shot 2021-02-09 at 10.42.50 PM.png$

Exercise 5.63

1. The signal flow graphs

$Screen Shot 2021-02-09 at 10.44.47 PM.png$

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

$Screen Shot 2021-02-09 at 10.45.12 PM.png$

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

$Screen Shot 2021-02-09 at 10.45.43 PM.png$

Exercise 5.67

The three conditions of Definition 5.65 are

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

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

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:

$Screen Shot 2021-02-09 at 10.53.17 PM.png$

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

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

$Screen Shot 2021-02-09 at 10.54.30 PM.png$

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

$Screen Shot 2021-02-10 at 10.58.58 PM.png$

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).