Apologies. The purpose of the following talk is to give an overview of the present state of aims, methods and results in Pure Proof Theory. Shortage of time forces me to concentrate on my very personal views. This entails that I will emphasize the work which I know best, i.e., work that has been done in the triangle Stanford, Munich and Münster. I am of course well aware that there are as important results coming from outside this triangle (...) and I apologize for not displaying these results as well.Moreover the audience should be aware that in some points I have to oversimplify matters. Those who complain about that are invited to consult the original papers.1.1. General. Proof theory startedwithHilbert's Programme which aimed at a finitistic consistency proof for mathematics.By Gödel's Theorems, however, we know that we can neither formalize all mathematics nor even prove the consistency of formalized fragments by finitistic means. Inspite of this fact I want to give some reasons why I consider proof theory in the style of Gentzen's work still as an important and exciting field of Mathematical Logic. I will not go into applications of Gentzen's cut-elimination technique to computer science problems—this may be considered as applied proof theory—but want to concentrate on metamathematical problems and results. In this sense I am talking about Pure Proof Theory.Mathematicians are interested in structures. There is only one way to find the theorems of a structure. Start with an axiom system for the structure and deduce the theorems logically. These axiom systems are the objects of proof-theoretical research. Studying axiom systems there is a series of more or less obvious questions. (shrink)

Apologies. The purpose of the following talk is to give an overview of the present state of aims, methods and results in Pure Proof Theory. Shortage of time forces me to concentrate on my very personal views. This entails that I will emphasize the work which I know best, i.e., work that has been done in the triangle Stanford, Munich and Münster. I am of course well aware that there are as important results coming from outside this triangle (...) and I apologize for not displaying these results as well.Moreover the audience should be aware that in some points I have to oversimplify matters. Those who complain about that are invited to consult the original papers.1.1. General. Proof theory startedwithHilbert's Programme which aimed at a finitistic consistency proof for mathematics.By Gödel's Theorems, however, we know that we can neither formalize all mathematics nor even prove the consistency of formalized fragments by finitistic means. Inspite of this fact I want to give some reasons why I consider proof theory in the style of Gentzen's work still as an important and exciting field of Mathematical Logic. I will not go into applications of Gentzen's cut-elimination technique to computer science problems—this may be considered as applied proof theory—but want to concentrate on metamathematical problems and results. In this sense I am talking about Pure Proof Theory.Mathematicians are interested in structures. There is only one way to find the theorems of a structure. Start with an axiom system for the structure and deduce the theorems logically. These axiom systems are the objects of proof-theoretical research. Studying axiom systems there is a series of more or less obvious questions. (shrink)

In this paper we argue that hybrid logic is the deductive setting most natural for Kripke semantics. We do so by investigating hybrid axiomatics for a variety of systems, ranging from the basic hybrid language (a decidable system with the same complexity as orthodox propositional modal logic) to the strong Priorean language (which offers full first-order expressivity).We show that hybrid logic offers a genuinely first-order perspective on Kripke semantics: it is possible to define base logics which extend automatically to a (...) wide variety of frame classes and to prove completeness using the Henkin method. In the weaker languages, this requires the use of non-orthodox rules. We discuss these rules in detail and prove non-eliminability and eliminability results. We also show how another type of rule, which reflects the structure of the strong Priorean language, can be employed to give an even wider coverage of frame classes. We show that this deductive apparatus gets progressively simpler as we work our way up the expressivity hierarchy, and conclude the paper by showing that the approach transfers to first-order hybrid logic. (shrink)

In the present note we make use of some information given in [2]. Also, the terminology and notation do not dier from those accepted in [2]; in particular this concerns the formalism for the predicate calculus. Let A be a model of a rst-order language L. We say that A realizes a set of formulas Fla i A j= [a] for some valuation a in A and all 2 . We say that A omits i A does not realize . (...) A formula 2 Fla is consistent with a theory T in i there is a model of T which realizes fg. (shrink)

By generalizing Kreisel’s proof of the Second Incompleteness Theorem of G¨odel I extract a general principle which can also be used for otherpurely model-theoretical proofs of that theorem.

Translation of: Kritik der reinen Vernunft.

This introduction to the basic ideas of structural proof theory contains a thorough discussion and comparison of various types of formalization of first-order logic. Examples are given of several areas of application, namely: the metamathematics of pure first-order logic (intuitionistic as well as classical); the theory of logic programming; category theory; modal logic; linear logic; first-order arithmetic and second-order logic. In each case the aim is to illustrate the methods in relatively simple situations and then apply them elsewhere (...) in much more complex settings. There are numerous exercises throughout the text. In general, the only prerequisite is a standard course in first-order logic, making the book ideal for graduate students and beginning researchers in mathematical logic, theoretical computer science and artificial intelligence. For the new edition, many sections have been rewritten to improve clarity, new sections have been added on cut elimination, and solutions to selected exercises have been included. (shrink)

This book continues from where the authors' previous book, Structural Proof Theory, ended. It presents an extension of the methods of analysis of proofs in pure logic to elementary axiomatic systems and to what is known as philosophical logic. A self-contained brief introduction to the proof theory of pure logic is included that serves both the mathematically and philosophically oriented reader. The method is built up gradually, with examples drawn from theories of order, lattice theory and (...) elementary geometry. The aim is, in each of the examples, to help the reader grasp the combinatorial behaviour of an axiom system, which typically leads to decidability results. The last part presents, as an application and extension of all that precedes it, a proof-theoretical approach to the Kripke semantics of modal and related logics, with a great number of new results, providing essential reading for mathematical and philosophical logicians. (shrink)

Sequent calculi constitute an interesting and important category of proof systems. They are much less known than axiomatic systems or natural deduction systems are, and they are much less known than they should be. Sequent calculi were designed as a theoretical framework for investigations of logical consequence, and they live up to the expectations completely as an abundant source of meta-logical results. The goal of this book is to provide a fairly comprehensive view of sequent calculi -- including a (...) wide range of variations. The focus is on sequent calculi for various non-classical logics, from intuitionistic logic to relevance logic, through linear and modal logics. A particular version of sequent calculi, the so-called consecution calculi, have seen important new developments in the last decade or so. The invention of new consecution calculi for various relevance logics allowed the last major open problem in the area of relevance logic to be solved positively: pure ticket entailment is decidable. An exposition of this result is included in chapter 9 together with further new decidability results (for less famous systems). A series of other results that were obtained by J. M. Dunn and me, or by me in the last decade or so, are also presented in various places in the book. Some of these results are slightly improved in their current presentation. Obviously, many calculi and several important theorems are not new. They are included here to ensure the completeness of the picture; their original formulations may be found in the referenced publications. This book contains very little about semantics, in general, and about the semantics of non-classical logic in particular. (shrink)

In the 18th and 19th centuries two transitions took place in the development of mathematical analysis: a shift from the geometric approach to the formula-centered approach, followed by a shift from the formula-centered approach to the concept-centered approach. We identify, on the basis of Bolzano's Purely Analytic Proof [Bolzano 1817], the ways in which Bolzano's approach can be said to be concept-centered. Moreover, we conclude that Bolzano's attitude towards the geometric approach on the one hand and the formula-centered approach (...) on the other were of a different nature; the for­mer being one of rejection, the latter of non-participation. Bolzano supports his concept-centered methodology by philosophical views, which were partially shared by mathematicians with a formula-centered approach to analysis. (shrink)

Purity is known as an ideal of proof that restricts a proof to notions belonging to the ‘content’ of the theorem. In this paper, our main interest is to develop a conception of purity for formal (natural deduction) proofs. We develop two new notions of purity: one based on an ontological notion of the content of a theorem, and one based on the notions of surrogate ontological content and structural content. From there, we characterize which (classical) first-order natural (...) deduction proofs of a mathematical theorem are pure. Formal proofs that refer to the ontological content of a theorem will be called ‘fully ontologically pure’. Formal proofs that refer to a surrogate ontological content of a theorem will be called ‘secondarily ontologically pure’, because they preserve the structural content of a theorem. We will use interpretations between theories to develop a proof-theoretic criterion that guarantees secondary ontological purity for formal proofs. (shrink)

This book provides a detailed, updated exposition and defense of five of the historically most important (but in recent years largely neglected) philosophical proofs of God’s existence: the Aristotelian, the Neo-Platonic, the Augustinian, the Thomistic, and the Rationalist. It also offers a thorough treatment of each of the key divine attributes—unity, simplicity, eternity, omnipotence, omniscience, perfect goodness, and so forth—showing that they must be possessed by the God whose existence is demonstrated by the proofs. Finally, it answers at length all (...) of the objections that have been leveled against these proofs. This work provides as ambitious and complete a defense of traditional natural theology as is currently in print. Its aim is to vindicate the view of the greatest philosophers of the past— thinkers like Aristotle, Plotinus, Augustine, Aquinas, Leibniz, and many others— that the existence of God can be established with certainty by way of purely rational arguments. It thereby serves as a refutation both of atheism and of the fideism that gives aid and comfort to atheism. (shrink)

In this paper, we show the equivalence between the provability of a proof system of basic hybrid logic and that of translated formulas of the classical predicate logic with equality and explicit substitution by a purely proof–theoretic method. Then we show the equivalence of two groups of proof systems of hybrid logic: the group of labelled deduction systems and the group of modal logic-based systems.

It is well known that the modal logic S5 can be embedded in the classical predicate logic by interpreting the modal operator in terms of a quantifier. Wajsberg [10] proved this fact in a syntactic way. Mints [7] extended this result to the quantified version of S5; using a purely proof-theoretic method he showed that the quantified S5 corresponds to the classical predicate logic with one-sorted variable. In this paper we extend Mints' result to the basic modal logic S4; (...) we investigate the correspondence between the quantified versions of S4 (with and without the Barcan formula) and the classical predicate logic (with one-sorted variable). We present a purely proof-theoretic proof-transformation method, reducing an LK-proof of an interpreted formula to a modal proof. (shrink)

In order to perform certain actions – such as incarcerating a person or revoking parental rights – the state must establish certain facts to a particular standard of proof. These standards – such as preponderance of evidence and beyond reasonable doubt – are often interpreted as likelihoods or epistemic confidences. Many theorists construe them numerically; beyond reasonable doubt, for example, is often construed as 90 to 95% confidence in the guilt of the defendant. -/- A family of influential cases (...) suggests standards of proof should not be interpreted numerically. These ‘proof paradoxes’ illustrate that purely statistical evidence can warrant high credence in a disputed fact without satisfying the relevant legal standard. In this essay I evaluate three influential attempts to explain why merely statistical evidence cannot satisfy legal standards. (shrink)

A logic of grounding where what is grounded can be a collection of truths is a “many-many” logic of ground. The idea that grounding might be irreducibly many-many has recently been suggested by Dasgupta. In this paper I present a range of novel philosophical and logical reasons for being interested in many-many logics of ground. I then show how Fine’s State-Space semantics for the Pure Logic of Ground can be extended to the many-many case, giving rise to the (...) class='Hi'>Pure Logic of Many-Many Ground. In the second, more technical, part of the paper, I do two things. First, I present an alternative formalization of plg; this allows us to simplify Fine’s completeness proof for plg. Second, I formalize plmmg using an infinitary sequent calculus and prove that this formalization is sound and complete. (shrink)

This is a purely conceptual paper. It aims at presenting and putting into perspective the idea of a proof-theoretic semantics of the logical operations. The first section briefly surveys various semantic paradigms, and Section 2 focuses on one particular paradigm, namely the proof-theoretic semantics of the logical operations.

It is well known that the modal logic S5 can be embedded in the classical predicate logic by interpreting the modal operator in terms of a quantifier. Wajsberg proved this fact in a syntactic way. Mints extended this result to the quantified version of S5; using a purely proof-theoretic method he showed that the quantified S5 corresponds to the classical predicate logic with one-sorted variable. In this paper we extend Mints’ result to the basic modal logic S4; we investigate (...) the correspondence between the quantified versions of S4 and the classical predicate logic. We present a purely proof-theoretic proof-transformation method, reducing an LK-proof of an interpreted formula to a modal proof. (shrink)

Our aim is to express in exact terms the old idea of solving problems by pure questioning. We consider the problem of derivability: "Is A derivable from Δ by classical propositional logic?". We develop a calculus of questions E*; a proof (called a Socratic proof) is a sequence of questions ending with a question whose affirmative answer is, in a sense, evident. The calculus is sound and complete with respect to classical propositional logic. A Socratic proof (...) in E* can be transformed into a Gentzen-style proof in some sequent calculi. Next we develop a calculus of questions E**; Socratic proofs in E** can be transformed into analytic tableaux. We show that Socratic proofs can be grounded in Inferential Erotetic Logic. After a slight modification, the analyzed systems can also be viewed as hypersequent calculi. (shrink)

First-order logic is formalized by means of tools taken from the logic of questions. A calculus of questions which is a counterpart of the Pure Calculus of Quantifiers is presented. A direct proof of completeness of the calculus is given.

We discuss the problem raised by Miller to re-prove the well-known equivalences of some Lindenbaum theorems for deductive systems without an application of the Axiom of Choice. We present five special constructions of deductive systems, each of them providing some partial solutions to the mathematical problem. We conclude with a short discussion of the underlying philosophical problem of deciding, whether a given proof satisfies our demand that the Axiom of Choice is not applied.

This contribution defends two claims. The first is about why thought experiments are so relevant and powerful in mathematics. Heuristics and proof are not strictly and, therefore, the relevance of thought experiments is not contained to heuristics. The main argument is based on a semiotic analysis of how mathematics works with signs. Seen in this way, formal symbols do not eliminate thought experiments (replacing them by something rigorous), but rather provide a new stage for them. The formal world resembles (...) the empirical world in that it calls for exploration and offers surprises. This presents a major reason why thought experiments occur both in empirical sciences and in mathematics. The second claim is about a looming aporia that signals the limitation of thought experiments. This aporia arises when mathematical arguments cease to be fully accessible, thus violating a precondition for experimenting in thought. The contribution focuses on the work of Vladimir Voevodsky (1966–2017, Fields medalist in 2002) who argued that even very pure branches of mathematics cannot avoid inaccessibility of proof. Furthermore, he suggested that computer verification is a feasible path forward, but only if proof is not modeled in terms of formal logic. (shrink)

The paper contains proof-theoretic investigation on extensions of Kripke-Platek set theory, KP, which accommodate first-order reflection. Ordinal analyses for such theories are obtained by devising cut elimination procedures for infinitary calculi of ramified set theory with Пn reflection rules. This leads to consistency proofs for the theories KP+Пn reflection using a small amount of arithmetic and the well-foundedness of a certain ordinal system with respect to primitive decending sequences. Regarding future work, we intend to avail ourselves of these new (...) cut elimination techniques to attain an ordinal analysis of П12 comprehension by approaching П12 comprehension through transfinite levels of reflection. (shrink)

We introduce an extension of natural deduction that is suitable for dealing with modal operators and induction. We provide a proof reduction system and we prove a strong normalization theorem for an intuitionistic calculus. As a consequence we obtain a purely syntactic proof of consistency. We also present a classical calculus and we relate provability in the two calculi by means of an adequate formula translation.

In a classical 1976 paper, Solovay proved the arithmetical completeness of the modal logic GL; provability of a formula in GL coincides with provability of its arithmetical interpretations of it in Peano Arithmetic. In that paper, he also provided an axiomatic system GLS and proved arithmetical completeness for GLS; provability of a formula in GLS coincides with truth of its arithmetical interpretations in the standard model of arithmetic. Proof theory for GL has been studied intensively up to the present (...) day. However, it might sound somewhat strange that no proof theory for GLS was ever developed nor even suggested thus far, except for the axiomatic system offered by Solovay. In this paper, we develop a proof theory for GLS based on the sequent calculus method. We provide a sequent calculus for GLS and prove the cut-elimination and some standard consequences of it: the interpolation and definability theorems. As another consequence of cut-elimination, we also prove the equivalence of GL and GLS with respect to a special form of formulas which we call Gödel sentences, using a purely proof-theoretical method. (shrink)

In this paper, we suggest the broader concept of proof-event, introduced by Joseph Goguen, as a fundamental methodological tool for studying proofs in history of mathematics. In this framework, proof is understood not as a purely syntactic object, but as a social process that involves at least two agents; this highlights the communicational aspect of proving. We claim that historians of mathematics essentially study proof-events in their research, since the mathematical proofs they face in the extant sources (...) involve many informal components, often not completely formalizable, and convey some kind of semantic content calling for understanding and verification. We illustrate the application of this methodological approach in some outstanding historical cases, paying particular attention to the process of proof interpretation that makes a proof-event alive. Finally, we suggest a classification of proof-events, according to the conditions imposed upon problem-solving. This enables us to speak about broad classes of proof-events in history of mathematics that share a common characteristic. (shrink)

Why can testimony alone be enough for findings of liability? Why statistical evidence alone can’t? These questions underpin the “Proof Paradox” (Redmayne 2008, Enoch et al. 2012). Many epistemologists have attempted to explain this paradox from a purely epistemic perspective. I call it the “Epistemic Project”. In this paper, I take a step back from this recent trend. Stemming from considerations about the nature and role of standards of proof, I define three requirements that any successful account in (...) line with the Epistemic Project should meet. I then consider three recent epistemic accounts on which the standard is met when the evidence rules out modal risk (Pritchard 2018), normic risk (Ebert et al. 2020), or relevant alternatives (Gardiner 2019 2020). I argue that none of these accounts meets all the requirements. Finally, I offer reasons to be pessimistic about the prospects of having a successful epistemic explanation of the paradox. I suggest the discussion on the proof paradox would benefit from undergoing a ‘value-turn’. (shrink)

Miller, D., G. Nadathur, F. Pfenning and A. Scedrov, Uniform proofs as a foundation for logic programming, Annals of Pure and Applied Logic 51 125–157. A proof-theoretic characterization of logical languages that form suitable bases for Prolog-like programming languages is provided. This characterization is based on the principle that the declarative meaning of a logic program, provided by provability in a logical system, should coincide with its operational meaning, provided by interpreting logical connectives as simple and fixed search (...) instructions. The operational semantics is formalized by the identification of a class of cut-free sequent proofs called uniform proofs. A uniform proof is one that can be found by a goal-directed search that respects the interpretation of the logical connectives as search instructions. The concept of a uniform proof is used to define the notion of an abstract logic programming language, and it is shown that first-order and higher-order Horn clauses with classical provability are examples of such a language. Horn clauses are then generalized to hereditary Harrop formulas and it is shown that first-order and higher-order versions of this new class of formulas are also abstract logic programming languages if the inference rules are those of either intuitionistic or minimal logic. The programming language significance of the various generalizations to first-order Horn clauses is briefly discussed. (shrink)

This article develops the Pure Logic of Iterated Full Ground (PLIFG), a logic of ground that can deal with claims of the form “ϕ grounds that (ψ grounds θ)”—what we call iterated grounding claims. The core idea is that some truths Γ ground a truth ϕ when there is an explanatory argument (of a certain sort) from premisses Γ to conclusion ϕ. By developing a deductive system that distinguishes between explanatory and nonexplanatory arguments we can give introduction rules for (...) operators for factive and nonfactive full ground, as well as for a propositional “identity” connective. Elimination rules are then found by using a proof-theoretic inversion principle. (shrink)

Hilbert’s program in the philosophy of mathematics comes in two parts. One part is a technical part. To carry out this part of the program one has to prove a certain technical result. The other part of the program is a philosophical part. It is concerned with philosophical questions that are the real aim of the program. To carry out this part one, basically, has to show why the technical part answers the philosophical questions one wanted to have answered. Hilbert (...) probably thought that he had completed the philosophical part of his program, maybe up to a few details. What was left to do was the technical part. To carry it out one, roughly, had to give a precise axiomatization of mathematics and show that it is consistent on purely finitistic grounds. This would come down to giving a relative consistency proof of mathematics in finitist mathematics, or to give a proof-theoretic reduction of mathematics on to finitist mathematics (we will look at these notions in more detail soon). It is widely believed that Gödel’s theorems showed that the technical part of Hilbert’s program could not be carried out. Gödel’s theorems show that the consistency of arithmetic can not even be proven in arithmetic, not to speak of by finitistic means alone. So, the technical part of Hilbert’s program is hopeless, and since Hilbert’s program essentially relied on both the technical and the philosophical part, Hilbert’s program as a whole is hopeless. Justified as this attitude is, it is a bit unfortunate. It is unfortunate because it takes away too much attention from the philosophical part of Hilbert’s program. And this is unfortunate for two reasons. (shrink)

In this paper we calibrate the exact proof-theoretic strength of Kruskal's theorem, thereby giving, in some sense, the most elementary proof of Kruskal's theorem. Furthermore, these investigations give rise to ordinal analyses of restricted bar induction.

We upgrade [3] to a complete proof of the conjecture NP = PSPACE that is known as one of the fundamental open problems in the mathematical theory of computational complexity; this proof is based on [2]. Since minimal propositional logic is known to be PSPACE complete, while PSPACE to include NP, it suffices to show that every valid purely implicational formula ρ has a proof whose weight and time complexity of the provability involved are both polynomial in (...) the weight of ρ. As is [3], we use proof theoretic approach. Recall that in [3] we considered any valid ρ in question that had a “short” tree-like proof π in the Hudelmaier-style cutfree sequent calculus for minimal logic. The “shortness” means that the height of π and the total weight of different formulas occurring in it are both polynomial in the weight of ρ. However, the size, and hence also the weight, of π could be exponential in that of ρ. To overcome this trouble we embedded π into Prawitz’s proof system of natural deductions containing single formulas, instead of sequents. As in π, the height and the total weight of different formulas of the resulting tree-like natural deduction ∂1 were polynomial, although the size of ∂1 still could be exponential, in the weight of ρ. In our next, crucial move, ∂1 was deterministically compressed into a “small”, although multipremise, dag-like deduction ∂ whose horizontal levels contained only mutually different formulas, which made the whole weight polynomial in that of ρ. However, ∂ required a more complicated verification of the underlying provability of ρ. In this paper we present a nondeterministic compression of ∂ into a desired standard dag-like deduction ∂0 that deterministically proves ρ in time and space polynomial in the weight of ρ.2 Together with [3] this completes the proof of NP = PSPACE.Natural deductions are essential for our proof. Tree-to-dag horizontal compression of π merging equal sequents, instead of formulas, is not sufficient, since the total number of different sequents in π might be exponential in the weight of ρ – even assuming that all formulas occurring in sequents are subformulas of ρ. On the other hand, we need Hudelmaier’s cutfree sequent calculus in order to control both the height and total weight of different formulas of the initial tree-like proof π, since standard Prawitz’s normalization although providing natural deductions with the subformula property does not preserve polynomial heights. It is not clear yet if we can omit references to π even in the proof of the weaker result NP = coNP. (shrink)

Pure Type Systems, PTSs, introduced as a generalisation of the type systems of Barendregt's lambda-cube, provide a foundation for actual proof assistants, aiming at the mechanic verification of formal proofs. In this paper we consider simplifications of some of the rules of PTSs. This is of independent interest for PTSs as this produces more flexible PTS-like systems, but it will also help, in a later paper, to bridge the gap between PTSs and systems of Illative Combinatory Logic. First (...) we consider a simplification of the start and weakening rules of PTSs, which allows contexts to be sets of statements, and a generalisation of the conversion rule. The resulting Set-modified PTSs or SPTSs, though essentially equivalent to PTSs, are closer to standard logical systems. A simplification of the abstraction rule results in Abstraction-modified PTSs or APTSs. These turn out to be equivalent to standard PTSs if and only if a condition (*) holds. Finally we consider SAPTSs which have both modifications. (shrink)