Uniformity, universality, and computability theory

DOI10.1142/S0219061317500039zbMATH Open1420.03121arXiv1606.01976OpenAlexW3106146772MaRDI QIDQ5268400FDOQ5268400

Andrew S. Marks

Publication date: 20 June 2017

Published in: Journal of Mathematical Logic (Search for Journal in Brave)

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.

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

zbMATH Keywords

computability theoryBorel reducibilityBorel equivalence relationsMartin's conjectureuniversal countable Borel equivalence relationsMartin measureuniformity, descriptive set theory

Mathematics Subject Classification ID

Other Turing degree structures (03D28) Descriptive set theory (03E15)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Topics in orbit equivalence
• On Groups of Measure Preserving Transformations. I
• Ergodic Equivalence Relations, Cohomology, and Von Neumann Algebras. I
• On Groups of Measure Preserving Transformations. II
• JSL volume 79 issue 2 Cover and Back matter
• The Structure of Hyperfinite Borel Equivalence Relations
• The axiom of determinateness and reduction principles in the analytical hierarchy
• A Glimm-Effros Dichotomy for Borel Equivalence Relations
• Linear algebraic groups and countable Borel equivalence relations
• Analytic determinacy and 0^#
• Measurable cardinals and analytic games
• \(\ell^2\) invariants of equivalence relations and groups
• COUNTABLE BOREL EQUIVALENCE RELATIONS
• Canonical Ramsey theory on Polish spaces
• Borel chromatic numbers
• Higher set theory and mathematical practice
• Popa superrigidity and countable Borel equivalence relations
• Martin's conjecture and strong ergodicity
• Conjugacy equivalence relation on subgroups
• Universal Borel actions of countable groups
• New Directions in Descriptive Set Theory
• Structurable equivalence relations
• On non-singular transformations of a measure space. I
• Rigidity theorems for actions of product groups and countable Borel equivalence relations
• On the complexity of the isomorphism relation for finitely generated groups
• On Suborderings of Degrees of Recursive Unsolvability
• Borel structurability on the 2-shift of a countable group
• A determinacy approach to Borel combinatorics
• Turing determinacy and the continuum hypothesis
• The complexity of the classification of Riemann surfaces and complex manifolds
• CALIBRATING DETERMINACY STRENGTH IN LEVELS OF THE BOREL HIERARCHY
• Martin's conjecture, arithmetic equivalence, and countable Borel equivalence relations

Cited In (9)

• Hyperfiniteness and Borel combinatorics
• Title not available (Why is that?)
• Borel structurability by locally finite simplicial complexes
• Equivalence of generics
• Title not available (Why is that?)
• FORCING CONSTRUCTIONS AND COUNTABLE BOREL EQUIVALENCE RELATIONS
• Expressing uniformity via oracles
• Measurable graph combinatorics
• The uniform Martin’s conjecture for many-one degrees

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)