8.4: Рішення для глави 4
- Page ID
- 66349
1. Діаграма Хассе для Xop × Y показана тут (ігноруйте кольори):
2. Є профунктор\(\land\): X → Y, тобто функтор X\(^{op}\) × Y → B, такий, що на зображенні вище синій посилається в true, а чорний - в false, тобто
\(\land\)(моноїд, нічого) =\(\land\) (моноїд, ця книга)
=\(\land\) (попередній порядок, ця книга) =\(\land\) (категорія, ця книга) = правда
\(\land\)(попередній порядок, нічого) =\(\land\) (категорія, нічого) = брехня.
Попереднє замовлення X\(^{op}\) × Y описує завдання зі зменшенням складності. Наприклад, (ми сподіваємося) моїй тітці легше пояснити моноїд, даний цією книгою, ніж їй пояснити моноїд без цієї книги. Профунктор\(\land\) описує можливі стани знань для моєї тітки: вона може описувати моноїди без сторонньої допомоги, категорії за допомогою книги тощо Це верхній набір, тому що ми припускаємо, що якщо вона може виконати завдання, вона також може виконати будь-яке більш легке завдання.
Ми робили це раніше! Сподіваємося, ви згадали, як це зробити. Якщо ні, див. вправу 2.84.
Нагадаємо з визначення 2.41, що V-функтор Φ: X\(^{op}\) × Y → V - це функція Φ: Ob (X\(^{op}\) × Y) → Ob (V) така, що для всіх (x, y) та (x ′, y ′) у X\(^{op}\) × Y ми маємо
(X\(^{op}\) × Y) ((x, y), (x ', y')) ≤ V (Φ (x, y), Φ (x', y')).
Використовуючи визначення V-категорії продукту (визначення 2.74) та протилежної V-категорії (Вправа 2.73) на лівій стороні та використання Зауваження 2.89, яке описує, як ми розглядаємо кванту V як збагачену над собою, з правого боку, це розпаковує до
Х (х ′, х) Y (у, у ′) ≤ Φ (x, y) -o Φ (x ′, y ′)
Використовуючи симетрію та визначення хом-елемента, Eq. (2.80), ми бачимо, що Φ є профунктором тоді і тільки тоді, коли
X (x ′, x) Φ (x, y) Y (у, y ′) ≤ Φ (х ′, у ′).
Так, оскільки Bool -functor точно такий же, як монотонна карта, визначення Bool -profunctor та співвідношення доцільності ідеально!
Матриця доцільності для Φ дорівнює
Матриця витрат для Φ дорівнює
\ (\ почати {вирівняний}
\ Phi=M_ {X} ^ {3} * M_ {\ Phi} * M_ {Y} ^ {2} &=\ ліворуч (\ почати {масив} {cccc}
0 & 6 & 3 & 11\\
2 & 0 &
5\
5 & 3 & 0 & 0 & 0
\\ кінець {масив}\ праворуч)\ ліворуч (\ почати {масив} {ccc}
\ infty &\ infty &\ infty\\
1 &\ infty\\ infty\
\ infty &\ infty\\ infty\
\ infty & 9 &\ infty
\ кінець {масив}\ праворуч)\ лівий (\ почати {масив} {CCC}
0 & 4 & 3\\
3 & 0 & 6\\
7 & 4 & 0
\ кінець {масив}\ праворуч)\\
&=\ ліворуч (\ почати {масив} {ccc}
17 & 20 &\ infty\\
11 &\ infty\\ 14\\
14 &\ 17 &\ infty\\
20 & 9 &\ infty
\ кінець {масив}\ праворуч)\ лівий (\ begin {масив} {lll}
0 & 4\
3 & 0 & 6\\
7 & 4 & 0
\ end {масив}\ праворуч)\\
&=\ left (\ begin {масив} {ccc}
17 & 20\\
11 & 14\\
14 & 17 & 17\\
12 & 9 & 15
\ кінець {масив}\ праворуч)
\ кінець {вирівняний}\)
Так, це справедливо: це просто означає, що профунктор Φ: (T × E) → $ не відноситься (добродушний, смішний) до будь-якого елементу $. Більш формально це означає, що Φ (добродушний, смішний), р) = помилковий для всіх р\(\in\) $ = {$100K, $500K, $1M}. Ми можемо інтерпретувати це, щоб означати, що неможливо створити добродушний, смішний фільм для будь-якого з представлених варіантів витрат - так принаймні не менше ніж за мільйон доларів.
Існує ряд методів, за допомогою яких можна отримати правильну відповідь. Одним із способів, який добре працює для цього прикладу, є пошук найкоротших шляхів на схемі: так буває, що всі найкоротші шляхи проходять через мости від D до y і y до r, тому в даному випадку (Φ; ψ) (−, −) = X (−, D) + 9 + Z (r , −). Це дає:
Більш методичним способом є використання множення матриць. Ось один із способів ви можете зробити множення, використовуючи кілька хитрощів.
\ (\ почати {вирівняний}
\ Phi_ {9} ^ {\ circ}\ Psi &=\ ліворуч (M_ {X} ^ {3} * M_ {\ Phi} * M_ {Y} ^ {Y} * M_ {\ Psi} * M_ {Z} ^ {3}\ праворуч)\\
&=M_ {X} ^ {3} * M_ {\ Phi} * M_ {Y} ^ {4} * M_ {\ Psi} * M_ {Z} ^ {3}\
&=\ ліворуч (M_ {X} ^ {3} * M_ {\ Phi} * M_ {Y} ^ {2}\ праворуч) * M_ {\ Psi} * M_ {Z} ^ {3}\\
&=\ Phi* M_ {\ Psi} * M_ {Z} ^ {3}\
&=\ ліворуч (\ почати {масив} {lll}
17 & 20\\
11 & 14\\
14 & 17\\
12 & 9 & 15
\ кінець {масив}\ праворуч)\ лівий (\ початок { масив} {lll}
\ inty &\ infty &\ infty &\ infty\
\ infty &\ infty & 0 &\ infty\\
4 &\ infty &\ infty & 4
\ end {масив}\ вправо)\ лівий (\ почати {масив} {lll}
0 & 2 & 4 & 5\\
4 & підсилювач; 0 & 2\\
2 & 4 & 0 & 1\\
1 & 3 & 5 & 0
\ кінець {масив}\ праворуч)\\
&=\ ліворуч (\ почати {масив} {lll}
17 & 20\\
11 & 14\ 14\
14\ 14 & 17 \\
12 & 9 & 15
\ кінець {масив}\ праворуч)\ лівий (\ begin {масив} {llll}
\ infty &\ infty &\ infty\\ infty\\
2 & 0 & 1\\
4 & 6 & 8 & 4
\ end {масив}\ праворуч)\
\ лівий (\ почати {масив} {llll}
22 & 24 & 20 & 21\\
16 & 18 & 14 & 15\\
19 & 21 & 17\ 18\
11 & 13 & 9 & 10
\ кінець {масив}\ праворуч)
\ кінець {вирівняний}\)
Вибираємо вартість -категорію X з ур. (2.56). Блок профунктора U\(_{X}\) на X описується мостовою схемою
1. Перша рівність - це одиничність V (Визначення 2.2 (b)).
Другий крок використовує монотонність (визначення 2.2 (а)), застосовану до нерівностей I ≤ P (p, p) (закон ідентичності для P при p, визначення 2.46 (a)) та Φ (p, q) ≤ Φ (p, q) (рефлексивність попереднього порядку V, Визначення 1.30 (а)). Третій крок використовує визначення join: для всіх x і y, оскільки будь-який x ≤ x, ми маємо x ≤ x\(\lor\) y. Остаточна рівність - це лише визначення профункторного складу, визначення 4.21.
2. Зверніть увагу, що в Bool я = true.
Оскільки закон ідентичності в p говорить true ≤ P (p, p), а true є найбільшим елементом попереднього порядку Bool, ми, таким чином, маємо P (p, p) = true для всіх p. Це показує, що перша нерівність у еквалайзері (4.28) - це рівність.
Друга нерівність більше задіяна. Зверніть увагу, що за вищесказаним можна вважати ліву частину нерівності дорівнює Φ (p, q). Розбиваємо на два випадки. Припустимо, Φ (p, q) = істина. Потім, знову ж таки, оскільки істина є найбільшим елементом\(\mathbb{B}\), ми повинні мати рівність.
Далі припустимо Φ (p, q) = брехня. Зверніть увагу, що оскільки Φ є монотонною картою P\(^{op}\) × Q → Bool, якщо p ≤ p у P, то Φ (p 1, q) ≤ Φ (p, q) у бул.
Таким чином, якщо P (p, p 1) = істинно, то Φ (p\(_{1}\), q) = Φ (p, q) = помилково.
Звідси випливає, що для всіх\(\in\) р 1 Р у нас є або P (p, p\(_{1}\)) = помилково, або Φ (p\(_{1}\), q) = помилково, а значить =\(\bigvee\)\(_{p_{1} \in\ P}\) P (p, p\(_{1}\))\(\land\) Φ (p \(_{1}\), q) =\(\bigvee\)\(_{p_{1} \in\ P}\) брехня = брехня.
Таким чином, в будь-якому випадку ми бачимо, що Φ (p, q) =\(\bigvee\)\(_{p_{1} \in\ P}\) P (p, p\(_{1}\))\(\land\) Φ (p\(_{1}\), q), як потрібно.
3. Перше рівняння - одиничність в моноїдальних категоріях, v I = v для будь-якого v\(\in\) V. Друга полягає в тому, що I ≤ Q (q, q) за одиничністю збагачених категорій, див. Визначення 2.46 разом з монотонністю моноїдного добутку: v\(_{1}\) ≤ v\(_{2}\) означає v v\(_{1}\) ≤ v v\(_{2}\). Третій був показаний у вправі 4.9.
Це дуже схоже на вправу 2.104: ми використовуємо асоціативність. Зверніть увагу, однак, ми також вимагаємо, щоб V був симетричним моноїдальним замкнутим, оскільки це означає розподіл над\(\lor\) (пропозиція 2.87 2), і V бути скелетним, тому ми можемо перетворити еквіваленти в рівності.
\ (\ почати {вирівняний}
(\ Phi\ текст {;}\ Psi)\ текст {;}\ Іпсилон) (p, s) &=\ bigvee_ {r\ in\ mathcal {R}}\ ліворуч (\ bigvee_ {q\ in\ mathbb {Q}}\ Phi (p, q)\ час\ Psi (q, r)\ право)\ час\ Іпсилон (r, s)\\
&=\ bigvee_ {r\ in\ mathcal {R}, q\ in\ mathbb {Q}}\ Phi (p, q)\ раз\ Psi (q, r)\ час\ Іпсилон (r, s)\\
&=\ bigvee_ {q\ in\ mathbb {Q}}\ Phi (p, q)\ час\ bigvee_ {r\ in\ mathcal {R}} (\ Psi (q, r)\ час\ Іпсилон (r, s))\\
& =(\ Phi\ text {}; (}\ Psi\ текст {;}\ Іпсилон)) (p, s)
\ кінець {вирівняний}\)
Це дуже просто. Бажаємо перевірити\(\widehat{id}\): P → P має формулу\(\widehat{id}\) (p, q) = P (p, q). За визначенням 4.34,\(\widehat{id}\) (р, q) := P (id (p), q) = Р (р, q). Таким чином, вони однакові.
З'єднання\(\check{+}\):\(\mathbb{R}\) →\(\mathbb{R}\) ×\(\mathbb{R}\) ×\(\mathbb{R}\) посилає (a, b, c, d) до\(\mathbb{R}\) (a, b + c + d), що є істинним, якщо a ≤ b + c + d, і false в іншому випадку.
1. За визначенням 4.34,\(\widehat{F}\) (р, q) = Q (F (p), q) і\(\check{G}\) (р, q) = Q (p, G (q)). Оскільки V є скелетним, F і G є V суміжними якщо і тільки тоді, коли Q (F (p), q) = Q (p, G (q)). Таким чином F і G є суміжними якщо і тільки якщо\(\widehat{F}\) =\(\check{G}\).
2. Зауважте, що id: P → P є V-подібним до себе, оскільки обидві сторони ур. (4,40) тоді дорівнюють P (p, q). Таким чином\(\widehat{id}\) =\(\check{id}\).
Діаграма Хассе для колажу даного профунктора досить просто така:
Оскільки у нас є лише приблизне визначення, ми можемо лише приблизно перевірити це: ми не будемо морочитися з поняттям добре себе. Тим не менш, ми все ще можемо порівняти визначення 2.2 з визначенням 4.45.
По-перше, нагадаємо з розділу 3.2.3, що попередній порядок - це категорія P така, що для кожного\(\in\) p, q P множина P (p, q) має не більше одного елемента.
На поверхні все виглядає багатообіцяюще: обидва визначення мають дві складові і чотири властивості. У складовій (i) як Визначення 2.2, так і Визначення 4.45 закликають до одного і того ж: елемента або об'єкта попереднього порядку П. Поки що добре. Однак складова (ii) - це те, що стає цікавим: визначення 2.2 викликає лише функцію: P × P → P, тоді як визначення 4.45 викликає функтор.
Нагадаємо з прикладу 3.42, що функтори між попередніми замовленнями - це саме монотонні карти. Таким чином, нам потрібно для функції у визначенні 2.2, щоб бути монотонною картою. Це саме властивість (a) визначення 2.2: вона говорить, що якщо (x\(_{1}\), x\(_{2}\)) ≤ (y\(_{1}\), y\(_{2}\)) в P P, то ми повинні мати x\(_{1}\) x\(_{2}\)\(_{1}\) ≤ y \(_{2}\)У П. Так це також випадок, що у визначенні 2.2 що є функтором.
Решта властивостей легко порівнюються, приймаючи природні ізоморфізми рівністю або еквівалентністю в P. Дійсно, властивість (b) визначення 2.2 відповідає обом властивостям (а) і (b) визначення 4.45, а потім відповідні властивості (c) і (d) аналогічно відповідають.
- \(_{gE}\)(5, 3) = брехня,\(_{gF}\) (5, 3) = 2.
- \(_{gE}\)(3, 5) = правда,\(_{gF}\) (3, 5) = −2.
- h (5, правда) = 5.
- h (−5, правда) = −5.
- h (−5, брехня) = 6.
- \(_{qG}\)(−2, 3) = 2,\(_{qF}\) (−2, 3) = −13.
- \(_{qG}\)(2, 3) = −1,\(_{qF}\) (2, 3) = 7.
Так, приблизне визначення приблизно погоджується: прості старі категорії Set -categories! Детально нам потрібно порівняти визначення 4.51, коли V = (Set, {1}, ×) з визначенням 3.6. В обох випадках ми бачимо, що (i) запитує колекцію об'єктів і (ii) просить для всіх пар об'єктів x, y набір C (x, y) морфізмів. Більш того, нагадаємо, що моноїдальна одиниця I є одним елементом set {1}.
Це означає, що ідентифікатор морфізму\(_{x}\): I → C (x, x) є ідентифікатором функції\(_{x}\): {1} → C (x, x). Це ті ж дані, що і просто елемент id\(_{x}\) = id\(_{x}\) (1)\(\in\) C (x, x); ми називаємо ці дані морфізмом ідентичності на x. Нарешті, морфізм;: C (x, y) C (y, z) → C (x, z) є функцією;: C (x, y) × C (y, z) → C (x, z); це саме композиція вимагається у визначенні 3.6 (iv).
Таким чином, в обох випадках дані погоджуються. У Визначенні 3.6 ми також вимагаємо, щоб ці дані задовольняли дві умови, унікальність та асоціативність. Це те, що мається на увазі під останнім реченням визначення 4.51.
Елементом ідентичності у категорії Cost X є морфізм I → X (x, x) у Cost = ([0, ∞], ≥, 0, +), і, отже, умова, що 0 ≥ X (x, x). Це означає, що X (x, x) = 0. З точки зору відстаней, ми інтерпретуємо це як означає, що відстань від будь-якої точки до себе дорівнює 0. Ми вважаємо, що це досить розумна умова для поняття відстані, щоб підкорятися.
1. Ось картинка одиничної кореляції Ø →\(\underline{3}\)\(\underline{3}\), де ми намалювали порожній набір з порожнім пунктирним прямокутником зліва:
2. Ось картинка кореляції графства\(\underline{3}\)\(\underline{3}\) → Ø:
3. Ось зображення рівняння змії зліва від ур. (4.59).
Враховуючи два попередні замовлення ресурсів X та Y, попередній порядок X × Y представляє набір усіх пар ресурсів, x\(\in\) X та \(\in\)y, з (x, y) ≤ (x ′, y ′) iff x ≤ x ′ та y ≤ у ′. Тобто, якщо х доступний з урахуванням x ′ і y доступний з урахуванням y ′, то (x, y) доступний з урахуванням (x ′, y ′).
З огляду на два профунктори Φ: X\(_{1}\) → X\(_{2}\) і ψ: Y\(_{1}\) → Y\(_{2}\), профунктор Φ × ψ представляє їх сполучність, тобто І. Іншими словами, якщо y\(_{1}\) можна отримати заданою x\(_{1}\) І y\(_{2}\) можна отримати заданою x\(_{2}\), то (y\(_{1}\), y\(_{2}\)) можна отримати заданою (x\(_{1}\), х\(_{2}\)).
Профунктор X × 1 → X, визначений функтором α: (X × 1)\(^{op}\) × X → V, який відображає α (x, 1), y) := X (x, y) є ізоморфізмом. Він має обернену α\(^{-1}\): X → X × 1, визначену α\(^{-1}\) (x, (y, 1)) := X (x, y). Щоб побачити, що α\(^{-1}\); α = U\(_{x}\), зауважте спочатку, що одиничний закон для X при z і визначення об'єднання мають на увазі
X (x, z) = X (x, z) I ≤ Х (х, з) X (z, z) ≤\(\bigvee_{y \in X}\) Х (х, у) X (у, з),
тоді як композиція говорить X (x, y) X (y, z) ≤ X (x, z) і, отже,
\(\bigvee_{y \in X}\)Х (х, у) Х (у, з) ≤\(\bigvee_{y \in X}\) Х (х, з) X (y, z)
Таким чином, розпакувавши визначення складу профунктора, ми маємо
(α\(^{-1}\); α) (х, з) =\(\bigvee_{(y,1) \in Xx1}\) α (х, (у, 1)) α\(^{-1}\) (у, 1), z) =\(\bigvee_{y \in X}\) Х (х, у) Х (у, з) = Х (х, з).
Аналогічно ми можемо показати α; α\(^{−1}\) = U\(_{X×1}\), а отже, що α - це ізоморфізм X × 1 → X. Крім того, ми можемо аналогічно показати, що β (1, x), y) := X (x, y) визначає ізоморфізм β: 1 × X → X.
Перевіряємо перше рівняння змії, те, що знаходиться на лівій стороні ур. (4.59). Доказ того, що знаходиться на правій стороні, аналогічний. Треба показати, що композитний Φ профункторів
\(X \stackrel{a^{-1}}{\rightarrow} X x 1 \stackrel{U_{x} x n_{x}}{\longrightarrow} X x X^{op} x X \stackrel{\mathcal{E}_{x} x U_{x}} {\longrightarrow} 1 x X \stackrel{a}{\rightarrow} X\)
це сама ідентичність (тобто. одиничний профунктор на X), де α і α\(^{−1}\) - ізоморфізми, визначені в розчині до вправи 4.65 вище.
Вільно використовуючи розподільну здатність над\(\land\), значення Φ (x, y) цього композиту при (x, y)\(\in\) X\(^{op}\) × X задається
\ (\ почати {вирівняний}
&\ bigvee_ {x}\ альфа^ {-1} (x, (a, 1))\ час (\ mathrm {U} х\ раз\ та x) ((a, 1), (b, c, d)\\
& a, b, c, d, e\ in X &\ час (\ epsilon x\ times\ times m {U} x) ((b, c, d), (1, е))\ час\ альфа ((1, е), y)\\
=&\ bigvee_ {\ альфа} ^ {-1} (x, (a, 1)\ час\ mathrm {U} x (a, b)\ іноді\ eta x (1, c, d)\\\
& a, b, c, d, e\ in\ matchal {X}\ quad\ час\ епілон х (b, c, 1)\ час\ mathm {U} x (d, e)\ час\ час\ альфа (1), e), y)\\
=&\ bigvee_ {a, b, c, d, e\ в X}\\
=& x (x, y)
\ end {вирівняний}\)
де на останньому кроці ми неодноразово використовуємо аргумент Lemma 4.27, який показує, що композиція з модулем профунктора U\(_{X}\) (a, b) = X (a, b) - це ідентичність. Це показує, що Φ (x, y) є профунктором ідентичності, і, отже, показує перше рівняння змії. Знову ж таки, перевірка іншого рівняння змії аналогічна.