Given a linear order $\mathcal{S}$, let $\mathbb{A}\_\mathcal{S}$ be the class of all ordertypes which do not embed $\mathcal{S}$ (= do not have a suborder isomorphic to $\mathcal{S}$). Say that a linear order $\mathcal{S}$ is **deep** iff there is a computable functional $\Phi$ with the property that, whenever $\mathcal{M}$ is a linear order with domain $\mathbb{N}$ and $\mathcal{M}\in\mathbb{A}\_\mathcal{S}$, we have $\Phi^\mathcal{M}\in\mathbb{A}\_\mathcal{S}\setminus\mathbb{A}\_\mathcal{M}$ but $\mathcal{M}\in\mathbb{A}\_{\Phi^\mathcal{M}}$. *(Note that $\Phi$ does *not* have to preserve isomorphism. Also, if $\mathcal{S}$ is deep then $\mathbb{A}\_\mathcal{S}$ trivially has no maximal elements, but I see no reason for the converse to hold.)*


For example, $\omega, \omega^\*$, and $\eta$ (= the ordertypes of the naturals, negative naturals, and rationals respectively) are each deep via the single functional $\mathcal{M}\mapsto\mathcal{M}+\mathcal{M}$. On the other hand, no finite linear order is deep for trivial reasons.



> 
> **Question 1**: Is $\zeta$ (= the ordertype of the integers) deep?
> 
> 
> 


Certainly the same functional won't work here: $\omega+\omega^\*\in\mathbb{A}\_\zeta$, but $\omega+\omega^\*+\omega+\omega^\*=\omega+\zeta+\omega^\*$.


More generally, I'm interested in which countable linear orders are deep; $\zeta$ just seems like the first interesting case to consider.




---


I'm also interested in the following (even-more-)effective version of depth. Say that $\mathcal{S}$ is **effectively deep** iff there are computable functionals $\Phi,\Psi,\Theta,\Xi$ such that for every linear order $\mathcal{M}$ whatsoever we have


* $\Phi^\mathcal{M}$ is a linear order,
* $\Psi^\mathcal{M}$ is an embedding of $\mathcal{M}$ into $\Phi^\mathcal{M}$,
* if $f$ is an embedding of $\mathcal{S}$ into $\Psi^\mathcal{M}$, then $\Theta^{f,\mathcal{M}}$ is an embedding of $\mathcal{S}$ into $\mathcal{M}$, and
* if $g$ is an embedding of $\Phi^\mathcal{M}$ into $\mathcal{M}$, then $\Xi^{g,\mathcal{M}}$ is an embedding of $\mathcal{S}$ into $\mathcal{M}$.


*(In the last two bulletpoints, if $f/g$ is not of the appropriate type we don't require $\Theta^{f,\mathcal{M}}/\Xi^{g,\mathcal{M}}$ to even be fully defined.)*



> 
> **Question 2**: Is $\zeta$ effectively deep?
> 
> 
> 


(Note that $\omega,\omega^\*,$ and $\eta$ are still effectively deep.)



Computable functionals avoiding embeddings of linear orderings
Yes, $\zeta$ is deep. Observe that $\mathcal{M} \in \mathbb{A}\_\zeta$ iff $\mathcal{M} = L\_0 + L\_1$ for some $L\_0$ well-founded and $L\_1$ reverse well-founded. Moreover, this division is arithmetical in $\mathcal{M}$: to determine which side a point $x$ belongs to, search for $x+1$, $x-1$, $x+2$, $x-2$, etc (where $x+n$ denotes the $n$th successor, and $x-n$ denotes the $n$th predecessor). Then $x$ belongs to $L\_0$ iff some $x-n$ fails to exist, and $x$ belongs to $L\_1$ iff some $x+n$ fails to exist.


So we have two $\mathcal{M}$-arithmetical ordinals: $L\_0$ and $L\_1^\star$. Arithmetical ordinals are computably presentable, and in fact we can uniformly pass from an arithmetical index for an ordinal $\alpha$ to a computable index for an ordinal $\beta \ge \alpha$, and this relativizes with all uniformity (this follows from Watnik's theorem). So given $\mathcal{M}$, we can uniformly obtain ordinals $\beta\_0$ and $\beta\_1$, and then we can form the linear order $\beta\_0 + 1 + \beta\_1^\star$ as our $\Phi^{\mathcal{M}}$.




---


I've written and deleted the beginnings of an argument for not effectively deep several times. I suspect there's a forcing construction to show it, but it's not coming together.


