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.



Maximal chains of order type $\omega_1^{ck}$ in computable partial orders?
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.)


