Hostname: page-component-8448b6f56d-qsmjn Total loading time: 0 Render date: 2024-04-25T04:44:01.244Z Has data issue: false hasContentIssue false
  • English
  • Français

Monotone inductive definitions over the continuum

Published online by Cambridge University Press:  12 March 2014

Douglas Cenzer
Douglas Cenzer*
Affiliation:
University of Florida, Gainesville, Florida 32601
Get access Rights & Permissions [Opens in a new window]

Extract

Monotone inductive definitions occur frequently throughout mathematical logic. The set of formulas in a given language and the set of consequences of a given axiom system are examples of (monotone) inductively defined sets. The class of Borel subsets of the continuum can be given by a monotone inductive definition. Kleene's inductive definition of recursion in a higher type functional (see [6]) is fundamental to modern recursion theory; we make use of it in §2.

Inductive definitions over the natural numbers have been studied extensively, beginning with Spector [11]. We list some of the results of that study in §1 for comparison with our new results on inductive definitions over the continuum. Note that for our purposes the continuum is identified with the Baire space ωω.

It is possible to obtain simple inductive definitions over the continuum by introducing real parameters into inductive definitions over N—as in the definition of recursion in [5]. This is itself an interesting concept and is discussed further in [4]. These parametric inductive definitions, however, are in general weaker than the unrestricted set of inductive definitions, as is indicated below.

In this paper we outline, for several classes of monotone inductive definitions over the continuum, solutions to the following characterization problems:

(1) What is the class of sets which may be given by such inductive definitions ?

(2) What is the class of ordinals which are the lengths of such inductive definitions ?

These questions are made more precise below. Most of the results of this paper were announced in [2].

Type
Research Article
Information
The Journal of Symbolic Logic , Volume 41 , Issue 1 , March 1976 , pp. 188 - 198
Copyright
Copyright © Association for Symbolic Logic 1976

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] Blass, A. and Cenzer, D., Cores of Π1 1 sets of reals, this Journal, vol. 39 (1974), pp. 649–654.Google Scholar
[2] Cenzer, D., Inductively defined sets of reals, Bulletin of the American Mathematical Society, vol. 80 (1974), pp. 485–487.CrossRefGoogle Scholar
[3] Cenzer, D., Ordinal recursion and inductive definitions, Generalized recursion theory (Fenstad, J. and Hinman, P., Editors), North-Holland, Amsterdam, 1974, pp. 221–264.Google Scholar
[4] Cenzer, D., Parametric inductive definitions and recursive operators over the continuum, Fundamenta Mathematicae (1976).Google Scholar
[5] Hinman, P., Recursion-theoretic hierarchies, Springer-Verlag, Berlin and New York, 1976.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.Google Scholar
[7] Moschovakis, Y. N., Determinacy and prewellorderings of the continuum, Mathematical logic and foundations of set theory (Bar-Hillel, , Editor), North Holland, Amsterdam, 1970, pp. 24–62.Google Scholar
[8] Moschovakis, Y. N., Abstract first order computability. II, Transactions of the American Mathematical Society, vol. 188 (1969), pp. 427–504.Google Scholar
[9] Moschovakis, Y. N., Elementary induction on abstract structures, North-Holland, Amsterdam, 1974.Google Scholar
[10] Moschovakis, Y. N., Structural characterizations of classes of relations, General recursion theory, North-Holland, Amsterdam, 1974, pp. 53–79.Google Scholar
[11] Spector, C., Inductively defined sets of natural numbers, Infinitlstic methods, Pergamon, Oxford, 1961, pp. 97–102.Google Scholar