Movatterモバイル変換

We show that every MALL proof-structure [9] satisfies the property of softness, originally a categorical notion introduced by Joyal. Furthermore, we show that the notion of hereditary softness precisely captures Girard’s algebraic restriction of the technical condition on proof-structures. Relying on this characterization, we prove a MALL+Mix sequentialization theorem by a proof-theoretical method, using Girard’s notion of jump. Our MALL+Mix correctness criterion subsumes the Danos/Fleury-Retoré criterion [6] for MLL+Mix.

Direct download(4 more)   Export citation   Bookmark   4 citations  

We shall give a direct proof of the independence result of a Buchholz style-Hydra Game on labeled finite trees. We shall show that Takeuti-Arai's cut-elimination procedure of $(\Pi^{1}_{1}-CA) + BI$ and of the iterated inductive definition systems can be directly expressed by the reduction rules of Buchholz's Hydra Game. As a direct corollary the independence result of the Hydra Game follows.

Direct download(4 more)   Export citation   Bookmark   2 citations  

We first note that Gentzen's proof-reduction for his consistency proof of PA can be directly interpreted as moves of Kirby-Paris' Hydra Game, which implies a direct independence proof of the game . Buchholz's Hydra Game for labeled hydras is known to be much stronger than PA. However, we show that the one-dimensional version of Buchholz's Game can be exactly identified to Kirby-Paris' Game , by a simple and natural interpretation . Jervell proposed another type of a combinatorial game, by abstracting (...) Gentzen's proof-reductions and showed that his game is independent of PA. We show that this Jervell's game is actually much stronger than PA, by showing that the critical ordinal of Jervell's game is φω = ϵ0) in the Veblen hierarchy of ordinals. (shrink)

Direct download   Export citation   Bookmark   2 citations  

We prove that the full completeness theorem for MLL+Mix holds by the simple interpretation via formulas as objects and proofs as Z-invariant morphisms in the *-autonomous category of topologized vector spaces. We do this by generalizing the recent work of Blute and Scott 101–142) where they used the semantical framework of dinatural transformation introduced by Girard–Scedrov–Scott , Logic from Computer Science, vol. 21, Springer, Berlin, 1992, pp. 217–241). By omitting the use of dinatural transformation, our semantics evidently allows the interpretation (...) of the cut-rule, while the original Blute–Scott's does not. Moreover, our interpretation for proofs is preserved automatically under the cut elimination procedure. In our semantics proofs themselves are characterized by the concrete algebraic notion “Z-invariance”, and our denotational semantics provides the full completeness. Our semantics is naturally extended to the full completeness semantics for CyLL+Mix owing to an elegant method of Blute–Scott 1413–1436) 101–142))). (shrink)

Direct download(4 more)   Export citation   Bookmark   2 citations  

In this paper, we present a categorical model for Multiplicative Additive Polarized Linear Logic , which is the linear fragment of Olivier Laurent’s Polarized Linear Logic. Our model is based on an adjunction between reflective/coreflective full subcategories / of an ambient *-autonomous category . Similar structures were first introduced by M. Barr in the late 1970’s in abstract duality theory and more recently in work on game semantics for linear logic. The paper has two goals: to discuss concrete models and (...) to present various completeness theorems.As concrete examples, we present a hypercoherence model, using Ehrhard’s hereditary/anti-hereditary objects, a Chu-space model, a double gluing model over our categorical framework, and a model based on iterated double gluing over a *-autonomous category.For the multiplicative fragment of. (shrink)

Direct download(4 more)   Export citation   Bookmark   1 citation  

This paper presents a polarized phase semantics, with respect to which the linear fragment of second order polarized linear logic of Laurent [15] is complete. This is done by adding a topological structure to Girard's phase semantics [9]. The topological structure results naturally from the categorical construction developed by Hamano—Scott [12]. The polarity shifting operator ↓ (resp. ↑) is interpreted as an interior (resp. closure) operator in such a manner that positive (resp. negative) formulas correspond to open (resp. closed) facts. (...) By accommodating the exponentials of linear logic, our model is extended to the polarized fragment of the second order linear logic. Strong forms of completeness theorems are given to yield cut-eliminations for the both second order systems. As an application of our semantics, the first order conservativity of linear logic is studied over its polarized fragment of Laurent [16]. Using a counter model construction, the extension of this conservativity is shown to fail into the second order, whose solution is posed as an open problem in [16]. After this negative result, a second order conservativity theorem is proved for an eta expanded fragment of the second order linear logic, which fragment retains a focalized sequent property of [3]. (shrink)

Direct download(6 more)   Export citation   Bookmark  

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. (shrink)

Direct download(4 more)   Export citation   Bookmark   4 citations