4.4: Категоризація

Тут ми перемикаємо передачі, щоб обговорити загальне поняття під назвою категорифікація. Почнемо знову з основ, класифікуючи кілька понять, з якими ми вже стикалися. Мета полягає у визначенні компактних закритих категорій та їх схеми підключення в стилі зворотного зв'язку. У цей момент ми повернемося до історії спільного дизайну та V-profunctors загалом, і покажемо, що вони насправді утворюють компактну замкнуту категорію, і таким чином інтерпретують діаграми, які ми малювали з часу Eq. (4.1).

Основна ідея категоризації

Загальна ідея категоризації полягає в тому, що ми беремо річ, яку ми знаємо, і додаємо структуру до неї, так що те, що раніше властивості стали структурами. Ми робимо це таким чином, щоб ми могли відновити те, що ми класифікували, забувши цю нову структуру. Це досить розпливчасто; наведемо приклад. Основна арифметика стосується властивостей натуральних чисел N, таких як той факт, що 5 + 3 = 8. Одним із способів класифікації N є використання категорії FinSet скінченних множин і функцій. Щоб отримати класифікацію, ми замінюємо грубі 5, 3 та 8 наборами таких багатьох елементів, скажімо\(\underline{5}\) = {яблуко, банан, вишня, дракон, слон},\(\underline{3}\) = {яблуко, помідор, диня}, і\(\underline{8}\) = {Алі, Боб, Карл, Деб, Елі, Фріц, Джем, Хелен} відповідно. Ми також замінюємо + на неспільне об'єднання множин, а брут-властивість рівності зі структурою ізоморфізму. Що робить це хорошою категорифікацією, так це те, що, зробивши ці заміни, аналог 5 + 3 = 8 все ще вірний\(\underline{5}\):\(\underline{3}\)\(\cong\)\(\underline{8}\).

У цьому класифікованому світі ми маємо більше структури, щоб говорити про відносини- кораблі між об'єктами, тому ми можемо бути більш точними про те, як вони пов'язані один з одним. Таким чином, справа не в тому,\(\underline{5}\) що\(\underline{3}\) дорівнює обраному нами восьмиелементному набору 8, але точніше, що існує оборотна функція порівняння двох, показуючи, що вони ізоморфні в категорії FinSet.

Зверніть увагу, що у вищезгаданій конструкції ми зробили ряд варіантів; тут ми повинні остерігатися. Вибір хорошої категоризації - наприклад, створення хорошої алгебраїчної структури, такої як попередні замовлення або кванти, є частиною мистецтва математики. Не існує визначеного способу категоризації, і успіх обраної категоризації часто є емпіричним: її багатша структура повинна дозволити нам більше зрозуміти тему, яку ми хочемо моделювати.

Як ще один приклад, емпірично приємним способом категоризації попередніх замовлень є кішка- егорифікувати їх, а також категорії. У цьому випадку замість властивості брута «існує морфізм a → b», позначається a ≤ b або P (a, b) = true, ми замість цього скажемо «тут безліч морфізмів a → b». Ми отримуємо домашній набір, а не хом-булеве значення. Насправді - щоб заявити це таким чином прямо з первісного озу - так само, як попередні замовлення є Bool -categories, звичайні категорії насправді Set -categories.

відображення на електричних схемах

Припустимо, у нас є попереднє замовлення. Ми представили дуже простий вид схеми підключення в розділі 2.2.2. Це дозволило нам намалювати коробку

всякий раз, коли x\(_{0}\) ≤ x\(_{1}\). З'єднавши їх разом, ми могли б довести факти в нашому попередньому порядку. Наприклад

надає доказ того, що x\(_{0}\) ≤ x\(_{3}\) (зовнішня коробка), використовуючи три факти (внутрішні коробки), x\(_{0}\) ≤ x\(_{1}\)\(_{2}\), x\(_{1}\) ≤ x та x\(_{2}\) ≤ x \(_{3}\).

Як класифіковані попередні замовлення, категорії мають в основному таку ж схему підключення, як попередні замовлення, а саме послідовності коробок всередині коробки. Але оскільки ми замінили той факт, що x\(_{0}\) ≤ x\(_{1}\) на структуру набору морфізмів, нам потрібно вміти маркувати наші коробки іменами морфізму:

Припустимо, задані додаткові морфізми g: B → C і h: C → D. Представляючи їх кожен як коробки, як ми зробили для f, у нас може виникнути спокуса склеїти їх разом, щоб сформувати нову коробку:

В ідеалі це також був би морфізм у нашій категорії: зрештою, ми сказали, що ми можемо представляти морфізми з коробками з одним входом і одним виходом. Але почекайте, скажете ви! Ми не знаємо, який це морфізм. Це f; (г; ч)? Або (f; г); ч? Добре, що ви такі обережні. На щастя, нас рятують властивості, які повинна мати категорія.

Асоціативність говорить f; (g; h) = (f; g); h, тому не має значення, який шлях ми вирішили спробувати розшифрувати коробку.

Аналогічно, морфізм ідентичності на об'єкті x намальований, як ліворуч нижче, але ми побачимо, що малювати id не\(_{x}\) шкідливо будь-яким із наступних трьох способів:

За визначенням 3.6 морфізми в категорії задовольняють двом властивостям, званим властивістю унітальності та властивістю асоціативності.

Унікальність говорить про те, що id\(_{x}\); f = f = f = id\(_{y}\) для будь-якого f: x → y. З точки зору діаграм, це б сказав:

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

У розділі 2.2.2 ми також побачили схеми підключення для моноїдальних попередніх замовлень. Тут нам було дозволено малювати коробки, які можуть мати кілька набраних входів і виходів, але без вибору мітки (завжди ≤):

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

Крім того, симетрична моноїдальна категорія має правило композиції та моноїдальний твір, які дозволяють нам поєднувати ці поля для інтерпретації діаграм так:

Нарешті, ця структура повинна підкорятися законам узгодженості, аналогічним асоціативності та унікальності в категоріях, які дозволяють однозначно інтерпретувати такі діаграми. У наступному розділі ми будемо трохи більш формальними, але корисно пам'ятати, що, коли ми говоримо, що наші дані повинні бути «добре поводяться», це все, що ми маємо на увазі.

Моноїдальні категорії

Визначено V-категорії для симетричного моноїдального попереднього порядку V у визначенні 2.46. Так само, як попередні замовлення виявилися особливими видами категорій (див. Розділ 3.2.3), моноїдальні попередні замовлення - це особливі види моноїдальних категорій. І так само, як ми можемо розглянути V-категорії для моноїдального попереднього замовлення, ми також можемо розглянути V-категорії, коли V є моноїдальною категорією. Це ще один вид категоризації.

Скоро ми зустрінемо моноїдальну категорію (Set, {1}, ×). Моноїдальний добуток прийме дві множини, S і T, і поверне множину S × T = {(s, t) |\(\in\) s S, \(\in\)t}. Але тоді як для моноїдальних попередніх порядків ми мали грубу асоціативну властивість (p q) r = p (q r), відповідна ідея в Set не зовсім вірна:

\ (\ begin {вирівняний}
& S\ раз (T\ раз U) :=\ {(s, (t, u))\ середина s\ in S, t\ in T, u\ в U\}\
=? & (S\ раз T)\ раз U: =\ {(s, t), u)\ середина s\ в S, t\ in T, u\ в U\}
\ кінець {вирівняний}\)

Вони трохи відрізняються множинами: перша містить пари, що складаються з елементів в S і елемента в T × U, тоді як друга містить пари, що складаються з елемента в S × T і елемента в U. Набори не рівні, але вони явно ізоморфні, тобто різниця між ними - «всього лише питання бухгалтерського обліку». Таким чином, нам потрібна структура ізоморфізму бухгалтерського обліку, щоб відстежувати асоціативність:

\(\alpha_{s, t, u}:\{(s,(t, u)) \mid s \in S, t \in T, u \in U\} \stackrel{\cong}{\rightarrow}\{((s, t), u) \mid s \in S, t \in T, u \in U\}\)

Є кілька речей, про які слід згадати, перш ніж ми зануримося в ці ідеї. По-перше, тільки тому, що ви замінюєте грубі речі та властивості структурами, це не означає, що у вас більше немає грубих речей і властивостей: з'являються нові! Не тільки це, але по-друге, новий грубий матеріал, як правило, складніший, ніж те, з чого ви почали. Наприклад, вище ми замінили рівняння асоціативності ізоморфізмом α s, t, u, але тепер нам потрібна більш складна властивість, щоб гарантувати, що всі ці α поводяться розумно! Єдиний вихід з цього мурасу - додати нескінченно багато структури, яка веде одну до «∞ -категорій», але ми не будемо обговорювати це тут.

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

Грубе визначення: 4.45.

Дозвольте C бути категорією. Симетрична моноїдальна структура на С складається з наступних складових:

(i) об'єкт I\(\in\) Ob (C) називається моноїдальною одиницею, і

(ii) функтор: C × C → C, званий моноїдальним добутком

схильний до добре себе, природних ізоморфізмів

(а) λ\(_{c}\): I c \(\cong\)c для кожного c\(\in\) Ob (C),

(b) ρ\(_{c}\): c I\(\cong\) c для кожного c\(\in\) Ob (C),

(c) α\(_{c,d,e}\) :( c d) e\(\cong\) c (d e) для кожного c, d, e\(\in\) Ob (C), і

(d) σ\(_{c,d}\): c d \(\cong\)d c для кожного c, d\(\in\) Ob (C), називається карта підкачки, така, що σ ◦ σ = id.

Категорія, забезпечена симетричною моноїдальної структурою, називається симетричною моноїдальної категорією.

Зауваження 4.46. Якщо ізоморфізми в (а), (b) і (c) —але не (d) -замінені рівностями, то ми говоримо, що моноїдальна структура сувора, і це повне (негрубе) визначення симетричної суворої моноїдальної категорії. Насправді симетричні суворі моноїдальні категорії - це майже те ж саме, що і симетричні моноїдальні категорії, через результат, відомий як теорема когерентності Мака Лейна. Підсумок цієї теореми полягає в тому, що ми можемо, коли нам корисно, робити вигляд, що наші моноїдальні категорії суворі: наприклад, ми неявно робимо це, коли малюємо електричні схеми. Попросіть свого товариського теоретика категорії сусідства пояснити, як!

Зауваження 4.47. Для тих, хто ще не знайшов дружнього теоретика категорії експертів, ми робимо наступне зауваження. Повне (негрубе) визначення симетричної моноїдальної категорії полягає в тому, що симетрична моноїдальна категорія - це категорія, забезпечена еквівалентністю (основній категорії) симетричної суворої моноїдальної категорії. Це можна розпакувати, використовуючи Зауваження 4.46 та наш коментар щодо еквівалентності категорій у Зауваження 3.59, але ми не очікуємо, що ви цього зробите. Натомість, ми сподіваємося, що це дасть вам більше стимулів запитати дружнього експерта теоретика категорії!

Вправа 4.48.

Переконайтеся, що моноїдальні категорії дійсно узагальнюють моноїдальні попередні замовлення: моноїдальний попередній порядок - це моноїдальна категорія (P, I,) де,

для кожного p, q\(\in\) P множина P (p, q) має не більше одного елемента. ♦

Приклад 4.49.

Як ми вже говорили вище, існує моноїдальна структура на Set, де моноїдальна одиниця - це певний вибір однотонної множини, скажімо, I: = {1}, а моноїдальний твір -: = ×. Що означає, що × є функтором, це те, що:

• Для будь-якої пари об'єктів, тобто множин, (S, T)\(\in\) Ob (Set × Set), отримується множина (S × T)\(\in\) Ob (Set). Ми знаємо, що це таке: множина пар {(s, t) | s\(\in\) S, t\(\in\) T}.
• Для будь-якої пари морфізмів, тобто функцій, f: S → S ′ і g: T → T ′, отримується функція (f × g): (S × T) → (S ′× T ′). Працює точково: (f × g) (s, t) := (f (s), g (t)).
• Вони повинні зберігати ідентичності: id\(_{S}\) × id\(_{T}\) = id\(_{S×T}\) для будь-яких множин S, T.
• Вони повинні зберігати склад: для будь-яких функцій\(S \stackrel{f}{\rightarrow} S^{\prime} \stackrel{f^{\prime}}{\rightarrow} S^{\prime \prime} \text { and } T \stackrel{g}{\rightarrow} T^{\prime} \stackrel{g^{\prime}}{\rightarrow} T^{\prime \prime}\), один має

(ф × г); (f '× г') = (f; g) × (f '; g').

Чотири умови, (a), (b), (c) та (d) дають ізоморфізми {1} × \(\cong\)S S тощо.

Ці карти очевидні у випадку Set, наприклад функція {(1, s) | s\(\in\) S} → S надсилання (1, s) до s. Ми називали такі речі бухгалтерією.

Вправа 4.50.

Розглянемо моноїдальну категорію (Set, 1, ×) разом з діаграмою

Припустимо, що A = B = C = D = F = G = Z і E\(\mathbb{B}\) = {true, false}, і припустимо, що f\(_{C}\) (a) = | a |, f\(_{D}\) (a) = a∗ 5, g\(_{E}\) (d, b) = «d ≤ b,» g\(_{F}\) (d, b) = d − b, а h (c, e) = якщо е потім c ще 1 − c.

1. Що таке г\(_{E}\) (5,3) і г\(_{F}\) (5,3)?

2. Що таке г\(_{E}\) (3,5) і г\(_{F}\) (3,5)?

3. Що таке h (5, правда)?

4. Що таке h (−5, правда)?

5. Що таке h (−5, false)?

Вся діаграма тепер визначає функцію A × B → G × F; назвіть її q.

6. Що таке q\(_{G}\) (−2, 3) та q\(_{F}\) (−2, 3)?

7. Що таке q\(_{G}\) (2, 3) і q\(_{F}\) (2, 3)?

Ми побачимо більше моноїдальних категорій протягом решти цієї книги. ♦

Категорії, збагачені в симетричну моноїдальну категорію

Нам це знову не знадобиться, але ми колись пообіцяли пояснити, чому V-категорії, де V - симетричний моноїдальний попередній порядок, заслуговують на те, щоб їх розглядали як типи категорій. Причина, як ми вже натякали, полягає в тому, що категорії дійсно повинні називатися Set -categories. Але почекайте, набір - це не попереднє замовлення! Нам доведеться узагальнити - категорию—V-категорії.

Ми зараз наведемо приблизне визначення категорій, збагачених симетричною моноїдальною категорією V. як у визначенні 4.45, ми пригнічуємо деякі технічні частини в цьому ескізі, приховуючи їх під назвою «звичайні асоціативні та унітальні закони».

Грубе визначення: 4.51.

Нехай V - симетрична моноїдальна категорія, як у визначенні 4.45. Щоб вказати категорію, збагачену V, або V -категорію, позначену X,

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

(ii) для кожної пари x, y\(\in\) Ob (X) вказується об'єкт X (x, y)\(\in\) V, який називається хом-об'єктом для x, y;

(iii) для кожного x\(\in\) Ob (X) вказується ідентифікатор морфізму\(_{x}\): I → X (x, x) у V, який називається елементом ідентичності;

(iv) для кожного x, y, z\(\in\) Ob (X) вказується морфізм;: X (x, y) X (y, z) → X (x, z), називається морфізмом композиції.

Ці складові зобов'язані задовольняти звичним асоціативним і одиничним законам.

Точне, не грубе визначення можна знайти в інших джерелах, наприклад [NLA18], [Wik18], [Kel05].

Вправа 4.52.

Нагадаємо з прикладу 4.49, що V = (Set, {1}, ×) - це симетрична моноїдальна категорія. Це означає, що ми можемо застосувати визначення 4.51. Чи (грубе) визначення грубо узгоджується з визначенням категорії, наведеним у Визначенні 3.6? Або є тонка різниця? ♦

Зауваження 4.53. Ми вперше визначили V-категорії у визначенні 2.46, де V повинен був бути моноїдальним попереднім порядком. Щоб перевірити, що ми не зловживаємо нашими умовами, це гарна ідея, щоб переконатися, що V-категорії відповідно до визначення 2.46 все ще є V-категоріями відповідно до визначення 4.51.

Перше, що слід зауважити, це те, що кожен симетричний моноїдальний попередній порядок - це симетрична моноїдальна категорія (Вправа 4.48). Таким чином, враховуючи симетричний моноїдальний попередній порядок V, ми можемо застосувати визначення 4.51. Потрібні дані (i) і (ii) потім змушують нас добре почати: обидва визначення V-категорії вимагають об'єктів і hom-об'єктів, і вони вказуються однаково. З іншого боку, визначення 4.51 вимагає двох додаткових даних: (iii) елементи ідентичності та (iv) морфізми композиції. Звідки вони беруться?

У випадку попередніх замовлень існує максимум один морфізм між будь-якими двома об'єктами, тому нам не потрібно вибирати елемент ідентичності та морфізм композиції. Натомість нам просто потрібно переконатися, що елемент ідентичності та морфізм композиції існують. Саме про це говорять властивості (a) та (b) визначення 2.46.

Наприклад, вимога (iii) про те, що V-категорія X має обраний елемент ідентичності id x: I → X (x, x) для об'єкта x просто стає вимогою (a), що I ≤ X (x, x) є істинним у V. Це характерно для історії категоризації: те, що були простими властивостями у визначенні 2.46, стали структурами у визначенні 4.51.

Вправа 4.54.

Що таке елементи ідентичності в метричних просторах Ловера (тобто Cost -categories)? Як ми це інтерпретуємо з точки зору відстаней? ♦