It is a common thought that mathematics can be not only true but also beautiful, and many of the greatest mathematicians have attached central importance to the aesthetic merit of their theorems, proofs and theories. But how, exactly, should we conceive of the character of beauty in mathematics? In this paper I suggest that Kant's philosophy provides the resources for a compelling answer to this question. Focusing on §62 of the ‘Critique of Aesthetic Judgment’, I argue against the common (...) view that Kant's aesthetics leaves no room for beauty in mathematics. More specifically, I show that on the Kantian account beauty in mathematics is a non-conceptual response felt in light of our own creative activities involved in the process of mathematical reasoning. The Kantian proposal I thus develop provides a promising alternative to Platonist accounts of beauty widespread among mathematicians. While on the Platonist conception the experience of mathematical beauty consists in an intellectual insight into the fundamental structures of the universe, according to the Kantian proposal the experience of beauty in mathematics is grounded in our felt awareness of the imaginative processes that lead to mathematical knowledge. The Kantian account I develop thus offers to elucidate the connection between aesthetic reflection, creative imagination and mathematical cognition. (shrink)

The initial premise of this paper is that the structure of a proof is inherent in the definition of the proof. Side conditions to deal with the discharging of assumptions means that this does not hold for systems of natural deduction, where proofs are given by monotone inductive definitions. We discuss the idea of using higher order definitions and the notion of a functional closure as a foundation to avoid these problems. In order to focus on structural issues we (...) introduce a more abstract perspective, where a structural proof theory becomes part of a more general theory of functional closures. A notion of proof equations is discussed as a structural classifier and we compare the Russell and Ekman paradoxes to illustrate this. (shrink)

A new semantics is presented for the logic of proofs (LP), [1, 2], based on the intuition that it is a logic of explicit knowledge. This semantics is used to give new proofs of several basic results concerning LP. In particular, the realization of S4 into LP is established in a way that carefully examines and explicates the role of the + operator. Finally connections are made with the conventional approach, via soundness and completeness results.

“Now, in calm weather, to swim in the open ocean is as easy to the practised swimmer as to ride in a spring-carriage ashore. But the awful lonesomeness is intolerable. The intense concentration of self in the middle of such a heartless immensity, my God! who can tell it? Mark, how when sailors in a dead calm bathe in the open sea—mark how closely they hug their ship and only coast along her sides.” (Herman Melville, Moby Dick, Chapter 94).

Cook and Reckhow defined a propositional formulation of the pigeonhole principle. This paper shows that there are Frege proofs of this propositional pigeonhole principle of polynomial size. This together with a result of Haken gives another proof of Urquhart's theorem that Frege systems have an exponential speedup over resolution. We also discuss connections to provability in theories of bounded arithmetic.

This book presents reverse mathematics to a general mathematical audience for the first time. Reverse mathematics is a new field that answers some old questions. In the two thousand years that mathematicians have been deriving theorems from axioms, it has often been asked: which axioms are needed to prove a given theorem? Only in the last two hundred years have some of these questions been answered, and only in the last forty years has a systematic approach been developed. In Reverse (...) Mathematics, John Stillwell gives a representative view of this field, emphasizing basic analysis--finding the "right axioms" to prove fundamental theorems--and giving a novel approach to logic. Stillwell introduces reverse mathematics historically, describing the two developments that made reverse mathematics possible, both involving the idea of arithmetization. The first was the nineteenth-century project of arithmetizing analysis, which aimed to define all concepts of analysis in terms of natural numbers and sets of natural numbers. The second was the twentieth-century arithmetization of logic and computation. Thus arithmetic in some sense underlies analysis, logic, and computation. Reverse mathematics exploits this insight by viewing analysis as arithmetic extended by axioms about the existence of infinite sets. Remarkably, only a small number of axioms are needed for reverse mathematics, and, for each basic theorem of analysis, Stillwell finds the "right axiom" to prove it. By using a minimum of mathematical logic in a well-motivated way, Reverse Mathematics will engage advanced undergraduates and all mathematicians interested in the foundations of mathematics. (shrink)

Some thirty years ago, two proposals were made concerning criteria for identity of proofs. Prawitz proposed to analyze identity of proofs in terms of the equivalence relation based on reduction to normal form in natural deduction. Lambek worked on a normalization proposal analogous to Prawitz's, based on reduction to cut-free form in sequent systems, but he also suggested understanding identity of proofs in terms of an equivalence relation based on generality, two derivations having the same generality if (...) after generalizing maximally the rules involved in them they yield the same premises and conclusions up to a renaming of variables. These two proposals proved to be extensionally equivalent only for limited fragments of logic. The normalization proposal stands behind very successful applications of the typed lambda calculus and of category theory in the proof theory of intuitionistic logic. In classical logic, however, it did not fare well. The generality proposal was rather neglected in logic, though related matters were much studied in pure category theory in connection with coherence problems, and there are also links to low-dimensional topology and linear algebra. This proposal seems more promising than the other one for the general proof theory of classical logic. (shrink)

If proofs are nothing more than truth makers, then there is no force in the standard argument against classical logic (there is no guarantee that there is either a proof forA or a proof fornot A). The standard intuitionistic conception of a mathematical proof is stronger: there are epistemic constraints on proofs. But the idea that proofs must be recognizable as such by us, with our actual capacities, is incompatible with the standard intuitionistic explanations of the meanings (...) of the logical constants. Proofs are to be recognizable in principle, not necessarily in practice, as shown in section 1. Section 2 considers unknowable propositions of the kind involved in Fitch''s paradox:p and it will never be known thatp. It is argued that the intuitionist faces a dilemma: give up strongly entrenched common sense intuitions about such unknowable propositions, or give up verificationism. The third section considers one attempt to save intuitionism while partly giving up verificationism: keep the idea that a proposition is true iff there is a proof (verification) of it, and reject the idea that proofs must be recognizable in principle. It is argued that this move will have the effect that some standard reasons against classical semantics will be effective also against intuitionism. This is the case with Dummett''s meaning theoretical argument. At the same time the basic reason for regarding proofs as more than mere truth makers is lost. (shrink)

N. Tennant; XI*—Entailment and Proofs, Proceedings of the Aristotelian Society, Volume 79, Issue 1, 1 June 1979, Pages 167–190, https://doi.org/10.1093/aristote.

A structure which generalizes formulas by including substitution terms is used to represent proofs in classical logic. These structures, called expansion trees, can be most easily understood as describing a tautologous substitution instance of a theorem. They also provide a computationally useful representation of classical proofs as first-class values. As values they are compact and can easily be manipulated and transformed. For example, we present an explicit transformations between expansion tree proofs and cut-free sequential proofs. A (...) theorem prover which represents proofs using expansion trees can use this transformation to present its proofs in more human-readable form. Also a very simple computation on expansion trees can transform them into Craig-style linear reasoning and into interpolants when they exist. We have chosen a sublogic of the Simple Theory of Types for our classical logic because it elegantly represents substitutions at all finite types through the use of the typed -calculus. Since all the proof-theoretic results we shall study depend heavily on properties of substitutions, using this logic has allowed us to strengthen and extend prior results: we are able to prove a strengthen form of the firstorder interpolation theorem as well as provide a correct description of Skolem functions and the Herbrand Universe. The latter are not straightforward generalization of their first-order definitions. (shrink)

Proofs are central, and unique, to mathematics. They establish the truth of theorems and provide us with the most secure knowledge we can possess. It is thus perhaps unsurprising that philosophers once thought that the only value proofs have lies in establishing the truth of theorems. However, such a view is inconsistent with mathematical practice. If a proof’s only value is to show a theorem is true, then mathematicians would have no reason to reprove the same theorem in (...) different ways, yet this is a practice they frequently engage in. This suggests that proofs can have a wide variety of values. My purpose in this chapter is to provide a survey of some of them. I will discuss how proofs can have practical value, for example, by helping mathematicians to make new discoveries or learn new mathematical tools, and how they can have abstract value, for example, by being beautiful or explanatory. I will also explore the relationships between different proof values. (shrink)

Mathematicians often intentionally leave gaps in their proofs. Based on interviews with mathematicians about their refereeing practices, this paper examines the character of intentional gaps in published proofs. We observe that mathematicians’ refereeing practices limit the number of certain intentional gaps in published proofs. The results provide some new perspectives on the traditional philosophical questions of the nature of proof and of what grounds mathematical knowledge.

Partial consistency statements can be expressed as polynomial-size propositional formulas. Frege proof systems have polynomial-size partial self-consistency proofs. Frege proof systems have polynomial-size proofs of partial consistency of extended Frege proof systems if and only if Frege proof systems polynomially simulate extended Frege proof systems. We give a new proof of Reckhow's theorem that any two Frege proof systems p-simulate each other. The proofs depend on polynomial size propositional formulas defining the truth of propositional formulas. These are (...) already known to exist since the Boolean formula value problem is in alternating logarithmic time; this paper presents a proof of this fact based on a construction which is somewhat simpler than the prior proofs of Buss and of Buss-Cook- Gupta-Ramachandran. (shrink)

In this paper we extend to non-classical set theories the standard strategy of proving independence using Boolean-valued models. This extension is provided by means of a new technique that, combining algebras (by taking their product), is able to provide product-algebra-valued models of set theories. In this paper we also provide applications of this new technique by showing that: (1) we can import the classical independence results to non-classical set theory (as an example we prove the independence of $\mathsf {CH}$ ); (...) and (2) we can provide new independence results. We end by discussing the role of non-classical algebra-valued models for the debate between universists and multiversists and by arguing that non-classical models should be included as legitimate members of the multiverse. (shrink)

In this paper individual proofs are integrated into provability logic. Systems of axioms for a logic with operators “A is provable” and “p is a proof of A” are introduced, provided with Kripke semantics and decision procedure. Completeness theorems with respect to the arithmetical interpretation are proved.

This is a most welcome reissue of Davidson’s highly praised book, first published in 1987. The combination in a single book of arguments for the existence of Go.

This paper investigates the depth of resolution proofs, that is to say, the length of the longest path in the proof from an input clause to the conclusion. An abstract characterization of the measure is given, as well as a discussion of its relation to other measures of space complexity for resolution proofs.

This third edition, now available in paperback, is a follow up to the author's classic Boolean-Valued Models and Independence Proofs in Set Theory. It provides an exposition of some of the most important results in set theory obtained in the 20th century: the independence of the continuum hypothesis and the axiom of choice.

In this document, we study a 3-polygraphic translation for the proofs of SKS, a formal system for classical propositional logic. We prove that the free 3-category generated by this 3-polygraph describes the proofs of classical propositional logic modulo structural bureaucracy. We give a 3-dimensional generalization of Penrose diagrams and use it to provide several pictures of a proof. We sketch how local transformations of proofs yield a non contrived example of 4-dimensional rewriting.

After a brief flirtation with logicism around 1917, David Hilbertproposed his own program in the foundations of mathematics in 1920 and developed it, in concert with collaborators such as Paul Bernays andWilhelm Ackermann, throughout the 1920s. The two technical pillars of the project were the development of axiomatic systems for everstronger and more comprehensive areas of mathematics, and finitisticproofs of consistency of these systems. Early advances in these areaswere made by Hilbert (and Bernays) in a series of lecture courses atthe (...) University of Göttingen between 1917 and 1923, and notably in Ackermann's dissertation of 1924. The main innovation was theinvention of the -calculus, on which Hilbert's axiom systemswere based, and the development of the -substitution methodas a basis for consistency proofs. The paper traces the developmentof the ``simultaneous development of logic and mathematics'' throughthe -notation and provides an analysis of Ackermann'sconsistency proofs for primitive recursive arithmetic and for thefirst comprehensive mathematical system, the latter using thesubstitution method. It is striking that these proofs use transfiniteinduction not dissimilar to that used in Gentzen's later consistencyproof as well as non-primitive recursive definitions, and that thesemethods were accepted as finitistic at the time. (shrink)

We show how to extract effective bounds Φ for $\bigwedge u^1 \bigwedge v \leq_\gamma tu \bigvee w^\eta G_0$ -sentences which depend on u only (i.e. $\bigwedge u \bigwedge v \leq_\gamma tu \bigvee w \leq_\eta \Phi uG_0$ ) from arithmetical proofs which use analytical assumptions of the form \begin{equation*}\tag{*}\bigwedge x^\delta\bigvee y \leq_\rho sx \bigwedge z^\tau F_0\end{equation*} (γ, δ, ρ, and τ are arbitrary finite types, η ≤ 2, G0 and F0 are quantifier-free, and s and t are closed terms). If (...) τ ≤ 2, (*) can be weakened to $\bigwedge x^\delta, z^\tau\bigvee y \leq_\rho sx \bigwedge \tilde{z} \leq_\tau z F_0$ . This is used to establish new conservation results about weak König's lemma. Applications to proofs in classical analysis, especially uniqueness proofs in approximation theory, will be given in subsequent papers. (shrink)

In the paper the joint Logic of Proofs and Provability is presented that incorporates both the modality □ for provability 287–304) and the proof operator tF representing the proof predicate “t is a proof of F” . The obtained system naturally includes both the modal logic of provability GL and Artemov's Logic of Proofs . The presence of the modality □ requires two new operations on proofs that together with operations of allow to realize all the invariant (...) operations on proofs admitting description in the modal propositional language. Logic is proved to be decidable and complete with the intended provability semantics. (shrink)

Inductive characterizations of the sets of terms, the subset of strongly normalizing terms and normal forms are studied in order to reprove weak and strong normalization for the simply-typed λ-calculus and for an extension by sum types with permutative conversions. The analogous treatment of a new system with generalized applications inspired by generalized elimination rules in natural deduction, advocated by von Plato, shows the flexibility of the approach which does not use the strong computability/candidate style à la Tait and Girard. (...) It is also shown that the extension of the system with permutative conversions by η-rules is still strongly normalizing, and likewise for an extension of the system of generalized applications by a rule of ``immediate simplification''. By introducing an infinitely branching inductive rule the method even extends to Gödel's T. (shrink)

String representations of events are applied to Robin Cooper’s proposal that propositions in natural language semantics are types of situations. Links with the higher types of prooftheoretic semantics are forged, deepening type-theoretic interpretations of Discourse Representation Structures to encompass event structures.

In this paper I show that proofs by contradiction were a serious problem in seventeenth century mathematics and philosophy. Their status was put into question and positive mathematical developments emerged from such reflections. I analyse how mathematics, logic, and epistemology are intertwined in the issue at hand. The mathematical part describes Cavalieri's and Guldin's mathematical programmes of providing a development of parts of geometry free of proofs by contradiction. The logical part shows how the traditional Aristotelean doctrine that (...) perfect demonstrations are causal demonstrations influenced the reflection on proofs by contradiction. The main protagonist of this part is Wallis. Finally, I analyse some epistemological developments arising from the Cartesian tradition. In particular, I look at Arnauld's programme of providing an epistemologically motivated reformulation of Geometry free of proofs by contradiction. The conclusion explains in which sense these epistemological reflections can be compared with those informing contemporary intuitionism. (shrink)

Propositional proof complexity is the study of the sizes of propositional proofs, and more generally, the resources necessary to certify propositional tautologies. Questions about proof sizes have connections with computational complexity, theories of arithmetic, and satisfiability algorithms. This is article includes a broad survey of the field, and a technical exposition of some recently developed techniques for proving lower bounds on proof sizes.

The essay collection "Kant on Proofs for God's Existence" provides a highly needed, comprehensive analysis of the radical turns of Kant's views on proofs for God's existence.— In the "Theory of Heavens" (1755), Kant intends to harmonize the Newtonian laws of motion with a physico-theological argument for the existence of God. But only a few years later, in the "Ground of Proof" essay (1763), Kant defends an ontological ('possibility' or 'modal') argument on the basis of its logical exactitude (...) while he praises the physico-theological argument for its beauty and appeal to the common sense. In the first "Critique" (1781/7), Kant replaces traditional constitutive ontological, cosmological, and physico-theological proofs with his own regulative theoretical and moral-practical religious arguments. He continues to defend a moral argument in the second "Critique" (1788). But in the third "Critique" (1790), Kant reintroduces a physico-theological besides an ethicotheological argument in order to unify the critical system of philosophy. Kant develops further moral arguments and arguments from evil in the "Theodicy" essay (1791) and the "Religion" (1793/4), and still searches for the right kind of proof for God's existence in the "Opus postumum" (1796–1804).—Part one of this volume is dedicated to an analysis of Kant's proofs for God's existence in their historical order that explains which proofs Kant favors or rejects in various periods of his thought. Part two contains a systematic classification of main kinds of proof for God's existence in Kant that outlines the argumentative structure of particular kinds of proof and discusses Kant's potential reasons for their variations and modifications. The essay collection speaks to Kant specialists, philosophers, and theologians, but introduces the topic to non-academic readers also. -/- Contributers: Uygar Abaci (Pennsylvania State University), Craig Bacon (University of South Carolina), Andrew Chignell (Princeton University), Eckart Förster (Humboldt University, Johns Hopkins University), Ina Goy (Beijing Normal University) Paul Guyer (Brown University), Graham Oppy (Monash University), Lara Ostaric (Temple University), Stephen Palmquist (Independent Scholar), Lawrence Pasternack (Oklahoma State University), Konstantin Pollok (University of Mainz), Oliver Sensen (University of Tulane), Allen Wood (Bloomington University, Stanford University). (shrink)

One of the central aims of the philosophical analysis of mathematical explanation is to determine how one can distinguish explanatory proofs from non-explanatory proofs. In this paper, I take a closer look at the current status of the debate, and what the challenges for the philosophical analysis of explanatory proofs are. In order to provide an answer to these challenges, I suggest we start from analysing the concept understanding. More precisely, I will defend four claims: understanding is (...) a condition for explanation, unificatory understanding is a type of explanatory understanding, unificatory understanding is valuable in mathematics, and mathematical proofs can contribute to unificatory understanding. As a result, in a context where the epistemic aim is to unify mathematical results, I argue it is fruitful to make a distinction between proofs based on their explanatory value. (shrink)

We prove that for sufficiently large N, there are tautologies of size O that require proofs containing Ω lines in axiomatic systems of propositional logic based on axioms and the rule of substitution for single variables. These tautologies have proofs with O lines in systems with the multiple substitution rule.

This article features long-sought proofs with intriguing properties (such as the absence of double negation and the avoidance of lemmas that appeared to be indispensable), and it features the automated methods for finding them. The theorems of concern are taken from various areas of logic that include two-valued sentential (or propositional) calculus and infinite-valued sentential calculus. Many of the proofs (in effect) answer questions that had remained open for decades, questions focusing on axiomatic proofs. The approaches we (...) take are of added interest in that all rely heavily on the use of a single program that offers logical reasoning, William McCune's automated reasoning program OTTER. The nature of the successes and approaches suggests that this program offers researchers a valuable automated assistant. This article has three main components. First, in view of the interdisciplinary nature of the audience, we discuss the means for using the program in question (OTTER), which flags, parameters, and lists have which effects, and how the proofs it finds are easily read. Second, because of the variety of proofs that we have found and their significance, we discuss them in a manner that permits comparison with the literature. Among those proofs, we offer a proof shorter than that given by Meredith and Prior in their treatment of ukasiewicz's shortest single axiom for the implicational fragment of two-valued sentential calculus, and we offer a proof for the ukasiewicz 23-letter single axiom for the full calculus. Third, with the intent of producing a fruitful dialogue, we pose questions concerning the properties of proofs and, even more pressing, invite questions similar to those this article answers. (shrink)