Uniformity, universality, and computability theory
From MaRDI portal
Publication:5268400
Abstract: We prove a number of results motivated by global questions of uniformity in computability theory, and universality of countable Borel equivalence relations. Our main technical tool is a game for constructing functions on free products of countable groups. We begin by investigating the notion of uniform universality, first proposed by Montalb'an, Reimann and Slaman. This notion is a strengthened form of a countable Borel equivalence relation being universal, which we conjecture is equivalent to the usual notion. With this additional uniformity hypothesis, we can answer many questions concerning how countable groups, probability measures, the subset relation, and increasing unions interact with universality. For many natural classes of countable Borel equivalence relations, we can also classify exactly which are uniformly universal. We also show the existence of refinements of Martin's ultrafilter on Turing invariant Borel sets to the invariant Borel sets of equivalence relations that are much finer than Turing equivalence. For example, we construct such an ultrafilter for the orbit equivalence relation of the shift action of the free group on countably many generators. These ultrafilters imply a number of structural properties for these equivalence relations.
Recommendations
Cites work
- scientific article; zbMATH DE number 3911340 (Why is no real title available?)
- scientific article; zbMATH DE number 4108753 (Why is no real title available?)
- scientific article; zbMATH DE number 702561 (Why is no real title available?)
- scientific article; zbMATH DE number 722611 (Why is no real title available?)
- scientific article; zbMATH DE number 1531923 (Why is no real title available?)
- scientific article; zbMATH DE number 1795300 (Why is no real title available?)
- scientific article; zbMATH DE number 218589 (Why is no real title available?)
- scientific article; zbMATH DE number 2204762 (Why is no real title available?)
- scientific article; zbMATH DE number 5785892 (Why is no real title available?)
- A Glimm-Effros Dichotomy for Borel Equivalence Relations
- A determinacy approach to Borel combinatorics
- Analytic determinacy and 0#
- Borel chromatic numbers
- Borel structurability on the 2-shift of a countable group
- CALIBRATING DETERMINACY STRENGTH IN LEVELS OF THE BOREL HIERARCHY
- COUNTABLE BOREL EQUIVALENCE RELATIONS
- Canonical Ramsey theory on Polish spaces
- Conjugacy equivalence relation on subgroups
- Ergodic Equivalence Relations, Cohomology, and Von Neumann Algebras. I
- Higher set theory and mathematical practice
- JSL volume 79 issue 2 Cover and Back matter
- Linear algebraic groups and countable Borel equivalence relations
- Martin's conjecture and strong ergodicity
- Martin's conjecture, arithmetic equivalence, and countable Borel equivalence relations
- Measurable cardinals and analytic games
- New Directions in Descriptive Set Theory
- On Groups of Measure Preserving Transformations. I
- On Groups of Measure Preserving Transformations. II
- On Suborderings of Degrees of Recursive Unsolvability
- On non-singular transformations of a measure space. I
- On the complexity of the isomorphism relation for finitely generated groups
- Popa superrigidity and countable Borel equivalence relations
- Rigidity theorems for actions of product groups and countable Borel equivalence relations
- Structurable equivalence relations
- The Structure of Hyperfinite Borel Equivalence Relations
- The axiom of determinateness and reduction principles in the analytical hierarchy
- The complexity of the classification of Riemann surfaces and complex manifolds
- Topics in orbit equivalence
- Turing determinacy and the continuum hypothesis
- Universal Borel actions of countable groups
- ^2 invariants of equivalence relations and groups
Cited in
(10)- Hyperfiniteness and Borel combinatorics
- scientific article; zbMATH DE number 2154080 (Why is no real title available?)
- Borel structurability by locally finite simplicial complexes
- The uniform Martin's conjecture for many-one degrees
- Equivalence of generics
- scientific article; zbMATH DE number 2167522 (Why is no real title available?)
- scientific article; zbMATH DE number 5064948 (Why is no real title available?)
- FORCING CONSTRUCTIONS AND COUNTABLE BOREL EQUIVALENCE RELATIONS
- Expressing uniformity via oracles
- Measurable graph combinatorics
This page was built for publication: Uniformity, universality, and computability theory
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5268400)
