Dichotomy theorems for families of non-cofinal essential complexity

DOI10.1016/J.AIM.2016.08.044MaRDI QIDQ329489zbMATHOpenAlexFDO

Authors John D. Clemens, Dominique Lecomte, Benjamin D. Miller

Publication date 21 October 2016

Published in Advances in Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1412.8684

zbMATH Keywords

smoothcomplexitydichotomyequivalence relation

Mathematics Subject Classification ID

Classes of sets (Borel fields, (sigma)-rings, etc.), measurable sets, Suslin sets, analytic sets (28A05) Descriptive set theory (03E15)

Abstract: We prove that for every Borel equivalence relation $E$, either $E$ is Borel reducible to $mathbb{E}_0$, or the family of Borel equivalence relations incompatible with $E$ has cofinal essential complexity. It follows that if $F$ is a Borel equivalence relation and $calF$ is a family of Borel equivalence relations of non-cofinal essential complexity which together satisfy the dichotomy that for every Borel equivalence relation $E$, either $EincalF$ or $F$ is Borel reducible to $E$, then $calF$ consists solely of smooth equivalence relations, thus the dichotomy is equivalent to a known theorem.

Recommendations

• Completeness for nondeterministic complexity classes
• Generalized theorems on relationships among reducibility notions to certain complexity classes
• Hard-core theorems for complexity classes
• Expressibility and Nonuniform Complexity Classes
• Some complexity results about essential closed sets
• Khutoretskii's theorem for generalized computable families
• A full complexity dichotomy for immanant families
• Refining Nondeterminism in Relativizations of Complexity Classes
• Some results on the complexity of families of sets
• A note on almost-everywhere-complex sets and separating deterministic- time-complexity classes

Cites work

• scientific article; zbMATH DE number 722611 (Why is no real title available?)
• A Glimm-Effros Dichotomy for Borel Equivalence Relations
• Borel equivalence relations induced by actions of the symmetric group
• Counting the number of equivalence classes of Borel and coanalytic equivalence relations
• Ergodic Equivalence Relations, Cohomology, and Von Neumann Algebras. I
• Essential countability of treeable equivalence relations
• Selection theorems and treeability
• The Structure of Hyperfinite Borel Equivalence Relations
• The classification of hypersmooth Borel equivalence relations

Cited in

(2)

• Acyclicity and reduction
• Relative primeness and Borel partition properties for equivalence relations

This page was built for publication: Dichotomy theorems for families of non-cofinal essential complexity

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q329489)