( A Part 5 - Part 7 A )
"This statement is not self-referential "
- Now we come to the self-reference?
- Yes, now.
We have given a set of axioms is recursive, consistent, and allows prove all true arithmetical statements finitary (1) . We prove that there is a sentence G such that neither it nor its negation are provable from these axioms. [As stated in the previous chapter, we will assume that we are reproducing the proof of Godel for a set of specific axioms.]
remember that even before we give the axioms, we had already established a coding ie a function that each statement to a succession of statements and each assigned a natural number. (That was the first part of the demonstration Gödel.)
didactic purposes, let's imagine that two mathematicians, will be called Kurt and David, who are studying the proof of Gödel. Kurt has chosen the same encoding that we (technical details of which we have not), while David, pure stubborn, has chosen a completely different coding.
Suppose that Kurt encoding (which is also ours) to the statements they always correspond primes (2) . More precisely, we assume that Kurt coding it that " n is the code for a statement if and only if n is prime. "Coding For David, the situation is completely different and there is no code wording is a prime number (the latter happens, for example, Gödel's original coding).
Once we have the axioms, it is well established which set of statements that are provable from them (and that includes, among others, the axioms themselves). It is also well established which set the codes of these statements provable (that is, of course, a set of natural numbers).
Note that both Kurt and for David the set of provable statements is exactly the same. However, both disagree on which set of codes corresponding to these statements, as they differ as to what number is assigned to each statement.
The second part of the proof of Gödel was to prove that, no matter what the encoding chosen, and whatever the system of axioms given (provided that the assumptions mentioned in the previous chapter), there specific arithmetic property, expressible in the formal language that defines the whole assembly codes demonstrable statements.
Of course, Kurt and David differ on what is the defining property of their respective sets of codes (as they both "see" code sets), but both will be able to describe in terms of specific arithmetic properties (3) .
Normally the property is terribly complex arithmetic to express, I would say that in reality is "humanly impossible" to express in detail. For this reason, exposures show Gödel often stated that the property in question is simply to "be the code a provable statement "(or, more briefly, to" be demonstrably ").
But it is precisely these" abbreviations "that often lead to confusion here trying to dispel. So we will use Once again, our imagination and assume that for Kurt all the codes contained demonstrable is exactly the set of all primes can be written as a sum or difference of three consecutive primes (4) . [It is the task for the interested reader to verify that this property can be expressed in formal language.]
For example, 3 to 5 + 7 = 5, so number 5 (for Kurt) the code of a demonstrable statement, as do the 13, which is -5 + 7 + 11. The 2, however, can not be written as a sum or difference of three consecutive primes, so 2 is the code of a statement is not provable (always understand "demonstrable from the axioms given").
The third part of the proof of Gödel's First Theorem is to prove a number n such that the statement " n is a cousin who can not be written as a sum or difference of three primes consecutive " (in some of the possible translations into formal language) code is precisely the number n . Imagine that this number is No 43 (which, Jan fact, I believe, can not be written as a sum or difference of three consecutive primes).
In summary, Kurt finds that the statement (in a formal language translations): "43 is prime and can not be written as a sum or difference of three consecutive primes" have code 43. This is the famous undecidable statement G which builds the proof of Gödel.
(Note that, for his part, David has found a completely different set G. Each coding generates an undecidable statement different.)
"The statement G:" 43 is prime and can not be written as a sum or difference of three consecutive primes "is self-referential?
From the point of view of Kurt, "43 is prime and can not be written as a sum or difference of three consecutive primes" is equivalent (semantically!) To the statement "43 is the code of a statement it's unprovable. " And as to that statement belongs code 43 then equals: "My code is not a provable statement" or, as they say, "I do not demonstrable coy." For Kurt, it is self-referential.
How does David's situation? For him, "43 is prime and can not be written as a sum or difference of three consecutive primes" is not self-referential, because the code (whatever) sure is not the number 43. The statement does not refer to its code, dino of any number. Moreover, 43, to David, not even the code of a statement and "Be the addition or subtraction of three primes" is an arithmetic property irrelevant for metamathematics.
For Kurt, his statement G is self-referential, but David is not. in fact, no arithmetic is essentially self-referential statement, all depends on the encoding you choose.
The fourth and last part of the proof of Gödel's First Theorem is to prove that neither G nor its negation are provable from the axioms given. But a moment! Does this show does not depend on self-reference of G? "Kurt can only show the undecidability of" his "statement, and David only that of yours? No, no. The proof of the undecidability of G does not depend on their supposed self-reference. This demonstration is purely based on syntactic concepts. Kurt will demonstrate that "their" G is undecidable and David will understand perfectly that show. Similarly, Kurt will fully understand the reasoning that makes David to prove that "his" statement is undecidable (for the given axioms.)
Moreover, neither David nor Kurt even need to know that their statements can be interpreted as self-referential. The show does not need that concept.
Why is mentioned much, then, self-reference? Because we, humans, we find it very uncomfortable manage with purely syntactic concepts and when they need to constantly deal with the use of "semantic crutches." The Interpreting G as "I am not provable" is used (as one of those "crutches") to help in building the set G. Also, why not say it is used to show more compelling (for a demonstration not only be correct, but must also appear.)
The idea of \u200b\u200bself-reference, with its own-is-no-is paradoxical, often stealing the spotlight of the theorem while hiding purely syntactic nature of their demonstration. I repeat: the set G itself is not self-referential (it only takes that color when viewed through the lens of a specific encoding) and the demonstration of undecidability does not need this so-called self-reference.
continued ...
Notes:
(1) metamathematics By their nature, Gödel's theorems are stated and shown by appealing to syntactic concepts. How is it possible then to talk about "real finitary statements," since the notion of "truth" is a semantic concept. The explanation is that we are dealing with a narrow concept of "truth" of statements which speak only truth is verifiable (and, indeed, definable) by syntactic processes (ie algorithmic). It might be preferable to speak of finitary statements incorrect.
(2) is perfectly possible to define a code that complies with this condition, but would be impractical if you want to develop in detail the proof of Gödel.
(3) I will not discuss here the technical details of the demonstration, which can be seen in any of the books mentioned in the previous chapter. May also be those details in the thread of this forum entitled "Gödel's Theorem" (from the hundreds of comments, you must clear those containing the details of the demo.)
(4) For the whole sample to be meaningful must satisfy three conditions: a) must be infinitely many primes that can be written as a sum or difference of three consecutive primes; b) There must be infinite cousins \u200b\u200b can not write as a sum or difference of three consecutive primes; c) The number 43 should not be able to write as a sum or difference of three consecutive primes. I guess the three true statements. If you happen to be false, this does not invalidate the concepts presented, but only require to find a different example, or to imagine that the statements are true.
0 comments:
Post a Comment