Index                                                                                                                                      Main essay

 

Three beliefs that lend illusory legitimacy to Cantor’s diagonal argument

Bhupinder Singh Anand[1]

 

(A .pdf  file of this essay before the current update is available at http://arXiv.org/abs/math/0304310)

1.  Cantor’s diagonal argument, Gödel’s proof, and Turing’s Halting problem

Whatever other beliefs there may remain for considering Cantor’s diagonal argument[2] as mathematically legitimate, there are three that, prima facie, lend it an illusory legitimacy; they need to be explicitly discounted appropriately.

The first - Cantor’s diagonal argument defines a non-countable Dedekind real number[3]; the second - Gödel uses the argument to define a formally undecidable, but interpretively true, proposition; and the third - Turing uses the argument to define an uncomputable Dedekind real number.

2.  Cantor’s diagonal argument

In the first case, we may, Platonically[4], define any natural number, expressed in binary notation, and followed by a period and a non-terminating sequence of the integers 0 and 1, as a Cantorian real number.

Cantor’s diagonal argument, then, considers any, given, 1-1 correspondence:

(*)        nCn      

where n ranges over the natural numbers, and Cn is a Cantorian real number of the form 0.an1an2an3...ani..., where ani is either 0 or 1 for any given i. Cantor then defines the Cantorian number 0.b1b2b3...bi..., such that bi is not equal to aii for any i. Clearly, 0.b1b2b3...bi... does not correspond to any natural number n in the given 1-1 correspondence (*). Since any given natural number n can obviously be corresponded to the Cantorian number where n is expressed in binary notation, and followed by a period, and a non-terminating series of 0’s, Cantor concludes that the Cantorian real numbers are uncountable.

It is not at all obvious, however, that the following conclusion can be drawn from the above argument:

Every Cantorian real number necessarily defines a classical[5] Dedekind cut[6] in the rational numbers (or its, classically equivalent, Cauchy sequence[7] of rationals).

For instance, we note, first, that the classical definition of a Cauchy sequence, {sn}, of rational numbers, implicitly implies that, for each such sequence, there is some effective method of proving that, given any rational number ε > 0, there is an integer N such that nN, mN implies that |sn - sm| ≤ ε.

Since there can only be denumerable such effective methods, it follows that, classically, the real numbers, when defined as Cauchy sequences, are denumerable. It, also, follows that the Cantorian real number defined by the diagonal argument cannot be assumed, without a constructive proof, to be a classical Dedekind real number.

Second, consider the non-terminating series of the odd natural numbers 1, 3, 5, 7, ... . We can express this as the non-terminating binary series:

1, 11, 101, 111, ... ,

and correspond to it the non-terminating sequence of rational numbers:

0.1, 0.11, 0.101, 0.111, ... .

Clearly, this last series oscillates; it can, prima facie, be computed by a classical Turing machine; and it defines a Cantorian real number if we, not entirely unreasonably, Platonically interpret Turing’s various postulations[8], in his seminal paper [Tu36], to implicitly imply that the non-terminating sequence of instantaneous tape descriptions[9] of every, non-halting, “circle-free a-machine”, uniquely defines a mathematical object that consists of a non-terminating sequence of the integers 0 and 1, whose individual terms are not necessarily computable.

However, equally clearly, the above series does not yield a Cauchy sequence of rational numbers that can be taken to define[10] a Dedekind real number[11].

Cantor’s argument should, therefore, be interpreted only as establishing that we cannot define a number-theoretic function f(n) = Cn in such a way that the range of f(n) contains all, and only, the Cantorian real numbers.

However, there may yet be some definable number-theoretic function, f(n), such that:

(a)  its range contains all the Dedekind real numbers;

(b)  it is undefined in the class R of Dedekind real numbers for some values in its domain;

(c)  it is defined for these values in the extended class of Cantorian real numbers (which clearly contains all the Dedekind real numbers).

Such a function, moreover, need not be algorithmically computable. Thus there may be no Turing machine T such that, given any natural number k, T halts if, and only if, it can be held to compute the Cantorian real number f(k). This would be the case if there were, for instance, some k such that any effective method of computing f(k) were necessarily dependent on k, and, so, not necessarily an effective method of computing f(n) for every n.[12]

The conclusion: We can neither conclude that Cantor’s diagonal argument determines an uncountable Dedekind real number, nor conclude from it that the cardinality of the Dedekind real numbers necessarily differs from that of the Dedekind (Peano) natural numbers[13].

3.  Gödel’s proof

In the second case, Gödel’s use of the diagonal argument, in his seminal 1931 paper on formally undecidable propositions [Go31a], is purely illustrative. He uses it in his Introduction simply to sketch the main ideas of his Theorem VI heuristically, without claiming any formal rigour. The aim of his paper, as he then remarks, is to show that ([Go31a], p9):

... The method of proof which has just been explained can obviously be applied to every formal system which, first, possesses sufficient means of expression when interpreted according to its meaning to define the concepts (especially the concept ‘provable formula’) occurring in the above argument; and, secondly, in which every provable formula is true. In the precise execution of the above proof, which now follows, we shall have the task (among others) of replacing the second of the assumptions just mentioned by a purely formal and much weaker assumption.

The question arises: Is it valid to treat Gödel’s heuristic argument, based on a semantic concept of intuitive “soundness[14]”, as being equivalent to his Theorem VI? Such equivalence is, of course, intuitionistically objectionable; even classically, set-theoretic arguments[15] corresponding to Cantor’s diagonal argument are not considered constructive in any sense.

That Gödel did not consider the two as equivalent is suggested by his remarks at the end of his Theorem VI ([Go31a], p26):

One can easily convince oneself that the proof we have just given is constructive (for all the existential assertions occurring in the proof rest upon Theorem V which, as it is easy to see, is intuitionistically unobjectionable), ... .

Thus, Gödel’s conversion of the non-constructive, semantic, argument into a syntactic one that he considered constructive, and intuitionistically unobjectionable, is significant; although a strong Platonist, Gödel’s remarks indicate that he intended to ensure that his argument, in Theorem VI, does not admit possible inconsistencies that could be argued as being inherent in the classically accepted non-constructivity of Cantor's diagonal argument.

4.1  Turing real numbers

In the third case, the real numbers considered by Turing, in his original 1936 paper on computable numbers [Tu36], were explicitly defined as the computations of “circle-free a-machines”. Turing wrote:

(i) The “computable” numbers may be described briefly as the real numbers whose expressions as a decimal are calculable by finite means.

(ii) According to my definition, a number is computable if its decimal can be written down by a machine.

(iii) The computable numbers do not, however, include all definable numbers, and an example is given of a definable number which is not computable.

(iv) If at each stage the motion of a machine ... is completely determined by the configuration, we shall call the machine an “automatic machine” (or a-machine).

(v) If an a-machine prints two kinds of symbols, of which the first kind (called figures) consists entirely of 0 and 1 (the others being called symbols of the second kind), then the machine will be called a computing machine. If the machine is supplied with a blank tape and set in motion, starting from the correct initial m-configuration, the subsequence of the symbols printed by it which are of the first kind will be called the sequence computed by the machine. The real number whose expression as a binary decimal is obtained by prefacing this sequence by a decimal point is called the number computed by the machine.

Thus, Turing implicitly implied here that every a-machine could be said to “compute” a binary sequence, which, in turn, could be suitably interpreted as defining a real number.

(vi) If a computing machine never writes down more than a finite number of symbols of the first kind it will be called circular. Otherwise it is said to be circle-free.

(vii) A sequence is said to be computable if it can be computed by a circle-free machine. A number is computable if it differs by an integer from the number computed by a circle-free machine.

Since a circle-free a-machine may not halt, this clarification of Turing’s can, not unreasonably, be interpreted as, again implicitly, defining the irrational numbers between 0 and 1 as the non-terminating sequence of instantaneous tape descriptions of a non-halting, circle-free, a-machine. The rational numbers between 0 and 1 correspond, obviously, to the finite sequence of instantaneous tape descriptions of a halting a-machine.

However, as in the case of Cantorian real numbers, we cannot assume, in the absence of a formal, constructive and intuitionistically unobjectionable[16], proof, that a given Turing real number, as defined, implicitly, in (v) and (vii) above, is also a Dedekind real number.

4.2       Turing’s Halting argument

Although Turing appears to argue in his paper [Tu36] that Cantor’s argument can be taken to establish the Platonic existence of an uncomputable Turing real number, he seems to have been ambivalent about using the argument unrestrictedly whilst introducing his Halting argument.

Perhaps, echoing Gödel’s earlier reservations to some extent, Turing too felt the need to express - albeit obliquely - awareness of a non-constructive element in the use of Cantor’s diagonal argument to define a Dedekind real number. Whatever the reason, he offered an alternative argument that was, essentially, based on defining an uncomputable number-theoretic function, rather than on non-constructively postulating that a period, followed by a non-terminating sequence of the digits 0 and 1, necessarily defines a Dedekind real number.

The ambivalence is reflected below, in Turing’s description of the Halting problem [Tu36]:

(viii) ... we might apply the diagonal process. “If the computable sequences are enumerable, let In be the nth computable sequence, and let Yn(m) be the mth figure in In. Let J  be the sequence with 1–Yn(n) as its nth figure. Since J is computable, there exists a number k such that 1–Yn(n) = Yk(n) for all n. Putting n = k, we have 1 = 2Yk(k), i.e. 1 is even. This is impossible. The computable sequences are therefore not enumerable”.[17]

The fallacy in this argument lies in the assumption that J is computable. It would be true if we could enumerate the computable sequences by finite means, but the problem of enumerating computable sequences is equivalent to the problem of finding out whether a given number is the D.N of a circle-free machine, and we have no general process for doing this in a finite number of steps. In fact, by applying the diagonal process argument correctly, we can show that there cannot be any such general process.

The simplest and most direct proof of this is by showing that, if this general process exists, then there is a machine which computes J. This proof, although perfectly sound, has the disadvantage that it may leave the reader with a feeling that “there must be something wrong”. The proof which I shall give has not this disadvantage, and gives a certain insight into the significance of the idea “circle-free”. It depends not on constructing J, but on constructing J', whose nth figure is Yn(n).

(ix) Let us suppose that there is such a process; that is to say, that we can invent a machine D which, when supplied with the S.D of any computing machine M will test this S.D and if M is circular will mark the S.D with the symbol “u” and if it is circle-free will mark it with “s”. By combining the machines D and I we could construct a machine M to compute the sequence J'. The machine D may require a tape. We may suppose that it uses the E-squares beyond all symbols on F-squares, and that when it has reached its verdict all the rough work done by D is erased.

The machine H has its motion divided into sections. In the first n–1 sections, among other things, the integers 1, 2, …, n–1 have been written down and tested by the machine D. A certain number, say R(n–1), of them have been found to be the D.N’s of circle-free machines. In the nth section the machine D tests the number n. If n is satisfactory, i.e., if it is the D.N of a circle-free machine, then R(n) = 1+R(n–1) and the first. R(n) figures of the sequence of which a D.N is n are calculated. The R(n)th figure of this sequence is written down as one of the figures of the sequence  J' computed by H. If n is not satisfactory, then R(n) = R(n–1) and the machine goes on to the (n+1)th section of its motion.

(x) From the construction of H we can see that H is circle-free. Each section of the motion of H comes to an end after a finite number of steps. For, by our assumption about D, the decision as to whether n is satisfactory is reached in a finite number of steps. If n is not satisfactory, then the nth section is finished. If n is satisfactory, this means that the machine M(n) whose D.N is n is circle-free, and therefore its R(n)th figure can be calculated in a finite number of steps. When this figure has been calculated and written down as the R(n)th figure of J', the nth section is finished. Hence H is circle-free.

(xi) Now let k be the D.N of H. What does H do in the kth section of its motion? It must test whether k is satisfactory, giving a verdict “s” or “u”. Since k is the D.N of H, and since H is circle-free, the verdict cannot be “u”. On the other hand the verdict cannot be “s”. For if it were, then in the kth section of its motion H would be bound to compute the first R(k–1)+1 = R(k) figures of the sequence computed by the machine with k as its D.N and to write down the R(k)’th as a figure of the sequence computed by H. The computation of the first R(k)–1 figures would be carried out all right, but the instructions for calculating the R(k)’th would amount to “calculate the first R(k) figures computed by H and write down the R(k)’th”. This R(k)’th figure wonld never be found. I.e., H is circular, contrary both to what we have found in the last paragraph and to the verdict “s”. Thus both verdicts are impossible and we conclude that there can be no machine D.

4.3  The Halting problem and CT

Now, Turing’s alternative argument is, essentially, the following form of the Halting problem[18]:

Suppose we have a Turing machine WillHalt which, given an input string M+w, will halt and accept the string if Turing machine M halts on input w, and will halt and reject the string if Turing machine M does not halt on input w. Viewed as a Boolean function, WillHalt(M, w) (halts and) returns true in the first case, and (halts and) returns false in the second.

Moreover, without appealing to Cantor’s diagonal argument, it is easily proven by contradiction that Turing machine WillHalt(M, w) cannot exist. However, the proof does not address an implicit, and foundationally fundamental, non-constructive issue: what, precisely, do we mean by “M does not halt on input w”?

If “WillHalt(M, w)” could effectively determine somehow that “M does not halt on input w”, then this procedure could be built into M, and so M would halt on w (possibly with the perplexing annotation: “Sorry, this program is being halted as the program has determined that it does not halt!”). Thus, we cannot even define the machine WillHalt(M, w) as a Turing machine without inviting an immediate inconsistency!

Prima facie, the definition appears similar to that of a “Liar” proposition as “The ‘Liar’ proposition is a lie”, or that of a “Russell” set as “{x | ‘x’ is a member of the ‘Russell’ set if and only ‘x’ is not a member of ‘x’}”![19]

So, if we accept that WillHalt(M, w) is a well-defined Boolean function, then the significant conclusion from the above (and Turing’s) argument is not that WillHalt(M, w) is Turing-uncomputable, since we cannot define a Turing machine WillHalt, but that, if the function is effectively computable, then the Church-Turing Thesis, abbreviated CT, is false.

4.4  CT and Turing’s “oracle”

We note that, in his paper [Tu36], Turing did not conclude from his Halting argument that a function such as WillHalt(M, w) is not computable; he only concluded that such a function cannot be computed by a Logical Computing (Turing) Machine as defined by him. However, since he was of the view that effective computability was, indeed, equivalent to computability by an LCM, Turing later proposed that a function such as WillHalt could, perhaps, be defined as an “oracle” that is not necessarily mechanical.

As noted by Hodges [Ho00]:

Turing's 1938 Princeton Ph.D. thesis, work conducted in close cooperation with Church, was entitled Systems of logic defined by ordinals, and published as (Turing 1939). Predominantly the work consisted of highly technical developments within mathematical logic. However the driving force lay in the question: what is the consequence of supplementing a formal system with uncomputable deductive steps? In pursuit of this question, Turing introduced the definition of an “oracle” which can supply on demand the answer to the halting problem for every Turing machine. ... Turing defined the “oracle” purely mathematically as an uncomputable function, and said, “We shall not go any further into the nature of this oracle apart from saying that it cannot be a machine.” The essential point of the oracle is that it performs non-mechanical steps.

Clearly, if the Church-Turing Thesis is false, then WillHalt can be a machine; further, if WillHalt is effectively computable, then CT is false. We thus consider whether there are mechanical computational processes that are not obviously duplicable by the operations of a classical Turing machine.

Now, prima facie, it is reasonable to assume that we can, in principle, modify the definition of a Turing machine T so that it will always recognise a “looping” situation; we simply specify that T record every instantaneous tape description at the execution of each machine instruction (in the manner of a classical - albeit virtual and infinite - two-dimensional, teleprinter-type tape), and compare the current instantaneous tape description with the record before proceeding to the next instruction. We could, further, instruct the machine T to interrupt the computation, and to assign arbitrary values and, or, further associated actions, to those instances of WillHalt(M, w) whose occurrences cause the machine to loop as in (xi) above[20].

Is such a machine a classical Turing machine? Is the resultant predicate well-defined? Does the above construction transform a Turing-undecidable predicate into an effectively decidable one? It is not obvious whether classical theory can provide unequivocal answers to these questions without recourse to CT, which would beg the question.

Clearly, if we can show, or accept, that the extended WillHalt(M, w) is well-defined[21], then CT is false.

5.  The influence of Gödel’s reasoning

We can argue that the Platonist roots of Turing’s “oracle” are dimly visible in the classical acceptance of the non-constructivity that is implicit in Gödel’s reasoning. Prima facie, most classical interpretations uncritically draw sustenance, and strength, from the original reasoning and conclusions expressed by Gödel in his 1931 paper. Thus it would not be surprising if classically accepted heuristic, and formal, expositions are founded on implicit, non-constructive, Platonist assumptions that could be implicit in Gödel’s formal, and informal, reasoning. The non-constructive logical consequences of such arguments would also, then, be classically accepted - perhaps reluctantly - simply because their non-constructive roots are obscurely hidden in such implicit premises.

For instance, Gödel’s and Rosser's reasoning on the definability of “undecidable” sentences in any Peano Arithmetic, assuming its consistency, is classically viewed as being definitively formal. The numerous attempts to challenge the reasoning and its conclusions over the years (starting with Wittgenstein most notably, and apparently led by Yessenin-Volpin later) have invariably, and quite effectively, attracted the fatal criticism of being heuristic, and non-formal, by Gödel’s standard of constructiveness.

However, both Gödel’s and Rosser's arguments are based on critical interpretations of their formal arguments that appeal to semantic elements at some point in their reasonings. Anomalous consequences of such reasoning[22] could be obscured if, having accepted these results as definitively formal, classical expositions of the arguments appeal at some critical points to heuristic interpretations and reasoning for ease of exposition. Classical theory may, then, be focusing more on the implications of the accepted interpretations of Gödel’s reasoning, and less on seeking any possible non-formal components that may be implicit either in the reasoning, or in its interpretation.

References[23]

[Go31a]  Gödel, Kurt. 1931. On formally undecidable propositions of Principia Mathematica and related systems I. In M. Davis (ed.). 1965. The Undecidable. Raven Press, New York.

[Go31b]  Gödel, Kurt. 1931. On formally undecidable propositions of Principia Mathematica and related systems I. Translated by B. Meltzer. 1962. University of Edinburgh.

 

<Web page: http://home.ddc.net/ygg/etext/godel/index.htm>

[Go51]    Gödel, Kurt. 1951. Some basic theorems on the foundations of mathematics and their implications. Gibbs lecture. In Kurt Gödel, Collected Works III, pp. 304-323. 1995. Unpublished Essays and Lectures. S. Feferman et al (ed.). Oxford University Press, New York.

[Ho00]    Hodges, A. 2000. Uncomputability in the work of Alan Turing and Roger Penrose. (Unpublished lecture)

 

<Web page: http://www.turing.org.uk/philosophy/lecture1.html>

[HW98]  Hodges, W. 1998. An editor recalls some hopeless papers. The Bulletin of Symbolic Logic, Volume 4, Issue 1, March 1998, pages 1-16.

 

<Web link: http://www.math.ucla.edu/%7Easl/bsl/0401-toc.htm>

[Me64]   Mendelson, Elliott. 1964. Introduction to Mathematical Logic. Van Norstrand, Princeton

[Ru53]    Rudin, Walter. 1953. Principles of Mathematical Analysis. McGraw Hill, New York.

[Tu36]     Turing, Alan. 1936. On computable numbers, with an application to the Entscheidungsproblem.

 

<Web page: http://www.abelard.org/turpap2/tp2-ie.asp>

 

(Updated: Friday 17th September 2:53:53 AM IST by re@alixcomsi.com)

Index           Top of page

 


[1] The author is an independent scholar. E-mail: re@alixcomsi.com; anandb@vsnl.com.

 

[2] Cf. [Ru53], p23, Theorem 2.16.

 

[3] Cf. [Ru53], p9, Definition 1.31.

 

[4] By Platonically we mean it is not necessary that, given any natural number n, we have access to an effective method for calculating the n’th term of the sequence in the definition that follows.

 

[5] For the purposes of this essay we take Rudin [Ru53], and Mendelson [Me64], as representative, in the areas that they cover, of standard expositions of classical real analysis, and, first order logic and effective computability, respectively.

 

[6] Cf. [Ru53], p3, Definition 1.4.

 

[7] Cf. [Ru53], p39, Definition 3.10.

 

[8] See §4.1(vii) below.

 

[9] Cf. ([Me64], p230).

 

[10] Cf. [Ru53], p39, Theorem 3.11.

 

[11] Cf. [Ru53], p9, Theorem 1.32.

 

[12] Of particular interest, are Turing’s following remarks:

 

“The expression ‘there is a general process for determining …’ has been used throughout this section as equivalent to ‘there is a machine which will determine …’ This usage can be justified if and only if we can justify our definition of ‘computable’. For each of these ‘general process’ problems can be expressed as a problem concerning a general process for determining whether a given integer n has a property G(n) [e.g. G(n) might mean ‘n is satisfactory’ or ‘n is the Gödel representation of a provable formula’], and this is equivalent to computing a number whose n’th figure is 1 if G (n) is true and 0 if it is false. ...

 

... The computable numbers do not include all (in the ordinary sense) definable numbers. Let P be a sequence whose n’th figure is 1 or 0 according as n is or is not satisfactory. It is an immediate consequence of the theorem of §8 that P is not computable. It is (so far as we know at present) possible that any assigned number of figures of P can be calculated, but not by a uniform process. When sufficiently many figures of P have been calculated, an essentially new method is necessary in order to obtain more figures.”

 

This point was echoed later by, in this case, Gödel - in his Gibbs lecture - where he, again implicitly, suggested that not every effective method need necessarily be algorithmic, although every algorithm is, necessarily, an effective method [Go51]:

 

“I wish to point out that one may conjecture the truth of a universal proposition (for example, that I shall be able to verify a certain property for any integer given to me) and at the same time conjecture that no general proof for this fact exists. It is easy to imagine situations in which both these conjectures would be very well founded. For the first half of it, this would, for example, be the case if the proposition in question were some equation F(n) = G(n) of two number-theoretical functions which could be verified up to very great numbers n.”

 

[13] We note that the latter result can, however, be proved non-constructively in an axiomatic set theory such as, say, ZFC, (see [Ru53], p34, Theorem 2.40, Corollary).

 

[14] A formal theory is considered “sound” if its theorems are true under its standard interpretation.

 

[15] Cf. [Ru53], p34, Theorem 2.40, Corollary.

 

[17] Turing’s Halting argument can, also, be interpreted as implying that, whereas every Turing real number (his computable sequence) is, obviously, a Cantorian real number, some Cantorian real numbers are not Turing real numbers (computable sequences).

 

[18] Cf. David Matuszek’s lecture notes at http://www.netaxs.com/people/nerp/automata/halting2.html.

 

[19] We note that definitions such as those of the “Liar” proposition and of the “Russell” set are striking examples of what may be termed as pseudo-propositions of a language; they have no communicable content. They highlight the importance of viewing every formal system non-Platonically as a language of communication. Reasonably, any concept expressible within a communicable language must, ipso facto, be capable of effectively unambiguous interpretation.

 

Clearly, if the raison d'etre of a language is to be a medium for communicating properties about content that lies outside the language, then the self-referential study of the internal structure of a language must also aim at effectively unambiguous communication - in this case, of the nature and structure of formal, finite, strings that are finitely constructible within the language.

 

Admitting non-finite, non-constructive elements into the language may compromise it to the point where we could permit non-communicable (or, more accurately, non-discernible) entities to be reflected in the language in such a way that they can be interpreted ambiguously by various interpretations - and yet give the illusion of unambiguous interpretation within each interpretation.

 

For instance, if we accept the argument that Cantorian real numbers are not necessarily Dedekind real numbers, then Cantor's diagonal construction may, indeed, be a notable example of such ambiguous interpretation.

 

[20] We note that, in the k’th section, machine H will input, and attempt to simulate, machine k, on input k, ad infinitum.

 

[21] That WillHalt(M, w) is a well-defined function is classically well-accepted; the classical conclusion that the Halting argument constructively establishes the existence of a Turing-uncomputable number-theoretic function presumes such well-definedness.

 

[22] For instance, although Gödel’s semantic reasoning is, indeed - as he remarks - constructive and intuitionistically unobjectionable, Rosser’s application of the Deduction Theorem, on the basis of a semantic hypothesis is, prima facie, non-constructive, intuitionistically objectionable, and arguably valid.

 

Briefly, Rosser’s informal meta-argument seems to depend critically on the semantic argument that (cf. [Me64], p146), assuming [H] is a provable formula in any Peano Arithmetic, PA, which is assumed simply consistent, and assuming, further, that j is the Gödel-number of a proof of [H] in PA, and given that:

 

(i) If PA proves: [H], then PA proves: [q(j)],

 

where [q(y)] is also a PA-formula, we may conclude, by the standard Deduction Theorem of first-order logic, that:

 

(ii) PA proves: [Hq(j)].

 

However, such a conclusion is questionable, since (ii) may not be true.

 

To see this, note that, given any natural number h, we could construct a Turing-machine T that would decompose h to check whether it is in fact the Gödel-number of some well-formed formula [H] of PA. However, assuming the provability of [H], T would be unable to conclude that the meta-assertion (ii) is valid, since the assertion does not hold for every natural number j. Such validity would, of course, follow if (ii) is valid.

 

In other words, the formal meta-mathematical expression of (i) is, actually, the meta-statement:

 

(iii) If PA proves: [H], then there is some j such that PA proves: [q(j)].

 

Now, from this, we cannot conclude (as Rosser does) that:

 

(iv) If PA proves: [H], then PA proves: [(Ej)q(j)].

 

Thus, from (iii), we may only conclude that, under the standard interpretation, it is true there must, then, be a number j. However, for j to be introduced as a primitive symbol into a formal PA-proof, as in Rosser's arguments (i) and (ii), where he applies the Deduction Theorem, we also need a formal PA-proof that, under Rosser’s hypothesis, the number j is adequately defined in every interpretation. However, [(Ej)q(j)] may be PA-unprovable.

 

Moreover, if j is Turing uncomputable, then j may not be adequately definable by any PA-formula, and so the Deduction Theorem cannot be applied to the meta-assertion (i), to conclude (ii), within a formal proof sequence of PA, so as to yield Rosser’s undecidable proposition in PA.

 

Of course, the deduction:

 

PA proves: [q(j)]

 

would follow from standard logical axioms if it could, indeed, be shown that [(E!j)q(j)] is PA-provable (where “!” signifies uniqueness) - which is not the case.

 

In other words, Rosser's argument simply assumes, implicitly, that, if we are given an h as above, then some j is always Turing-computable (hence there is always a PA-formula that uniquely represents such j), and arrives at a contradiction. However, the contradiction only establishes that j may be Turing-uncomputable for some h. In the absence of a PA-proof of (iv), we cannot logically conclude from this, as he seems to do, that there is no such j.

 

[23] MSC-class: 03B10

 

Key words: Algorithm, arithmetic, Cantor, Cauchy, Church, circle-free, classical, computable, consistent, constructive, Dedekind, diagonal construction, effective method, formal system, function, Gödel, interpretation, instantaneous, intuitive, loop, mapping, mathematical object, model, natural number, non-terminating, number-theoretic, Peano, Platonic, predicate, proposition, real number, satisfactory, sentence, set theory, sound, standard model, tape description, Turing, uncomputable, uncountable, undecidable, uniform method.