2.3: Збагачення

Last updated
Save as PDF

Page ID: 66433

$ \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}}$

У цьому розділі ми представимо V-категорії, де V - симетричний моноїдальний попередній порядок. Ми побачимо, що категорії Bool - це попередні замовлення, і що категорії витрат є приємним узагальненням поняття метричного простору.

V -категорії

Хоча V-категорії можна визначити навіть тоді, коли V не симетричний, тобто просто підкоряється умовам (a) — (c) визначення 2.2, деякі речі працюють не зовсім правильно. Наприклад, пізніше у Вправі 2.75 ми побачимо, що умова симетрії необхідна для існування добутків V-категорій. У всякому разі, ось визначення.

Визначення: 2.46.

Нехай V = (V, ≤, I,) є симетричним моноїдальним попереднім порядком. V -категорія X складається з двох складових, що задовольняють двом властивостям. Щоб вказати X,

(i) вказується множина Ob (X), елементи якої називаються об'єктами;

(ii) для кожних двох об'єктів x, y вказується елемент X (x, y)$\in$ V, який називається хом-об'єктом. $^{2}$

Вищевказані складові зобов'язані задовольняти двом властивостям:

(a) для кожного об'єкта x$\in$ Ob (X) ми маємо I ≤ X (x, x), і

(б) для кожних трьох об'єктів x, y, z$\in$ Ob (X) ми маємо X (x, y) X (y, z) ≤ X (x, z). Ми називаємо V базою збагачення для X або скажемо, що Х збагачений в V.

Приклад 2.47.

Як ми побачимо в наступному підрозділі, з кожного попереднього замовлення ми можемо побудувати Bool -категорію, і навпаки. Отже, щоб відчути V-категорії, розглянемо попередній порядок, згенерований діаграмою Хассе:

$Знімок екрана 2021-01-10 о 8.57.43 PM.png$

Як це відповідає Bool -категорії X? Ну, об'єкти X - це просто елементи попереднього порядку, тобто Ob (X) = {p, q, r, s, t}. Далі для кожної пари об'єктів (x, y) нам потрібен елемент$\mathbb{B}$ = {false, true}: просто візьміть true, якщо x ≤ y, і false, якщо інакше. Так, наприклад, так як s ≤ t і t$\nleq$ s, у нас є X (s, t) = істина і X (t, s) = брехня. Згадуючи з прикладу 2.27, що моноїдальна одиниця I Була вірна, просто перевірити, що це підкоряється як (а), так і (b), тому у нас є категорія Bool.

Загалом, іноді зручно представляти V-категорію X квадратної матрицею. Рядки і стовпці матриці відповідають об'єктам X, а (x, y) -й запис - це просто хом-об'єкт X (x, y). Так, наприклад, вищевказаний попередній порядок в Eq. (2.48) може бути представлений матрицею

$Знімок екрана 2021-01-10 о 8.58.30 PM.png$

Попередні замовлення як Bool -категорії

Наш колега Пітер Гейтс назвав теорію категорій «споконвічним соком», тому що стільки її можна визначити з точки зору інших її частин. Немає ніде справедливо назвати початком, тому що початок можна визначити з точки зору чогось іншого. Так і бути; це частина веселощів.

Теорма 2.49.

Існує відповідність один до одного між попередніми замовленнями та категоріями Bool.

Тут ми опиняємося в соці, тому що ми говоримо, що попередні замовлення такі ж, як Bool -категорії, тоді як Bool сам по собі є попереднім замовленням. «То тоді Бул як... збагачений сам по собі?» Так, кожне попереднє замовлення, включаючи Bool, збагачується в Bool, як ми зараз побачимо. Доказ теореми 2.49. Давайте перевіримо, що ми можемо побудувати попереднє замовлення з будь-якої категорії Bool. Оскільки$\mathbb{B}$ = {false, true}, визначення 2.46 говорить, що Bool -категорія складається з двох речей:

(i) набір Ob (X), і

(ii) для кожного x, y$\in$ Ob (X) елемент X (x, y)$\in$ B, тобто або X (x, y) = істина, або X (x, y) = брехня.

Ми будемо використовувати ці дві речі, щоб почати формування попереднього порядку, чиї елементи є об'єктами X. Отже, давайте назвемо попередній порядок (X, ≤), і нехай X = Ob (X). Для ≤ відношення, давайте оголосимо x ≤ y, якщо X (x, y) = true. У нас є задатки попереднього порядку, але для того, щоб він працював, співвідношення ≤ має бути рефлексивним та перехідним. Давайте подивимося, чи отримаємо їх із властивостей, гарантованих визначенням 2.46:

(a) для кожного елемента x$\in$ X ми маємо true ≤ X (x, x),

(b) для кожних трьох елементів x, y, z$\in$ X ми маємо X (x, y)$\wedge$ X (y, z) ≤ X (x, z).
Для b$\in$ Bool, якщо true ≤ b, то b = true, тому перша заява говорить X (x, x) = true, що означає x ≤ x. Для другого твердження можна звернутися до еквалайзера (2.28). Оскільки false ≤ b для всіх$\in$ b B, єдиний спосіб оператор (b) має будь-яку силу, якщо X (x, y) = true і X (y, z) = true, і в цьому випадку це змушує X (x, z) = true. Ця умова точно перекладається як приказка, що x ≤ y та y ≤ z означає x ≤ z. Таким чином, ми отримали рефлексивність і транзитивність від двох аксіом Bool -категорій.

У прикладі 2.47 ми побудували Bool -категорію з попереднього замовлення. Ми залишаємо читачеві узагальнити цей приклад і показати, що дві конструкції обернені; див. Вправа 2.50.

Приклад 2.50.

Почніть з попереднього замовлення (P, ≤) і використовуйте його для визначення категорії Bool, як ми це робили в прикладі 2.47. На доказ теореми 2.49 ми показали, як перетворити цю категорію Bool назад у попередній порядок. Покажіть, що роблячи це, ви отримуєте попереднє замовлення, з якого ви почали.
Аналогічно, покажіть, що якщо ви перетворите категорію Bool на попереднє замовлення, використовуючи вищевказаний доказ, а потім повернете попереднє замовлення назад у категорію Bool за допомогою вашого методу, ви отримаєте категорію Bool, з якої ви почали. ♦

Зараз ми обговоримо красиве застосування поняття збагачених категорій: метричні простори.

Метричні простори Ловера

Метричні простори пропонують точний спосіб опису просторів точок, кожна пара яких розділена деякою відстанню. Ось звичайне визначення:

Визначення: 2.51.

Метричний простір (X, d) складається з:

(i) множина X, елементи якої називаються точками, і

(ii) функція d: X × X →$\mathbb{R}$$_≥0$, де d (x, y) називається відстань між x і y

Ці складові повинні задовольняти чотирьом властивостям:

(а) для кожного х$\in$ Х, у нас є d (x, x) = 0,
(b) для кожного x, y$\in$ X, якщо d (x, y) = 0 то x = y,

(c) для кожного х, у$\in$ X, ми маємо d (x, y) = d (y, x), і
(d) для кожного х, у, z$\in$ X, ми маємо д (х, у) + г (у, з) ≥ д (х, з).

Четверте властивість називається нерівністю трикутника.
Якщо ми запитаємо замість (ii) функції d: X × X → [0, ∞] =$\mathbb{R}$$_{≥0}$$\cup$ {∞}, ми викликаємо (X, d) розширений метричний простір.

Нерівність трикутника говорить про те, що при побудові маршруту від x до z відстань завжди максимум те, що ви отримуєте, вибираючи проміжну точку y і йдучи

х → у → з.

$Знімок екрана 2021-01-11 в 1.23.44 AM.png$

Він може бути викликаний трьома різними способами на наведеному вище зображенні: 3 + 5 ≥ 7,2, але також 5 + 7,2 ≥ 3 та 3 + 7,2 ≥ 5. Ах так, і 5 + 3 ≥ 7,2, 7,2 + 5 ≥ 3 і 7,2 + 3 ≥ 5.

Нерівність трикутника чудово фіксує щось про відстань, як і той факт, що d (x, x) = 0 для будь-якого x. Однак дві інші умови не зовсім такі загальні, як хотілося б. Дійсно, є багато прикладів речей, які «повинні» бути метричними просторами, але які не задовольняють умовам (b) або (c) визначення 2.51.

Наприклад, що, якщо ми візьмемо X, щоб бути місцями у вашому районі, але замість вимірювання відстані, ви хочете d (x, y) виміряти зусилля, щоб отримати від x до y. Тоді, якщо є якісь пагорби, аксіома симетрії, d (x, y) =$^{?}$ d (y, x), зазнає невдачі: легше дістатися від x до y, щоб потім перейти з y в гору до x.

Ще один спосіб знайти модель, яка порушує аксіому симетрії, - це уявити, що елементи X - це не точки, а цілі регіони, такі як США, Іспанія та Бостон. Скажіть, що відстань від регіону A до регіону B розуміється за допомогою налаштування «Я поставлю вас у довільну частину A, і вам просто потрібно дістатися куди завгодно в B; яка відстань у найгіршому сценарії?» Отже, d (США, Іспанія) - це відстань від десь на заході США до західного краю Іспанії: вам просто потрібно потрапити в Іспанію, але ви починаєте в гіршій можливій частині США для цього.

Приклад 2.52.

Яка відстань більша під вищевказаним описом, d (Іспанія, США) або d (США, Іспанія)? ♦

Це поняття відстані, яке сильно пов'язане з чимось, що називається відстань Хаусдорфа,$^{3}$ знову задовольнить нерівність трикутника, але це порушує умову симетрії. Це також порушує іншу умову, тому що d (Бостон, США) = 0. Незалежно від того, де ви знаходитесь у Бостоні, відстань до найближчої точки США дорівнює 0. З іншого боку, d (США, Бостон)$\neq$ 0.

Нарешті, можна уявити собі використання для відстаней, які не є кінцевими. З точки зору моїх зусиль, відстань звідси до Плутона становить ∞, і не було б краще, якби Плутон все ще був планетою. Аналогічно, з точки зору відстані Хаусдорфа, розглянутої вище, відстань між двома областями часто нескінченна, наприклад, відстань між {r$\in$$\mathbb{R}$ | r < 0} та {0} як підмножин ($\mathbb{R}$, d) нескінченна.

Коли ми скидаємо умови (b) і (c) і допускаємо нескінченні відстані, ми отримуємо fol-lowing розслаблене поняття метричного простору, вперше запропоноване Ловере. Згадайте симетричний моноїдальний попередній порядок Вартість = ([0, ∞], ≥, 0, +) з прикладу 2.37.

Визначення: 2.53.

Метричний простір Ловера - це категорія «Вартість».

Це дуже компактне визначення, але воно упаковує удар. Давайте розберемося, що це означає,

пов'язуючи його зі звичайним визначенням метричного простору. За визначенням 2.46, категорія витрат X складається з:

(i) множина Ob (X),
(ii) для кожного x, y$\in$ Ob (X) елемента X (x, y)$\in$ [0, ∞].

Тут множина Ob (X) грає роль множини точок, а X (x, y)$\in$ [0, ∞] грає роль відстані, тому напишемо трохи перекладача:

Х: = Об (Х) г (х, у) := Х (х, у).

Властивості категорії, збагаченої вартістю, є: (a) 0 ≥ d (x, x) для всіх x$\in$ X, і
(b) d (x, y) + d (y, z) ≥ d (x, z) для всіх x, y, z$\in$ X.

Починаючи з d (x, x)$\in$ [0, ∞], якщо 0 ≥ d (x, x) то d (x, x) = 0. Отже, перша умова еквівалентна першій умові з визначення 2.51, а саме d (x, x) = 0. Друга умова - нерівність трикутника.

Приклад 2.54.

Множині$\mathbb{R}$ дійсних чисел можна задати метричну просторову структуру, а отже, і метричну просторову структуру Ловера. А саме d (x, y) := | y − x |, абсолютне значення різниці. Так d (3, 7) = 4.

Вправа 2.55.

Розглянемо симетричний моноїдальний попередній порядок ($\mathbb{R}_{≥0}$, ≥, 0, +), який майже такий же, як Вартість, за винятком того, що він не включає ∞. Як би ви охарактеризували різницю між метричним простором Ловера та категорією ($\mathbb{R}_{≥0}$, ≥, 0, +) у значенні визначення 2.46? ♦

Представлення метричних просторів із зваженими графами Так само, як можна перетворити діаграму Хассе в попередній порядок, можна перетворити будь-який зважений граф - графік, ребра якого позначені числами w ≥ 0, у метричний простір Ловера. По суті, ми будемо розглядати їх як графіки, позначені елементами [0, ∞], а точніше називати їх вартісними -зваженими графами. $^{4}$

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

$Знімок екрана 2021-01-11 в 1.45.39 AM.png$

За заданим зваженим графом формують метрику$d_{X}$ на його множині X вершин, встановивши d (p, q) як довжину найкоротшого шляху від p до q. Наприклад, ось таблиця відстаней для Y

$Знімок екрана 2021-01-11 в 1.46.23 AM.png$

Вправа 2.58.

Заповніть наступну таблицю відстаней на зваженому графіку X від еквалайзера (2.56)

$Знімок екрана 2021-01-11 в 1.47.48 AM.png$

Вище ми перетворили зважений графік G, наприклад, як показано в еквалайзері (2.56), у таблицю відстаней, але це вимагає трохи мислення. Існує більш пряма конструкція для взяття G і отримання квадратної матриці M G, рядки і стовпці якої індексуються вершинами G. Для цього встановіть M G рівним 0 уздовж діагоналі, щоб бути ∞ скрізь, де ребро не вистачає, і щоб бути товщиною краю, якщо є ребро.

Наприклад, матриця, пов'язана з Y в еквалайзері (2.56), буде

$Знімок екрана 2021-01-11 в 1.48.42 AM.png$

Як тільки ви побачите, як ми це зробили, ви зрозумієте, що не потрібно думати, щоб перетворити зважений граф G в матрицю M G таким чином. Пізніше в розділі 2.5.3 ми побачимо, що більш складні «матриці відстані» d Y, такі як Eq. (2.57), можна отримати з простих матриць графа M Y, таких як Eq. (2.59), повторюючи певний вид «множення матриць».

Вправа 2.60.

Заповніть матрицю M X, пов'язану з графом X у еквалайзері (2.56):

$Знімок екрана 2021-01-11 в 1.49.47 AM.png$

V -варіації на попередніх замовленнях і метричних просторах

Ми розповіли історію Була і Коста. Але в розділі 2.2.4 ми навели приклади багатьох інших моноїдальних попередніх замовлень, і кожен з них служить основою збагачення для своєрідної збагаченої категорії. Які з них корисні? Щось стає корисним лише тоді, коли хтось знаходить йому застосування. Ми знайдемо використання для одних, а не для інших, хоча ми заохочуємо читачів подумати про те, що означало б збагатити різні моноїдальні категорії, розглянуті вище; можливо, вони можуть знайти застосування, яке ми не досліджували.

Вправа 2.61.

Нагадаємо моноїдальний попередній порядок NMY: = (P, ≤, yes, min) з вправи 2.34. Інтерпретувати, що таке NMY -категорія ♦

наступні дві вправи, ми використовуємо V-зважені графіки для побудови V-категорій. Це можливо, тому що ми будемо використовувати попередні замовлення, які, як Bool і Cost, приєднуються.

Вправа 2.62.

Нехай M - множина, а M: = (P (M), M$\subseteq$,$\cap$) - моноїдальний передпорядок, елементи якого є підмножинами M.

Хтось дає таке тлумачення: «Для будь-якого набору М, уявіть це як сукупність видів транспорту (наприклад, автомобіль, човен, піша). Тоді M-категорія X повідомляє вам усі режими, які отримають вас від a аж до b, для будь-яких двох точок a, b$\in$ Ob (X)».

Намалюйте графік з чотирма вершинами і чотирма або п'ятьма ребрами, кожен з яких позначений підмножиною M = {автомобіль, човен, фут}.
З цього графіка можна побудувати M-категорію, де хом-об'єкт від x до y обчислюється наступним чином: для кожного шляху p від x до y візьміть перетин множин, що позначають ребра в p. Потім візьміть об'єднання цих множин по всіх шляхах p від x до y. Випишіть відповідну матрицю хом-об'єктів чотири на чотири, і переконайте себе, що це дійсно М-категорія.
Чи правильно виглядає тлумачення людини, або вона тонко помиляється якось? ♦

Вправа 2.63.

Розглянемо моноїдальний передпорядок W: = ($\mathbb{N}$$\cup${∞}, ≤, ∞, min).

Намалюйте невеликий графік, позначений елементами N$\cup$ {∞}.
Випишіть матрицю, рядки і стовпці якої індексуються вузлами в
graph, і чий (x, y) -й запис задається максимумом по всіх шляхах p з x
до y мінімальної мітки краю в p.
Довести, що ця матриця є матрицею хом-об'єктів для W-категорії. Це буде
дати вам відчуття того, як працює W.
Складіть інтерпретацію, як у вправі 2.62, як уявити збагачення в W ♦