nLab
double gluing

Double gluing

Double gluing

Idea

Double gluing, coupled with orthogonality, is a method for creating new models of linear logic such as star-polycategories and star-autonomous categories. It is a variation of gluing methods (such as Artin gluing) that works for classical rather than intuitionistic (linear) logic. It is a general method that encompases many existing spaces such as phase spaces, coherence spaces, finiteness spaces, totality spaces, probabilistic coherence spaces?.

Although the name presumably refers to gluing along “two functors at once”, it turns out to also be closely connected to double categories, and in particular to comma double categories.

Double gluing along hom-sets with orthogonality

Coherence spaces via double gluing

We begin with the definition of coherence spaces, presented in a way that is amenable to generalization.

If uXu\subset X and vXv\subseteq X, write uvu\perp v if |uv|1|u\cap v|\leq 1. Given UP(X)U\subseteq P(X), let U ={vXuU.uv}{U}^\perp=\{v \subseteq X \mid \forall u \in U. u \perp v\}. Now a coherence space can be given by a set XX together with a set UP(X)U\subseteq P(X) of cliques and a set VP(X)V\subseteq P(X) of co-cliques that are orthogonal in the sense that U=V U=V^\perp and V=U V=U^\perp.

In this presentation of coherence spaces, we can regard uu as a relation 1X1\to X, and vv as a relation X1X\to 1. The relation \perp is then a family of subsets X[1X]×[X1]\perp_X\subseteq [1\to X]\times [X\to 1].

General definition of double gluing along hom-sets with tight orthogonality

Let CC be a symmetric monoidal category with an object I *I^*, and let a family XC(I,X)×C(X,I *)\perp_X\subseteq C(I,X)\times C(X,I^*) of relations be given. (For coherence spaces, let C=RelC=Rel and I=I *I=I^* and \perp be as above.

Let XX be an object of CC. The relation \perp defines a Galois connection between C(I,X)C(I,X) and C(X,I *)C(X,I^*) in the usual way: for UC(I,X){U}\subseteq C(I,X) we have U ={vC(X,I *)uU.uv}{U}^\perp = \{ v \in C(X,I^*) \mid \forall u\in {U}. u\perp v \}, and likewise for VC(X,J){V}\subseteq C(X,J) we have V ={uC(I,X)vV.uv}{V}^\perp = \{ u \in C(I,X) \mid \forall v\in {V}. u\perp v \}.

We define a tight orthogonality space (X,U,V)(X,U,V) to be an object XCX\in C together with UC(I,X){U}\subseteq C(I,X) and VC(X,I *){V}\subseteq C(X,I^*) that is a fixed point of this Galois connection, U =V{U}^\perp = {V} and V =U{V}^\perp= U.
A morphism between tight orthogonality spaces (X 1,U 1,V 1)(X 2,U 2,V 2)(X_1,{U_1},{V_1})\to (X_2,{U_2},{V_2}) is a morphism fC(X 1,X 2)f\in C(X_1,X_2) such that

  1. if uU 1u\in {U_1}, then fuU 2f\circ u \in {U_2};
  2. if vV 2v\in{V_2} then vfV 1v\circ f\in {V_1}.

Theorem: (Hyland-Schalk): If an orthogonality XC(I,X)×C(X,I *)\bot_X\subseteq C(I,X)\times C(X,I^*) on a star-autonomous category satisfies four conditions for orthogonalities, a symmetry condition, and a precision condition, then the tight orthogonality spaces form a star-polycategory.

One source of good orthogonality relations XC(I,X)×C(X,I *)\bot_X\subseteq C(I,X)\times C(X,I^*) are the focuses FC(I,I *)F\subseteq C(I,I^*), from which we can let u Xvu\bot_X v if (vu)F(v\circ u)\in F. However, not all the useful orthogonalities arise from focuses.

Examples

  • coherence spaces: Let C=RelC=Rel, and let u Xvu\bot_X v if |uv|1|u\cap v|\leq 1.
  • totality spaces: Let C=RelC=Rel, and let u Xvu\bot_X v if |uv|=1|u\cap v|=1.
  • finiteness spaces: Let C=RelC=Rel, and let u Xvu\bot_X v if |uv|<ω|u\cap v|\lt\omega.
  • phase semantics: Let MM be a commutative monoid, and let FMF\subseteq M be given. Regarding MM as a one-object category, with object II, we put u Ivu\bot_I v if vuFvu\in F. Then an object of the orthogonality category (I,U,V)(I,U,V) is determined by a “fact” UMU\subseteq M. However, to get the poset version of phase semantics we restrict the morphisms of the orthogonality category to the ones that come from the identity III\to I.
  • probabilistic coherence spaces: Let CC be the category of weighted relations, i.e. countable sets and [0,][0,\infty]-valued matrices between them. Let u Xvu\bot_X v if (vu)[0,1](v\circ u)\in [0,1]. In other words, the focus FC(I,I *)F\subseteq C(I,I^*) comprises the scalars in [0,1][0,1]. One then cuts down further to impose a bounded completeness condition.
  • quantum causal structure: Let C=CPC=CP, the category of finite dimensional Hilbert spaces and completely positive maps between them (see quantum operation, although here we do not begin by insisting that they are trace preserving). Let u Xvu\bot_X v if vu=1v\circ u=1. In other words, the focus FCP(,)F\subseteq CP(\mathbb{C},\mathbb{C}) is the singleton map {1}\{1\}. Now, for any finite dimensional Hilbert space XX, {trace X} \{trace_X\}^\perp comprises “states” of XX, and a morphism (X,{trace X} ,{trace X} )(Y,{trace Y} ,{trace Y} )(X,\{trace_X\}^\perp,\{trace_X\}^{\perp\perp})\to (Y,\{trace_Y\}^\perp,\{trace_Y\}^{\perp\perp}) is the same thing as a quantum operation, i.e. a completely positive trace preserving map.
  • Frölicher spaces: Let C=SetC=Set, let I=I *=I=I^*=\mathbb{R}, and let u Xvu\bot_X v if (vu):(v\circ u):\mathbb{R}\to\mathbb{R} is smooth. In other words, the focus FC(,)F\subseteq C(\mathbb{R},\mathbb{R}) comprises the smooth maps.

General double gluing

Let CC be any (symmetric) polycategory and EE a co-subunary polycategory (i.e. all morphisms have codomain arity 0 or 1), and let L:CChu(E)L:C\to Chu(E) be a polycategory functor. We consider CC as a vertically discrete double polycategory and LL as a functor Chu(E)C\to \mathbb{C}hu(E) into the double Chu construction. Similarly, consider Chu(E)Chu(E) as a vertically discrete double polycategory, including into hu(E)\mathbb{C}hu(E) as the horizontal polycategory.

The double gluing polycategory is then the comma double polycategory (i.e. the comma object in the 2-category of polycategories)

Note that:

  1. If CC is a multicategory (i.e. a co-unary polycategory), then so is Gl(L)Gl(L).

  2. If EE has a counit that is terminal so that Chu(E)=Chu(E,1)Chu(E) = Chu(E,1), CC is a representable multicategory (i.e. a symmetric monoidal category), and EE is representable and closed with products so that Chu(E,1)Chu(E,1) is a *\ast-autonomous category, then polycategory functors CChu(E)C\to Chu(E) are equivalent to pairs of a lax symmetric monoidal functor L:CEL:C\to E and a functor K:CE opK:C\to E^{op} together with a “contraction” L(R)K(RS)K(S)L(R) \otimes K(R\otimes S) \to K(S) satisfying a few axioms. This is how the definition is phrased in Hyland and Schalk.

  3. If CC is a *\ast-polycategory, then *\ast-polycategory functors L:CChu(E)L:C\to Chu(E) are equivalent to functors U 1CEU_{\le 1} C\to E where U 1CU_{\le 1} C is the underlying co-subunary polycategory of CC. If EE has a counit that is terminal so that Chu(E)=Chu(E,1)Chu(E) = Chu(E,1), then these are equivalent to multicategory functors U =1CEU_{=1} C \to E. In particular, we can double-glue along any lax symmetric monoidal functor with *\ast-autonomous domain.

If CC and EE are closed and representable with sufficient limits and colimits, then one can show (similarly to the conditions for a Chu construction to be representable) that Gl(L)Gl(L) is also representable (as a multicategory or a polycategory, respectively) and closed. Thus, double gluing can produce closed symmetric monoidal and *\ast-autonomous categories.

The case of double gluing along hom-functors, discussed above, is the case when E=SetE=Set so that Chu(E,1)Chu(E,1) is *\ast-autonomous, as above, and L(X)=C(I,X)L(X) =C(I,X) with K(X)=C(X,I *)K(X) = C(X,I^*), together with a restriction that the gluing morphisms be monic (and the additional “orthogonality” restriction.

References

  • Martin Hyland and Andrea Schalk, Glueing and orthogonality for models of linear logic, Theoretical Computer Science 294 (2003) 183–231 (pdf)

Last revised on October 14, 2019 at 18:46:06. See the history of this page for a list of all contributions to it.