Hostname: page-component-cd9895bd7-8ctnn Total loading time: 0 Render date: 2024-12-25T02:34:57.392Z Has data issue: false hasContentIssue false
  • English
  • Français

The graph-theoretic approach to descriptive set theory

Published online by Cambridge University Press:  05 September 2014

Benjamin D. Miller
Benjamin D. Miller*
Affiliation:
Institut für Mathematische Logik und Grundlagenforschung, Fachbereich Mathematik und Informatik, Universität Münster, Einsteinstraße 62, 48149 Münster, Germany E-mail: [email protected], URL: http://wwwmath.uni-muenster.de/u/ben.miller
Get access Rights & Permissions [Opens in a new window]

Abstract

We sketch the ideas behind the use of chromatic numbers in establishing descriptive set-theoretic dichotomy theorems.

Keywords

Primary 03E15secondary 28A05.Coloringsdescriptive set theorydichotomy theorems.
Type
Articles
Information
Bulletin of Symbolic Logic , Volume 18 , Issue 4 , December 2012 , pp. 554 - 575
Copyright
Copyright © Association for Symbolic Logic 2012

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] Alexandroff, P. S., Sur la puissance des ensembles measurables B, Comptes Rendu Mathématiques des Académie des Sciences. Paris, vol. 162 (1916), pp. 323–325.Google Scholar
[2] Burgess, John P., A reflection phenomenon in descriptive set theory, Polska Akademia Nauk. Fundamenta Mathematicae, vol. 104 (1979), no. 2, pp. 127–139.Google Scholar
[3] Caicedo, A. E. and Ketchersid, R. O., G0 dichotomies in natural models of AD+ , preprint, 2011.Google Scholar
[4] Caicedo, Andrés Eduardo, Clemens, John Daniel, Conley, Clinton Taylor, and Miller, Benjamin David, Definability of small puncture sets, Fundamenta Mathematicae, vol. 215 (2011), no. 1, pp. 39–51.Google Scholar
[5] Cantor, Georg, Über eine Eigenschaft des Inbegriffes aller reellen algebraischen Zahlen, Journal für die Reine und Angewandte Mathematik, vol. 77 (1874), pp. 258–262.Google Scholar
[6] Cantor, Georg, Über unendliche, lineare Punktmannigfaltigkeiten. VI, Mathematische Annalen, vol. 23 (1884), pp. 210–246.Google Scholar
[7] Cohen, Paul, The independence of the continuum hypothesis, Proceedings ofthe National Academy of Sciences of the United States of America, vol. 50 (1963), pp. 1143–1148.Google Scholar
[8] Cohen, Paul, The independence of the continuum hypothesis. II, Proceedings of the National Academy of Sciences of the United States of America, vol. 51 (1964), pp. 105–110.Google Scholar
[9] Effros, Edward G., Transformation groups and C*-algebras, Annals of Mathematics. Second Series, vol. 81 (1965), pp. 38–55.Google Scholar
[10] Feng, Qi, Homogeneity for open partitions of pairs of reals, Transactions of the American Mathematical Society, vol. 339 (1993), no. 2. pp. 659–684.CrossRefGoogle Scholar
[11] Glimm, James, Type I C*-algebras. Annals of Mathematics. Second Series, vol. 73 (1961), pp. 572–612.CrossRefGoogle Scholar
[12] Gödel, Kurt, The consistency of the Continuum Hypothesis, Annals of Mathematics Studies, no. 3, Princeton University Press, Princeton, N. J., 1940.Google Scholar
[13] Harrington, L. A., Kechris, A. S., and Louveau, A., A Glimm–Effros dichotomy for Borel equivalence relations. Journal of the American Mathematical Society, vol. 3 (1990), no. 4, pp. 903–928.CrossRefGoogle Scholar
[14] Harrington, Leo, A powerless proof of Silver's theorem, unpublished notes, 1976.Google Scholar
[15] Harrington, Leo, Marker, David, and Shelah, Saharon. Borel orderings. Transactions of the American Mathematical Society, vol. 310 (1988), no. 1, pp. 293–302.CrossRefGoogle Scholar
[16] Hausdorff, F., Die Mächtigkeit der Borelschen Mengen, Mathematische Annalen, vol. 77 (1916), no. 3, pp. 430–437.Google Scholar
[17] Hilbert, David, Mathematical problems, Bulletin of the American Mathematical Society, vol. 8 (1902), no. 10, pp. 437–479.Google Scholar
[18] Hjorth, Greg, Selection theorems and treeability, Proceedings of the American Mathematical Society, vol. 136 (2008), no. 10, pp. 3647–3653.Google Scholar
[19] Kanovei, Vladimir, Two dichotomy theorems on colourability of non-analytic graphs, Fundamenta Mathematicae, vol. 154 (1997), no. 2. pp. 183–201.CrossRefGoogle Scholar
[20] Kanovei, Vladimir, When a partial Borel order is linearizable, Fundamenta Mathematicae, vol. 155 (1998), no. 3, pp. 301–309.Google Scholar
[21] Kechris, A. S., Solecki, S., and Todorcevic, S., Borel chromatic numbers, Advances in Mathematics, vol. 141 (1999), no. 1, pp. 1–44.Google Scholar
[22] Kechris, Alexander S., Classical descriptive set theory, Graduate Texts in Mathematics, vol. 156, Springer-Verlag, New York, 1995.Google Scholar
[23] Lecomte, Dominique, A dichotomy characterizing analytic digraphs of uncountable Borel chromatic number in any dimension, Transactions of the American Mathematical Society, vol. 361 (2009), no. 8, pp. 4181–4193.Google Scholar
[24] Miller, Arnold W., Descriptive set theory and forcing, Lecture Notes in Logic, vol. 4, Springer-Verlag, Berlin, 1995.Google Scholar
[25] Miller, B. D., Dichotomy theorems for countably infinite dimensional analytic hypergraphs, Annals of Pure and Applied Logic, vol. 162 (2011), no. 7, pp. 561–565.Google Scholar
[26] Shelah, Saharon, On co-κ-Souslin relations, Israel Journal of Mathematics, vol. 47 (1984), no. 2-3, pp. 139–153.Google Scholar
[27] Silver, Jack H., Counting the number of equivalence classes of Borel and coanalytic equivalence relations, Annals of Mathematical Logic, vol. 18 (1980), no. 1, pp. 1–28.Google Scholar
[28] Souslin, M. Ya., Sur une définition des ensembles mesurables B sans nombres transfinis, Comptes Rendu Mathématiques de l'Académie des Sciences. Paris, vol. 164 (1917), pp. 88–91.Google Scholar
[29] Srivastava, S. M., A course on Borel sets, Graduate Texts in Mathematics, vol. 180, Springer-Verlag, New York, 1998.Google Scholar
[30] van Engelen, Fons, Kunen, Kenneth, and Miller, Arnold W., Two remarks about analytic sets, Set theory and its applications, Lecture Notes in Mathematics, vol. 1401, Springer, Berlin, 1989, pp. 68–72.Google Scholar