Incompleteness Theorems . He asserts that, under certain conditions, no formal mathematical theory capable of describing natural numbers and arithmetic with sufficient expressiveness is both consistent and complete. That is, if the axioms of this theory do not contradict each other, then there are sentences that cannot be proven or refuted. The arithmetic theories for which the theorem is valid are basically those in which the deduction of theorems can be done using an algorithm .
The proof of the theorem is completely explicit: in it a formula is constructed, usually denoted G in honor of Gödel, for which given a proof of it, a refutation can be constructed, and vice versa. However, the natural interpretation of that sentence in terms of natural numbers is true. The second incompleteness theorem is a particular case of the first: it affirms that one of the undecidable sentences of said theory is the one that “affirms” its consistency. In other words, if the system in question is consistent, it cannot be tested within the system itself.
Summary
[ hide ]
- 1 Statement of theorems
- 1 Context
- 2 Preliminaries
- 3 First theorem
- 4 Second theorem
- 5 Examples of undecidable claims
- 6 Misunderstandings around Gödel’s theorems
- 7 Discussion and implications
- 8 Proof of the first theorem
- 9 Proof of the second theorem
- 10 Bibliography
- 11 Sources
Statement of theorems
Context
Incompleteness theorems are formulated in the context of a formal first-order theory. A first-order theory is nothing more than a simplified model of mathematical reasoning, made up of two elements:
- A formal language, consisting of a set of signs, and a syntax, which determines which sign chains are well-formed formulas.
- A deductive calculation, formed by the rules of inference , which define when, of a series of given formulas, one of them is “consequence” of the rest; and by the axioms , a certain set of formulas (which can be infinite).
With these elements the concept of proof is studied: the theorems are those formulas that are obtained from a chain of formulas that are either axioms or are the consequence of previous formulas.
The consistency of a theory is a basic requirement for it to be useful, since according to the explosion principle , an inconsistent theory demonstrates any formula. Completeness is a “desirable” characteristic, which would allow a theory to have an “answer” to every “question” that can be asked in its language. The first incompleteness theorem states that, under certain hypotheses, a formal theory cannot have both characteristics.
The first of these hypotheses is that the theory be arithmetic. An arithmetic theory is a formal theory that includes signs capable of describing natural numbers (such as: “+”, “×” or “0”), so that either their axioms or their theorems contain the so-called Peano axioms , which are the basic statements of arithmetic.
The second hypothesis is that the theory is recursive, which basically means that the procedure to distinguish
- well-formed formulas of which they are not,
- if one formula is a consequence of others or not,
- whether a given formula is an axiom or not is an algorithm, and can be carried out unambiguously in finite time.
Preliminary
Concepts that will help a better understanding of the theorem. First of all, you must know what a paradox is. A paradox is a proposition that contradicts itself, an incoherent proposition. A good example of a paradox is Socrates’ famous phrase “I just know I don’t know anything.” Obviously, if you don’t know anything, you already know something, then the proposition contradicts itself. The contradiction of this paradox arises at the moment when Socrates refers to himself. Gödel’s theorem has a lot to do with propositions that refer to themselves.
Another rather old paradox is the one known as “the paradox of Epimenides or the liar” that said “The Cretans, always deceivers”. As Epimenides was Cretan we can translate the statement thus: “I always lie. I never tell the truth.” What can be inferred from this paradox? If Epimenides always lies, that statement would be false, therefore, he does not always lie and always tells the truth. But if he tells the truth, the statement would turn out to be true, therefore he always lies and never tells the truth. And so we could continue to infinity, without reaching anything concrete. Again, self-reference produces a paradox.
A variant of the Epimenides paradox is as follows: Suppose we meet Epimenides and he says, “This statement is false.” Is it telling the truth or is it lying? Again self-reference produces a paradox. We always find self-reference. Let’s think more carefully about this case and give it another aspect using mathematical language. Let’s say:
B = [This statement is not true] = [B is false]
The question is, is B false or true? They are the only two options. We are going to analyze them and see what situations they pose. Suppose B is true. If B is true, the statement “B is false” is true. Wow, we are faced with a contradiction. How about we try the other option? Let’s now assume that B is false. If this is so, we find that the statement “B is false” is not true, then we could say that “B is true”, but had we not said that B was false? A new contradiction.
This paradox will be very useful for Gödel, who replaces the word “truth” with “provable”. Gödel creates proposition G, where:
G = [This statement is not provable] = [G is unprovable]
Gödel tells us that G may be true, but that we will never prove it. We are faced with the fact that the fact that a proposition is true has more weight than the fact that it is demonstrable.
Another curious paradox is the following:
The following sentence is false. The previous sentence is true.
We leave it to the reader to find the inconsistency, but we cannot fail to point out that again the phenomenon of self-reference causes the paradox. In this particular case, each proposition refers to the other, creating an “infinite loop”. Another similar case is the well-known drawing by MC Escher, “Hands that draw”. If the reader wanted to know more about these “eternal and graceful loops”, we recommend the book “Gödel, Escher, Bach. An eternal and graceful loop” by Douglas R. Hofstadter.
First theorem
Proving this theorem involves constructing a certain formula, the “Gödel sentence” G, and demonstrating that it cannot be proved or refuted in T, that is, it is independent or undecidable. For this, since in a recursive theory all proof is an algorithmic procedure, Gödel developed a method to code formulas and proofs by means of numbers and operations on them, called Gödel numbering. Once this is done, sentence G is the one that states “there is no number x with the property P”, where the property P, when examined in light of this equivalence between numbers and formulas, means “to be the proof (in the theory T) of G ». Therefore, sentence G affirms “I am not demonstrable in theory T”. (See detailed reasoning below.)
The fact that G is not demonstrable implies that it is true — for it affirms its own indemonstrability — in the natural interpretation in which the variables of the theory are interpreted as natural numbers. This means that no arithmetic theory under the conditions of the theorem can prove all the true statements of arithmetic. Furthermore, the fact that ¬G is also not demonstrable means that if taken as an axiom, the resulting theory T ‘= T + ¬G is also consistent, despite the fact that ¬G is false in its natural interpretation. Every consistent first-order theory has a model, that is, a set of mathematical objects for which the T theorems are true statements; and a model of T ‘is itself a model of T (since all the theorems of T are of T’). This fact then indicates the existence of non-standard models of arithmetic: whatever the objects that the theory T ‘describes, they verify all the arithmetic theorems, but they are not the natural numbers (for which ¬G is false). In other words, the first incompleteness theorem ensures that first-order theories cannot fully characterize the objects they describe.
Note that taking G (or its opposite) as axiom gives rise to a new theory T ‘in which G (or its opposite) is trivially demonstrable. However, this does not invalidate the theorem, since G (or its opposite) speak of “demonstrability in T”. T ‘is also incomplete: a new sentence G’ can be written that states “I am not demonstrable in T ‘”. In short, for a formal theory that is consistent and complete, one of the hypotheses must fail: either it is not recursive and there is no algorithm to distinguish the axioms from the rest of the formulas, as is the case of the consistent extensions that are constructed in Gödel’s completeness theorem; or they are not arithmetic, in the sense that they do not describe a large enough portion of the natural numbers and their axioms, such as Presburger’s arithmetic.
Second theorem
The statement in the second theorem refers to a formula, Consis T, which can be built on any theory T (see below), and which states that theory T is consistent. The Consis T statement simply states, again using the “equivalence” between proofs and numerical operations, “there is no proof of 0 = 1” (the absence of proof for any formula is equivalent to the consistency of the theory, due to the principle of explosion). Then you have:
To show that Consis T is not a theorem, Gödel’s numbering and the expressive capacity of arithmetic theories must be used once again to convert the first incompleteness theorem into the formal Consis T theorem ⇒ ¬∃x P (x) , where P is the property mentioned above of “being a proof of G”. Since G affirms its own indemonstrability, this formal theorem is equivalent to Consis T ⇒ G, so if Consis T were demonstrable, by pure formal deduction G would also be so, which is impossible if T is consistent (according to the first theorem of incompleteness).
The second incompleteness theorem imposes serious limitations when proving the consistency of a formal theory T: it can never be done using only T itself. If an extension T ‘is used in which Consis T can be demonstrated, the consistency of T itself ‘cannot be demonstrated in either T or T’.
Examples of undecidable claims
The existence of an undecidable statement within a formal system is not in itself a surprising phenomenon. The subsequent combined work of Gödel and Paul Cohen has given concrete examples of undecidable statements: both the axiom of choice and the hypothesis of the continuum are undecidable in the standard axiomatization of set theory. Those results do not require the incompleteness theorem.
In 1936 , Alan Turing demonstrated that the problem of stopping is undecidable. Later this result was generalized in the field of recursive functions in Rice’s Theorem which shows that all decision problems that are not trivial are undecidable in a system that is Turing-complete.
Gregory Chaitin produced undecidable claims in algorithmic information theory and in fact proved his own incompleteness theorem in that context.
Misunderstandings around Gödel’s theorems
Since Gödel’s first incompleteness theorem is so famous, it has given rise to many misunderstandings. Here we summarize some:
- The theorem does not imply that every interesting axiom system is incomplete. For example, Euclidean geometrycan be axiomatized so that it is a complete system.
Discussion and implications
The incompleteness results affect the philosophy of mathematics , particularly points of view such as formalism , which uses formal logic to define its principles. You can paraphrase the first theorem saying
“You will never be able to find an axiom system that is capable of demonstrating all mathematical truths and no falsehood.”
On the other hand, from a strictly formalist perspective this paraphrase would be considered meaningless because it presupposes that mathematical “truth” and “falsehood” are well defined in an absolute sense, rather than being relative to each formal system.
In essence, the proof of the first theorem is to construct a p statement within a formal axiom system that can be given the following meta- mathematical interpretation: p = “This statement cannot be proven.” As such, it can be seen as a modern version of the liar paradox. Contrary to the liar’s statement, p does not refer directly to himself; the above interpretation can only be “seen” from outside the formal system. The position that the theorem shows that humans have an ability that transcends formal logic can also be criticized in the following way: We do not know if the p statement is true or not, because we do not know (nor can we know) if the system is consistent. So we don’t really know any truth that is outside the system. All we know is the following: Either p is undemonstrable within the system, or the system is inconsistent.
This statement is easily demonstrable within the system. Another implication is that Gödel’s work motivated Alan Turing ( 1912 – 1954) to study which functions were capable of being calculated and which were not. For this he used his Turing Machine, a general-purpose machine through which he formalized the functions and calculation procedures. Proving that there were functions that are not possible to calculate using the Turing Machine. The paradigm of this set of functions is represented by the function that establishes “if given a Turing Machine, it produces a result or, on the contrary, it is calculated indefinitely”. This function, known as the Halting Problem, will be a fundamental piece to demonstrate the incomputability of certain functions.
Proof of the first theorem
Let it be a formal arithmetic and recursive theory T ω-consistent. Let the formula ¬∃z be DEM (z, x), where DEM is the formula that expresses the numerical relation Dem — relative to the formal theory T—. By the diagonal lemma there is a sentence G with a Gödel number g, for which G ⇔ ¬∃z, DEM (z, [g]) is demonstrated, that is, it states that “no number encodes a proof (in T) of the formula represented by g “, or in other words,” I am not demonstrable (in T) “. The negation of this sentence, ¬G, is equivalent to ∃z, DEM (z, [g]), or “my negation is demonstrable (in T)”.
Suppose then that G can be proved. Then there exists a number n that satisfies Dem (n, g), and in T then DEM ([n], [g]) can be proved, which formally implies ¬G; and this is impossible if T is consistent. Therefore there is no proof of G, and ¬Dem (n, g) is true for all numbers n, resulting in an infinite number of formal theorems ¬DEM ([n], [g]) for each numeral [ n]. Since T is consistente-consistent, then it cannot happen that ∃x, DEM (x, [g]) is a theorem, so ¬G is unprovable, and T is undecidable.
Proof of the second theorem
The proof of the second incompleteness theorem requires a technical fact that Gödel did not originally prove. Let be a theory T in the above conditions and let be the formula Consis T ≡ ¬∃z, DEM (z, [k]), where k is the Gödel number of the sentence 0 = 1. Consis T affirms that theory T is consistent (because it leaves something unproven). The formal version (of the first part) of the first incompleteness theorem can be expressed as Consis T ⇒ ¬∃y, DEM (y, [g]) and this is precisely equivalent to Consis T ⇒ G. So, to be able to prove formally this sentence, Consis T would be unprovable since we would then have a proof of G, in contradiction to the first theorem.
The technical fact that is needed is precisely proof that the proof of the first incompleteness theorem can be “translated” into a formal proof of the Consis T ⇒ ¬∃y, DEM (y, [g]) statement. This is possible in all recursive arithmetic theory, since they verify certain conditions of demonstrability.
