Editing Gödel's incompleteness theorems (section)

== First incompleteness theorem<!--'Gödel's first incompleteness theorem' and 'First incompleteness theorem' redirect here--> ==
{{See also|Proof sketch for Gödel's first incompleteness theorem}}
'''Gödel's first incompleteness theorem'''<!--boldface per WP:R#PLA--> first appeared as "Theorem VI" in Gödel's 1931 paper "[[On Formally Undecidable Propositions of Principia Mathematica and Related Systems]] I". The hypotheses of the theorem were improved shortly thereafter by {{harvs|txt=yes|first=J. Barkley |last=Rosser|year=1936}} using [[Rosser's trick]]. The resulting theorem (incorporating Rosser's improvement) may be paraphrased in English as follows, where "formal system" includes the assumption that the system is effectively generated.

<blockquote>'''First Incompleteness Theorem''': "Any consistent formal system {{mvar|F}} within which a certain amount of elementary arithmetic can be carried out is incomplete; i.e. there are statements of the language of {{mvar|F}} which can neither be proved nor disproved in {{mvar|F}}." (Raatikainen 2020)<!-- this is a direct quote from (Raatikainen 2020) --></blockquote>

The unprovable statement {{math|''G''<sub>''F''</sub>}} referred to by the theorem is often referred to as "the Gödel sentence" for the system {{mvar|F}}. The proof constructs a particular Gödel sentence for the system {{mvar|F}}, but there are infinitely many statements in the language of the system that share the same properties, such as the conjunction of the Gödel sentence and any [[logically valid]] sentence.

Each effectively generated system has its own Gödel sentence. It is possible to define a larger system {{mvar|F'}}&nbsp;that contains the whole of {{mvar|F}} plus {{math|''G''<sub>''F''</sub>}} as an additional axiom. This will not result in a complete system, because Gödel's theorem will also apply to {{mvar|F'}}, and thus {{mvar|F'}} also cannot be complete. In this case, {{math|''G''<sub>''F''</sub>}} is indeed a theorem in {{mvar|F'}}, because it is an axiom. Because {{math|''G''<sub>''F''</sub>}} states only that it is not provable in {{mvar|F}}, no contradiction is presented by its provability within {{mvar|F'}}. However, because the incompleteness theorem applies to {{mvar|F'}}, there will be a new Gödel statement {{math|''G''<sub>''F''<nowiki>&thinsp;</nowiki>'</sub>}} for {{mvar|F'}}, showing that {{mvar|F'}} is also incomplete. {{math|''G''<sub>''F''<nowiki></nowiki>&thinsp;'</sub>}} will differ from {{math|''G''<sub>''F''</sub>}} in that {{math|''G''<sub>''F''<nowiki></nowiki>&thinsp;'</sub>}} will refer to {{mvar|F'}}, rather than&nbsp;{{mvar|F}}.

=== Syntactic form of the Gödel sentence ===

The Gödel sentence is designed to refer, indirectly, to itself. The sentence states that, when a particular sequence of steps is used to construct another sentence, that constructed sentence will not be provable in {{mvar|F}}. However, the sequence of steps is such that the constructed sentence turns out to be {{math|''G''<sub>''F''</sub>}} itself. In this way, the Gödel sentence {{math|''G''<sub>''F''</sub>}} indirectly states its own unprovability within {{mvar|F}}.<ref>{{harvnb|Smith|2007|p=135}}.</ref>

To prove the first incompleteness theorem, Gödel demonstrated that the notion of provability within a system could be expressed purely in terms of arithmetical functions that operate on [[Gödel number]]s of sentences of the system. Therefore, the system, which can prove certain facts about numbers, can also indirectly prove facts about its own statements, provided that it is effectively generated. Questions about the provability of statements within the system are represented as questions about the arithmetical properties of numbers themselves, which would be decidable by the system if it were complete.

Thus, although the Gödel sentence refers indirectly to sentences of the system {{mvar|F}}, when read as an arithmetical statement the Gödel sentence directly refers only to natural numbers. It asserts that no natural number has a particular property, where that property is given by a [[primitive recursive function|primitive recursive]] relation {{harv|Smith|2007|p=141}}.   As such, the Gödel sentence can be written in the language of arithmetic with a simple syntactic form. In particular, it can be expressed as a formula in the language of arithmetic consisting of a number of leading universal quantifiers followed by a quantifier-free body (these formulas are at level <math>\Pi^0_1</math> of the [[arithmetical hierarchy]]).  Via the [[MRDP theorem]], the Gödel sentence can be re-written as a statement that a particular polynomial in many variables with integer coefficients never takes the value zero when integers are substituted for its variables {{harv|Franzén|2005|p=71}}.

=== Truth of the Gödel sentence ===

The first incompleteness theorem shows that the Gödel sentence {{math|''G''<sub>''F''</sub>}} of an appropriate formal theory {{mvar|F}} is unprovable in {{mvar|F}}. Because, when interpreted as a statement about arithmetic, this unprovability is exactly what the sentence (indirectly) asserts, the Gödel sentence is, in fact, true ({{harvnb|Smoryński|1977|p=825}}; also see {{harvnb|Franzén|2005|pp=28–33}}). For this reason, the sentence {{math|''G''<sub>''F''</sub>}} is often said to be "true but unprovable." {{harv|Raatikainen|2020}}.  However, since the Gödel sentence cannot itself formally specify its intended interpretation, the truth of the sentence {{math|''G''<sub>''F''</sub>}} may only be arrived at via a meta-analysis from outside the system. In general, this meta-analysis can be carried out within the weak formal system known as [[primitive recursive arithmetic]], which proves the implication {{math|''Con''(''F'')→''G''<sub>F</sub>}}, where {{math|''Con''(''F'')}} is a canonical sentence asserting the consistency of {{mvar|F}} ({{harvnb|Smoryński|1977|p=840}}, {{harvnb|Kikuchi|Tanaka|1994|p=403}}).

Although the Gödel sentence of a consistent theory is true as a statement about the [[intended interpretation]] of arithmetic, the Gödel sentence will be false in some [[Peano axioms#Nonstandard models|nonstandard models of arithmetic]], as a consequence of Gödel's [[completeness theorem]] {{harv|Franzén|2005|p=135}}.  That theorem shows that, when a sentence is independent of a theory, the theory will have models in which the sentence is true and models in which the sentence is false.  As described earlier, the Gödel sentence of a system {{mvar|F}} is an arithmetical statement which claims that no number exists with a particular property. The incompleteness theorem shows that this claim will be independent of the system {{mvar|F}}, and the truth of the Gödel sentence follows from the fact that no standard natural number has the property in question. Any model in which the Gödel sentence is false must contain some element which satisfies the property within that model. Such a model must be "nonstandard" &ndash; it must contain elements that do not correspond to any standard natural number ({{harvnb|Raatikainen|2020}}, {{harvnb|Franzén|2005|p=135}}).

=== Relationship with the liar paradox ===

Gödel specifically cites [[Richard's paradox]] and the [[liar paradox]] as semantical analogues to his syntactical incompleteness result in the introductory section of "[[On Formally Undecidable Propositions in Principia Mathematica and Related Systems I]]".  The [[liar paradox]] is the sentence "This sentence is false."  An analysis of the liar sentence shows that it cannot be true (for then, as it asserts, it is false), nor can it be false (for then, it is true). A Gödel sentence {{mvar|G}} for a system {{mvar|F}} makes a similar assertion to the liar sentence, but with truth replaced by provability: {{mvar|G}} says "{{mvar|G}} is not provable in the system {{mvar|F}}."  The analysis of the truth and provability of {{mvar|G}} is a formalized version of the analysis of the truth of the liar sentence.

It is not possible to replace "not provable" with "false" in a Gödel sentence because the predicate "{{mvar|Q}} is the [[Gödel number]] of a false formula" cannot be represented as a formula of arithmetic. This result, known as [[Tarski's undefinability theorem]], was discovered independently both by Gödel, when he was working on the proof of the incompleteness theorem, and by the theorem's namesake, [[Alfred Tarski]].

=== Extensions of Gödel's original result ===

Compared to the theorems stated in Gödel's 1931 paper, many contemporary statements of the incompleteness theorems are more general in two ways. These generalized statements are phrased to apply to a broader class of systems, and they are phrased to incorporate weaker consistency assumptions.

Gödel demonstrated the incompleteness of the system of ''[[Principia Mathematica]]'', a particular system of arithmetic, but a parallel demonstration could be given for any effective system of a certain expressiveness. Gödel commented on this fact in the introduction to his paper, but restricted the proof to one system for concreteness.  In modern statements of the theorem, it is common to state the effectiveness and expressiveness conditions as hypotheses for the incompleteness theorem, so that it is not limited to any particular formal system. The terminology used to state these conditions was not yet developed in 1931 when Gödel published his results.

Gödel's original statement and proof of the incompleteness theorem requires the assumption that the system is not just consistent but ''[[omega-consistent|ω-consistent]]''. A system is '''ω-consistent''' if it is not ω-inconsistent, and is ω-inconsistent if there is a predicate {{mvar|P}} such that for every specific natural number {{mvar|m}} the system proves {{math|~''P''(''m'')}}, and yet the system also proves that there exists a natural number {{mvar|n}} such that {{mvar|P}}({{mvar|n}}). That is, the system says that a number with property {{mvar|P}} exists while denying that it has any specific value. The ω-consistency of a system implies its consistency, but consistency does not imply ω-consistency. {{harvard citations |txt=yes |first=J. Barkley |last=Rosser |author1-link=J. Barkley Rosser |year=1936}} strengthened the incompleteness theorem by finding a variation of the proof ([[Rosser's trick]]) that only requires the system to be consistent, rather than ω-consistent. This is mostly of technical interest, because all true formal theories of arithmetic (theories whose axioms are all true statements about natural numbers) are ω-consistent, and thus Gödel's theorem as originally stated applies to them. The stronger version of the incompleteness theorem that only assumes consistency, rather than ω-consistency, is now commonly known as Gödel's incompleteness theorem and as the Gödel–Rosser theorem.