◄ Contents

◄ Index

Chapter 2 ►

Chapter 1 : Introduction and terminology

1-01   Introduction

In this monograph, we establish three significant, inter-related results :

Chapter 2

We firstly show a fallacy in Gφdel’s claim in his famous 1931 paper ‘On Formally Undecidable Propositions of Principia Mathematica and Related Systems I’ that his reasoning is constructive and intuitionistically unobjectionable.

We show that, in his Theorem V on the expressibility and decidability of primitive recursive relations in any formal system S, Gφdel’s argument that every primitive recursive arithmetical relation and function can be constructively expressed in terms of only the primitive symbols of S, and is therefore formally expressible as a formula of S, is flawed.

In a constructive system of Arithmetic, Gφdel’s famous Theorem VI, and its consequences, thus reduce to unproven hypotheses since Gφdel invalidly assumes in the former that the primitive recursive relation  ~[x B [ Sb ( y : (19, z(y)) ) ] ] is a formula of S that can be constructively expressed in terms of only the primitive symbols of S for undetermined (variable) x and y, and hence Gφdel-numbered, to yield a specific PREDICATE q in S that is a FUNCTION of the two FREE VARIABLES 17 and 19, but independent of the free variables x and y.

Chapter 3

We show next that the error in Gφdel’s reasoning is rooted in the mistaken belief that every primitive recursive relation is constructively decidable in any formal system such as the Principia Mathematica.

We show specifically that if, in any such formal system S, we make explicit the intuitive meta-assumptions (which Gφdel makes implicitly) that underlie such systems :

a)   a formula is provable in S for every set of values of the free variables that occur in it if and only if it is provable in S, and

b)   a formula holds in S for every set of values that occur in it if and only if its closure holds in S,

then S is inconsistent if we assume that every primitive recursive relation is formally decidable in S.

Chapter 4

We show thirdly that Gφdel’s construction of an UNDECIDABLE SENTENCE can be carried out by elementary reasoning alone in any simply consistent formal system if we assume only that every primitive recursive relation can be Gφdel-numbered.

We reason in an intuitionistically unobjectionable way in the meta-theory M of Gφdel’s formal system S to show how his meta-Theorem VI - on the UNPROVABILITY in S of the FORMULA 17Genr, which corresponds in S to the meta-statement ‘17Genr is not PROVABLE in S’ - is essentially a conditional meta-Theorem in M which does not appeal to his Theorem V on the decidability of primitive recursive relations in S, nor depend on whether S is w-consistent, but only on the Gφdel-numberability of his primitive recursive relation Q (x, y).

Chapter 5

We show that Gφdel’s Theorem V depends on application of a non-constructive principle of induction.

1-02   Terminology : Standard

We assume familiarity with the standard terminology, concepts and reasoning in Gφdel [1931], with the following modifications for typographical convenience and easier readability :

(a)  We use CAPITAL types to indicate words or phrases that are to be specifically understood as explicitly defined in Gφdel [1931].

(b)  We prefix the symbol ‘~’ to denote negation where Gφdel uses a ‘bar’ over the expression  [Gφdel 1931 : p8 footnote 11a].

(c)  We write Gφdel’s substitution expressions linearly (where Gφdel uses a matrix format), as, for example :

Sb ( q : ( (17, z(x)), (19, z(y)), ... ) )

where ‘z(x)’, ‘z(y)’, ... are the NUMERALS respectively for any given finite set of numbers ‘x’, ‘y’, ... that are to be substituted for a given finite set of VARIABLES ‘17’, ‘19’, ... respectively in the PREDICATE ‘q’ [Gφdel 1931 : p20 definition31].

Thus ‘Sb ( q : ( (17, z(x)), (19, z(y)), ... ) )’ is a PRIMITIVE RECURSIVE PREDICATE in the  formal  system S that corresponds to (is the Gφdel number of) the formula obtained from the formula that corresponds to (whose Gφdel number is) ‘q’ by substituting (for any finite set of numbers ‘x’, ‘y’, ...) the NUMERALS ‘z(x)’, ‘z(y)’, ... respectively for a given finite set of VARIABLES ‘17’, ‘19’, ... respectively in the formula that corresponds to (whose Gφdel number is) ‘q’.

1-03   Terminology : Non-standard

We introduce some non-standard terminology and symbols - such as ‘├S’, ‘~’, ‘(x1)’, ‘╟S’, ‘qGdl R(x)’ - for expressing various intuitive meta-concepts and reasoning symbolically :

(d)  We denote Gφdel’s meta-statement ‘R(x1, … , xn) is a provable formula in S’ [Gφdel 1931 : p13] in the meta-theory M of S by ‘├S R(x1, … , xn)’.

(e)  We denote Gφdel’s meta-statement ‘R(x1, … , xn) is not a provable formula in S’ [Gφdel 1931 : p13] in the meta-theory M of S by ‘~├S R(x1, … , xn)’.

(f)  We denote Gφdel’s meta-statement ‘R(x1, … , xn)  is a provable formula in S for all sets of values of  x1, … , xn’ in the meta-theory M of S by ‘(x1) … (xn) ├S R(x1, … , xn)’.

(g)  We denote Gφdel’s meta-statement ‘R(x1, … , xn) is not a provable formula in S for some set of values of x1, … , xn’ in the meta-theory M of S by ‘~[(x1) … (xn) ├S R(x1, … , xn)]’.

(h)  We denote Gφdel’s meta-statement ‘P holds (is an intuitively TRUE sentence) in the interpretation A of S’ [Gφdel 1931 : p14] in the meta-theory M of S by ‘╟ A P’.

(i)   We denote Gφdel’s meta-statement ‘P does not hold (is an intuitively FALSE sentence) in the interpretation A of S’ [Gφdel 1931 : p14] in the meta-theory M of S by ‘~╟ A P ’.

(j)  We denote Gφdel’s meta-statement ‘R(x1, … , xn) holds (is an intuitively TRUE formula) in the interpretation A of S for all sets of values of x1, … , xn’ [Gφdel 1931 : p14] in the meta-theory M of S by ‘(x1) … (xn)╟ A R(x1, … , xn)’.

(k)  We denote Gφdel’s meta-statement ‘R(x1, … , xn)  does not hold (is an intuitively FALSE formula) in the interpretation A of S for some set of values of x1, … , xn’ [Gφdel 1931 : p14] in the meta-theory M of S by ‘~ [ (x1) … (xn)╟A R(x1, … , xn) ]’.

(l)   We denote the meta-statement ‘q is the Gφdel number of R(x1, … , xn)’ in the meta-theory M of S [Gφdel 1931 : p13-14], where q is a natural number and R(x1, … , xn) a well-formed formula in S, by ‘╟ M qGdl( R(x1, … , xn))’.

Gφdel expresses this equivalently by stating that ‘the PREDICATE (natural number) q corresponds to the formula R(x1, … , xn) of S’ [Gφdel 1931 : p23].

◄ Index       ◄ Title       ◄ Copyright       ◄ Dedication       ◄ Preface       ◄ Contents       ▲ Chapter 1       Chapter 2 ►

Chapter 3 ►       Chapter 4 ►       Chapter 5 ►       References ►       Roots ►       Bibliography ►       Web_links ►

◄ Questioning Gφdel’s Theorems (Dec 2000)       ◄ Beyond Gφdel (Oct 2001)

 (Updated : 10/18/01 9:48:48 AM by re@alixcomsi.com)