Струнная диаграмма

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

История

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

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

Интуиция

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

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

Определение

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

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

Моноидальная подпись $\Sigma$ дается:

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

• диаграмма личности ${\text{id}}(x)$ с ${\text{len}}({\text{id}}(x))=0$ и ${\text{dom}}({\text{id}}(x))=x$,
• композиция двух диаграмм как объединение их списка слоев,
• тензор двух диаграмм как композиция усов $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')}$.

Две диаграммы равны (с точностью до аксиом моноидальных категорий), если они находятся в одном и том же классе эквивалентности отношения конгруэнтности, генерируемого обменником :

$$d\otimes {\text{dom}}(d')\ \circ \ {\text{cod}}(d)\otimes d'\quad =\quad {\text{dom}}(d)\otimes d'\ \circ \ d\otimes {\text{cod}}(d')$$

То есть, если коробки в двух последовательных слоях не соединены, то их порядок можно поменять местами. Интуитивно понятно, что если между двумя параллельными процессами нет связи, то порядок, в котором они происходят, не имеет значения.

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

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

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

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

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

Двойственность между коммутативными диаграммами (слева) и струнными диаграммами (справа)

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

Примеры

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

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

Струнная схема агрегата

Струнная диаграмма устройства

Струнная диаграмма личности

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

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

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

Схематическое изображение равенства $(\varepsilon F)\circ F(\eta )=1_{F}$

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

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

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

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

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

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

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

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

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

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

• Теория параллелизма
• Искусственные нейронные сети
• Теория игр
• Байесовская вероятность
• Сознание
• Марковские ядра
• Графики потока сигналов
• Конъюнктивные запросы
• Двунаправленные преобразования
• Категорическая квантовая механика
• Квантовые схемы , квантовые вычисления на основе измерений и квантовая коррекция ошибок , см. ZX-исчисление.
• Обработка естественного языка , см. DisCoCat.
• Квантовая обработка естественного языка

См. также

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

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

• Коты (2007). Струнные диаграммы 1 (потоковое видео) . Ютуб. Архивировано из оригинала 19 декабря 2021 г.
• Струнные диаграммы в n Lab
• DisCoPy , набор инструментов Python для вычислений с помощью строковых диаграмм.

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

• СМИ, связанные со строковой диаграммой, на Викискладе?