Proof sketch for Gödel's first incompleteness theorem

This article gives a sketch of a proof of Gödel's first incompleteness theorem. This theorem applies to any formal theory that satisfies certain technical hypotheses, which are discussed as needed during the sketch. We will assume for the remainder of the article that a fixed theory satisfying these hypotheses has been selected.'There is no algorithm M whose output contains all true sentences of arithmetic and no false ones.' This article gives a sketch of a proof of Gödel's first incompleteness theorem. This theorem applies to any formal theory that satisfies certain technical hypotheses, which are discussed as needed during the sketch. We will assume for the remainder of the article that a fixed theory satisfying these hypotheses has been selected. Throughout this article the word 'number' refers to a natural number. The key property these numbers possess is that any natural number can be obtained by starting with the number 0 and adding 1 a finite number of times. Gödel's theorem applies to any formal theory that satisfies certain properties. Each formal theory has a signature that specifies the nonlogical symbols in the language of the theory. For simplicity, we will assume that the language of the theory is composed from the following collection of 15 (and only 15) symbols: This is the language of Peano arithmetic. A well-formed formula is a sequence of these symbols that is formed so as to have a well-defined reading as a mathematical formula. Thus x = SS0 is well formed while x = ∀+ is not well formed. A theory is a set of well-formed formulas with no free variables. A theory is consistent if there is no formula F such that both F and its negation are provable. ω-consistency is a stronger property than consistency. Suppose that F(x) is a formula with one free variable x. In order to be ω-consistent, the theory cannot prove both ∃m F(m) while also proving ¬F(n) for each natural number n. The theory is assumed to be effective, which means that the set of axioms must be recursively enumerable. This means that it is theoretically possible to write a finite-length computer program that, if allowed to run forever, would output the axioms of the theory (necessarily including every well-formed instance of the axiom schema of induction) one at a time and not output anything else. This requirement is necessary; there are theories that are complete, consistent, and include elementary arithmetic, but no such theory can be effective. The sketch here is broken into three parts. In the first part, each formula of the theory is assigned a number, known as a Gödel number, in a manner that allows the formula to be effectively recovered from the number. This numbering is extended to cover finite sequences of formulas. In the second part, a specific formula PF(x, y) is constructed such that for any two numbers n and m, PF(n,m) holds if and only if n represents a sequence of formulas that constitutes a proof of the formula that m represents. In the third part of the proof, we construct a self-referential formula that, informally, says 'I am not provable', and prove that this sentence is neither provable nor disprovable within the theory. Importantly, all the formulas in the proof can be defined by primitive recursive functions, which themselves can be defined in first-order Peano arithmetic. The first step of the proof is to represent (well-formed) formulas of the theory, and finite lists of these formulas, as natural numbers. These numbers are called the Gödel numbers of the formulas.