foundations of mathematics Godel

Implicit in Hilbert’s program had been the hope that the syntactic notion of provability would capture the semantic notion of truth. Gödel came up with the surprising discovery that this was not the case for type theory and related languages adequate for arithmetic, as long as the following assumptions are insisted upon:

1. The set of theorems (provable statements) is effectively enumerable, by virtue of the notion of proof being decidable.
2. The set of true statements of mathematics is ω-complete in the following sense: given any formula ϕ(x), containing a free variable x of type N, the universal statement ∀_{x ∊ N}ϕ(x) will be true if ϕ(n) is true for each numeral n—that is, for n = 0, n = S0, n = SS0, and so on.
3. The language is consistent.

Actually, Gödel also made a somewhat stronger assumption, which, as the American mathematician J. Barkley Rosser later showed, could be replaced by assuming consistency. Gödel’s ingenious argument was based on the observation that syntactical statements about the language of mathematics can be translated into statements of arithmetic, hence into the language of mathematics. It was partly inspired by an argument that supposedly goes back to the ancient Greeks and which went something like this: Epimenides says that all Cretans are liars; Epimenides is a Cretan; hence Epimenides is a liar. Under the assumptions 1 and 2, Gödel constructed a mathematical statement g that is true but not provable. If it is assumed that all theorems are true, it follows that neither g nor ¬g is a theorem.

No mathematician doubts assumption 1; by looking at a purported proof of a theorem, suitably formalized, it is possible for a mathematician, or even a computer, to tell whether it is a proof. By listing all proofs in, say, alphabetic order, an effective enumeration of all theorems is obtained. Classical mathematicians also accept assumption 2 and therefore reluctantly agree with Gödel that, contrary to Hilbert’s expectation, there are true mathematical statements which are not provable.

However, moderate intuitionists could draw a different conclusion, because they are not committed to assumption 2. To them, the truth of the universal statement ∀_{x ∊ N}ϕ(x) can be known only if the truth of ϕ(n) is known, for each natural number n, in a uniform way. This would not be the case, for example, if the proof of ϕ(n) increases in difficulty, hence in length, with n. Moderate intuitionists might therefore identify truth with provability and not be bothered by the fact that neither g nor ¬g is true, as they would not believe in the principle of the excluded third in the first place.

Intuitionists have always believed that, for a statement to be true, its truth must be knowable. Moreover, moderate intuitionists might concede to formalists that to say that a statement is known to be true is to say that it has been proved. Still, some intuitionists do not accept the above argument. Claiming that mathematics is language-independent, intuitionists would state that in Gödel’s metamathematical proof of his incompleteness theorem, citing ω-completeness to establish the truth of a universal statement yields a uniform proof of the latter after all.

Gödel considered himself to be a Platonist, inasmuch as he believed in a notion of absolute truth. He took it for granted, as do many mathematicians, that the set of true statements is ω-complete. Other logicians are more skeptical and want to replace the notion of truth by that of truth in a model. In fact, Gödel himself, in his completeness theorem, had shown that for a mathematical statement to be provable it is necessary and sufficient that it be true in every model. His incompleteness theorem now showed that truth in every ω-complete model is not sufficient for provability. This point will be returned to later, as the notion of model for type theory is most easily formulated with the help of category theory, although this is not the way Gödel himself proceeded. See below Gödel and category theory.