2.1 Computable structures, cohesive products, and cohesive powers

Fix a computable language $\mathfrak {L}$ . A computable $\mathfrak {L}$ -structure $\mathcal {A}$ consists of a non-empty computable domain $A \subseteq \mathbb {N}$ and uniformly computable interpretations of the relation, function, and constant symbols of $\mathfrak {L}$ . Often the domain of a structure $\mathcal {A}$ (computable or not) is denoted by $|\mathcal {A}|$ . Likewise, a uniformly computable sequence of $\mathfrak {L}$ -structures $(\mathcal {A}_i : i \in \mathbb {N})$ consists of a uniformly computable sequence $(A_i : i \in \mathbb {N})$ of non-empty domains, where $A_i \subseteq \mathbb {N}$ for each i, along with uniformly computable interpretations all the symbols of $\mathfrak {L}$ in the structures $(\mathcal {A}_i : i \in \mathbb {N})$ . Equivalently, an $\mathfrak {L}$ -structure $\mathcal {A}$ is computable if its atomic diagram is computable, and a sequence of $\mathfrak {L}$ -structures $(\mathcal {A}_i : i \in \mathbb {N})$ is uniformly computable if the corresponding sequence of atomic diagrams is uniformly computable. More generally, a computable $\mathfrak {L}$ -structure is decidable (n-decidable) if its elementary diagram ( $\!\! \Sigma _n$ -elementary diagram) is computable, and a uniformly computable sequence of $\mathfrak {L}$ -structures is uniformly decidable (uniformly n-decidable) if the corresponding sequence of elementary diagrams ( $\Sigma _n$ -elementary diagrams) is uniformly computable. Note that a $0$ -decidable $\mathfrak {L}$ -structure is the same thing as a computable $\mathfrak {L}$ -structure, and a uniformly $0$ -decidable sequence of $\mathfrak {L}$ -structures is the same thing as a uniformly computable sequence of $\mathfrak {L}$ -structures.

We present the definition of cohesive products and cohesive powers as in [Reference Dimitrov, Harizanov, Morozov, Shafer, Soskova and Vatev8] (see also [Reference Dimitrov4, Reference Dimitrov and Harizanov6]).

As in the classical case, a computable structure $\mathcal {A}$ always naturally embeds into its cohesive powers. For $a \in |\mathcal {A}|$ , let $f_a$ be the total computable function with constant value a. Then for any cohesive set C, the so-called canonical embedding $a \mapsto [f_a]$ embeds $\mathcal {A}$ into $\prod _C \mathcal {A}$ .

The extent to which analogs of Łoś’s theorem hold for cohesive products and powers depends on what formulas are decidable in the structures. We make the following definitions as in [Reference Dimitrov, Harizanov, Morozov, Shafer, Soskova and Vatev8]. Say that a computable sequence of formulas $(\Phi _i : i \in \mathbb {N})$ is uniformly decidable in a uniformly computable sequence of structures $(\mathcal {A}_n : n \in \mathbb {N})$ if there is an algorithm that, given an n, an i, a subformula $\Psi (\vec {y})$ of $\Phi _i$ , and a sequence of parameters $\vec {a}$ from $|\mathcal {A}_n|$ of appropriate length, determines whether $\mathcal {A}_n \models \Psi (\vec {a})$ . That is, $(\Phi _i : i \in \mathbb {N})$ is uniformly decidable in $(\mathcal {A}_n : n \in \mathbb {N})$ if the set

$$ \begin{align*} \{\langle n, i, \Psi(\vec{y}), \vec{a} \rangle : \Psi \text{ is a subformula of } \Phi_i \;\land\; |\vec{a}| = |\vec{y}| \;\land\; \mathcal{A}_n \models \Psi(\vec{a})\} \end{align*} $$

is computable. In the case of a single formula $\Phi $ (and its subformulas), we say that $\Phi $ is uniformly decidable in $(\mathcal {A}_n : n \in \mathbb {N})$ .

We obtain the following analogs of Łoś’s theorem from Lemma 2.2. We abuse the terminology somewhat by saying that a formula is $\Delta _n$ if it is logically equivalent to both a $\Sigma _n$ formula and a $\Pi _n$ formula.

The analog of Łoś’s theorem achieves an extra quantifier in the case of sentences and cohesive powers.

It follows that the full analogs of Łoś’s theorem hold when the structures are uniformly decidable. If $(\mathcal {A}_i : i \in \mathbb {N})$ is a uniformly decidable sequence of structures, then the conclusion of Theorem 2.3 item 3 holds for every first-order formula $\Phi $ . Similarly, if $\mathcal {A}$ is a decidable structure, then the conclusion of Theorem 2.4 item (1) holds for every first-order sentence $\Phi $ .

In [Reference Dimitrov, Harizanov, Morozov, Shafer, Soskova and Vatev8] it is shown (following [Reference Nelson33]) that cohesive products of uniformly decidable sequences of structures are recursively saturated and that, for $n> 0$ , cohesive products of uniformly $n $ -decidable sequences of structures are $\Sigma _n$ -recursively saturated. More interestingly, it is shown that we obtain an extra level of saturation as well as the $n=0$ case when the cohesive set is assumed to be $\Pi _1$ : cohesive products of uniformly $n $ -decidable sequences of structures over $\Pi _1$ cohesive sets are $\Sigma _{n+1}$ -recursively saturated [Reference Dimitrov, Harizanov, Morozov, Shafer, Soskova and Vatev8, Theorem 2.18]. We now show that the same holds for cohesive products over $\Delta _2$ cohesive sets: cohesive products of uniformly $n $ -decidable sequences of structures over $\Delta _2$ cohesive sets are $\Sigma _{n+1}$ -recursively saturated.

Recall the definitions pertaining to saturation. Let $\mathfrak {L}$ be a language, let $\mathcal {A}$ be an $\mathfrak {L}$ -structure, and let $D \subseteq |\mathcal {A}|$ be a collection of parameters from $|\mathcal {A}|$ . Let $\mathfrak {L}_D = \mathfrak {L} \cup D$ be the language obtained by augmenting $\mathfrak {L}$ with fresh constant symbols identified with the members of D. A type $(of\, \mathcal {A})$ over D is a set of $\mathfrak {L}_D$ -formulas $p(\vec {x}) = p(x_0, \dots , x_{m-1})$ in m fixed variables $x_0, \dots , x_{m-1}$ that is finitely satisfied in $\mathcal {A}$ : for every $\Phi _0(\vec {x}), \dots , \Phi _{k-1}(\vec {x}) \in p(\vec {x})$ , $\mathcal {A} \models \exists \vec {x} \, \bigwedge _{i < k} \Phi _i(\vec {x})$ . A type $p(\vec {x})$ of $\mathcal {A}$ over D is realized if there are $a_0, \dots , a_{m-1} \in |\mathcal {A}|$ such that for all $\Phi (\vec {x}) \in p(\vec {x})$ , $\mathcal {A} \models \Phi (\vec {a})$ . A type is a $\Sigma _n$ -type if every formula in the type is $\Sigma _n$ . Now let $\mathfrak {L}$ be a computable language. An $\mathfrak {L}$ -structure $\mathcal {A}$ is recursively saturated if it realizes every computable type over a finite set of parameters, and it is $\Sigma _n$ -recursively saturated if it realizes every computable $\Sigma _n$ -type over a finite set of parameters.

Let $p(\vec {x})$ be a type of some structure $\mathcal {A}$ over parameters D. For us, D is always finite or countable, and we enumerate it as a sequence $\vec {c}$ of appropriate length. We write $p(\vec {x}; \vec {c})$ for $p(\vec {x})$ and $\Phi (\vec {x}; \vec {c})$ for a formula of $p(\vec {x}; \vec {c})$ when we want to highlight the parameters. Here, $\Phi (\vec {x}; \vec {c})$ is shorthand for $\Phi (\vec {x}; \vec {c} {\restriction } k)$ , where $\vec {c} {\restriction } k$ is the shortest initial segment of $\vec {c}$ containing all the parameters appearing in $\Phi $ . We also write $\Phi (\vec {x}; \vec {y})$ for the $\mathcal {L}$ -formula corresponding to $\Phi (\vec {x}; \vec {c})$ , with fresh variables $\vec {y}$ in place of the parameters $\vec {c}$ .

The following lemma extends [Reference Dimitrov, Harizanov, Morozov, Shafer, Soskova and Vatev8, Lemma 2.17] by allowing $\Delta _2$ cohesive sets and by allowing infinite sequences of uniformly partial computable parameters. Say that a sequence $([\psi _\ell ] : \ell \in \mathbb {N})$ of elements of some cohesive product is uniformly partial computable if the sequence $(\psi _\ell : \ell \in \mathbb {N})$ of representatives is uniformly partial computable.

Proof. As $p(\vec {x}; \overrightarrow {[\psi ]})$ is a type,

$$ \begin{align*} \prod\nolimits_C \mathcal{A}_n \models \exists \vec{x}\, \bigwedge_{i < k} \exists \vec{z}_i\, \Phi_i(\vec{x}, \vec{z}_i; \overrightarrow{[\psi]}) \end{align*} $$

for each k. To streamline the notation, let $\psi \colon \mathbb {N}^2 \to \mathbb {N}^{<\mathbb {N}}$ be the partial computable function given by $\psi (i,n) \simeq \langle \psi _0(n), \dots , \psi _{\ell _i-1}(n) \rangle $ , where $\ell _i$ is least such that $\overrightarrow {[\psi ]} {\restriction } \ell _i$ contains all the parameters of $\overrightarrow {[\psi ]}$ appearing in $\Phi _i$ . Notice that $C \subseteq ^* \{n : \psi (i,n){\downarrow }\}$ for every i.

Our goal is to partially compute a function $\theta \colon \mathbb {N} \to \mathbb {N}^m$ so that $C \subseteq ^* {\mathrm {dom}}(\theta )$ and

(*) $$ \begin{align} \exists^\infty n \in C \; \Big( \mathcal{A}_n \models \exists \vec{z}_i\, \Phi_i(\theta(n), \vec{z}_i; \psi(i,n)) \Big) \end{align} $$

for each i. The set

$$ \begin{align*} \Big\{n : \mathcal{A}_n \models \exists \vec{z}_i\, \Phi_i(\theta(n), \vec{z}_i; \psi(i,n))\Big\} \end{align*} $$

is c.e. for each i because $\Phi _i$ is uniformly decidable in $(\mathcal {A}_n : n \in \mathbb {N})$ . Thus (*) implies that

$$ \begin{align*} \forall^\infty n \in C \; \Big( \mathcal{A}_n \models \exists \vec{z}_i\, \Phi_i(\theta(n), \vec{z}_i; \psi(i,n)) \Big) \end{align*} $$

for each i by cohesiveness. Once $\theta $ has been defined, we let $\varphi _j = \pi _j \circ \theta $ for each $j < m$ . We then have that $[\varphi _0], \dots , [\varphi _{m-1}] \in |\prod _C \mathcal {A}_n|$ and that

$$ \begin{align*} \prod\nolimits_C \mathcal{A}_n \models \exists \vec{z}_i\, \Phi_i\left(\overrightarrow{[\varphi]}, \vec{z}_i; \overrightarrow{[\psi]} \right) \end{align*} $$

for each i by Lemma 2.2 item (2). Thus $[\varphi ], \dots , [\varphi _{m-1}]$ realize $p(\vec {x}; \overrightarrow {[\psi ]})$ in $\prod _C \mathcal {A}_n$ .

Let $f \colon \mathbb {N}^2 \to \{0,1\}$ be a $\Delta _2$ -approximation to the cohesive set C. Let $(U_k : k \in \mathbb {N})$ be the uniformly c.e. sequence of sets given by

$$ \begin{align*} U_k = \left\{\langle \vec{a}, n \rangle \in \mathbb{N}^m \times \mathbb{N}: \mathcal{A}_n \models \bigwedge_{i < k} \exists \vec{z}_i\, \Phi_i(\vec{a}, \vec{z}_i; \psi(i,n))\right\} \end{align*} $$

with uniformly computable $\subseteq $ -increasing enumerations $(U_{k,s})_{s \in \mathbb {N}}$ of finite sets for each k. These enumerations are given in terms of strong indices, so membership in $U_{k,s}$ as well as its size are uniformly computable in k and s. The sequence $(U_k : k \in \mathbb {N})$ is uniformly c.e. because the formulas $(\Phi _i : i \in \mathbb {N})$ are uniformly decidable in $(\mathcal {A}_n : n \in \mathbb {N})$ . Notice that if $k \leq j$ , then $U_j \subseteq U_k$ . We can therefore arrange the enumerations so that if $k \leq j$ , then $\forall s \, (U_{j, s} \subseteq U_{k, s})$ .

We partially compute $\theta $ by computing an increasing sequence $\theta _0 \subseteq \theta _1 \subseteq \theta _2 \subseteq \cdots $ of finite approximations to $\theta $ . Start at stage $0$ with $\theta _0 = \emptyset $ . At stage s, we have $\theta _s$ , and we define $\theta _{s+1}$ .

Say that n covers k at stage s if the following conditions hold:

1. (a) $n> k$ .

2. (b) $f(n,s) = 1$ .

3. (c) $\theta _s(n){\downarrow }$ .

4. (d) $\langle \theta _s(n), n \rangle \in U_{k,s}$ .

If there is an n that covers k at stage s, then we say that k is covered at stage s. Let $k^0_s$ be the least number that is not covered at the start of stage s. If $s> 0$ , then let $k^1_s$ be the least number (if it exists) for which there is an n with $f(n,s) = 0$ that covered $k^1_s$ at stage $s-1$ , but no $\widehat {n} \leq n$ covers $k^1_s$ at stage s. If $k^1_s$ is defined, then let $k_s = \min \{k^0_s, k^1_s\}$ . Otherwise, let $k_s = k^0_s$ . Now check if there is an $n < s$ meeting the following conditions:

1. (i) $n> k_s$ .

2. (ii) $f(n,s) = 1$ .

3. (iii) $\theta _s(n){\uparrow }$ .

4. (iv) There is an $\vec {a}$ with $\langle \vec {a}, n \rangle \in U_{k_s, s}$ .

If there is such an n, choose the least such n, choose the first corresponding $\vec {a}$ as in item (iv), and extend $\theta _s$ to $\theta _{s+1}$ by setting $\theta _{s+1}(n) = \vec {a}$ . If there is no such n, then set $\theta _{s+1} = \theta _s$ . Now go to stage $s+1$ . This completes the definition of $\theta $ .

Suppose that n covers k at some stage $s_0$ . Then the only way that n could fail to cover k at some stage $s> s_0$ is by the failure of condition (b). If, however, $n \in C$ , then there is a stage $s_1> s_0$ such that $\forall s \geq s_1 \; (f(n,s) = 1)$ . Then n covers k at all stages $s \geq s_1$ . In this situation, we say that k is covered by an $n \in C$ . We show by induction on k that every k is eventually covered by an $n \in C$ .

Claim. Every $k $ is eventually covered by an $n \in C$ .

Proof of Claim

Proceed by induction on k. Let $s_0$ be a stage by which all $\widehat {k} < k$ have been covered by members of C. Let c be the greatest member of C covering a $\widehat {k} < k$ at stage $s_0$ . Let $s_1> s_0$ be a stage by which f has settled to its final value on all n up to c: $\forall n \leq c \; \forall s \geq s_1 \; (f(n,s) = C(n))$ . Then $k_s \geq k$ at all stages $s> s_1$ . By assumption,

$$ \begin{align*} \prod\nolimits_C \mathcal{A}_n \models \exists \vec{x}\, \bigwedge_{i < k} \exists \vec{z}_i\, \Phi_i\left(\vec{x}, \vec{z}_i; \overrightarrow{[\psi]} \right), \end{align*} $$

and therefore,

$$ \begin{align*} C \subseteq^* \left\{n : \mathcal{A}_n \models \exists \vec{x}\, \bigwedge_{i < k} \exists \vec{z}_i\, \Phi_i\big(\vec{x}, \vec{z}_i; \psi(i,n) \big)\right\} \end{align*} $$

by Lemma 2.2 item (1). The lemma applies because prenexing the formula $\exists \vec {x}\, \bigwedge _{i < k} \exists \vec {z}_i\, \Phi _i(\vec {x}, \vec {z}_i; \vec {y})$ yields a formula of the form $\exists \vec {w}\, \Psi (\vec {w}; \vec {y})$ , where $\Psi $ is uniformly decidable in $(\mathcal {A}_n : n \in \mathbb {N})$ . Let $n_0$ be least with $n_0> k$ , $n_0 \in C$ , $\theta _{s_1}(n_0){\uparrow }$ , and $\exists \vec {a} \, (\langle \vec {a}, n_0 \rangle \in U_k)$ . If $\theta _s(n_0)$ is defined for the first time during a stage $s> s_1$ , then it is to cover a j with $k \leq j < n_0$ . That is, if the value of $\theta _s(n_0)$ is determined at stage $s> s_1$ , then it is chosen so that $\langle \theta _s(n_0), n_0 \rangle \in U_{j, s} \subseteq U_{k, s}$ for a $j \geq k$ . Therefore $n_0$ covers k at any stage $s> s_1$ at which $\theta _s(n_0){\downarrow }$ and $f(n_0, s) = 1$ .

Let $s_2> \max \{n_0, s_1\}$ be large enough so that $\forall n \leq n_0 \; \forall s \geq s_2 \; (f(n,s) = C(n))$ and that $\exists \vec {a} \, (\langle \vec {a}, n_0 \rangle \in U_{k, s_2})$ . Consider stage $s_2$ . If k is not covered at stage $s_2$ , then it must be that $k_{s_2} = k$ and that $\theta _{s_2}(n_0){\uparrow }$ . Furthermore, by choice of $n_0$ and $s_2$ , $n_0 < s_2$ is the least number meeting conditions (i)–(iv) at stage $s_2$ . Therefore $\theta _{s_2 + 1}(n_0)$ is defined to cover k at stage $s_2$ , so k is covered by an element of C.

Suppose instead that k is covered at stage $s_2$ . Let n be the least number for which there is a stage $s_3 \geq s_2$ at which n covers k. If $n \in C$ , then k is covered by an element of C, as desired. If $n \notin C$ , then there is a least stage $s> s_3$ with $f(n,s) = 0$ . The number n covers k at stage $s-1$ , but by the choice of n, no $\widehat {n} \leq n$ covers k at stage s. Thus $k^1_s = k$ , so $k_s = k$ . If $\theta _s(n_0){\downarrow }$ , then $n_0$ must already cover k as observed above. If $\theta _s(n_0){\uparrow }$ , then $n_0 < s$ is the least number meeting conditions (i)–(iv) at stage s. Therefore $\theta _{s + 1}(n_0)$ is defined to cover k at stage s, so k is covered by an element of C. This completes the proof of the claim.

To complete the proof, consider the formula $\exists \vec {z}_i\, \Phi _i$ . By the claim, every k is eventually covered by an $n \in C$ . Thus for every $k> i$ , there is an $n> k$ with $n \in C$ , $\theta (n){\downarrow }$ , and $\langle \theta (n), n \rangle \in U_k$ . Thus $C \subseteq ^* {\mathrm {dom}}(\theta )$ by cohesiveness, and

$$ \begin{align*} \exists^\infty n \in C \; \Big( \mathcal{A}_n \models \exists \vec{z}_i\, \Phi_i(\theta(n), \vec{z}_i; \psi(i,n)) \Big) \end{align*} $$

as desired.

2.2 Cohesive products and powers of computable linear orders

A linear order $\mathcal {L} = (L; \prec )$ consists of a non-empty set L equipped with a binary relation $\prec $ satisfying the following axioms:

• • $\forall x \, (x \nprec x)$ .

• • $\forall x \, \forall y \, \forall z \, \big ( (x \prec y \,\land \, y \prec z) \;\rightarrow \; x \prec z \big )$ .

• • $\forall x \, \forall y \, (x \prec y \,\lor \, x = y \,\lor \, y \prec x)$ .

Furthermore, a linear order $\mathcal {L}$ is dense if $\forall x \, \forall y \, \exists z \, (x \prec y \;\rightarrow \; x \prec z \prec y)$ and has no endpoints if $\forall x \, \exists y \, \exists z \, (y \prec x \prec z)$ . A computable linear order $\mathcal {L} = (L; \prec _{\mathcal {L}})$ therefore consists of a non-empty computable set $L \subseteq \mathbb {N}$ and a computable relation ${\prec _{\mathcal {L}}} \,\subseteq \, L \times L$ that linearly orders L.

Let $\mathcal {L} = (L; \prec _{\mathcal {L}})$ be a linear order, and let $a, b \in L$ . Let $\min _{\prec _{\mathcal {L}}} \{a, b\}$ and $\max _{\prec _{\mathcal {L}}} \{a, b\}$ denote the minimum and maximum of a and b with respect to $\prec _{\mathcal {L}}$ ; let $(a,b)_{\mathcal {L}} = \{x \in L : a \prec _{\mathcal {L}} x \prec _{\mathcal {L}} b\}$ and $[a,b]_{\mathcal {L}} = \{x \in L : a \preceq _{\mathcal {L}} x \preceq _{\mathcal {L}} b\}$ denote the open and closed intervals defined by a and b; and let $|(a,b)_{\mathcal {L}}|$ and $|[a,b]_{\mathcal {L}}|$ denote the cardinalities of the respective intervals. It is convenient to allow $b \prec _{\mathcal {L}} a$ in the interval notation, in which case $(a,b)_{\mathcal {L}} = [a,b]_{\mathcal {L}} = \emptyset $ . Let a $\unicode{x2ABB}_{\mathcal {L}} b$ denote that the interval $(a,b)_{\mathcal {L}}$ is infinite.

Recall that $\omega $ denotes the order-type of the natural numbers $(\mathbb {N}; <)$ , that $\zeta $ denotes the order-type of the integers $(\mathbb {Z}; <)$ , and that $\eta $ denotes the order-type of the rationals $(\mathbb {Q}; <)$ , all with their usual orders. We refer to $(\mathbb {N}; <)$ , $(\mathbb {Z}; <)$ , and $(\mathbb {Q}; <)$ as the usual presentations of $\omega $ , $\zeta $ , and $\eta $ . For each $n \geq 1$ , let $\boldsymbol {n}$ denote the order-type of the finite linear order $(\{0, 1, \dots , n-1\}; <)$ . For any order-type $\alpha $ , a computable linear order of type $\alpha $ is called a computable copy of $\alpha $ . A computable copy of $\omega $ is not necessarily isomorphic to the usual presentation of $\omega $ via a computable isomorphism. Every countable dense linear order without endpoints has order-type $\eta $ , and every computable copy of $\eta $ is computably isomorphic to the usual presentation of $\eta $ (see [Reference Rosenstein35, Theorem 2.8 and Exercise 16.4]).

Let $\mathcal {L}_0 + \mathcal {L}_1$ and $\mathcal {L}_0\mathcal {L}_1$ denote the usual sum and product of linear orders $\mathcal {L}_0$ and $\mathcal {L}_1$ . Let $\mathcal {L}^*$ denote the reverse of the linear order $\mathcal {L}$ . Furthermore, recall the generalized sum of a sequence $(\mathcal {M}_\ell : \ell \in |\mathcal {L}|)$ of linear orders indexed by the elements of a linear order $\mathcal {L}$ .

Definition 2.7 (See [Reference Rosenstein35, Definition 1.38])

Let $\mathcal {L}$ be a linear order, and let $(\mathcal {M}_\ell : \ell \in |\mathcal {L}|)$ be a sequence of linear orders indexed by $|\mathcal {L}|$ . The generalized sum $\sum _{\ell \in |\mathcal {L}|}\mathcal {M}_\ell $ of $(\mathcal {M}_\ell : \ell \in |\mathcal {L}|)$ over $\mathcal {L}$ is the linear order $\mathcal {S} = (S; \prec _{\mathcal {S}})$ defined as follows. Write $\mathcal {L} = (L; \prec _{\mathcal {L}})$ , and write $\mathcal {M}_\ell = (M_\ell; \prec _{\mathcal {M}_\ell })$ for each $\ell \in L$ . Define $S = \{(\ell , m) : \ell \in L \,\land \, m \in M_\ell \}$ , and define

$$ \begin{align*} (\ell_0, m_0) \prec_{\mathcal{S}} (\ell_1, m_1) \quad\text{if and only if}\quad (\ell_0 \prec_{\mathcal{L}} \ell_1) \;\lor\; (\ell_0 = \ell_1 \,\land\, m_0 \prec_{\mathcal{M}_{\ell_0}} m_1). \end{align*} $$

Generalized sums may be used to define the shuffle of a non-empty and at-most-countable collection of linear orders.

In Definition 2.8, it is helpful to identify each linear order in X with a unique color and think of the function $f \colon \mathbb {Q} \to X$ as a coloring of $\mathbb {Q}$ in which every color occurs densely. The shuffle $\boldsymbol {\sigma }(X)$ is then obtained by replacing each element of $\mathbb {Q}$ by the linear order with which it is colored. Also, we usually think of the X in a shuffle $\boldsymbol {\sigma }(X)$ as a collection of order-types instead of as a collection of concrete linear orders.

If $\mathcal {L}$ is a computable linear order and $(\mathcal {M}_\ell : \ell \in |\mathcal {L}|)$ is a uniformly computable sequence of linear orders indexed by $|\mathcal {L}|$ , then the pairing function may be used to compute a copy of $\sum _{\ell \in |\mathcal {L}|}\mathcal {M}_\ell $ . Furthermore, if $(\mathcal {M}_n : n \in \mathbb {N})$ is a uniformly computable sequence of linear orders, then a computable dense coloring $f \colon \mathbb {Q} \to \mathbb {N}$ of $\mathbb {Q}$ may be used to compute a copy of $\boldsymbol {\sigma }(\{\mathcal {M}_n : n \in \mathbb {N}\})$ .

Recall now the condensations and in particular the finite condensation of a linear order. In general, a condensation of a linear order $\mathcal {L}$ is obtained by partitioning $\mathcal {L}$ into non-empty intervals and then by collapsing each interval to a point.

Definition 2.10. Let $\mathcal {L} = (L; \prec _{\mathcal {L}})$ be a linear order. For $x \in L$ , let ${\mathbf {c}_{\text {F}}}(x)$ denote the set of $y \in L$ for which there are only finitely many elements between x and y:

$$ \begin{align*} {\mathbf{c}_{\text{F}}}(x) = \Big\{y \in L : \text{ the interval } \big[\min\nolimits_{\prec_{\mathcal{L}}}\{x,y\}, \max\nolimits_{\prec_{\mathcal{L}}}\{x,y\}\big]_{\mathcal{L}} \text{ is finite} \Big\}. \end{align*} $$

The set ${\mathbf {c}_{\text {F}}}(x)$ is always a non-empty interval, as $x \in {\mathbf {c}_{\text {F}}}(x)$ . The finite condensation ${\mathbf {c}_{\text {F}}}(\mathcal {L})$ of $\mathcal {L}$ is the condensation obtained from the partition $\{{\mathbf {c}_{\text {F}}}(x) : x \in L\}$ .

When a linear order $\mathcal {L} = (L; \prec _{\mathcal {L}})$ is partitioned into non-empty intervals as in Definition 2.9, the intervals of the partition are called the blocks of $\mathcal {L}$ . For the finite condensation of $\mathcal {L}$ , the blocks are the sets of the form ${\mathbf {c}_{\text {F}}}(x)$ for $x \in L$ , each of which has order-type either $\omega $ , $\omega ^*$ , $\zeta $ , or $\boldsymbol {n}$ for some $n \geq 1$ . For $x, y \in L$ , we also have that ${\mathbf {c}_{\text {F}}}(x) \prec _{{\mathbf {c}_{\text {F}}}(\mathcal {L})} {\mathbf {c}_{\text {F}}}(y)$ if and only if $x \unicode{x2ABB}_{\mathcal {L}} y$ .

Linear orders are axiomatized by $\Pi _1$ sentences, so it follows from Theorem 2.3 item (2) that a cohesive product of a uniformly computable sequence of linear orders is again a linear order. The properties of a linear order being dense and having no endpoints can each be expressed by $\Pi _2$ sentences, so also a cohesive product of a uniformly computable sequence of dense linear orders is a dense linear order, and a cohesive product of a uniformly computable sequence of linear orders without endpoints is a linear order without endpoints.

In [Reference Dimitrov, Harizanov, Morozov, Shafer, Soskova and Vatev8] it is shown that cohesive powers commute with the sum, product, and reverse operations on computable linear orders.

In [Reference Dimitrov, Harizanov, Morozov, Shafer, Soskova and Vatev8], it is also shown that the finite condensation of the cohesive product of a uniformly computable sequence of linear orders over a $\Pi _1$ cohesive set is always dense. Furthermore, it is shown that the finite condensation of the cohesive power of a computable copy of $\omega $ over a $\Pi _1$ cohesive set always has order-type $\boldsymbol {1} + \eta $ . We extend both results to $\Delta _2$ cohesive sets and recall a few helpful lemmas from [Reference Dimitrov, Harizanov, Morozov, Shafer, Soskova and Vatev8].

Proof. The cohesive product $\prod _C \mathcal {L}_n$ is $\Sigma _1$ -recursively saturated by Theorem 2.6, so it suffices to show that the finite condensation of a $\Sigma _1$ -recursively saturated linear order is dense.

Let $\mathcal {M} = (M; \prec _{\mathcal {M}})$ be a $\Sigma _1$ -recursively saturated linear order, and let $a, b \in M$ be such that $a \unicode{x2ABB}_{\mathcal {M}} b$ . We need to find a $c \in M$ with $a \unicode{x2ABB}_{\mathcal {M}} c \unicode{x2ABB}_{\mathcal {M}} b$ . For each $k \in \mathbb {N}$ , let $\Phi _k(x; a, b)$ be the following formula (with parameters a and b) expressing that the intervals $(a, x)_{\mathcal {M}}$ and $(x, b)_{\mathcal {M}}$ have at least k elements each

$$ \begin{align*} &\Phi_k(x;a,b)\\ &\quad\equiv \exists w_0, \dots, w_{k-1}, z_0, \dots, z_{k-1} (a \prec w_0 \prec \cdots \prec w_{k-1} \prec x \prec z_0 \prec \cdots \prec z_{k-1} \prec b). \end{align*} $$

The set $p(x;a,b) = \{\Phi _k(x; a, b) : k \in \mathbb {N}\}$ is a computable set of $\Sigma _1$ formulas, and it is a type over $\{a,b\}$ because the interval $(a,b)_{\mathcal {M}}$ is infinite. Thus $p(x;a,b)$ is realized by some $c \in M$ by $\Sigma _1$ -recursive saturation. The intervals $(a, c)_{\mathcal {M}}$ and $(c, b)_{\mathcal {M}}$ are therefore both infinite, so $a \unicode{x2ABB}_{\mathcal {M}} c \unicode{x2ABB}_{\mathcal {M}} b$ as desired.

Let $\mathcal {L} = (L; \prec _{\mathcal {L}})$ be a computable copy of $\omega $ , and let C be a cohesive set. It is straightforward to check that if $\varphi \colon \mathbb {N} \to L$ is a total computable injection, then $[\varphi ]$ is not in the image of the canonical embedding. Therefore the cohesive power $\prod _C \mathcal {L}$ has the form $\omega + \mathcal {M}$ for some non-empty linear order $\mathcal {M}$ . Call an element of $\prod _C \mathcal {L}$ standard if it is in the image of the canonical embedding, and call the element non-standard otherwise.

In Lemma 2.16, the condition $\liminf _{n \in C} \varphi (n) = \infty $ may be replaced by $\lim _{n \in C} \varphi (n) = \infty $ and by $\limsup _{n \in C} \varphi (n) = \infty $ .

The main result of [Reference Dimitrov, Harizanov, Morozov, Shafer, Soskova and Vatev8] is that for a variety of countable linear orders $\mathcal {M}$ with ${\mathbf {c}_{\text {F}}}(\mathcal {M}) \cong \boldsymbol {1} + \eta $ and for a given $\Pi _1$ cohesive set C, it is possible to design a computable copy $\mathcal {L}$ of $\omega $ that achieves $\prod _C \mathcal {L} \cong \mathcal {M}$ .

The proof of Theorem 2.19 involves a coloring apparatus whereby a computable copy of $\omega $ is colored in such a way as to induce a coloring on its cohesive power with certain density properties. We end this section by introducing the coloring apparatus.

A colored linear order is a two-sorted structure, where one sort is the domain L of the linear order and the other sort is the set $\mathbb {N}$ of colors. The language consists of unary relation symbols for L and $\mathbb {N}$ , a binary relation symbol for F, and the binary relation symbol $\prec $ . Though we must technically formalize F as a relation, we use the function notation $F(\ell ) = d$ instead of the relation notation $F(\ell , d)$ .

We typically follow the notational convention of letting $\mathcal {O} = (L, \mathbb {N}; \prec _{\mathcal {L}}, F)$ denote a colored linear order with the additional coloring structure and letting $\mathcal {L} = (L; \prec _{\mathcal {L}})$ denote the underlying linear order. So let $\mathcal {O}$ be a computable colored linear order, let $\mathcal {L}$ be the underlying linear order, and let C be a cohesive set. The cohesive power $\prod _C \mathcal {O}$ consists of a linear order $\prod _C \mathcal {L}$ , a collection of colors $\prod _C \mathbb {N}$ , and a (graph of a) function $F^{\prod _C \mathcal {O}} \colon |\prod _C \mathcal {L}| \to |\prod _C \mathbb {N}|$ thought of as a coloring of $\prod _C \mathcal {L}$ . If $[\varphi ]$ is in the domain of $\prod _C \mathcal {O}$ , then, by cohesiveness, either $\varphi (n)$ is an element of the linear order (i.e., is of the first sort) for almost every $n \in C$ , or $\varphi (n)$ is a color (i.e., is of the second sort) for almost every $n \in C$ . Therefore $[\varphi ]$ is either an element of the linear order $\prod _C \mathcal {L}$ or an element of the collection of colors $\prod _C \mathbb {N}$ . See also the discussion of reducts and substructures of cohesive powers in [Reference Dimitrov, Harizanov, Morozov, Shafer, Soskova and Vatev8, Section 2]. That $\prec _{\mathcal {L}}$ linearly orders L is expressible by a $\Pi _1$ sentence, so $\prec _{\prod _C \mathcal {L}}$ indeed linearly orders $|\prod _C \mathcal {L}|$ by Theorem 2.4. That F is the graph of a function with domain L and codomain $\mathbb {N}$ is expressible by a $\Pi _2$ sentence, so $F^{\prod _C \mathcal {O}}$ is indeed the graph of a function with domain $|\prod _C \mathcal {L}|$ and codomain $|\prod _C \mathbb {N}|$ by Theorem 2.4 as well.

Again let $\mathcal {O} = (L, \mathbb {N}; \prec _{\mathcal {L}}, F)$ be a computable colored linear order, let $\mathcal {L} = (L; \prec _{\mathcal {L}})$ , and let C be a cohesive set. To disambiguate between the elements of the linear order $\prod _C \mathcal {L}$ and the colors of $\prod _C \mathbb {N}$ inside the cohesive power $\prod _C \mathcal {O}$ , we write $[\varphi ]$ for the elements of $\prod _C \mathcal {L}$ , and we write $[\![ \delta ]\!] $ for the elements of $\prod _C \mathbb {N}$ . Call a color $[\![ \delta ]\!] \in |\prod _C \mathbb {N}|$ a solid color if $\delta $ is eventually constant on C: $\exists d \in \mathbb {N}\; \forall ^\infty n \in C\; (\delta (n) = d)$ . Otherwise, call $[\![ \delta ]\!] $ a striped color.

We want to color a computable copy of $\omega $ so that in the cohesive power by a given cohesive set, between any two distinct non-standard elements there are elements of every solid color plus at least one element of a striped color. In this situation, we say that the cohesive power is colorful.

In Definition 2.21, item (1) implies item (2) when the cohesive set is $\Delta _2$ . Let $\mathcal {O} = (L, \mathbb {N}; \prec _{\mathcal {L}}, F)$ be a computable colored copy of $\omega $ , let C be a $\Delta _2$ cohesive set, and suppose that $\prod _C \mathcal {O}$ satisfies Definition 2.21 item (1). Let $[\varphi ]$ and $[\psi ]$ be non-standard elements of $\prod _C \mathcal {L}$ with $[\psi ] \prec _{\prod _C \mathcal {L}} [\varphi ]$ . Let $\delta _i \colon \mathbb {N} \to \mathbb {N}$ be the constant function with value i for each i, so that $([\![ \delta _i ]\!] : i \in \mathbb {N})$ is a uniformly computable sequence of all the solid colors of $\prod _C \mathbb {N}$ . Now consider the computable $\Sigma _1$ -type $p(x; [\varphi ], [\psi ], [\![ \delta _0 ]\!] , [\![ \delta _1 ]\!] , \dots )$ consisting of the formula expressing $[\psi ] \prec x \prec [\varphi ]$ and, for each i, the formula expressing $F(x) \neq [\![ \delta _i ]\!] $ . The set of formulas p is indeed a type because every solid color occurs between $[\varphi ]$ and $[\psi ]$ . Thus p is realized by some $[\theta ] \in |\prod _C \mathcal {L}|$ by Theorem 2.6 item (2). Then $[\psi ] \prec _{\prod _C \mathcal {L}} [\theta ] \prec _{\prod _C \mathcal {L}} [\varphi ]$ , and $F^{\prod _C \mathcal {O}}([\theta ])$ is a striped color because it is not equal to any solid color. Thus $\prod _C \mathcal {O}$ also satisfies Definition 2.21 item (2).

Given a $\Pi _1$ cohesive set C, we can compute a colored copy $\mathcal {O}$ of $\omega $ such that $\prod _C \mathcal {O}$ is colorful by [Reference Dimitrov, Harizanov, Morozov, Shafer, Soskova and Vatev8, Theorem 5.3]. In Section 4, we compute a single colored copy $\mathcal {O}$ of $\omega $ such that $\prod _C \mathcal {O}$ is colorful for every $\Delta _2$ cohesive set C.

If $\mathcal {O} = (R, \mathbb {N}; \prec _{\mathcal {R}}, F)$ is a computable colored copy of $\omega $ , $\mathcal {R}$ denotes $(R; \prec _{\mathcal {R}})$ , and C is a cohesive set for which $\prod _C \mathcal {O}$ is colorful, then $\prod _C \mathcal {R} \cong \omega + \eta $ . This is because the standard elements of $\prod _C \mathcal {R}$ form an initial segment of order-type $\omega $ by Lemma 2.15, the non-standard elements have no endpoints by Lemma 2.17, and the colorfulness of $\prod _C \mathcal {O}$ implies that the non-standard elements of $\prod _C \mathcal {R}$ are dense. In [Reference Dimitrov, Harizanov, Morozov, Shafer, Soskova and Vatev8, Section 6], order-types other than $\omega + \eta $ are achieved by starting with $\mathcal {R}$ and computing another copy $\mathcal {L}$ of $\omega $ by replacing each element of $\mathcal {R}$ by some finite linear order depending on the element’s color and the desired order-type. The technique for producing $\mathcal {L}$ from $\mathcal {O}$ does not depend on the cohesive set C: so long as $\prod _C \mathcal {O}$ is colorful, the cohesive power $\prod _C \mathcal {L}$ has the desired order-type.

We emphasize that the linear order $\mathcal {L}$ in the conclusion of Lemma 2.22 is not the underlying linear order of $\mathcal {O}$ , but it is obtained from the underlying linear order of $\mathcal {O}$ by replacing its elements by finite linear orders. Theorem 2.19 is achieved by starting with a $\Pi _1$ cohesive set $C $ , computing a colored copy $\mathcal {O}$ of $\omega $ such that $\prod _C \mathcal {O}$ is colorful as in [Reference Dimitrov, Harizanov, Morozov, Shafer, Soskova and Vatev8, Theorem 5.3], and then applying Lemma 2.22.