*This is a question which has been bothering me now for quite some time. I've talked to a number of people about it, and we've shown that a few basic ideas can't work, but other than that haven't made any progress. At this point it's making the switch from "interesting" to "deeply annoying," so I want to ask it here and get it out of my system if only so I can get back to my actual work:*

******

A *PAC tree* is a tree $\subseteq 2^{<\omega}$ which is computable, has no dead ends, and has no noncomputable paths. In http://www.math.uchicago.edu/~drh/Papers/Papers/primedec.pdf, Hirschfeldt showed (via a very beautiful short argument) that every noncomputable set $X$ computes a listing of the isolated paths through a given PAC tree.

There is a structural interpretation of this result, as follows. For a tree $T$, let $\mathcal{L}_T^{iso}$ be (the ordertype of) the isolated paths of $T$, ordered lexicographically. If $T$ is PAC, then $\mathcal{L}_T^{iso}$ is countable, and in particular scattered (since $T$ must have countably many paths); and Hirschfeldt's result implies that $\mathcal{L}_T^{iso}$ has a copy computable in every noncomputable set as long as $T$ is PAC.

This strongly suggests that every PAC linear ordering - that is, every linear ordering $\mathcal{L}$ which is isomorphic to $\mathcal{L}_T^{iso}$ for some PAC tree $T$ - has a computable copy. However, on the other hand, it is easy to show$^1$ that there is no computable function $f$ such that, if $e$ is an index for a PAC tree, then $f(e)$ is an index for the corresponding PAC order $\mathcal{L}_{\Phi_e}^{iso}$. This suggests there is not a very easy proof that every PAC order has a computable copy. So my question is:

> Does every PAC ordering has a computable copy?

*I'm certain that the answer is "yes": the existence of a linear order with no computable copy, which has a copy in every noncomputable degree, is a major open problem; more specifically, there are a number of results strongly suggesting that scattered linear orders cannot have such subtle computability-theoretic behavior, and every PAC order is scattered since PAC trees must have countably many paths and any tree with a dense set of paths embeds a perfect tree. Also, I can't extend the diagonalization to handle even **two** computable guessing functions, for reasons explained at the end of the proof below.*

REMARK: Hirschfeldt pointed out a broader class of orders that has similar properties. Call a tree $T\subseteq 2^{<\omega}$ *quasi-PAC* if for each node $\sigma\in T$, if there is a non-computable path through $\sigma$ then $T$ is perfect above $\sigma$. Then for any two noncomputable sets $X$, $Y$, the linear orders consisting of paths through $T$ picked out via Hirschfeldt's "coin-flipping" procedure using $X$ and using $Y$ are isomoprhic; so the *quasi-PAC orders* also all have copies in every non-computable degree. However, such orders may have copies of $\mathbb{Q}$ corresponding to nodes above which the corresponding tree is perfect, so this is a strictly larger class of orders. Again, we believe that every quasi-PAC order has a computable copy, but this is a stronger claim than the above, which we are already unable to prove.

A secondary question: it is easy to construct PAC orders of arbitrarily high computable Hausdorff rank. This suggests that every computable linear order is a PAC order; however, explicitly passing from computable orders to PAC trees is something I haven't been able to do. So:

> Is every computable scattered linear order a PAC order?

What I can show: Every c.s.l.o. is *equimorphic to* a PAC order. This follows from Jullien's theorem via Montalban's notion of signed trees: by a straightforward induction, every order corresponding to a signed tree is PAC, and finite sums of PAC orders are PAC. However, equimorphism is an extremely coarse invariant - every *hyperarithmetic* linear order is equimorphic to a computable linear order - so this sheds no real light on this question. I briefly thought I had a proof that every c.s.l.o. is PAC via induction on the Hausdorff rank, using an $\alpha$-system argument (see Chapter 14 in Ash and Knight "Computable structures and the hyperarithmetic hierarchy") for rank $\alpha$, but it turned out to be wrong.

********

$^1$ Here's the proof; it's a bit long, but the underlying idea is very simple.

By the Recursion Theorem, we can transform this into the following problem: consider a game in which player I builds a PAC tree, and player II builds a linear order. Player II wins if their linear order is isomorphic to the order of isolated paths through player I's tree, or if player I builds a tree which is not PAC. Specifically, on the $s+1$th turn, player I takes her previous tree $T_s$ of height $s$ and extends it to a tree $T_{s+1}$ of height $s+1$, and player II adds some finite number of points (possibly 0) to their linear order $L_s$ to form $L_{s+1}$. Note that player II must "keep pace" with player I: we can assume that the size of player II's linear order at stage $s$ is exactly equal to the number of height-$s$ nodes of player I's tree. Moreover, we can assume that the domain of each $L_s$ forms an initial segment of $\omega$.

It is now enough to show that player I has a computable strategy defeating every strategy by player II. Her strategy will involve adding a bit of information to the tree she is building: in addition to the height-$s$ tree $T_s$, at the end of player II's play at stage $s$ she will also "tag" a node $\sigma$ on $T_s$ of maximal length. The tagged nodes will extend each other: $\sigma_s\prec \sigma_{s+1}$ for every $s$. The idea is for player I to continually make guesses as to whether player II is guessing that she will play (something which looks like) $\omega$, $\omega^*$, or $\omega+\omega^*$, and act accordingly.

Specifically, here is the strategy for player I. At stage 1, she will begin with $T_1=\{\langle 0\rangle, \langle 1\rangle\}$. Player II will then play a linear order with two elements 0, 1; WLOG she plays $0<1$. Player I then tags $\langle 1\rangle\in T_1$.

At stage $s+1$, player I plays the tree $\{\tau^\smallfrown\langle 0\rangle: \tau\in T_s\}\cup \{\sigma_s^\smallfrown\langle 0\rangle, \sigma_s^\smallfrown\langle 1\rangle\}$. (Part of that is redundant, but hopefully makes the picture clearer.) Player II then plays a linear order $L_{s+1}$, which by our assumption consists of $L_s$ together with a single new element $n_s$. There is exactly one isomorphism between $L_{s+1}$ and the set of maximal-length nodes of $T_{s+1}$, ordered left-to-right, and by induction the image of $1$ under this isomorphism is either $\sigma_s^\smallfrown\langle 0\rangle$ or $\sigma_s^\smallfrown\langle 1\rangle$; this node is then tagged $\sigma_{s+1}$.

The resulting tree $T_\infty=\bigcup_{s\in\omega} T_s$ is clearly a PAC tree - it has exactly one nonisolated path, and that path splits at every level, and every isolated path becomes isolated as soon as it splits off the nonisolated path; so I wins unless $L_\infty=\bigcup_{s\in\omega} L_s\cong \mathcal{L}_{T_\infty}^{iso}$. However, $L_\infty$ is either $\omega+1+\omega^*$, in which case $\mathcal{L}_{T_\infty}^{iso}$ is $\omega+\omega^*$; or $\omega+n+1$, in which case $\mathcal{L}_{T_\infty}^{iso}$ is $\omega+n$; or $1+n+\omega^*$, in which case $\mathcal{L}_{T_\infty}^{iso}$ is $n+\omega^*$. In particular, the element $1$ of player II's ordering always winds up corresponding to an non-isolated path through $T_s$. So player I wins.

Note that a crucial component of this proof is that at each stage, player II is forced to allow player I to keep attacking the point $\langle 1\rangle$; this is because only one point is played at each stage, and player I always attacks $\langle 1\rangle$ at each stage. Once we try to handle even two opponents, this strategy breaks down.