Download PDF - Borel and Baire reducibilityAll rights reserved. Copyright exceptions and limitations apply

ArticleOriginal scientific text

Title

Borel and Baire reducibility

Authors 1

Affiliations

  1. Department of Mathematics, Ohio State University, Columbus, OH 43210, U.S.A.

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.

Bibliography

  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.
  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.
  3. [Fr81] H. Friedman, On the necessary use of abstract set theory, Adv. Math. 41 (1981), 209-280.
  4. [FS89] H. Friedman and L. Stanley, A Borel reducibility theory for classes of countable structures, J. Symbolic Logic 54 (1989), 894-914.
  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.
  6. [Hj] G. Hjorth, Classification and orbit equivalence relations, preprint.
  7. [Hj98] G. Hjorth, An absoluteness principle for Borel sets, J. Symbolic Logic 63 (1998), 663-693.
  8. [HK97] G. Hjorth and A. S. Kechris, New dichotomies for Borel equivalence relations, Bull. Symbolic Logic 3 (1997), 329-346.
  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.
  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.
Fundamenta Mathematicae
2000/164/1
Export to PBN, Opens in new tab
Pages:
61-69
Main language of publication
English
Received
1999-05-25
Accepted
1999-09-02
Published
2000
Exact and natural sciences