A semantical proof of De Jongh's theorem

Summary In 1969, De Jongh proved the maximality of a fragment of intuitionistic predicate calculus forHA. Leivant strengthened the theorem in 1975, using proof-theoretical tools (normalisation of infinitary sequent calculi). By a refinement of De Jongh's original method (using Beth models instead of Kripke models and sheafs of partial combinatory algebras), a semantical proof is given of a result that is almost as good as Leivant's. Furthermore, it is shown thatHA can be extended to Higher Order Heyting Arithmetic+all true ₂ ⁰ -sentences + transfinite induction over primitive recursive well-orderings. As a corollary of the proof, maximality of intuitionistic predicate calculus is established wrt. an abstract realisability notion defined over a suitable expansion ofHA.     

Decidability of Some Classes of Modal Logic

We describe a modal sequential calculus some modal rules of which do not contain duplications of the main formula. We also prove its equivalence to the modal calculus S4 and the decidability of some classes of formulas containing only oneplace predicate variables.     

Glivenko Classes of Sequents for Temporal Logic with Time Gaps

Let LB be a sequent calculus of the first-order classical temporal logic TB with time gaps. Let, further, LBJ be the intuitionistic counterpart of LB. In this paper, we consider conditions under which a sequent is derivable in the calculus LBJ if and only if it is derivable in the calculus LB. Such conditions are defined for sequents with one formula in the succedent (purely Glivenko -classes) and for sequents with the empty succedent (Glivenko -classes).     

Embedding classical in minimal implicational logic

Consider the problem which set V of propositional variables suffices for whenever , where , and ?_c and ?_i denote derivability in classical and intuitionistic implicational logic, respectively. We give a direct proof that stability for the final propositional variable of the (implicational) formula A is sufficient; as a corollary one obtains Glivenko's theorem. Conversely, using Glivenko's theorem one can give an alternative proof of our result. As an alternative to stability we then consider the Peirce formula . It is an easy consequence of the result above that adding a single instance of the Peirce formula suffices to move from classical to intuitionistic derivability. Finally we consider the question whether one could do the same for minimal logic. Given a classical derivation of a propositional formula not involving ⊥, which instances of the Peirce formula suffice as additional premises to ensure derivability in minimal logic? We define a set of such Peirce formulas, and show that in general an unbounded number of them is necessary.     

On a problem of Erdös and Alladi

We give an estimate for the quantity {f(n):nx, p(n)y}, wherep(n) denotes the greatest prime factor ofn andf belongs to a certain class of multiplicative functions. As an application, we show that for the Moebius function, ({(n):nx, p(n)y}) ({1:nx, p(n)y})^–1 tends to zero, asx, uniformly iny2, and thus settle a conjecture of Erdös.Supported by a grant from the Deutsche Forschungsgesellschaft.     

Atomic polymorphism and the existence property

We present a purely proof-theoretic proof of the existence property for the full intuitionistic first-order predicate calculus, via natural deduction, in which commuting conversions are not needed. Such proof illustrates the potential of an atomic polymorphic system with only three generators of formulas – conditional and first and second-order universal quantifiers – as a tool for proof-theoretical studies.     

Fuzzy constructive logic

We introduce a logical system in which the principles of fuzzy logic are interpreted from the point of view of the constructive approach The language of predicate formulas without functional symbols and symbols of constants is considered. The notion of identically trae predicate formula in the framework of the introduced logic is defined; two variants of this definition are given. Theorems concerning identically true predicate formulas are proved. Some connections between the introduced logic and the constructive (intuitionistic) predicate calculus are established. Bibliography: 40 titles. Translated from Zapiski Nauchnykh Seminarov POMI, Vol. 358, 2008, pp. 130–152.     

Preservation of equivalence of derivations under reduction of depth of formulas

In this paper we consider derivations in the (&, )-fragment of the intuitionistic propositional calculus. As is known, replacement of any occurrence of a formula [F] in a sequent S by an occurrence of the formula [p], where p is a new propositional variable, with the simultaneous addition to the antecedent of the formula F p or p F depending on the sign of the occurrence of F in S, leaves the derivability unchanged. We give a proof of the fact that the natural extension of this transformation to derivations preserves the relation of equivalence of derivations, i.e., transformed derivations are equivalent if and only if the originals are equivalent. (Derivations are considered equivalent if certain of their normal forms coincide, or, what is the same, if their deductive terms coincide.) It is proved that by the iteration of this transformation, each derivation of an arbitrary sequent S can be transformed into a derivation of a sequent S, depending only on S, whose succedent is a variable, and in the antecedent there occur only formulas of the form a,a & b, a b,,(a b) c, a & b c, a (b & c), wherea, b, c are variables. Here if S is balanced, then S is also balanced. (A sequent is called balanced if each variable occurs in it no more than twice.) The familiar correspondence between certain concepts of the theory of categories and concepts of the theory of proofs allows one to assert that there has been constructed a univalent functor, mapping a free Cartesian closed category into itself.Translated from Zapiski Nauchnykh Seminarov Leningradskogo Otdeleniya Matematicheskogo Instituta im. V. A. Steklova AN SSSR, Vol. 88, pp. 197–207, 1979.     

Primitive recursive estimate of strong normalization for predicate calculus

The strong normalization theorem asserts that any sequence of reductions (standard steps of cut elimination) stops at an object in normal form, i.e., at an object to which further reductions are inapplicable. The most intuitive proofs of strong normalization for various systems, including first- and second-order arithmetic, use, essentially, the concept of hereditary normalizability of an object. This concept, for objects of unbounded complexity, cannot be expressed in the language of arithmetic, so that the proofs mentioned leave its domain. Howard's proof for arithmetic, using nonunique assignment of ordinals, apparently, can be modified so as to get a primitive recursive proof of strict normalizability for the -fragment of the intuitionistic predicate calculus, but the author of the present paper has not succeeded in overcoming the combinatorial difficulties. Our goal is to give an intuitive proof for the predicate calculus, from which one can extract a primitive recursive estimate of the number of reductions, and a proof in primitive recursive arithmetic of the fact that this estimate is proper. The proof of normalizability, that is, the construction of a special reduction sequence stopping at a normal term, is well known. In this sequence one first converts subterms of the highest levell, and first the innermost of them. (Corresponding to this, in the proof one can apply reduction with respect to level.) Here the number of convertible terms of maximal level, suitable for reduction, is lowered and the newly arising convertible terms have lower level.Translated from Zapiski Nauchnykh Seminarov Leningradskogo Otdeleniya Matematicheskogo Instituta im. V. A. Steklova AN SSSR, Vol. 88, pp. 131–135, 1979.     

An intuitionistic formula hierarchy based on high‐school identities

We revisit the notion of intuitionistic equivalence and formal proof representations by adopting the view of formulas as exponential polynomials. After observing that most of the invertible proof rules of intuitionistic (minimal) propositional sequent calculi are formula (i.e., sequent) isomorphisms corresponding to the high‐school identities, we show that one can obtain a more compact variant of a proof system, consisting of non‐invertible proof rules only, and where the invertible proof rules have been replaced by a formula normalization procedure. Moreover, for certain proof systems such as the G4ip sequent calculus of Vorob'ev, Hudelmaier, and Dyckhoff, it is even possible to see all of the non‐invertible proof rules as strict inequalities between exponential polynomials; a careful combinatorial treatment is given in order to establish this fact. Finally, we extend the exponential polynomial analogy to the first‐order quantifiers, showing that it gives rise to an intuitionistic hierarchy of formulas, resembling the classical arithmetical hierarchy, and the first one that classifies formulas while preserving isomorphism.     

Queues with Equally Heavy Sojourn Time and Service Requirement Distributions

For the G/G/1 queue with First-Come First-Served, it is well known that the tail of the sojourn time distribution is heavier than the tail of the service requirement distribution when the latter has a regularly varying tail. In contrast, for the M/G/1 queue with Processor Sharing, Zwart and Boxma [26] showed that under the same assumptions on the service requirement distribution, the two tails are equally heavy. By means of a probabilistic analysis we provide a new insightful proof of this result, allowing for the slightly weaker assumption of service requirement distributions with a tail of intermediate regular variation. The new approach allows us to also establish the tail equivalence for two other service disciplines: Foreground–Background Processor Sharing and Shortest Remaining Processing Time. The method can also be applied to more complicated models, for which no explicit formulas exist for (transforms of) the sojourn time distribution. One such model is the M/G/1 Processor Sharing queue with service that is subject to random interruptions. The latter model is of particular interest for the performance analysis of communication networks.     

The Gödel-McKinsey-Tarski embedding for infinitary intuitionistic logic and its extensions

The Gödel-McKinsey-Tarski embedding allows to view intuitionistic logic through the lenses of modal logic. In this work, an extension of the modal embedding to infinitary intuitionistic logic is introduced. First, a neighborhood semantics for a family of axiomatically presented infinitary modal logics is given and soundness and completeness are proved via the method of canonical models. The semantics is then exploited to obtain a labelled sequent calculus with good structural properties. Next, soundness and faithfulness of the embedding are established by transfinite induction on the height of derivations: the proof is obtained directly without resorting to non-constructive principles. Finally, the modal embedding is employed in order to relate classical, intuitionistic and modal derivability in infinitary logic extended with axioms.     

A short proof of Glivenko theorems for intermediate predicate logics

We give a simple proof-theoretic argument showing that Glivenko’s theorem for propositional logic and its version for predicate logic follow as an easy consequence of the deduction theorem, which also proves some Glivenko type theorems relating intermediate predicate logics between intuitionistic and classical logic. We consider two schemata, the double negation shift (DNS) and the one consisting of instances of the principle of excluded middle for sentences (REM). We prove that both schemata combined derive classical logic, while each one of them provides a strictly weaker intermediate logic, and neither of them is derivable from the other. We show that over every intermediate logic there exists a maximal intermediate logic for which Glivenko’s theorem holds. We deduce as well a characterization of DNS, as the weakest (with respect to derivability) scheme that added to REM derives classical logic.     

Ein Syntaktischer Beweis für die Zulässigkeit der Schnittregel im Kalkül von Schütte für die Intuitionistische Typenlogik

In [1] Girard gives a procedure, by which all derivations in the calculus of natural deductions of Prawitz [4] are transformed into normal derivations. Exploiting his idea we give a syntactical proof of the admissibility of the cut rule in Schütte's formal system of intuitionistic type theory. We obtain a normal form theorem but not a normalization theorem. Our Berechnungsprädikate are different from the candidats de reductibilite of Girard. In the case of second order logic Berechnungsprädikate für Terme t^(O) are not defined for derivations ending with r^O e t^(O) which are normalizable, but for finite formula sets with the property, that r^O e t^(O) is derivable without cut.     

二重积分变量代换公式证明的探讨

在一般教材中二重积分变量代换公式的证明通常采用几何的方法,也有部分数学分析教材给与了严格的分析证明,但证明不便直观的几何说明.本文对二重积分变量代换公式进行了一些探讨,给出了一个较简洁直观的分析证明方法.     

The Skolemization of prenex formulas in intermediate logics

The skolem class of a logic consists of the formulas for which the derivability of the formula is equivalent to the derivability of its Skolemization. In contrast to classical logic, the skolem classes of many intermediate logics do not contain all formulas. In this paper it is proven for certain classes of propositional formulas that any instance of them by (independent) predicate sentences in prenex normal form belongs to the skolem class of any intermediate logic complete with respect to a class of well-founded trees. In particular, all prenex sentences belong to the skolem class of these logics, and this result extends to the constant domain versions of these logics.     

Some Cubic Summation and Transformation Formulas

q-Analogues of two cubic summation formulas that have recently caught the attention of Bill Gosper are found by first showing their connection with the q-binomial formula and then using some known transformation formulas. We also find a q-extension of a cubic transformation formula involving Gauss' hypergeometric function, which turns out to be a relation between balanced and very-well-poised 109 series.     

Method of Propagating Waves for a One-Dimensional Inhomogeneous Medium

The aim of this work is to develop a method of propagating waves based on the idea of a wave as a changing state of a medium. This method allows us to represent a solution of the one-dimensional wave equation in an inhomogeneous medium as the sum of two constantly deformed waves, the right wave and the left wave, transported from point to point with coefficients depending on the points and the transport time. By the propagating-wave method we obtain explicit (as far as possible) formulas for solutions of the mixed problem with homogeneous and inhomogeneous boundary conditions and solutions of the Goursat problem. The derivation of these formulas is based on special convolution formulas for the transport coefficients that are similar to the addition identities for trigonometric functions.__________Translated from Trudy Seminara imeni I. G. Petrovskogo, No. 24, pp. 3–43, 2004.