Диаграмма струны

Диаграммы строк — это формальный графический язык для представления морфизмов в моноидальных категориях или, в более общем смысле, 2-ячеек в 2-категориях . Они являются важным инструментом в прикладной теории категорий . При интерпретации в моноидальной категории векторных пространств и линейных отображений с тензорным произведением диаграммы строк называются тензорными сетями или графической нотацией Пенроуза . Это привело к развитию категориальной квантовой механики , в которой аксиомы квантовой теории выражаются на языке моноидальных категорий.

История

Гюнтер Хотц дал первое математическое определение струнных диаграмм для формализации электронных схем . ^[1] Однако изобретение струнных диаграмм обычно приписывают Роджеру Пенроузу , ^[2] а диаграммы Фейнмана также описывают как предшественников. ^[3] Позднее они были охарактеризованы как стрелки свободных моноидальных категорий в основополагающей статье Андре Джояля и Росса Стрита . ^[4] Хотя диаграммы в этих первых статьях были нарисованы от руки, появление программного обеспечения для набора текста, такого как LaTeX и PGF/TikZ, сделало публикацию струнных диаграмм более распространенной. ^[5]

Экзистенциальные графы и диаграммные рассуждения Чарльза Сандерса Пирса, возможно, являются старейшей формой струнных диаграмм, они интерпретируются в моноидальной категории конечных множеств и отношений с декартовым произведением . ^[6] Линии тождества экзистенциальных графов Пирса могут быть аксиоматизированы как алгебра Фробениуса , разрезы являются унарными операторами на homsets, которые аксиоматизируют логическое отрицание . Это делает струнные диаграммы надежной и полной двумерной системой вывода для логики первого порядка , ^[7] изобретенной независимо от одномерного синтаксиса Begriffsschrift Готтлоба Фреге .

Интуиция

Диаграммы строк состоят из коробок , которые представляют процессы , со списком проводов, входящих сверху и снизу, которые представляют входные и выходные системы , обрабатываемые коробкой . Начиная с набора проводов и коробок, называемых сигнатурой , можно сгенерировать набор всех диаграмм строк по индукции: ${\displaystyle f:x\to y}$ ${\displaystyle x}$ ${\displaystyle y}$ ${\displaystyle f}$

• каждый ящик представляет собой диаграмму строки, ${\displaystyle f:x\to y}$
• для каждого списка проводов идентификатор представляет собой строковую диаграмму, представляющую процесс, который ничего не делает с его входной системой, он изображен как пучок параллельных проводов, ${\displaystyle x}$ ${\displaystyle {\text{id}}(x):x\to x}$
• для каждой пары диаграмм струн и их тензор является диаграммой струн, представляющей параллельную композицию процессов, она изображается как горизонтальная конкатенация двух диаграмм, ${\displaystyle f:x\to y}$ ${\displaystyle f':x'\to y'}$ ${\displaystyle f\otimes f':xx'\to yy'}$
• для каждой пары диаграмм строк и их композиция представляет собой диаграмму строк, представляющую последовательную композицию процессов, она рисуется как вертикальная конкатенация двух диаграмм. ${\displaystyle f:x\to y}$ ${\displaystyle g:y\to z}$ ${\displaystyle g\circ f:x\to z}$

Определение

Алгебраический

Пусть звезда Клини обозначает свободный моноид , т.е. множество списков с элементами в множестве . ${\displaystyle X^{\star }}$ ${\displaystyle X}$

Моноидальная сигнатура задается следующим образом: ${\displaystyle \Sigma }$

• набор генерирующих объектов , списки генерирующих объектов также называются типами , ${\displaystyle \Sigma _{0}}$ ${\textstyle \Sigma _{0}^{\star }}$
• набор генерирующих стрелок , также называемых ящиками , ${\displaystyle \Sigma _{1}}$
• пара функций , которые назначают домен и кодомен каждому блоку, т.е. типы входа и выхода. ${\displaystyle {\text{dom}},{\text{cod}}:\Sigma _{1}\to \Sigma _{0}^{\star }}$

Морфизм моноидальной сигнатуры — это пара функций и , совместимая с областью и кодоменом, т.е. такая, что и . Таким образом, мы получаем категорию моноидальных сигнатур и их морфизмов. ${\displaystyle F:\Sigma \to \Sigma '}$ ${\displaystyle F_{0}:\Sigma _{0}\to \Sigma '_{0}}$ ${\displaystyle F_{1}:\Sigma _{1}\to \Sigma '_{1}}$ ${\displaystyle {\text{dom}}\circ F_{1}\ =\ F_{0}\circ {\text{dom}}}$ ${\displaystyle {\text{cod}}\circ F_{1}\ =\ F_{0}\circ {\text{cod}}}$ ${\displaystyle \mathbf {MonSig} }$

Существует забывающий функтор , который отправляет моноидальную категорию в свою базовую сигнатуру и моноидальный функтор в свой базовый морфизм сигнатур, т. е. он забывает тождество, композицию и тензор. Свободный функтор , т. е. левый сопряженный к забывающему функтору, отправляет моноидальную сигнатуру в свободную моноидальную категорию, которую он генерирует. ${\displaystyle U:\mathbf {MonCat} \to \mathbf {MonSig} }$ ${\displaystyle C_{-}:\mathbf {MonSig} \to \mathbf {MonCat} }$ ${\displaystyle \Sigma }$ ${\displaystyle C_{\Sigma }}$

Диаграммы строк (с генераторами из ) являются стрелками в свободной моноидальной категории . ^[8] Интерпретация в моноидальной категории определяется моноидальным функтором , который по свободе однозначно определяется морфизмом моноидальных сигнатур . Интуитивно, как только дан образ порождающих объектов и стрелок, образ каждой диаграммы, которую они порождают, фиксируется. ${\displaystyle \Sigma }$ ${\displaystyle C_{\Sigma }}$ ${\displaystyle D}$ ${\displaystyle F:C_{\Sigma }\to D}$ ${\displaystyle F:\Sigma \to U(D)}$

Геометрический

Топологический граф , также называемый одномерным клеточным комплексом , представляет собой кортеж хаусдорфова пространства , замкнутого дискретного подмножества узлов и набора связных компонент, называемых ребрами , каждый из которых гомеоморфен открытому интервалу с границей в и такому, что . ${\displaystyle (\Gamma ,\Gamma _{0},\Gamma _{1})}$ ${\displaystyle \Gamma }$ ${\displaystyle \Gamma _{0}\subseteq \Gamma }$ ${\displaystyle \Gamma _{1}}$ ${\displaystyle \Gamma _{0}}$ ${\textstyle \Gamma -\Gamma _{0}=\coprod \Gamma _{1}}$

Плоский граф между двумя действительными числами с — это конечный топологический граф, вложенный в , так что каждая точка также является узлом и принадлежит замыканию ровно одного ребра в . Такие точки называются внешними узлами , они определяют домен и кодомен диаграммы строки, т.е. список ребер, которые соединены с верхней и нижней границей. Остальные узлы называются внутренними узлами . ${\displaystyle a,b\in \mathbb {R} }$ ${\displaystyle a<b}$ ${\displaystyle \mathbb {R} \times [a,b]}$ ${\displaystyle x\in \Gamma \ \cap \ \mathbb {R} \times \{a,b\}}$ ${\displaystyle x\in \Gamma _{0}}$ ${\displaystyle \Gamma _{1}}$ ${\displaystyle {\text{dom}}(\Gamma ),{\text{cod}}(\Gamma )\in \Gamma _{1}^{\star }}$ ${\displaystyle f\in \Gamma _{0}\ -\ \{a,b\}\times \mathbb {R} }$

Плоский граф является прогрессивным , также называемым лежачим , когда вертикальная проекция инъективна для каждого ребра . Интуитивно, ребра в прогрессивном плоском графе идут сверху вниз без изгиба назад. В этом случае каждому ребру можно задать ориентацию сверху вниз с обозначенными узлами как источник и цель. Затем можно определить домен и кодомен каждого внутреннего узла , заданные списком ребер, которые имеют источник и цель. ${\displaystyle e\to [a,b]}$ ${\displaystyle e\in \Gamma _{1}}$ ${\displaystyle {\text{dom}}(f),{\text{cod}}(f)\in \Gamma _{1}^{\star }}$ ${\displaystyle f}$

Плоский граф является общим , когда вертикальная проекция инъективна, т.е. никакие два внутренних узла не находятся на одной высоте. В этом случае можно определить список внутренних узлов, упорядоченных сверху вниз. ${\displaystyle \Gamma _{0}-\{a,b\}\times \mathbb {R} \to [a,b]}$ ${\displaystyle {\text{boxes}}(\Gamma )\in \Gamma _{0}^{\star }}$

Прогрессивный плоский граф помечается моноидальной сигнатурой, если он снабжен парой функций от ребер до генерирующих объектов и от внутренних узлов до генерирующих стрелок, совместимым с доменом и кодоменом способом. ${\displaystyle \Sigma }$ ${\displaystyle v_{0}:\Gamma _{1}\to \Sigma _{0}}$ ${\displaystyle v_{1}:\Gamma _{0}-\{a,b\}\times \mathbb {R} \to \Sigma _{1}}$

Деформация плоских графов — это непрерывное отображение, такое что ${\displaystyle h:\Gamma \times [0,1]\to [a,b]\times \mathbb {R} }$

• изображение определяет плоский график для всех , ${\displaystyle h(-,t)}$ ${\displaystyle t\in [0,1]}$
• для всех , если является внутренним узлом для некоторых, то он является внутренним для всех . ${\displaystyle x\in \Gamma _{0}}$ ${\displaystyle h(x,t)}$ ${\displaystyle t}$ ${\displaystyle t\in [0,1]}$

Деформация является прогрессивной (общей, помеченной), если является прогрессивной (общей, помеченной) для всех . Деформации индуцируют отношение эквивалентности с тогда и только тогда, когда существует некоторое с и . Диаграммы строк являются классами эквивалентности помеченных прогрессивных плоских графов . Действительно, можно определить: ${\displaystyle h(-,t)}$ ${\displaystyle t\in [0,1]}$ ${\displaystyle \Gamma \sim \Gamma '}$ ${\displaystyle h}$ ${\displaystyle h(-,0)=\Gamma }$ ${\displaystyle h(-,1)=\Gamma '}$

• диаграмма идентичности как набор параллельных ребер, помеченных некоторым типом , ${\displaystyle {\text{id}}(x)}$ ${\displaystyle x\in \Sigma _{0}^{\star }}$
• композиция двух диаграмм как их вертикальная конкатенация, при этом область значений первой отождествляется с областью значений второй,
• тензор двух диаграмм как их горизонтальная конкатенация.

Комбинаторный

В то время как геометрическое определение делает явной связь между теорией категорий и низкоразмерной топологией , комбинаторное определение необходимо для формализации диаграмм строк в системах компьютерной алгебры и использования их для определения вычислительных задач . Одним из таких определений является определение диаграмм строк как классов эквивалентности хорошо типизированных формул, сгенерированных сигнатурой, тождеством, композицией и тензором. На практике удобнее кодировать диаграммы строк как формулы в общей форме , которые находятся во взаимной связи с помеченными общими прогрессивными плоскими графами, определенными выше.

Исправьте моноидальную сигнатуру . Слой определяется как тройка типа слева, ящика посередине и типа справа. У слоев есть домен и кодомен, определенные очевидным образом. Это образует направленный мультиграф , также известный как колчан , с типами в качестве вершин и слоями в качестве ребер. Диаграмма строк кодируется как путь в этом мультиграфе , т. е. она задается как: ${\displaystyle \Sigma }$ ${\displaystyle (x,f,y)\in \Sigma _{0}^{\star }\times \Sigma _{1}\times \Sigma _{0}^{\star }=:L(\Sigma )}$ ${\displaystyle x}$ ${\displaystyle f}$ ${\displaystyle y}$ ${\displaystyle {\text{dom}},{\text{cod}}:L(\Sigma )\to \Sigma _{0}^{\star }}$ ${\displaystyle d}$

• домен как отправная точка ${\displaystyle {\text{dom}}(d)\in \Sigma _{0}^{\star }}$
• длина , ${\displaystyle {\text{len}}(d)=n\geq 0}$
• список ${\displaystyle {\text{layers}}(d)=d_{1}\dots d_{n}\in L(\Sigma )}$

такой что и для всех . Фактически, явный список слоев избыточен, достаточно указать длину типа слева от каждого слоя, известную как смещение . Усы диаграммы по типу определяются как конкатенация справа от каждого слоя и симметрично для усов слева. Затем можно определить: ${\displaystyle {\text{dom}}(d_{1})={\text{dom}}(d)}$ ${\displaystyle {\text{cod}}(d_{i})={\text{dom}}(d_{i+1})}$ ${\displaystyle i<n}$ ${\displaystyle d\otimes z}$ ${\displaystyle d=(x_{1},f_{1},y_{1})\dots (x_{n},f_{n},y_{n})}$ ${\displaystyle z}$ ${\displaystyle d\otimes z=(x_{1},f_{1},y_{1}z)\dots (x_{n},f_{n},y_{n}z)}$ ${\displaystyle z\otimes d}$

• диаграмма идентичности с и , ${\displaystyle {\text{id}}(x)}$ ${\displaystyle {\text{len}}({\text{id}}(x))=0}$ ${\displaystyle {\text{dom}}({\text{id}}(x))=x}$
• композиция двух диаграмм как конкатенация их списка слоев,
• тензор двух диаграмм как композиция усов . ${\displaystyle d\otimes d'=d\otimes {\text{dom}}(d')\ \circ \ {\text{cod}}(d)\otimes d'}$

Обратите внимание, что поскольку диаграмма имеет общую форму (т.е. каждый слой содержит ровно один блок), определение тензора обязательно смещено: диаграмма слева находится выше диаграммы справа. Можно было бы выбрать противоположное определение . ${\textstyle d\otimes d'={\text{dom}}(d)\otimes d'\ \circ \ d\otimes {\text{cod}}(d')}$

Две диаграммы равны (с точностью до аксиом моноидальных категорий), когда они находятся в одном и том же классе эквивалентности отношения конгруэнтности, генерируемого посредником : То есть, если блоки в двух последовательных слоях не соединены, то их порядок можно поменять местами. Интуитивно понятно, что если между двумя параллельными процессами нет связи, то порядок, в котором они происходят, не имеет значения. $${\displaystyle d\otimes {\text{dom}}(d')\ \circ \ {\text{cod}}(d)\otimes d'\quad =\quad {\text{dom}}(d)\otimes d'\ \circ \ d\otimes {\text{cod}}(d')}$$

Проблема слов для свободных моноидальных категорий, т. е. решение вопроса о том, равны ли две заданные диаграммы, может быть решена за полиномиальное время . Интерчейнджер — это конфлюэнтная переписывающая система на подмножестве гранично-связанных диаграмм, т. е. всякий раз, когда плоские графы имеют не более одного связного компонента, который не связан с доменом или кодоменом, и аргумент Экмана–Хилтона не применим. ^[9]

Расширение до 2-х категорий

Идея состоит в том, чтобы представить структуры размерности d структурами размерности 2-d , используя двойственность Пуанкаре . Таким образом,

• объект представлен частью плоскости,
• 1-ячейка представлена ​​вертикальным сегментом, называемым струной , разделяющим плоскость на две части (правая часть соответствует A , а левая — B ), ${\displaystyle f:A\to B}$
• 2-ячейка представлена ​​пересечением строк (строк, соответствующих f выше связи, строк, соответствующих g ниже связи). ${\displaystyle \alpha :f\Rightarrow g:A\to B}$

Параллельная композиция 2-клеток соответствует горизонтальному сопоставлению диаграмм, а последовательная композиция – вертикальному сопоставлению диаграмм.

Моноидальная категория эквивалентна 2-категории с одной 0-ячейкой. Интуитивно, переход от моноидальных категорий к 2-категориям сводится к добавлению цветов к фону диаграмм строк.

Примеры

Уравнение змеи

Рассмотрим сопряжение между двумя категориями и где левое сопряжение и естественные преобразования и являются соответственно единицей и коединицей. Диаграммы строк, соответствующие этим естественным преобразованиям, следующие: ${\displaystyle (F,G,\eta ,\varepsilon )}$ ${\displaystyle {\mathcal {C}}}$ ${\displaystyle {\mathcal {D}}}$ ${\displaystyle F:{\mathcal {C}}\leftarrow {\mathcal {D}}}$ ${\displaystyle G:{\mathcal {C}}\rightarrow {\mathcal {D}}}$ ${\displaystyle \eta :I\rightarrow GF}$ ${\displaystyle \varepsilon :FG\rightarrow I}$

Строка, соответствующая тождественному функтору, изображается пунктирной линией и может быть опущена. Определение присоединения требует следующих равенств:

${\displaystyle {\begin{aligned}(\varepsilon F)\circ F(\eta )&=1_{F}\\G(\varepsilon )\circ (\eta G)&=1_{G}\end{aligned}}}$

Первый из них изображен как

Моноидальная категория, в которой каждый объект имеет левый и правый сопряженный, называется жесткой категорией . Диаграммы строк для жестких категорий можно определить как непрогрессивные плоские графы, то есть ребра могут изгибаться назад.

В контексте категориальной квантовой механики это известно как уравнение змеи .

Категория гильбертовых пространств является жесткой, этот факт лежит в основе доказательства корректности протокола квантовой телепортации . Единица и коединица присоединения являются абстракцией состояния Белла и измерения Белла соответственно. Если Алиса и Боб разделяют два кубита Y и Z в запутанном состоянии и Алиса выполняет ( пост-выбранное ) запутанное измерение между Y и другим кубитом X, то этот кубит X будет телепортирован от Алисы к Бобу: квантовая телепортация является тождественным морфизмом.

Иллюстрация диаграммного исчисления: протокол квантовой телепортации , смоделированный в категориальной квантовой механике.

Это же уравнение появляется в определении предгрупповых грамматик , где оно охватывает понятие информационного потока в семантике естественного языка . Это наблюдение привело к разработке фреймворка DisCoCat и квантовой обработки естественного языка .

Иерархия графических языков

Было введено множество расширений строковых диаграмм для представления стрелок в моноидальных категориях с дополнительной структурой, образуя иерархию графических языков, которая классифицирована в «Обзоре графических языков для моноидальных категорий» Селинджера. ^[10]

• Сплетенные моноидальные категории с трехмерными диаграммами, обобщение групп кос .
• Симметричные моноидальные категории с 4-мерными диаграммами, где ребра могут пересекаться, обобщение симметрической группы .
• Ленточные категории с трехмерными диаграммами, где края ненаправлены, обобщение узловых диаграмм .
• Компактные замкнутые категории с 4-мерными диаграммами, где ребра неориентированы, обобщение графической нотации Пенроуза .
• Категории кинжалов , где каждая диаграмма имеет горизонтальное отражение.

Список приложений

Струнные диаграммы были использованы для формализации следующих объектов исследования.

• Теория параллелизма ^[11]
• Искусственные нейронные сети ^[12]
• Теория игр ^[13]
• Байесовская вероятность ^[14]
• Сознание ^[15]
• Марковские ядра ^[16]
• Графики потока сигналов ^[17]
• Конъюнктивные запросы ^[18]
• Двунаправленные преобразования ^[19]
• Категориальная квантовая механика
• Квантовые схемы , квантовые вычисления на основе измерений и квантовая коррекция ошибок , см. ZX-исчисление
• Обработка естественного языка , см. DisCoCat
• Квантовая обработка естественного языка

Смотрите также

• Сети доказательств , обобщение диаграмм строк, используемых для обозначения доказательств в линейной логике.
• Экзистенциальные графы , предшественники строковых диаграмм, используемых для обозначения формул в логике первого порядка.
• Графическая нотация Пенроуза и диаграммы Фейнмана — два предшественника струнных диаграмм в физике.
• Тензорные сети , интерпретация диаграмм строк в векторных пространствах , линейные отображения и тензорное произведение

Ссылки

1. Хотц, Гюнтер (1965). «Eine Algebraisierung des Syntheseproblems von Schaltkreisen I.». Электронная информация Verarbeitung und Kybernetik . 1 (3): 185–205.
2. Пенроуз, Роджер (1971). «Применение отрицательных размерных тензоров». Комбинаторная математика и ее приложения . 1 : 221–244.
3. Baez, J.; Stay, M. (2011), Coecke, Bob (ред.), "Физика, топология, логика и вычисления: Розеттский камень", Новые структуры для физики , Lecture Notes in Physics, т. 813, Берлин, Гейдельберг: Springer, стр. 95–172, arXiv : 0903.0340 , Bibcode : 2011LNP...813...95B, doi : 10.1007/978-3-642-12821-9_2, ISBN 978-3-642-12821-9, S2CID  115169297 , получено 2022-11-08
4. Джойал, Андре; Стрит, Росс (1991). «Геометрия тензорного исчисления, I». Advances in Mathematics . 88 (1): 55–112. doi :10.1016/0001-8708(91)90003-P.
5. "Категории: История диаграмм струн (тема, 2017may02-...)". angg.twu.net . Получено 2022-11-11 .
6. Брэди, Джеральдин; Тримбл, Тодд Х (2000). «Категорическая интерпретация пропозициональной логики Альфа К. С. Пирса». Журнал чистой и прикладной алгебры . 149 (3): 213–239. doi :10.1016/S0022-4049(98)00179-0.
7. Хейдон, Натан; Собочинский, Павел\л (2020). «Композиционная диаграмматическая логика первого порядка». Международная конференция по теории и применению диаграмм . Springer: 402–418.
8. Джойал, Андре; Стрит, Росс (1988). «Планарные диаграммы и тензорная алгебра». Неопубликованная рукопись, доступна на веб-сайте Росс-Стрит .
9. Викари, Джейми; Делпойх, Антонин (2022). «Нормализация для плоских струнных диаграмм и квадратичный алгоритм эквивалентности». Логические методы в информатике . 18 .
10. Селинджер, Питер (2010), «Обзор графических языков для моноидальных категорий», Новые структуры для физики , Springer, стр. 289–355 , получено 08.11.2022
11. Абрамски, Сэмсон (1996). «Повторное прослеживание некоторых путей в алгебре процессов». Международная конференция по теории параллелизма . Springer: 1–17.
12. Фонг, Брендан; Спивак, Дэвид И.; Туйерас, Реми (01.05.2019). «Обратное распространение ошибки как функтор: композиционная перспектива контролируемого обучения». arXiv : 1711.10455 [math.CT].
13. Гани, Нил; Хеджес, Жюль; Виншель, Виктор; Зан, Филипп (2018). «Композиционная теория игр». Труды 33-го ежегодного симпозиума ACM/IEEE по логике в компьютерных науках. стр. 472–481. doi :10.1145/3209108.3209165. ISBN 9781450355834. S2CID  17887510.
14. Coecke, Bob; Spekkens, Robert W (2012). «Изображение классического и квантового байесовского вывода». Synthese . 186 (3): 651–696. arXiv : 1102.2368 . doi : 10.1007/s11229-011-9917-5. S2CID  3736082.
15. Синьорелли, Камило Мигель; Ван, Куанлонг; Коек, Боб (2021-10-01). «Рассуждения о сознательном опыте с помощью аксиоматической и графической математики». Сознание и познание . 95 : 103168. doi : 10.1016/j.concog.2021.103168 . hdl : 10230/53097 . ISSN  1053-8100. PMID  34627099. S2CID  235683270.
16. Фриц, Тобиас (август 2020 г.). «Синтетический подход к марковским ядрам, условной независимости и теоремам о достаточных статистиках». Успехи математики . 370 : 107239. arXiv : 1908.07021 . doi : 10.1016/j.aim.2020.107239. S2CID  201103837.
17. Бончи, Филиппо; Собочинский, Павел; Занаси, Фабио (сентябрь 2014 г.). "Категорическая семантика графов потока сигналов". CONCUR 2014 – Теория параллелизма . Конспект лекций по информатике. Том. CONCUR 2014 - Теория параллелизма - 25-я международная конференция. Рим, Италия. стр. 435–450. doi :10.1007/978-3-662-44584-6_30. ISBN 978-3-662-44583-9. S2CID  18492893.{{cite book}}: CS1 maint: location missing publisher (link)
18. Бончи, Филиппо; Сибер, Йенс; Собочинский, Павел (20 апреля 2018 г.). «Графические конъюнктивные запросы». arXiv : 1804.07626 [cs.LO].
19. Райли, Митчелл (2018). «Категории оптики». arXiv : 1809.00738 [math.CT].

Внешние ссылки

• TheCatsters (2007). Диаграммы струн 1 (потоковое видео) . Youtube. Архивировано из оригинала 2021-12-19.
• Диаграммы струн в n Lab
• DisCoPy, набор инструментов Python для вычислений с использованием строковых диаграмм

Внешние ссылки

• Медиа, связанные с диаграммой струны на Wikimedia Commons