Hay doble puertas de la lógica?

Question

En la categoría de la teoría de la utilidad de dualising dispositivos tales como monoids a comonoids ha demostrado, donde la multiplicación que se lleva dos entradas a una salida es dualised a comultiplication que toma una entrada y dos salidas.

Hay una interpretación similar de la lógica? Puede haber tal cosa como un co-o un co-o la puerta?

Answer 1

Esta es una pregunta interesante. A continuación son mis pensamientos.

Las puertas de la lógica como monoids

El $\vee$ (o) e $\wedge$ (e) las puertas de la lógica son monoids sobre el conjunto de valores booleanos $\mathbb{B} = \{F, T\}$ (falso y verdadero): $(\mathbb{B}, \vee, T)$ $(\mathbb{B}, \wedge, F)$ respectivamente. Una manera de pensar de esta manera categórica es como un monoid objeto en algunos categoría monoidal. Ya que estamos tratando con conjuntos, que esta categoría sea la categoría de conjuntos con la estructura monoidal de productos Cartesianos con algunos arbtirary singleton conjunto 1 = $\{\bullet\}$ es decir $(\mathbf{Set}, \times, 1)$. Por lo tanto, la multiplicación y la unidad de operaciones de la o y y monoids son $\vee : \mathbb{B} \times \mathbb{B} \rightarrow \mathbb{B}$, $T : 1 \rightarrow \mathbb{B}$ y $\wedge : \mathbb{B} \times \mathbb{B} \rightarrow \mathbb{B}$, $F : 1 \rightarrow \mathbb{B}$ respectivamente.

Dualising a un comonoid

Comonoid objetos de más de $\mathbb{B}$ $\mathbf{Set}$ tiene un comultiplication $\delta : \mathbb{B} \rightarrow \mathbb{B} \times \mathbb{B}$ y counit $\varepsilon : \mathbb{B} \rightarrow 1$. Así que, como dices, uno de entrada se asigna a dos salidas. Sin embargo, la comonoid leyes (dual a la monoid las leyes del estado que $(id \times \varepsilon) \circ \delta = \langle{id, !_\mathbb{B}}\rangle$ $(\varepsilon \times id) \circ \delta = \langle{!_\mathbb{B}, id}\rangle$ donde $!_A : A \rightarrow 1$ es decir comultiplication de entrada, seguido por un counit de uno de los componentes es el mismo que el emparejamiento que de entrada con algunos singleont conjunto (inversa de las flechas en el diagrama de la monoid leyes). En $\textbf{Set}$ esto significa que la única opción para $\delta$ (para cumplir las leyes) es la duplicación, es decir,, $\delta = \langle{id, id}\rangle$ ($\delta\ x \mapsto (x, x)$). Por lo tanto co-o y co-y sólo puede ser duplicación, con el counit $\varepsilon = !_\mathbb{B}$ el mapeo de su entrada a la arbitraria singleton set 1 (olvidando su entrada). No hay otra opción.

Relación entre $\vee$/$\wedge$ monoids y la duplicación comonoid

La duplicación de la operación es el derecho a la identidad (sección) de la $\vee$ $\wedge$ operaciones decir $\vee \circ \delta = id$ $\wedge \circ \delta = id$ (desde $\vee$ $\wedge$ son idempotente monoids). Sin embargo, $\delta$ no es la izquierda-inversa (retracción), por ejemplo, $\delta \circ \vee \neq id$, por lo tanto no se forma un isomorfismo. Esto se puede entender fácilmente a partir de una teoría de la información desde la perspectiva de la $\vee$ reduce la cantidad de información a partir de dos bits a uno de los bits, y $\delta$ conserva la cantidad de información mediante la duplicación de la bit, mientras que el $id$ conserva ambos bits de información.

Tenga en cuenta que el counit de este comonoid es la izquierda-identidad (retracción) de $F$ $T$ es decir $\varepsilon \circ F = id$$\varepsilon \circ T = id$. El counit no puede ser el derecho a la identidad (de la sección). Usted puede seguir una teoría de la información argumento similar a los anteriores para entender por qué: $\varepsilon$ va de 1-bit de información a 0-bits de información (desde siempre sabemos lo que es en este singleton set$1$, de todos modos), por lo tanto no hay información puede ser llevado a la morfismos $F : 1 \rightarrow \mathbb{B}$$T : 1 \rightarrow \mathbb{B}$, que crear un nuevo bit de información, por ejemplo,$(T \circ \varepsilon) F \mapsto T$$T \circ \varepsilon \neq id$.

Anexo

Podemos tratar de ser más creativos con nuestros comonoid? Por ejemplo, podemos utilizar una diferente estructura monoidal sobre los conjuntos tales como conjuntos de pares? Entonces, por ejemplo, podríamos definir un doble a $\wedge$ que nos da a todos sus "posibles" entradas: $\delta\ F \mapsto [(F, F), (F, T), (T, F)]$$\delta\ T \mapsto [(T, T)]$. Así, el subyacente categoría monoidal estructura es $A \otimes B = \mathcal{P}(A \times B)$ donde $f \otimes g\ \{(x_0, y_0), \ldots, (x_n, y_n)\} \mapsto \{(f\ x_0, g\ y_0), \ldots, (f\ x_n, g\ x_n)\}$. Por desgracia, esto no nos da una comonoid como las leyes son violadas, por ejemplo,$((\varepsilon \otimes id) \circ \delta)\ F \mapsto \{(\bullet, F), (\bullet, T)\}$$\langle{!_\mathbb{B}, id}\rangle F \mapsto \{(\bullet, F)\}$. He tratado de pensar de otras estructuras, pero todos cumplen con un fin similar.