AMS eBook CollectionsOne of the world's most respected mathematical collections, available in digital format for your library or institution
Classes of Polish spaces under effective Borel isomorphism
About this Title
Vassilios Gregoriades, Technische Universität Darmstadt, Fachbereich Mathematik, Arbeitsgruppe Logik, Schloßgartenstraße 7, 64289 Darmstadt, Germany
Publication: Memoirs of the American Mathematical Society
Publication Year:
2016; Volume 240, Number 1135
ISBNs: 978-1-4704-1563-1 (print); 978-1-4704-2822-8 (online)
DOI: https://doi.org/10.1090/memo/1135
Published electronically: October 9, 2015
Keywords: Recursively presented metric space,
effective Borel isomorphism,
$\Delta ^1_1$ isomorphism,
$\Delta ^1_1$ injection,
Kleene space,
Spector-Gandy space.
MSC: Primary 03E15, 03D30, 03D60
Table of Contents
Chapters
- Preface
- 1. Introduction
- 2. The spaces $\mathcal {N}^{T}$
- 3. Kleene spaces
- 4. Characterizations of $\mathcal {N}$ up to $\Delta ^1_1$ isomorphism
- 5. Spector-Gandy spaces
- 6. Questions and related results
Abstract
We study the equivalence classes under $\Delta ^1_1$ isomorphism, otherwise effective Borel isomorphism, between complete separable metric spaces which admit a recursive presentation and we show the existence of strictly increasing and strictly decreasing sequences as well as of infinite antichains under the natural notion of $\Delta ^1_1$-reduction, as opposed to the non-effective case, where only two such classes exist, the one of the Baire space and the one of the naturals. A key tool for our study is a mapping $T \mapsto \mathcal {N}^{T}$ from the space of all trees on the naturals to the class of Polish spaces, for which every recursively presented space is $\Delta ^1_1$-isomorphic to some $\mathcal {N}^{T}$ for a recursive $T$, so that the preceding spaces are representatives for the classes of $\Delta ^1_1$ isomorphism. We isolate two large categories of spaces of the type $\mathcal {N}^{T}$, the Kleene spaces and the Spector-Gandy spaces and we study them extensively. Moreover we give results about hyperdegrees in the latter spaces and characterizations of the Baire space up to $\Delta ^1_1$ isomorphism.- Jon Barwise, Infinitary logic and admissible sets, J. Symbolic Logic 34 (1969), no. 2, 226–252. MR 406760, DOI 10.2307/2271099
- Jon Barwise, Admissible sets and structures, Springer-Verlag, Berlin-New York, 1975. An approach to definability theory; Perspectives in Mathematical Logic. MR 0424560
- Stephen Binns, A splitting theorem for the Medvedev and Muchnik lattices, MLQ Math. Log. Q. 49 (2003), no. 4, 327–335. MR 1987431, DOI 10.1002/malq.200310034
- L. E. J. Brouwer, Beweis, dass jede volle Function gleichmäßig stetig ist, Konin. Neder. Akad. van Weten.te Amst. Proc. 27 (1924), 189–193, reprinted in L. E. J. Brouwer, Collected Works, vol. 1, North-Holland, Amsterdam, 1975.
- Stephen Binns and Stephen G. Simpson, Embeddings into the Medvedev and Muchnik lattices of $\Pi ^0_1$ classes, Arch. Math. Logic 43 (2004), no. 3, 399–414. MR 2052891, DOI 10.1007/s00153-003-0195-x
- C. T. Chong and Liang Yu, Recursion Theory: The Syntax and Structure of Definability, In preparation.
- Gabriel Debs, Effective properties in compact sets of Borel functions, Mathematika 34 (1987), no. 1, 64–68. MR 908840, DOI 10.1112/S0025579300013280
- S. Feferman, Some applications of the notions of forcing and generic sets, Fund. Math. 56 (1964/65), 325–345. MR 176925, DOI 10.4064/fm-56-3-325-345
- Ekaterina B. Fokina, Sy-David Friedman, and Asger Törnquist, The effective theory of Borel equivalence relations, Ann. Pure Appl. Logic 161 (2010), no. 7, 837–850. MR 2601014, DOI 10.1016/j.apal.2009.10.002
- Harvey M. Friedman, Borel sets and hyperdegrees, J. Symbolic Logic 38 (1973), 405–409. MR 335248, DOI 10.2307/2273034
- R. O. Gandy, On a problem of Kleene’s, Bull. Amer. Math. Soc. 66 (1960), 501–502.
- R. O. Gandy, Proof of Mostowski’s conjecture, Bull. Acad. Polon. Sci. Sér. Sci. Math. Astronom. Phys. 8 (1960), 571–575 (English, with Russian summary). MR 126383
- Peter M. Gerdes, Harrington’s solution to McLaughlin’s conjecture and non-uniform self-moduli, Preprint, 27 pages, 15 December 2010, arXiv:1012.3427v1, submitted for publication.
- V. Gregoriades and Y. N. Moschovakis, Notes on Effective Descriptive Set Theory, In preparation.
- Vassilios Gregoriades, Turning Borel sets into clopen sets effectively, Fund. Math. 219 (2012), no. 2, 119–143. MR 2993469, DOI 10.4064/fm219-2-4
- R. O. Gandy and G. E. Sacks, A minimal hyperdegree, Fund. Math. 61 (1967), 215–223. MR 225653, DOI 10.4064/fm-61-2-215-223
- Joseph Arthur Harrison, SOME APPLICATIONS OF RECURSIVE PSEUDO-WELL ORDERINGS, ProQuest LLC, Ann Arbor, MI, 1966. Thesis (Ph.D.)–Stanford University. MR 2615958
- Joseph Harrison, Recursive pseudo-well-orderings, Trans. Amer. Math. Soc. 131 (1968), 526–543. MR 244049, DOI 10.1090/S0002-9947-1968-0244049-7
- L. Harrington, Mclaughlin’s conjecture, 1976, Handwritten Notes.
- Peter G. Hinman, Some applications of forcing to hierarchy problems in arithmetic, Z. Math. Logik Grundlagen Math. 15 (1969), 341–352. MR 280376, DOI 10.1002/malq.19690152004
- Greg Hjorth, Universal co-analytic sets, Proc. Amer. Math. Soc. 124 (1996), no. 12, 3867–3873. MR 1343698, DOI 10.1090/S0002-9939-96-03494-6
- Carl G. Jockusch, Jr. and Robert I. Soare, Encodability of Kleene’s $O$, J. Symbolic Logic 38 (1973), 437–440.
- Alexander S. Kechris, Classical descriptive set theory, Graduate Texts in Mathematics, vol. 156, Springer-Verlag, New York, 1995. MR 1321597
- Alexander S. Kechris, Measure and category in effective descriptive set theory, Ann. Math. Logic 5 (1972/73), 337–384. MR 369072, DOI 10.1016/0003-4843(73)90012-0
- Takayuki Kihara, Incomputability of simply connected planar continua, Computability 1 (2012), no. 2, 131–152. MR 3064226, DOI 10.3233/com-12012
- S. C. Kleene, On notation for ordinal numbers, J. Symbolic Logic 3 (1938), 150–155.
- S. C. Kleene, Recursive predicates and quantifiers, Trans. Amer. Math. Soc. 53 (1943), 41–73.
- S. C. Kleene, Arithmetical predicates and function quantifiers, Trans. Amer. Math. Soc. 79 (1955), 312–340. MR 70594, DOI 10.1090/S0002-9947-1955-0070594-4
- S. C. Kleene, Hierarchies of number-theoretic predicates, Bull. Amer. Math. Soc. 61 (1955), 193–213.
- S. C. Kleene, On the forms of the predicates in the theory of constructive ordinals. II, Amer. J. Math. 77 (1955), 405–428. MR 70595, DOI 10.2307/2372632
- Motokiti Kondô, L’uniformisation des complémentaires analytiques, Proc. Imp. Acad. Tokyo 13 (1937), no. 8, 287–291 (French). MR 1568473
- S. C. Kleene and Emil L. Post, The upper semi-lattice of degrees of recursive unsolvability, Ann. of Math. (2) 59 (1954), 379–407. MR 61078, DOI 10.2307/1969708
- G. Kreisel, Analysis of the Cantor-Bendixson theorem by means of the analytic hierarchy, Bull. Acad. Polon. Sci. Sér. Sci. Math. Astr. Phys. 7 (1959), 621–626. (unbound insert) (English, with Russian summary). MR 0118673
- G. Kreisel, Set theoretic problems suggested by the notion of potential totality. , Infinitistic Methods (Proc. Sympos. Foundations of Math., Warsaw, 1959) Pergamon, Oxford; Państwowe Wydawnictwo Naukowe, Warsaw, 1961, pp. 103–140. MR 0146073
- G. Kreisel, Some axiomatic results on second order arithmetic,, 1963, Seminar notes, Stanford Univ., Stanford, Calif.
- Kinjiro Kunugui, Sur un problème de M. E. Szpilrajn, Proc. Imp. Acad. Tokyo 16 (1940), 73–78 (French). MR 1819
- H. Lebesgue, Sur les fonctions represéntables analytiquement, Journal de Mathématiques $6^\textrm {e}$ serie 1 (1905), 139–216.
- Alain Louveau, A separation theorem for $\Sigma ^{1}_{1}$ sets, Trans. Amer. Math. Soc. 260 (1980), no. 2, 363–378. MR 574785, DOI 10.1090/S0002-9947-1980-0574785-X
- N. Lusin and W. Sierpinski, Sur un ensemble non measurable B, Journal de Mathématiques $9^\textrm {e}$ serie 2 (1923), 53–72.
- N. Lusin, Sur les ensembles non measurables B et l’emploi de la diagonale de Cantor, Comptes Rendus Acad. Sci. Paris 181 (1925), 95–96.
- Richard Mansfield, Perfect subsets of definable sets of real numbers, Pacific J. Math. 35 (1970), 451–457. MR 280380
- Werner Markwald, Zur Theorie der konstruktiven Wohlordnungen, Math. Ann. 127 (1954), 135–149 (German). MR 61076, DOI 10.1007/BF01361115
- Donald A. Martin, Proof of a conjecture of Friedman, Proc. Amer. Math. Soc. 55 (1976), no. 1, 129. MR 406785, DOI 10.1090/S0002-9939-1976-0406785-9
- Yiannis N. Moschovakis, Elementary induction on abstract structures, North-Holland Publishing Co., Amsterdam-London; American Elsevier Publishing Co., Inc., New York, 1974. Studies in Logic and the Foundations of Mathematics, Vol. 77. MR 0398810
- Yiannis N. Moschovakis, Descriptive set theory, 2nd ed., Mathematical Surveys and Monographs, vol. 155, American Mathematical Society, Providence, RI, 2009. MR 2526093
- Yiannis N. Moschovakis, Kleene’s amazing second recursion theorem, Bull. Symbolic Logic 16 (2010), no. 2, 189–239. MR 2675490, DOI 10.2178/bsl/1286889124
- Hartley Rogers Jr., Theory of recursive functions and effective computability, 2nd ed., MIT Press, Cambridge, MA, 1987. MR 886890
- Gerald E. Sacks, The recursively enumerable degrees are dense, Ann. of Math. (2) 80 (1964), 300–312. MR 166089, DOI 10.2307/1970393
- Gerald E. Sacks, Measure-theoretic uniformity in recursion theory and set theory, Trans. Amer. Math. Soc. 142 (1969), 381–420.
- Gerald E. Sacks, Higher recursion theory, Perspectives in Mathematical Logic, Springer-Verlag, Berlin, 1990. MR 1080970
- Stephen G. Simpson, Implicit definability in arithmetic, submitted for publication.
- Stephen G. Simpson, Minimal covers and hyperdegrees, Trans. Amer. Math. Soc. 209 (1975), 45–64.
- Stephen G. Simpson, Mass problems and randomness, Bull. Symbolic Logic 11 (2005), no. 1, 1–27.
- Clifford Spector, Recursive well-orderings, J. Symbolic Logic 20 (1955), 151–163. MR 74347, DOI 10.2307/2266902
- Clifford Spector, On degrees of recursive unsolvability, Ann. of Math. (2) 64 (1956), 581–592.
- Clifford Spector, Measure-theoretic construction of incomparable hyperdegrees, J. Symbolic Logic 23 (1958), 280–288. MR 112830, DOI 10.2307/2964288
- C. Spector, Hyperarithmetical quantifiers, Fund. Math. 48 (1959/60), 313–320. MR 120147, DOI 10.4064/fm-48-3-313-320
- Hisao Tanaka, A basis result for $\Pi _{1}{}^{1}$-sets of postive measure, Comment. Math. Univ. St. Paul. 16 (1967/68), 115–127. MR 236017
- S. K. Thomason, The forcing method and the upper semilattice of hyperdegrees, Trans. Amer. Math. Soc. 129 (1967), 38–57. MR 219421, DOI 10.1090/S0002-9947-1967-0219421-0