Sammanhängande utrymme

För koherenta utrymmen i topologi, se spektralrymd .

I bevisteorin är ett koherent utrymme (även koherensutrymme) ett begrepp som introduceras i den semantiska studien av linjär logik .

Låt en mängd C ges. Två delmängder S , T ⊆ C sägs vara ortogonala , skrivna S ⊥ T , om S ∩ T är ∅ eller en singelton . Dualen i en familj F ⊆ ℘( C ) är familjen F ^⊥ av alla delmängder S ⊆ C ortogonal mot varje medlem av F , dvs. sådan att S ⊥ T för alla T ∈ F . Ett koherent rum F över C är en familj av C -delmängder för vilka F = ( F ^⊥ ) ^⊥ .

I Bevis och Typer kallas koherenta rum koherensrum. En fotnot förklarar att även om de i det franska originalet var espaces cohérents , användes koherensrymdsöversättningen eftersom spektrala utrymmen ibland kallas koherenta utrymmen.

Definitioner

Enligt definitionen av Jean-Yves Girard är ett koherensutrymme ${\mathcal {A}}$ en samling uppsättningar som uppfyller nedåtgående och binär fullständighet i följande betydelse:

• Nedstängning: alla delmängder av en uppsättning i ${\mathcal {A}}$ förblir i ${\mathcal {A}}$ : ${\ displaystyle a'\subset a\in {\mathcal {A}}\implies a'\in {\mathcal {A}}}$
• Binär fullständighet: för varje delmängd $M$ av ${\displaystyle {\mathcal {A}}} ,$ om den parvisa föreningen av något av dess element är i ${\mathcal {A}}$ , så är föreningen av alla element i $M$ : $\forall M\subset {\mathcal {A}},\left((\forall a_{1},a_{2}\in M,\ a_{1}\cup a_{2}\in {\mathcal {A }})\implies \bigcup M\in {\mathcal {A}}\right)$

Elementen i uppsättningarna i ${\mathcal {A}}$ är kända som tokens , och de är elementen i mängden $|{\mathcal {A}}|=\bigcup {\mathcal {A}}=\{\alpha |\{\alpha \}\in {\mathcal {A}}\ }$ .

Koherensrum överensstämmer en-till-en med (oriktade) grafer (i betydelsen en bijektion från uppsättningen koherensrum till den för oriktade grafer). Grafen som motsvarar ${\mathcal {A}}$ kallas webben av ${\mathcal {A}}$ och är grafen inducerad en reflexiv , symmetrisk relation $\sim$ över tokenutrymmet $|{\mathcal {A}}|$ av ${\mathcal {A}}$ känd som coherence modulo ${\mathcal {A}}$ definierad som:

$$a\sim b\iff \{a,b\}\in {\mathcal {A}}$$

I webben av ${\mathcal {A}}$ är noder tokens från $|{\mathcal {A}}|$ och en kant delas mellan noderna $a$ och $b$ när $a\sim b$ (dvs ${\displaystyle \{a,b\}\in {\mathcal {A}}} .)$ Denna graf är unik för varje koherensutrymme, och i synnerhet element i ${\mathcal {A }}$ är exakt klicken på webben av ${\displaystyle {\mathcal {A}}},$ dvs. uppsättningarna av noder vars element är parvis intill varandra (har en kant .)

Koherensrum som typer

Koherensrum kan fungera som en tolkning för typer i typteori där punkter av en typ ${\mathcal {A}}$ är punkter i koherensutrymmet ${\mathcal {A}}$ . Detta gör att vissa strukturer kan diskuteras på typer. Till exempel kan varje term $a$ av typen ${\mathcal {A}}$ ges en uppsättning ändliga approximationer $I$ som i själva verket är en riktad mängd med delmängdsrelation. Med $a$ som en koherent delmängd av tokenutrymmet $|{\mathcal {A}}|$ (dvs. ett element av ${\mathcal {A}}$ ), vilket element som helst av $I$ är en ändlig delmängd av $a$ och därför också koherent, och vi har $a=\bigcup a_{i},a_{i}\in I.$

Stabila funktioner

Funktioner mellan typerna ${\mathcal {A}}\to {\mathcal {B}}$ ses som stabila funktioner mellan koherensrum. En stabil funktion definieras som en som respekterar approximationer och uppfyller ett visst stabilitetsaxiom. Formellt är $F:{\mathcal {A}}\to {\mathcal {B}}$ en stabil funktion när

1. Den är monoton med avseende på delmängdsordningen (respekterar approximation, kategoriskt , är en funktor över poset ${\mathcal {A}}$ ): $a'\subset a\in {\mathcal {A}}\implies F(a')\subset F(a).$
2. Den är kontinuerlig (kategoriskt, bevarar filtrerade kogränser ): ${\textstyle F(\bigcup _{i\in I}^{\uparrow }a_{i})=\bigcup _{i\in I}^{\uparrow }F(a_{i})} där ⋃ i$ ∈ $\bigcup _{i\in I}^{\ uparrow }}$ är den riktade föreningen över $I$ , uppsättningen av ändliga approximationer av $a$ .
3. Den är stabil : $a_{1}\cup a_{2}\in {\mathcal {A}}\implies F(a_{1}\cap a_{2})=F(a_{1})\cap F(a_ {2}).$ Kategoriskt betyder detta att det bevarar tillbakadraget :
   

Produktutrymme

För att anses vara stabila måste funktioner av två argument uppfylla kriteriet 3 ovan i denna form:

$${\ 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})}$$

vilket skulle innebära att förutom stabiliteten i varje argument ensam, pullbacken

bevaras med stabila funktioner av två argument. Detta leder till definitionen av ett produktutrymme ${\mathcal {A}}\ \&\ {\mathcal {B}}$ som gör en bijektion mellan stabila binära funktioner (funktioner av två argument) och stabila unära funktioner (ett argument) över produktutrymmet. Produktens koherensutrymme är en produkt i kategorisk mening, dvs den uppfyller produktens universella egendom . Det definieras av ekvationerna:

• $|{\mathcal {A}}\ \&\ {\mathcal {B}}|=|{\mathcal {A }}|+|{\mathcal {B}}|=(\{1\}\times |{\mathcal {A}}|)\cup (\{2\}\times |{\mathcal {B}} |)$ (dvs. uppsättningen av tokens av ${\mathcal {A}}\ \&\ {\mathcal {B}}$ är samprodukten (eller disjunkt union ) av token-uppsättningarna av ${ \displaystyle {\mathcal {A}}}$ och ${\mathcal {B}}$ .
• Polletter från olika uppsättningar är alltid koherenta och polletter från samma uppsättning är koherenta exakt när de är koherenta i den uppsättningen.
  • $(1,\alpha )\sim _{{\mathcal {A}}\ \&\ {\mathcal {B }}}(1,\alpha ')\iff \alpha \sim _{\mathcal {A}}\alpha '$
  • $(2,\beta )\sim _{{\mathcal {A}}\ \&\ {\mathcal {B }}}(2,\beta ')\iff \beta \sim _{\mathcal {B}}\beta '$
  • $(1,\alpha )\sim _{{\mathcal {A}}\ \&\ {\mathcal {B}}}(2,\beta ),\forall \alpha \in |{\mathcal { A}}|,\beta \in |{\mathcal {B}}|$

• Girard, J.-Y. ; Lafont, Y.; Taylor, P. (1989), Proofs and types (PDF) , Cambridge University Press .
• Girard, J.-Y. (2004), "Mellan logik och kvantik: ett område", i Ehrhard; Girard; Ruet; et al. (red.), Linjär logik i datavetenskap (PDF) , Cambridge University Press .