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

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.

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

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

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.

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