8
$\begingroup$

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.

Improve this question
$\endgroup$
3
  • $\begingroup$ I think $n$ is $1+\log_2 n$-unsimplifiable. (Thinking of $k$-unsimplifiable as "revealed in time $k$" basically.) If the analogy holds then I guess $X\ge\omega$ is enough... $\endgroup$
    – Bjørn Kjos-Hanssen
    Commented Jan 8, 2020 at 8:09
  • $\begingroup$ Or need a weird sense in which $2^{\omega^2}=\omega_1^{CK}$ $\endgroup$
    – Bjørn Kjos-Hanssen
    Commented Jan 8, 2020 at 8:26
  • $\begingroup$ $n$ is $1+\log_2 n$-unsimplifiable for finite $n$. Fix any order $B$, $|A|>|B|$. Ch picks $a_1\in A$ near the middle of $A$. Then Du picks some $b_1\in B$. Either (i) $|A_{<a_1}|>|B_{<b_1}|$ or (ii) $|A_{>a_1}|>|B_{>b_1}|$. Ch picks $a_2<a_1$, near the middle of $A_{<a_1}$, in case (i), and $a_2>a_1$, near the middle of $A_{>a_2}$, in case (ii). Continuing, we maintain the property that $|A_{<a_k}|>|B_{<b_k}|$ or $|A_{>a_k}|>|B_{>b_k}|$. So Ch always goes where Du has little room left. Eventually Du runs out of room. Ch picks the greatest element of $X$ not yet picked. $\endgroup$
    – Bjørn Kjos-Hanssen
    Commented Jan 8, 2020 at 18:46

0

Reset to default

You must log in to answer this question.

Browse other questions tagged .