Back to Search
Start Over
Softness of hypercoherences and MALL full completeness
- Source :
- Annals of Pure and Applied Logic. 131(1-3):1-63
- Publication Year :
- 2005
- Publisher :
- Elsevier BV, 2005.
-
Abstract
- We prove a full completeness theorem for multiplicative–additive linear logic (i.e. MALL ) 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 MALL 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 MALL proof-structure. • The proof-structure associated with any dinatural transformation is a MALL 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.
- Subjects :
- Softness
Discrete mathematics
Functor
Logic
Double gluing
010102 general mathematics
MALL proof-nets
Structure (category theory)
Hypercoherences
0102 computer and information sciences
Dinaturality
01 natural sciences
Multiplicative–additive linear logic
Linear logic
Denotation
Full completeness
Fragment (logic)
010201 computation theory & mathematics
Completeness (order theory)
Gödel's completeness theorem
0101 mathematics
Dinatural transformation
Mathematics
Subjects
Details
- ISSN :
- 01680072
- Volume :
- 131
- Issue :
- 1-3
- Database :
- OpenAIRE
- Journal :
- Annals of Pure and Applied Logic
- Accession number :
- edsair.doi.dedup.....6d75c3c60b9c77d44181ad98cfd58e51
- Full Text :
- https://doi.org/10.1016/j.apal.2004.05.002