8.2: Рішення для глави 2
- Page ID
- 66336
Експерт має рацію! Пропозиція порушує властивість (a), коли x\(_{1}\) = −1, x\(_{2}\) = 0, y\(_{1}\) = −1, і y\(_{2}\) = 1.
Дійсно −1 ≤ −1 і 0 ≤ 1, але −1 ∗ 0 = 0\(\nleq\) −1 = −1 ∗ 1.
Щоб перевірити, що (Диск (M), =, ∗, e) є симетричним моноїдальним попереднім порядком, нам потрібно перевірити, що наші запропоновані дані відповідають умовам (a) - (d) Визначення 2.2. Умова (а) просто стверджує тавтологію\(_{1}\), що x x\(_{2}\) =\(_{1}\) x x\(_{2}\), умови (b) і (c) - це саме рівняння Eq. (2.7), і (d) - умова комутатності. Отже, ми закінчили. Ми залишаємо вам вирішити, чи говоримо ми правду, коли сказали, що це легко.
1. Ось рядок за рядком доказ, де ми пишемо причину кожного кроку в дужках праворуч.
Нагадаємо, ми називаємо властивості (a) і (c) у визначенні 2.2 монотонність і асоціативність відповідно.
t + u ≤ (v + w) + u (монотонність, t ≤ v + w, u ≤ u)
= v + (ш + u) (асоціативність)
≤ v + (x + z) (монотонність, v ≤ v, w + u ≤ х+ v)
= (v + х) + z (асоціативність)
≤ y + z. (монотонність, v + x ≤ y, z ≤ z)
- Ми використовуємо рефлексивність, коли ми стверджуємо, що u ≤ u, v ≤ v та z ≤ z, і використовуємо транзитивність, щоб стверджувати, що наведена вище послідовність нерівностей передбачає єдину нерівність t + u ≤ y + z .
- Ми знаємо, що аксіома симетрії не потрібна, оскільки жодна пара проводів не перетинається.
Умова (а), монотонність, говорить про те, що якщо x → y і z → w - реакції, то x + z → y + w - реакція. Умова (b), Unitality, тримає як 0 означає відсутність матеріалу, і додавання матеріалу до якогось іншого матеріалу не змінює його. Умова (c), асоціативність, говорить про те, що при об'єднанні трьох колекцій x, y та z молекул не має значення, чи поєднуєте ви x і y, а потім z, або поєднуєте x з y вже об'єднаними з z. Умова (d), симетрія, говорить про те, що об'єднання x з y є таким же, як об'єднання y з x. Все це вірно в нашій моделі хімії, тому (Mat, →, 0, +) утворює симетричний моноїдальний попередній порядок.
Моноїдальна одиниця повинна бути помилковою. Симетричний моноїдальний попередній порядок задовольняє іншим умовам; це можна перевірити, просто перевіривши всі випадки.
Моноїдальна одиниця - натуральне число 1. Оскільки ми знаємо, що (\(\mathbb{N}\), ≤) є попереднім порядком, нам просто потрібно перевірити, що ∗ є монотонним, асоціативним, одиничним з 1 та симетричним. Це всім знайомі факти з арифметики.
Ця пропозиція не монотонна: у нас є 1|1 і 1|2, а (1 + 1)\(\not |\) (1 + 2).
1.
2. Нам потрібно показати, що (a) якщо x ≤ y і z ≤ w, то min (x, z) ≤ min (y, w), (b) min (x, yes) = x = min (так, x), (c) min (min (x, y), z ) = хв (х, хв (у, з)), а (г) хв (х, у) = хв (у, з). Найпростіший спосіб - просто перевірити всі випадки.
Так, (P (S), ≤, S,) є симетричним моноїдальним попереднім порядком.
Залежно від вашого настрою, ви можете придумати будь-яке з наступного. По-перше, ми могли б взяти моноїдальну одиницю, щоб бути деяким твердженням істинним, що вірно для всіх натуральних чисел, таких як «n - натуральне число».
Ми можемо з'єднати цю одиницю з моноїдальним добутком\(\land\), який приймає твердження P і Q і робить твердження P\(\land\) Q, де (P\(\land\) Q) (n) істинно, якщо P (n) і Q (n) є істинними, а false інакше. Потім (Prop\(^{\mathbb{N}}\), ≤, true,\(\land\)) утворює симетричний моноїдальний попередній порядок.
Інший варіант - прийняти define false як деяке твердження, яке є помилковим для всіх натуральних чисел, таких як «n + 10 ≤ 1» або «n зроблено з сиру».
Ми також можемо визначити\(\lor\) таке, що (P\(\lor\) Q) (n) істинно тоді і тільки тоді, коли принаймні один з P (n) і Q (n) є істинним. Потім (Prop\(^{\mathbb{N}}\), ≤, false,\(\lor\)) утворює симетричний моноїдальний попередній порядок.
Унікальність і асоціативність не мають нічого спільного з порядком в X\(^{op}\): вони просто стверджують, що I х = х I, і (x y) z = x (y з). Оскільки вони вірні в X, вони вірні в X\(^{op}\). Симетрія трохи складніша, оскільки в запитує лише те, що x y еквівалентно y x. Тим не менш, це все ще вірно в X,\(^{op}\) тому що це вірно в X. Дійсно той факт, що\(\cong\) (х y) (y x) в X означає, що (х y) ≤ (y x) і (y x) ) ≤ (x y) в X, які відповідно означають, що (y x) ≤ (x y) і (x y) ≤ (y x) в X\(^{op}\), і, отже, що (x y) \(\cong\)(y x) в X\(^{op}\) теж.
1. Вартість попереднього замовлення\(^{op}\) має базовий набір [0, ∞], а звичайний порядок збільшення дійсних чисел ≤ як його порядок.
2. Його моноїдальна одиниця дорівнює 0.
3. Його моноїдальний продукт - +.
1. Карта g монотонна як g (false) = ∞ ≥ 0 = g (true), задовольняє умові (a), оскільки 0 ≥ 0 = g (true), і задовольняє умові (b), оскільки
2. Оскільки всі нерівності щодо (а) та (b) вище насправді є рівностями, g - суворий моноїдний монотон.
Відповідь на всі ці питання позитивна: d і u - це і суворі моноїдальні монотони. Ось один із способів інтерпретувати це. Функція d запитує 'є x '= 0?'. Це монотонно, 0 дорівнює 0, а сума двох елементів [0, ∞] дорівнює 0 тоді і тільки тоді, коли вони обидва 0. Функція u запитує «є x скінченним?». Аналогічно, це монотонно, 0 є кінцевим, а сума x і y є кінцевою, якщо і тільки тоді, коли x і y обидва кінцеві.
- Так, множення монотонне в ≤, одиничне по відношенню до 1, асоціативне та симетричне, тому (\(\mathbb{N}\), ≤, 1, ∗) є моноїдальним попереднім порядком. Ми також зустрілися з цим попереднім замовленням у вправі 2.31.
- Карта f (n) = 1 для всіх n\(\in\)\(\mathbb{N}\) визначає моноїдальний монотон f: (\(\mathbb{N}\), ≤, 0, +) → (\(\mathbb{N}\), ≤, 1, ∗). (Насправді вона унікальна! Чому?)
- (\(\mathbb{Z}\), ≤, ∗, 1) не є моноїдальним попереднім порядком, оскільки ∗ не є монотонним. Дійсно −1 ≤ 0, але (−1 ∗ −1)\(\nleq\) (0 ∗ 0).
- Нехай (P, ≤) є попереднім замовленням. Як це Bool -категорія? Наступний приклад 2.47, ми можемо побудувати Bool -категорію X\(_{P}\) з P як набір об'єктів, а з X\(_{P}\) (p, q) := true, якщо p ≤ q, і X\(_{P}\) (p, q) := false інакше. Як ми можемо перетворити це назад на попередній порядок? Після доведення теореми 2.49 ми будуємо попередній порядок з базовою множиною Ob (X\(_{P}\)) = P, і з p ≤ q якщо і тільки якщо X\(_{P}\) (p, q) = true. Це саме попереднє замовлення (P, ≤)!
- Нехай X бути Bool -категорія. Доказом теореми 2.49 ми будуємо попередній порядок (Ob (X), ≤), де x ≤ y якщо і тільки тоді, коли X (x, y) = true. Потім, після нашого узагальнення Прикладу 2.47 в 1., ми будуємо Bool -категорію X′, набір об'єктів якої є Ob (X), і такий, що X′ (x, y) = true якщо і тільки якщо x ≤ y в (Ob (X), ≤). Але за конструкцією це означає X′ (x, y) = X (x, y). Таким чином, ми повертаємося Bool -категорія ми почали з.
Відстань d (США, Іспанія) більше: відстань від, наприклад, Сан-Дієго до будь-якої Іспанії більше, ніж відстань від будь-якої точки Іспанії до Нью-Йорка.
Різниця між метричним простором Ловера, тобто категорією, збагаченою понад ([0, ∞], ≥, 0, +) та категорією, збагаченою понад (\(\mathbb{R}_{≥0}\), ≥, 0, +), полягає в тому, що в останньому нескінченні відстані не допускаються між точками. Таким чином, ви можете назвати останнє метричним простором Ловера на скінченну відстань.
Таблиця відстаней для Х дорівнює
Матриця реберних ваг X дорівнює
NMY -категорія X - це набір X разом з, для всіх пар елементів x, y в X, значенням X (x, y) рівним ні, можливо, або так. Крім того, ми повинні мати X (x, x) = так і min (X (x, y), X (y, z)) ≤ X (x, z) для всіх x, y, z. Таким чином, NMY -категорія може розглядатися як сукупність точок разом із заявою - ні, можливо, або так - про те, чи можна перейти від однієї точки до іншої. Зокрема, завжди можна дістатися до точки, якщо ви вже там, і це якомога менше, щоб отримати від x до z, як це, щоб отримати від x до y, а потім у до z.
Ось один із способів виконати це завдання.
1.
2. Відповідна М-категорія, її називають X, має hom-об'єкти:
Наприклад, для обчислення хом-об'єкта X (C, D) ми помічаємо, що існує два шляхи: C → A → B → D і C → D. Для першого шляху перетином є набір {boat}. Для другого шляху перехрестя в комплекті {foot, car}. Їх об'єднання, і, таким чином, хом-об'єкт X (C, D), - це весь набір M.
Це обчислення містить ключ для того, чому X є M-категорією: взявши об'єднання по всіх шляхах, ми гарантуємо, що X (x, y) X (y, z)\(\subseteq\) X (x, z) для всіх x, y, z.
3. Тлумачення людини виглядає нам правильно.
1.
2. Матриця M з (x, y)\(^{th}\) entry equal to the maximum, taken over all paths p from x to y, of the minimum edge label in p is
3. This is a matrix of hom-objects for a W-category since the diagonal values are all equal to the monoidal unit ∞, and because min(M(x, y), M(y, z)) ≤ M(x, y) for all x, y, z \(\in\) {A, B, C}.
4. One interpretation is as a weight limit (not to be confused with ‘weighted limit,’ a more advanced categorical notion), for example for trucking cargo between cities. The hom-object indexed by a pair of points (x, y) describes the maximum cargo weight allowed on that route. There is no weight limit on cargo that remains at some point x, so the hom-object from x to x is always infinite. The maximum weight that can be trucked from x to z is always at least the minimum of that that can be trucked from x to y and then y to z. (It is ‘at least’ this much because there may be some other, better route that does not pass through y.)
This preorder describes the ‘is a part of’ relation. That is, x ≤ y when d(x, y) = 0, which happens when x is a part of y. So Boston is a part of the US, and Spain is a part of Spain, but the US is not a part of Boston.
1. Recall the monoidal monotones d and u from Exercise 2.44. The function f is equal to d; let g be equal to u.
2. Let X be the Lawvere metric space with two objects A and B, such that d(A, B) = d(B, A) = 5. Then we have X\(_{f}\) = \(\begin{array}{l} A \\\bullet\end{array}\)\(\begin{array}{l} B \\\bullet\end{array}\) while X\(_{g}\) = \(\begin{array}{l} A \\\bullet\end{array}\)\(\begin{array}{l} B \\\bullet\end{array}\).
- An extended metric space is a Lawvere metric space that obeys in addition the properties (b) if d(x, y) = 0 then x = y, and (c) d(x, y) = d(y, x) of Definition 2.51. Let’s consider the dagger condition first. It says that the identity function to the opposite Cost-category is a functor, and so for all x, y we must have d(x, y) ≤ d(y, x). But this means also that d(y, x) ≤ d(x, y), and so d(x, y) = d(y, x). This is exactly property (c). Now let’s consider the skeletality condition. This says that if d(x, y) = 0 and d(y, x) = 0, then x = y. Thus when we have property (c), d(x, y) = d(y, x), this is equivalent to property (b). Thus skeletal dagger Cost-categories are the same as extended metric spaces!
- Recall from Exercise 1.73 that skeletal dagger preorders are sets. The analogy “preorders are to sets as Lawvere metric spaces are to extended metric spaces” is thus the observation that just as extended metric spaces are skeletal dagger Cost-categories, sets are skeletal dagger Bool- categories.
1. Let (x, y) \(\in\) X × Y. Since X and Y are V-categories, we have I ≤ X(x, x) and I ≤ Y(y, y). Thus I = I ⊗ I ≤ X(x, x) ⊗ Y(y, y) = (X × Y)((x, y), (x, y)).
2. Using the definition of product hom-objects, and the symmetry and monotonicity of ⊗ we have
(X × Y)((x\(_{1}\), y\(_{1}\)), (x\(_{2}\), y\(_{2}\))) ⊗ (X × Y)((x\(_{2}\), y\(_{2}\)), (x\(_{3}\), y\(_{3}\)))
= X(x\(_{1}\), x\(_{2}\)) ⊗ Y(y\(_{1}\), y\(_{2}\)) ⊗ X(x\(_{2}\), x\(_{3}\)) ⊗ Y(y\(_{2}\), y\(_{3}\))
= X(x\(_{1}\), x\(_{2}\)) ⊗ X(x\(_{2}\), x\(_{3}\)) ⊗ Y(y\(_{1}\), y\(_{2}\)) ⊗ Y(y\(_{2}\), y\(_{3}\))
≤ X(x\(_{1}\), x\(_{3}\)) ⊗ Y(y\(_{1}\), y\(_{3}\))
= (X × Y)((x\(_{1}\), y\(_{1}\)), (x\(_{3}\), y\(_{3}\))) .
3. In particular, we use the symmetry, to conclude that Y(y\(_{1}\), y\(_{2}\)) ⊗ X(x\(_{2}\), x\(_{3}\)) = X(x\(_{2}\), x\(_{3}\)) ⊗ Y(y\(_{1}\), y\(_{2}\)).
We just apply Definition 2.74(ii): (\(\mathbb{R}\) × \(\mathbb{R}\))((5, 6), (−1, 4)) = \(\mathbb{R}\)(5, −1) + \(\mathbb{R}\)(6, 4) = 6 + 2 = 8.
1. The function−⊗v :V → V is monotone, because if u ≤ u′ then u ⊗ v ≤ u′ ⊗ v by the monotonicity condition (a) in Definition 2.2.
2. Let a := (v -o w) in Eq.(2.80). The right hand side is thus (v -o w) ≤ (v -o w), which is true by reflexivity. Thus the left hand side is true too. This gives ((v -o w) ⊗ v) ≤ w.
3. Let u ≤ u′. Then, using 2., (v -o u) ⊗ v ≤ u ≤ u′. Applying Eq.(2.80), we thus have (v -o u) ≤ (v -o u′). This shows that the map (v -o −): V → V is monotone.
4. Eq.(2.80) is exactly the adjointness condition from Definition 1.95, except for the fact that we do not know (− ⊗ v) and (v -o −) are monotone maps. We proved this, however, in items 1 and 3 above.
We need to find the hom-element. This is given by implication. That is, define the function x ⇒ y by the table
Then (a \(\land\) v) ≤ w if and only if a ≤ (v ⇒ w). Indeed, if v = false then a \(\land\) false = false, and so the left hand side is always true.
But (false ⇒ w) = true, so the right hand side is always true too. If v = true, then a \(\land\) true = a so the left hand side says a ≤ w.
But (true ⇒ w) = w, so the right hand side is the same. Thus ⇒ defines a hom-element as per Eq. (2.80).
We showed in Exercise 2.84 that Bool is symmetric monoidal closed, and in Exercise 1.7 and Example 1.88 that the join is given by the OR operation \(\lor\). Thus Bool is a quantale.
Yes, the powerset monoidal preorder (P(S), \(\subseteq\), S, ∩) is a quantale. The hom-object B -o C is given by \(\bar{B}\) \(\bigcup\) C, where \(\bar{B}\) is the complement of B: it contains all elements of S not contained in B.
To see that this satisfies Eq. (2.80), note that if (A ∩ B) \(\subseteq\) C, then
A = (A ∩ \(\bar{B}\)) \(\bigcup\) (A ∩ B) \(\subseteq\) \(\bar{B}\) \(\bigcup\) C.
On the other hand, if A \(\subseteq\) (\(\bar{B}\) \(\bigcup\) C), then
A ∩ B \(\subseteq\) (\(\bar{B}\) \(\bigcup\) C) ∩ B (\(\bar{B}\) ∩ B) \(\bigcup\) (C ∩ B) = C ∩ B \(\subseteq\) C.
So (P(S), \(\subseteq\), S, ∩) is monoidal closed. Furthermore, joins are given by union of subobjects, so it is a quantale.
1a. In Bool, (\(\bigvee\) Ø) = false, the least element.
1b. In Cost, (\(\bigvee\) Ø) = ∞. This is because we use the opposite order ≥ on [0, ∞], so \(\bigvee\) Ø is the greatest element of [0, ∞]. Note that in this case our convention from Definition 2.90, where we denote (\(\bigvee\) Ø) = 0, is a bit confusing! Beware!
2a. In Bool, x (\lor\) y is the usual join, OR.
2b. In Cost, x (\lor\) y is the minimum min(x, y). Again because we use the opposite order on [0, ∞], the join is the greatest number less than or equal to x and y.
The 2 × 2-identity matrices for (\(\mathbb{N}\), ≤, 1, ∗), Bool, and Cost are respectively
1. We first use Proposition 2.87 (2) and symmetry to show that for all v \(\in\) V, 0 ⊗ v = 0.
0 ⊗ v \(\cong\) v ⊗ 0 \(\cong\) (v ⊗ \(\bigvee_{a \in Ø}\)a) = \(\bigvee_{a \in Ø}\)(v ⊗ a) = 0.
Then we may just follow the definition in Eq. (2.101):
\(\begin{aligned}
I_{X} * M(x, y) &=\bigvee_{x^{\prime} \in X} I_{X}\left(x, x^{\prime}\right) \otimes M\left(x^{\prime}, y\right) \\
&=\left(I_{X}(x, x) \otimes M(x, y)\right) \vee\left(\bigvee_{x^{\prime} \in X, x^{\prime} \neq x} I_{X}\left(x, x^{\prime}\right) \otimes M\left(x^{\prime}, y\right)\right) \\
&=(I \otimes M(x, y)) \vee\left(\bigvee_{x^{\prime} \in X, x^{\prime} \neq x} 0 \otimes M\left(x^{\prime}, y\right)\right) \\
&=M(x, y) \vee 0=M(x, y) .
\end{aligned}\)
2. This again follows from Proposition 2.87(2) and symmetry, making use also of the associativity of ⊗:
\(\begin{aligned}
((M * N) * P)(w, z) &=\bigvee_{y \in Y}\left(\bigvee_{x \in X} M(w, x) \otimes N(x, y)\right) \otimes P(y, z) \\
& \cong \bigvee_{y \in Y, x \in X} M(w, x) \otimes N(x, y) \otimes P(y, z) \\
& \cong \bigvee_{x \in X} M(w, x) \otimes\left(\bigvee_{y \in Y} N(x, y) \otimes P(y, z)\right) \\
&=(M *(N * P))(w, z)
\end{aligned}\)
We have the matrices