August 17, 2025

Countable and finitary reductions on equivalence relations

MHMeng-Che HoCalifornia State University System SJStephen JacksonWeber State University SLSteffen LemppUniversité Claude Bernard Lyon 1

Key Points

The study identifies both the existence and non-existence of complete equivalence relations under various reductions, enhancing our understanding of equivalence relations.
Key findings demonstrate that both countable and finitary reductions can significantly impact the structure of equivalence relations in Baire and Cantor spaces.
Using methods from computability theory and descriptive set theory, the research draws connections between Borel equivalence relations and computable reducibility.
The implications of these results suggest a deeper understanding of the complexity and classification of equivalence relations within mathematical frameworks.

Abstract

Inspired by the very successful study of Borel equivalence relations under Borel reducibility in descriptive set theory and equivalence relations on ω under computable reducibility in computability theory, R. Miller defined a family of reducibility notions. Defined on equivalence relations on Baire space or Cantor space, these reducibilities are required to succeed (uniformly) on all finite or countable subsets of the whole space. In this paper, we combine methods from computability theory and descriptive set theory to study equivalence relations under these reductions. In particular, we show existence and non-existence of complete equivalence relations in various settings.

Perguntar à IA

Bookmark

View Full Paper