Espacio coherente

La definición original de Jean-Yves Girard es una familia de conjuntos.${\displaystyle {\mathcal {A}}}$, que cumplen las siguientes condiciones de cierre :

• Cierre hacia abajo : si${\displaystyle a\in {\mathcal {A}}}$y${\displaystyle a'\subseteteq a}$, entonces${\displaystyle a'\in {\mathcal {A}}}$.
• Completitud binaria : para cada${\displaystyle M\subseteq {\mathcal {A}}}$, si${\displaystyle a_{1}\cup a_{2}\in {\mathcal {A}}}$a pesar de${\displaystyle a_{1},a_{2}\in M}$, entonces${\displaystyle \bigcup M\in {\mathcal {A}}}$.

Los elementos de los conjuntos en${\displaystyle {\mathcal {A}}}$son tokens . El conjunto de tokens es$${\displaystyle |{\mathcal {A}}|=\bigcup {\mathcal {A}}=\{\alpha \mid \{\alpha \}\in {\mathcal {A}}\}.}$$Decimos que cada${\displaystyle a\in A}$es un conjunto coherente de tokens . Si un conjunto${\displaystyle X}$se da por adelantado y los elementos de${\displaystyle {\mathcal {A}}}$se presentan como subconjuntos de${\displaystyle X}$, entonces también se requiere${\displaystyle \{\alpha \}\in {\mathcal {A}}}$por cada${\displaystyle \alpha \in X}$Esto indica intuitivamente que cualquier token es coherente al menos consigo mismo.

Dada dicha familia, se obtiene una relación reflexiva y simétrica.${\displaystyle \sim }$en${\displaystyle |{\mathcal {A}}|}$, llamada coherencia módulo${\displaystyle {\mathcal {A}}}$, estableciendo$${\displaystyle \alpha \sim \beta \quad {\text{si y solo si}}\quad \{\alpha ,\beta \}\in {\mathcal {A}}.}$$Los elementos de${\displaystyle {\mathcal {A}}}$son entonces precisamente los subconjuntos de${\displaystyle |{\mathcal {A}}|}$cuyos elementos están relacionados por pares mediante${\displaystyle \sim }$.

Los conjuntos coherentes están parcialmente ordenados bajo inclusión. Por completitud binaria y el lema de Zorn , cualquier conjunto coherente está contenido en un conjunto máximamente coherente. En consecuencia, solo es necesario especificar los conjuntos máximamente coherentes,${\displaystyle {\mathcal {A}}_{\max }}$, luego realiza un cierre descendente:$${\displaystyle {\mathcal {A}}=\{a:\exists a'\in {\mathcal {A}}_{\max },a'\supset a\}}$$La única condición en${\displaystyle {\mathcal {A}}_{\max }}$¿Es que cualquiera de dos?${\displaystyle a,a'\in {\mathcal {A}}_{\max }}$, si son distintos, entonces ninguno contiene al otro.

Los espacios de coherencia están en biyección con grafos no dirigidos cuyos vértices son tokens.

Dado un espacio de coherencia${\displaystyle {\mathcal {A}}}$, su gráfico asociado, llamado la red de${\displaystyle {\mathcal {A}}}$, tiene conjunto de vértices${\displaystyle |{\mathcal {A}}|}$Sus aristas son los pares no ordenados.${\displaystyle \{\alpha,\beta \}}$de tal manera que${\displaystyle \alpha \sim \beta }$. Tenga en cuenta que requerimos que cada vértice tenga una arista propia simplemente como una convención conveniente.

Por el contrario, dado un grafo no dirigido${\displaystyle (|{\mathcal {A}}|,E)}$donde cada vértice tiene una arista propia, se obtiene un espacio de coherencia tomando${\displaystyle {\mathcal {A}}}$ser la familia de todas las camarillas del grafo:$${\displaystyle {\mathcal {A}}=\{a\subseteq |{\mathcal {A}}|\mid \forall \alpha ,\beta \in a,\{\alpha ,\beta \}\in E\}.}$$Es decir, los elementos de${\displaystyle {\mathcal {A}}}$son los conjuntos de vértices cuyos elementos son adyacentes por pares.

Dejar${\displaystyle |{\mathcal {A}}|}$ser un conjunto de tokens. Dos subconjuntos${\displaystyle a,b\subseteq |{\mathcal {A}}|}$Se dice que son ortogonales (o polares ) si${\displaystyle a\cap b}$está vacío o es un singleton . Lo escribimos como${\displaystyle a\perp b}$.

Para una familia${\displaystyle {\mathcal {A}}\subseteq {\mathcal {P}}(|{\mathcal {A}}|)}$, su dual es la familia$${\displaystyle {\mathcal {A}}^{\perp }=\{a\subseteq |{\mathcal {A}}|\mid \forall b\in {\mathcal {A}},\ a\perp b\}.}$$Un espacio de coherencia es una familia${\displaystyle {\mathcal {A}}\subseteq {\mathcal {P}}(|{\mathcal {A}}|)}$satisfactorio$${\displaystyle {\mathcal {A}}=({\mathcal {A}}^{\perp })^{\perp }.}$$Es decir, es una familia que es biorthogonalmente cerrada bajo polaridad.

Una función estable se define como una función que asigna funciones a grupos de personas:$${\displaystyle f:{\mathcal {A}}\to {\mathcal {B}}}$$de tal manera que es

• continuo: Si${\displaystyle \{a_{i}\}_{i}\subset {\mathcal {A}}}$es una familia dirigida , entonces${\displaystyle f(\cup _{i}a_{i})=\cup _{i}f(a_{i})}$.
• estable: Si${\displaystyle a,a'\in {\mathcal {A}}}$de tal manera que${\displaystyle a\cup a'\in {\mathcal {A}}}$, entonces${\displaystyle f(a\cap a')=f(a)\cap f(a')}$.

Por estabilidad, si${\displaystyle a\subset a'\in {\mathcal {A}}}$entonces${\displaystyle f(a)\subset f(a')}$, entonces${\displaystyle f}$es monótono .

Por estabilidad,${\displaystyle f(a)=\cup _{a'\subset a,a'{\text{ is finite}}}f(a')}$. Por lo tanto, demuestra que${\displaystyle f}$está determinado por su valor en conjuntos coherentes finitos.

Para la continuidad, considerando el caso especial donde${\displaystyle \{a_{i}\}_{i}\subset {\mathcal {A}}}$es el conjunto vacío , tenemos${\displaystyle f(\emptyset )=\emptyset }$.

Dada una función estable, su traza${\displaystyle Tr(f)\subset {\mathcal {A}}\times |{\mathcal {B}}|}$se define como$${\displaystyle Tr(f):=\{(a,\beta )|a\in {\mathcal {A}},\beta \in f(a),(\forall a'\subsetneq a,\beta \not \in f(a'))\}}$$Es decir, cada${\displaystyle (a,\beta )\in Tr(f)}$es tal que${\displaystyle a}$es un conjunto coherente mínimo necesario para producir token${\displaystyle \beta }$. Por estabilidad, cualquier${\displaystyle (a,\beta )\in Tr(f)}$debe tener un finito${\displaystyle a}$.

Por el contrario, cada función estable está determinada por su traza:$${\displaystyle f(a)=\{\beta$$ :(a',\beta )\in Tr(f),a'\subset a\}}

Una función estable${\displaystyle f}$es lineal si y solo si alguno${\displaystyle (a,\beta )\in Tr(f)}$,${\displaystyle a}$tiene un solo elemento. Esta fue la motivación original de la lógica lineal .

Las funciones lineales estables son particularmente simples y pueden considerarse como una función con valores de clique.${\displaystyle f:|{\mathcal {A}}|\to {\mathcal {B}}}$de tal manera que, dado un grupo,${\displaystyle a\in {\mathcal {A}}}$,${\displaystyle \cup _{\alpha \in a}f(\alpha )}$sigue siendo una camarilla en${\displaystyle {\mathcal {B}}}$.

Cualquier espacio coherente puede especificarse mediante sus conjuntos máximamente coherentes. Cualquier unión de dos conjuntos máximamente coherentes distintos es incoherente.

Dado un espacio coherente${\displaystyle {\mathcal {A}}}$, su polar${\displaystyle {\mathcal {A}}^{\perp }}$sigue siendo un espacio coherente. Esta es una construcción de objeto dual en la teoría de categorías.

Dado cualquier conjunto${\displaystyle X}$, tenemos el espacio coherente discreto/mínimo${\displaystyle \{\{\alpha \}:\alpha \in X\}}$y el espacio coherente indiscreto/máximo${\displaystyle {\mathcal {P}}(X)}$.

Dados dos espacios coherentes${\displaystyle {\mathcal {A}},{\mathcal {B}}}$, hay un espacio coherente${\displaystyle {\mathcal {A}}\&{\mathcal {B}}}$(se pronuncia "A y B"). Se define como un grafo. El conjunto de tokens es la unión disjunta de los dos conjuntos de tokens:$${\displaystyle |{\mathcal {A}}\&{\mathcal {B}}|=|{\mathcal {A}}|+|{\mathcal {B}}|}$$y los bordes de${\displaystyle {\mathcal {A}}\&{\mathcal {B}}}$es la unión de los bordes en${\displaystyle {\mathcal {A}}}$, los bordes en${\displaystyle {\mathcal {B}}}$, y${\displaystyle \{\{\alpha ,\beta \}:\alpha \in {\mathcal {A}},\beta \in {\mathcal {B}}\}}$. De manera más general, dada una familia de espacios coherentes,${\displaystyle \{{\mathcal {A}}_{i}\}_{i\in I}}$, podemos definir${\displaystyle \&_{i\in I}{\mathcal {A}}_{i}}$similarmente.

Dados dos espacios coherentes${\displaystyle {\mathcal {A}},{\mathcal {B}}}$, hay un espacio coherente${\displaystyle {\mathcal {A}}\sqcup {\mathcal {B}}}$El conjunto de tokens sigue siendo$${\displaystyle |{\mathcal {A}}\sqcup {\mathcal {B}}|=|{\mathcal {A}}|+|{\mathcal {B}}|}$$y los bordes de${\displaystyle {\mathcal {A}}\sqcup {\mathcal {B}}}$es la unión de los bordes en${\displaystyle {\mathcal {A}}}$, los bordes en${\displaystyle {\mathcal {B}}}$. Este es el coproducto . Esto se puede definir en general para una familia de espacios coherentes,${\displaystyle \{{\mathcal {A}}_{i}\}_{i\in I}}$.

Dados dos conjuntos${\displaystyle X,Y}$, el conjunto de funciones parciales de tipo${\displaystyle X\to Y}$puede ser modelado por un espacio coherente. El conjunto de tokens es${\displaystyle X\times Y}$y los bordes son${\displaystyle \{(x,y),(x',y')\}}$a pesar de${\displaystyle x\neq x'}$. De forma equivalente, para cada${\displaystyle x\in X}$, definir${\displaystyle {\mathcal {Y}}_{x}}$ser el espacio coherente discreto/mínimo de${\displaystyle Y}$. Entonces${\displaystyle \&_{x\in X}{\mathcal {Y}}_{x}}$es el espacio coherente que construimos.

Esto se puede entender intuitivamente de la siguiente manera: una función parcial${\displaystyle f:X\to Y}$tiene el conjunto de rasgos${\displaystyle \{(x,f(x)):x\in X\land f(x){\text{ is defined}}\}}$Un conjunto máximamente coherente es el conjunto de rasgos de una función total. Al enumerar los valores de una función parcial, enumeramos el conjunto de rasgos, que es coherente en cada paso. Esto es útil cuando${\displaystyle f}$es calculado por una máquina de Turing que podría no detenerse en algunas entradas. Si${\displaystyle f(x)}$Si el proceso no se detiene, simplemente no observamos el rasgo durante la enumeración. El conjunto de rasgos observados permanecerá coherente en todas las etapas de nuestra enumeración.

Ahora, define${\displaystyle {\mathcal {X}},{\mathcal {Y}}}$ser los espacios coherentes discretos/mínimos. Entonces${\displaystyle f:{\mathcal {X}}\to {\mathcal {Y}}}$es una función estable si y solo si existe una función parcial${\displaystyle f':X\to Y}$, de tal manera que$${\displaystyle f(\{x\})={\begin{cases}\{f'(x)\}&{\text{ if }}f'(x){\text{ is defined,}}\\\emptyset &{\text{ else}}\end{cases}}}$$y${\displaystyle f'}$puede identificarse con su conjunto de rasgos, que es un conjunto coherente en${\displaystyle \&_{x\in X}{\mathcal {Y}}_{x}}$. De este modo,${\displaystyle \mathrm {Hom} _{\mathbf {Coh} }({\mathcal {X}},{\mathcal {Y}})\simeq \&_{x\in X}{\mathcal {Y}}_{x}}$es un espacio coherente.

En general, tenemos un functor${\displaystyle \Rightarrow$ :\mathbf {Coh} ^{2}\to \mathbf {Coh} } , contravariante en el primer argumento y covariante en el segundo argumento, de tal manera que$${\displaystyle \mathrm {Hom} _{\mathbf {Coh} }({\mathcal {A}},{\mathcal {B}})\simeq {\mathcal {A}}\Rightarrow {\mathcal {B}}}$$Es decir, dados cualesquiera dos espacios coherentes${\displaystyle {\mathcal {A}},{\mathcal {B}}}$, el conjunto de hom entre ellos también está estructurado como un espacio coherente. Esto hace que la categoría se enriquezca a sí misma.

El conjunto de fichas${\displaystyle |{\mathcal {A}}\Rightarrow {\mathcal {B}}|}$es${\displaystyle {\mathcal {A}}_{\text{fin}}\times |{\mathcal {B}}|}$, dónde${\displaystyle {\mathcal {A}}_{\text{fin}}}$es el conjunto de conjuntos coherentes finitos no vacíos en${\displaystyle {\mathcal {A}}}$Dos fichas${\displaystyle (a,\beta ),(a',\beta ')}$son coherentes si y solo si

• Si${\displaystyle a\cup a'\in {\mathcal {A}}}$, entonces${\displaystyle \{\beta ,\beta '\}\in {\mathcal {B}}}$.
• Si${\displaystyle a\cup a'\in {\mathcal {A}}}$y${\displaystyle a\neq a'}$, entonces${\displaystyle \beta \neq \beta '}$.

Tenga en cuenta que, si${\displaystyle a\cup a'\not \in {\mathcal {A}}}$, entonces${\displaystyle (a,\beta ),(a',\beta ')}$para cualquier${\displaystyle \beta ,\beta '\in |{\mathcal {B}}|}$. Es decir, solo exigimos coherencia en${\displaystyle {\mathcal {B}}}$dada coherencia en${\displaystyle {\mathcal {A}}}$. Si no hay coherencia en${\displaystyle {\mathcal {A}}}$, entonces no hacemos exigencias de coherencia en${\displaystyle {\mathcal {B}}}$.

Funciones entre tipos${\displaystyle {\mathcal {A}}\to {\mathcal {B}}}$se consideran funciones estables entre espacios de coherencia. Una función estable se define como aquella que respeta aproximantes y satisface un cierto axioma de estabilidad. Formalmente,${\displaystyle F:{\mathcal {A}}\to {\mathcal {B}}}$es una función estable cuando

1. Es monótono con respecto al orden del subconjunto (respeta la aproximación, categóricamente , es un functor sobre el poset${\displaystyle {\mathcal {A}}}$):${\displaystyle a'\subset a\in {\mathcal {A}}\implies F(a')\subset F(a).}$
2. Es continuo (categóricamente, conserva los colímites filtrados ):${\textstyle F(\bigcup _{i\in I}^{\uparrow }a_{i})=\bigcup _{i\in I}^{\uparrow }F(a_{i})}$dónde${\textstyle \bigcup _{i\in I}^{\uparrow }}$es la unión dirigida sobre${\displaystyle I}$, el conjunto de aproximaciones finitas de${\displaystyle a}$.
3. Es estable :${\displaystyle a_{1}\cup a_{2}\in {\mathcal {A}}\implies F(a_{1}\cap a_{2})=F(a_{1})\cap F(a_{2}).}$Categóricamente, esto significa que conserva el retroceso :

   

Para ser consideradas estables, las funciones de dos argumentos deben satisfacer el criterio 3 anterior de esta forma:$${\displaystyle a_{1}\cup a_{2}\in {\mathcal {A}}\land b_{1}\cup b_{2}\in {\mathcal {B}}\implies F(a_{1}\cap a_{2},b_{1}\cap b_{2})=F(a_{1},b_{1})\cap F(a_{2},b_{2})}$$lo que significaría que, además de la estabilidad en cada argumento por separado, el retroceso

se conserva con funciones estables de dos argumentos. Esto lleva a la definición de un espacio producto.${\displaystyle {\mathcal {A}}\ \&\ {\mathcal {B}}}$que establece una biyección entre funciones binarias estables (funciones de dos argumentos) y funciones unarias estables (de un argumento) sobre el espacio producto. El espacio de coherencia producto es un producto en el sentido categórico, es decir, satisface la propiedad universal para productos. Se define mediante las ecuaciones:

• ${\displaystyle |{\mathcal {A}}\ \&\ {\mathcal {B}}|=|{\mathcal {A}}|+|{\mathcal {B}}|=(\{1\}\times |{\mathcal {A}}|)\cup (\{2\}\times |{\mathcal {B}}|)}$(es decir, el conjunto de fichas de${\displaystyle {\mathcal {A}}\ \&\ {\mathcal {B}}}$es el coproducto (o unión disjunta ) de los conjuntos de tokens de${\displaystyle {\mathcal {A}}}$y${\displaystyle {\mathcal {B}}}$.
• Los tokens de diferentes conjuntos siempre son coherentes, y los tokens del mismo conjunto son coherentes precisamente cuando son coherentes en ese conjunto.
  • ${\displaystyle (1,\alpha )\sim _{{\mathcal {A}}\ \&\ {\mathcal {B}}}(1,\alpha ')\iff \alpha \sim _{\mathcal {A}}\alpha '}$
  • ${\displaystyle (2,\beta )\sim _{{\mathcal {A}}\ \&\ {\mathcal {B}}}(2,\beta ')\iff \beta \sim _{\mathcal {B}}\beta '}$
  • ${\displaystyle (1,\alpha )\sim _{{\mathcal {A}}\ \&\ {\mathcal {B}}}(2,\beta ),\forall \alpha \in |{\mathcal {A}}|,\beta \in |{\mathcal {B}}|}$