In this paper I have considered various attempts to attribute significance to Gödel's second incompleteness theorem (G2 for short). Two of these attempts (Beth-Cohen and the position maintaining that G2 shows the failure of Hilbert's Program), I have argued, are false. Two others (an argument suggested by Beth, Cohen and ??? and Resnik's Interpretation), I argue, are groundless.

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)

The prevalent interpretation of Gödel’s Second Theorem states that a sufficiently adequate and consistent theory does not prove its consistency. It is however not entirely clear how to justify this informal reading, as the formulation of the underlying mathematical theorem depends on several arbitrary formalisation choices. In this paper I examine the theorem’s dependency regarding Gödel numberings. I introducedeviantnumberings, yielding provability predicates satisfying Löb’s conditions, which result in provable consistency sentences. According to the main result of (...) this paper however, these “counterexamples” do not refute the theorem’s prevalent interpretation, since once a natural class ofadmissiblenumberings is singled out, invariance is maintained. (shrink)

According to a common view, belief in God cannot be proved and is an issue that must be left to faith. Kant went even further and argued that he can prove this unprovability. But any argument implying that a certain sentence is not provable is challenged by Gödel’s second theorem. Indeed, one trivial consequence of GST is that for any formal system F that satisfies certain conditions and for every sentence K that is formulated in F it is (...) impossible to prove, from F, that K is not provable. In the article, I explore the general issue of proving the unprovability of the existence of God. Of special interest is the question of the relation between the existence of God and the conditions that F must satisfy in order to allow for its subjection to GST. (shrink)

This episode introduces the Second Incompleteness Theorem, says something about what it takes to prove it, and why it matters. Just two very quick reminders before we start. We said..

In several publications, Juliet Floyd and Hilary Putnam have argued that the so-called ‘notorious paragraph’ of the Remarks on the Foundations of Mathematics contains a valuable philosophical insight about Gödel’s informal proof of the first incompleteness theorem – in a nutshell, the idea they attribute to Wittgenstein is that if the Gödel sentence of a system is refutable, then, because of the resulting ω-inconsistency of the system, we should give up the translation of Gödel’s sentence by the English sentence (...) “I am unprovable”.I will argue against Floyd and Putnam’s use of the idea, and I will indirectly question its attribution to Wittgenstein. First, I will point out that the idea is inefficient in the context of the first incompleteness theorem because there is an explicit assumption of soundness in Gödel’s informal discussion of that theorem. Secondly, I will argue that of he who makes the observation that Floyd and Putnam think Wittgenstein has made about the first theorem, one will expect to see an analogous observation about Gödel’s second incompleteness theorem – yet we see nothing to that effect in Wittgenstein’s remarks. Incidentally, that never-made remark on the import of the second theorem is of genuine logical significance.‏. (shrink)

While Gödel’s first theorem remains valid under substitution of various provability predicates, Gödel’s second theorem does not. This is one reason to label G1 as “extensional” but to call G2 “intensional.” Although this asymmetry between G1 and G2 is known for long, no satisfying account of G2’s intensionality has been put forward. After briefly reviewing the discussion so far, the paper presents a new analysis based on two observations. First, the underestimated role of provable closure under modus. (...) Provable closure under modus ponens—usually listed as the second derivability condition—or similar requirements, do not get much attention since their proof isn’t perceived as much of challenge. Closer inspection shows, however, that the requirement of provable closure under modus ponens interacts differently with different formalized proof predicates and has thus a direct bearing on the discussion of G2’s intensionality. Second, in order to establish the co-extensionality of various proof predicates and hence the extensionality of G1, the role informal consistency assumption play goes largely unnoticed and unanalyzed. Closer inspection shows, however, that if such informal consistency assumptions are being made precise, the former distinction between G1 and G2 becomes blurry and G2’s intensionality can be made go away. Both observation then support the thesis that the traditional extensional/intensional distinction is not as robust as the received view believed it to be. (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)

The consistency of a second-order version of Morley’s Theorem on the number of countable models was proved in [EHMT23] with the aid of large cardinals. We here dispense with them.

We discuss the probabilistic analysis of explanatory power and prove a representation theorem for posterior ratio measures recently advocated by Schupbach and Sprenger. We then prove a representation theorem for an alternative class of measures that rely on the notion of relative probability distance. We end up endorsing the latter, as relative distance measures share the properties of posterior ratio measures that are genuinely appealing, while overcoming a feature that we consider undesirable. They also yield a telling result (...) concerning formal accounts of explanatory power versus inductive confirmation, thereby bridging our discussion to a so-called no-miracle argument. (shrink)

We introduce a second-order system V1-Horn of bounded arithmetic formalizing polynomial-time reasoning, based on Grädel's 35) second-order Horn characterization of P. Our system has comprehension over P predicates , and only finitely many function symbols. Other systems of polynomial-time reasoning either allow induction on NP predicates , and hence are more powerful than our system , or use Cobham's theorem to introduce function symbols for all polynomial-time functions . We prove that our system is equivalent to QPV (...) and Zambella's P-def. Using our techniques, we also show that V1-Horn is finitely axiomatizable, and, as a corollary, that the class of Σ1b consequences of S21 is finitely axiomatizable as well, thus answering an open question. (shrink)

In this paper, we introduce systems of nonstandard second-order arithmetic which are conservative extensions of systems of second-order arithmetic. Within these systems, we do reverse mathematics for nonstandard analysis, and we can import techniques of nonstandard analysis into analysis in weak systems of second-order arithmetic. Then, we apply nonstandard techniques to a version of Riemannʼs mapping theorem, and show several different versions of Riemannʼs mapping theorem.

Differential equations of second order appear in physical applications such as fluid dynamics, electromagnetism, acoustic vibrations, and quantum mechanics. In this paper, necessary and sufficient conditions are established of the solutions to second-order half-linear delay differential equations of the form ς y u ′ y a ′ + ∑ j = 1 m p j y u c j ϑ j y = 0 for y ≥ y 0, under the assumption ∫ ∞ ς η − 1 / (...) a d η = ∞. We consider two cases when a c j, where a and c j are the quotient of two positive odd integers. Two examples are given to show effectiveness and applicability of the result. (shrink)

The proofs of Gödel (1931), Rosser (1936), Kleene (first 1936 and second 1950), Chaitin (1970), and Boolos (1989) for the first incompleteness theorem are compared with each other, especially from the viewpoint of the second incompleteness theorem. It is shown that Gödel’s (first incompleteness theorem) and Kleene’s first theorems are equivalent with the second incompleteness theorem, Rosser’s and Kleene’s second theorems do deliver the second incompleteness theorem, and Boolos’ theorem (...) is derived from the second incompleteness theorem in the standard way. It is also shown that none of Rosser’s, Kleene’s second or Boolos’ theorems is equivalent with the second incompleteness theorem, and Chaitin’s incompleteness theorem neither delivers nor is derived from the second incompleteness theorem. We compare (the strength of) these six proofs with one another. (shrink)

In this paper, we show within ${\mathsf{RCA}_0}$ that both the Jordan curve theorem and the Schönflies theorem are equivalent to weak König’s lemma. Within ${\mathsf {WKL}_0}$ , we prove the Jordan curve theorem using an argument of non-standard analysis based on the fact that every countable non-standard model of ${\mathsf {WKL}_0}$ has a proper initial part that is isomorphic to itself (Tanaka in Math Logic Q 43:396–400, 1997).

Yu, X., Riesz representation theorem, Borel measures and subsystems of second-order arithmetic, Annals of Pure and Applied Logic 59 65-78. Formalized concept of finite Borel measures is developed in the language of second-order arithmetic. Formalization of the Riesz representation theorem is proved to be equivalent to arithmetical comprehension. Codes of Borel sets of complete separable metric spaces are defined and proved to be meaningful in the subsystem ATR0. Arithmetical transfinite recursion is enough to prove the measurability (...) of Borel sets for any finite Borel measure on a compact complete separable metric space. (shrink)

In the Lambek calculus of order 2 we allow only sequents in which the depth of nesting of implications is limited to 2. We prove that the decision problem of provability in the calculus can be solved in time polynomial in the length of the sequent. A normal form for proofs of second order sequents is defined. It is shown that for every proof there is a normal form proof with the same axioms. With this normal form we can (...) give an algorithm that decides provability of sequents in polynomial time. (shrink)

In this paper we study proofs of some general forms of the Second Incompleteness Theorem. These forms conform to the Feferman format, where the proof predicate is fixed and the representation of the set of axioms varies. We extend the Feferman framework in one important point: we allow the interpretation of number theory to vary.

We shall prove the second incompleteness theorem via Kolmogorov complexity.

This paper will introduce the notion of a naming convention and use this paradigm to both develop a new version of the Second Incompleteness Theorem and to describe when an axiom system can partially evade the Second Incompleteness Theorem.

Hindman's Theorem is a prototypical example of a combinatorial theorem with a proof that uses the topology of the ultrafilters. We show how the methods of this proof, including topological arguments about ultrafilters, can be translated into second order arithmetic.

By RCA 0 , we denote a subsystem of second order arithmetic based on Δ0 1 comprehension and Δ0 1 induction. We show within this system that the real number system R satisfies all the theorems (possibly with non-standard length) of the theory of real closed fields under an appropriate truth definition. This enables us to develop linear algebra and polynomial ring theory over real and complex numbers, so that we particularly obtain Hilbert’s Nullstellensatz in RCA 0.

We show that the maximal linear extension theorem for well partial orders is equivalent over RCA0 to ATR0. Analogously, the maximal chain theorem for well partial orders is equivalent to ATR0 over RCA0.

Working within weak subsystems of second-order arithmetic Z2 we consider two versions of the Baire Category theorem which are not equivalent over the base system RCA0. We show that one version (B.C.T.I) is provable in RCA0 while the second version (B.C.T.II) requires a stronger system. We introduce two new subsystems of Z2, which we call RCA+ 0 and WKL+ 0, and show that RCA+ 0 suffices to prove B.C.T.II. Some model theory of WKL+ 0 and its importance (...) in view of Hilbert's program is discussed, as well as applications of our results to functional analysis. (shrink)

This little gem is stated unbilled and proved in the last two lines of §2 of the short note Kleene [1938]. In modern notation, with all the hypotheses stated explicitly and in a strong form, it reads as follows:Second Recursion Theorem. Fix a set V ⊆ ℕ, and suppose that for each natural number n ϵ ℕ = {0, 1, 2, …}, φn: ℕ1+n ⇀ V is a recursive partial function of arguments with values in V so that (...) the standard assumptions and hold with. Every n-ary recursive partial function with values in V is for some e. For all m, n, there is a recursive function : Nm+1 → ℕ such that.Then, for every recursive, partial function f of arguments with values in V, there is a total recursive function of m arguments such thatProof. Fix e ϵ ℕ such that and let.We will abuse notation and write ž; rather than ž() when m = 0, so that takes the simpler formin this case ). (shrink)

The pointwise ergodic theorem is nonconstructive. In this paper, we examine origins of this non-constructivity, and determine the logical strength of the theorem and of the auxiliary statements used to prove it. We discuss properties of integrable functions and of measure preserving transformations and give three proofs of the theorem, though mostly focusing on the one derived from the mean ergodic theorem. All the proofs can be carried out in ACA₀; moreover, the pointwise ergodic theorem (...) is equivalent to (ACA) over the base theory RCA₀. (shrink)

Slides for the third tutorial on Gödel's incompleteness theorems, held at UniLog 5 Summer School, Istanbul, June 24, 2015.

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)

Let us recall that Raphael Robinson's Arithmetic Q is an axiom system that differs from Peano Arithmetic essentially by containing no Induction axioms [13], [18]. We will generalize the semantic-tableaux version of the Second Incompleteness Theorem almost to the level of System Q. We will prove that there exists a single rather long Π 1 sentence, valid in the standard model of the Natural Numbers and denoted as V, such that if α is any finite consistent extension of (...) Q + V then α will be unable to prove its Semantic Tableaux consistency. The same result will also apply to axiom systems α with infinite cardinality when these infinite-sized axiom systems satisfy a minor additional constraint, called the Conventional Encoding Property. Our formalism will also imply that the semantic-tableaux version of the Second Incompleteness Theorem generalizes for the axiom system IΣ 0 , as well as for all its natural extensions. (This answers an open question raised twenty years ago by Paris and Wilkie [15].). (shrink)

Representation theorems are often taken to provide the foundations for decision theory. First, they are taken to characterize degrees of belief and utilities. Second, they are taken to justify two fundamental rules of rationality: that we should have probabilistic degrees of belief and that we should act as expected utility maximizers. We argue that representation theorems cannot serve either of these foundational purposes, and that recent attempts to defend the foundational importance of representation theorems are unsuccessful. As a result, (...) we should reject these claims, and lay the foundations of decision theory on firmer ground. (shrink)

We examine second order intuitionistic propositional logic, IPC². Let $F_\exists $ be the set of formulas with no universal quantification. We prove Glivenko's theorem for formulas in $F_\exists $ that is, for φ € $F_\exists $ φ is a classical tautology if and only if ¬¬φ is a tautology of IPC². We show that for each sentence φ € $F_\exists $ (without free variables), φ is a classical tautology if and only if φ is an intuitionistic tautology. As (...) a corollary we obtain a semantic argument that the quantifier V is not definable in IPC² from ⊥, V, ^, →. (shrink)

We prove that any 1-closed (see def 1.1) model of the Π 2 consequences of PA satisfies ¬Cons PA which gives a proof of the second Godel incompleteness theorem without the use of the Godel diagonal lemma. We prove a few other theorems by the same method.

Theorems of hyperarithmetic analysis occupy an unusual neighborhood in the realms of reverse mathematics and recursion-theoretic complexity. They lie above all the fixed iterations of the Turing jump but below ATR $_{0}$. There is a long history of proof-theoretic principles which are THAs. Until the papers reported on in this communication, there was only one mathematical example. Barnes, Goh, and Shore [1] analyze an array of ubiquity theorems in graph theory descended from Halin’s [9] work on rays in graphs. They (...) seem to be typical applications of ACA $_{0}$ but are actually THAs. These results answer Question 30 of Montalbán’s Open Questions in Reverse Mathematics [19] and supply several other natural principles of different and unusual levels of complexity.This work led in [25] to a new neighborhood of the reverse mathematical zoo: almost theorems of hyperarithmetic analysis. When combined with ACA $_{0}$ they are THAs but on their own are very weak. Denizens both mathematical and logical are provided. Generalizations of several conservativity classes are defined and these ATHAs as well as many other principles are shown to be conservative over RCA $_{0}$ in all these senses and weak in other recursion-theoretic ways as well. These results answer a question raised by Hirschfeldt and reported in [19] by providing a long list of pairs of principles one of which is very weak over RCA $_{0}$ but over ACA $_{0}$ is equivalent to the other which may be strong or very strong going up a standard hierarchy and at the end being stronger than full second-order arithmetic. (shrink)

Informal statements of Gödel's Second Incompleteness Theorem, referred to here as Informal Second Incompleteness, are simple and dramatic. However, current versions of Formal Second Incompleteness are complicated and awkward. We present new versions of Formal Second Incompleteness that are simple, and informally imply Informal Second Incompleteness. These results rest on the isolation of simple formal properties shared by consistency statements. Here we do not address any issues concerning proofs of Second Incompleteness.

We study definability of second order generalized quantifiers on finite structures. Our main result says that for every second order type t there exists a second order generalized quantifier of type t which is not definable in the extension of second order logic by all second order generalized quantifiers of types lower than t.