Categorical semantics

Revision as of 19:41, 23 March 2009

Constructing denotational models of linear can be a tedious work. Categorical model are useful to identify the fundamental structure of these models, and thus simplify and make more abstract the elaboration of those models.

TODO: why categories? how to extract categorical models? etc.

See ^[1]for a more detailed introduction to category theory.

Modeling IMLL

A model of IMLL is a closed symmetric monoidal category. We recall the definition of these categories below.

Definition (Monoidal category)

A monoidal category $(\mathcal{C},\otimes,I,\alpha,\lambda,\rho)$ is a category $\mathcal{C}$ equipped with

a functor $\otimes:\mathcal{C}\times\mathcal{C}\to\mathcal{C}$ called tensor product,
an object $I$ called unit object,
three natural isomorphisms $α$ , $λ$ and $ρ$ , called respectively associator, left unitor and right unitor, whose components are

$\alpha_{A,B,C}:(A\otimes B)\otimes C\to A\otimes (B\otimes C) \qquad \lambda_A:I\otimes A\to A \qquad \rho_A:A\otimes I\to A$

such that

for every objects $A, B, C, D$ in $\mathcal{C}$ , the diagram

commutes,

for every objects $A$ and $B$ in $\mathcal{C}$ , the diagrams

commute.

Definition (Braided, symmetric monoidal category)

A braided monoidal category is a category together with a natural isomorphism of components

$\gamma_{A,B}:A\otimes B\to B\otimes A$

called braiding, such that the two diagrams

UNIQ1f1801c714089712-math-00000011-QINU

commute for every objects $A$ , $B$ and $C$ .

A symmetric monoidal category is a braided monoidal category in which the braiding satisfies

$\gamma_{B,A}\circ\gamma_{A,B}=A\otimes B$

for every objects $A$ and $B$ .

Definition (Closed monoidal category)

A monoidal category $(\mathcal{C},\tens,I)$ is left closed when for every object $A$ , the functor

$B\mapsto A\otimes B$

has a right adjoint, written

$B\mapsto(A\limp B)$

This means that there exists a bijection

$\mathcal{C}(A\tens B, C) \cong \mathcal{C}(B,A\limp C)$

which is natural in $B$ and $C$ . Equivalently, a monoidal category is left closed when it is equipped with a left closed structure, which consists of

an object $A\limp B$ ,
a morphism $\mathrm{eval}_{A,B}:A\tens (A\limp B)\to B$ , called left evaluation,

for every objects $A$ and $B$ , such that for every morphism $f:A\otimes X\to B$ there exists a unique morphism $h:X\to A\limp B$ making the diagram

T O D O

commute.

Dually, the monoidal category $\mathcal{C}$ is right closed when the functor $B\mapsto B\otimes A$ admits a right adjoint. The notion of right closed structure can be defined similarly.

In a symmetric monoidal category, a left closed structure induces a right closed structure and conversely, allowing us to simply speak of a closed symmetric monoidal category.

Modeling the additives

Definition (Product)

Definition (Monoid)

Property

Categories with products vs monoidal categories.

Modeling IMLL

Introduced in^[2].

Definition (Linear-non linear (LNL) adjunction)

A linear-non linear adjunction is a symmetric monoidal adjunction between lax monoidal functors

$(\mathcal{M},\times,\top) TODO (\mathcal{L},\otimes,I)$

in which the category $\mathcal{M}$ has finite products.

Modeling negation

*-autonomous categories

Definition (*-autonomous category)

Suppose that we are given a symmetric monoidal closed category $(\mathcal{C},\tens,I)$ and an object $R$ of $\mathcal{C}$ . For every object $A$ , we define a morphism

$\partial_{A}:A\to(A\limp R)\limp R$

as follows. By applying the bijection of the adjunction defining (left) closed monoidal categories to the identity morphism $\mathrm{id}_{A\limp R}:A\limp R \to A\limp R$ , we get a morphism $A\tens (A\limp R)\to R$ , and thus a morphism $(A\limp R)\tens A\to R$ by precomposing with the symmetry $\gamma_{A\limp R,A}$ . The morphism $\partial_A$ is finally obtained by applying the bijection of the adjunction defining (left) closed monoidal categories to this morphism. The object $R$ is called dualizing when the morphism $\partial_A$ is a bijection for every object $A$ of $\mathcal{C}$ . A symmetric monoidal closed category is *-autonomous when it admits such a dualizing object.

Compact closed categories

Definition (Compact closed category)

A symmetric monoidal category $(\mathcal{C},\tens,I)$ is compact closed when every object $A$ has a (left) dual.

In a compact closed category the left and right duals of an object $A$ are isomorphic.

Property

A compact closed category is monoidal closed.

Other categorical models

Properties of categorical models

The Kleisli category

References

↑ MacLane, Saunders. Categories for the Working Mathematician. Volume 5, 1971.
↑ Benton, Nick. A Mixed Linear and Non-Linear Logic: Proofs, Terms and Models.. CSL'94. journal. Volume 933, 1995.

[0] MacLane, Saunders. Categories for the Working Mathematician. Volume 5, 1971.

[1] Benton, Nick. A Mixed Linear and Non-Linear Logic: Proofs, Terms and Models.. CSL'94. journal. Volume 933, 1995.

[1]

[2]

@@ Line 86: / Line 86: @@
 == Modeling negation ==
+=== *-autonomous categories ===
 {{Definition|title=*-autonomous category|
 Suppose that we are given a symmetric monoidal closed category <math>(\mathcal{C},\tens,I)</math> and an object <math>R</math> of <math>\mathcal{C}</math>. For every object <math>A</math>, we define a morphism
 :<math>\partial_{A}:A\to(A\limp R)\limp R</math>
 as follows. By applying the bijection of the adjunction defining (left) closed monoidal categories to the identity morphism <math>\mathrm{id}_{A\limp R}:A\limp R \to A\limp R</math>, we get a morphism <math>A\tens (A\limp R)\to R</math>, and thus a morphism <math>(A\limp R)\tens A\to R</math> by precomposing with the symmetry <math>\gamma_{A\limp R,A}</math>. The morphism <math>\partial_A</math> is finally obtained by applying the bijection of the adjunction defining (left) closed monoidal categories to this morphism. The object <math>R</math> is called ''dualizing'' when the morphism <math>\partial_A</math> is a bijection for every object <math>A</math> of <math>\mathcal{C}</math>. A symmetric monoidal closed category is ''*-autonomous'' when it admits such a dualizing object.
+}}
+=== Compact closed categories ===
+{{Definition|title=Compact closed category|
+A symmetric monoidal category <math>(\mathcal{C},\tens,I)</math> is ''compact closed'' when every object <math>A</math> has a (left) dual.
+}}
+In a compact closed category the left and right duals of an object <math>A</math> are isomorphic.
+{{Property|
+A compact closed category is monoidal closed.
 }}

Categorical semantics

Revision as of 19:41, 23 March 2009

Contents

Modeling IMLL

Modeling the additives

Modeling IMLL

Modeling negation

*-autonomous categories

Compact closed categories

Other categorical models

Properties of categorical models

The Kleisli category

References

Views

Personal tools

Navigation

Search

Tools