# Anticipating Turing’s and Godel’s Results

Post’s considerations that are presented in this part take his Thesis for granted. It is perfectly clear to Post that the significance of his results depends on it. For example, Post writes, referring to the unsolvability of the finiteness problem for the class of all normal systems:

The correctness of this result is clearly entirely dependent on the trustworthiness of the analysis leading to the above generalization. *(Anticipation,* p. 48)

In order to obtain this very result, he outlines in §9 of *Anticipation* “a minimum mathematical development”. He sharpens the informal proof he sketched in §8, beginning with the definition of a particular ordering of all the bases of normal systems, called the *a -ordering.* The diagonal set *D _{a}* relative to this ordering is called the

*N-set.*The definition is followed by the “almost trivial theorem” that no normal system has the

*N*-set as the set of assertions involving only the letter

*a.*Post asserts that this theorem provides the “mathematical basis for the no finite method theorem” and emphasizes that it would be trivial, “were it not for the all embraciveness of normal systems” (

*Anticipation*, p.50), i.e., the correctness of his Thesis.

In the remainder of §9 proofs of statements are only sketched, although “a complete mathematical proof thereof clearly can be given”. (*Anticipation*, p. 50)^{[1]} Post labels the statements cautiously as (Theorem)-s. Among them is the formulation of an “important intermediate” assertion.

(Theorem). *There exists a normal system K and a correspondence C such that for each normal system and enunciation thereof there is one and only one enunciation in K by correspondence C*, *and such that such an enunciation in K is asserted when and only when the corresponding normal system versus enunciation is such that the enunciation is an assertion in that normal system.* (*Anticipation*, p. 51)

Post refers to the normal system *K* as “the *complete normal system* because, in a way, it contains all normal systems”. A footnote attached to this remark states, “the ‘complete normal system’ would thus correspond to Turing’s ‘universal computing machine’”.^{[2]} *(Anticipation,* fn. 95)

The normal system *M* has a *finite-normal-test* if there exists a normal system *M'* on the primitive letters of *M* supplemented by at least the letter *b* and such that the following correspondence between their enunciations holds: *P* is an assertion in *M'* when and only when it is an assertion in *M*; *bP* is an assertion in *M'* when and only when *P* is not an assertion in *M. ^{[3]}* Thus, for each enunciation

*P*of

*M*exactly one of the two sequences

*P*or

*bP*is an assertion of

*M',*and which is the assertion depends entirely on whether

*P*is or is not an assertion of

*M*. We have consequently a (Theorem) that can be proved by a

*reductio ad absurdum*argument: if there were such a system constituting a flnite-normal-test for

*K*, then a system could be constructed that would generate exactly the

*N*-set; but that is impossible.

- (Theorem).
*There exists no finite-normal-test for the complete normal system K*. - (Anticipation, p. 52)

Following the argument for this (Theorem), Post describes “the positive content” of its proof. In conjunction with the previous (Theorem) it allows us to construct from a flnite-normal-test *L* for *K* a normal system *L'* such that *L* will give a *wrong* answer to the question, whether the a-sequence of length *m**'* is an assertion of *L**',* which is the *m*^{7}-th normal system.

The above requirements on a flnite-normal-test for *K* are weakened in §10 or rather, as Post puts it in his letter to Godel of 30 October 1938, his examination of the “source of the contradiction” in the above argument led to a particular statement in the extending logic “such that neither it nor its negative was asserted” in that logic. (Godel [28], p. 170) So let *K* be again the complete normal system and assume that *L* is a normal system whose alphabet includes that of *K*. Now *L* is not *always* to give an answer to the question, whether or not an enunciation of *K* is an assertion of *K*; rather, when *L* gives an answer, it has to be correct. More precisely, let *L* have at least the primitive letter *b* in addition to the primitive letters of *K* .If *S* is a normal system and *P* one of its enunciations, we require *(S, P)* to be an assertion of *L* if and only if *P* is an assertion of S; whereas, if *b(S, P)* is an assertion of *L*, then *P *must not be an assertion of *S*. In terms of the complete system *K* this is equivalent to the following: *(S, P)* is an assertion of *L* if and only if it is an assertion of *K*, and if *b(S, P)* is an assertion of *L*, then *(S, P)* is not an assertion of *K*. Post calls such an *L* a *normal-deductive-system* adjoined to *K* and remarks, if *b* is added to *K*, the resulting system is normal-deductive.^{[4]}

Observe an important property of any normal-deductive-system *L*: such a system cannot prove both *(S, P)* and *b(S, P*). This property is similar to Godel’s consistency requirement, at least with respect to the set of enunciations of the form *(S, P)* and *b(S, P)**.* Via a diagonal argument an analogue of Godel’s First Theorem^{[5]} can be obtained, showing that a particular enunciation is undecidable:

(Theorem). *No normal-deductive-system* [*L*] is complete, there always existing a normal system *S* and enunciation *P* thereof such that *P* is not in *S* [thus, *(S, P)* is not in *L*], while *b(S, P)* is not in the normal-deductive-system [L]. *(Anticipation,* p. 54)

Thus every normal-deductive system *L* is incomplete at least with respect to the set of enunciations of the form *(**S**, **P*). The restriction to such enunciations does not diminish the significance of the result; after all, Godel’s Theorem similarly states “the incompleteness of any symbolic logic with respect to the class of arithmetical propositions”. (*Anticipation*, fn. 101)

After the above incompleteness (Theorem) has been asserted, Post adds a “still more important” one, stating that normal-deductive systems can always be extended. According to him, the following statement “rules out the possibility of a completed symbolic logic. That is, any symbolic logic can be made more complete.” *(**Anticipation**,* fn. 101) In the letter to Godel, mentioned above, he makes the reason for this extendibility clearer; *L* does not decide the enunciation *(**S**, **P**),* but the proof of the above (Theorem) and an appeal to the meaning of *(**S**, **P**),* “*S* asserts *P*”, do decide it. The statement is formulated in the following way:

(Theorem). *No normal-deductive-system is equivalent to the complete logical system (if such there be); better, given any normal-deductive-system there exists another which second proves more theorems (to put it roughly) than the first.* (Anticipation, *p. 54)*

These results taken together with those of §9 of *Anticipation* lead Post to the conclusion, *“A complete logic is impossible. ”* This is for Post “an iconoclastic result from a logician’s point of view”, as it means “logic must be informal not only in some parts of its description, but also in its very operation”. *(**Anticipation**,* pp. 54-5) “Better still”, Post writes, *“The Logical Process is Essentially Creative. ”* This creative aspect of the logical process is the crucial conclusion for Post.^{[6]} In the very introduction to *Anticipation* he had emphasized already:

[P]erhaps the greatest service the present account could render would stem from its stressing of its final conclusion that mathematical thinking is, and must be, essentially creative.

*(Anticipation,* p. 4)

He immediately adds in a footnote a deeply puzzling remark that seems to provide a reason for the creativeness of mathematical thinking:

Yet, as this account emphasizes, the creativeness of human mathematics has a counterpart inescapable limitation thereof—witness the absolutely unsolvable (combinatory) problems.

*(Anticipation,* fn. 12)

A similar remark is found in his [45] after Post establishes what he called there *Godel’s theorem in miniature**:*

The conclusion is unescapable [sic] that even for such a fixed, well defined body of mathematical propositions, *mathematical thinking is, and must remain, essentially creative.* To the writer’s mind, this conclusion must inevitably result in at least a partial reversal of the entire axiomatic trend of the late nineteenth and early twentieth centuries, with a return to meaning and truth as being of the essence in mathematics. (Post [45], p. 295)

To understand the first claim, we not only have to clarify the ordinary meaning of *counterpart**,* we also have to gain a deeper insight into the meaning Post associates with creativeness.

Here is, first of all, an attempt to rephrase Post’s claim, guided by the Oxford English Dictionary as to the meaning of counterpart^{20}: *the creativeness of human mathematics* is a natural complement to *its inescapable limitation**.* Indeed, in the twice-mentioned letter to Godel, Post characterizes his incompleteness theorem “as a corollary of the existence of absolutely unsolvable problems”. (Godel [28], p. 170) He describes then also how the detailed analysis of his proof of the unsolvability result as sketched above, once the consistency of the logic and the meaning of the relevant *Entscheidungsproblem* have been granted, leads “to a definite yes or no answer to the enunciation that the assumed logic failed to decide”. He therefore concluded:

that mathematical proof was *essentially creative* in that once having set up a formal system relative to say the above Entscheidungsproblem we could then always transcend that system, i.e. add to the set of assertions relative to the same body of enunciations—a conclusion I believe also reached in your work. (Godel [28], pp. 170-71, our emphasis)

The enunciation to be added can actually be effectively constructed, given the appropriate technical set up.^{21} A mathematical and restrictive understanding of creativeness is clear, but let us also point out that our parallel reading of the informal concept is supported in *Anticipation**:* footnote 7 consists of just the following sequence of words: “Produced, created—in practice, written down”; it is attached to the word “generated” (according to rules) and is to make that word’s meaning clear. In sum, we have reached a restrictive understanding of creativeness and how it can be viewed as a natural complement to the limitation of mathematical thinking.

Before discussing this issue further, we may ask, why generated sets should play such a central and exclusive role as instruments for solving combinatory problems. In *Anticipation**,* pages 2-3, the issue is described in its proper conceptual context, and this context gives also a first hint as to the restrictive character of the generative process.^{22} According to Post, recursiveness, Л-definability and even Turing- computability were introduced, to capture effective calculability. His own work, in contrast, attempts to capture the informal notion of generated sets for the following reason: ^{[7]} ^{[8]} ^{[9]}

This [notion of generated sets] derives from the idea of a *symbolic logic* rather than that of an algorithm, and may be described by saying that each member of the set is at some time generated by the continued application of a given method, while that method will at no time yield an individual ... not in the set. *(Anticipation,* p. 3, our emphasis)

We saw in Sect. 7.3, how canonical systems of forms A and *B* were used to give precise, rule-based descriptions of significant fragments of *Principia Mathematica**, *namely, sentential and predicate logic. Post assumed that the full system of *Principia Mathematica* could be described in a similar way and, furthermore, that it would be syntactically complete. Thus, the finiteness problem would be solved, as in the case of sentential logic, if an obviously decidable criterion for provability could be found. This line of thought made it strategically appropriate to focus on generating theorems and to work on simplifying the production rules. In this way, Post was led first to normal systems and then to the reversal of his whole program, having discovered the unsolvability of the decision problem for all normal systems. For the sake of its broader significance, the reversal required the generalization for generated sets.

The *inescapable limitation of human mathematics* is exemplified, as we saw, by the absolute unsolvability of a particular combinatorial problem. That is the rock bottom of Post’s analysis of the incompleteness phenomenon and the ultimate grounding for his appeal to return to *meaning* and *truth*, as well as to use an open concept of *proof**.* These three notions, freed from a reliance on formal procedures, are involved in the argument for the creativeness of human mathematics, and Post believes that these developments will effect “a reversal of the entire axiomatic trend of the late 19th and early 20th centuries”. So it is crucial to grasp Post’s reasons for viewing the combinatorial problem as *absolutely* unsolvable—for *Homo Sapiens Mathematicus**. *In Sect. 7.6 we explore Post’s way of securing a natural law and thus the basis for the claim of *absolute* unsolvability; it was expressed by Post repeatedly, but most directly in his letter to Godel: “... the absolute unsolvability of that problem [the above combinatorial problem] has but a basis in the nature of physical induction at least in my work and I still think in any work.” (Godel [28], p. 171) We assume that the adjective “physical” is simply meant to contrast this form of (“ordinary” scientific) induction from mathematical induction; it is the physical induction that is used to support a natural law.

Note to the reader. The next two parts take on the difficult and genuinely challenging task to disentangle two strands in Post’s thinking about the central methodological issue. There is, on the one hand, the *investigation of symbol complexes and mechanical operations* on them; this seems to be motivated by the finitary character of symbolic logics. There is, on the other hand, the *ambition to ground the finiteness and discreteness assumptions* concerning such logics in structural features of the human mind or, rather, self-consciousness. The task is made even more difficult by the fact that the considerations concerning the ambitious grounding are presented through the fragmentary excerpts in the Appendix to *Anticipation**;* see footnote 26 below. Our analysis is just a beginning.

- [1] The full sentence is this: “Our remaining ‘theorems’ deserve that name only in the sense that acomplete mathematical proof thereof clearly can be given—as contrasted with our generalizationof §7”.
- [2] The footnotes were added by Post at the time of writing the Anticipation paper in the late 1930s
- [3] and early 1940s. They were not part of his original notes from the 1920s.
- [4] This explains why the requirement on L was not weakened in case (S, P) is an assertion of L:“There is no reason for doing so since by suitably adjoining K to such a weak L the stronger Lwould result.” (Anticipation, p. 53).
- [5] Godel formulated the first incompleteness theorem in its full generality as pertaining to all consistent formal systems containing some elementary number theory most strikingly in 1964 in his [26],the Postscriptum to his Princeton Lecture Notes. For the “precise and unquestionably adequate”characterization of formal systems he appealed to Turing’s and Post’s work. He wrote there: “Aformal system can simply be defined by any mechanical procedure for producing formulas, calledprovable formulas.”.
- [6] At this very spot Post remarks (Anticipation, p. 55) that his conclusion goes contrary to theviewpoint of C. I. Lewis as it was reported above in Sect. 7.2. Furthermore, he mentions that it is“not so much contrary to Russell’s viewpoint (since he does not fully express himself)” and thatit is “in line with Bergson’s Creative Evolution”. Post is not correct with his remark on Lewis,as the latter had a more sophisticated understanding of mathematics than expressed through theprogrammatic heterodox view; see (Lewis [34], pp.359-361).
- [7] One particularly fitting meaning for counterpart is articulated as follows: “One of two parts whichfit and complete each other; a person or a thing forming a natural complement to another.”.
- [8] The various features mentioned in the informal discussion found their way into the definition of a“creative set” of natural numbers in (Post [45], p. 295). Post envisions on page 296 not only a finite,but indeed transfinite iteration of this extending process. The iteration along Kleene’s constructiveordinals is actually carried out in (Davis [9], p. 190) continuing work in (Davis [8]). The statementadded to a particular system S is the Godel sentence G for S. Assuming that S satisfies the standardrepresentability and derivability conditions, G is equivalent to the consistency statement for S. Theresults, for this type of extension, from Feferman’s [20] progressions of theories (and Turing’s [57]ordinal logics) can be directly transferred to the Post-Davis construction.
- [9] Clearly, Post’s discussion excludes sets definable by generalized inductive definitions, likeKleene’s O, as generated sets, as they require a “rule” with infinitely many premises.