Hostname: page-component-586b7cd67f-t7fkt Total loading time: 0 Render date: 2024-11-28T15:27:41.089Z Has data issue: false hasContentIssue false
  • English
  • Français

Countable functionals and the projective hierarchy

Published online by Cambridge University Press:  12 March 2014

Dag Normann
Dag Normann*
Affiliation:
University of Oslo, Oslo, Norway
Get access Rights & Permissions [Opens in a new window]

Extract

Kleene [7] and Kreisel [8] defined independently the countable (continuous) functionals. Kleene [7] defined the countable functionals of type k to be total functionals of type k acting in a continuous way when restricted to countable arguments of type k − 1. He also defined the associates for countable functionals. They are functions α: N → N containing information about how the functional acts on countable arguments. Kleene [7] showed that the countable functionals are closed under the computations derived from S1–S9 of his paper [6], and that every computable functional has a recursive associate.

Kreisel defined the continuous functionals to be equivalence-classes of associates. By his definition it is meaningless to let a continuous functional act upon anything but continuous arguments.

One disadvantage of Kleene's approach is that two different functionals may have the same associates We will later see that there may be two functionals φ1 and φ2 with the same associates but such that the relations

are not the same.

In more recent papers on the countable functionals it is normal to regard the hierarchy 〈Ct(k)〉kϵN of countable functionals as a type-structure such that the functionals in Ct(k + 1) are maps from Ct(k) to N(Ct(0) = N), see e.g. Bergstra [1] and Gandy and Hyland [3].

We will then enjoy the streamlined formalism of a type-structure in which S1–S9 have meaning, but avoid the ambiguities of Kleene's original approach.

We will presuppose a brief familiarity with the theory of the countable functionals.

Type
Research Article
Information
The Journal of Symbolic Logic , Volume 46 , Issue 2 , June 1981 , pp. 209 - 215
Copyright
Copyright © Association for Symbolic Logic 1981

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]Bergstra, J., Computability and continuity infinite types, Thesis, University of Utrecht, 1976.Google Scholar
[2]Bergstra, J., 1-envelopes of continuous functionals, Recursive function theory, Newsletter, no. 16 (1977), item 196.Google Scholar
[3]Gandy, R. O. and Hyland, J. M. E., Computable and recursively countable functions of higher type, Logic Colloquium '76 (Gandy, R. O. and Hylands, J. M. E., Editors), North-Holland, Amsterdam, 1977, pp. 407–438.Google Scholar
[4]Hyland, J. M. E., Filter spaces and continuous functionals, Annals of Mathematical Logic, vol. 16 (1979), pp. 101–143.CrossRefGoogle Scholar
[5]Hyland, J. M. E., The intrinsic recursion theory on the countable or continuous functionals, Generalized recursion theory. II (Fenstad, J. E., Gandy, R. O. and Sacks, G. E., Editors), North-Holland, Amsterdam, 1978, pp. 135–145.Google Scholar
[6]Kleene, S. C., Recursive functionals and quantifiers of finite types. I, Transactions of the American Mathematical Society, vol. 91 (1959), pp. 1–52; II, vol. 108 (1963), pp. 106–142.Google Scholar
[7]Kleene, S. C., Countable functionals, Constructivity in mathematics (Heyting, A., Editor), North-Holland, Amsterdam, 1959, pp. 87–100.Google Scholar
[8]Kreisel, G., Interpretation of analysis by means of constructive functionals of finite types, Constructivity in mathematics (Heyting, A., Editor), North-Holland, Amsterdam, 1959, pp. 101–128.Google Scholar
[9]Moldestad, J. and Normann, D., Models for recursion theory, this Journal, vol. 41 (1976), pp. 719–729.Google Scholar
[10]Normann, D., A continuous functional with noncollapsing hierarchy, this Journal, vol. 43 (1978), pp. 487–491.Google Scholar
[11]Normann, D., Countable functionals and the analytic hierarchy, Preprint no. 17, University of Oslo, 1977.Google Scholar
[12]Normann, D., Non-obtainable continuous functionals, Proceedings of the Sixth International Congress of Logic, Methodology and Philosophy of Science, Hannover, 1979 (to appear).Google Scholar
[13]Normann, D., Recursion on the countable functionals, Lecture Notes in Mathematics, no. 811, Springer-Verlag, Heidelberg, 1980.Google Scholar
[14]Normann, D. and Wainer, S.S., The 1-section of a countable functional, Preprint no. 4, University of Oslo, 1978; this Journal, vol. 45 (1980), pp. 549–562.Google Scholar
[15]Rogers, H. Jr., Theory of recursive functions and effective computability, McGraw-Hill, New York, 1967.Google Scholar
[16]Sacks, G.E., Degrees of unsolvability, Annals of Mathematical Studies, Princeton University Press, Princeton, NJ, 1963.Google Scholar
[17]Sacks, G.E., The l-section of a type-n object, Generalized recursion theory (Fenstad, J. E. and Hinman, P. G., Editors), North-Holland, Amsterdam, 1974, pp. 81–93.Google Scholar
[18]Sacks, G.E., The k-section of a type-n object, American Journal of Mathematics, vol. 99 (1977), pp. 901–917.CrossRefGoogle Scholar
[19]Shoenfield, J. R., Degrees of unsolvability, Mathematics Studies 2, North-Holland, Amsterdam and American Elsevier, New York, 1971.Google Scholar