Related categories
Siblings:
883 found
Search inside:
(import / add options)   Order:
1 — 50 / 883
  1. Erik Aarts (1994). Proving Theorems of the Second Order Lambek Calculus in Polynomial Time. Studia Logica 53 (3):373 - 387.
    In the Lambek calculus of order 2 we allow only sequents in which the depth of nesting of implications is limited to 2. We prove that the decision problem of provability in the calculus can be solved in time polynomial in the length of the sequent. A normal form for proofs of second order sequents is defined. It is shown that for every proof there is a normal form proof with the same axioms. With this normal form we can give (...)
    Remove from this list   Direct download (6 more)  
     
    Export citation  
     
    My bibliography   1 citation  
  2. Samson Abramsky & Radha Jagadeesan (1994). Games and Full Completeness for Multiplicative Linear Logic. Journal of Symbolic Logic 59 (2):543-574.
    We present a game semantics for Linear Logic, in which formulas denote games and proofs denote winning strategies. We show that our semantics yields a categorical model of Linear Logic and prove full completeness for Multiplicative Linear Logic with the MIX rule: every winning strategy is the denotation of a unique cut-free proof net. A key role is played by the notion of history-free strategy; strong connections are made between history-free strategies and the Geometry of Interaction. Our semantics incorporates a (...)
    Remove from this list   Direct download (6 more)  
     
    Export citation  
     
    My bibliography   30 citations  
  3. Michele Abrusci & Christian Retoré, Some Proof Theoretical Remarks on Quantification in Ordinary Language.
    This paper surveys the common approach to quantification and generalised quantification in formal linguistics and philosophy of language. We point out how this general setting departs from empirical linguistic data, and give some hints for a different view based on proof theory, which on many aspects gets closer to the language itself. We stress the importance of Hilbert's oper- ator epsilon and tau for, respectively, existential and universal quantifications. Indeed, these operators help a lot to construct semantic representation close to (...)
    Remove from this list   Direct download (2 more)  
     
    Export citation  
     
    My bibliography  
  4. V. M. Abrusci (1991). Sequent Calculus and Phase Semantics for Pure Non-Commutative Classical Propositional Logic. Journal of Symbolic Logic 56:1403-1451.
    Remove from this list  
     
    Export citation  
     
    My bibliography   2 citations  
  5. V. Michele Abrusci (2014). On Hilbert's Axiomatics of Propositional Logic. Perspectives on Science 22 (1):115-132.
    Hilbert's conference lectures during the year 1922, Neuebegründung der Mathematik. Erste Mitteilung and Die logischen Grundlagen der Mathematik (both are published in (Hilbert [1935] 1965) pp. 157-195), contain his first public presentation of an axiom system for propositional logic, or at least for a fragment of propositional logic, which is largely influenced by the study on logical woks of Frege and Russell during the previous years.The year 1922 is at the beginning of Hilbert's foundational program in its definitive form. The (...)
    Remove from this list   Direct download (3 more)  
     
    Export citation  
     
    My bibliography  
  6. V. Michele Abrusci (1991). Phase Semantics and Sequent Calculus for Pure Noncommutative Classical Linear Propositional Logic. Journal of Symbolic Logic 56 (4):1403-1451.
    Remove from this list   Direct download (6 more)  
     
    Export citation  
     
    My bibliography   6 citations  
  7. V. Michele Abrusci & Paul Ruet (1999). Non-Commutative Logic I: The Multiplicative Fragment. Annals of Pure and Applied Logic 101 (1):29-64.
    We introduce proof nets and sequent calculus for the multiplicative fragment of non-commutative logic, which is an extension of both linear logic and cyclic linear logic. The two main technical novelties are a third switching position for the non-commutative disjunction, and the structure of order variety.
    Remove from this list   Direct download (4 more)  
     
    Export citation  
     
    My bibliography   5 citations  
  8. Peter Aczel, Harold Simmons & S. S. Wainer (eds.) (1992). Proof Theory: A Selection of Papers From the Leeds Proof Theory Programme, 1990. Cambridge University Press.
    This work is derived from the SERC "Logic for IT" Summer School Conference on Proof Theory held at Leeds University. The contributions come from acknowledged experts and comprise expository and research articles which form an invaluable introduction to proof theory aimed at both mathematicians and computer scientists.
    Remove from this list   Direct download  
     
    Export citation  
     
    My bibliography  
  9. Romà J. Adillon & Ventura Verdú (2000). On a Contraction-Less Intuitionistic Propositional Logic with Conjunction and Fusion. Studia Logica 65 (1):11-30.
    In this paper we prove the equivalence between the Gentzen system G LJ*\c , obtained by deleting the contraction rule from the sequent calculus LJ* (which is a redundant version of LJ), the deductive system IPC*\c and the equational system associated with the variety RL of residuated lattices. This means that the variety RL is the equivalent algebraic semantics for both systems G LJ*\c in the sense of [18] and [4], respectively. The equivalence between G LJ*\c and IPC*\c is a (...)
    Remove from this list   Direct download (7 more)  
     
    Export citation  
     
    My bibliography  
  10. Henry Africk (1992). Classical Logic, Intuitionistic Logic, and the Peirce Rule. Notre Dame Journal of Formal Logic 33 (2):229-235.
    A simple method is provided for translating proofs in Grentzen's LK into proofs in Gentzen's LJ with the Peirce rule adjoined. A consequence is a simpler cut elimination operator for LJ + Peirce that is primitive recursive.
    Remove from this list   Direct download (5 more)  
     
    Export citation  
     
    My bibliography  
  11. Henry Africk (1972). A Proof Theoretic Proof of Scott's General Interpolation Theorem. Journal of Symbolic Logic 37 (4):683-695.
    Remove from this list   Direct download (5 more)  
     
    Export citation  
     
    My bibliography  
  12. Bahareh Afshari & Michael Rathjen (2010). A Note on the Theory of Positive Induction, {{Rm ID}^*_1}. Archive for Mathematical Logic 49 (2):275-281.
    The article shows a simple way of calibrating the strength of the theory of positive induction, ${{\rm ID}^{*}_{1}}$ . Crucially the proof exploits the equivalence of ${\Sigma^{1}_{1}}$ dependent choice and ω-model reflection for ${\Pi^{1}_{2}}$ formulae over ACA 0. Unbeknown to the authors, D. Probst had already determined the proof-theoretic strength of ${{\rm ID}^{*}_{1}}$ in Probst, J Symb Log, 71, 721–746, 2006.
    Remove from this list   Direct download (3 more)  
     
    Export citation  
     
    My bibliography   1 citation  
  13. Bahareh Afshari & Michael Rathjen (2009). Reverse Mathematics and Well-Ordering Principles: A Pilot Study. Annals of Pure and Applied Logic 160 (3):231-237.
    The larger project broached here is to look at the generally sentence “if X is well-ordered then f is well-ordered”, where f is a standard proof-theoretic function from ordinals to ordinals. It has turned out that a statement of this form is often equivalent to the existence of countable coded ω-models for a particular theory Tf whose consistency can be proved by means of a cut elimination theorem in infinitary logic which crucially involves the function f. To illustrate this theme, (...)
    Remove from this list   Direct download (3 more)  
     
    Export citation  
     
    My bibliography  
  14. Mojtaba Aghaei & Mohammad Ardeshir (2003). A Gentzen-Style Axiomatization for Basic Predicate Calculus. Archive for Mathematical Logic 42 (3):245-259.
    We introduce a Gentzen-style sequent calculus axiomatization for Basic Predicate Calculus. Our new axiomatization is an improvement of the previous axiomatizations, in the sense that it has the subformula property. In this system the cut rule is eliminated.
    Remove from this list   Direct download (3 more)  
     
    Export citation  
     
    My bibliography  
  15. Mojtaba Aghaei & Mohammad Ardeshir (2001). Gentzen-Style Axiomatizations for Some Conservative Extensions of Basic Propositional Logic. Studia Logica 68 (2):263-285.
    We introduce two Gentzen-style sequent calculus axiomatizations for conservative extensions of basic propositional logic. Our first axiomatization is an ipmrovement of, in the sense that it has a kind of the subformula property and is a slight modification of. In this system the cut rule is eliminated. The second axiomatization is a classical conservative extension of basic propositional logic. Using these axiomatizations, we prove interpolation theorems for basic propositional logic.
    Remove from this list   Direct download (7 more)  
     
    Export citation  
     
    My bibliography   1 citation  
  16. Stefano Aguzzoli & Agata Ciabattoni (2000). Finiteness in Infinite-Valued Łukasiewicz Logic. Journal of Logic, Language and Information 9 (1):5-29.
    In this paper we deepen Mundici's analysis on reducibility of the decision problem from infinite-valued ukasiewicz logic to a suitable m-valued ukasiewicz logic m , where m only depends on the length of the formulas to be proved. Using geometrical arguments we find a better upper bound for the least integer m such that a formula is valid in if and only if it is also valid in m. We also reduce the notion of logical consequence in to the same (...)
    Remove from this list   Direct download (6 more)  
     
    Export citation  
     
    My bibliography   2 citations  
  17. Stefano Aguzzoli & Brunella Gerla (2002). Finite-Valued Reductions of Infinite-Valued Logics. Archive for Mathematical Logic 41 (4):361-399.
    In this paper we present a method to reduce the decision problem of several infinite-valued propositional logics to their finite-valued counterparts. We apply our method to Łukasiewicz, Gödel and Product logics and to some of their combinations. As a byproduct we define sequent calculi for all these infinite-valued logics and we give an alternative proof that their tautology problems are in co-NP.
    Remove from this list   Direct download (3 more)  
     
    Export citation  
     
    My bibliography   1 citation  
  18. Marc Aiguier & Delphine Longuet (2010). Some General Results About Proof Normalization. Logica Universalis 4 (1):1-29.
    In this paper, we provide a general setting under which results of normalization of proof trees such as, for instance, the logicality result in equational reasoning and the cut-elimination property in sequent or natural deduction calculi, can be unified and generalized. This is achieved by giving simple conditions which are sufficient to ensure that such normalization results hold, and which can be automatically checked since they are syntactical. These conditions are based on basic properties of elementary combinations of inference rules (...)
    Remove from this list   Direct download (5 more)  
     
    Export citation  
     
    My bibliography  
  19. Seiki Akama (1990). Subformula Semantics for Strong Negation Systems. Journal of Philosophical Logic 19 (2):217 - 226.
    We present a semantics for strong negation systems on the basis of the subformula property of the sequent calculus. The new models, called subformula models, are constructed as a special class of canonical Kripke models for providing the way from the cut-elimination theorem to model-theoretic results. This semantics is more intuitive than the standard Kripke semantics for strong negation systems.
    Remove from this list   Direct download (5 more)  
     
    Export citation  
     
    My bibliography   1 citation  
  20. Luca Alberucci & Gerhard Jäger (2005). About Cut Elimination for Logics of Common Knowledge. Annals of Pure and Applied Logic 133 (1):73-99.
    The notions of common knowledge or common belief play an important role in several areas of computer science , in philosophy, game theory, artificial intelligence, psychology and many other fields which deal with the interaction within a group of “agents”, agreement or coordinated actions. In the following we will present several deductive systems for common knowledge above epistemic logics –such as K, T, S4 and S5 –with a fixed number of agents. We focus on structural and proof-theoretic properties of these (...)
    Remove from this list   Direct download (3 more)  
     
    Export citation  
     
    My bibliography   5 citations  
  21. David Albrecht, Frank A. Bäuerle, John N. Crossley & John S. Jeavons (1998). Curry-Howard Terms for Linear Logic. Studia Logica 61 (2):223-235.
    In this paper we 1. provide a natural deduction system for full first-order linear logic, 2. introduce Curry- Howard -style terms for this version of linear logic, 3. extend the notion of substitution of Curry- Howard terms for term variables, 4. define the reduction rules for the Curry- Howard terms and 5. outline a proof of the strong normalization for the full system of linear logic using a development of Girard's candidates for reducibility, thereby providing an alternative (...)
    Remove from this list   Direct download (3 more)  
     
    Export citation  
     
    My bibliography  
  22. Natasha Alechina (2000). Functional Dependencies Between Variables. Studia Logica 66 (2):273-283.
    We consider a predicate logic Lfd where not all assignments of values to individual variables are possible. Some variables are functionally dependent on other variables. This makes sense if the models of logic are assumed to correspond to databases or states. We show that Lfd is undecidable but has a complete and sound sequent calculus formalisation.
    Remove from this list   Direct download (7 more)  
     
    Export citation  
     
    My bibliography  
  23. Natasha Alechina & Michiel van Lambalgen (1996). Generalized Quantification as Substructural Logic. Journal of Symbolic Logic 61 (3):1006-1044.
    We show how sequent calculi for some generalized quantifiers can be obtained by generalizing the Herbrand approach to ordinary first order proof theory. Typical of the Herbrand approach, as compared to plain sequent calculus, is increased control over relations of dependence between variables. In the case of generalized quantifiers, explicit attention to relations of dependence becomes indispensible for setting up proof systems. It is shown that this can be done by turning variables into structured objects, governed by various types of (...)
    Remove from this list   Direct download (7 more)  
     
    Export citation  
     
    My bibliography   1 citation  
  24. Michael Alekhnovich, Sam Buss, Shlomo Moran & Toniann Pitassi (2001). Minimum Propositional Proof Length is NP-Hard to Linearly Approximate. Journal of Symbolic Logic 66 (1):171-191.
    We prove that the problem of determining the minimum propositional proof length is NP- hard to approximate within a factor of 2 log 1 - o(1) n . These results are very robust in that they hold for almost all natural proof systems, including: Frege systems, extended Frege systems, resolution, Horn resolution, the polynomial calculus, the sequent calculus, the cut-free sequent calculus, as well as the polynomial calculus. Our hardness of approximation results usually apply to proof length measured either by (...)
    Remove from this list   Direct download (6 more)  
     
    Export citation  
     
    My bibliography   1 citation  
  25. R. Alonderis (2013). A Proof-Search Procedure for Intuitionistic Propositional Logic. Archive for Mathematical Logic 52 (7-8):759-778.
    A sequent root-first proof-search procedure for intuitionistic propositional logic is presented. The procedure is obtained from modified intuitionistic multi-succedent and classical sequent calculi, making use of Glivenko’s Theorem. We prove that a sequent is derivable in a standard intuitionistic multi-succedent calculus if and only if the corresponding prefixed-sequent is derivable in the procedure.
    Remove from this list   Direct download (3 more)  
     
    Export citation  
     
    My bibliography  
  26. Romas Alonderis (2007). Glivenko Classes of Sequents for Propositional Star-Free Likelihood Logic. Logic Journal of the IGPL 15 (1):1-19.
    We consider conditions under which sequents are derivable in an intuitionistic sequent calculus of propositional star-free likelihood logic iff they are derivable in a classical counterpart of the calculus. Such conditions are defined for sequents with one formula in the succedent and for sequents with empty succedent.
    Remove from this list   Direct download  
     
    Export citation  
     
    My bibliography  
  27. Martin Amerbauer (1996). Cut-Free Tableau Calculi for Some Propositional Normal Modal Logics. Studia Logica 57 (2-3):359 - 372.
    We give sound and complete tableau and sequent calculi for the prepositional normal modal logics S4.04, K4B and G 0(these logics are the smallest normal modal logics containing K and the schemata A A, A A and A ( A); A A and AA; A A and ((A A) A) A resp.) with the following properties: the calculi for S4.04 and G 0are cut-free and have the interpolation property, the calculus for K4B contains a restricted version of the cut-rule, the (...)
    Remove from this list   Direct download (5 more)  
     
    Export citation  
     
    My bibliography   2 citations  
  28. Jean-Marc Andreoli (2001). Focussing and Proof Construction. Annals of Pure and Applied Logic 107 (1-3):131-163.
    This paper proposes a synthetic presentation of the proof construction paradigm, which underlies most of the research and development in the so-called “logic programming” area. Two essential aspects of this paradigm are discussed here: true non-determinism and partial information. A new formulation of Focussing, the basic property used to deal with non-determinism in proof construction, is presented. This formulation is then used to introduce a general constraint-based technique capable of dealing with partial information in proof construction. One of the baselines (...)
    Remove from this list   Direct download (3 more)  
     
    Export citation  
     
    My bibliography   6 citations  
  29. James H. Andrews (2007). An Untyped Higher Order Logic with Y Combinator. Journal of Symbolic Logic 72 (4):1385 - 1404.
    We define a higher order logic which has only a notion of sort rather than a notion of type, and which permits all terms of the untyped lambda calculus and allows the use of the Y combinator in writing recursive predicates. The consistency of the logic is maintained by a distinction between use and mention, as in Gilmore's logics. We give a consistent model theory, a proof system which is sound with respect to the model theory, and a cut-elimination proof (...)
    Remove from this list   Direct download (2 more)  
     
    Export citation  
     
    My bibliography  
  30. P. B. Andrews (2002). An Introduction to Mathematical Logic and Type Theory: To Truth Through Proof. Kluwer Academic Publishers.
    This introduction to mathematical logic starts with propositional calculus and first-order logic. Topics covered include syntax, semantics, soundness, completeness, independence, normal forms, vertical paths through negation normal formulas, compactness, Smullyan's Unifying Principle, natural deduction, cut-elimination, semantic tableaux, Skolemization, Herbrand's Theorem, unification, duality, interpolation, and definability. The last three chapters of the book provide an introduction to type theory (higher-order logic). It is shown how various mathematical concepts can be formalized in this very expressive formal language. This expressive notation facilitates proofs (...)
    Remove from this list   Direct download (2 more)  
     
    Export citation  
     
    My bibliography   7 citations  
  31. Irving H. Anellis (2012). Jean van Heijenoort's Contributions to Proof Theory and Its History. Logica Universalis 6 (3-4):411-458.
    Jean van Heijenoort was best known for his editorial work in the history of mathematical logic. I survey his contributions to model-theoretic proof theory, and in particular to the falsifiability tree method. This work of van Heijenoort’s is not widely known, and much of it remains unpublished. A complete list of van Heijenoort’s unpublished writings on tableaux methods and related work in proof theory is appended.
    Remove from this list   Direct download (6 more)  
     
    Export citation  
     
    My bibliography  
  32. Toshiyasu Arai (2011). Quick Cut-Elimination for Strictly Positive Cuts. Annals of Pure and Applied Logic 162 (10):807-815.
    In this paper we show that the intuitionistic theory for finitely many iterations of strictly positive operators is a conservative extension of Heyting arithmetic. The proof is inspired by the quick cut-elimination due to G. Mints. This technique is also applied to fragments of Heyting arithmetic.
    Remove from this list   Direct download (4 more)  
     
    Export citation  
     
    My bibliography  
  33. Toshiyasu Arai (2002). Epsilon Substitution Method for Theories of Jump Hierarchies. Archive for Mathematical Logic 41 (2):123-153.
    We formulate epsilon substitution method for theories (H)α0 of absolute jump hierarchies, and give two termination proofs of the H-process: The first proof is an adaption of Mints M, Mints-Tupailo-Buchholz MTB, i.e., based on a cut-elimination of a specially devised infinitary calculus. The second one is an adaption of Ackermann Ack. Each termination proof is based on transfinite induction up to an ordinal θ(α0+ ω)0, which is best possible.
    Remove from this list   Direct download (3 more)  
     
    Export citation  
     
    My bibliography   5 citations  
  34. Toshiyasu Arai (2002). Review: Wilfried Buchholz, Notation Systems for Infinitary Derivations ; Wilfried Buchholz, Explaining Gentzen's Consistency Proof Within Infinitary Proof Theory ; Sergei Tupailo, Finitary Reductions for Local Predicativity, I: Recursively Regular Ordinals. [REVIEW] Bulletin of Symbolic Logic 8 (3):437-439.
    Remove from this list   Direct download (3 more)  
     
    Export citation  
     
    My bibliography  
  35. Toshiyasu Arai (1998). Some Results on Cut-Elimination, Provable Well-Orderings, Induction and Reflection. Annals of Pure and Applied Logic 95 (1-3):93-184.
    We gather the following miscellaneous results in proof theory from the attic.1. 1. A provably well-founded elementary ordering admits an elementary order preserving map.2. 2. A simple proof of an elementary bound for cut elimination in propositional calculus and its applications to separation problem in relativized bounded arithmetic below S21.3. 3. Equivalents for Bar Induction, e.g., reflection schema for ω logic.4. 4. Direct computations in an equational calculus PRE and a decidability problem for provable inequations in PRE.5. 5. Intuitionistic fixed (...)
    Remove from this list   Direct download (3 more)  
     
    Export citation  
     
    My bibliography   1 citation  
  36. Andrew Arana (2010). Proof Theory in Philosophy of Mathematics. Philosophy Compass 5 (4):336-347.
    A variety of projects in proof theory of relevance to the philosophy of mathematics are surveyed, including Gödel's incompleteness theorems, conservation results, independence results, ordinal analysis, predicativity, reverse mathematics, speed-up results, and provability logics.
    Remove from this list   Direct download (6 more)  
     
    Export citation  
     
    My bibliography  
  37. Andrew Arana (2009). On Formally Measuring and Eliminating Extraneous Notions in Proofs. Philosophia Mathematica 17 (2):208–219.
    Many mathematicians and philosophers of mathematics believe some proofs contain elements extraneous to what is being proved. In this paper I discuss extraneousness generally, and then consider a specific proposal for measuring extraneousness syntactically. This specific proposal uses Gentzen’s cut-elimination theorem. I argue that the proposal fails, and that we should be skeptical about the usefulness of syntactic extraneousness measures.
    Remove from this list   Direct download (12 more)  
     
    Export citation  
     
    My bibliography   3 citations  
  38. Mohammad Ardeshir (1999). A Translation of Intuitionistic Predicate Logic Into Basic Predicate Logic. Studia Logica 62 (3):341-352.
    Basic Predicate Logic, BQC, is a proper subsystem of Intuitionistic Predicate Logic, IQC. For every formula in the language {, , , , , , }, we associate two sequences of formulas 0,1,... and 0,1,... in the same language. We prove that for every sequent , there are natural numbers m, n, such that IQC , iff BQC n m. Some applications of this translation are mentioned.
    Remove from this list   Direct download (7 more)  
     
    Export citation  
     
    My bibliography  
  39. Mohammad Ardeshir & Wim Ruitenburg (2001). Basic Propositional Calculus II. Interpolation. Archive for Mathematical Logic 40 (5):349-364.
    Let ℒ and ? be propositional languages over Basic Propositional Calculus, and ℳ = ℒ∩?. Weprove two different but interrelated interpolation theorems. First, suppose that Π is a sequent theory over ℒ, and Σ∪ {C⇒C′} is a set of sequents over ?, such that Π,Σ⊢C⇒C′. Then there is a sequent theory Φ over ℳ such that Π⊢Φ and Φ, Σ⊢C⇒C′. Second, let A be a formula over ℒ, and C 1, C 2 be formulas over ?, such that A∧C 1⊢C (...)
    Remove from this list   Direct download (3 more)  
     
    Export citation  
     
    My bibliography   1 citation  
  40. Ofer Arieli & Christian Straßer (2015). Sequent-Based Logical Argumentation. Argument and Computation 6 (1):73-99.
    We introduce a general approach for representing and reasoning with argumentation-based systems. In our framework arguments are represented by Gentzen-style sequents, attacks between arguments are represented by sequent elimination rules, and deductions are made according to Dung-style skeptical or credulous semantics. This framework accommodates different languages and logics in which arguments may be represented, allows for a flexible and simple way of expressing and identifying arguments, supports a variety of attack relations, and is faithful to standard methods of drawing conclusions (...)
    Remove from this list   Direct download (3 more)  
     
    Export citation  
     
    My bibliography  
  41. Alexandre Arruda & Ana Martins (2009). Natural Deduction for the Finite Least Fixed Point Logic with an Infinitary Rule. Logic Journal of the IGPL 17 (5):531-558.
    The notion of the least fixed point of an operator is widely applied in computer science as, for instance, in the context of query languages for relational databases. Some extensions of first-order classical logic with fixed point operators, as the least fixed point logic , were proposed to deal with problems related to the expressivity of FOL. LFP captures the complexity class PTIME over the class of finite ordered structures. The descriptive characterization of computational classes is a central issue within (...)
    Remove from this list   Direct download  
     
    Export citation  
     
    My bibliography  
  42. S. Artemov, B. Kushner, G. Mints, E. Nogina & A. Troelstra (1999). In Memoriam: Albert G. Dragalin, 1941-1998. Bulletin of Symbolic Logic 5 (3):389-391.
  43. A. Avellone, M. Ferrari & P. Miglioli (1999). Duplication-Free Tableau Calculi and Related Cut-Free Sequent Calculi for the Interpolable Propositional Intermediate Logics. Logic Journal of the IGPL 7 (4):447-480.
    We get cut-free sequent calculi for the interpolable propositional intermediate logics by translating suitable duplication-free tableau calculi developed within a semantical framework. From this point of view, the paper also provides semantical proofs of the admissibility of the cut-rule for appropriate cut-free sequent calculi.
    Remove from this list   Direct download  
     
    Export citation  
     
    My bibliography   1 citation  
  44. Jeremy Avigad, Proof Theory.
    At the turn of the nineteenth century, mathematics exhibited a style of argumentation that was more explicitly computational than is common today. Over the course of the century, the introduction of abstract algebraic methods helped unify developments in analysis, number theory, geometry, and the theory of equations; and work by mathematicians like Dedekind, Cantor, and Hilbert towards the end of the century introduced set-theoretic language and infinitary methods that served to downplay or suppress computational content. This shift in emphasis away (...)
    Remove from this list   Direct download (3 more)  
     
    Export citation  
     
    My bibliography  
  45. Jeremy Avigad, Algebraic Proofs of Cut Elimination.
    Algebraic proofs of the cut-elimination theorems for classical and intuitionistic logic are presented, and are used to show how one can sometimes extract a constructive proof and an algorithm from a proof that is nonconstructive. A variation of the double-negation translation is also discussed: if ϕ is provable classically, then ¬(¬ϕ)nf is provable in minimal logic, where θnf denotes the negation-normal form of θ. The translation is used to show that cut-elimination theorems for classical logic can be viewed as special (...)
    Remove from this list   Direct download (5 more)  
     
    Export citation  
     
    My bibliography   2 citations  
  46. Jeremy Avigad, “Clarifying the Nature of the Infinite”: The Development of Metamathematics and Proof Theory.
    We discuss the development of metamathematics in the Hilbert school, and Hilbert’s proof-theoretic program in particular. We place this program in a broader historical and philosophical context, especially with respect to nineteenth century developments in mathematics and logic. Finally, we show how these considerations help frame our understanding of metamathematics and proof theory today.
    Remove from this list   Direct download (3 more)  
     
    Export citation  
     
    My bibliography  
  47. Jeremy Avigad (2010). Proof Theory. Gödel and the Metamathematical Tradition. In Kurt Gödel, Solomon Feferman, Charles Parsons & Stephen G. Simpson (eds.), Kurt Gödel: Essays for His Centennial. Association for Symbolic Logic
  48. Jeremy Avigad, The Computational Content of Classical Arithmetic to Appear in a Festschrift for Grigori Mints.
    Almost from the inception of Hilbert's program, foundational and structural efforts in proof theory have been directed towards the goal of clarifying the computational content of modern mathematical methods. This essay surveys various methods of extracting computational information from proofs in classical first-order arithmetic, and reflects on some of the relationships between them. Variants of the Godel-Gentzen double-negation translation, some not so well known, serve to provide canonical and efficient computational interpretations of that theory.
    Remove from this list   Direct download (2 more)  
     
    Export citation  
     
    My bibliography  
  49. Jeremy Avigad (2004). Forcing in Proof Theory. Bulletin of Symbolic Logic 10 (3):305-333.
    Paul Cohen’s method of forcing, together with Saul Kripke’s related semantics for modal and intuitionistic logic, has had profound effects on a number of branches of mathematical logic, from set theory and model theory to constructive and categorical logic. Here, I argue that forcing also has a place in traditional Hilbert-style proof theory, where the goal is to formalize portions of ordinary mathematics in restricted axiomatic theories, and study those theories in constructive or syntactic terms. I will discuss the aspects (...)
    Remove from this list   Direct download (13 more)  
     
    Export citation  
     
    My bibliography   4 citations  
  50. Jeremy Avigad (2002). A Realizability Interpretation for Classical Arithmetic. Bulletin of Symbolic Logic 8 (3):439-440.
    Summary. A constructive realizablity interpretation for classical arithmetic is presented, enabling one to extract witnessing terms from proofs of 1 sentences. The interpretation is shown to coincide with modified realizability, under a novel translation of classical logic to intuitionistic logic, followed by the Friedman-Dragalin translation. On the other hand, a natural set of reductions for classical arithmetic is shown to be compatible with the normalization of the realizing term, implying that certain strategies for eliminating cuts and extracting a witness from (...)
    Remove from this list   Direct download (3 more)  
     
    Export citation  
     
    My bibliography  
1 — 50 / 883