4.3: Категорії Profunctors

Last updated
Save as PDF

Page ID: 66231

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

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

Складання профункторів

Якщо співвідношення доцільності повинні бути морфізмами, нам потрібно дати формулу для складання двох з них послідовно. Уявіть, що у вас є міста P, Q і R, і у вас є мости і, отже, матриці доцільності, що з'єднують ці міста, скажімо Φ: P → Q і ψ: Q → R.

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

Матриці доцільності для Φ (синім кольором) і ψ (червоним кольором) є:

$Знімок екрана 2021-01-17 в 1.59.49 PM.png$

Як і в Зауваження 2.95, ми уособлюємо кванту як навігатор. Отже, уявіть, що навігатор намагається дати матрицю здійсненності Φ; ψ для отримання від P до R. Як це робити? В основному, для кожної пари р $\in$Р і$\in$ р р, навігатор шукає через Q для точки шляху q, десь обидва до яких ми можемо отримати від р І з якого ми можемо дістатися до r. Це правда, що ми можемо орієнтуватися від p до r, якщо є точка шляху q, через яку подорожувати; це великий АБО над усіма можливими q. Формула складу таким чином:

$\left(\Phi_{9}^{\circ} \Psi\right)(p, r):=\bigvee_{q \in \mathbb{Q}} \Phi(p, q) \wedge \Psi(q, r)$(4.20)

Але, як ми говорили в Eq. (2.101), це можна розглядати як множення матриці. У нашому прикладі результат

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

і можна перевірити, що це відповідає на питання «чи можете ви дістатися звідси туди» в Eq. (4.19): ви не можете отримати від N до x, але ви можете отримати від N до y.

Формула (4.20) пишеться в терміні квантової Бул, але вона працює для довільних (одиничних комутативних) кількалей. Наведемо наступне визначення.

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

Нехай V є кванталлю, нехай X, Y і Z будуть V-категоріями, а Φ: X → Y і ψ: Y → Z бути V-профункторами.

Визначимо їх складові, що позначаються Φ; ψ: X → Z за формулою

$\left(\Phi_{9} \Psi\right)(p, r)=\bigvee_{q \in Q}(\Phi(p, q) \otimes \Psi(q, r))$

Вправа 4.22.

Розглянемо Вартість -profunctors Φ: X → Y і ψ: Y → Z, показані нижче:

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

Заповніть матрицю для складеного профунктора:

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

Категорії V - Професор і Фес

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

Нагадаємо з Зауваження 1.35, що попередній порядок є скелетним попереднім замовленням, якщо кожного разу, коли x ≤ y та y ≤ x, ми маємо x = y. Скелетні попередні замовлення також відомі як посети. Ми говоримо, що квантал є скелетним, якщо його основний попередній порядок є скелетним; Бул і Вартість - це скелетні квантали.

Теорема 4.23.

Для будь-якої скелетної кванталі V існує категорія Prof, об'єктами$_{V}$ якої є V-категорії X, морфізмами яких є V-профунктори X → Y, і з композицією, визначеною як у Визначенні 4.21.

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

Визначаємо Feas = проф$_{Bool}$.

На даний момент, можливо, у вас є два питання на увазі. Що таке морфізми ідентичності? І навіщо нам потрібно було спеціалізуватися на скелетних квантах? Виявляється, ці два питання тісно пов'язані між собою.

Визначити одиничний профунктор U$_{X}$: X → X на V-категорії X за формулою

U$_{X}$ (х, у) := Х (х, у) . (4,25)

Як ми це інтерпретуємо? Нагадаємо, що, за визначенням 2.46, X вже присвоює кожній парі елементів x, y$\in$ X хом-об'єкт X (x, y)$\in$ V. Модульний профунктор UX просто призначає кожній парі (x, y) той самий об'єкт.

У випадку Bool блок profunctor на деякому попередньому порядку X можна намалювати так:

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

Очевидно, що складання зв'язку доцільності з одиницею залишає його незмінним; це зміст Lemma 4.27.

Вправа 4.26.

Виберіть не надто просту категорію Cost X. Дайте діаграму у стилі моста для модульного профунктора U$_{X}$: X → X ♦

Лема 4.27.

Складання будь-якого профунктора Φ: P → Q з одиничним профунктором, U$_{P}$ або U$_{Q}$, повертає Φ:

$\mathrm{U}_{\mathcal{P}} \text { ; } \Phi=\Phi=\Phi_{\text {9 }}^{\circ} \mathrm{U}_{\mathrm{Q}}$

Доказ. Ми показуємо, що U$_{P}$; Φ = Φ тримає; доводячи Φ = Φ; U$_{Q}$ подібне. Виправте р$\in$ Р і q$\in$ Q. Оскільки V скелетний, для доказу рівності досить показати Φ ≤ U$_{P}$; Φ і U$_{P}$; Φ ≤ Φ. У нас один напрямок:

$\Phi(p, q)=I \otimes \Phi(p, q) \leq \mathcal{P}(p, p) \otimes \Phi(p, q) \leq \bigvee_{p_{1} \in P}\left(\mathcal{P}\left(p, p_{1}\right) \otimes \Phi\left(p_{1}, q\right)\right)=\left(\mathrm{U}_{\mathcal{P}} \text { ; } \Phi\right)(p, q)$(4,28)

Для іншого напрямку ми повинні показати$\bigvee_{p1 \(\in$ P}\) (P (p, p$_{1}$) Φ (p$_{1}$, q)) ≤ Φ (p, q).

Але за визначенням об'єднання це тримає, якщо P (p, p$_{1}$) Φ (p$_{1}$, q) ≤ Φ (p, q) вірно для кожного p$_{1}$$\in$ P. Це випливає з визначень 2.46 та 4.8:

$\mathcal{P}\left(p, p_{1}\right) \otimes \Phi\left(p_{1}, q\right)=\mathcal{P}\left(p, p_{1}\right) \otimes \Phi\left(p_{1}, q\right) \otimes I \leq \mathcal{P}\left(p, p_{1}\right) \otimes \Phi\left(p_{1}, q\right) \otimes 2(q, q) \leq \Phi(p, q)$(4,29)$\square$

Вправа 4.30.

Обґрунтуйте кожен з чотирьох кроків (=, ≤, ≤, =) в еквалайзері (4.28).
У випадку V = Bool, ми можемо безпосередньо показати кожен з чотирьох кроків в еквалайзері. (4.28) насправді рівність. Як?
Вирівняти кожен з трьох кроків (=, ≤, ≤) в еквалайзері (4.29) . ♦

Склад профункторів також асоціативний; ми залишаємо вам доказ.

Лема 4.3.1.

Серійний склад профункторів асоціативний. Тобто, задані профунктори Φ: P → Q, ψ: Q → R, і: R → S, ми маємо

(Φ; Ψ); У = Φ; (Ψ; У)

Вправа 4.3.2.

Доведіть Лемма 4.31. (Підказка: не забудьте використовувати той факт, що V є скелетним. ) ♦

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

$Знімок екрана 2021-01-17 в 2.42.15 PM.png$

З іншого боку, ми бачили, що техніко-економічні відносини є складовими проблем спільного проектування, і ми знаємо, що проблеми спільного проектування можуть бути зображені з набагато багатшою схемою підключення, наприклад:

$Знімок екрана 2021-01-17 в 2.42.52 PM.png$

Це натякає на те, що категорія Feas має більшу структуру. Ми бачили схеми підключення, де коробки можуть мати кілька входів і виходів раніше, в розділі 2; там вони зображували морфізми в моноїдальному попередньому порядку. З іншого боку, коробки на монтажних схемах глави 2 не могли мати чітких міток, як коробки в проблемі спільного проектування: всі коробки в монтажній схемі для моноїдальних попередніх замовлень вказують порядок ≤, тоді як вище ми бачимо коробки, позначені «шасі», «Двигун» тощо. Так само ми знаємо, що Feas - це належна категорія, а не просто попереднє замовлення. Щоб зрозуміти ці діаграми тоді, ми повинні ввести нову структуру, яка називається моноїдальною категорією. Моноїдальна категорія - це категоризований моноїдальний попередній порядок.

Зауваження 4.33. Хоча ми вирішили визначити Проф$_{V}$ лише для скелетних кванталів у теоремі 4.23, працювати з нескелетними не надто важко. Є два прямих- вперед способи зробити це. По-перше, ми можемо дозволити морфізмам Prof$_{V}$ бути класами ізоморфізму V-профункторів. Це аналогічно трюку, який ми будемо використовувати при визначенні категорії Коспан$_{C}$ в Definition 6.45. По-друге, ми можемо розслабити те, що ми маємо на увазі під категорією, лише вимагаючи, щоб композиція була єдиною та асоціативною «аж до ізоморфізму». Це також тип категоризації, відомий як теорія бікатегорій.

У наступному розділі ми обговоримо категоризацію та введемо моноїдальні категорії. По-перше, ми закінчимо цей розділ, обговорюючи, чому profunctors називаються profunctors, і формально вводячи щось називається колаж profunctor.

Веселі факти про профункторів: компаньйони, сукупності, колажі

Компаньйони і сполучники. Нагадаємо, що попередній порядок - це категорія Bool, а монотонна карта - це Bool -функтор. Ми говорили вище, що profunctor - це узагальнення функтора; як так?

Насправді кожен V-функтор породжує два V-профунктори, звані компаньйоном і кон'юнктором.

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

Нехай F: P → Q буде V-функтором. Супутник F, позначається$widehat{F}$: P → Q і сукупність$widehat{F}$, позначається$\breve{F}$: Q P визначаються наступними V-профункторами:

$\widehat{F}(p, q):=Q(F(p), q) \text { and } \breve{F}(q, p):=Q(q, F(p))$

Давайте ще раз розглянемо справу Bool.

Можна думати про монотонну карту F: P → Q як купу стрілок, одна з яких виходить з кожної вершини p$\in$ P і приземляється на деякій вершині F (p)$\in$ Q.

$Знімок екрана 2021-01-17 в 2.53.48 PM.png$

Це виглядає як фотографії мостів, що з'єднують міста, і якщо розглядати наведену вище картину в цьому світлі, вони бачать супутника$\widehat{F}$. Але тепер подумки переверніть кожну пунктирну стрілку, і в результаті будуть мости Q до P. Це профунктор Q → P! Ми називаємо це$\breve{F}$.

Приклад 4.35.

Для будь-якого попереднього порядку P існує ідентифікаційний функтор id: P → P. Його супутник і сполучений згодні$\widehat{id}$ =$\breve{id}$: P → P. Результуючий профунктор фактично є одиничним профунктором U$_{P}$, як визначено в екв. (4.25).

Приклад 4.36.

Переконайтеся, що$\widehat{id}$ супутник id: P → P дійсно має формулу одиничного профунктора, наведену в еквалайзері (4.25) . ♦

Приклад 4.37.

Розглянемо функцію +:$\mathbb{R}$ ×$\mathbb{R}$ ×$\mathbb{R}$ →$\mathbb{R}$, посилаючи трійку (a, b, c) дійсних чисел в a + b + c$\in$ $\mathbb{R}$.

Ця функція монотонна, тому що якщо (a, b, c) ≤ (a ′, b ′, c ′) —тобто якщо a ≤ a і b ≤ b, а c ≤ c то очевидно a + b + c ≤ a + b + c. При цьому у нього є компаньйон і супутник.

Його супутник$\widehat{+}$: ($\mathbb{R}$×$\mathbb{R}$ ×$\mathbb{R}$) →$\mathbb{R}$ є функцією, яка посилає (a, b, c, d) до true, якщо a + b + c ≤ d і false інакше.

Вправа 4.38.

Нехай +:$\mathbb{R}$ ×$\mathbb{R}$ ×$\mathbb{R}$ →$\mathbb{R}$ буде таким, як у прикладі 4.37. Що таке його сполучна$\breve{+}$? ♦

Зауваження 4.39 (V-сумісні). Нагадаємо з визначення 1.95 визначення Галуа connec- tion між попередніми замовленнями P і Q. визначення примикання може бути розширено від збагаченого Bool налаштування (попередніх замовлень і монотонних карт) до V-збагаченого налаштування для довільних моноїдальних попередніх порядків V. У цьому випадку визначення V -adjunction є парою V-функторів F: P → Q і G: Q → P такі, що наступні тримають для всіх p$\in$ P і q$\in$ Q.

Р (р, Г (q))$\cong$ Q (Ф (р), q) (4,40)

Вправа 4.41.

Нехай V — скелетна кванта, нехай P та Q — V-категоріями, а F: P → Q та G: Q → P — V-функторами.

Показати, що F і G є V-подібними з'єднаннями (як у Eq. (4.40)) тоді і тільки тоді, коли супутник q першого дорівнює з'єднанню останнього:$\widehat{F}$ =$\breve{G}$.
Використовуйте це, щоб довести, що$\widehat{id}$ =$\breve{id}$, як було зазначено в прикладі 4.35. ♦

Колаж з профунктора. Ми малювали профунктори як мости, що з'єднують міста. Можна отримати інклювання, яке, враховуючи V-профунктор Φ: X → Y між V-категоріями X і Y, ми перетворили Φ на якусь нову V-категорію, яка має X зліва та Y праворуч. Це працює для будь-якого V і profunctor Φ, і називається конструкцією колажу.

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

Дозвольте V бути квантовою, нехай X і Y будуть V-категоріями, а Φ: X → Y бути V-профунктором. Колаж Φ, позначений Col (Φ) - це V-категорія, визначена наступним чином:

(i) Об (Col (Φ)) := Ob (X) Ob (Y);
(ii) Для будь-якого a, b$\in$ Ob (Col (Φ)) визначте Col (Φ) (a, b)$\in$ V, щоб бути

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

Існують очевидні функтори$i_{x}$: X → Col (Φ) і$i_{y}$: Y → Col (Φ), що посилають кожен об'єкт і морфізм на «себе», звані колажними включеннями.

Деякі картинки допоможуть це прояснити.

Приклад 4.43.

Розглянемо наступну картину вартості -profunctor Φ: X → Y:

$Знімок екрана 2021-01-17 в 3.39.34 PM.png$

Він відповідає наступним матрицям

$Знімок екрана 2021-01-17 в 3.40.07 PM.png$

Узагальнену діаграму Хассе колажу можна отримати, просто взявши об'єднання діаграм Хассе для X і Y, і додаючи в мости як стрілки. З огляду на вищевказаний профунктор Φ, намалюємо діаграму Хассе для Col (Φ) внизу зліва, а справа - матричне представлення Cost -категорії Cost:

Вправа 4.44.

Намалюйте діаграму Хассе для колажу профунктора, показаного тут:

$Знімок екрана 2021-01-17 в 3.48.09 PM.png$