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)

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.

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)

The unwinding that Cook, 767–774 2004) proposed is a simple but powerful method of generating new paradoxes from known ones. This paper extends Cook’s unwinding to a larger class of paradoxes and studies further the basic properties of the unwinding. The unwinding we study is a procedure, by which when inputting a Boolean modal net together with a definable digraph, we get a set of sentences in which we have a ‘counterpart’ for each sentence of the Boolean modal net and (...) each point of the digraph. What is more, whenever a sentence of the Boolean modal net says another sentence is necessary, then the counterpart of the first sentence at a point correspondingly says the counterparts of the second one at all accessible points of that point are all true. The output of the procedure is called ‘the unwinding of a Boolean modal net on a definable digraph’. We prove that the unwinding procedure preserves paradoxicality: a Boolean modal net is paradoxical on a definable digraph, iff the unwinding of it on this digraph is also paradoxical. Besides, the dependence digraph for the unwinding of a Boolean modal net on a definable digraph is proved to be isomorphic to the unwinding of the dependence digraph for the Boolean modal net on the previous definable digraph. So the unwinding of a Boolean modal net on a digraph is self-referential, iff the Boolean modal net is self-referential and the digraph is cyclic. Thus, on the one hand, the unwinding of any Boolean modal net on an acyclic digraph is non-self-referential. In particular, the unwinding of any Boolean modal net on \ is non-self-referential. On the other hand, if a Boolean modal net is paradoxical on a locally finite digraph, the unwinding of it on that digraph must be self-referential. Hence, starting from a Boolean modal paradox, the unwinding can output a non-self-referential paradox only if the digraph is not locally finite. (shrink)

This paper proposes substitutional definitions of logical truth and consequence in terms of relative interpretations that are extensionally equivalent to the model-theoretic definitions for any relational first-order language. Our philosophical motivation to consider substitutional definitions is based on the hope to simplify the meta-theory of logical consequence. We discuss to what extent our definitions can contribute to that.

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)

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)

This paper investigates a set of issues connected with the so-called conservativeness argument against deflationism. Although I do not defend that argument, I think the discussion of it has raised some interesting questions about whether what I call “compositional principles,” such as “a conjunction is true iff its conjuncts are true,” have substantial content or are in some sense logically trivial. The paper presents a series of results that purport to show that the compositional principles for a first-order language, taken (...) together, have substantial logical strength, amounting to a kind of abstract consistency statement. (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)

Halbach has argued that Tarski biconditionals are not ontologically conservative over classical logic, but his argument is undermined by the fact that he cannot include a theory of arithmetic, which functions as a theory of syntax. This article is an improvement on Halbach's argument. By adding the Tarski biconditionals to inclusive negative free logic and the universal closure of minimal arithmetic, which is by itself an ontologically neutral combination, one can prove that at least one thing exists. The result can (...) then be strengthened to the conclusion that infinitely many things exist. Those things are not just all Gödel codes of sentences but rather all natural numbers. Against this background inclusive negative free logic collapses into noninclusive free logic, which collapses into classical logic. The consequences for ontological deflationism with respect to truth are discussed. (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)

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)

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)

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)

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)

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)

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)

I attribute an 'intensional reading' of the second incompleteness theorem to its author, Kurt G del. My argument builds partially on an analysis of intensional and extensional conceptions of meta-mathematics and partially on the context in which G del drew two familiar inferences from his theorem. Those inferences, and in particular the way that they appear in G del's writing, are so dubious on the extensional conception that one must doubt that G del could have understood his theorem extensionally. However, (...) on the intensional conception, the inferences are straightforward. For that reason I conclude that G del had an intensional understanding of his theorem. Since this conclusion is in tension with the generally accepted view of G del's understanding of mathematical truth, I explain how to reconcile that view with the intensional reading of the theorem that I attribute to G del. The result is a more detailed account of G del's conception of meta-mathematics than is currently available. (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.

A notion of finitary inductively presented (f.i.p.) logic is proposed here, which includes all syntactically described logics (formal systems)met in practice. A f.i.p. theory FS0 is set up which is universal for all f.i.p. logics; though formulated as a theory of functions and classes of expressions, FS0 is a conservative extension of PRA. The aims of this work are (i)conceptual, (ii)pedagogical and (iii)practical. The system FS0 serves under (i)and (ii)as a theoretical framework for the formalization of metamathematics. The general approach (...) may be used under (iii)for the computer implementation of logics. In all cases, the work aims to make the details manageable in a natural and direct way. (shrink)

-/- Provability logic is a modal logic that is used to investigate what arithmetical theories can express in a restricted language about their provability predicates. The logic has been inspired by developments in meta-mathematics such as Gödel’s incompleteness theorems of 1931 and Löb’s theorem of 1953. As a modal logic, provability logic has been studied since the early seventies, and has had important applications in the foundations of mathematics. -/- From a philosophical point of view, provability logic is interesting because (...) the concept of provability in a fixed theory of arithmetic has a unique and non-problematic meaning, other than concepts like necessity and knowledge studied in modal and epistemic logic. Furthermore, provability logic provides tools to study the notion of self-reference. (shrink)

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.

The goals of reduction andreductionism in the natural sciences are mainly explanatoryin character, while those inmathematics are primarily foundational.In contrast to global reductionistprograms which aim to reduce all ofmathematics to one supposedly ``universal'' system or foundational scheme, reductive proof theory pursues local reductions of one formal system to another which is more justified in some sense. In this direction, two specific rationales have been proposed as aims for reductive proof theory, the constructive consistency-proof rationale and the foundational reduction rationale. However, (...) recent advances in proof theory force one to consider the viability of these rationales. Despite the genuine problems of foundational significance raised by that work, the paper concludes with a defense of reductive proof theory at a minimum as one of the principal means to lay out what rests on what in mathematics. In an extensive appendix to the paper,various reduction relations betweensystems are explained and compared, and arguments against proof-theoretic reduction as a ``good'' reducibilityrelation are taken up and rebutted. (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)

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)

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)

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.

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)

Though my ultimate concern is with issues in epistemology and metaphysics, let me phrase the central question I will pursue in terms evocative of philosophy of religion: What are the implications of our logic-in particular, of Cantor and G6del-for the possibility of omniscience?

It is argued that an instrumentalist notion of proof such as that represented in Hilbert's viewpoint is not obligated to satisfy the conservation condition that is generally regarded as a constraint on Hilbert's Program. A more reasonable soundness condition is then considered and shown not to be counter-exemplified by Godel's First Theorem. Finally, attention is given to the question of what a theory is; whether it should be seen as a "list" or corpus of beliefs, or as a method for (...) selecting beliefs. The significance of this question for assessing "intensional" results like Godel's Second Theorem, and their bearing on Hilbert's Program are discussed. (shrink)

We consider a seemingly popular justification (we call it the Re-flexivity Defense) for the third derivability condition of the Hilbert-Bernays-Löb generalization of Godel's Second Incompleteness Theorem (G2). We argue that (i) in certain settings (rouglily, those where the representing theory of an arithmetization is allowed to be a proper subtheory of the represented theory), use of the Reflexivity Defense to justify the tliird condition induces a fourth condition, and that (ii) the justification of this fourth condition faces serious obstacles. We (...) conclude that, in the types of settings mentioned, the Reflexivity Defense does not justify the usual ‘reading’ of G2—namely, that the consistency of the represented theory is not provable in the representing theory. (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.

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)

The alleged proof of the non-mechanical, or non-computational, character of the human mind based on Gödel’s incompleteness theorem is revisited. Its history is reviewed. The proof, also known as the Lucas argument and the Penrose argument, is refuted. It is claimed, following Gödel himself and other leading logicians, that antimechanism is not implied by Gödel’s theorems alone. The present paper sets out this refutation in its strongest form, demonstrating general theorems implying the inconsistency of Lucas’s arithmetic and the semantic inadequacy (...) of Penrose’s arithmetic. On the other hand, the limitations to our capacity for mechanizing or programming the mind are also indicated, together with two other corollaries of Gödel’s theorems: that we cannot prove that we are consistent, and that we cannot fully describe our notion of a natural number. (shrink)

In this paper, we investigate Rosser provability predicates whose provability logics are normal modal logics. First, we prove that there exists a Rosser provability predicate whose provability logic is exactly the normal modal logic \. Secondly, we introduce a new normal modal logic \ which is a proper extension of \, and prove that there exists a Rosser provability predicate whose provability logic includes \.

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)

It can be argued that only the equational theories of some sub-elementary function algebras are finitistic or intuitive according to a certain interpretation of Hilbert's conception of intuition. The purpose of this paper is to investigate the relation of those restricted forms of equational reasoning to classical quantifier logic in arithmetic. The conclusion reached is that Edward Nelson's ‘predicative arithmetic’ program, which makes essential use of classical quantifier logic, cannot be justified finitistically and thus requires a different philosophical foundation, possibly (...) as a restricted form of logicism. (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)

Solovay proved (Israel J Math 25(3–4):287–304, 1976) that the propositional provability logic of any ∑2-sound recursively enumerable extension of PA is characterized by the propositional modal logic GL. By contrast, Montagna proved in (Notre Dame J Form Log 25(2):179–189, 1984) that predicate provability logics of Peano arithmetic and Bernays–Gödel set theory are different. Moreover, Artemov proved in (Doklady Akademii Nauk SSSR 290(6):1289–1292, 1986) that the predicate provability logic of a theory essentially depends on the choice of a binumeration of the (...) theory which is used to construct the provability predicate. In this paper, we compare predicate provability logics of I∑ n ’s. For a binumeration α(x) of a recursive theory T, let PL α(T) be the predicate provability logic of T defined by α(x). We prove that for any natural numbers i, j such that 0 < i < j, there exists a ∑1 binumeration α(x) of some recursive axiomatization of I∑ i such that ${{\sf PL}_\alpha({\rm I \Sigma}_i) \nsupseteq \bigcap_{\beta(x)}{\sf PL}_\beta({\rm I \Sigma}_j)}$ and ${{\sf PL}_\alpha({\rm I \Sigma}_i) \nsubseteq \bigcup_{\beta(x)}{\sf PL}_\beta({\rm I \Sigma}_j)}$ , where β(x) ranges over all ∑1 binumerations of recursive axiomatizations of I∑ j. (shrink)

In a paper published in 1975, Robert Jeroslow introduced the concept of an experimental logic as a generalization of ordinary formal systems such that theoremhood is a (or in practice ) rather than . These systems can be viewed as (rather crude) representations of axiomatic theories evolving stepwise over time. Similar ideas can be found in papers by Putnam (1965) and McCarthy and Shapiro (1987). The topic of the present article is a discussion of a suggestion by Allen Hazen, that (...) these experimental logics might provide an illuminating way of representing “the human mathematical mind”. This is done in the context of the well-known Lucas-Penrose thesis. Though we agree that Jeroslow's model has some merit in this context, and that the Lucas-Penrose arguments certainly are less than persuasive, some semi-technical doubts are raised concerning the alleged impact of experimental logics on the question of knowable self-consistency. (shrink)

This paper deals with the modal logics associated with (possibly nonstandard) provability predicates of Peano Arithmetic. One of our goals is to present some modal systems having the fixed point property and not extending the Gödel-Löb system GL. We prove that, for every has the explicit fixed point property. Our main result states that every complete modal logic L having the Craig's interpolation property and such that , where and are suitable modal formulas, has the explicit fixed point property.

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.

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)

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)