The proofs of Kleene, Chaitin and Boolos for Gödel's First Incompleteness Theorem are studied from the perspectives of constructivity and the Rosser property. A proof of the incompleteness theorem has the Rosser property when the independence of the true but unprovable sentence can be shown by assuming only the (simple) consistency of the theory. It is known that Gödel's own proof for his incompleteness theorem does not have the Rosser property, and we show that neither do Kleene's or Boolos' proofs. (...) However, we show that a variant of Chaitin's proof can have the Rosser property. The proofs of Gödel, Rosser and Kleene are constructive in the sense that they explicitly construct, by algorithmic ways, the independent sentence(s) from the theory. We show that the proofs of Chaitin and Boolos are not constructive, and they prove only the mere existence of the independent sentences. (shrink)

The shortest definition of a number by a first order formula with one free variable, where the notion of a formula defining a number extends a notion used by Boolos in a proof of the Incompleteness Theorem, is shown to be non computable. This is followed by an examination of the complexity of sets associated with this function.

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

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.

We give some information about new proofs of the incompleteness theorems, found in 1990s. Some of them do not require the diagonal lemma as a method of construction of an independent statement.

We define a liar-type paradox as a consistent proposition in propositional modal logic which is obtained by attaching boxes to several subformulas of an inconsistent proposition in classical propositional logic, and show several famous paradoxes are liar-type. Then we show that we can generate a liar-type paradox from any inconsistent proposition in classical propositional logic and that undecidable sentences in arithmetic can be obtained from the existence of a liar-type paradox. We extend these results to predicate logic and discuss Yablo’s (...) Paradox in this framework. Furthermore, we define explicit and implicit self-reference in paradoxes in the incompleteness phenomena. (shrink)

By formalizing Berry's paradox, Vopěnka, Chaitin, Boolos and others proved the incompleteness theorems without using the diagonal argument. In this paper, we shall examine these proofs closely and show their relationships. Firstly, we shall show that we can use the diagonal argument for proofs of the incompleteness theorems based on Berry's paradox. Then, we shall show that an extension of Boolos' proof can be considered as a special case of Chaitin's proof by defining a suitable Kolmogorov complexity. We shall show (...) also that Vopěnka's proof can be reformulated in arithmetic by using the arithmetized completeness theorem. (shrink)

We present a semantic proof of Gödel's second incompleteness theorem, employing Grelling's antinomy of heterological expressions. For a theory T containing ZF, we define the sentence HETT which says intuitively that the predicate “heterological” is itself heterological. We show that this sentence doesn't follow from T and is equivalent to the consistency of T. Finally we show how to construct a similar incompleteness proof for Peano Arithmetic.

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

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.

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.