6.5: Опери та їх алгебри

Last updated
Save as PDF

Page ID: 66313

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

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

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

Щоб завершити наше обговорення композиційних структур, ми хочемо швидко намалювати щось, що ми можемо використовувати як якусь метакомпозиційну структуру, відому як опера. Ми побачили в розділі 6.4.3, що ми можемо будувати електричні ланцюги з симетричного моноїдального функтора FinSet → Set. Так само ми побачимо, що ми можемо побудувати приклади нових алгебраїчних структур з оперних функцій O → множина.

Схеми розводки опери

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

Однак одним, можливо, незадовільним результатом є те, що категорія гіперграфа intro- duces артефакти, такі як область і кодомен ланцюга, які не притаманні структурі схем або їх складу. Схеми просто мають єдиний межовий інтерфейс, а не «домени» та «кодомени». Це не означає, що вищевказана модель не є корисною: у багатьох додатках векторний простір не має бажаної основи, але часто корисно вибрати таку, щоб ми могли використовувати матриці (або графіки потоку сигналів!). Але варто було б мати категорії-теоретичну модель, яка більш безпосередньо представляє композиційну структуру схем. Загалом, ми хочемо, щоб теоретико-категорія модель відповідала нашому бажаному додатку, як рукавичка. Давайте швидко накидаємо, як це можна зробити.

Повернемося на секунду до монтажних схем. Ми побачили, що схеми підключення для категорій гіперграфів в основному виглядають так:

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

Зверніть увагу, що якщо у вас була коробка з A і B зліва і D праворуч, ви могли б підключити наведену вище схему прямо всередині неї, і отримати новий розімкнутий ланцюг. Це основний хід опер.

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

$Знімок екрана 2021-01-24 в 7.53,15 PM.png$

Ви бачите, як діаграми Eq. (6.89) та Eq. (6.90) насправді однакові в

умови взаємозв'язку шаблону? Єдина відмінність полягає в тому, що останній не має різниці вліво/вправо: ми втратили саме те, що хотіли втратити.

Вартість полягає в тому, що «коробки» f, g, h, k в еквалайзері (6.90) більше не мають лівого/правого dis-tinction; вони просто кола зараз. Це не було б погано, за винятком того, що це означає, що вони більше не можуть представляти морфізми в категорії - як раніше, в еквалайзері (6.89), оскільки морфізми в категорії за визначенням мають домен і кодомен. Наші нові кола не мають такої відмінності. Тож тепер нам потрібен абсолютно новий спосіб категорично думати про «коробки»: якщо вони більше не є морфізмами в категорії, які вони? Відповідь зустрічається в теорії опери.

Розуміючи опери, ми виявимо, що нам потрібно орієнтуватися в одному зі зрушень рівня, про які ми вперше обговорювали в розділі 1.4.5. Зверніть увагу, що для оформлених коспанів ми визначаємо категорію гіперграфа за допомогою симетричного моноїдального функтора. Це нагадує наше коротке обговорення алгебраїчних теорій у розділі 5.4.2, де ми визначили щось, що називається теорією моноїдів як проп М, і визначаємо моноїди за допомогою функторів M → Set; див. Зауваження 5.74.

Таким же чином ми можемо розглядати категорію Коспан$_{FinSet}$ як якусь «теорію категорій гіперграфа», і таким чином визначити категорії гіперграфа як функтори Коспан$_{FinSet}$ → Множина.

Ось і ідея. Операда O визначатиме теорію або граматику композиції, а операційні функції O → Set, відомі як O -алгебри, описуватимуть конкретні програми, які підкоряються цій граматиці.

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

Щоб вказати операційну операцію,

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

(ii) для кожного кортежу (t$_{1}$,..., t$_{n}$, t) типів вказується множина O (t$_{1}$,..., t$_{n}$; t), елементи якого називаються операціями арності (t$_{1}$,.,., т$_{n}$; т);

(iii) для кожної пари кортежів (s$_{1}$,...$_{m}$, s, t$_{i}$) і (t$_{1}$,...$_{n}$, t, t) вказується функція

◦$_{i}$: О (с$_{1}$,..., с$_{m}$; т$_{i}$) × О (т$_{1}$,..., т$_{n}$; т) → О (т$_{1}$,..., т$_{i-1}$, с$_{1}$,..., с $_{m}$, т$_{i+1}$,..., т$_{n}$; т);

називається заміщенням; і

(iv) для кожного типу t вказується операція id$_{t}$ $\in$O (t; t), яка називається операцією ідентичності.

Вони повинні підкорятися узагальненим законам ідентичності та асоціативності.

Давайте на мить ігноруємо типи і подумаємо, що моделює ця структура. Інтуїція полягає в тому, що опера складається з, для кожного n, набору операцій парності в тобто всіх операціях, які приймають n аргументів. Якщо взяти операцію f парності m і підключити вивід до i -го аргументу операції g з парністю n, ми отримаємо операцію парності m + n − 1: у нас є m аргументів для заповнення m, а інші n − 1 аргументи заповнити m. Яку операцію арності m + n − 1 ми отримаємо? Це описується функцією підстановки ◦$_{i}$, яка говорить, що ми отримуємо операцію f ◦$_{i}$ g$\in$ O (m + n − 1). Умови когерентності говорять про те, що ці функції ◦$_{i}$ фіксують наступну інтуїтивну картину:

$Знімок екрана 2021-01-25 о 11.22.46 AM.png$

Типи потім дозволяють нам вказати, ну, типи аргументів входів, які приймає кожна функція. Отже, приготування чаю - це 2-арна операція, операція з arity 2, тому що це займає дві речі. Для приготування чаю потрібно трохи теплої води, а вам потрібно трохи заварки.

Приклад 6.92.

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

Щоб визначити граматику без контексту на якомусь алфавіті, можна вказати деякі правила виробництва, які говорять про те, як сформувати сутність у деякій синтаксичній категорії з купи сутностей в інших синтаксичних категоріях. Наприклад, ми можемо сформувати іменну фразу з визначника (The), прикметника (щасливого) та іменника (хлопчика). Контекстні вільні граматики важливі як у лінгвістиці, так і в інформатиці. У першому вони є основним способом говорити про структуру речень природними мовами. В останньому вони мають вирішальне значення при розробці аналізаторів для мов програмування.

Так само, як графіки представляють безкоштовні категорії, контекстні граматики представляють безкоштовні опери. Ця ідея вперше була помічена в [HMP98].

Опери з симетричних моноїдальних категорій

У Визначенні 6.97 ми побачимо, що великий клас оперд походить від симетричних моноїдальних категорій. Перш ніж пояснити це, наведемо пару прикладів. Мабуть, найважливіша опера - це Сет.

Приклад 6.93.

Опера Набір наборів має

(i) Встановлює X як типи.

(ii) Функції X$_{1}$ × ··· × X$_{n}$ → Y як операції орності (X$_{1}$,..., X$_{n}$; Y).

(iii) Заміна, визначена

(g ◦$_{i}$ f) (х$_{1}$,..., х$_{i-1}$, ш$_{1}$,..., ш$_{m}$, х$_{i+1}$,..., х$_{n}$)
= г ( х$_{1}$,..., х$_{i-1}$, ф (ш$_{1}$,..., ш$_{m}$), х$_{i+1}$,..., х$_{n}$

де f$\in$ Set (W$_{1}$,..., W$_{m}$; X$_{i}$), g$\in$ Набір (X$_{1}$,..., X$_{n}$; Y), а отже, g ◦ $_{i}$f - функція

(g ◦$_{i}$ f): Х$_{1}$ × ··· × Х$_{i-1}$ × Ш$_{1}$ × ···Ш × Ш$_{m}$ $_{i+1}$× Х × ·· × Х$_{n}$ → У

(iv) Ідентифікатори id$_{X}$ $\in$Set (X; X) задаються ідентифікаційною функцією id$_{X}$: X → X.

Далі ми наведемо приклад, який нагадує нам, для чого вся ця опера: схеми підключення.

Приклад 6.94.

Опера Коспан скінченної множини коспанів має

(i) Натуральні числа a$\in$$\mathbb{N}$ як типи.

(ii) Коспани a$\underline{_{1}}$ + ··+ a$\underline{_{n}}$ → p ← b скінченних множин як операції орності (a$_{1}$,..., a$_{n}$; b).

(iii) Заміна, визначена pushout.

(iv) Ідентифікатори$_{a}$ $\in$встановлюються (a; a) щойно задані ідентифікатором cospan$\underline{a}$\ stackrel {id$_{\underline{a}}$ {\ rightarrow}$\underline{a}$\ stackrel {id$_{\underline{a}}$} {\ leftarrow}$\underline{a}$\).

Це оперний аналог моноїдальної категорії (Коспан$_{FinSet}$, 0, +).

Ми можемо зобразити операції в цій опері за допомогою діаграм, як ми намалювали вище. Наприклад, ось картинка операції:

$Знімок екрана 2021-01-25 о 11.55.06 AM.png$

Це операція арності ($\underline{3}$,$\underline{3}$,$\underline{4}$,$\underline{2}$; 3). Чому? Кола, позначені f і g, мають 3 порти, h має 4 порти, k має 2 порти, а зовнішнє коло має 3 порти: 3, 3, 4, 2; 3.

Так як саме Eq. (6.95) морфізм в цій опері?

Ну і морфізм цього$\underline{3}$ +$\underline{3}$$\underline{4}$ +$\underline{2}$\ stackrel {a} {\ rightarrow}\ підкреслення {p}\ stackrel {b} {\ leftarrow}\ підкреслення {3}\).

На схемі вище вершина$\underline{p}$ - це безліч$\underline{7}$, тому що на схемі 7 вузлів •. Функція a надсилає кожен порт на одному з малих кіл до вузла, до якого він підключається, а функція b надсилає кожен порт зовнішнього кола до вузла, до якого він підключається.

Ми можемо зобразити кожну операцію в опері Коспан у вигляді схеми підключення. Часто корисно думати про опери як про опис граматики електричної схеми. Операція підстановки опери означає вставлення однієї схеми підключення в коло або коробку в іншій схемі підключення.

Вправа 6.96.

1. Розглянемо наступний коспан$\in$ Коспана (2, 2; 2):

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

Намалюйте його як схему підключення з двома внутрішніми колами, кожен з двома портами, і одним зовнішнім колом з двома портами.

2. Намалюйте схему підключення, відповідну наступним коспан g$\in$ Cospan (2, 2, 2; 0):

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

3. Обчислити коспан g ◦$_{1}$ f. У чому його рідкість?

4. Намалюйте коспан g ◦$_{1}$ f. Ви бачите це як заміну? ♦

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

Визначення 6.97.

Для будь-якої симетричної моноїдальної категорії (C, I,) існує опера O, звана операдою$_{C}$, що лежить в основі C, визначена як має:

(i) Про (С) як типи.

(ii)$_{1}$ морфізми C ··· C$_{n}$ → D в С як операції арності (C$_{1}$,..., C$_{n}$; D).

(iii) заміщення визначається

(f ◦$_{i}$ g) := f ◦ (id,..., id, g, id,..., id)

(iv) ідентичності id$_{a}$ $\in$O$_{C}$ (a; a), визначені ідентифікатором$_{a}$.

Ми також можемо перетворити будь-який моноїдальний функтор в те, що називається функтором опери.

Опера для реквізиту гіперграфа

Функтор опери приймає типи однієї опери до типів іншої, а потім операції першої до операцій другої таким чином, що поважає це.

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

Припустимо, задано дві операди O і P з колекціями типів T і U відповідно. Щоб вказати операційний функтор F: O → P,

(i) задає функцію f: T → U.
(ii) Для всіх $_{1}$орiтацій (t,., t$_{n}$; t) в O вказується функція

Ф: О (т$_{1}$,..., т$_{n}$; т) → П (ф (т$_{1}$$_{n}$),..., ф (т))

таким чином, що композиція та ідентичність зберігаються.

Так само, як множинні функтори C → Набір з будь-якої категорії C представляють особливий інтерес— ми бачили їх як екземпляри бази даних у розділі 3 так, щоб встановити -значні функції O → Набір з будь-якої опери O.

Визначення 6.99.

Алгеброю опери O є операційний функтор F: O → множина.

Ми можемо думати про функтори O → Set як визначення набору можливих способів заповнення полів у монтажній схемі. Дійсно, кожна коробка в монтажній схемі представляє тип t даної опери O, а алгебра F: O → Set прийме тип t і поверне набір F (t) наповнювачів для коробки t. Причому, задавши операцію (тобто схему підключення) f$\in$ O (t 1,., t n; t; t), отримаємо функцію F (f), яка приймає елемент кожної множини F (t i), і повертає елемент F (t). Наприклад, він приймає n ланцюгів з інтерфейсом t 1,., t n відповідно, і повертає ланцюг з межею t.

Приклад 6.100.

Для електричних ланцюгів типи - це знову кінцеві множини, T = Ob (FinSet), де кожній скінченній множині$\in$ t T відповідає комірці з t портами. Так само, як і раніше, у нас є набір Circ (t) наповнювачів, а саме набір електричних ланцюгів з цим t -маркованими клемами. Як оперна алгебра, Circ: Cospan → Set перетворює схеми підключення, як ця

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

в формули, які будують нову схему з купи існуючих.

У намальованому вище випадку ми отримаємо морфізм Circ (φ)$\in$ Set (Circ (2), Circ (2), Circ (2); Circ (0)), тобто функцію

Коло (φ): Коло (2) × Коло (2) × Коло (2) → Коло (0).

Ми могли б застосувати цю функцію до трьох елементів Circ (2), показаних тут

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

і результатом буде замкнутий контур з початку глави:

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

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

Пропозиція 6.101.

Існує еквівалентність між Коспаном -алгебрами і реквізитом гіперграфа.

Ще однією перевагою використання операд є те, що можна варіювати саму оперу, від Коспана до чогось подібного (наприклад, опери «кобордизмів»), і отримати дещо інші правила композиційності.

Насправді опери з додатковою складністю в їх визначенні - можуть бути cus-tomized навіть більше, ніж всі композиційні структури, визначені досі. Наприклад, ми можемо визначити опери електричних схем, де схеми підключення повинні відповідати точним умовам набагато більш конкретним, ніж обмеження категорії, наприклад, вимагати, щоб сама схема не мала проводів, які проходять прямо через неї. Насправді опери досить сильні, щоб визначити себе: грубо кажучи, існує операда для оперд: категорія оперд еквівалентна категорії алгебр для певної опери [Lei04, Приклад 2.2.23]. Хоча опери, звичайно, можна знову узагальнити, вони завершують наш хід через неформальну ієрархію композиційних структур, від попередніх замовлень до категорій до моноїдальних категорій до оперд.