Softness of hypercoherences and full completeness

Annals of Pure and Applied Logic 131 (1-3):1-63 (2005)
  Copy   BIBTEX

Abstract

We prove a full completeness theorem for multiplicative–additive linear logic using a double gluing construction applied to Ehrhard’s *-autonomous category of hypercoherences. This is the first non-game-theoretic full completeness theorem for this fragment. Our main result is that every dinatural transformation between definable functors arises from the denotation of a cut-free proof. Our proof consists of three steps. We show:• Dinatural transformations on this category satisfy Joyal’s softness property for products and coproducts.• Softness, together with multiplicative full completeness, guarantees that every dinatural transformation corresponds to a Girard proof-structure.• The proof-structure associated with any dinatural transformation is a proof-net, hence a denotation of a proof. This last step involves a detailed study of cycles in additive proof-structures.The second step is a completely general result, while the third step relies on the concrete structure of a double gluing construction over hypercoherences.

Links

PhilArchive



    Upload a copy of this work     Papers currently archived: 92,283

External links

Setup an account with your affiliations in order to access resources via your University's proxy server

Through your library

Similar books and articles

Z-modules and full completeness of multiplicative linear logic.Masahiro Hamano - 2001 - Annals of Pure and Applied Logic 107 (1-3):165-191.
Linear Läuchli semantics.R. F. Blute & P. J. Scott - 1996 - Annals of Pure and Applied Logic 77 (2):101-142.
The Shuffle Hopf Algebra and Noncommutative Full Completeness.R. F. Blute & P. J. Scott - 1998 - Journal of Symbolic Logic 63 (4):1413-1436.
The shuffle Hopf algebra and noncommutative full completeness.R. F. Blute & P. J. Scott - 1998 - Journal of Symbolic Logic 63 (4):1413-1436.
Completeness of MLL Proof-Nets w.r.t. Weak Distributivity.Jean-Baptiste Joinet - 2007 - Journal of Symbolic Logic 72 (1):159 - 170.

Analytics

Added to PP
2014-01-16

Downloads
25 (#636,619)

6 months
9 (#317,143)

Historical graph of downloads
How can I increase my downloads?

References found in this work

The structure of multiplicatives.Vincent Danos & Laurent Regnier - 1989 - Archive for Mathematical Logic 28 (3):181-203.
Linear logic: its syntax and semantics.Jean-Yves Girard - 1995 - In Jean-Yves Girard, Yves Lafont & Laurent Regnier (eds.), Advances in Linear Logic. Cambridge University Press. pp. 222--1.
Linear Läuchli semantics.R. F. Blute & P. J. Scott - 1996 - Annals of Pure and Applied Logic 77 (2):101-142.

View all 8 references / Add more references