##Question

Suppose $A,X$ are computable well-orderings. Say that $A$ is $X$-unsimplifiable if there is no computable well-ordering $B$ whose ordertype is strictly less than that of $A$ but such that Duplicator has a computable winning strategy in the Ehrenfeucht-Fraisse game on $A$ and $B$ of length $X$.

(See below for the definition of these games.)

My question is:

Is there any computable well-ordering $X$ such that there are $X$-unsimplifiable computable well-orderings of ordertype arbitrarily large below $\omega_1^{CK}$?

If we drop the requirement that the winning strategies for Duplicator be computable, the answer is of course negative (this is an easy generalization about the usual results on elementary equivalence of ordinals). But that argument is extremely non-effective - basically, we have to guess at which intervals in $A$ are "large," and that can't be done computably.

I suspect that the answer is yes, and indeed that $X$-unsimplifiable $A$s exist for every $X$ of sufficiently large ordertype (say, $\ge\omega^2$). However, I don't see how to prove it; in particular, when I try to build such an $A$ for a given $X$ I keep winding up with an ill-founded linear order.

##Details of the game $EF_X(A,B)$

Players Challenger and Duplicator alternately pick individual elements of $A$ or $B$ - for simplicity, we assume they have disjoint domains - with Challenger going first and on each turn Duplicator picking from whichever of the two structures Challenger did not pick from. Additionally, on each of their moves Challenger plays an element of $X$ smaller than all elements of $X$ played up to that point; basically, $X$ functions as a "clock" which eventually runs out (since $X$ is a well-ordering).

Once Challenger has no legal moves, the game ends. The winner is determined as follows: a pair of tuples $\overline{a}\in A$ and $\overline{b}\in B$ have been built by Challenger and Duplicator at this point, and Duplicator wins iff the structures $(A;\overline{a})$ and $(B;\overline{b})$ satisfy the same atomic sentences.

Question

Suppose $A,X$ are computable well-orderings. Say that $A$ is $X$-unsimplifiable if there is no computable well-ordering $B$ whose ordertype is strictly less than that of $A$ but such that Duplicator has a computable winning strategy in the Ehrenfeucht-Fraisse game on $A$ and $B$ of length $X$.

(See below for the definition of these games.)

My question is:

Is there any computable well-ordering $X$ such that there are $X$-unsimplifiable computable well-orderings of ordertype arbitrarily large below $\omega_1^{CK}$?

If we drop the requirement that the winning strategies for Duplicator be computable, the answer is of course negative (this is an easy generalization about the usual results on elementary equivalence of ordinals). But that argument is extremely non-effective - basically, we have to guess at which intervals in $A$ are "large," and that can't be done computably.

I suspect that the answer is yes, and indeed that $X$-unsimplifiable $A$s exist for every $X$ of sufficiently large ordertype (say, $\ge\omega^2$). However, I don't see how to prove it; in particular, when I try to build such an $A$ for a given $X$ I keep winding up with an ill-founded linear order.

Details of the game $EF_X(A,B)$

Players Challenger and Duplicator alternately pick individual elements of $A$ or $B$ - for simplicity, we assume they have disjoint domains - with Challenger going first and on each turn Duplicator picking from whichever of the two structures Challenger did not pick from. Additionally, on each of their moves Challenger plays an element of $X$ smaller than all elements of $X$ played up to that point; basically, $X$ functions as a "clock" which eventually runs out (since $X$ is a well-ordering).

Once Challenger has no legal moves, the game ends. The winner is determined as follows: a pair of tuples $\overline{a}\in A$ and $\overline{b}\in B$ have been built by Challenger and Duplicator at this point, and Duplicator wins iff the structures $(A;\overline{a})$ and $(B;\overline{b})$ satisfy the same atomic sentences.