The first incompleteness theorem yields directly the fact that truth in a system (e.g., in N) to which the theorem applies is undecidable. If it were decidable, then all true sentences would form a recursive set, and they could be taken as the axioms of a formal system that would be complete. This claim depends on the reasonable and widely accepted assumption that all that is required of the axioms of a formal system is that they make it possible to decide effectively whether a given sentence is an axiom.

Alternatively, the above assumption can be avoided by resorting to a familiar lemma, or auxiliary truth: that all recursive or computable functions and relations are representable in the system (e.g., in N). Since truth in the language of a system is itself not representable (definable) in the system, it cannot, by the lemma, be recursive (i.e., decidable).

The same lemma also yields the undecidability of such systems with regard to theorems. Thus, if there were a decision procedure, there would be a computable function f such that f(i) equals 1 or 0 according as the ith sentence is a theorem or not. But then what f(i) = 0 says is just that the ith sentence is not provable. Hence, using Gödel’s device, a sentence (say the tth) is again obtained saying of itself that it is not provable. If f(t) = 0 is true, then, because f is representable in the system, it is a theorem of the system. But then, because f(t) = 0 is (equivalent to) the tth sentence, f(t) = 1 is also true and therefore provable in the system. Hence, the system, if consistent, is undecidable with regard to theorems.

Although the system N is incompletable and undecidable, it has been discovered by the Polish logician M. Presburger and by Skolem (both in 1930) that arithmetic with addition alone or multiplication alone is decidable (with regard to truth) and therefore has complete formal systems. Another well-known positive finding is that of the Polish-American semanticist and logician Alfred Tarski, who developed a decision procedure for elementary geometry and elementary algebra (1951).

Consistency proofs

The best-known consistency proof is that of the German mathematician Gerhard Gentzen (1936) for the system N of classical (or ordinary, in contrast to intuitionistic) number theory. Taking ω (omega) to represent the next number beyond the natural numbers (called the “first transfinite number”), Gentzen’s proof employs an induction in the realm of transfinite numbers (ω + 1, ω + 2, . . . ; 2ω, 2ω + 1, . . . ; ω², ω² + 1, . . . ), which is extended to the first epsilon-number, ε₀ (defined as the limit of . . . ), which is not formalizable in N. This proof, which has appeared in several variants, has opened up an area of rather extensive work.

Intuitionistic number theory, which denies the classical concept of truth and consequently eschews certain general laws such as “either A or ∼A,” and its relation to classical number theory have also been investigated (see mathematics, foundations of: Intuitionism). This investigation is considered significant, because intuitionism is believed to be more constructive and more evident than classical number theory. In 1932 Gödel found an interpretation of classical number theory in the intuitionistic theory (also found by Gentzen and by Bernays). In 1958 Gödel extended his findings to obtain constructive interpretations of sentences of classical number theory in terms of primitive recursive functionals.

More recently, work has been done to extend Gentzen’s findings to ramified theories of types and to fragments of classical analysis and to extend Gödel’s interpretation and to relate classical analysis to intuitionistic analysis. Also, in connection with these consistency proofs, various proposals have been made to present constructive notations for the ordinals of segments of the German mathematician Georg Cantor’s second number class, which includes ω and the first epsilon-number and much more. A good deal of discussion has been devoted to the significance of the consistency proofs and the relative interpretations for epistemology (the theory of knowledge).

The propositional calculus

It is easy to show that the propositional calculus is complete in the sense that every valid sentence in it—i.e., every tautology, or sentence true in all possible worlds (in all interpretations)—is a theorem, as may be seen in the following example. “Either p or not-p” ( p ∨ ∼p) is always true because p is either true or false. In the former case, p ∨ ∼p is true because p is true; in the latter case, because ∼p is true. One way to prove the completeness of this calculus is to observe that it is sufficient to reduce every sentence to a conjunctive normal form—i.e., to a conjunction of disjunctions of single letters and their negations. But any such conjunction is valid if and only if every conjunct is valid; and a conjunct is valid if and only if it contains some letter p as well as ∼p as parts of the whole disjunction. Completeness follows because (1) such conjuncts can all be proved in the calculus and (2) if these conjuncts are theorems, then the whole conjunction is also a theorem.

The consistency of the propositional calculus (its freedom from contradiction) is more or less obvious, because it can easily be checked that all its axioms are valid—i.e., true in all possible worlds—and that the rules of inference carry from valid sentences to valid sentences. But a contradiction is not valid; hence, the calculus is consistent. The conclusion, in fact, asserts more than consistency, for it holds that only valid sentences are provable.

The calculus is also easily decidable. Since all valid sentences, and only these, are theorems, each sentence can be tested mechanically by putting true and false for each letter in the sentence. If there are n letters, there are 2ⁿ possible substitutions. A sentence is then a theorem if and only if it comes out true in every one of the 2ⁿ possibilities.

The independence of the axioms is usually proved by using more than two truth values. These values are divided into two classes: the desired and the undesired. The axiom to be shown independent can then acquire some undesired value, whereas all the theorems that are provable without this axiom always get the desired values. This technique is what originally suggested the many-valued logics.