Diagrama de cuerdas

Deja que la estrella Kleene${\displaystyle X^{\star }}$denotamos el monoide libre , es decir, el conjunto de listas con elementos en un conjunto${\displaystyle X}$.

Una firma monoide${\displaystyle \Sigma }$está dado por:

• un conjunto${\displaystyle \Sigma _{0}}$de generar objetos , las listas de generar objetos en${\textstyle \Sigma _{0}^{\star }}$también se les llama tipos ,
• un conjunto${\displaystyle \Sigma _{1}}$de generar flechas , también llamadas cajas ,
• un par de funciones${\displaystyle {\text{dom}},{\text{cod}}:\Sigma _{1}\to \Sigma _{0}^{\star }}$que asignan un dominio y un codominio a cada caja, es decir, los tipos de entrada y salida.

Un morfismo de signatura monoide${\displaystyle F:\Sigma \to \Sigma '}$es un par de funciones${\displaystyle F_{0}:\Sigma _{0}\to \Sigma '_{0}}$y${\displaystyle F_{1}:\Sigma _{1}\to \Sigma '_{1}}$que sea compatible con el dominio y el codominio, es decir, de tal manera que${\displaystyle {\text{dom}}\circ F_{1}\ =\ F_{0}\circ {\text{dom}}}$y${\displaystyle {\text{cod}}\circ F_{1}\ =\ F_{0}\circ {\text{cod}}}$. Así obtenemos la categoría${\displaystyle \mathbf {MonSig} }$de firmas monoidales y sus morfismos.

Hay un functor olvidadizo${\displaystyle U:\mathbf {MonCat} \to \mathbf {MonSig} }$que envía una categoría monoidal a su signatura subyacente y un functor monoidal a su morfismo de signaturas subyacente, es decir, olvida la identidad, la composición y el tensor. El functor libre${\displaystyle C_{-}:\mathbf {MonSig} \to \mathbf {MonCat} }$, es decir, el adjunto izquierdo del functor olvidadizo, envía una signatura monoide.${\displaystyle \Sigma }$a la categoría monoide libre${\displaystyle C_{\Sigma }}$genera.

Diagramas de cadenas (con generadores de${\displaystyle \Sigma }$) son flechas en la categoría monoidal libre${\displaystyle C_{\Sigma }}$. ^{[ 9 ]} La interpretación en una categoría monoide${\displaystyle D}$es un definido por un functor monoidal${\displaystyle F:C_{\Sigma }\to D}$, que por su libertad está determinado de forma única por un morfismo de firmas monoidales${\displaystyle F:\Sigma \to U(D)}$Intuitivamente, una vez que se proporciona la imagen de los objetos y flechas generadores, la imagen de cada diagrama que generan queda fija.

Un grafo topológico , también llamado complejo celular unidimensional , es una tupla.${\ Displaystyle (\ Gamma, \ Gamma _ {0}, \ Gamma _ {1})}$de un espacio Hausdorff${\displaystyle \Gamma }$, un subconjunto discreto cerrado${\displaystyle \Gamma _{0}\subseteq \Gamma }$de nodos y un conjunto de componentes conectados${\displaystyle \Gamma _{1}}$llamados aristas , cada una homeomorfa a un intervalo abierto con frontera en${\displaystyle \Gamma _{0}}$y tal que${\textstyle \Gamma -\Gamma _{0}=\coprod \Gamma _{1}}$.

Un gráfico plano entre dos números reales${\displaystyle a,b\in \mathbb {R} }$con${\displaystyle a<b}$es un grafo topológico finito incrustado en${\displaystyle \mathbb {R} \times [a,b]}$de tal manera que cada punto${\displaystyle x\in \Gamma \ \cap \ \mathbb {R} \times \{a,b\}}$también es un nodo${\displaystyle x\in \Gamma _{0}}$y pertenece al cierre de exactamente una arista en${\displaystyle \Gamma _{1}}$Estos puntos se denominan nodos externos y definen el dominio y el codominio .${\displaystyle {\text{dom}}(\Gamma ),{\text{cod}}(\Gamma )\in \Gamma _{1}^{\star }}$del diagrama de cuerdas, es decir, la lista de aristas que están conectadas al límite superior e inferior. Los demás nodos${\displaystyle f\in \Gamma _{0}\ -\ \{a,b\}\times \mathbb {R} }$se denominan nodos internos .

Un gráfico plano es progresivo , también llamado recumbente , cuando la proyección vertical${\displaystyle e\to [a,b]}$es inyectable para cada borde${\ Displaystyle e \ en \ Gamma _ {1}}$Intuitivamente, las aristas en un grafo plano progresivo van de arriba abajo sin curvarse hacia atrás. En ese caso, a cada arista se le puede dar una orientación de arriba abajo con nodos designados como origen y destino. Entonces se puede definir el dominio y el codominio.${\displaystyle {\text{dom}}(f),{\text{cod}}(f)\in \Gamma _{1}^{\star }}$de cada nodo interno${\displaystyle f}$, dada por la lista de aristas que tienen origen y destino.

Un gráfico plano es genérico cuando la proyección vertical${\displaystyle \Gamma _{0}-\{a,b\}\times \mathbb {R} \to [a,b]}$es inyectivo, es decir, no hay dos nodos internos a la misma altura. En ese caso, se puede definir una lista.${\displaystyle {\text{boxes}}(\Gamma )\in \Gamma _{0}^{\star }}$de los nodos internos ordenados de arriba a abajo.

Un gráfico plano progresivo se etiqueta mediante una firma monoidal.${\displaystyle \Sigma }$si viene equipado con un par de funciones${\displaystyle v_{0}:\Gamma _{1}\to \Sigma _{0}}$desde bordes hasta la generación de objetos y${\displaystyle v_{1}:\Gamma _{0}-\{a,b\}\times \mathbb {R} \to \Sigma _{1}}$desde nodos internos hasta la generación de flechas, de una manera compatible con dominio y codominio.

Una deformación de gráficos planos es una aplicación continua.${\displaystyle h:\Gamma \times [0,1]\to [a,b]\times \mathbb {R} }$de tal manera que

• la imagen de${\displaystyle h(-,t)}$define un gráfico plano para todos${\displaystyle t\in [0,1]}$,
• a pesar de${\displaystyle x\in \Gamma _{0}}$, si${\displaystyle h(x,t)}$es un nodo interno para algunos${\displaystyle t}$es interno para todos${\displaystyle t\in [0,1]}$.

Una deformación es progresiva (genérica, etiquetada) si${\displaystyle h(-,t)}$es progresivo (genérico, etiquetado) para todos${\displaystyle t\in [0,1]}$. Las deformaciones inducen una relación de equivalencia con${\displaystyle \Gamma \sim \Gamma '}$si y solo si hay alguna${\displaystyle h}$con${\displaystyle h(-,0)=\Gamma }$y${\displaystyle h(-,1)=\Gamma '}$Los diagramas de cadenas son clases de equivalencia de grafos planos progresivos etiquetados . De hecho, se puede definir:

• el diagrama de identidad${\displaystyle {\text{id}}(x)}$como un conjunto de aristas paralelas etiquetadas por algún tipo${\displaystyle x\in \Sigma _{0}^{\star }}$,
• la composición de dos diagramas como su concatenación vertical con el codominio del primero identificado con el dominio del segundo,
• el tensor de dos diagramas como su concatenación horizontal.

Si bien la definición geométrica explicita el vínculo entre la teoría de categorías y la topología de baja dimensión , se requiere una definición combinatoria para formalizar los diagramas de cadenas en sistemas de álgebra computacional y utilizarlos para definir problemas computacionales . Una de estas definiciones consiste en definir los diagramas de cadenas como clases de equivalencia de fórmulas bien tipadas generadas por la signatura, la identidad, la composición y el tensor. En la práctica, resulta más conveniente codificar los diagramas de cadenas como fórmulas en forma genérica , que están en biyección con los grafos planos progresivos genéricos etiquetados definidos anteriormente.

Corregir una firma monoide${\displaystyle \Sigma }$Una capa se define como una tripleta${\displaystyle (x,f,y)\in \Sigma _{0}^{\star }\times \Sigma _{1}\times \Sigma _{0}^{\star }=:L(\Sigma )}$de un tipo${\displaystyle x}$A la izquierda, una caja${\displaystyle f}$en el medio y un tipo${\displaystyle y}$A la derecha. Las capas tienen un dominio y un codominio.${\displaystyle {\text{dom}},{\text{cod}}:L(\Sigma )\to \Sigma _{0}^{\star }}$definido de la forma obvia. Esto forma un multigrafo dirigido , también conocido como carcaj , con los tipos como vértices y las capas como aristas. Un diagrama de cuerdas${\displaystyle d}$está codificado como una ruta en este multigrafo , es decir, viene dado por:

• un dominio${\displaystyle {\text{dom}}(d)\in \Sigma _{0}^{\star }}$como punto de partida
• una longitud${\displaystyle {\text{len}}(d)=n\geq 0}$,
• una lista de${\displaystyle {\text{layers}}(d)=d_{1}\dots d_{n}\in L(\Sigma )}$

de tal manera que${\displaystyle {\text{dom}}(d_{1})={\text{dom}}(d)}$y${\displaystyle {\text{cod}}(d_{i})={\text{dom}}(d_{i+1})}$a pesar de${\displaystyle i<n}$De hecho, la lista explícita de capas es redundante; basta con especificar la longitud del tipo a la izquierda de cada capa, conocida como desplazamiento . El bigote${\displaystyle d\otimes z}$de un diagrama${\displaystyle d=(x_{1},f_{1},y_{1})\dots (x_{n},f_{n},y_{n})}$por un tipo${\displaystyle z}$se define como la concatenación a la derecha de cada capa${\displaystyle d\otimes z=(x_{1},f_{1},y_{1}z)\dots (x_{n},f_{n},y_{n}z)}$y simétricamente para el bigote${\displaystyle z\otimes d}$a la izquierda. Entonces se puede definir:

• el diagrama de identidad${\displaystyle {\text{id}}(x)}$con${\displaystyle {\text{len}}({\text{id}}(x))=0}$y${\displaystyle {\text{dom}}({\text{id}}(x))=x}$,
• la composición de dos diagramas como la concatenación de su lista de capas,
• el tensor de dos diagramas como la composición de bigotes${\displaystyle d\otimes d'=d\otimes {\text{dom}}(d')\ \circ \ {\text{cod}}(d)\otimes d'}$.

Nótese que, dado que el diagrama está en forma genérica (es decir, cada capa contiene exactamente una caja), la definición de tensor está necesariamente sesgada: el diagrama de la izquierda se sitúa por encima del de la derecha. Se podría haber elegido la definición opuesta.${\textstyle d\otimes d'={\text{dom}}(d)\otimes d'\ \circ \ d\otimes {\text{cod}}(d')}$.

Dos diagramas son iguales (salvo los axiomas de las categorías monoidales) siempre que estén en la misma clase de equivalencia de la relación de congruencia generada por el intercambiador :$${\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')}$$Es decir, si las cajas de dos capas consecutivas no están conectadas, su orden puede intercambiarse. Intuitivamente, si no hay comunicación entre dos procesos paralelos, el orden en que ocurren es irrelevante.

El problema de palabras para categorías monoidales libres, es decir, decidir si dos diagramas dados son iguales, se puede resolver en tiempo polinomial . El intercambiador es un sistema de reescritura confluente en el subconjunto de diagramas conexos de frontera , es decir, siempre que los grafos planos no tengan más de un componente conexo que no esté conectado al dominio o codominio y el argumento de Eckmann-Hilton no sea aplicable. ^{[ 10 ]}

Consideremos una adjunción${\displaystyle (F,G,\eta ,\epsilon )}$entre dos categorías${\displaystyle {\mathcal {C}}}$y${\displaystyle {\mathcal {D}}}$dónde${\displaystyle F:{\mathcal {C}}\leftarrow {\mathcal {D}}}$es adjunto izquierdo de${\displaystyle G:{\mathcal {C}}\rightarrow {\mathcal {D}}}$y las transformaciones naturales${\displaystyle \eta :I\rightarrow GF}$y${\displaystyle \epsilon :FG\rightarrow I}$son respectivamente la unidad y la counidad. Los diagramas de cuerdas correspondientes a estas transformaciones naturales son:

Diagrama de cuerdas de la unidad

Diagrama de cuerdas de la counidad

Diagrama de cuerdas de la identidad

La cadena correspondiente al functor identidad se dibuja como una línea punteada y puede omitirse. La definición de una adjunción requiere las siguientes igualdades:

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

El primero se representa como

Representación esquemática de la igualdad${\displaystyle (\epsilon F)\circ F(\eta )=1_{F}}$

Una categoría monoidal donde cada objeto tiene un adjunto izquierdo y uno derecho se denomina categoría rígida . Los diagramas de cuerdas para categorías rígidas se pueden definir como grafos planos no progresivos , es decir, las aristas pueden curvarse hacia atrás.

En el contexto de la mecánica cuántica categórica , esto se conoce como la ecuación de la serpiente .

La categoría de espacios de Hilbert es rígida; este hecho subyace a la prueba de corrección del protocolo de teletransportación cuántica . La unidad y la counidad de la adjunción son una abstracción del estado de Bell y la medición de Bell , respectivamente. Si Alice y Bob comparten dos cúbits Y y Z en un estado entrelazado y Alice realiza una medición entrelazada ( postseleccionada ) entre Y y otro cúbit X, entonces este cúbit X será teletransportado de Alice a Bob: la teletransportación cuántica es un morfismo identidad.

Un ejemplo del cálculo diagramático: el protocolo de teletransportación cuántica modelado en mecánica cuántica categórica.

La misma ecuación aparece en la definición de gramáticas de pregrupos, donde captura la noción de flujo de información en la semántica del lenguaje natural . Esta observación ha llevado al desarrollo del marco DisCoCat y al procesamiento cuántico del lenguaje natural .