Preservation theorems in linear continuous logic

Linear continuous logic is the fragment of continuous logic obtained by restricting connectives to addition and scalar multiplications. Most results in the full continuous logic have a counterpart in this fragment. In particular a linear form of the compactness theorem holds. We prove this variant and use it to deduce some basic preservation theorems.     

Models of linear logic

We engage a study of nonmodal linear logic which takes times ⊗ and the linear conditional ⊸ to be the basic connectives instead of times and linear negation ()^⊥ as in Girard's approach. This difference enables us to obtain a very large subsystem of linear logic (called positive linear logic) without an involutionary negation (if the law of double negation is removed from linear logic in Girard's formulation, the resulting subsystem is extremely limited). Our approach enables us to obtain several natural models for various subsystems of linear logic, including a generic model for the so-called minimal linear logic. In particular, it is seen that these models arise spontaneously in the transition from set theory to multiset theory. We also construct a model of full (nonmodal) linear logic that is generic relative to any model of positive linear logic. However, the problem of constructing a generic model for positive linear logic remains open. Bibliography: 2 titles. Published inZapiski Nauchnykh Seminarov POMI, Vol. 220, 1995, pp. 23–35. Original     

Local computation in linear logic

This work deals with the exponential fragment of Girard's linear logic ([3]) without the contraction rule, a logical system which has a natural relation with the direct logic ([10], [7]). A new sequent calculus for this logic is presented in order to remove the weakening rule and recover its behavior via a special treatment of the propositional constants, so that the process of cut-elimination can be performed using only “local” reductions. Hence a typed calculus, which admits only local rewriting rules, can be introduced in a natural manner. Its main properties — normalizability and confluence — has been investigated; moreover this calculus has been proved to satisfy a Curry-Howard isomorphism ([6]) with respect to the logical system in question. MSC: 03B40, 03F05.     

Dynamic linear time temporal logic

A simple extension of the propositional temporal logic of linear time is proposed. The extension consists of strengthening the until operator by indexing it with the regular programs of propositional dynamic logic. It is shown that DLTL, the resulting logic, is expressively equivalent to the monadic second-order theory of ω-sequences. In fact, a sublogic of DLTL which corresponds to propositional dynamic logic with a linear time semantics is already expressively complete. We show that DLTL has an exponential time decision procedure and admits a finitary axiomatization. We also point to a natural extension of the approach presented here to a distributed setting.     

Maximality of compression semigroups

LetG be a connected semisimple Lie group andr an involution onG. Further letL be an open subgroup of the groupG ^r ofr-fixed points andP⊂-G a parabolic subgroup. The semigroupS(L,P)∶={g∈G∶gLP⊂-LP} is called the compression semigroup of theL-orbit of the base point in the flag manifoldG/P. We show that compression semigroups for open orbits and regular symmetric pairs are maximal semigroups. Supported by a DFG Heisenberg-grant.     

Non decomposable connectives of linear logic

This paper studies the so-called generalized multiplicative connectives of linear logic, focusing on the question of finding the “non-decomposable” ones, i.e., those that cannot be expressed as combinations of the default binary connectives of multiplicative linear logic, ⊗ (times) and ⅋ (par). In particular, we concentrate on generalized connectives of a surprisingly simple form, called “entangled connectives”, and prove a characterization theorem giving a criterion for identifying the undecomposable entangled ones.     

A note on infinitary continuous logic

We show how to extend the Continuous Propositional Logic by means of an infinitary rule in order to achieve a Strong Completeness Theorem. Eventually we investigate how to recover a weak version of the Deduction Theorem.     

Modeling linear logic with implicit functions

Just as intuitionistic proofs can be modeled by functions, linear logic proofs, being symmetric in the inputs and outputs, can be modeled by relations (for example, cliques in coherence spaces). However generic relations do not establish any functional dependence between the arguments, and therefore it is questionable whether they can be thought as reasonable generalizations of functions. On the other hand, in some situations (typically in differential calculus) one can speak in some precise sense about an implicit functional dependence defined by a relation. It turns out that it is possible to model linear logic with implicit functions rather than general relations, an adequate language for such a semantics being (elementary) differential calculus. This results in a non-degenerate model enjoying quite strong completeness properties.     

Maximality of analytic operator algebras

LetM be a σ-finite von Neumann algebra andα be an action ofR onM. LetH ^∞(α) be the associated analytic subalgebra; i.e.H ^∞(α)={X ∈M: sp_∞(X) [0, ∞]}. We prove that every σ-weakly closed subalgebra ofM that containsH ^∞(α) isH ^∞(γ) for some actionγ ofR onM. Also we show that (assumingZ(M)∩M ^α = Ci)H ^∞(α) is a maximal σ-weakly closed subalgebra ofM if and only if eitherH ^∞(α)={A ∈M: (I−F)xF=0} for some projectionF ∈M, or sp(α)=Γ(α).     

Unification in linear temporal logic LTL

We prove that a propositional Linear Temporal Logic with Until and Next (LTL) has unitary unification. Moreover, for every unifiable in LTL formula A there is a most general projective unifier, corresponding to some projective formula B, such that A is derivable from B in LTL. On the other hand, it can be shown that not every open and unifiable in LTL formula is projective. We also present an algorithm for constructing a most general unifier.     

The Maximality of Cartesian Categories

It is proved that equations between arrows assumed for cartesian categories are maximal in the sense that extending them with any new equation in the language of free cartesian categories collapses a cartesian category into a preorder. An analogous result holds for categories with binary products, which may lack a terminal object. The proof is based on a coherence result for cartesian categories, which is related to model‐theoretic methods of normalization. This maximality of cartesian categories, which is analogous to Post completeness, shows that the usual equivalence between deductions in conjunctive logic induced by βη normalization in natural deduction is chosen optimally.     

Polar Subspaces and Automatic Maximality

This paper is about certain linear subspaces of Banach SN spaces (that is to say Banach spaces which have a symmetric nonexpansive linear map into their dual spaces). We apply our results to monotone linear subspaces of the product of a Banach space and its dual. In this paper, we establish several new results and also give improved proofs of some known ones in both the general and the special contexts.     

Normal deduction in the intuitionistic linear logic

We describe a natural deduction system NDIL for the second order intuitionistic linear logic which admits normalization and has a subformula property. NDIL is an extension of the system for !-free multiplicative linear logic constructed by the author and elaborated by A. Babaev. Main new feature here is the treatment of the modality !. It uses a device inspired by D. Prawitz' treatment of S4 combined with a construction introduced by the author to avoid cut-like constructions used in -elimination and global restrictions employed by Prawitz. Normal form for natural deduction is obtained by Prawitz translation of cut-free sequent derivations. Received: March 29, 1996     

Maximality of Positive Operator-valued Measures

A positive operator-valued measure is a (weak-star) countably additive set function from a σ-field Σ to the space of nonnegative bounded operators on a separable complex Hilbert space . Such functions can be written as M = V*E(·)V in which E is a spectral measure acting on a complex Hilbert space and V is a bounded operator from to such that the only closed linear subspace of , containing the range of V and reducing E (Σ), is itself. Attention is paid to an existing notion of maximality for positive operator-valued measures. The purpose of this paper is to show that M is maximal if and only if E, in the above representation of M, generates a maximal commutative von Neumann algebra.