“In Mathematics there is no ignorabimus. We must know, we shall know.”
-David Hilbert
The incompleteness theorem, says roughly the following: under certain conditions in any language there exist true but unprovable statements.
The Set of True Statements– We assume that we are given a subset T of the set L (where L is the alphabet of the language under consideration) which is called the set of “true statements” (or simply “truths”). In going right to the subset T we are omitting such intermediate steps as: firstly, specifying which words of all the possible ones in the alphabet L are correctly formed expressions in the language, i.e.. have a definite meaning in our interpretation of the language (for example, 2 + 3, x + 3, x = y, x = 3, 2 = 3, 2 = 2 ‘are correctly formed expressions, while + = x is not); secondly, which of all the expressions are formulas, i.e., in our interpretation make statements which may depend on a parameter (for example, x = 3, x = y, 2 = 3, 2 = 2); thirdly, specifying which of all the possible formulas are closed formulas, i. e., statements which do not depend on parameters (for example, 2 = 3, 2 = 2); and finally, which of all the possible closed formulas are true statements (for example, 2 = 2).
Attempts at a Precise Formulation of the Incompleteness
Theorem.
First Attempt– “Under certain conditions, given a fundamental pair (L, T) and a deductive system (P, P, B) over L, there always exists a word in T which does not have a proof.” This statement is still too vague. In particular, we could obviously think up many deductive systems having very few provable words. For example, there are no provable words at all in the empty deductive system (where P = 0).
Second Attempt– There is another more natural approach. Suppose we are given a language, in the precise meaning that we are given a fundamental pair (L, T). We now look for a deductive system over L (intuitively, we look for techniques of proof) in which we can prove as many words in T as possible, ideally, all words in T. Gödel’s theorem describes a situation in which such a deductive system (in which every word of T has a proof) does not exist. Thus, we would like to make the following statement: “Under certain conditions concerning the fundamental pair (L, T) there does not exist a deductive system over L in which every word in T has a proof.” However, this statement is clearly false, since one need only take the deductive system with P = L, P = P” and ~ (p) = p for all p in P”: then every word in L is trivially provable. Thus, we need a restriction on the deductive systems that we are allowed to use.
The Simplest Incompleteness Criteria
We now know that enumerability of the set T is equivalent to the existence of a complete and consistent deductive system for (L, T). However, we might be interested not in all truths in the language, but only in truths of a certain type or a certain class, much as a student studying for a math exam is not concerned with the truth of all mathematical statements, but only those which are likely to be encountered on the exam. For example, we might want to construct a deductive system in which one can derive all true statements of length at most 1000 and cannot derive any false statement of length at most 1000. In this case, for a statement of length greater than 1000 the question of whether or not it can be derived in the deductive system may have nothing- to do with whether or not it is true. Moreover, in certain situations (such as the language of set theory), one cannot even define the set of all truths in their totality. This is why we restrict ourselves to considering consistency and completeness for subsets of the word set L.
