Proof of that there is no uniform proof of the Effective Dushnik-Miller conjecture.

45 Views Asked by At

I'm a little confused by Theorem 5.23 in Rod Downey's "Computability Theory and Linear Orderings." Specifically, I'm not sure how he constructs such an A (meeting the requirements $R_e$ seems to make $A$ a counterexample to the effective D-M conjecture) and how constructing such an $A$ is supposed to demonstrate that the effective D-M conjecture has no uniform proof? Thanks for any help you can give in understanding this proof. For concreteness, the statement is:

There is no uniform procedure which, when given a computable linear ordering $A$ produces a computable $B \cong A$ such that if $A$ contains no strongly $\eta$-like interval then $B$ has no nontrivial computable self-embedding.

Note that, to him, a uniform procedure turns the computable set $W_e$ into the computable set $W_{f(e)}$ via a computable $f$. To do this, he says:

We build an infinite $(A, \leq)$ such that $A$ has no strongly $\eta$-like intervals and we meet the requirements "$R_e \colon$ if $W_e \cong A$ then $(W_e, \leq)$ has a nontrivial computable self-embedding." The result will then follow by use of the recursion theorem.

Wouldn't this requirements make $A$ a counter-example to Effective Dushnik-Miller? Again, thanks so much for helping, and let me know if anything I wrote is unclear!