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?

  • $\begingroup$ ZF+DC+AC is just ZFC. $\endgroup$
    – Asaf Karagila
    Jul 10 '17 at 7:18
  • $\begingroup$ Sorry, that was a typo: I meant AD, the axiom of determinacy. $\endgroup$
    – V. Bard
    Jul 10 '17 at 7:39
  • $\begingroup$ That makes way more sense! :) $\endgroup$
    – Asaf Karagila
    Jul 10 '17 at 7:41
  • $\begingroup$ We don't even know whether any part of MC is consistent with ZF. $\endgroup$
    – 喻 良
    Sep 15 '17 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
    Sep 16 '17 at 8:14

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}$.

  • $\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
    Sep 25 '17 at 9:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.