Dichotomy theorems for families of non-cofinal essential complexity

DOI10.1016/J.AIM.2016.08.044zbMATH Open1423.03172arXiv1412.8684OpenAlexW2963318617MaRDI QIDQ329489FDOQ329489

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

Publication date: 21 October 2016

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

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.

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

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

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)

Cites Work

• Title not available (Why is that?)
• Ergodic Equivalence Relations, Cohomology, and Von Neumann Algebras. I
• The Structure of Hyperfinite Borel Equivalence Relations
• A Glimm-Effros Dichotomy for Borel Equivalence Relations
• The classification of hypersmooth Borel equivalence relations
• Borel equivalence relations induced by actions of the symmetric group
• Selection theorems and treeability
• Counting the number of equivalence classes of Borel and coanalytic equivalence relations
• Essential countability of treeable 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)