Godel's Proof by Nagel Ernest & James R. Newman & Douglas R. Hofstadter

Author:Nagel, Ernest & James R. Newman & Douglas R. Hofstadter [Nagel, Ernest]
Language: eng
Format: mobi
Publisher: NYU Press academic
Published: 2001-09-30T16:00:00+00:00

VII

Gödel’s Proofs

Gödel’s paper is difficult. Forty-six preliminary definitions, together with several important preliminary propositions, must be mastered before the main results are reached. We shall take a much easier road; nevertheless, it should afford the reader glimpses of the ascent and of the crowning structure.

A Gödel numbering

Gödel described a formalized calculus, which we shall call “PM,” within which all the customary arithmetical notations can be expressed and familiar arithmetical relations established.15 The formulas of the calculus are constructed out of a class of elementary signs, which constitute the fundamental vocabulary. A set of primitive formulas (or axioms) are the underpinning, and the theorems of the calculus are formulas derivable from the axioms with the help of a carefully enumerated set of Transformation Rules (or rules of inference).

Gödel first showed that it is possible to assign a unique number to each elementary sign, each formula (or sequence of signs), and each proof (or finite sequence of formulas). This number, which serves as a distinctive tag or label, is called the “Gödel number” of the sign, formula, or proof.16

The elementary signs belonging to the fundamental vocabulary are of two kinds: the constant signs and the variables. We shall assume that there are exactly twelve constant signs,17 to which the integers from 1 to 12 are attached as Gödel numbers. Most of these signs are already known to the reader: ‘~’ (short for ‘not’); ‘V’ (short for ‘or’); ‘⊃’ (short for ‘if . . . then . . .’); ‘=’ (short for ‘equals’); ‘0’ (the numeral representing the number zero); ‘+’ (short for ‘plus’); ‘×’ (short for ‘times’); and three signs of punctuation, namely, the left parenthesis ‘(’, the right parenthesis ‘)’, and the comma ‘,’. In addition, two other signs will be used: the inverted letter ‘E’, which may be read as ‘there is’, and which occurs in so-called “existential quantifiers”; and the lowercase letter ‘s’, which is prefixed to numerical expressions to designate the immediate successor of a number.

To illustrate: the formula ‘(∃x) (x = s0)’ may be read ‘There is an x such that x is the immediate successor of zero’. The table below displays the twelve constant signs, states the Gödel number associated with each one, and indicates the usual meaning of the sign.

Download

Copyright Disclaimer:
This site does not store any files on its server. We only index and link to content provided by other sites. Please contact the content providers to delete copyright contents if any and email us, we'll remove relevant links or contents immediately.