Godel's Proof

Posted by Ali Reda | Posted in | Posted on 10/20/2014

Gödel showed that Principia, or any other system within which arithmetic can be developed, is essentially incomplete. In other words, given any consistent set of arithmetical axioms, there are true arithmetical statements that cannot be derived from the set.

Godel showed that it is impossible to give a meta-mathematical proof of the consistency of a system comprehensive enough to contain the whole of arithmetic—unless the proof itself employs rules of inference in certain essential respects different from the Transformation Rules used in deriving theorems within the system. Such a proof may, to be sure, possess great value and importance. However, if the reasoning in it is based on rules of inference much more powerful than the rules of the arithmetical calculus, so that the consistency of the assumptions in the reasoning is as subject to doubt as is the consistency of arithmetic, the proof would yield only a specious victory: one dragon slain only to create another.

A few examples will help to an understanding of Hilbert’s distinction between mathematics (i.e., a system of meaningless signs) and meta-mathematics (meaningful statements about mathematics, the signs occurring in the calculus, their arrangement and relations). Consider the expression: 2 + 3 = 5 This expression belongs to mathematics (arithmetic) and is constructed entirely out of elementary arithmetical signs. On the other hand, the statement ‘2 + 3 = 5’ is an arithmetical formula asserts something about the displayed expression. The statement does not express an arithmetical fact and does not belong to the formal language of arithmetic; it belongs to meta-mathematics, because it characterizes a certain string of arithmetical signs as being a formula. if we wish to say something about a word (or other linguistic sign), it is not the word itself (or the sign) that can appear in the sentence, but only a name for the word (or sign). According to a standard convention we construct a name for a linguistic expression by placing single quotation marks around it. Our text adheres to this convention. It is correct to write: Chicago is a populous city. But it is incorrect to write: Chicago is tri-syllabic. To express what is intended by this latter sentence, one must write: ‘Chicago’ is tri-syllabic. Likewise, it is incorrect to write: x = 5 is an equation. We must, instead, formulate our intent by: ‘x = 5’ is an equation.

Godel devised a method of representation such that neither the arithmetical formula corresponding to a certain true meta-mathematical statement about the formula, nor the arithmetical formula corresponding to the denial of the statement, is demonstrable within the calculus. Since one of these arithmetical formulas must codify an arithmetical truth, yet neither is derivable from the axioms, the axioms are incomplete. Gödel’s method of representation also enabled him to construct an arithmetical formula corresponding to the meta-mathematical statement ‘The calculus is consistent’ and to show that this formula is not demonstrable within the calculus. It follows that the meta-mathematical statement cannot be established unless rules of inference are used that cannot be represented within the calculus, so that, in proving the statement, rules must be employed whose own consistency may be as questionable as the consistency of arithmetic itself. Gödel established these major conclusions by using a remarkably ingenious form of mapping. Since every expression in the calculus is associated with a (Gödel) number, a meta-mathematical statement about expressions and their relations to one another may be construed as a statement about the corresponding (Gödel) numbers and their arithmetical relations to one another. In this way meta-mathematics becomes completely “arithmetized.” Each metamathematical statement is represented by a unique formula within arithmetic; and the relations of logical dependence between meta-mathematical statements are fully reflected in the numerical relations of dependence between their corresponding arithmetical formulas which contain Godel Numbers. As if it was the mapping between Geometry and Algebra using a Cartesian system of coordinates.

Definitions





An arithmetic statement ‘(p ? p) ? p’ , its Godel number is 28 × 3112 × 52 × 7112 × 119 × 133 × 17112, which we shall designate by the letter ‘a’.
An arithmetic statement ‘(p ? p)’, whose Gödel number is 28 × 3112 × 52 × 7112 × 119; we shall designate it by the letter ‘b’.
A meta-mathematical statement that the formula ‘(p ? p)’ is an initial part of the axiom ‘(p ? p) ? p’, can be mapped to ‘b is a factor of a’

A meta-mathematical statement: ‘The sequence of formulas with Gödel number x is a proof of the formula with Gödel number z’. in arithmetic is mapped to ‘Dem (x, z)’
since the Gödel number x = 2^m × 3^z was assigned to the (fragment of a) proof whose conclusion has the Gödel number n.
the meta-mathematical statement ‘The sequence of formulas with the Gödel number x is not a proof for the formula with the Gödel number z’ is represented by a definite formula in the formalized arithmetical system. This formula is the formal contradictory of ‘Dem (x, z)’, namely,
‘~ Dem (x, z)’.

‘sub (m, 13, m)’, the Gödel number of the formula obtained from the formula with Gödel number m, by substituting for the variable with the Gödel number 13 the numeral for m. the resulting expression does not assert anything and therefore cannot be true or false. It merely designates or names a number, by describing it as a certain function of other numbers

The definition of the property of being Richardian does not belong to the series initially intended, because this definition involves metamathematical notions such as the number of signs occurring in expressions. We can outflank the Richard Paradox by distinguishing carefully between statements within arithmetic and statements about some system of notation in which arithmetic is codified. In the Richard Paradox, the number n is the number associated with a certain meta-mathematical expression. In the Gödel construction, the number n is associated with a certain arithmetical formula belonging to the formal calculus, though this arithmetical formula in fact represents a meta-mathematical statement because the meta-mathematics of arithmetic has been mapped onto arithmetic. In developing the Richard Paradox, the question is asked whether the number n possesses the meta-mathematical property of being Richardian. In the Gödel construction, the question asked is whether the number sub (n, 13, n) possesses a certain arithmetical property—namely, the arithmetical property expressed by the formula ‘(x) ~ Dem (x, z)’. There is therefore no confusion in the Gödel construction between statements within arithmetic and statements about arithmetic, such as occurs in the Richard Paradox.

Proof

(I) Godel constructs an arithmetical formula G that represents the meta-mathematical statement: ‘The formula G is not demonstrable’. This formula G thus ostensibly says of itself that it is not demonstrable. Up to a point, G is constructed analogously to the Richard Paradox. In that Paradox, the expression ‘Richardian’ is associated with a certain number n, and the sentence ‘n is Richardian’ is constructed. In Gödel’s argument, the formula G is also associated with a certain number h, and is so constructed that it corresponds to the statement: ‘The formula with the associated number h is not demonstrable’.

‘(x) ~ Dem (x, z)’, which represents within arithmetic the meta-mathematical statement: ‘For every x, the sequence of formulas with Gödel number x is not a proof for the formula with Gödel number z’. it is the unique representative, within the calculus, of the meta-mathematical statement: ‘The formula with Gödel number z is not demonstrable’ or, to put it another way, ‘No proof can be adduced for the formula with Gödel number z’.

‘sub (y, 13, y)’ designates a number. This number is the Gödel number of the formula obtained from the formula with Gödel number y, by substituting for the variable with Gödel number 13 the numeral for y.

(x) ~ Dem (x, sub (y, 13, y)) represents ‘The formula with Gödel number sub (y, 13, y) is not demonstrable’.The Previous formula has a Gödel number that can actually be calculated. Suppose the number to be n.

We now substitute for the variable with Gödel number 13 (i.e., for the variable ‘y’) in the formula of line (1) the numeral for n. A new formula is then obtained, which we shall call ‘G’ and display under that label: (G) (x) ~ Dem (x, sub (n, 13, n)), it says ‘The formula with Gödel number sub (n, 13, n) is not demonstrable’. Also ‘sub (n, 13, n)’ designates a number. This number is the Gödel number of the formula obtained from the formula with Gödel number n, by substituting for the variable with Gödel number 13 the numeral for n.

This formula occurs within the arithmetical calculus, and therefore must have a Gödel number. This number is sub (n, 13, n). To grasp this, we must recall that sub (n, 13, n) is the Gödel number of the formula that is obtained from the formula with Gödel number n (which is (x) ~ Dem (x, sub (y, 13, y))) by substituting for the variable with Gödel number 13 (i.e., for the variable ‘y’) the numeral for n. But the formula G has been obtained from the formula with Gödel number n (which is (x) ~ Dem (x, sub (y, 13, y))) by substituting for the variable ‘y’ occurring in it the numeral for n. Hence the Gödel number of G is in fact sub (n, 13, n). So the formula G is referring to itself and asserting of itself to be not demonstrable.
--  Gödel used a modified version of the liar paradox, replacing "this sentence is false" with "this sentence is not provable". G says that G isn't demonstrable. So If G is demonstrable, we should demonstrate that it isn't demonstrable.

(ii) Gödel also showed that G is demonstrable if, and only if, its formal negation ~ G is demonstrable. This step in the argument is again analogous to a step in the Richard Paradox, in which it is proved that n is Richardian if, and only if, n is not Richardian. However, if a formula and its own negation are both formally demonstrable, the arithmetical calculus is not consistent. Accordingly, if the calculus is consistent, neither G nor ~ G is formally derivable from the axioms of arithmetic. Therefore, if arithmetic is consistent, G is a formally undecidable formula.

We outline the first part of Gödel’s argument that if G is demonstrable then ~ G is demonstrable. Suppose the formula G were demonstrable. Then there must be a sequence of formulas within arithmetic that constitutes a proof for G. Let the Gödel number of this proof be k. Accordingly, the arithmetical relation designated by ‘Dem (x, z)’ must hold between k (the Gödel number of the proof), and sub (n, 13, n) (the Gödel number of G), which is to say that ‘Dem (k, sub (n, 13, n))’ must be a true arithmetical formula. However, it can be shown that this arithmetical relation is of such type that, if it holds between a definite pair of numbers, the formula that expresses this fact is demonstrable. Consequently, the formula ‘Dem (k, sub (n, 13, n))’ is not only true, but also formally demonstrable; that is, the formula is a theorem. But, with the help of the Transformation Rules in elementary logic, we can immediately derive from this theorem the formula ‘~ (x) ~ Dem (x, sub (n, 13, n))’. We have therefore shown that if the formula G is demonstrable its formal negation is demonstrable. It follows that if the formal system is consistent the formula G is not demonstrable.

(iii) Gödel then proved that, although the formula G is undecidable if the axioms of the system are consistent, it can nevertheless be shown by meta-mathematical reasoning that G is true. It is true in the sense that it asserts that every integer possesses a certain arithmetical property, which can be exactly defined and is exhibited by whatever integer is examined. However, that we have established an arithmetical truth, not by deducing it formally from the axioms of arithmetic, but by a meta-mathematical argument.
--How did he prove that G is true ?? Not from axioms of arithmetic, because they lead to a contradiction (G is formally undecidable), but in meta-mathematical statements, since there is a contradiction, then It can't be proved or demonstrated is true. G is formally undecidable, so it is, not demonstrable.

(IV) Since G is both true and formally undecidable within the arithmatic, the axioms of arithmetic are incomplete. In other words, we cannot deduce all arithmetical truths from the axioms. Moreover, Gödel established that arithmetic is essentially incomplete: even if additional axioms were assumed so that the true formula G could be formally derived from the augmented set, another true but formally undecidable formula could be constructed by repeating in the new system the procedure used originally for specifying a true but undecidable formula in the initial system.
--Result 1

(V) Next, Gödel described how to construct an arithmetical formula A that represents the meta-mathemetical statement: ‘Arithmetic is consistent’; since that from a contradictory set of axioms any formula can be derived. The converse: namely, if not every formula is a theorem (i.e., if there is at least one formula that is not derivable from the axioms), then the calculus is consistent. So the meta-mathemetical statement: ‘Arithmetic is consistent’ is equivalent to the statement ‘There is at least one formula of arithmetic that is not demonstrable’. The latter is represented in the formal calculus by the following formula, which we shall call ‘A’: (A) (?y)(x) ~ Dem (x, y) In words, this says: ‘There is at least one Godel number y such that, for every Godel number x, x does not stand in the relation Dem to y’. Interpreted meta-mathematically, the formula asserts: ‘There is at least one formula of arithmetic for which no sequence of formulas constitutes a proof’.

(VI)On the other hand, the consequent clause in this statement—namely, ‘It [arithmetic] is incomplete’ follows directly from ‘There is a true arithmetical statement that is not formally demonstrable in arithmetic’; and the latter, as the reader will recognize, is represented in the arithmetical calculus by an old friend, the formula G (x) ~ Dem (x, sub (n, 13, n)).

(VII) Accordingly, the conditional meta-mathematical statement ‘If arithmetic is consistent, it is incomplete’ is represented by combining the previous 2 formulas in a iff relation.
(VI) Then he proved that the formula ‘A ? G’ is formally demonstrable.

(VII) Then he showed that the formula A is not demonstrable. For suppose it were demonstrable. Then, since A ? G is demonstrable, by use of the Rule of Detachment the formula G would be demonstrable, which isn't the case, so if the arithmetic is consistent, the formula A is not demonstrable. From this it follows that the consistency of arithmetic cannot be established by an argument that can be represented in the formal arithmetical calculus. The grand final step is before us: we must conclude that if arithmetic is consistent its consistency cannot be established by any meta-mathematical reasoning that can be represented within the formalism of arithmetic. This imposing result of Gödel’s analysis should not be misunderstood: it does not exclude a meta-mathematical proof of the consistency of arithmetic. What it excludes is a proof of consistency that can be mirrored by the formal deductions of arithmetic.
--Reuslt 2