We prove that a Borel equivalence relation is classifiable by countable structures if and only if it is Borel reducible to a countable level of the hereditarily countable sets. We also prove the following result which was originally claimed in [FS89]: the zero density ideal of sets of natural numbers is not classifiable by countable structures.
@article{bwmeta1.element.bwnjournal-article-fmv164i1p61bwm,
author = {Harvey Friedman},
title = {Borel and Baire reducibility},
journal = {Fundamenta Mathematicae},
volume = {163},
year = {2000},
pages = {61-69},
language = {en},
url = {http://dml.mathdoc.fr/item/bwmeta1.element.bwnjournal-article-fmv164i1p61bwm}
}
Friedman, Harvey. Borel and Baire reducibility. Fundamenta Mathematicae, Tome 163 (2000) pp. 61-69. http://gdmltest.u-ga.fr/item/bwmeta1.element.bwnjournal-article-fmv164i1p61bwm/
[00000] [BK96] H. Becker and A. S. Kechris, The Descriptive Set Theory of Polish Group Actions, London Math. Soc. Lecture Note Ser. 232, Cambridge Univ. Press, 1996. | Zbl 0949.54052
[00001] [DJK94] R. Dougherty, S. Jackson and A. S. Kechris, The structure of hyperfinite Borel equivalence relations, Trans. Amer. Math. Soc. 341 (1994), 193-225. | Zbl 0803.28009
[00002] [Fr81] H. Friedman, On the necessary use of abstract set theory, Adv. Math. 41 (1981), 209-280. | Zbl 0483.03030
[00003] [FS89] H. Friedman and L. Stanley, A Borel reducibility theory for classes of countable structures, J. Symbolic Logic 54 (1989), 894-914. | Zbl 0692.03022
[00004] [HKL90] L. A. Harrington, A. S. Kechris and A. Louveau, A Glimm-Effros dichotomy for Borel equivalence relations, J. Amer. Math. Soc. 3 (1990), 903-928. | Zbl 0778.28011
[00005] [Hj] G. Hjorth, Classification and orbit equivalence relations, preprint. | Zbl 0942.03056
[00006] [Hj98] G. Hjorth, An absoluteness principle for Borel sets, J. Symbolic Logic 63 (1998), 663-693. | Zbl 0909.03042
[00007] [HK97] G. Hjorth and A. S. Kechris, New dichotomies for Borel equivalence relations, Bull. Symbolic Logic 3 (1997), 329-346. | Zbl 0889.03038
[00008] [HKL98] G. Hjorth, A. S. Kechris and A. Louveau, Borel equivalence relations induced by actions of the symmetric group, Ann. Pure Appl. Logic 92 (1998), 63-112. | Zbl 0930.03058
[00009] [Ke94] A. S. Kechris, Classical Descriptive Set Theory, Grad. Texts in Math. 156, Springer, 1994.
[00010] [Ke] A. S. Kechris, Actions of Polish groups and classification problems, preprint.
[00011] [Sc65] D. Scott, Logic with denumerably long formulas and finite strings of quantifiers, in: Theory of Models, J. W. Addison, L. Henkin and A. Tarski (eds.), North-Holland, Amsterdam, 1965, 329-341.
[00012] [Si99] S. G. Simpson, Subsystems of Second Order Arithmetic, Perspect. Math. Logic, Springer, 1999.