CUT ELIMINATION FOR PROPOSITIONAL DYNAMIC LOGIC WITHOUT

The aim of this paper is to extend the semantic analysis of tense logic in Rescher/Urquhart [3] to propositional dynamic logic without*. For this we develop a nested sequential calculus whose axioms and rules directly reflect the steps in the semantic analysis. It is shown that this calculus, with the cut rule omitted, is complete with respect to the standard semantics. It follows that cut elimination does hold for this nested sequential calculus. MSC: 03B45.     

A formalization of Sambins's normalization for GL

Sambin [6] proved the normalization theorem (Hauptsatz) for GL, the modal logic of provability, in a sequent calculus version called by him GLS. His proof does not take into account the concept of reduction, commonly used in normalization proofs. Bellini [1], on the other hand, gave a normalization proof for GL using reductions. Indeed, Sambin's proof is a decision procedure which builds cut-free proofs. In this work we formalize this procedure as a recursive function and prove its recursiveness in an arithmetically formalizable way, concluding that the normalization of GL can be formalized in PA. MSC: 03F05, 03B35, 03B45.     

Dual‐Context Sequent Calculus and Strict Implication

We introduce a dual‐context style sequent calculus which is complete with respectto Kripke semantics where implication is interpreted as strict implication in the modal logic K. The cut‐elimination theorem for this calculus is proved by a variant of Gentzen's method.     

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.     

INTERDEFINABILITY OF LAMBEKIAN FUNCTORS

Several Gentzen-style (sequential) syntactic type calculi with product(s) are considered. They form a hierarchy in such a way that one calculus results from another by imposing a new condition (expressed in terms of “structural rules”) upon the sequent-forming operation. It turns out that, at some steps of this process, two different functors collapse to a single one. For the remaining stages of the hierarchy, analogues of Wajsbergs's theorem on non-mutual-definability are proved.     

A Finite Hilbert-Style Axiomatization of the Implication-Less Fragment of the Intuitionistic Propositional Calculus

In this paper we obtain a finite Hilbert-style axiomatization of the implicationless fragment of the intuitionistic propositional calculus. As a consequence we obtain finite axiomatizations of all structural closure operators on the algebra of {–}-formulas containing this fragment. Mathematics Subject Classification: 03B20, 03B22, 06D15.     

Normal form of derivations in the nonassociative and commutative lambek calculus with product

We show that derivations in the nonassociative and commutative Lambek calculus with product can be transformed to a normal form as it is the case with derivations in noncommutative calculi. As an application we obtain that the class of languages generated by categorial grammars based on the nonassociative and commutative Lambek calculus with product is included in the class of CF-languages. MSC: 68Q50, 03D15, 03B65.     

关于“一致有界的一族无穷小的积是无穷小”定理

针对微积分教材关于"无穷小的积是否是无穷小"的命题的模糊叙述,证明"一致有界的一族无穷小的积仍是无穷小".     

Proof-theoretical analysis of order relations

A proof-theoretical analysis of elementary theories of order relations is effected through the formulation of order axioms as mathematical rules added to contraction-free sequent calculus. Among the results obtained are proof-theoretical formulations of conservativity theorems corresponding to Szpilrajns theorem on the extension of a partial order into a linear one. Decidability of the theories of partial and linear order for quantifier-free sequents is shown by giving terminating methods of proof-search.Mathematics Subject Classification (2000): 03F05, 06A05, 06A06     

The Fractional Calculus for Some Stochastic Processes

Abstract

The integration and differentiation of fractional orders are well known concepts for deterministic functions (see Miller, K.S.; Ross, B. An Introduction to Fractional Calculus and Fractional Differential Equations; John Wiley: New York, 1993; I. Podlubny and Ahmed M.A. El-Sayed, On two definitions of fractional calculus Slovak Academy of Sciences Institute of experimental Phys. UEF-03-96 ISBN 80-7099-252-2, 1996; Podlubny, I. Fractional Differential Equations; Acad. Press: San Diego – New York, London etc. 1999; Samko, S.G.; Kilbas, A.A.; Marichev, O. Integral and derivatives of the fractional orders and some of their applications. Nauka i Teknika Minisk 1983). In earlier work, we have studied the fractional calculus for mean square continuous stochastic processes. In this work, we shall study the mean square (m.s.) fractional calculus for stochastic processes which are m.s. Riemann-integrable and prove some its properties.     

Proof-theoretical investigation of temporal logic with time gaps

In the paper, the first-order intuitionistic temporal logic sequent calculus LBJ is considered. The invertibility of some of the LBJ rules, syntactic admissibility of the structural rules and the cut rule in LBJ, as well as Harrop and Craig's interpolation theorems for LBJ are proved. Gentzen's midsequent theorem is proved for the LBJ' calculus which is obtained from LBJ by removing the antecedent disjunction rule from it. Published in Lietuvos Matematikos Rinkinys, Vol. 40, No. 3, pp. 255–276, July–September, 2000.     

Relating Categorical Semantics for Intuitionistic Linear Logic

There are several kinds of linear typed calculus in the literature, some with their associated notion of categorical model. Our aim in this paper is to systematise the relationship between three of these linear typed calculi and their models. We point out that mere soundness and completeness of a linear typed calculus with respect to a class of categorical models are not sufficient to identify the most appropriate class uniquely. We recommend instead to use the notion of internal language when relating a typed calculus to a class of models. After clarifying the internal languages of the categories of models in the literature we relate these models via reflections and coreflections. Mathematics Subject Classifications (2000) 03G30, 03B15, 18C50, 03B20.     

Hilbert's ϵ-operator in intuitionistic type theories

We investigate Hilbert's ?-calculus in the context of intuitionistic type theories, that is, within certain systems of intuitionistic higher-order logic. We determine the additional deductive strength conferred on an intuitionistic type theory by the adjunction of closed ?-terms. We extend the usual topos semantics for type theories to the ?-operator and prove a completeness theorem. The paper also contains a discussion of the concept of “partially defined” ?-term. MSC: 03B15, 03B20, 03G30.     

Cofinal Indiscernibles and some Applications to New Foundations

We prove a theorem about models with indiscernibles that are cofinal in a given linear order. We apply this theorem to obtain new independence results for Quine's set theory New Foundations, thus solving two open problems in this field. Mathematics Subject Classification : 03C55, 03B15, 03B60, 03E70.     

On the Calculus of Limiting Subhessians

We discuss various qualification assumptions that allow calculus rules for limiting subhessians to be derived. Such qualification assumptions are based on a singular limiting subjet derived from a sequence of efficient subsets of symmetric matrices. We introduce a new efficiency notion that results in a weaker qualification assumption than that introduced in Ioffe and Penot (Trans Amer Math Soc 249: 789–807, 1997) and prove some calculus rules that are valid under this weaker qualification assumption. The work of A. Eberhard was supported by ARC research grant DP0664423.     

Light affine lambda calculus and polynomial time strong normalization

Light Linear Logic (LLL) and Intuitionistic Light Affine Logic (ILAL) are logics that capture polynomial time computation. It is known that every polynomial time function can be represented by a proof of these logics via the proofs-as-programs correspondence. Furthermore, there is a reduction strategy which normalizes a given proof in polynomial time. Given the latter polynomial time “weak” normalization theorem, it is natural to ask whether a “strong” form of polynomial time normalization theorem holds or not. In this paper, we introduce an untyped term calculus, called Light Affine Lambda Calculus (λLA), which corresponds to ILAL. λLA is a bi-modal λ-calculus with certain constraints, endowed with very simple reduction rules. The main property of LALC is the polynomial time strong normalization: any reduction strategy normalizes a given λLA term in a polynomial number of reduction steps, and indeed in polynomial time. Since proofs of ILAL are structurally representable by terms of λLA, we conclude that the same holds for ILAL. This is a full version of the paper [21] presented at LICS 2001.     

A Differentiation Theory for Itô's Calculus

Abstract

A peculiar feature of Itô's calculus is that it is an integral calculus that gives no explicit derivative with a systematic differentiation theory counterpart, as in elementary calculus. So, can we define a pathwise stochastic derivative of semimartingales with respect to Brownian motion that leads to a differentiation theory counterpart to Itô's integral calculus? From Itô's definition of his integral, such a derivative must be based on the quadratic variation process. We give such a derivative in this note and we show that it leads to a fundamental theorem of stochastic calculus, a generalized stochastic chain rule that includes the case of convex functions acting on continuous semimartingales, and the stochastic mean value and Rolle's theorems. In addition, it interacts with basic algebraic operations on semimartingales similarly to the way the deterministic derivative does on deterministic functions, making it natural for computations. Such a differentiation theory leads to many interesting applications, some of which we address in an upcoming article.     

Cut-Elimination Theorem for the Logic of Constant Domains

The logic CD is an intermediate logic (stronger than intuitionistic logic and weaker than classical logic) which exactly corresponds to the Kripke models with constant domains. It is known that the logic CD has a Gentzen-type formulation called LD (which is same as LK except that (→) and (?–) rules are replaced by the corresponding intuitionistic rules) and that the cut-elimination theorem does not hold for LD . In this paper we present a modification of LD and prove the cut-elimination theorem for it. Moreover we prove a “weak” version of cut-elimination theorem for LD , saying that all “cuts” except some special forms can be eliminated from a proof in LD . From these cut-elimination theorems we obtain some corollaries on syntactical properties of CD : fragments collapsing into intuitionistic logic. Harrop disjunction and existence properties, and a fact on the number of logical symbols in the axiom of CD . Mathematics Subject Classification : 03B55. 03F05.     

Sequent calculi for propositional star-free likelihood logic

We consider classical, multisuccedent intuitionistic, and intuitionistic sequent calculi for propositional likelihood logic. We prove the admissibility of structural rules and cut rule, invertibility of rules, correctness of the calculi, and completeness of the classical calculus with respect to given semantics.__________Published in Lietuvos Matematikos Rinkinys, Vol. 45, No. 1, pp. 3–21, January–March, 2005.     

A normalizing system of natural deduction for intuitionistic linear logic

 The main result of this paper is a normalizing system of natural deduction for the full language of intuitionistic linear logic. No explicit weakening or contraction rules for -formulas are needed. By the systematic use of general elimination rules a correspondence between normal derivations and cut-free derivations in sequent calculus is obtained. Normalization and the subformula property for normal derivations follow through translation to sequent calculus and cut-elimination. Received: 10 October 2000 / Revised version: 26 July 2001 / Published online: 2 September 2002 Mathematics Subject Classification (2000): 03F52, 03F05 Keywords or phrases: Linear logic – Natural deduction – General elimination rules