Hostname: page-component-586b7cd67f-g8jcs Total loading time: 0 Render date: 2024-11-23T23:08:46.706Z Has data issue: false hasContentIssue false
  • English
  • Français

Cores of Π11 sets of reals

Published online by Cambridge University Press:  12 March 2014

Andreas Blass  and
Douglas Cenzer
Andreas Blass
Affiliation:
University of Michigan, Ann Arbor, Michigan 48104
Douglas Cenzer
Affiliation:
University of Florida, Gainesville, Florida 32601
Get access Rights & Permissions [Opens in a new window]

Extract

A classical result of descriptive set theory expresses every co-analytic subset of the real line as the union of an increasing sequence of Borel sets, the length of the chain being at most the first uncountable ordinal ℵ1 (see [5], [8]). An effective analog of this theorem, obtained by replacing co-analytic (Π11) and Borel (Δ11) with their lightface analogs, would represent every Π11 subset of the real line as the union of a chain of Δ11 sets. No such analog is true, however, because some Δ11 sets are not the union of their Δ11 subsets. For example, the set W, consisting of those reals which code well-orderings (in some standard coding) is Π11, but, by the boundedness principle ([3], [9]), any Δ11 subset of W contains codes only for well-orderings shorter than ω1, the first nonrecursive ordinal. Accordingly, we define the core of a Π11 set to be the union of its Δ11 subsets; clearly this is the largest subset of the given Π11 set for which an effective version of the classical representation could exist.

In §1, we develop the elementary properties of cores of Π11 sets. For example, such a core is itself Π11 and can be represented as the union of a chain of Δ11 sets in a natural way; the chain will have length at most ω1. We show that the core of a Π11 set is “almost all” of the set, while on the other hand there are uncountable Π11 sets with empty cores.

Type
Research Article
Information
The Journal of Symbolic Logic , Volume 39 , Issue 4 , December 1974 , pp. 649 - 654
Copyright
Copyright © Association for Symbolic Logic 1974

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] Cenzer, D., Inductively defined sets of reals, Bulletin of the American Mathematical Society (to appear).Google Scholar
[2] Cenzer, D., Monotone inductive definitions over the continuum (to appear).Google Scholar
[3] Cenzer, D., Ordinal recursion and inductive definitions, Generalized recursion theory, Oslo 1972 (Fenstad, J. E. and Hinman, P., Editors) North-Holland, Amsterdam, 1974, pp. 221–264.Google Scholar
[4] Hinman, P., Recursion-theoretic hierarchies, Springer-Verlag, Berlin and New York (to appear).Google Scholar
[5] Kuratowski, K., Topologie, Monografie Matematyczne, Warsaw, 1950.Google Scholar
[6] Rogers, H., Theory of recursive functions and effective computability, McGraw-Hill, New York, 1967.Google Scholar
[7] Sacks, G., Measure-theoretic uniformity, Transactions of the American Mathematical Society, vol. 142 (1969), pp. 381–420.Google Scholar
[8] Solovay, R., On the cardinality of Σ2 1 sets of reals, Foundations of mathematics, Springer-Verlag, New York, 1969.Google Scholar
[9] Spector, C., Recursive well-orderings, this Journal, vol. 20 (1955), pp. 151–163.Google Scholar
[10] Tanaka, H., Notes on measure and category in recursion theory, Annals of the Japan Association for Philosophy of Science, vol. 3 (1970), pp. 231–241.Google Scholar
[11] Thomason, S. K., The forcing method and the upper semilattice of hyperdegrees, Transactions of the American Mathematical Society, vol. 129 (1967), pp. 38–57.Google Scholar