Hostname: page-component-745bb68f8f-l4dxg Total loading time: 0 Render date: 2025-01-22T08:50:38.621Z Has data issue: false hasContentIssue false
  • English
  • Français

Which number theoretic problems can be solved in recursive progressions on Π11-paths through O?

Published online by Cambridge University Press:  12 March 2014

G. Kreisel
G. Kreisel*
Affiliation:
Stanford University, Stanford, California 94305
Get access Rights & Permissions [Opens in a new window]

Extract

This note is an addendum to an incompleteness result of Feferman and Spector [1]: for any such progression satisfying the (natural) conditions listed in [1] there is a true Π10-formula which cannot be derived in the progression. The idea of their proof yields a stronger result.

If each numerical instance A[x/n] of the formula A (with the free numerical variable x) is decided in a recursive progression along a Π11-path then the set {n: ⊦ A[x/n]} is recursive.

In other words, only recursively solvable problems are decidable in such progressions. This yields the incompleteness result of [1] when specialized to some Π10 formula A which defines a nonrecursive set, since then some instance A[x/n] must be undecided and A[x/n] is a closed Π10 formula. The stronger result is needed to extend Church's thesis for total functions reckonable in formal systems to (total) functions reckonable in recursive progressions onΠ11-paths. A partially reckonable function always has a Π11 graph (and if its graph is Δ11 then it is by C. Jockusch, r.e.; so some Π11 sets are not partially reckonable). The relevance of these facts for the model of mathematical reasoning provided by (variants of) Turing's ordinal logics is analyzed in (b) (ii) of Part II, which goes into our current knowledge about Church's thesis.

Type
Research Article
Information
The Journal of Symbolic Logic , Volume 37 , Issue 2 , June 1972 , pp. 311 - 334
Copyright
Copyright © Association for Symbolic Logic 1972

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

REFERENCES

[1]Feferman, S. and Spector, C., Incompleteness along paths in progressions of theories, this Journal, vol. 27 (1962), pp. 383–390.Google Scholar
[2]Friedbero, R. M. and Rogers, H., Reducibility and completeness of sets of integers, Zeitschrift für mathematische Logik und Grundlagen der Mathematik, vol. 5 (1959), pp. 117–125.CrossRefGoogle Scholar
[3]Gandy, R. O., The concept of computability, Scientific thought 1900–1960, Clarendon Press, Oxford, 1969, pp. 1–4.Google Scholar
[4]Kreisel, G., Mathematical logic: what has it done for the philosophy of mathematics, Bertrand Russell, philosopher of the century, Academic Press, London, 1967, pp. 201–272, 315–316.Google Scholar
[5]Kreisel, G., Hubert's programme and the search for automatic proof procedures, Springer Lecture Notes, vol. 125 (1970), pp. 128–146; reviewed in Zentralblatt für Mathematik und ihre Grenzgebiete, vol. 206 (1971), pp. 277–278.CrossRefGoogle Scholar
[6]Kreisel, G., A Church's thesis: A kind of reducibility axiom for constructive mathematics, Intuitionism and proof theory, North-Holland, Amsterdam, 1970, pp. 121–150; reviewed in Zentralblatt für Mathematik und ihre Grenzgebiete, vol. 199 (1971), pp. 300–301.Google Scholar
[7]Kreisel, G., Some reasons for generalizing recursion theory, Logic Colloquium '69, North-Holland, Amsterdam, 1971, pp. 139–198; reviewed in Zentralblatt für Mathematik und ihre Grenzgebiete, vol. 219 (1972), pp. 17–19.CrossRefGoogle Scholar
[8]Kreisel, G., A survey of proof theory. II, Proceedings of the Second Scandinavian Logic Symposium, North-Holland, Amsterdam, 1971, pp. 109–170. Corrections. P. 147, 1. 14, replace by the stronger principleCrossRefGoogle Scholar
[9]Turing, A. M., On computable numbers, with an application to the Entscheidungsproblem, Proceedings of the London Mathematical Society, vol. 42 (1936/1937), pp. 230–265.Google Scholar
[10]Feferman, S., Transfinite recursive progressions of axiomatic theories, this Journal, vol. 27 (1962), pp. 259–316.Google Scholar
[11]Barendregt, H. P., Supplementary part II of dissertation, Utrecht, 1971.Google Scholar
[12]Troelstra, A. S., Principles of intuitionism, Springer Lecture Notes, vol. 95 (1969).Google Scholar
[13]Troelstra, A. S., Notions of realizability for intuitionistic arithmetic and intuitionistic arithmetic in all finite types, Proceedings of the Second Scandinavian Logic Symposium, North-Holland, Amsterdam, 1971, pp. 369–405.CrossRefGoogle Scholar