Skip to main content
Added reference
Source Link
V. Bard
  • 151
  • 5

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). HenceSo, if KCit is true (provablyprovable in ZF + DC + AD)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?

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. Hence, if KC is true (provably in ZF + DC + AD), 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?

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?

deleted 5 characters in body
Source Link
V. Bard
  • 151
  • 5

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 of }x. $$$$ 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. Hence, if KC is true (provably in ZF + DC + AD), 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?

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 of }x. $$ 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. Hence, if KC is true (provably in ZF + DC + AD), 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?

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. Hence, if KC is true (provably in ZF + DC + AD), 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?

added 56 characters in body
Source Link
V. Bard
  • 151
  • 5

By Kechris' conjecture (KC) I mean the assertion that Turing equivalence $\equiv_T$ is a universal countable Borel equivalence relation. It 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 of }x. $$ 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. SoHence, if Kechris' conjectureKC is true (provably in ZF + DC + AD), then part 1 of Martin's conjectureMC is false, even in its weaker "Borel" formulation.

These two conjectures are usually presented as completely contraposed, being two extremely different way of imaginating the structure of the set of Turing-invariant functions preordered by $\le_m$.

My question is: could it be that the universalitydoes anyone know of any contradiction arising from KC and the $\equiv_T$ is in fact consistent withsecond part 2 of Martin's conjecture, i.e. with the statement that the set of Turing-invariant functions which are increasing on a cone is prewellordered by $\le_m$MC?

By Kechris' conjecture I mean the assertion that Turing equivalence $\equiv_T$ is a universal countable Borel equivalence relation. 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. So, if Kechris' conjecture is true (provably in ZF + DC + AD), then part 1 of Martin's conjecture is false, even in its weaker "Borel" formulation.

These two conjectures are usually presented as completely contraposed, being two extremely different way of imaginating the structure of the set of Turing-invariant functions preordered by $\le_m$.

My question is: could it be that the universality of $\equiv_T$ is in fact consistent with part 2 of Martin's conjecture, i.e. with the statement that the set of Turing-invariant functions which are increasing on a cone is prewellordered by $\le_m$?

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 of }x. $$ 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. Hence, if KC is true (provably in ZF + DC + AD), 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?

edited tags
Link
V. Bard
  • 151
  • 5
Loading
edited body
Source Link
V. Bard
  • 151
  • 5
Loading
edited tags
Link
V. Bard
  • 151
  • 5
Loading
Source Link
V. Bard
  • 151
  • 5
Loading