Maximal chains of order type $\omega_1^{ck}$ in computable partial orders?

Question

Can a computable partial order have a maximal chain of order-type $\omega_1^{ck}$? My instinct is to say no, of course not, but I can't actually make the argument. If the p.o. also has chains of Harrison type, there seems to be no violation of $\Sigma^1_1$-bounding.

Edit: The answer is yes. Let $T$ be the tree of descending sequences in a Harrison order, so $T$ has nodes of every computable rank. Let $P$ consist of all finite antichains of $T$, and define an ordering on $P$ by $F \le G$ if for every $x \in F$ there is a $y \in G$ such that $x$ extends $y$ (in the tree order).

One shows that for $F \in P$, if every element of $F$ is ranked, then the partial order below $F$ is well-founded (König's Lemma or just an argument on ranks), and further that if $\alpha = \max_{x \in F} \text{rank}(x)$, then $F$ bounds a chain of order-type $\alpha$ (induction on $\alpha$). Then let $x_0, x_1, x_2, \dots$ be the ranked children of the root; one shows that $\{x_0\}, \{x_0, x_1\}, \dots$ can be extended to a maximal chain of type $\omega_1^{ck}$.

Second edit: Here's how to show that $\mathcal{O}$ has continuum many paths of length $\omega_1^{ck}$, so $\mathcal{O}^*$ works as an example.

Fix $H$ a computable Harrison ordering for which the successor function and the set of limit points are both computable, and nonuniformly fix the least element. Fix $(a_n)_{n \in \omega}$ an increasing sequence of limit points which is cofinal in the well-founded part (said sequence will be noncomputable, but that's okay). The plan is to build notations corresponding to the elements of $H$ using effective transfinite recursion, but at each $a_n$ we'll use padding to cause a bifurcation, giving us a perfect tree of notations. Since the sequence is noncomputable, our function giving the notations will have to be fed the $a_n$.

To the details. Let $A$ be the set of (canonically given) finite partial functions from $H$ to $2$. Let $A' \subset A$ be those functions for which all the elements of the domain are from the sequence $(a_n)_{n \in \omega}$. We build a partial computable function $f: \omega \times H \times A \to \mathcal{O}^*$. We define $f(e, x, \sigma)$ as follows:

If $x$ is the least element of $H$, $f(e, x, \sigma)$ is the notation for $0$.

If $x$ is the successor of $y$ in $H$, we compute $\phi_e(x, \sigma)$. Assuming this converges to a notation $b$, we output the notation for the successor of $b$. ($2^b$ in Kleene's system.)

If $x$ is a limit point of $H$, then compute an increasing sequence $(b_n)_{n \in \omega}$ cofinal below $x$, and let $i$ be such that $\phi_i(n) = \phi_e(b_n, \sigma)$. If $\sigma(x) = 1$, then we use padding to find an equivalent $i' > i$; otherwise, we keep this $i$. We then output the notation corresponding to this $i$ or $i'$. ($3\cdot 5^i$, in Kleene's system.)

Now apply the $s$-$m$-$n$ theorem to get a total computable $s$ with $\phi_{s(e)}(x, \sigma) = f(e, x, \sigma)$, then the recursion theorem to get an $\hat{e}$ with $\phi_{s(\hat{e})} = \phi_{\hat{e}}$.

Now we consider $\phi_{\hat{e}}(x, \sigma)$ for $x$ in the well-founded part of $H$ and $\sigma \in A'$. By a bunch of inductions: 1) $\phi_{\hat{e}}(x, \sigma)\downarrow$ and is a notation for the order-type of $x$; 2) $\phi_{\hat{e}}(x,\sigma) = \phi_{\hat{e}}(x,\sigma\upharpoonright_{\text{support}(\sigma)}) = \phi_{\hat{e}}(x,\sigma\upharpoonright_{\le x})$; 3) $\phi_{\hat{e}}(x,\sigma) \le_{\mathcal{O}} \phi_{\hat{e}}(y,\sigma)$ iff $x \le y$; and 4) if $\sigma(a_n) = 1-\tau(a_n)$, then $\phi_{\hat{e}}(a_n, \sigma) \neq \phi_{\hat{e}}(a_n,\tau)$. So this gives us our perfect tree of notations.

Answer 1

This is perhaps a simplification of the example you give: let $H$ be a Harrison order and let $P$ be the poset of pairs $(a,b)\in H$ with $a<b$, ordered by $$(a,b)\le (a',b') \quad\iff\quad a\le a'\mbox{ and }b\ge b'.$$ Note that in a chain in $P$, we do not require both coordinates to simultaneously change.

Let $(\alpha_i)_{i\in\omega}$ be cofinal in $\omega_1^{CK}$. Fix a descending sequence $(h_i)_{i\in\omega}$ in the Harrison order such that the ill-founded part of $H$ is exactly the union of the final segments given by the $h_i$s. Then - identifying elements of the well-founded part of $H$ with computable ordinals - the sequence $$(\alpha, h_{\min\{k: \alpha_k>\alpha\}})$$ is a maximal chain in $P$ with ordertype $\omega_1^{CK}$.

---

Here's another example:

Let $\mathcal{O}^*$ be the "computable analogue" of $\mathcal{O}$ (so $\mathcal{O}^*$ is a computable poset which is an end-extension of $\mathcal{O}$; see Sacks' book for details). Fix an increasing sequence $(\alpha_i)_{i\in\omega}$ of computable ordinals cofinal in $\omega_1^{CK}$ and an enumeration $(p_i)_{i\in\omega}$ of $\mathcal{O}^*\setminus\mathcal{O}$. We can iteratively build a sequence of notations $n_i$ for $\alpha_i$ such that $n_i<_\mathcal{O}n_{i+1}$ and $n_i\not<_{\mathcal{O}^*}p_i$; the downwards closure of $\{n_i:i\in\omega\}$ then is a maximal chain in $\mathcal{O}^*$ and clearly has ordertype $\omega_1^{CK}$. The key point is that by picking a cofinal $\omega$-sequence in $\omega_1^{CK}$ we avoid having to deal with limit stages in this construction, which would otherwise be a problem (we might become maximal too early).

(This is closely related to the construction above, which is unsurprising.)