Tag Archives: Kurt Gödel

Gödel’s Proof

Gödel showed (i) how to construct 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’. But (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.  Gödel then proved (iii) that, though G is not formally demonstrable, it nevertheless is a true arithmetical formula. 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, (iv) Since G is both true and formally undecidable, 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, (v) Next, Gödel described how to construct an arithmetical formula A that represents the meta-mathematical statement: ‘Arithmetic is consistent’; and he proved that the formula ‘A ⊃ G’ is formally demonstrable. Finally, he showed that 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.

(From Nagel and Newman‘s “Gödel’s Proof”

Advertisements

Antinomy or the Deceit of Clarity

“In point of fact, Bertrand Russell constructed a contradiction within the framework of elementary logic itself that is precisely analogous to the contradiction first developed in the Cantorian theory of infinite classes. Russell’s antinomy can be stated as follows. Classes seem to be of two kinds: those which do not contain themselves as members, and those which do. A class will be called “normal” if, and only if, it does not contain itself as a member; otherwise it will be called “non-normal”. An example of a normal class is the class of mathematicians, for patently the class itself is not a mathematician and is therefore not a member of itself. An example of a non-normal class is the class of all thinkable things; for the class of all thinkable things is itself thinkable and is therefore a member of itself. Let ‘N’ by definition stand for the class of all normal classes. We ask whether N itself is a normal class. If N is normal, it is a member of itself (for by definition N contains all normal classes); but, in that case, N is non-normal, because by definition a class that contains itself as a member is non-normal. On the other hand, if N is non-normal, it is a member of itself (by definition of non-normal); but, in that case, Nis normal, because by definition the members of N are normal classes. In short, N is normal if, and only if, Nis non-normal. It follows that the statement ‘N is normal’ is both true and false. This fatal contradiction results from an uncritical use of the apparently pellucid notion of class. Other paradoxes were found later, each of them constructed by means of familiar and seemingly cogent modes of reasoning. Mathematicians came to realize that in developing consistent systems familiarity and intuitive clarity are weak reeds to lean on.[1]


[1] Nagel and Newman, in Gödel’s Proof, pp. 23,24 & 25,  University of Florida Libraries.