Embedding partial orders

Suppose that $\Phi^{G^{\neq i}}_e = G^{[i]}$ for some $i$ and $e$. Let $W$ be the c.e. set of strings $\sigma$ for which some position $\langle i, y \rangle < |\sigma|$ satisfies $\Phi^{\sigma^{\neq i}}_e(y)\converge \neq \sigma(\langle i, y \rangle)$. Since $G$ is 1-generic (Definition 5.6 of “The finite extension method”), some prefix $\sigma$ of $G$ belongs to $W$ or has no extension in $W$.

If $\sigma \prec G$ belongs to $W$, then $\sigma^{\neq i} \prec G^{\neq i}$, so $\Phi^{G^{\neq i}}_e(y) = \Phi^{\sigma^{\neq i}}_e(y) \neq \sigma(\langle i, y \rangle) = G^{[i]}(y)$ for some $y$, a contradiction.

Suppose that $\sigma \prec G$ has no extension in $W$. Choose $y$ with $\langle i, y \rangle \geq |\sigma|$. Since $\Phi^{G^{\neq i}}_e(y)$ converges, there is $m > \langle i, y \rangle$ with $\Phi^{G^{\neq i} \uh m}_e(y)\converge = v$. Let $\tau$ be $G \uh m$ with the bit at position $\langle i, y \rangle$ replaced by $1 - v$. Then $\tau$ extends $\sigma$, because $\langle i, y \rangle \geq |\sigma|$, and $\tau^{\neq i} = G^{\neq i} \uh m$, because the modified position is in column $i$. So $\Phi^{\tau^{\neq i}}_e(y)\converge = v \neq \tau(\langle i, y \rangle)$, and $\tau \in W$, a contradiction.

Let $P = \{ p_0, p_1, \dots \}$. Define $f(p_n)$ by induction. Given $f(p_0), \dots, f(p_{n-1})$, preserving the order and its negation on $\{ p_0, \dots, p_{n-1} \}$, let $F$ be the image, and transport the order of $\{ p_0, \dots, p_n \}$ to $F \cup \{ p \}$ through $f$ and $p_n \mapsto p$. By the extension property, there is $q \in Q \setminus F$ realizing the same relations with $F$; let $f(p_n) = q$. The map $f$ is injective, since $q \notin F$, and preserves the order in both directions.

A one-point extension of a finite part $F$ of a partial order is determined by the sets $L = \{ a \in F : a < p \}$ and $V = \{ a \in F : p < a \}$. These sets define a partial order on $F \cup \{ p \}$ extending that of $F$ if and only if $L$ is closed downward in $F$, $V$ is closed upward in $F$, $L \cap V = \emptyset$, and $a \leq b$ for all $a \in L$ and $b \in V$. Call such a triple $(F, L, V)$ consistent with the order of $F$.

Fix a computable list of all triples of finite subsets of $\nat$ in which each triple appears infinitely often. We build the order $\preceq$ on $\nat$ by adding the element $s$ at stage $s$, deciding its relations with $0, \dots, s - 1$ once and for all. At stage $s$, let $(F, L, V)$ be the $s$-th triple of the list. If $F \subseteq \{ 0, \dots, s-1 \}$ and the triple is consistent with the current order on $F$, let

for $y < s$, and $s$ is incomparable with the other elements. Otherwise $s$ is incomparable with all $y < s$.

The order remains a partial order. Let $D$ and $E$ be the sets of elements below and above $s$. $D$ is closed downward and $E$ upward. They are disjoint: $b \preceq y \preceq a$ with $a \in L$, $b \in V$ would give $b \preceq a$, while $a \preceq b$ by consistency, so $a = b \in L \cap V$. Transitivity through $s$ holds: if $y \prec s \prec z$, then $y \preceq a \preceq b \preceq z$ for some $a \in L$, $b \in V$, so $y \preceq z$, and $y \neq z$ since $D \cap E = \emptyset$.

The new element realizes the triple. For $a \in F$, $a \prec s$ if and only if $a \preceq a'$ for some $a' \in L$, if and only if $a \in L$, since $L$ is closed downward in $F$. Similarly $s \prec a$ if and only if $a \in V$.

The relation $\preceq$ is computable, since the relations of $s$ with smaller elements are decided at stage $s$ by a finite computation. A consistent triple $(F, L, V)$ appears at some stage $s$ with $F \subseteq \{ 0, \dots, s-1 \}$, and $s \notin F$ realizes it.

By Lemma 2.3 and Lemma 2.4, it suffices to embed the computable partial order $(\nat, \preceq)$. Let $G$ be a 1-generic set computable in $\emptyset'$ (Proposition 5.7 of “The finite extension method”), and $G_m = G^{[m]}$. For each $n$, let

the set whose column $m$ is $G_m$ if $m \preceq n$, and empty otherwise. Each $D_n$ is computable in $G$, hence in $\emptyset'$.

If $m \preceq n$, then $D_m \leq_T D_n$: the column $k$ of $D_m$ is the column $k$ of $D_n$ if $k \preceq m$, since then $k \preceq n$, and is empty otherwise, and $\preceq$ is computable.

If $m \not\preceq n$, then $G_m \leq_T D_m$, since $m \preceq m$, and $D_n \leq_T G^{\neq m}$, since column $m$ is empty in $D_n$ and $\preceq$ is computable. So $D_m \leq_T D_n$ would give $G_m \leq_T G^{\neq m}$, contradicting Theorem 2.2.

So $n \mapsto \deg_T(D_n)$ preserves the order in both directions, and is injective since $\preceq$ is antisymmetric.

We define strings $\sigma_\rho$, for $\rho \in \bstr$, with $\sigma_{\rho 0}$ and $\sigma_{\rho 1}$ incomparable extensions of $\sigma_\rho$, and set $X_Z = \bigcup_n \sigma_{Z \uh n}$.

Let $\sigma_\varepsilon = \varepsilon$. Suppose that $\sigma_\rho$ is defined for all $\rho$ of length $n$. We modify these finitely many strings by finitely many extension steps, one for each $e < n$ and each ordered pair $(\rho, \rho')$ of distinct strings of length $n$. In the step for $(e, \rho, \rho')$, let $x = |\sigma_{\rho'}|$. If some $\tau \succeq \sigma_\rho$ has $\Phi^\tau_e(x)\converge = v$, replace $\sigma_\rho$ by $\tau$ and $\sigma_{\rho'}$ by $\sigma_{\rho'} b$, where $b \in \{0, 1\}$ is a bit different from $v$. Otherwise leave the strings unchanged; then $\Phi^Y_e(x)\diverge$ for every $Y \succeq \sigma_\rho$, by the use principle. In both cases, $\Phi^Y_e \neq X$ for all $Y \succeq \sigma_\rho$ and $X \succeq \sigma_{\rho'}$, and this remains true after further extensions. After all steps, let $\sigma_{\rho 0}$ and $\sigma_{\rho 1}$ be the final strings for $\rho$ followed by $0$ and by $1$.

Let $Z \neq Z'$, and $e \in \nat$. For $n > e$ larger than the first position where $Z$ and $Z'$ differ, $\rho = Z \uh n$ and $\rho' = Z' \uh n$ are distinct, and the step for $(e, \rho, \rho')$ ensures $\Phi^{X_Z}_e \neq X_{Z'}$. So $X_{Z'} \not\leq_T X_Z$, and symmetrically.