( A Part 6 - Part 8 A )
"The statement:" The statement "The statement: "This statement is unprovable" is unprovable "is unprovable" is unprovable?
Summary of the literature: Kurt and David have chosen paths set encodings for and for finite sequences of statements written in formal language. Once done, both received the same system of axioms is recursive arithmetic and consistent and that can demonstrate all finitary statements true. [As mentioned in the previous chapter, we will assume that we are reproducing the proof of Godel for a set of specific axioms]
Kurt notes that Such a system of statements and as codified by him elected, all the codes contained demonstrable is exactly the set of all primes can be written as a sum or difference of three consecutive primes. [Obviously, for other systems of axioms, or other coding, arithmetic property that defines the set of provable statements codes will be different.]
Finally, following the demonstration of Gödel, Kurt has proven that syntactically the statement G: "43 is a cousin who can not be written as a sum or difference of three consecutive primes is decidable for the set of axioms that have given. Ie neither G nor its negation are provable from those axioms.
Take now the function g (x ) defined as follows: g (x ) is the x -th prime number. For example g (1) = 2, g (2) = 3, g (3) = 5, etc.. Let us assume, without proof, that the function g (x ) is defined by the formal language of arithmetic. That is, it is possible to express in formal language that a property, depending on the variable x , which is only accomplished by the x -th prime. Due to the restrictions in formal language the construction of this definition is not a trivial problem, however, with a little ingenuity, can be (1) .
Kurt G The statement is then equivalent to:
x A (non-(43 is prime, 43 = + / - g (x ) + / - g (x + 1) + / - g (x + 1 + 1)))
Where "A" indicates "all" and the + / - indicates that there is to do the eight possible combinations of sums and subtraction between g (x ), g (x + 1) g (x + 1 + 1).
Let us call P (x ) is (non-(43 is prime, 43 = + / - g (x ) + / - g (x + 1) + / - g (x + 1 + 1))). Then, the statement of Kurt G has the form A x P (x ).
Note that P (1) states that 43 is a cousin who can not get as addition or subtraction of numbers 2, 3 and 5. That is, P (1) is a finitary set true and then, by definition, is demonstrable from the axioms given system.
P (1 + 1) states that 43 is a cousin who can not get as add or subtract the numbers 3, 5 and 7. P (1 + 1) is also a finitary statement true and therefore, is provable from a given system.
Similarly, P (1 + 1 + 1), P (1 + 1 + 1 + 1 ),... are all proven. However, G: A x P (x ) is not provable. Each individual instance is provable, but the general statement is not. Actually, the statement G which Gödel constructed to demonstrate how to always have x P (x ) where P (1), P (1 + 1 ),... are all provable, but A x P (x ) is not, nor is its negation.
In the case of Kurt statement. the denial of G says: "43 no is prime or can be written as a sum or difference of three consecutive primes (in fact the negation of G is a formal language translation of this statement). Now, as G is undecidable, we may well add to the original axioms of Kurt so that the system so extended, while being resourceful and consistent, to prove non-G. [A simple and direct way to accomplish this is to add as an axiom the statement itself is not-G.]
A moment! But no-G is wrong ... How can you prove it? "A demonstration of non-G as the code corresponds to a number of" non-standard "?
answer first to the second question. As I have stressed that the code was already set from before we give the system of axioms. This coding assigns to each finite sequence of natural numbers set "ordinary." The demonstration of non-G from axiom system is expanded, in particular, a finite sequence of statements and as such, it deserves as an integer code. [If-G is an axiom, the demonstration of non-G has, as a single utterance, the very non-G.]
Regarding the first question, we saw in a previous chapter that the concept of "demonstrable" or "not proven" has, in principle, no relation to the "fake" or "true." There is no contradiction in the fact that a statement "false" is "demonstrably" to a system of axioms, although it consistently.
Moreover, to ease anxiety semantics, we can say that non-G is "false" only if we understand that refers to the universe of natural numbers. According to a famous theorem of course, if an axiom system is consistent then there is a universe of discourse in which their statements are "true." So no-G is true in a different universe of natural numbers. [When the system is the one of the Peano axioms, these alternate universes are often called "non-standard models" of arithmetic, hence the earlier reference to "non-standard numbers.] But these are considerations beyond the demonstration semantic of Gödel. (2)
continued ...
Notes:
(1) A major constraint is the formal language that does not support "Ellipsis." For example, the expression (the "A" indicates "all"):
A x ( x = 1 + 1 + ... + 1 ( x times))
is not a formal language statement. On the other hand (the "E" indicates "there"):
E x ( x = 1 + 1 + ... + 1 (10 times))
although strictly speaking Nor is a statement, it can be accepted as an abbreviation for:
E x ( x = 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1)
that definitely it is a statement written in formal language.
(2) A small example, consider the statement E x (1 + 1 = (1 + x ) (1 - x )). If we consider the universe of natural numbers then the statement is "false." But if the universe we add all complex numbers of form a + bi with to and b whole, then, in that universe so widespread, it becomes "true", since 2 = (1 + i) (1 - i).
A similar idea semantically helps us understand why it can happen that P (1), P (2), P (3 ),... are all provable without A x P (x ) is. There may be a universe that the property is worth P 1, 2, 3, 4, ... but fail in other numbers, numbers that are obtained by adding the 1 on.
0 comments:
Post a Comment