Borel and Baire reducibility

Harvey Friedman

Fundamenta Mathematicae (2000)

  • Volume: 164, Issue: 1, page 61-69
  • ISSN: 0016-2736

Abstract

top
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.

How to cite

top

Friedman, Harvey. "Borel and Baire reducibility." Fundamenta Mathematicae 164.1 (2000): 61-69. <http://eudml.org/doc/212448>.

@article{Friedman2000,
abstract = {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.},
author = {Friedman, Harvey},
journal = {Fundamenta Mathematicae},
keywords = {Borel equivalence relation; analytic equivalence relation; Borel reduction; Baire reduction},
language = {eng},
number = {1},
pages = {61-69},
title = {Borel and Baire reducibility},
url = {http://eudml.org/doc/212448},
volume = {164},
year = {2000},
}

TY - JOUR
AU - Friedman, Harvey
TI - Borel and Baire reducibility
JO - Fundamenta Mathematicae
PY - 2000
VL - 164
IS - 1
SP - 61
EP - 69
AB - 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.
LA - eng
KW - Borel equivalence relation; analytic equivalence relation; Borel reduction; Baire reduction
UR - http://eudml.org/doc/212448
ER -

References

top
  1. [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. Zbl0949.54052
  2. [DJK94] R. Dougherty, S. Jackson and A. S. Kechris, The structure of hyperfinite Borel equivalence relations, Trans. Amer. Math. Soc. 341 (1994), 193-225. Zbl0803.28009
  3. [Fr81] H. Friedman, On the necessary use of abstract set theory, Adv. Math. 41 (1981), 209-280. Zbl0483.03030
  4. [FS89] H. Friedman and L. Stanley, A Borel reducibility theory for classes of countable structures, J. Symbolic Logic 54 (1989), 894-914. Zbl0692.03022
  5. [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. Zbl0778.28011
  6. [Hj] G. Hjorth, Classification and orbit equivalence relations, preprint. Zbl0942.03056
  7. [Hj98] G. Hjorth, An absoluteness principle for Borel sets, J. Symbolic Logic 63 (1998), 663-693. Zbl0909.03042
  8. [HK97] G. Hjorth and A. S. Kechris, New dichotomies for Borel equivalence relations, Bull. Symbolic Logic 3 (1997), 329-346. Zbl0889.03038
  9. [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. Zbl0930.03058
  10. [Ke94] A. S. Kechris, Classical Descriptive Set Theory, Grad. Texts in Math. 156, Springer, 1994. 
  11. [Ke] A. S. Kechris, Actions of Polish groups and classification problems, preprint. 
  12. [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. 
  13. [Si99] S. G. Simpson, Subsystems of Second Order Arithmetic, Perspect. Math. Logic, Springer, 1999. 

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.