15
$\begingroup$

By Kechris' conjecture (KC) I mean the assertion that Turing equivalence $\equiv_T$ is a universal countable Borel equivalence relation. On the other hand, Martin's conjecture (MC) is a long-lasting conjecture about the set of Turing invariant functions as preordered by $$ f\le_m g\iff f(x)\le_T g(x) \text{ on a Turing cone}. $$ Roughly speaking, MC says that this structure is as simple as possible. For an introduction to MC, see e.g. https://arxiv.org/pdf/1109.1875.pdf

MC and KC are usually presented as completely contraposed conjectures; in fact, it is well known that if Turing equivalence is universal, then there are Borel Turing-invariant functions which are neither constant on a cone nor increasing on a cone (see https://arxiv.org/pdf/math/0001173.pdf at page 4). So, it is provable in ZF + DC that if KC is true, then part 1 of MC is false, even in its weaker "Borel" formulation.

My question is: does anyone know of any contradiction arising from KC and the second part of MC?

$\endgroup$
5
  • $\begingroup$ ZF+DC+AC is just ZFC. $\endgroup$
    – Asaf Karagila
    Commented Jul 10, 2017 at 7:18
  • $\begingroup$ Sorry, that was a typo: I meant AD, the axiom of determinacy. $\endgroup$
    – V. Bard
    Commented Jul 10, 2017 at 7:39
  • $\begingroup$ That makes way more sense! :) $\endgroup$
    – Asaf Karagila
    Commented Jul 10, 2017 at 7:41
  • $\begingroup$ We don't even know whether any part of MC is consistent with ZF. $\endgroup$
    – 喻 良
    Commented Sep 15, 2017 at 6:11
  • $\begingroup$ @喻良 You're right. What I was really asking is whether any contradiction arising from MC2+KC is known. Maybe I'm going to edit my question to make it clearer. $\endgroup$
    – V. Bard
    Commented Sep 16, 2017 at 8:14

1 Answer 1

2
$\begingroup$

This doesn't answer the question, but it cannot be that KC is true and $\leq_m$ is a prewellordering for all the Borel Turing invariant which are not constant a cone (not just the increasing ones). This is because as we show below, this implies there is a $\Delta^1_2$ wellordering of $\mathbb{R}$ (contradicting AD or AC+large cardinals).

We prove the claim: suppose $\equiv_T$ was a universal countable Borel equivalence relation, let $=_\mathbb{R}$ be the equality relation on $\mathbb{R}$, and consider the relation $=_\mathbb{R} \times \equiv_T$ which must be Borel reducible to $\equiv_T$ via some Borel reduction $f$. For each $x \in \mathbb{R}$, let $f_x$ be the Borel Turing invariant function where $f_x(y) = f((x,y))$. These $f_x$ are not constant one a cone and if $x \neq x'$, then for all $y$, $f_x(y) \not \equiv_T f_{x'}(y)$ (because $f$ is a Borel reduction). Hence, the functions $f_x$ are all distinct under $\leq_m$ which wellorders them. So the ordering $x \leq x'$ iff $f_x \leq_m f_{x'}$ is a $\Delta^1_2$ wellordering of $\mathbb{R}$.

$\endgroup$
1
  • $\begingroup$ Unfortunately, this requires both parts of MC: the functions $f_x$ need not be increasing on a cone if we don't assume part 1 of MC. $\endgroup$
    – V. Bard
    Commented Sep 25, 2017 at 9:04

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .