Skip to main content
3 of 4
added 3 characters in body
Dan Turetsky
  • 3.1k
  • 16
  • 27

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

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}$.

Dan Turetsky
  • 3.1k
  • 16
  • 27