Skip to main content Accessibility help

We use cookies to distinguish you from other users and to provide you with a better experience on our websites. Close this message to accept cookies or find out how to manage your cookie settings.

Close cookie message
×
Hostname: page-component-745bb68f8f-v2bm5 Total loading time: 0 Render date: 2025-02-12T08:46:05.373Z Has data issue: false hasContentIssue false

Early investigations of the degrees of Borel sets

from PART III - WADGE DEGREES AND POINTCLASSES

Published online by Cambridge University Press:  05 December 2011

By
William W. Wadge
Edited by
Alexander S. Kechris ,
Benedikt Löwe  and
John R. Steel
Alexander S. Kechris
Affiliation:
California Institute of Technology, Pasadena
Benedikt Löwe
Affiliation:
Universiteit van Amsterdam
John R. Steel
Affiliation:
University of California, Berkeley
Get access

Summary

In this paper, I give an overview/summary of the techniques used, and the results derived, in my 1984 PhD dissertation, Reducibility and Determinateness on the Baire Space. In particular, I focus on the calculation of the order type (and structure) of the collection of degrees of Borel sets.

§1 Introduction. I would like in this article to present a overview of the main results of my PhD dissertation, and of the game and other techniques used to derive them.

My first thought was to print the entire dissertation but I quickly realized that it was too long—about ten times too long! Hopefully, this condensed version will still be useful. In producing such a drastically shortened account, I have omitted detailed proofs, and many less important or intermediate results. Also, the remaining definitions and results are for the most part given informally.

In writing this I have in mind, first, colleagues (whether in Mathematics or Computing) who are not familiar with descriptive set theory but nevertheless would like to learn about “Wadge Degrees”. To make the material accessible to these readers I have included some basic information about, say, Borel sets that will be very familiar to Cabal insiders. However, my hope is that even experts in descriptive set theory may learn something, if not about my results, at least about the manner in which they were discovered. In particular, I would like to give some ‘classic’ notions, such as Boolean set operations, the attention they deserve.

Type
Chapter
Information
Wadge Degrees and Projective Ordinals , pp. 166 - 196
Publisher: Cambridge University Press
Print publication year: 2011

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

Addison, John W. [Add54] On Certain Points of the Theory of Recursive Functions, Ph.D. thesis, University of Wisconsin–Madison, 1954.Google Scholar
Wadge, William W. [Add04] Tarski's theory of definability: common themes in descriptive set theory, recursive function theory, classical pure logic, and finite-universe logic, Annals of Pure and Applied Logic, vol. 126 (2004), no. 1–3, pp. 77–92.Google Scholar
Barnes, John F. [Bar65] The classification of the closed-open and the recursive sets of number theoretic functions, Ph.D. thesis, UC Berkeley, 1965.Google Scholar
Davis, Morton [Dav64] Infinite games of perfect information, Advances in game theory (Dresher, Melvin, Shapley, Lloyd S., and Tucker, Alan W., editors), Annals of Mathematical Studies, vol. 52, 1964, pp. 85–101.Google Scholar
Hausdorff, Felix [Hau57] Set theory, Chelsea, New York, 1957, translated by Aumann, J. R..Google Scholar
Kantorovich, L. and Livenson, E. [KL32] Memoir on the analytical operations and projective sets I, Fundamenta Mathematicae, vol. 18 (1932), pp. 214–279.CrossRefGoogle Scholar
Kleene, Stephen C. [Kle50] A symmetric form of Gödel's theorem, Indagationes Mathematicae, vol. 12 (1950), pp. 244–246.Google Scholar
Kuratowski, Casimir [Kur58] Topologie. Vol. I, 4ème ed., Matematyczne, Monografie, vol. 20, Państwowe Wydawnictwo Naukowe, Warsaw, 1958.Google Scholar
Luzin, Nikolai [Luz30] Leçons sur les ensembles analytiques et leurs applications, Collection de monographies sur la théorie des fonctions, Gauthier-Villars, Paris, 1930.Google Scholar
Martin, Donald A. [Mar70] Measurable cardinals and analytic games, Fundamenta Mathematicae, vol. 66 (1970), pp. 287–291.Google Scholar
Martin, Donald A. [Mar75] Borel determinacy, Annals of Mathematics, vol. 102 (1975), no. 2, pp. 363–371.CrossRefGoogle Scholar
Mycielski, Jan and Steinhaus, Hugo [MS62] A mathematical axiom contradicting the axiom of choice, Bulletin de l'Académie Polonaise des Sciences, vol. 10 (1962), pp. 1–3.Google Scholar
Rogers, Hartley [Rog59] Computing degrees of unsolvability, Mathematische Annalen, vol. 138 (1959), pp. 125–140.CrossRefGoogle Scholar
Steel, John R. [Ste81B] Determinateness and the separation property, The Journal of Symbolic Logic, vol. 46 (1981), no. 1, pp. 41–44.CrossRefGoogle Scholar
Suslin, Mikhail Ya. [Sus17] Sur une définition des ensembles mesurables B sans nombres transfinis, Comptes Rendus Hebdomadaires des Séances de l'Académie des Sciences, vol. 164 (1917), pp. 88–91.Google Scholar
Tarski, Alfred [Tar00] Address at the Princeton University Bicentennial Conference on Problems of Mathematics (December 17–19, 1946), The Bulletin of Symbolic Logic, vol. 6 (2000), no. 1, pp. 1–44.Google Scholar
Veblen, Oswald [Veb08] Continuous increasing functions of finite and transfinite ordinals, Transactions of the American Mathematical Society, vol. 9 (1908), no. 3, pp. 280–292.CrossRefGoogle Scholar
Wadge, William W. [Wad84] Reducibility and determinateness on the Baire space, Ph.D. thesis, University of California, Berkeley, 1984.Google Scholar
Zermelo, Ernst [Zer13] Über eine Anwendung der Mengenlehre auf die Theorie des Schachspiels, Proceedings of the Fifth International Congress of Mathematicians (Hobson, E. W. and Love, A. E. H., editors), vol. 2, 1913, pp. 501–504.Google Scholar

Save book to Kindle

To save this book to your Kindle, first ensure [email protected] is added to your Approved Personal Document E-mail List under your Personal Document Settings on the Manage Your Content and Devices page of your Amazon account. Then enter the ‘name’ part of your Kindle email address below. Find out more about saving to your Kindle.

Note you can select to save to either the @free.kindle.com or @kindle.com variations. ‘@free.kindle.com’ emails are free but can only be saved to your device when it is connected to wi-fi. ‘@kindle.com’ emails can be delivered even when you are not connected to wi-fi, but note that service fees apply.

Find out more about the Kindle Personal Document Service.

Available formats
×

Save book to Dropbox

To save content items to your account, please confirm that you agree to abide by our usage policies. If this is the first time you use this feature, you will be asked to authorise Cambridge Core to connect with your account. Find out more about saving content to Dropbox.

Available formats
×

Save book to Google Drive

To save content items to your account, please confirm that you agree to abide by our usage policies. If this is the first time you use this feature, you will be asked to authorise Cambridge Core to connect with your account. Find out more about saving content to Google Drive.

Available formats
×