It is well understood and appreciated that Gödel’s Incompleteness Theorems apply to sufficiently strong, formal deductive systems. In particular, the theorems apply to systems which are adequate for conventional number theory. Less well known is that there exist algorithms which can be applied to such a system to generate a gödel-sentence for that system. Although the generation of a sentence is not equivalent to proving its truth, the present paper argues that the existence of these algorithms, when conjoined with Gödel’s (...) results and accepted theorems of recursion theory, does provide the basis for an apparent paradox. The difficulty arises when such an algorithm is embedded within a computer program of sufficient arithmetic power. The required computer program (an AI system) is described herein, and the paradox is derived. A solution to the paradox is proposed, which, it is argued, illuminates the truth status of axioms in formal models of programs and Turing machines. (shrink)

I had the pleasure of renewing my acquaintance with Per Lindström at the meeting of the Seventh Scandinavian Logic Symposium, held in Uppsala in August 1996. There at lunch one day, Per said he had long been curious about the development of some of the ideas in my paper [1960] on the arithmetization of metamathematics. In particular, I had used the construction of a non-standard definition !* of the set of axioms of P (Peano Arithmetic) to show that P + (...) {¬ Con!} is interpretable in P, where ! is a standard definition of the axioms of P and Con! expresses the consistency of P via that presentation. Per pointed out that there is a simple “two-line” proof of this interpretability result which does not require the use of such formulas as !*, and he wondered whether I had been aware of that. In fact, his proof had never occurred to me, and if it had at the time, it is possible I would never have been led to the use of non-natural definitions. Per regarded this as a happy accident, since subsequent work by him and others on interpretability made essential use of such definitions. In our conversation, I enlarged a bit on the background to my work on arithmetization, and when I was invited to contribute to this special issue of Theoria dedicated to Lindström, it seemed a natural choice to use the occasion to fill out the story. One caveat, though: the following is drawn largely from memory, not always reliable, supplemented by consultation of the 1960 paper and the 1957 dissertation from which it was drawn. (shrink)

Hilbert’s program was an ambitious and wide-ranging project in the philosophy and foundations of mathematics. In order to “dispose of the foundational questions in mathematics once and for all,” Hilbert proposed a two-pronged approach in 1921: first, classical mathematics should be formalized in axiomatic systems; second, using only restricted, “finitary” means, one should give proofs of the consistency of these axiomatic systems. Although Gödel’s incompleteness theorems show that the program as originally conceived cannot be carried out, it had many partial (...) successes, and generated important advances in logical theory and metatheory, both at the time and since. The article discusses the historical background and development of Hilbert’s program, its philosophical underpinnings and consequences, and its subsequent development and influences since the 1930s. (shrink)

In this paper we explain our pretense account of truth-talk and apply it in a diagnosis and treatment of the Liar Paradox. We begin by assuming that some form of deflationism is the correct approach to the topic of truth. We then briefly motivate the idea that all T-deflationists should endorse a fictionalist view of truth-talk, and, after distinguishing pretense-involving fictionalism (PIF) from error- theoretic fictionalism (ETF), explain the merits of the former over the latter. After presenting the basic framework (...) of our PIF account of truth-talk, we demonstrate a few advantages it offers over T-deflationist accounts that do not explicitly acknowledge pretense at work in the discourse. In turning to the Liar Paradox, we explain how the quasi-anaphoric functioning that our account attributes to truth-talk provides a diagnosis of the Liar Paradox (and other instances of semantic pathology) as having no content—in the sense of not specifying any of what we call M-conditions. At the same time, however, we vindicate the intuition that we can understand liar sentences, thereby avoiding one standard objection to “meaningless strategy” responses to the Liar Paradox. With this diagnosis in place, we then, by way of treatment, introduce a new predicate, ‘semantically defective’, and show how the explanation we give for its application allows for a consistent, yet revenge-immune, (dis)solution of the Liar Paradox, and semantic pathology generally. (shrink)

The goal of this paper is to explore the significance of Montague’s paradox—that is, any arithmetical theory $T\supseteq Q$ over a language containing a predicate $P$ satisfying $P\rightarrow \varphi $ and $T\vdash \varphi \,\therefore\,T\vdash P$ is inconsistent—as a limitative result pertaining to the notions of formal, informal, and constructive provability, in their respective historical contexts. To this end, the paradox is reconstructed in a quantified extension $\mathcal {QLP}$ of Artemov’s logic of proofs. $\mathcal {QLP}$ contains both explicit modalities $t:\varphi $ (...) and also proof quantifiers $x:\varphi $. In this system, the basis for the rule NEC is decomposed into a number of distinct principles governing how various modes of reasoning about proofs and provability can be internalized within the system itself. A conceptually motivated resolution to the paradox is proposed in the form of an argument for rejecting the unrestricted rule NEC on the basis of its subsumption of an intuitively invalid principle pertaining to the interaction of proof quantifiers and the proof-theorem relation expressed by explicit modalities. (shrink)

Proof-theoretic reflection principles are schemas which attempt to express the soundness of arithmetical theories within their own language, e.g., ${\mathtt{{Prov}_{\mathsf {PA}} \rightarrow \varphi }}$ can be understood to assert that any statement provable in Peano arithmetic is true. It has been repeatedly suggested that justification for such principles follows directly from acceptance of an arithmetical theory $\mathsf {T}$ or indirectly in virtue of their derivability in certain truth-theoretic extensions thereof. This paper challenges this consensus by exploring relationships between reflection principles (...) and principles of mathematical and transfinite induction as well as the status of the latter with respect to various foundational characterizations of number theory. (shrink)

Philosophers of science since Nagel have been interested in the links between intertheoretic reduction and explanation, understanding and other forms of epistemic progress. Although intertheoretic reduction is widely agreed to occur in pure mathematics as well as empirical science, the relationship between reduction and explanation in the mathematical setting has rarely been investigated in a similarly serious way. This paper examines an important particular case: the reduction of arithmetic to set theory. I claim that the reduction is unexplanatory. In defense (...) of this claim, I offer evidence from mathematical practice, and I respond to contrary suggestions due to Steinhart, Maddy, Kitcher and Quine. I then show how, even if set-theoretic reductions are generally not explanatory, set theory can nevertheless serve as a legitimate foundation for mathematics. Finally, some implications of my thesis for philosophy of mathematics and philosophy of science are discussed. In particular, I suggest that some reductions in mathematics are probably explanatory, and I propose that differing standards of theory acceptance might account for the apparent lack of unexplanatory reductions in the empirical sciences. (shrink)

ABSTRACT We use Gödel’s incompleteness theorems as a case study for investigating mathematical depth. We examine the philosophical question of what the depth of Gödel’s incompleteness theorems consists in. We focus on the methodological study of the depth of Gödel’s incompleteness theorems, and propose three criteria to account for the depth of the incompleteness theorems: influence, fruitfulness, and unity. Finally, we give some explanations for our account of the depth of Gödel’s incompleteness theorems.

This is a paper for a special issue of Semiotic Studies devoted to Stanislaw Krajewski’s paper. This paper gives some supplementary notes to Krajewski’s on the Anti-Mechanist Arguments based on Gödel’s incompleteness theorem. In Section 3, we give some additional explanations to Section 4–6 in Krajewski’s and classify some misunderstandings of Gödel’s incompleteness theorem related to AntiMechanist Arguments. In Section 4 and 5, we give a more detailed discussion of Gödel’s Disjunctive Thesis, Gödel’s Undemonstrability of Consistency Thesis and the definability (...) of natural numbers as in Section 7–8 in Krajewski’s, describing how recent advances bear on these issues. (shrink)

Georg Kreisel suggested various ways out of the Gödel incompleteness theorems. His remarks on ways out were somewhat parenthetical, and suggestive. He did not develop them in subsequent papers. One aim of this paper is not to develop those remarks, but to show how the basic idea that they express can be used to reason about the Lucas-Penrose-Putnam arguments that human minds are not finitary computational machines. Another aim is to show how one of Putnam’s two anti-functionalist arguments avoids the (...) logical error in the Lucas-Penrose arguments, extends those arguments, but succumbs to an absurdity. A third aim is to provide a categorization of the Lucas-Penrose-Putnam anti-functionalist arguments. (shrink)

We deal with the fragment of modal logic consisting of implications of formulas built up from the variables and the constant ‘true’ by conjunction and diamonds only. The weaker language allows one to interpret the diamonds as the uniform reflection schemata in arithmetic, possibly of unrestricted logical complexity. We formulate an arithmetically complete calculus with modalities labeled by natural numbers and ω, where ω corresponds to the full uniform reflection schema, whereas n<ω corresponds to its restriction to arithmetical Πn+1-formulas. This (...) calculus is shown to be complete w.r.t. a suitable class of finite Kripke models and to be decidable in polynomial time. (shrink)

We investigate the bimodal logics sound and complete under the interpretation of modal operators as the provability predicates in certain natural pairs of arithmetical theories . Carlson characterized the provability logic for essentially reflexive extensions of theories, i.e. for pairs similar to . Here we study pairs of theories such that the gap between and is not so wide. In view of some general results concerning the problem of classification of the bimodal provability logics we are particularly interested in such (...) pairs that is axiomatized over by ∏1-sentences only, and, for each n 1, proves the n-times iterated consistency of . A complete axiomatization, along with the appropriate Kripke semantics and decision procedures, is found for the two principal cases: finitely axiomatizable extensions of this sort, like e.g. ), ), etc., and reflexive extensions, like ¦n 1\s}), etc. We show that the first logic, ICP, is the minimal and the second one, RP, is the maximal within the class of the provability logics for such pairs of theories. We also show that there are some provability logics lying strictly between these two. As an application of the results of this paper, in the last section the polymodal provability logics for natural recursive progressions of theories based on iteration of consistency are characterized. We construct a system of ordinal notation , which gives exactly one notation to each constructive ordinal, such that the logic corresponding to any progression along coincides with that along natural Kalmar elementary well-orderings. (shrink)

Philosophers of language have drawn on metamathematical results in varied ways. Extensionalist philosophers have been particularly impressed with two, not unrelated, facts: the existence, due to Frege/Tarski, of a certain sort of semantics, and the seeming absence of intensional contexts from mathematical discourse. The philosophical import of these facts is at best murky. Extensionalists will emphasize the success and clarity of the model theoretic semantics; others will emphasize the relative poverty of the mathematical idiom; still others will question the aptness (...) of the standard extensional semantics for mathematics. In this paper I investigate some implications of the Gödel Second Incompleteness Theorem for these positions. I argue that the realm of mathematics, proof theory in particular, has been a breeding ground for intensionality and that satisfactory intensional semantic theories are implicit in certain rigorous technical accounts. (shrink)

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.

We argue that, under the usual assumptions for sufficiently strong arithmetical theories that are subject to Gödel’s First Incompleteness Theorem, one cannot, without impropriety, talk about *the* Gödel sentence of the theory. The reason is that, without violating the requirements of Gödel’s theorem, there could be a true sentence and a false one each of which is provably equivalent to its own unprovability in the theory if the theory is unsound.

In On Empirically Equivalent Systems of the World from 1975, Quine formulated a thesis of underdetermination roughly to the effect that every scientific theory has an empirically equivalent but logically incompatible rival, one that cannot be discarded merely as a terminological variant of the former. For Quine, the truth of this thesis was an open question. If true, some would argue that it undermines any belief in scientific theories that is based purely on their empirical success. But despite its potential (...) significance, surprisingly little has been done by way of establishing or refuting it. My aim is to establish the thesis for as large a class of theories as possible. Under various precisifications of the concepts involved, I show that it holds for all consistent and recursively axiomatizable theories that postulate infinitely many theoretical entities. (shrink)

This article is about Avicenna’s account of syllogisms comprising opposite premises. We examine the applications and the truth conditions of these syllogisms. Finally, we discuss the relation between these syllogisms and the principle of non-contradiction.

In this multi-disciplinary investigation we show how an evidence-based perspective of quantification---in terms of algorithmic verifiability and algorithmic computability---admits evidence-based definitions of well-definedness and effective computability, which yield two unarguably constructive interpretations of the first-order Peano Arithmetic PA---over the structure N of the natural numbers---that are complementary, not contradictory. The first yields the weak, standard, interpretation of PA over N, which is well-defined with respect to assignments of algorithmically verifiable Tarskian truth values to the formulas of PA under the interpretation. (...) The second yields a strong, finitary, interpretation of PA over N, which is well-defined with respect to assignments of algorithmically computable Tarskian truth values to the formulas of PA under the interpretation. We situate our investigation within a broad analysis of quantification vis a vis: * Hilbert's epsilon-calculus * Goedel's omega-consistency * The Law of the Excluded Middle * Hilbert's omega-Rule * An Algorithmic omega-Rule * Gentzen's Rule of Infinite Induction * Rosser's Rule C * Markov's Principle * The Church-Turing Thesis * Aristotle's particularisation * Wittgenstein's perspective of constructive mathematics * An evidence-based perspective of quantification. By showing how these are formally inter-related, we highlight the fragility of both the persisting, theistic, classical/Platonic interpretation of quantification grounded in Hilbert's epsilon-calculus; and the persisting, atheistic, constructive/Intuitionistic interpretation of quantification rooted in Brouwer's belief that the Law of the Excluded Middle is non-finitary. We then consider some consequences for mathematics, mathematics education, philosophy, and the natural sciences, of an agnostic, evidence-based, finitary interpretation of quantification that challenges classical paradigms in all these disciplines. (shrink)

What is the source of logical and mathematical truth? This book revitalizes conventionalism as an answer to this question. Conventionalism takes logical and mathematical truth to have their source in linguistic conventions. This was an extremely popular view in the early 20th century, but it was never worked out in detail and is now almost universally rejected in mainstream philosophical circles. Shadows of Syntax is the first book-length treatment and defense of a combined conventionalist theory of logic and mathematics. It (...) argues that our conventions, in the form of syntactic rules of language use, are perfectly suited to explain the truth, necessity, and a priority of logical and mathematical claims, as well as our logical and mathematical knowledge. (shrink)

In this multi-disciplinary investigation we show how an evidence-based perspective of quantification---in terms of algorithmic verifiability and algorithmic computability---admits evidence-based definitions of well-definedness and effective computability, which yield two unarguably constructive interpretations of the first-order Peano Arithmetic PA---over the structure N of the natural numbers---that are complementary, not contradictory. The first yields the weak, standard, interpretation of PA over N, which is well-defined with respect to assignments of algorithmically verifiable Tarskian truth values to the formulas of PA under the interpretation. (...) The second yields a strong, finitary, interpretation of PA over N, which is well-defined with respect to assignments of algorithmically computable Tarskian truth values to the formulas of PA under the interpretation. We situate our investigation within a broad analysis of quantification vis a vis: * Hilbert's epsilon-calculus * Goedel's omega-consistency * The Law of the Excluded Middle * Hilbert's omega-Rule * An Algorithmic omega-Rule * Gentzen's Rule of Infinite Induction * Rosser's Rule C * Markov's Principle * The Church-Turing Thesis * Aristotle's particularisation * Wittgenstein's perspective of constructive mathematics * An evidence-based perspective of quantification. By showing how these are formally inter-related, we highlight the fragility of both the persisting, theistic, classical/Platonic interpretation of quantification grounded in Hilbert's epsilon-calculus; and the persisting, atheistic, constructive/Intuitionistic interpretation of quantification rooted in Brouwer's belief that the Law of the Excluded Middle is non-finitary. We then consider some consequences for mathematics, mathematics education, philosophy, and the natural sciences, of an agnostic, evidence-based, finitary interpretation of quantification that challenges classical paradigms in all these disciplines. (shrink)

Esta enciclopédia abrange, de uma forma introdutória mas desejavelmente rigorosa, uma diversidade de conceitos, temas, problemas, argumentos e teorias localizados numa área relativamente recente de estudos, os quais tem sido habitual qualificar como «estudos lógico-filosóficos». De uma forma apropriadamente genérica, e apesar de o território teórico abrangido ser extenso e de contornos por vezes difusos, podemos dizer que na área se investiga um conjunto de questões fundamentais acerca da natureza da linguagem, da mente, da cognição e do raciocínio humanos, bem (...) como questões acerca das conexões destes com a realidade não mental e extralinguística. A razão daquela qualificação é a seguinte: por um lado, a investigação em questão é qualificada como filosófica em virtude do elevado grau de generalidade e abstracção das questões examinadas (entre outras coisas); por outro, a investigação é qualificada como lógica em virtude de ser uma investigação logicamente disciplinada, no sentido de nela se fazer um uso intenso de conceitos, técnicas e métodos provenientes da disciplina de lógica. O agregado de tópicos que constitui a área de estudos lógico-filosóficos é já visível, pelo menos em parte, no Tractatus Logico-Philosophicus de Ludwig Wittgenstein, uma obra publicada em 1921. E uma boa maneira de ter uma ideia sinóptica do território disciplinar abrangido por esta enciclopédia, ou pelo menos de uma porção substancial dele, é extrair do Tractatus uma lista dos tópicos mais salientes aí discutidos; a lista incluirá certamente tópicos do seguinte género, muitos dos quais se podem encontrar ao longo desta enciclopédia: factos e estados de coisas; objectos; representação; crenças e estados mentais; pensamentos; a proposição; nomes próprios; valores de verdade e bivalência; quantificação; funções de verdade; verdade lógica; identidade; tautologia; o raciocínio matemático; a natureza da inferência; o cepticismo e o solipsismo; a indução; as constantes lógicas; a negação; a forma lógica; as leis da ciência; o número. (shrink)

In this paper, we describe "metaphysical reductions", in which the well-defined terms and predicates of arbitrary mathematical theories are uniquely interpreted within an axiomatic, metaphysical theory of abstract objects. Once certain (constitutive) facts about a mathematical theory T have been added to the metaphysical theory of objects, theorems of the metaphysical theory yield both an analysis of the reference of the terms and predicates of T and an analysis of the truth of the sentences of T. The well-defined terms and (...) predicates of T are analyzed as denoting abstract objects and abstract relations, respectively, in the background metaphysics, and the sentences of T have a reading on which they are true. After the technical details are sketched, the paper concludes with some observations about the approach. One important observation concerns the fact that the proper axioms of the background theory abstract objects can be reformulated in a way that makes them sound more like logical axioms. Some philosophers have argued that we should accept (something like) them as being logical. (shrink)

We will study several weak axiom systems that use the Subtraction and Division primitives (rather than Addition and Multiplication) to formally encode the theorems of Arithmetic. Provided such axiom systems do not recognize Multiplication as a total function, we will show that it is feasible for them to verify their Semantic Tableaux, Herbrand, and Cut-Free consistencies. If our axiom systems additionally do not recognize Addition as a total function, they will be capable of recognizing the consistency of their Hilbert-style deductive (...) proofs. Our axiom systems will not be strong enough to recognize their Canonical Reflection principle, but they will be capable of recognizing an approximation of it, called the "Tangibility Reflection Principle". We will also prove some new versions of the Second Incompleteness Theorem stating essentially that it is not possible to extend our exceptions to the Incompleteness Theorem much further. (shrink)

Conventionalism about mathematics claims that mathematical truths are true by linguistic convention. This is often spelled out by appealing to facts concerning rules of inference and formal systems, but this leads to a problem: since the incompleteness theorems we’ve known that syntactic notions can be expressed using arithmetical sentences. There is serious prima facie tension here: how can mathematics be a matter of convention and syntax a matter of fact given the arithmetization of syntax? This challenge has been pressed in (...) the literature by Hilary Putnam and Peter Koellner. In this paper I sketch a conventionalist theory of mathematics, show that this conventionalist theory can meet the challenge just raised , and clarify the type of mathematical pluralism endorsed by the conventionalist by introducing the notion of a semantic counterpart. The paper’s aim is an improved understanding of conventionalism, pluralism, and the relationship between them. (shrink)

A crucial part of the contemporary interest in logicism in the philosophy of mathematics resides in its idea that arithmetical knowledge may be based on logical knowledge. Here an implementation of this idea is considered that holds that knowledge of arithmetical principles may be based on two things: (i) knowledge of logical principles and (ii) knowledge that the arithmetical principles are representable in the logical principles. The notions of representation considered here are related to theory-based and structure-based notions of representation (...) from contemporary mathematical logic. It is argued that the theory-based versions of such logicism are either too liberal (the plethora problem) or are committed to intuitively incorrect closure conditions (the consistency problem). Structure-based versions must on the other hand respond to a charge of begging the question (the circularity problem) or explain how one may have a knowledge of structure in advance of a knowledge of axioms (the signature problem). This discussion is significant because it gives us a better idea of what a notion of representation must look like if it is to aid in realizing some of the traditional epistemic aims of logicism in the philosophy of mathematics. (shrink)

The topic of this paper is our knowledge of the natural numbers, and in particular, our knowledge of the basic axioms for the natural numbers, namely the Peano axioms. The thesis defended in this paper is that knowledge of these axioms may be gained by recourse to judgements of probability. While considerations of probability have come to the forefront in recent epistemology, it seems safe to say that the thesis defended here is heterodox from the vantage point of traditional philosophy (...) of mathematics. So this paper focuses on providing a preliminary defense of this thesis, in that it focuses on responding to several objections. Some of these objections are from the classical literature, such as Frege's concern about indiscernibility and circularity, while other are more recent, such as Baker's concern about the unreliability of small samplings in the setting of arithmetic. Another family of objections suggests that we simply do not have access to probability assignments in the setting of arithmetic, either due to issues related to the~$\omega$-rule or to the non-computability and non-continuity of probability assignments. Articulating these objections and the responses to them involves developing some non-trivial results on probability assignments, such as a forcing argument to establish the existence of continuous probability assignments that may be computably approximated. In the concluding section, two problems for future work are discussed: developing the source of arithmetical confirmation and responding to the probabilistic liar. (shrink)

In this paper we formulate a version of Second Incompleteness Theorem. The idea is that a sequential sentence has ‘consistency power’ over a theory if it enables us to construct a bounded interpretation of that theory. An interpretation of V in U is bounded if, for some n , all translations of V -sentences are U -provably equivalent to sentences of complexity less than n . We call a sequential sentence with consistency power over T a pro-consistency statement for T (...) . We study pro-consistency statements. We provide an example of a pro-consistency statement for a sequential sentence A that is weaker than an ordinary consistency statement for A . We show that, if A is $${{\sf S}^{1}_{2}}$$ , this sentence has some further appealing properties, specifically that it is an Orey sentence for EA . The basic ideas of the paper essentially involve sequential theories. We have a brief look at the wider environment of the results, to wit the case of theories with pairing. (shrink)

In this paper, we characterize the strength of the predicative Frege hierarchy, , introduced by John Burgess in his book [J. Burgess, Fixing frege, in: Princeton Monographs in Philosophy, Princeton University Press, Princeton, 2005]. We show that and are mutually interpretable. It follows that is mutually interpretable with Q. This fact was proved earlier by Mihai Ganea in [M. Ganea, Burgess’ PV is Robinson’s Q, The Journal of Symbolic Logic 72 619–624] using a different proof. Another consequence of the our (...) main result is that is mutually interpretable with Kalmar Arithmetic . The fact that interprets EA was proved earlier by Burgess. We provide a different proof. Each of the theories is finitely axiomatizable. Our main result implies that the whole hierarchy taken together, , is not finitely axiomatizable. What is more: no theory that is mutually locally interpretable with is finitely axiomatizable. (shrink)

In this paper, we show how to construct for a given consistent theory U a $$\varSigma ^0_1$$ Σ 1 0 -predicate that both satisfies the Löb Conditions and the Kreisel Condition—even if U is unsound. We do this in such a way that U itself can verify satisfaction of an internal version of the Kreisel Condition.

In this paper we study the interpretations of a weak arithmetic, like Buss’s theory $\mathsf{S}^{1}_{2}$, in a given theory $U$. We call these interpretations the arithmetics of $U$. We develop the basics of the structure of the arithmetics of $U$. We study the provability logic of $U$ from the standpoint of the framework of the arithmetics of $U$. Finally, we provide a deeper study of the arithmetics of a finitely axiomatized sequential theory.

In this paper we study local induction w.r.t. Σ1‐formulas over the weak arithmetic. The local induction scheme, which was introduced in, says roughly this: for any virtual class that is progressive, i.e., is closed under zero and successor, and for any non‐empty virtual class that is definable by a Σ1‐formula without parameters, the intersection of and is non‐empty. In other words, we have, for all Σ1‐sentences S, that S implies, whenever is progressive. Since, in the weak context, we have (at (...) least) two definitions of Σ1, we obtain two minimal theories of local induction w.r.t. Σ1‐formulas, which we call Peano Corto and Peano Basso.In the paper we give careful definitions of Peano Corto and Peano Basso. We establish their naturalness both by giving a model theoretic characterization and by providing an equivalent formulation in terms of a sentential reflection scheme.The theories Peano Corto and Peano Basso occupy a salient place among the sequential theories on the boundary between weak and strong theories. They bring together a powerful collection of principles that is locally interpretable in. Moreover, they have an important role as examples of various phenomena in the metamathematics of arithmetical (and, more generally, sequential) theories. We illustrate this by studying their behavior w.r.t. interpretability, model interpretability and local interpretability. In many ways the theories are more like Peano arithmetic or Zermelo Fraenkel set theory, than like finitely axiomatized theories as Elementary Arithmetic, and. On the one hand, Peano Corto and Peano Basso are very weak: they are locally cut‐interpretable in. On the other hand, they behave as if they were strong: they are not contained in any consistent finitely axiomatized arithmetical theory, however strong. Moreover, they extend, the theory of parameter‐free Π1‐induction. (shrink)

We argue that thinking of the man-machine comparison in terms of a contest involves, in a reasonable scenario, a criterion of success that is neutral. This is because we want to avoid a petitio principii. We submit, however, that, by looking at things this way, one makes the most essential human things invisible. Thus, in a sense, the contest approach is self-defeating.

We investigate the theory IΔ 0 + Ω 1 and strengthen [Bu86. Theorem 8.6] to the following: if NP ≠ co-NP. then Σ-completeness for witness comparison formulas is not provable in bounded arithmetic. i.e. $I\delta_0 + \Omega_1 + \nvdash \forall b \forall c (\exists a(\operatorname{Prf}(a.c) \wedge \forall = \leq a \neg \operatorname{Prf} (z.b))\\ \rightarrow \operatorname{Prov} (\ulcorner \exists a(\operatorname{Prf}(a. \bar{c}) \wedge \forall z \leq a \neg \operatorname{Prf}(z.\bar{b})) \urcorner)).$ Next we study a "small reflection principle" in bounded arithmetic. We prove that for (...) all sentences φ $I\Delta_0 + \Omega_1 \vdash \forall x \operatorname{Prov}(\ulcorner \forall y \leq \bar{x} (\operatorname{Prf} (y. \overline{\ulcorner \varphi \urcorner}) \rightarrow \varphi)\urcorner).$ The proof hinges on the use of definable cuts and partial satisfaction predicates akin to those introduced by Pudlak in [Pu86]. Finally, we give some applications of the small reflection principle, showing that the principle can sometimes be invoked in order to circumvent the use of provable Σ-completeness for witness comparison formulas. (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.

The two different layers of logical theory—epistemological and ontological—are considered and explained. Special attention is given to epistemic assumptions of the kind that a judgement is granted as known, and their role in validating rules of inference, namely to aid the inferential preservation of epistemic matters from premise judgements to conclusion judgement, while ordinary Natural Deduction assumptions serve to establish the holding of consequence from antecedent propositions to succedent proposition.

In Honour of John Crossley’s 85th Birthday.

In this paper we prove that the preordering $\lesssim $ of provable implication over any recursively enumerable theory $T$ containing a modicum of arithmetic is uniformly dense. This means that we can find a recursive extensional density function $F$ for $\lesssim $. A recursive function $F$ is a density function if it computes, for $A$ and $B$ with $A\lnsim B$, an element $C$ such that $A\lnsim C\lnsim B$. The function is extensional if it preserves $T$-provable equivalence. Secondly, we prove a (...) general result that implies that, for extensions of elementary arithmetic, the ordering $\lesssim $ restricted to $\Sigma_{n}$-sentences is uniformly dense. In the last section we provide historical notes and background material. (shrink)

Can one quantify over absolutely everything? Absolutists answer positively, while relativists answer negatively. Here, I focus on the absolutism versus relativism debate in the framework of theories of truth, where relativism becomes a form of contextualism about truth predications. Contextualist theories of truth provide elegant and uniform solutions to the semantic paradoxes while preserving classical logic. However, they interpret harmless generalizations (such as “everything is self-identical”) in less than absolutely comprehensive domains, thus systematically misconstruing them. In this article, I show (...) that contextualism is broadly compatible with absolute generality. More specifically, I develop a bipartite contextualist semantics, or “bicontextualism,” on which sentences are split in two groups: the unproblematic sentences, which are compatible with absolute generality, and the problematic ones, which are given a relativist semantics. I then argue that bicontextualism retains the advantages of (orthodox) contextualism and does not give rise to new revenge paradoxes. (shrink)

I here investigate the sense in which diagonalization allows one to construct sentences that are self-referential. Truly self-referential sentences cannot be constructed in the standard language of arithmetic: There is a simple theory of truth that is intuitively inconsistent but is consistent with Peano arithmetic, as standardly formulated. True self-reference is possible only if we expand the language to include function-symbols for all primitive recursive functions. This language is therefore the natural setting for investigations of self-reference.

This paper is an investigation into what could be a goodexplication of ``theory S is reducible to theory T''''. Ipresent an axiomatic approach to reducibility, which is developedmetamathematically and used to evaluate most of the definitionsof ``reducible'''' found in the relevant literature. Among these,relative interpretability turns out to be most convincing as ageneral reducibility concept, proof-theoreticalreducibility being its only serious competitor left. Thisrelation is analyzed in some detail, both from the point of viewof the reducibility axioms and of modal logic.

From early work of N. Goodman to recent approaches by H. Field and D. Lewis, there have been attempts to combine 2nd order languages with calculi of individuals. This paper is a contribution, containing basic definitions and distinctions and some metatheorems, to the development of a general metatheory of such theories.

According to the implicit commitment thesis, once accepting a mathematical formal system S, one is implicitly committed to additional resources not immediately available in S. Traditionally, this thesis has been understood as entailing that, in accepting S, we are bound to accept reflection principles for S and therefore claims in the language of S that are not derivable in S itself. It has recently become clear, however, that such reading of the implicit commitment thesis cannot be compatible with well-established positions (...) in the foundations of mathematics which consider a specific theory S as self-justifying and doubt the legitimacy of any principle that is not derivable in S: examples are Tait’s finitism and the role played in it by Primitive Recursive Arithmetic, Isaacson’s thesis and Peano Arithmetic, Nelson’s ultrafinitism and sub-exponential arithmetical systems. This casts doubts on the very adequacy of the implicit commitment thesis for arithmetical theories. In the paper we show that such foundational standpoints are nonetheless compatible with the implicit commitment thesis. We also show that they can even be compatible with genuine soundness extensions of S with suitable form of reflection. The analysis we propose is as follows: when accepting a system S, we are bound to accept a fixed set of principles extending S and expressing minimal soundness requirements for S, such as the fact that the non-logical axioms of S are true. We call this invariant component the semantic core of implicit commitment. But there is also a variable component of implicit commitment that crucially depends on the justification given for our acceptance of S in which, for instance, may or may not appear reflection principles for S. We claim that the proposed framework regulates in a natural and uniform way our acceptance of different arithmetical theories. (shrink)

We study the relationships between two clusters of axiomatizations of Kripke’s fixed-point models for languages containing a self-applicable truth predicate. The first cluster is represented by what we will call ‘\-like’ theories, originating in recent work by Halbach and Horsten, whose axioms and rules are all valid in fixed-point models; the second by ‘\-like’ theories first introduced by Solomon Feferman, that lose this property but reflect the classicality of the metatheory in which Kripke’s construction is carried out. We show that (...) to any natural system in one cluster—corresponding to natural variations on induction schemata—there is a corresponding system in the other proving the same sentences true, addressing a problem left open by Halbach and Horsten and accomplishing a suitably modified version of the project sketched by Reinhardt aiming at an instrumental reading of classical theories of self-applicable truth. (shrink)

In the paper we investigate typed axiomatizations of the truth predicate in which the axioms of truth come with a built-in, minimal and self-sufficient machinery to talk about syntactic aspects of an arbitrary base theory. Expanding previous works of the author and building on recent works of Albert Visser and Richard Heck, we give a precise characterization of these systems by investigating the strict relationships occurring between them, arithmetized model constructions in weak arithmetical systems and suitable set existence axioms. The (...) framework considered will give rise to some methodological remarks on the construction of truth theories and provide us with a privileged point of view to analyze the notion of truth arising from compositional principles in a typed setting. (shrink)

Traces the development of recursive functions from their origins in the late nineteenth century to the mid-1930s, with particular emphasis on the work and influence of Kurt Gödel.

Hilbert developed his famous finitist point of view in several essays in the 1920s. In this paper, we discuss various extensions of it, with particular emphasis on those suggested by Hilbert and Bernays in Grundlagen der Mathematik (vol. I 1934, vol. II 1939). The paper is in three sections. The first deals with Hilbert's introduction of a restricted ? -rule in his 1931 paper ?Die Grundlegung der elementaren Zahlenlehre?. The main question we discuss here is whether the finitist (meta-)mathematician would (...) be entitled to accept this rule as a finitary rule of inference. In the second section, we assess the strength of finitist metamathematics in Hilbert and Bernays 1934. The third and final section is devoted to the second volume of Grundlagen der Mathematik. For preparatory reasons, we first discuss Gentzen's proposal of expanding the range of what can be admitted as finitary in his esssay ?Die Widerspruchsfreiheit der reinen Zahlentheorie? (1936). As to Hilbert and Bernays 1939, we end on a ?critical? note: however considerable the impact of this work may have been on subsequent developments in metamathematics, there can be no doubt that in it the ideals of Hilbert's original finitism have fallen victim to sheer proof-theoretic pragmatism. (shrink)

Within a weak subsystem of second-order arithmetic , that is -conservative over , we reformulate Kreisel's proof of the Second Incompleteness Theorem and Boolos' proof of the First Incompleteness Theorem.