Natural deduction with general elimination rules

The structure of derivations in natural deduction is analyzed through isomorphism with a suitable sequent calculus, with twelve hidden convertibilities revealed in usual natural deduction. A general formulation of conjunction and implication elimination rules is given, analogous to disjunction elimination. Normalization through permutative conversions now applies in all cases. Derivations in normal form have all major premisses of elimination rules as assumptions. Conversion in any order terminates. Through the condition that in a cut-free derivation of the sequent Γ⇒C, no inactive weakening or contraction formulas remain in Γ, a correspondence with the formal derivability relation of natural deduction is obtained: All formulas of Γ become open assumptions in natural deduction, through an inductively defined translation. Weakenings are interpreted as vacuous discharges, and contractions as multiple discharges. In the other direction, non-normal derivations translate into derivations with cuts having the cut formula principal either in both premisses or in the right premiss only. Received: 1 December 1998 / Revised version: 30 June 2000 / Published online: 18 July 2001     

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.     

Gentzen’s consistency proof without heightlines

This paper gives a Gentzen-style proof of the consistency of Heyting arithmetic in an intuitionistic sequent calculus with explicit rules of weakening, contraction and cut. The reductions of the proof, which transform derivations of a contradiction into less complex derivations, are based on a method for direct cut-elimination without the use of multicut. This method treats contractions by tracing up from contracted cut formulas to the places in the derivation where each occurrence was first introduced. Thereby, Gentzen’s heightline argument, which introduces additional cuts on contracted compound cut formulas, is avoided. To show termination of the reduction procedure an ordinal assignment based on techniques of Howard for Gödel’s T is used.     

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     

A new reduction sequence for arithmetic

The main type of result in proof theory having external applications is normalization theorems: any derivation can be reduced to normal form with the help of a finite number of standard transformations (reductions). An estimate for the convergence of the process of normalization gives an estimate for the growth of provable recursive functions, which recently found application to finitary combinatorics [J. Paris and L. Harrington, A mathematical incompleteness in Peano arithmetic, in: Handbook of Mathematical Logic (1978), pp. 1133–1142]. The definition of reduction for the predicate calculus and arithmetic is due to Gentzen, who proved a normalization theorem for derivations of atomic formulas and gave an estimate for convergence with the help of an assignment to derivations d of ordinals O(d)<₀ such that O(d)>O(d) for reductions ¯d of the derivation d. Later convergence was proved for arbitrary derivations; however, the slight clarity in the choice of ¯d and the proof of decrease of ordinals impede understanding and exposition: both Takeuti (G. Takeuti, Proof Theory, North-Holland, 1975) and Schütte (Ref. Zh. Mat., 1978, 7A48K) restrict themselves to derivations of atomic formulas. In the presentpaper there is given a shorter and clearer construction of reduction ¯d and assignment of ordinals, allowing one also to simplify the proof of decrease of ordinals. The source of all the simplifications is the connection with the continuous operator of cut elimination from infinite derivations proposed by the author. In particular, the symbol O_k(d), in terms of which O(d) is defined, can be read as ordinal height of the derivation, obtained after elimination of cuts of degree k from an infinite derivation in which d is represented in a standard way. We consider the L-formulation, where there are rules of introduction of connectives in the antecedent and succedent. Extension to the natural formulation is obtained with the help of Prawitz translation.Translated from Zapiski Nauchnykh Seminarov Leningradskogo Otdeleniya Matematicheskogo Instituta im. V. A. Steklova AN SSSR, Vol. 88, pp. 106–126, 1979.     

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.     

Classical linear logics with mix separation principle

Variants of classical linear logics are presented based on the modal version of new structural rule !?mingle instead of the known rules !weakening and ?weakening. The cut‐elimination theorems, the completeness theorems (with respect to Girard's phase models) and a characteristic property named the mix separation principle are proved for these logics.     

Normal derivability in modal logic

The standard rule of necessitation in systems of natural deduction for the modal logic S4 concludes □A from A whenever all assumptions A depends on are modal formulas. This condition prevents the composability and normalization of derivations, and therefore modifications of the rule have been suggested. It is shown that both properties hold if, instead of changing the rule of necessitation, all elimination rules are formulated in the manner of disjunction elimination, i.e. with an arbitrary consequence. (© 2005 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)     

A note on the MIR closure and basic relaxations of polyhedra

Anderson et al. (2005) [1] show that for a polyhedral mixed integer set defined by a constraint system Ax≥b, along with integrality restrictions on some of the variables, any split cut is in fact a split cut for a basic relaxation, i.e., one defined by a subset of linearly independent constraints. This result implies that any split cut can be obtained as an intersection cut. Equivalence between split cuts obtained from simple disjunctions of the form x_j≤0 or x_j≥1 and intersection cuts was shown earlier for 0/1-mixed integer sets by Balas and Perregaard (2002) [4]. We give a short proof of the result of Anderson, Cornuéjols and Li using the equivalence between mixed integer rounding (MIR) cuts and split cuts.     

Facet inequalities from simple disjunctions in cutting plane theory

The duality between facets of the convex hull of disjunctive sets and the extreme points of reverse polars of these sets is utilized to establish simple rules for the derivation of all facet cuts for simple disjunctions, namely, elementary disjunctions in nonnegative variables. These rules generalize the cut generation procedure underlying polyhedral convexity cuts with negative edge extensions. The latter are also shown to possess some interesting properties with respect to a biextremal problem that maximizes the distance, from the origin, of the nearest point feasible to the cut. A computationally inexpensive procedure is given to generate facet cuts for simple disjunctions which are dominant with respect to any specified preemptive ordering of variables.     

Sequent systems for compact bilinear logic

Compact Bilinear Logic (CBL), introduced by Lambek [14], arises from the multiplicative fragment of Noncommutative Linear Logic of Abrusci [1] (also called Bilinear Logic in [13]) by identifying times with par and 0 with 1. In this paper, we present two sequent systems for CBL and prove the cut‐elimination theorem for them. We also discuss a connection between cut‐elimination for CBL and the Switching Lemma from [14].     

An analytic center quadratic cut method for the convex quadratic feasibility problem

 We consider a quadratic cut method based on analytic centers for two cases of convex quadratic feasibility problems. In the first case, the convex set is defined by a finite yet large number, N, of convex quadratic inequalities. We extend quadratic cut algorithm of Luo and Sun [3] for solving such problems by placing or translating the quadratic cuts directly through the current approximate center. We show that, in terms of total number of addition and translation of cuts, our algorithm has the same polynomial worst case complexity as theirs [3]. However, the total number of steps, where steps consist of (damped) Newton steps, function evaluations and arithmetic operations, required to update from one approximate center to another is , where ε is the radius of the largest ball contained in the feasible set. In the second case, the convex set is defined by an infinite number of certain strongly convex quadratic inequalities. We adapt the same quadratic cut method for the first case to the second one. We show that in this case the quadratic cut algorithm is a fully polynomial approximation scheme. Furthermore, we show that, at each iteration, k, the total number steps (as described above) required to update from one approximate center to another is at most , with ε as defined above. Received: April 2000 / Accepted: June 2002 Published online: September 5, 2002 Key words. convex quadratic feasibility problem – interior-point methods – analytic center – quadratic cuts – potential function     

Combinatorial analysis of proofs in projective and affine geometry

The axioms of projective and affine plane geometry are turned into rules of proof by which formal derivations are constructed. The rules act only on atomic formulas. It is shown that proof search for the derivability of atomic cases from atomic assumptions by these rules terminates (i.e., solves the word problem). This decision method is based on the central result of the combinatorial analysis of derivations by the geometric rules: The geometric objects that occur in derivations by the rules can be restricted to those known from the assumptions and cases. This “subterm property” is proved by permuting suitably the order of application of the geometric rules. As an example of the decision method, it is shown that there cannot exist a derivation of Euclid’s fifth postulate if the rule that corresponds to the uniqueness of the parallel line construction is taken away from the system of plane affine geometry.     

Herbrand's theorem revisited

We present recent results on the deepening connection between proof theory and formal language theory. To each first-order proof with prenex cuts of complexity at most Π_n/Σ_n, we associate a typed (non-deterministic) tree grammar of order n (equivalently, an order n recursion scheme) that abstracts the computation of Herbrand sets obtained through Gentzen-style cut elimination. Apart from offering a means to compute Herbrand expansions directly from proofs with cuts, these grammars provide a structural counterpart to Herbrand's theorem that opens the door to tackling a number of questions in proof theory such as proof equivalence, proof compression and proof complexity. (© 2016 Wiley-VCH Verlag GmbH & Co. KGaA, Weinheim)     

Combinatorial analysis of proofs in projective and affine geometry

The axioms of projective and affine plane geometry are turned into rules of proof by which formal derivations are constructed. The rules act only on atomic formulas. It is shown that proof search for the derivability of atomic cases from atomic assumptions by these rules terminates (i.e., solves the word problem). This decision method is based on the central result of the combinatorial analysis of derivations by the geometric rules: The geometric objects that occur in derivations by the rules can be restricted to those known from the assumptions and cases. This “subterm property” is proved by permuting suitably the order of application of the geometric rules. As an example of the decision method, it is shown that there cannot exist a derivation of Euclid’s fifth postulate if the rule that corresponds to the uniqueness of the parallel line construction is taken away from the system of plane affine geometry.     

A Relationship Among Gentzen's Proof-Reduction,Kirby-Paris' Hydra Game and Buchholz's Hydra Game

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 (Section 1 and Appendix). 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 (which is two-dimensional but without labels), by a simple and natural interpretation (Section 2). 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 (Section 3) that this Jervell's game is actually much stronger than PA, by showing that the critical ordinal of Jervell's game is φ_ω (0) (while that of PA or of Kirby-Paris' Game is φ₁ (0) = ?₀) in the Veblen hierarchy of ordinals.     

Local time and Tanaka formula for a multitype Dawson–Watanabe superprocess

In [3] Dynkin defined the local time of a continuous superprocess as a stochastic integral and gave a criterion for existence of local time. Here we prove that the conditions in Dynkin's existence criterion are satisfied by the multitype Dawson–Watanabe superprocess, and give a Tanaka formula‐like representation of the local time which is used to show that the occupation measure of the multitype superprocess is absolutely continuous with respect to an appropriate reference measure, and that the corresponding density coincides a.s. with the local time. (© 2006 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)     

Scattering by a highly oscillating surface

The boundary function method [A. B. Vasil'eva, V. F. Butuzov, and L. V. Kalachev, The boundary function method for singular perturbation problems, SIAM Studies in Applied Mathematics, Philadelphia, 1995] is used to build an asymptotic expansion at any order of accuracy of a scalar time‐harmonic wave scattered by a perfectly reflecting doubly periodic surface with oscillations at small and large scales. Error bounds are rigorously established, in particular in an optimal way on the relevant part of the field. It is also shown how the maximum principle can be used to design a homogenized surface whose reflected wave yields a first‐order approximation of the actual one. The theoretical derivations are illustrated by some numerical experiments, which in particular show that using the homogenized surface outperforms the usual approach consisting in setting an effective boundary condition on a flat boundary. Copyright © 2014 John Wiley & Sons, Ltd.     

Generic cuts in models of arithmetic

We present some general results concerning the topological space of cuts of a countable model of arithmetic given by a particular indicator Y. The notion of “indicator” is de.ned in a novel way, without initially specifying what property is indicated and is used to de.ne a topological space of cuts of the model. Various familiar properties of cuts (strength, regularity, saturation, coding properties) are investigated in this sense, and several results are given stating whether or not the set of cuts having the property is comeagre. A new notion of “generic cut” is introduced and investigated and it is shown in the case of countable arithmetically saturated models M ? PA that generic cuts exist, indeed the set of generic cuts is comeagre in the sense of Baire, and furthermore that two generic cuts within the same “small interval” of the model are conjugate by an automorphism of the model.The paper concludes by outlining some applications to constructions of cuts satisfying properties incompatible with genericity, and discussing in model‐theoretic terms those properties for which there is an indicator Y. (© 2008 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)     

3‐Flows and Combs

Tutte's 3‐Flow Conjecture states that every 2‐edge‐connected graph with no 3‐cuts admits a 3‐flow. The 3‐Flow Conjecture is equivalent to the following: let G be a 2‐edge‐connected graph, let S be a set of at most three vertices of G; if every 3‐cut of G separates S then G has a 3‐flow. We show that minimum counterexamples to the latter statement are 3‐connected, cyclically 4‐connected, and cyclically 7‐edge‐connected.