§1. Overview. Philosophers and mathematicians have drawn lots of conclusions from Gödel's incompleteness theorems, and related results from mathematical logic. Languages, minds, and machines figure prominently in the discussion. Gödel's theorems surely tell us something about these important matters. But what?A descriptive title for this paper would be “Gödel, Lucas, Penrose, Turing, Feferman, Dummett, mechanism, optimism, reflection, and indefinite extensibility”. Adding “God and the Devil” would probably be redundant. Despite the breath-taking, whirlwind tour, I have the modest aim of forging (...) connections between different parts of this literature and clearing up some confusions, together with the less modest aim of not introducing any more confusions.I propose to focus on three spheres within the literature on incompleteness. The first, and primary, one concerns arguments that Gödel's theorem refutes the mechanistic thesis that the human mind is, or can be accurately modeled as, a digital computer or a Turing machine. The most famous instance is the much reprinted J. R. Lucas [18]. To summarize, suppose that a mechanist provides plans for a machine,M, and claims that the output ofMconsists of all and only the arithmetic truths that a human, or the totality of human mathematicians, will ever or can ever know. We assume that the output ofMis consistent. (shrink)

I survey some important semantical and axiomatic theories of self-referential truth. Kripke's fixed-point theory, the revision theory of truth and appraoches involving fuzzy logic are the main examples of semantical theories. I look at axiomatic theories devised by Cantini, Feferman, Freidman and Sheard. Finally some applications of the theory of self-referential truth are considered.

This paper propounds a systematic examination of the link between the Knower Paradox and provability interpretations of modal logic. The aim of the paper is threefold: to give a streamlined presentation of the Knower Paradox and related results; to clarify the notion of a syntactical treatment of modalities; finally, to discuss the kind of solution that modal provability logic provides to the Paradox. I discuss the respective strength of different versions of the Knower Paradox, both in the framework of first-order (...) arithmetic and in that of modal logic with fixed point operators. It is shown that the notion of a syntactical treatment of modalities is ambiguous between a self-referential treatment and a metalinguistic treatment of modalities, and that these two notions are independent. I survey and compare the provability interpretations of modality respectively given by Skyrms, B. (1978, The Journal of Philosophy 75: 368–387) Anderson, C.A. (1983, The Journal of Philosophy 80: 338–355) and Solovay, R. (1976, Israel Journal of Mathematics 25: 287–304). I examine how these interpretations enable us to bypass the limitations imposed by the Knower Paradox while preserving the laws of classical logic, each time by appeal to a distinct form of hierarchy. (shrink)

Soundness Arguments for the consistency of a (mathematical) theory S aim to show that S is consistent by first showing or employing the fact that S is sound, i.e., that all theorems of S are true. Although soundness arguments are virtually unanimously accepted as valid and sound for most of our accepted theories, philosophers disagree about their epistemic value, i.e., about whether such arguments can be employed to improve our epistemic situation concerning questions of consistency. This article provides a (partial) (...) negative answer to this question and argues that soundness arguments cannot be employed to justify their conclusion. Additionally, soundness arguments are unconvincing; they cannot be employed to overcome reasonable open-mindedness about their conclusion. (shrink)

The Geach‐Kaplan sentence is alleged to be an example of a non‐first‐orderizable sentence, and the proof of the alleged non‐first‐orderizability is credited to David Kaplan. However, there is also a widely shared intuition that the Geach‐Kaplan sentence is still first‐orderizable by invoking sets or other extra non‐logical resources. The plausibility of this intuition is particularly crucial for first‐orderism, namely, the thesis that all our scientific discourse and reasoning can be adequately formalized by first‐order logic. I first argue that the Geach‐Kaplan (...) sentence is, in fact, not first‐orderizable even by invoking extra non‐logical resources, in any sense that is acceptable for first‐orderism and adequately corresponds to the sense in which the Geach‐Kaplan sentence is deemed to be non‐first‐orderizable simpliciter via Kaplan's proof. To address this problem on behalf of first‐orderism, I then propose an alternative conception of first‐orderizability in the sense of which the Geach‐Kaplan sentence and any other second‐order sentences become first‐orderizable by invoking extra non‐logical resources; furthermore, in certain circumstances, they are first‐orderizable without incurring any extra ontological commitment. My analysis also turns out to yield (as a biproduct) a significant enhancement of the so‐called paradox of plurality. (shrink)

The aim of this paper is twofold: first, I provide a cluster of theories of truth in classical logic that is (internally) consistent with global reflection principles: the theories of positive truth (and falsity). After that, I analyse the _epistemic value_ of such theories. I do so employing the framework of cognitive projects introduced by Wright (Proc Aristot Soc 78:167–245, 2004), and employed—in the context of theories of truth—by Fischer et al. (Noûs 2019. https://doi.org/10.1111/nous.12292 ). In particular, I will argue (...) that theories of positive truth are _trustworthy_, analogously to the theories of full disquotational truth. Moreover, I argue that, for a given cognitive project, _if_ the acceptance of trustworthy theories is taken to be an _epistemic norm_ of cognitive project, then one has good reasons to accept theories of positive truth over other rival theories of truth in classical logic. On the other hand, the latter theories are deemed epistemically unacceptable. (shrink)

The notion of implicit commitment has played a prominent role in recent works in logic and philosophy of mathematics. Although implicit commitment is often associated with highly technical studies, it remains so far an elusive notion. In particular, it is often claimed that the acceptance of a mathematical theory implicitly commits one to the acceptance of a Uniform Reflection Principle for it. However, philosophers agree that a satisfactory analysis of the transition from a theory to its reflection principle is still (...) lacking. We provide an axiomatization of the minimal commitments implicit in the acceptance of a mathematical theory. The theory entails that the Uniform Reflection Principle is part of one's implicit commitments, and sheds light on the reason why this is so. We argue that the theory has interesting epistemological consequences in that it explains how justified belief in the axioms of a theory can be preserved to the corresponding reflection principle. The theory also improves on recent proposals for the analysis of implicit commitment based on truth or epistemic notions. (shrink)

Truth-theoretic deflationism holds that truth is simple, and yet that it can fulfil many useful logico-linguistic roles. Deflationism focuses on axioms for truth: there is no reduction of the notion of truth to more fundamental ones such as sets or higher-order quantifiers. In this paper I argue that the fundamental properties of reasonable, primitive truth predicates are at odds with the core tenets of classical truth-theoretic deflationism that I call fix, express, and quantify. Truth may be regarded as a broadly (...) logical, sui generis notion. However, this has little to do with the original aims of the deflationary theory of truth. (shrink)

What Bar-On and Simmons call 'Conceptual Deflationism' is the thesis that truth is a 'thin' concept in the sense that it is not suited to play any explanatory role in our scientific theorizing. One obvious place it might play such a role is in semantics, so disquotationalists have been widely concerned to argued that 'compositional principles', such as -/- (C) A conjunction is true iff its conjuncts are true -/- are ultimately quite trivial and, more generally, that semantic theorists have (...) misconceived the relation between truth, meaning, and logic. This paper argues, to the contrary, that even such simple compositional principles as (C) have substantial content that cannot be captured by deflationist 'proofs' of them. The key thought is that (C) is supposed, among other things, to affirm the truth-functionality of conjunction and that disquotationalists cannot, ultimately, make sense of truth-functionality. -/- This paper is something of a companion to "The Logical Strength of Compositional Principles". (shrink)

Beall and Murzi :143–165, 2013) introduce an object-linguistic predicate for naïve validity, governed by intuitive principles that are inconsistent with the classical structural rules. As a consequence, they suggest that revisionary approaches to semantic paradox must be substructural. In response to Beall and Murzi, Field :1–19, 2017) has argued that naïve validity principles do not admit of a coherent reading and that, for this reason, a non-classical solution to the semantic paradoxes need not be substructural. The aim of this paper (...) is to respond to Field’s objections and to point to a coherent notion of validity which underwrites a coherent reading of Beall and Murzi’s principles: grounded validity. The notion, first introduced by Nicolai and Rossi, is a generalisation of Kripke’s notion of grounded truth, and yields an irreflexive logic. While we do not advocate the adoption of a substructural logic, we take the notion of naïve validity to be a legitimate semantic notion that points to genuine expressive limitations of fully structural revisionary approaches. (shrink)

Even though disquotationalism is not correct as it is usually formulated, a deep insight lies behind it. Specifically, it can be argued that, modulo implicit commitment to reflection principles, all there is to the notion of truth is given by a simple, natural collection of truth-biconditionals.

In his book Shadows of the Mind: A search for the missing science of con- sciousness [SM below], Roger Penrose has turned in another bravura perfor- mance, the kind we have come to expect ever since The Emperor’s New Mind [ENM ] appeared. In the service of advancing his deep convictions and daring conjectures about the nature of human thought and consciousness, Penrose has once more drawn a wide swath through such topics as logic, computa- tion, artificial intelligence, quantum physics (...) and the neuro-physiology of the brain, and has produced along the way many gems of exposition of difficult mathematical and scientific ideas, without condescension, yet which should be broadly appealing. 1 While the aims and a number of the topics in SM are the same as in ENM, the focus now is much more on the two axes that Pen- rose grinds in earnest. Namely, in the first part of SM he argues anew and at great length against computational models of the mind and more specifi- cally against any account of mathematical thought in computational terms. Then in the second part, he argues that there must be a scientific account of consciousness but that will require a (still to be found) non-computational extension or modification of present-day quantum physics. (shrink)

We study the arithmetical schema asserting that every eventually decreasing elementary recursive function has a limit. Some other related principles are also formulated. We establish their relationship with restricted parameter-free induction schemata. We also prove that the same principle, formulated as an inference rule, provides an axiomatization of the Σ2-consequences of IΣ1.Using these results we show that ILM is the logic of Π1-conservativity of any reasonable extension of parameter-free Π1-induction schema. This result, however, cannot be much improved: by adapting a (...) theorem of D. Zambella and G. Mints we show that the logic of Π1-conservativity of primitive recursive arithmetic properly extends ILM.In the third part of the paper we give an ordinal classification of -consequences of the standard fragments of Peano arithmetic in terms of reflection principles. This is interesting in view of the general program of ordinal analysis of theories, which in the most standard cases classifies Π-classes of sentences. (shrink)

Gödel's two incompleteness theorems are among the most important results in modern logic, and have deep implications for various issues. They concern the limits of provability in formal axiomatic theories. The first incompleteness theorem states that in any consistent formal system F within which a certain amount of arithmetic can be carried out, there are statements of the language of F which can neither be proved nor disproved in F. According to the second incompleteness theorem, such a formal system cannot (...) prove that the system itself is consistent (assuming it is indeed consistent). These results have had a great impact on the philosophy of mathematics and logic. There have been attempts to apply the results also in other areas of philosophy such as the philosophy of mind, but these attempted applications are more controversial. The present entry surveys the two incompleteness theorems and various issues surrounding them. (shrink)

This article studies three most basic systems of truth as well as their subsystems over set theory ZF possibly with AC or the axiom of global choice GC, and then correlates them with subsystems of Morse–Kelley class theory MK. The article aims at making an initial step towards the axiomatic study of truth in set theory in connection with class theory. Some new results on the side of class theory, such as conservativity, forcing and some forms of the reflection principle, (...) are also presented. The equivalence results among systems of truth and classes obtained in this article are summarized in Theorem 104 , Theorem 107 and Theorem 108. (shrink)

From 1931 until late in his life (at least 1970) Godel called for the pursuit of new axioms for mathematics to settle both undecided number-theoretical propositions (of the form obtained in his incompleteness results) and undecided set-theoretical propositions (in particular CH). As to the nature of these, Godel made a variety of suggestions, but most frequently he emphasized the route of introducing ever higher axioms of in nity. In particular, he speculated (in his 1946 Princeton remarks) that there might be (...) a uniform (though non-decidable) rationale for the choice of the latter. Despite the intense exploration of the \higher in nite" in the last 30-odd years, no single rationale of that character has emerged. Moreover, CH still remains undecided by such axioms, though they have been demonstrated to have many other interesting set-theoretical consequences. (shrink)

Definitional and axiomatic theories of truth -- Objects of truth -- Tarski -- Truth and set theory -- Technical preliminaries -- Comparing axiomatic theories of truth -- Disquotation -- Classical compositional truth -- Hierarchies -- Typed and type-free theories of truth -- Reasons against typing -- Axioms and rules -- Axioms for type-free truth -- Classical symmetric truth -- Kripke-Feferman -- Axiomatizing Kripke's theory in partial logic -- Grounded truth -- Alternative evaluation schemata -- Disquotation -- Classical logic -- Deflationism (...) -- Reflection -- Ontological reduction -- Applying theories of truth. (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)

It has been argued, by Penrose and others, that Gödel's proof of his first incompleteness theorem shows that human mathematics cannot be captured by a formal system F: the Gödel sentence G(F) of F can be proved by a (human) mathematician but is not provable in F. To this argment it has been objected that the mathematician can prove G(F) only if (s)he can prove that F is consistent, which is unlikely if F is complicated. Penrose has invented a new (...) argument intended to avoid this objection. In the paper I try to show that Penrose's new argument is inconclusive. (shrink)

Philosophy and Phenomenological Research, EarlyView.

Gödel argued that the incompleteness theorems entail that the mind is not a machine, or that certain arithmetical propositions are absolutely undecidable. His view was that the mind is not a machine, and that no arithmetical propositions are absolutely undecidable. I argue that his position presupposes that the idealized mathematician has an ability which I call the recursive-ordinal recognition ability. I show that we have this ability if, and only if, there are no absolutely undecidable arithmetical propositions. I argue that (...) there are such propositions, but that no recognizable example of one can be identified, even in principle. (shrink)

The notion of implicit commitment has played a prominent role in recent works in logic and philosophy of mathematics. Although implicit commitment is often associated with highly technical studies, it remains an elusive notion. In particular, it is often claimed that the acceptance of a mathematical theory implicitly commits one to the acceptance of a Uniform Reflection Principle for it. However, philosophers agree that a satisfactory analysis of the transition from a theory to its reflection principle is still lacking. We (...) provide an axiomatization of the minimal commitments implicit in the acceptance of a mathematical theory. The theory entails that the Uniform Reflection Principle is part of one’s implicit commitments, and sheds light on why this is so. We argue that the theory has significant epistemological consequences in that it explains how justified belief in the axioms of a theory can be preserved to the corresponding reflection principle. The theory also improves on recent analyses of implicit commitment based on truth or epistemic notions. (shrink)

There has been a recent interest in hierarchical generalizations of classic incompleteness results. This paper provides evidence that such generalizations are readily obtainable from suitably formulated hierarchical versions of the principles used in the original proofs. By collecting such principles, we prove hierarchical versions of Mostowski’s theorem on independent formulae, Kripke’s theorem on flexible formulae, Woodin’s theorem on the universal algorithm, and a few related results. As a corollary, we obtain the expected result that the formula expressing “$\mathrm {T}$is$\Sigma _n$-ill” (...) is a canonical example of a$\Sigma _{n+1}$formula that is$\Pi _{n+1}$-conservative over$\mathrm {T}$. (shrink)

Reflection principles are of central interest in the development of axiomatic theories. Whereas they are independent statements they appear to have a specific epistemological status. Our trust in those principles is as warranted as our trust in the axioms of the system itself. This paper is an attempt in clarifying this special epistemic status. We provide a motivation for the adoption of uniform reflection principles by their analogy to a form of the constructive \(\omega \) -rule. Additionally, we analyse the (...) role of informal arithmetic and the conception of natural numbers as an inductive structure, also with regard to extra conceptual resources such as a primitive truth predicate. (shrink)

Recent work on formal theories of truth has revived an approach, due originally to Tarski, on which syntax and truth theories are sharply distinguished—‘disentangled’—from mathematical base theories. In this paper, we defend a novel philosophical constraint on disentangled theories. We argue that these theories must be epistemically stable: they must possess an intrinsic motivation justifying no strictly stronger theory. In a disentangled setting, even if the base and the syntax theory are individually stable, they may be jointly unstable. We contend (...) that this flaw afflicts many proposals discussed in the literature; we defend a new, stable disentangled theory, double second-order arithmetic. (shrink)

We give a survey of current research on Gödel’s incompleteness theorems from the following three aspects: classifications of different proofs of Gödel’s incompleteness theorems, the limit of the applicability of Gödel’s first incompleteness theorem, and the limit of the applicability of Gödel’s second incompleteness theorem.

In this note we study several topics related to the schema of local reflection \\) and its partial and relativized variants. Firstly, we introduce the principle of uniform reflection with \-definable parameters, establish its relationship with relativized local reflection principles and corresponding versions of induction with definable parameters. Using this schema we give a new model-theoretic proof of the \-conservativity of uniform \-reflection over relativized local \-reflection. We also study the proof-theoretic strength of Feferman’s theorem, i.e., the assertion of 1-provability (...) in S of the local reflection schema \\), and its generalized versions. We relate this assertion to the uniform \-reflection schema and, in particular, obtain an alternative axiomatization of \. (shrink)

Shoenfield’s completeness theorem states that every true first order arithmetical sentence has a recursive \-proof encodable by using recursive applications of the \-rule. For a suitable encoding of Gentzen style \-proofs, we show that Shoenfield’s completeness theorem applies to cut free \-proofs encodable by using primitive recursive applications of the \-rule. We also show that the set of codes of \-proofs, whether it is based on recursive or primitive recursive applications of the \-rule, is \ complete. The same \ completeness (...) results apply to codes of cut free \-proofs. (shrink)

Deflationists argue that ‘true’ is merely a logico-linguistic device for expressing blind ascriptions and infinite generalisations. For this reason, some authors have argued that deflationary truth must be conservative, i.e. that a deflationary theory of truth for a theory S must not entail sentences in S’s language that are not already entailed by S. However, it has been forcefully argued that any adequate theory of truth for S must be non-conservative and that, for this reason, truth cannot be deflationary :493–521, (...) 1998; Ketland in Mind 108:69–94, 1999). We consider two defences of conservative deflationism, respectively proposed by Waxman :429–463, 2017) and Tennant :551–582, 2002), and argue that they are both unsuccessful. In Waxman’s hands, deflationists are committed either to a non-purely expressive notion of truth, or to a conception of mathematics that does not allow them to justifiably exclude non-conservative theories of truth. Tennant’s conservative deflationism fares no better: if deflationist truth must be conservative over arithmetic, it can be shown to collapse into a non-conservative variety of deflationism. (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)

Guided by questions of scope, this paper provides an overview of what is known about both the scope and, consequently, the limits of Gödel’s famous first incompleteness theorem.

Ratajczyk, Z., Subsystems of true arithmetic and hierarchies of functions, Annals of Pure and Applied Logic 64 95–152. The combinatorial method coming from the study of combinatorial sentences independent of PA is developed. Basing on this method we present the detailed analysis of provably recursive functions associated with higher levels of transfinite induction, I, and analyze combinatorial sentences independent of I. Our treatment of combinatorial sentences differs from the one given by McAloon [18] and gives more natural sentences. The same (...) method give also a combinatorial technique with no use of the cut-elimination theorem which is appropriate to study proof-theoretic strength of subsystems of first order arithmetic and some of their expansions. It was used to analyze iterated reflection principle and system of transfinite induction with a satisfaction class. (shrink)

For “natural enough” systems of ordinal notation we show that α times iterated local reflection schema over a sufficiently strong arithmetic T proves the same Π 1 0 -sentences as ω α times iterated consistency. A corollary is that the two hierarchies catch up modulo relative interpretability exactly at ε-numbers. We also derive the following more general “mixed” formulas estimating the consistency strength of iterated local reflection: for all ordinals α ⩾ 1 and all β, β ≡ Π 1 0 (...) T ω α · , α ≡ Π 1 0 T β + ω α . Here T α stands for α times iterated local reflection over T , T β stands for β times iterated consistency, and ≡ Π 1 0 denotes mutual Π 1 0 -conservativity. In an appendix to this paper we develop our notion of “natural enough” system of ordinal notation and show that such systems do exist for every recursive ordinal. (shrink)

The relative strengths of first-order theories axiomatized by transfinite induction, for ordinals less-than 0, and formulas restricted in quantifier complexity, is determined. This is done, in part, by describing the provably recursive functions of such theories. Upper bounds for the provably recursive functions are obtained using model-theoretic techniques. A variety of additional results that come as an application of such techniques are mentioned.

We examine what happens if we replace ZFC with a localistic/relativistic system, LZFC, whose central new axiom, denoted by Loc(ZFC), says that every set belongs to a transitive model of ZFC. LZFC consists of Loc(ZFC) plus some elementary axioms forming Basic Set Theory (BST). Some theoretical reasons for this shift of view are given. All ${\Pi_2}$ consequences of ZFC are provable in LZFC. LZFC strongly extends Kripke-Platek (KP) set theory minus Δ0-Collection and minus ${\in}$ -induction scheme. ZFC+ “there is an (...) inaccessible cardinal” proves the consistency of LZFC. In LZFC we focus on models rather than cardinals, a transitive model being considered as the analogue of an inaccessible cardinal. Pushing this analogy further we define α-Mahlo models and ${\Pi_1^1}$ -indescribable models, the latter being the analogues of weakly compact cardinals. Also localization axioms of the form ${Loc({\rm ZFC}+\phi)}$ are considered and their global consequences are examined. Finally we introduce the concept of standard compact cardinal (in ZFC) and some standard compactness results are proved. (shrink)

Solovay proved the arithmetical completeness theorem for the system GL of propositional modal logic of provability. Montagna proved that this completeness does not hold for a natural extension QGL of GL to the predicate modal logic. Let Th(QGL) be the set of all theorems of QGL, Fr(QGL) be the set of all formulas valid in all transitive and conversely well-founded Kripke frames, and let PL(T) be the set of all predicate modal formulas provable in Tfor any arithmetical interpretation. Montagna’s results (...) are described as Th(QGL) ⊊ (Fr(QGL), PL(PA) ⊈ Fr(QGL), and Th(QGL) ⊊ PL(PA). In this paper, we prove the following three theorems: (1) Fr(QGL) ⊈ PL(T) for any Σ1-sound recursively enumerable extension T of I Σ1, (2) PL(T) ⊈ Fr(QGL) for any recursively enumerable S1755020312000275_inline1 A -theory T extending I Σ1, and (3) Th(QGL) ⊊ Fr(QGL) ∩ PL(T) for any recursively enumerable S1755020312000275_inline2 A -theory T extending I Σ2. To prove these theorems, we use iterated consistency assertions and nonstandard models of arithmetic, and we improve Artemov’s lemma which is used to prove Vardanyan’s theorem on the Π0 2-completeness of PL(T). (shrink)

The notion of strictly primitive recursive realizability is further investigated, and the realizable prenex sentences, which coincide with primitive recursive truths of classical arithmetic, are characterized as precisely those provable in transfinite progressions over a fragment of intuitionistic arithmetic. The progressions are based on uniform reflection principles of bounded complexity iterated along initial segments of a primitive recursively formulated system of notations for constructive ordinals. A semiformal system closed under a primitive recursively restricted -rule is described and proved equivalent to (...) the transfinite progressions with respect to the prenex sentences. (shrink)

In this paper I would like to indicate that this interpretation of Gödel goes far beyond what he really proved. I would like to show that to get from his result to a conclusion of the above kind requires a train of thought which is fuelled by much more than Gödel's result itself, and that a great deal of the excessive fuel should be utilized with an extra care.

When I was a teenager growing up in Los Angeles in the early 1940s, my dream was to become a mathematical physicist: I was fascinated by the ideas of relativity theory and quantum mechanics, and I read popular expositions which, in those days, besides Einstein’s The Meaning of Relativity, was limited to books by the likes of Arthur S. Eddington and James Jeans. I breezed through the high-school mathematics courses (calculus was not then on offer, and my teachers barely understood (...) it), but did less well in physics, which I should have taken as a reality check. On the philosophical side I read a mixed bag of Bertrand Russell, John Dewey and Alfred Korzybski (the missionary for “General Semantics” in Science and Sanity, a mish-mash of the theory of types, non-. (shrink)

The proof-theoretic results on axiomatic theories oftruth obtained by different authors in recent years are surveyed.In particular, the theories of truth are related to subsystems ofsecond-order analysis. On the basis of these results, thesuitability of axiomatic theories of truth for ontologicalreduction is evaluated.

This article presents Tarski's Address at the Princeton Bicentennial Conference on Problems of Mathematics, together with a separate summary. Two accounts of the discussion which followed are also included. The central topic of the Address and of the discussion is decision problems. The introductory note gives information about the Conference, about the background of the subjects discussed in the Address, and about subsequent developments to these subjects.

A theory T is tight if different deductively closed extensions of T (in the same language) cannot be bi-interpretable. Many well-studied foundational theories are tight, including $\mathsf {PA}$ [39], $\mathsf {ZF}$, $\mathsf {Z}_2$, and $\mathsf {KM}$ [6]. In this article we extend Enayat’s investigations to subsystems of these latter two theories. We prove that restricting the Comprehension schema of $\mathsf {Z}_2$ and $\mathsf {KM}$ gives non-tight theories. Specifically, we show that $\mathsf {GB}$ and $\mathsf {ACA}_0$ each admit different bi-interpretable extensions, (...) and the same holds for their extensions by adding $\Sigma ^1_k$ -Comprehension, for $k \ge 1$. These results provide evidence that tightness characterizes $\mathsf {Z}_2$ and $\mathsf {KM}$ in a minimal way. (shrink)

We consider fragments of uniform reflection for formulas in the analytic hierarchy over theories of second order arithmetic. The main result is that for any second order arithmetic theory $T_0$ extending $\mathsf {RCA}_0$ and axiomatizable by a $\Pi ^1_{k+2}$ sentence, and for any $n\geq k+1$, $$\begin{align*}T_0+ \mathrm{RFN}_{\varPi^1_{n+2}} \ = \ T_0 + \mathrm{TI}_{\varPi^1_n}, \end{align*}$$ $$\begin{align*}T_0+ \mathrm{RFN}_{\varSigma^1_{n+1}} \ = \ T_0+ \mathrm{TI}_{\varPi^1_n}^{-}, \end{align*}$$ where T is $T_0$ augmented with full induction, and $\mathrm {TI}_{\varPi ^1_n}^{-}$ denotes the schema of transfinite induction up (...) to $\varepsilon _0$ for $\varPi ^1_n$ formulas without set parameters. (shrink)

Journal of Mathematical Logic, Volume 23, Issue 02, August 2023. In mathematical logic there are two seemingly distinct kinds of principles called “reflection principles.” Semantic reflection principles assert that if a formula holds in the whole universe, then it holds in a set-sized model. Syntactic reflection principles assert that every provable sentence from some complexity class is true. In this paper, we study connections between these two kinds of reflection principles in the setting of second-order arithmetic. We prove that, for (...) a large swathe of theories, [math]-model reflection is equivalent to the claim that arbitrary iterations of uniform [math] reflection along countable well-orderings are [math]-sound. This result yields uniform ordinal analyzes of theories with strength between [math] and [math]. The main technical novelty of our analysis is the introduction of the notion of the proof-theoretic dilator of a theory [math], which is the operator on countable ordinals that maps the order-type of [math] to the proof-theoretic ordinal of [math]. We obtain precise results about the growth of proof-theoretic dilators as a function of provable [math]-model reflection. This approach enables us to simultaneously obtain not only [math], [math] and [math] ordinals but also reverse-mathematical theorems for well-ordering principles. (shrink)