ゲーデルの不完全性定理

Gödel’s Incompleteness Theorems (Stanford Encyclopedia of Philosophy) Stanford Encyclopedia of Philosophy Menu Browse Table of Contents What's New Random Entry Chronological Archives About Editorial Information About the SEP Editorial Board How to Cite the SEP Special Characters Advanced Tools Contact Support SEP Support the SEP PDFs for SEP Friends Make a Donation SEPIA for Libraries Entry Navigation Entry Contents Bibliography Academic Tools Friends PDF Preview Author and Citation Info Back to Top Gödel’s Incompleteness Theorems First published Mon Nov 11, 2013; substantive revision Wed Oct 8, 2025 Gödel’s two incompleteness theorems are among the most important results in modern logic, and have deep implications for various issues. They concern the limits of provability in formal axiomatic theories. The first incompleteness theorem states that in any consistent formal system \(F\) within which a certain amount of arithmetic can be carried out, there are statements of the language of \(F\) which can neither be proved nor disproved in \(F\). According to the second incompleteness theorem, such a formal system cannot prove that the system itself is consistent (assuming it is indeed consistent). These results have had a great impact on the philosophy of mathematics and logic. There have been attempts to apply the results also in other areas of philosophy such as the philosophy of mind, but these attempted applications are more controversial. The present entry surveys the two incompleteness theorems and various issues surrounding them. (See also the entry on Kurt Gödel for a discussion of the incompleteness theorems that contextualizes them within a broader discussion of his mathematical and philosophical work.) 1. Introduction 1.1 Outline 1.2 Some Formalized Theories 1.3 The Relevance of the Church-Turing Thesis 2. The First Incompleteness Theorem 2.1 Preliminaries 2.2 Representability 2.3 Arithmetization of the Formal Language 2.4 Diagonalization, or, “Self-reference” 2.5 The First Incompleteness Theorem—Proof Completed 2.6 Incompleteness and Non-standard Models 3. The Second Incompleteness Theorem 3.1 Preliminaries 3.2 Derivability Conditions 3.3 Feferman’s Alternative Approach to the Second Theorem 4. Results Related to the Incompleteness Theorems 4.1 Tarski’s Theorem on the Undefinability of Truth 4.2 The Undecidability Results 4.3 Reflection principles and Löb’s Theorem 4.4 Hilbert’s Tenth Problem and the MRDP Theorem 4.5 Concrete Cases of Unprovable Statements 5. The History and Early Reception of the Incompleteness Theorems 6. Philosophical Implications—Real and Alleged 6.1 Philosophy of Mathematics 6.2 Self-evident and Analytical Truths 6.3 ‘Gödelian’ Arguments against Mechanism 6.4 Gödel and Benacerraf on Mechanism and Platonism 6.5 Mysticism and the Existence of God? Further reading Bibliography Academic Tools Other Internet Resources Related Entries 1. Introduction 1.1 Outline Gödel’s incompleteness theorems are among the most important results in modern logic. These discoveries revolutionized the understanding of mathematics and logic, and had dramatic implications for the philosophy of mathematics. There have also been attempts to apply them in other fields of philosophy, but the legitimacy of many such applications is much more controversial. In order to understand Gödel’s theorems, one must first explain the key concepts essential to it, such as “formal system”, “consistency”, and “completeness”. Roughly, a formal system is a system of axioms equipped with rules of inference, which allow one to generate new theorems. The set of axioms is required to be finite or at least decidable, i.e., there must be an algorithm (an effective method) which enables one to mechanically decide whether a given statement is an axiom or not. If this condition is satisfied, the theory is called “recursively axiomatizable”, or, simply, “axiomatizable”. The rules of inference (of a formal system) are also effective operations, such that it can always be mechanically decided whether one has a legitimate application of a rule of inference at hand. Consequently, it is also possible to decide for any given finite sequence of formulas, whether it constitutes a genuine derivation, or a proof, in the system—given the axioms and the rules of inference of the system. A formal system is complete if for every statement of the language of the system, either the statement or its negation can be derived (i.e., proved) in the system. A formal system is consistent if there is no statement such that the statement itself and its negation are both derivable in the system. Only consistent systems are of any interest in this context, for it is an elementary fact of logic that in an inconsistent formal system every statement is derivable, and consequently, such a system is trivially complete. Gödel established two different though related incompleteness theorems, usually called the first incompleteness theorem and the second incompleteness theorem. “Gödel’s theorem” is sometimes used to refer to the conjunction of these two, but may refer to either—usually the first—separately. Accommodating an improvement due to J. Barkley Rosser in 1936, the first theorem can be stated, roughly, as follows: First incompleteness theorem Any consistent formal system \(F\) within which a certain amount of elementary arithmetic can be carried out is incomplete; i.e., there are statements of the language of \(F\) which can neither be proved nor disproved in \(F\). Gödel’s theorem does not merely claim that such statements exist: the method of Gödel’s proof explicitly produces a particular sentence that is neither provable nor refutable in \(F\); the “undecidable” statement can be found mechanically from a specification of \(F\). The sentence in question is a relatively simple statement of number theory, a purely universal arithmetical sentence. A common misunderstanding is to interpret Gödel’s first theorem as showing that there are truths that cannot be proved. This is, however, incorrect, for the incompleteness theorem does not deal with provability in any absolute sense, but only concerns derivability in some particular formal system or another. For any statement \(A\) unprovable in a particular formal system \(F\), there are, trivially, other formal systems in which \(A\) is provable (take \(A\) as an axiom). On the other hand, there is the extremely powerful standard axiom system of Zermelo-Fraenkel set theory (denoted as ZF , or, with the axiom of choice, ZFC ; see the section on the axioms of ZFC in the entry on set theory ), which is more than sufficient for the derivation of all ordinary mathematics. Now there are, by Gödel’s first theorem, arithmetical truths that are not provable even in ZFC . Proving them would thus require a formal system that incorporates methods going beyond ZFC . There is thus a sense in which such truths are not provable using today’s “ordinary” mathematical methods and axioms, nor can they be proved in a way that mathematicians would today regard as unproblematic and conclusive. Gödel’s second incompleteness theorem concerns the limits of consistency proofs. A rough statement is: Second incompleteness theorem For any consistent system \(F\) within which a certain amount of elementary arithmetic can be carried out, the consistency of \(F\) cannot be proved in \(F\) itself. In the case of the second theorem, \(F\) must contain a little bit more arithmetic than in the case of the first theorem, which holds under very weak conditions. It is important to note that this result, like the first incompleteness theorem, is a theorem about formal provability, or derivability (which is always relative to some formal system; in this case, to \(F\) itself). It does not say anything about whether, for a particular theory \(T\) satisfying the conditions of the theorem, the statement “\(T\) is consistent” can be proved in the sense of being shown to be true by a conclusive argument, or by a proof generally acceptable for mathematicians. For many theories, this is perfectly possible. 1.2 Some Formalized Theories The existence of incomplete theories is hardly surprising. Take any theory, even a complete one (see below for examples), and drop some axiom; unless the axiom is redundant, the resulting system is incomplete. The incompleteness theorems, however, deal with a much more radical kind of incompleteness phenomenon. Unlike the above sort of trivially incomplete theories, which can be easily completed, there is no way of completing the relevant theories; all their extensions, inasmuch as they are still formal systems and hence axiomatizable, are also incomplete. They remain, so to speak, eternally incomplete and can never be completed. They are “essentially incomplete”. In the first and loose statements of the incompleteness theorems given above, the vague requirement that “a certain amount of elementary arithmetic can be carried out” occurred. It is time to make this more precise. 1.2.1 Arithmetical Theories The weakest standard system of arithmetic that is usually considered in connection with incompleteness and undecidability is so-called Robinson arithmetic (due to Raphael M. Robinson; see Tarski, Mostowski and Robinson 1953), standardly denoted as Q . As axioms, it has the following seven assumptions: \[\begin{align} \tag{A1} &\neg(0 = x') \\ \tag{A2} &x' = y' \rightarrow x = y \\ \tag{A3} &\neg(x = 0) \rightarrow \exists y(x = y') \\ \tag{A4} &x + 0 = x \\ \tag{A5} &x + y' = (x + y)' \\ \tag{A6} &x \times 0 = 0 \\ \tag{A7} &x \times y' = (x \times y) + x \end{align}\] The intended interpretation of “\(x'\)” is the successor function, and obviously, of “+” and “\(\times\)”, the addition and the multiplication functions, respectively. “0” is the only constant and denotes the number zero. Adding to these elementary axioms the axiom scheme of induction: \[\tag{IND} \phi(0) \wedge \forall x[\phi(x) \rightarrow \phi(x')] \rightarrow \forall