We show that part I of the uniform Martin’s conjecture follows from a local phenomenon, namely that every non-constant uniformly Turing invariant f : [x]_T → [y]_T satisfies x ≤_T y. Besides improving our knowledge about part I of the uniform Martin’s conjecture (which turns out to be equivalent to Turing determinacy), the discovery of such local phenomenon also leads to new results that did not look strictly related to Martin’s conjecture before. In particular, we get that computable reducibility ≤_c on equivalence relations on N has a very complicated structure, as ≤_T is Borel reducible to it. We conclude by raising the question: Is part II of the uniform Martin’s conjecture implied by local phenomena, too? and briefly indicating possible directions.

Uniform martin’s conjecture, locally

Bard V.
First
2020-01-01

Abstract

We show that part I of the uniform Martin’s conjecture follows from a local phenomenon, namely that every non-constant uniformly Turing invariant f : [x]_T → [y]_T satisfies x ≤_T y. Besides improving our knowledge about part I of the uniform Martin’s conjecture (which turns out to be equivalent to Turing determinacy), the discovery of such local phenomenon also leads to new results that did not look strictly related to Martin’s conjecture before. In particular, we get that computable reducibility ≤_c on equivalence relations on N has a very complicated structure, as ≤_T is Borel reducible to it. We conclude by raising the question: Is part II of the uniform Martin’s conjecture implied by local phenomena, too? and briefly indicating possible directions.
2020
148
12
5369
5380
https://arxiv.org/abs/1907.10766
Computable reducibility; Martin’s conjecture; Uniformly invariant functions
Bard V.
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/2318/1788079
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 2
  • ???jsp.display-item.citation.isi??? 2
social impact