It was initially assumed that descriptive completeness and deductive completeness coincide. This assumption was relied on by Hilbert in his metalogical project of proving the consistency of arithmetic, and it was reinforced by Kurt Gödel’s proof of the semantic completeness of first-order logic in 1930. Improved versions of the completeness of first-order logic were subsequently presented by various researchers, among them the American mathematician Leon Henkin and the Dutch logician Evert W. Beth.

In 1931, however, the belief in the coincidence of descriptive and deductive completeness was shattered by the publication of Gödel’s paper “Über formal unentscheidbare Sätze der Principia Mathematica und verwandter Systeme” (1931; “On Formally Undecidable Propositions of Principia Mathematica and Related Systems”), in which he proved that even as basic a mathematical theory as elementary arithmetic is inevitably deductively incomplete. This conclusion is known as Gödel’s first incompleteness theorem.

Gödel’s proof uses an ingenious technique of discussing the syntax of a formal system of elementary arithmetic by its own means. Each expression in this language, including each sentence, is represented by a unique natural number, called its Gödel number. Gödel constructed a certain sentence G that says that a certain sentence n is not provable, where n is the Gödel number of G itself. (Loosely speaking, what G says is, “This sentence is unprovable.”) G is therefore true but unprovable.

Gödel called attention to the similarity between the sentence G and the traditional paradox of the liar (given any sentence that says of itself that it is not true, if that sentence is true, then it is false, and if it is false, then it is true). A more accurate analogy, however, would be to an actor in a play, who in his role in the play makes a statement about himself in his ordinary life outside the play. In a similar way, the sentence with the Gödel number n can say something about the number n itself.

Hence, any formal system of elementary arithmetic must be deductively incomplete. This does not mean, however, that there must be truths in arithmetic that are absolutely unprovable. Indeed, G is relative to some particular system. By strengthening the system, one could make G provable, but, in that case, there would inevitably be some other true sentence that is unprovable in the stronger system.

Later, it was found that Gödel’s incompleteness proof is a consequence of a more general result. The “diagonal lemma” states that, for any formula F(x) of elementary arithmetic with just one individual variable x, there is a number n, represented by the numeral n, such that the Gödel number of the sentence F[n] is n. Gödel’s theorem follows by taking F(x) to be the formula that says, “The formula with the Gödel number x is not provable.” Most of the detailed argumentation in a fully explicit proof of Gödel’s theorem consists in showing how to construct a formula of elementary number theory to express this predicate.

Gödel’s proof relies on the assumption that the formal system in question is consistent—that is, that a proposition and its negation cannot be proved within it. Moreover, Gödel’s proof itself can be carried out by means of an axiomatized elementary arithmetic. Hence, if one could prove the consistency of an axiomatized elementary arithmetic within the system itself, one would also be able to prove G within it. The conclusion that follows, that the consistency of arithmetic cannot be proved within arithmetic, is known as Gödel’s second incompleteness theorem. This result showed that Hilbert’s project of proving the consistency of arithmetic was doomed to failure. The consistency of arithmetic can be proved only by means stronger than those provided by arithmetic itself.

Gödel’s incompleteness theorems are among the most important results in the history of logic. Two related metatheoretical results were proved soon afterward. First, Alonzo Church showed in 1936 that, although first-order logic is semantically complete, it is not decidable. In other words, even though the class of first-order logical truths is axiomatizable, the class of propositions that are not logically true is not axiomatizable. Hence, there cannot be a mechanical procedure that would, in a finite number of steps, decide whether a given sentence is logically true or whether its negation is satisfiable.

Another related result was proved by the Polish-American logician Alfred Tarski in his monograph The Concept of Truth in Formalized Languages (1933). Tarski showed that the concept of truth can be explicitly defined for logical (formal) languages. But he also showed that such a definition cannot be given in the language for which the notion of truth is defined; rather, the definition must be stated in a richer metalanguage (see also object language).

Tarski’s truth-definition is compositional; that is, it defines the truth of a sentence in terms of the semantic attributes of its component expressions. He defined truth as a special case of the notion of satisfaction, first for the simplest formulas, called atomic formulas, and then step-by-step for complex formulas. A sentence such as F(a), for example, is true just in case the individual referred to by “a” satisfies the predicate F. The truth conditions of complex sentences like F(a) & G(b) are given in terms of the same notion of satisfaction together with the truth-functional definitions of the connectives. The quantified formula (∃x)F(x) is true if and only if there is at least one expression “a” such that the individual referred to by “a” satisfies F. Likewise, (∀x)F(x) is true if and only if every referring expression is such that the individual referred to by that expression satisfies F (see also semantics: Meaning and truth).