Will Stafford

In proof-theoretic semantics, the validity of atomic formulas is defined as their derivability in systems of atomic rules. We distinguish two types of such systems and two variants of semantics of formulas, one based on introduction rules for logical constants and one based on elimination rules. We thus define four semantics with their respective consequence relations. As these are not necessarily closed under substitution of arbitrary formulas for atoms, we consider the substitution-closed subsets of these four consequence relations in addition. We show which logics, in the sense of formal systems, are complete for seven of these notions. This systematizes in one place four previous results with three new results. For the semantics based on elimination rules intuitionistic or classical logic is complete, depending on the type of atomic rules, whereas the semantics based on introduction rules characterize intermediate logics. This answers several open questions about the main notions of proof-theoretic validity, although for one semantics of the introduction rule type we can only make a conjecture about possible logics. Further notions of proof-theoretic validity are suggested by considering alternative systems of atomic rules from the perspective of logic programming.

Several recent results bring into focus the superintuitionistic nature of most notions of proof-theoretic validity, but little work has been done evaluating the consequences of these results. Proof-theoretic validity claims to offer a formal explication of how inferences follow from the definitions of logic connectives (which are defined by their introduction rules). This paper explores whether the new results undermine this claim. It is argued that, while the formal results are worrying, superintuitionistic inferences are valid because the treatments of atomic formulas are insufficiently general, and a resolution to this issue is proposed.

Prawitz conjectured that the proof-theoretically valid logic is intuitionistic logic. Recent work on proof-theoretic validity has disproven this. In fact, it has been shown that proof-theoretic validity is not even closed under substitution. In this paper, we make a minor modification to the definition of proof-theoretic validity found in Prawitz’s 1973paper ‘Towards a foundation of a general proof theory’ and refined by Schroeder-Heister in ‘Validity concepts in proof-theoretic semantics’ (2006). We will call the new notion generalized proof-theoretic validity and show that the logic of generalized proof-theoretic validity is intuitionistic logic.

An account of mathematical understanding should account for the differences between theorems whose proofs are “easy” to discover, and those whose proofs are difficult to discover. Though Hilbert seems to have created proof theory with the idea that it would address this kind of “discovermental complexity”, much more attention has been paid to the lengths of proofs, a measure of the difficulty of _verifying_ of a _given_ formal object that it is a proof of a given formula in a given formal system. In this paper we will shift attention back to discovermental complexity, by addressing a “topological” measure of proof complexity recently highlighted by Alessandra Carbone ( 2009 ). Though we will contend that Carbone’s measure fails as a measure of discovermental complexity, it forefronts numerous important formal and epistemological issues that we will discuss, including the structure of proofs and the question of whether impure proofs are systematically simpler than pure proofs.

The interplay of philosophical ambitions and technical reality have given birth to rich and interesting approaches to explain the oft-claimed special character of mathematical and logical knowledge. Two projects stand out both for their audacity and their innovativeness. These are logicism and proof-theoretic semantics. This dissertation contains three chapters exploring the limits of these two projects. In both cases I find the formal results offer a mixed blessing to the philosophical projects. Chapter 1. Is a logicist bound to the claim that as a matter of analytic truth there is an actual infinity of objects? If Hume’s Principle is analytic then in the standard setting the answer appears to be yes. Hodes’s work pointed to a way out by offering a modal picture in which only a potential infinity was posited. However, this project was abandoned due to apparent failures of cross-world predication. I re-explore this idea and discover that in the setting of the potential infinite one can interpret first-order Peano arithmetic, but not second-order Peano arithmetic. I conclude that in order for the logicist to weaken the metaphysically loaded claim of necessary actual infinities, they must also weaken the mathematics they recover. Chapter 2. There have been several recent results bringing into focus the super-intuitionistic nature of most notions of proof-theoretic validity. But there has been very little work evaluating the consequences of these results. In this chapter, I explore the question of whether these results undermine the claim that proof-theoretic validity shows us which inferences follow from the meaning of the connectives when defined by their introduction rules. It is argued that the super-intuitionistic inferences are valid due to the correspondence between the treatment of the atomic formulas and more complex formulas. And so the goals of proof-theoretic validity are not undermined. Chapter 3. Prawitz (1971) conjectured that proof-theoretic validity offers a semantics for intuitionistic logic. This conjecture has recently been proven false by Piecha and Schroeder-Heister (2019). This chapter resolves one of the questions left open by this recent result by showing the extensional alignment of proof-theoretic validity and general inquisitive logic. General inquisitive logic is a generalisation of inquisitive semantics, a uniform semantics for questions and assertions. The chapter further defines a notion of quasi-proof-theoretic validity by restricting proof-theoretic validity to allow double negation elimination for atomic formulas and proves the extensional alignment of quasi-proof-theoretic validity and inquisitive logic.Abstract prepared by Will Stafford extracted partially from the dissertation.

Proof-theoretic validity has proven a useful tool for proof-theoretic semantics, because it explains the harmony found in the introduction and elimination rules for the intuitionistic calculus. However, the demonstration that a rule of proof is proof-theoretically valid requires checking an infinite number of cases, which raises the question of whether proof-theoretic validity is decidable. It is proven here that it is for the most prominent formulations in the literature for propositional logic.

Prawitz conjectured that proof-theoretic validity offers a semantics for intuitionistic logic. This conjecture has recently been proven false by Piecha and Schroeder-Heister. This article resolves one of the questions left open by this recent result by showing the extensional alignment of proof-theoretic validity and general inquisitive logic. General inquisitive logic is a generalisation of inquisitive semantics, a uniform semantics for questions and assertions. The paper further defines a notion of quasi-proof-theoretic validity by restricting proof-theoretic validity to allow double negation elimination for atomic formulas and proves the extensional alignment of quasi-proof-theoretic validity and inquisitive logic.

Is a logicist bound to the claim that as a matter of analytic truth there is an actual infinity of objects? If Hume’s Principle is analytic then in the standard setting the answer appears to be yes. Hodes’s work pointed to a way out by offering a modal picture in which only a potential infinity was posited. However, this project was abandoned due to apparent failures of cross-world predication. We re-explore this idea and discover that in the setting of the potential infinite one can interpret first-order Peano arithmetic, but not second-order Peano arithmetic. We conclude that in order for the logicist to weaken the metaphysically loaded claim of necessary actual infinities, they must also weaken the mathematics they recover.