Proof. Let \(\mathbb{A}\) be a Boolean algebra of size \(\leq\!\aleph_1\), and write \(\mathbb{A}\) as the union of a length-\(\omega_1\) sequence \(\left\langle \mathbb{A}_\alpha \colon \alpha< \omega_1 \right\rangle\) of subalgebras, such that \(\mathbb{A}_0 = \{\mathbf{0},\mathbf{1}\}\), and \(\mathbb{A}_\alpha\subseteq\mathbb{A}_\beta\) whenever \(\alpha\leq \beta\), and \(\mathbb{A}_\alpha= \bigcup_{\xi < \alpha}\mathbb{A}_\xi\) for limit \(\alpha< \omega_1\).

Using transfinite recursion, we now build a sequence \(\left\langle \eta_\alpha \colon \alpha< \omega_1 \right\rangle\) of maps such that each \(\eta_\alpha\) is an embedding \(\mathbb{A}_\alpha\to \mathbb{C}\), and the sequence is “coherent” in the sense that \(\eta_\alpha= \eta_\beta\!\restriction\!\mathbb{A}_\alpha\) whenever \(\alpha\leq \beta\). The base step is trivial: there is an embedding \(\eta_0: \mathbb{A}_0 \to \mathbb{C}\) because \(\mathbb{A}_0 = \{\mathbf{0},\mathbf{1}\}\). At successor steps, observe that \((\mathbb{A}_\alpha,\mathbb{A}_{\alpha+1},\iota,\eta_\alpha)\) is an instance of the lifting problem for \(\mathbb{C}\), taking \(\iota\) to be the inclusion map \(\mathbb{A}_\alpha\xhookrightarrow{} \mathbb{A}_{\alpha+1}\). By assumption, there is an embedding \(\eta_{\alpha+1}: \mathbb{A}_{\alpha+1} \to \mathbb{C}\) that extends \(\eta_\alpha\). At limit stages there is nothing to do: because \(\mathbb{A}_\alpha= \bigcup_{\xi < \alpha}\mathbb{A}_\xi\), we can (and must, to preserve coherence) define \(\eta_\alpha= \bigcup_{\xi < \alpha} \eta_\xi\), which is well-defined because the \(\eta_\xi\)’s are coherent. In the end, \(\eta = \bigcup_{\alpha< \omega_1}\eta_\alpha\) is an embedding \(\mathbb{A}\to \mathbb{C}\). ◻

Proof. Let \(\left\langle c_\xi \colon \xi < \omega_1 \right\rangle\) be an enumeration of \(\mathbb{C}\), and let \(\left\langle d_\xi \colon \xi < \omega_1 \right\rangle\) be an enumeration of \(\mathbb{D}\). Using transfinite recursion, we now build a sequence \(\left\langle \phi_\alpha \colon \alpha< \omega_1 \right\rangle\) of maps such that each \(\phi_\alpha\) is an isomorphism of its domain (which we denote \(\mathbb{C}_\alpha\)) to its codomain (which we denote \(\mathbb{D}_\alpha\)); furthermore, we shall have \(\mathbb{C}_\alpha\subseteq\mathbb{C}_\beta\) and \(\mathbb{D}_\alpha\subseteq\mathbb{D}_\beta\) whenever \(\alpha\leq \beta\), \(\mathbb{C}_\alpha= \bigcup_{\xi < \alpha}\mathbb{C}_\xi\) and \(\mathbb{D}_\alpha= \bigcup_{\xi < \alpha}\mathbb{D}_\xi\) for limit \(\alpha\), and the \(\phi_\alpha\)’s will be coherent, in the sense that \(\phi_\alpha= \phi_\beta\!\restriction\!\mathbb{C}_\alpha\) whenever \(\alpha\leq \beta\). Given \(X \subseteq\mathbb{C}\), let \(\langle\langle X \rangle\rangle\) denote the subalgebra of \(\mathbb{C}\) generated by \(X\), and similarly for \(\mathbb{D}\).

For the base case, let \(\mathbb{C}_0 = \{ \mathbf{0}_\mathbb{C},\mathbf{1}_\mathbb{C}\}\) and \(\mathbb{D}_0 = \{ \mathbf{0}_\mathbb{D},\mathbf{1}_\mathbb{D}\}\), and let \(\phi_0\) denote the unique isomorphism \(\mathbb{C}_0 \to \mathbb{D}_0\). At limit stages there is nothing to do: take \(\mathbb{C}_\alpha= \bigcup_{\xi < \alpha}\mathbb{C}_\xi\), \(\mathbb{D}_\alpha= \bigcup_{\xi < \alpha}\mathbb{D}_\xi\), and \(\phi_\alpha= \bigcup_{\xi < \alpha}\phi_\xi\), which is well-defined because the \(\phi_\xi\)’s are coherent.

At successor steps we obtain \(\phi_{\alpha+1}\) from \(\phi_\alpha\) by solving the lifting problem twice, once in the forwards direction and once in the backwards direction. First, let \(\mathbb{D}_{\alpha+1}^0 = \langle\langle \mathbb{D}_\alpha\cup \{d_\alpha\} \rangle\rangle\) and observe that \((\mathbb{D}_\alpha,\mathbb{D}^0_{\alpha+1},\iota,\phi_\alpha^{-1})\) is an instance of the lifting problem for \(\mathbb{C}\), where \(\iota\) denotes the inclusion \(\mathbb{D}_\alpha\xhookrightarrow{} \mathbb{D}_{\alpha+1}^0\). Consequently, there is an isomorphism \(\phi^0_{\alpha+1}\) from \(\mathbb{D}_{\alpha+1}^0\) to some subalgebra \(\mathbb{C}^0_{\alpha+1}\) of \(\mathbb{C}\) with \(\mathbb{C}^0_{\alpha+1} \supseteq \mathbb{C}_\alpha\). Second, let \(\mathbb{C}_{\alpha+1} = \langle\langle \mathbb{C}_\alpha^0 \cup \{c_\alpha\} \rangle\rangle\) and observe that \((\mathbb{C}_{\alpha+1}^0,\mathbb{C}_{\alpha+1},\iota,(\phi_\alpha^0)^{-1})\) is an instance of the lifting problem for \(\mathbb{D}\), where \(\iota\) denotes the inclusion \(\mathbb{C}_{\alpha+1}^0 \xhookrightarrow{} \mathbb{C}_{\alpha+1}\). Thus there is an isomorphism \(\phi_{\alpha+1}\) from \(\mathbb{C}_{\alpha+1}\) to some subalgebra \(\mathbb{D}_{\alpha+1}\) of \(\mathbb{D}\) with \(\mathbb{D}_{\alpha+1} \supseteq \mathbb{D}_{\alpha+1}^0\).

This completes the recursion. Because the \(\phi_\alpha\) are coherent partial isomorphisms, \(\phi = \bigcup_{\alpha< \omega_1}\phi_\alpha\) is an isomorphism from its domain \(\bigcup_{\alpha< \omega_1} \mathbb{C}_\alpha\) to its image \(\bigcup_{\alpha< \omega_1} \mathbb{D}_\alpha\). Furthermore, \(\bigcup_{\alpha< \omega_1} \mathbb{C}_\alpha= \mathbb{C}\), because we ensured at stage \(\alpha+1\) of the recursion that \(c_\alpha\in \mathbb{C}_{\alpha+1}\), and \(\bigcup_{\alpha< \omega_1} \mathbb{D}_\alpha= \mathbb{D}\), because we ensured at stage \(\alpha+1\) of the recursion that \(d_\alpha\in \mathbb{D}_{\alpha+1}\). ◻

Proof. This follows immediately from Theorems 2 and 4. ◻

Proof. This can be found in [25]; but the proof is short and not difficult, so we reproduce it here.

Let \(a \in \frac{\mathcal{P}(\omega)}{\mathrm{Fin}}\) with \(a \neq \mathbf{0},\mathbf{1}\). In other words, let \(a\) be the equivalence class \([A]\) of some \(A \subseteq\omega\) that is neither finite (since then \([A] = [\emptyset] = \mathbf{0}\)) nor co-finite (since then \([A] = [\omega] = \mathbf{1}\)). Because \(A\) is neither finite nor co-finite, the set \(B = \left\lbrace n \in A \colon n+1 \notin A \right\rbrace\) is infinite. But then \[\sigma([A]) - [A] \,=\, [A+1] - [A] \,=\, [(A+1) \setminus A] \,=\, [B+1] \,\neq\, \mathbf{0},\] which means that \(\sigma(a) = \sigma([A]) \not\leq [A] = a\).

A similar proof works for \(\langle \frac{\mathcal{P}(\omega)}{\mathrm{Fin}},\sigma^{-1} \rangle\). Alternatively, one may observe that, in general, \(\langle \mathbb{A},\alpha\rangle\) is compressible if and only if \(\langle \mathbb{A},\alpha^{-1} \rangle\) is, because if \(\alpha(x) \leq x\) then \(\alpha^{-1}(\mathbf{1}-x) \leq \mathbf{1}-x\). ◻

Proof. Like the previous theorem, this is a known fact and can be found (in dual form) in [26] or [25]. But like the previous theorem, the proof is short and not difficult, so we reproduce it here.

Suppose \(\eta\) is an embedding of \(\langle \mathbb{A},\alpha\rangle\) into an incompressible dynamical system \(\langle \mathbb{B},\beta\rangle\), and let \(x \in \mathbb{A}\setminus \{ \mathbf{0},\mathbf{1} \}\). Then \(\beta(\eta(x)) \not\leq \eta(x)\) (by the incompressibility of \(\langle \mathbb{B},\beta\rangle\)), which implies \(\eta(\alpha(x)) \not\leq \eta(x)\) (because \(\eta \circ \alpha= \beta\circ \eta\)), which implies \(\alpha(x) \not\leq x\) (because \(\eta^{-1}\) preserves inequalities). Thus \(\langle \mathbb{A},\alpha\rangle\) is incompressible. ◻

Proof. This is a straightforward adaptation of the proof of Theorem 3. ◻

Proof. Suppose \(\left\langle a_n \colon n \in \omega \right\rangle\) is an eventually small, eventually dense sequence in \(\mathbb{A}\setminus \{00\}\), and define \(\eta: \mathbb{A}\to \frac{\mathcal{P}(\omega)}{\mathrm{Fin}}\) by setting \(\eta(a) = [\left\lbrace n \in \omega \colon a_n \leq a \right\rbrace]\).

The definition of \(\eta\) readily implies \(\eta(\mathbf{0}) = [\emptyset]\) and \(\eta(\mathbf{1}) = [\omega]\). Now suppose \(a,b \in \mathbb{A}\). Let \(\mathcal{U}= \{ a-b,b-a,a \wedge b, \mathbf{1} - (a \vee b)\} \setminus \{\mathbf{0}\}\) (the partition of \(\mathbb{A}\) generated by \(a\) and \(b\)). Because \(\left\langle a_n \colon n \in \omega \right\rangle\) is eventually small, there is some \(N \in \omega\) such that if \(n \geq N\) then \(a_n\) is below \(\mathcal{U}\). It follows that \[\begin{align} \left\lbrace n \in \omega \colon a_n \leq a \vee b \right\rbrace =^* & \\ \left\lbrace n \in \omega \colon a_n \leq a-b \right\rbrace &\cup \left\lbrace n \in \omega \colon a_n \leq b-a \right\rbrace \cup \left\lbrace n \in \omega \colon a_n \leq a \wedge b \right\rbrace \\ =\, \left\lbrace n \in \omega \colon a_n \leq a \right\rbrace &\cup \left\lbrace n \in \omega \colon a_n \leq b \right\rbrace \end{align}\] which means that \[\begin{align} \eta(a \vee b) &\,=\, [\left\lbrace n \in \omega \colon a_n \leq a \vee b \right\rbrace] \,=\, [\left\lbrace n \in \omega \colon a_n \leq a \right\rbrace \cup \left\lbrace n \in \omega \colon a_n \leq b \right\rbrace] \\ &\,=\, [\left\lbrace n \in \omega \colon a_n \leq a \right\rbrace] \vee [\left\lbrace n \in \omega \colon a_n \leq b \right\rbrace] \,=\, \eta(a) \vee \eta(b). \end{align}\] A similar computation shows \(\eta(a \wedge b) = \eta(a) \wedge \eta(b)\) and \(\eta(\mathbf{1} - a) = \mathbf{1} - \eta(a)\).

Thus \(\eta\) is a homomorphism \(\mathbb{A}\to \frac{\mathcal{P}(\omega)}{\mathrm{Fin}}\). To check that it is injective, suppose \(a \in \mathbb{A}\) and \(a \neq 00\). Because \(\left\langle a_n \colon n \in \omega \right\rangle\) is eventually dense, \(\left\lbrace n \colon a_n \leq a \right\rbrace\) is infinite, which means \(\eta(a) = [\left\lbrace n \colon a_n \leq a \right\rbrace] \neq [\emptyset]\). In other words, the kernel of the homomorphism \(\eta\) is \(\{00\}\), and this implies \(\eta\) is injective. ◻

Proof. Let \(\left\langle a_k \colon k \in \omega \right\rangle\) be an enumeration of \(\mathbb{A}\setminus \{\mathbf{0}\}\), and for each \(n \in \omega\) let \(\mathcal{U}_n\) be the partition of \(\mathbb{A}\) generated by \(\left\lbrace a_k \colon k \leq n \right\rbrace\). ◻

Proof. Let \(\mathbb{A}\) be a countable Boolean algebra. Fix a sequence \(\mathcal{U}_0,\mathcal{U}_1,\mathcal{U}_2,\dots\) of partitions of \(\mathbb{A}\) with the properties stated in Lemma 1.

For \((1)\), let \(\left\langle a_n \colon n \in \omega \right\rangle\) be a sequence of members of \(\mathbb{A}\) obtained by simply listing the (finitely many) members of \(\mathcal{U}_0\), then listing the members of \(\mathcal{U}_1\), then \(\mathcal{U}_2\), etc. This sequence is both eventually small and eventually dense, so it induces an embedding \(\mathbb{A}\to \frac{\mathcal{P}(\omega)}{\mathrm{Fin}}\) by Theorem 10.

For \((2)\), suppose \(\eta: \mathbb{A}\to \frac{\mathcal{P}(\omega)}{\mathrm{Fin}}\) is an embedding. For each \(a \in \mathbb{A}\) fix a representative \(X_a\) of the equivalence class \(\eta(a)\): that is, \(X_a \subseteq\omega\) and \(\eta(a) = [X_a]\). For convenience, define \(n_{-1} = 0\), and then, for each \(k\), define \(n_k\) to be some natural number large enough that:

1. \(n_k > n_{k-1}\).

2. For each \(a \in \mathcal{U}_k\), \(X_a \cap [n_{k-1},n_k) \neq \emptyset\).

3. If \(a \in \mathbb{A}\) and \(a = \bigvee \left\lbrace u \in \mathcal{U}_k \colon u \leq a \right\rbrace\), then \[\left\lbrace X_u \setminus n_k \colon u \in \mathcal{U}_{k+1} \text{ and } u \leq a \right\rbrace\] is a partition of \(X_a \setminus n_k\).

It is clear that all sufficiently large \(n_k\) satisfy \((1)\) and \((2)\). For condition \((3)\), let \(A = \left\lbrace u \in \mathcal{U}_{k+1} \colon u \leq a \right\rbrace\), suppose \(a = \bigvee A\), and recall that, in \(\frac{\mathcal{P}(\omega)}{\mathrm{Fin}}\), \[[X_u] \wedge [X_{u'}] = \eta(u) \wedge \eta(u') = \eta(u \wedge u') = \eta(00) = [\emptyset]\] for all \(u,u' \in A\) with \(u \neq u'\). In other words, the sets in \(\left\lbrace X_u \colon u \in A \right\rbrace\) are “pairwise almost disjoint" in the sense that \(\left\lbrace X_u \setminus n \colon u \in A \right\rbrace\) are pairwise disjoint above \(N\) for large enough \(N\). Similarly, \([X_a] = \bigvee_{u \in A}[X_u]\) in \(\frac{\mathcal{P}(\omega)}{\mathrm{Fin}}\), and this implies \(\bigcup \left\lbrace X_u \setminus N \colon u \in A \right\rbrace = X_a \setminus N\) for large enough \(N\).

This describes the \(n_k\). Next, for each \(n \in \omega\), define \[a_n = a \qquad \text{ if and only if } \qquad n \in [n_{k-1},n_k), \, a \in \mathcal{U}_k, \text{ and }n \in X_a.\] We claim that this sequence is eventually small and eventually dense, and that it induces the embedding \(\eta: \mathbb{A}\to \frac{\mathcal{P}(\omega)}{\mathrm{Fin}}\).

The sequence is eventually small because for every partition \(\mathcal{V}\) of \(\mathbb{A}\), \(\mathcal{U}_k\) refines \(\mathcal{V}\) for all sufficiently large \(k\), which implies (by the definition of the \(a_n\)) that \(a_n\) is below \(\mathcal{V}\) for all sufficiently large \(n\).

To see that \(\left\langle a_n \colon n \in \omega \right\rangle\) is eventually dense, fix some \(a \in \mathbb{A}\setminus \{00\}\). There is some \(K \in \omega\) such that \(\mathcal{U}_k\) refines \(\{a,\mathbf{1} - a\}\) whenever \(k \geq K\). But then condition \((2)\) of our choice of the \(n_k\) implies that in every interval \([n_{k-1},n_k)\), there is some \(n\) such that \(a_n \leq a\). Hence \(\left\lbrace n \in \omega \colon a_n \leq a \right\rbrace\) is infinite.

Finally, we must show that \(\eta\) is induced by \(\left\langle a_n \colon n \in \omega \right\rangle\). Let \(\eta'\) be the embedding \(\mathbb{A}\to \frac{\mathcal{P}(\omega)}{\mathrm{Fin}}\) induced by \(\left\langle a_n \colon n \in \omega \right\rangle\) and fix \(a \in \mathbb{A}\). By our choice of the \(\mathcal{U}_k\), there is some \(K \in \omega\) such that \(\mathcal{U}_k\) refines \(\{a,\mathbf{1} - a\}\) whenever \(k \geq K\), which implies \(a = \bigvee \left\lbrace u \in \mathcal{U}_k \colon u \leq a \right\rbrace\) for all \(k \geq K\). By part \((3)\) of our choice of the \(n_k\), and by the definition of the \(a_n\), this implies that if \(n \geq n_K\), then \(a_n \leq a\) if and only if \(n \in X_a\). Thus \[\eta'(a) \,=\, [\left\lbrace n \in \omega \colon a_n \leq a \right\rbrace] \,=\, [X_a \setminus n_K] \,=\, [X_a] \,=\, \eta(a).\] As \(a\) was arbitrary, this shows \(\eta = \eta'\). ◻

Proof. For the “if” direction, fix two eventually small, eventually dense sequences \(\left\langle a_n \colon n \in \omega \right\rangle\), \(\left\langle b_n \colon n \in \omega \right\rangle\) in \(\mathbb{A}\) with \(\left\langle a_n \colon n \in \omega \right\rangle \approx \left\langle b_n \colon n \in \omega \right\rangle\). Fix some \(a \in \mathbb{A}\), and let \(\mathcal{U}= \{a,11-a\}\). Because \(\left\langle a_n \colon n \in \omega \right\rangle\) and \(\left\langle b_n \colon n \in \omega \right\rangle\) are eventually small, \(a_n\) and \(b_n\) are below \(\mathcal{U}\) for all sufficiently large \(n\). But also \(a_n \approx_\mathcal{U}b_n\) for sufficiently large \(n\). Combining these two things, if \(n\) is sufficiently large then either \(a_n,b_n \leq a\) or else \(a_n,b_n \leq \mathbf{1} - a\). Therefore \(\left\lbrace n \colon a_n \leq a \right\rbrace =^* \left\lbrace n \colon b_n \leq a \right\rbrace\), which means the embedding induced by \(\left\langle a_n \colon n \in \omega \right\rangle\) and the embedding induced by \(\left\langle b_n \colon n \in \omega \right\rangle\) both map \(a\) to the same member of \(\frac{\mathcal{P}(\omega)}{\mathrm{Fin}}\), namely \([\left\lbrace n \colon a_n \leq a \right\rbrace] = [\left\lbrace n \colon b_n \leq a \right\rbrace]\). As \(a\) was arbitrary, these two sequences induce the same embedding.

For the “only if” direction, fix two eventually small, eventually dense sequences \(\left\langle a_n \colon n \in \omega \right\rangle\), \(\left\langle b_n \colon n \in \omega \right\rangle\) in \(\mathbb{A}\) that induce the same embedding \(\mathbb{A}\to \frac{\mathcal{P}(\omega)}{\mathrm{Fin}}\). Let \(\mathcal{U}\) be a partition of \(\mathbb{A}\). Because \(\left\langle a_n \colon n \in \omega \right\rangle\) and \(\left\langle b_n \colon n \in \omega \right\rangle\) are eventually small, \(a_n\) and \(b_n\) are below \(\mathcal{U}\) for sufficiently large \(n\). In particular, \(a_n\) and \(b_n\) are each below exactly one member of \(\mathcal{U}\) for all sufficiently large \(n\). For any particular \(u \in \mathcal{U}\), \[\left\lbrace n \colon a_n \leq u \right\rbrace \,=^*\, \left\lbrace n \colon b_n \leq u \right\rbrace\] (because the sequences induce the same embedding \(\mathbb{A}\to \frac{\mathcal{P}(\omega)}{\mathrm{Fin}}\)). As this is true for every \(u \in \mathcal{U}\), \(a_n\) and \(b_n\) are each below the same member of \(\mathcal{U}\) for sufficiently large \(n\). Consequently, \(\left\langle a_n \colon n \in \omega \right\rangle \approx_\mathcal{U}\left\langle b_n \colon n \in \omega \right\rangle\). ◻

Proof. Let \(\eta\) denote the embedding \(\mathbb{A}\to \frac{\mathcal{P}(\omega)}{\mathrm{Fin}}\) induced by \(\left\langle a_n \colon n \in \omega \right\rangle\). Observe that \[\sigma^{-1} \circ \eta(a) = \sigma^{-1}([\left\lbrace n \colon a_n \leq a \right\rbrace]) = [\left\lbrace n-1 \colon a_n \leq a \right\rbrace] = [\left\lbrace n \colon a_{n+1} \leq a \right\rbrace]\] for every \(a\), which means that \(\sigma^{-1} \circ \eta\) is the embedding \(\mathbb{A}\to \frac{\mathcal{P}(\omega)}{\mathrm{Fin}}\) induced by the sequence \(\left\langle a_{n+1} \colon n \in \omega \right\rangle\). Likewise, \[\eta \circ \alpha^{-1}(a) = [\left\lbrace n \colon a_n \leq \alpha^{-1}(a) \right\rbrace] = [\left\lbrace n \colon \alpha(a_n) \leq a \right\rbrace]\] for every \(a\), which means that \(\eta \circ \alpha^{-1}\) is the embedding \(\mathbb{A}\to \frac{\mathcal{P}(\omega)}{\mathrm{Fin}}\) induced by the sequence \(\left\langle \alpha(a_n) \colon n \in \omega \right\rangle\).

By Theorem 12, this implies that \(\eta\) is an embedding from \(\langle\mathbb{A},\alpha^{-1}\rangle\) to \(\langle\frac{\mathcal{P}(\omega)}{\mathrm{Fin}},\sigma^{-1}\rangle\) if and only if \(\left\langle a_{n+1} \colon n \in \omega \right\rangle \approx \left\langle \alpha(a_n) \colon n \in \omega \right\rangle\). This proves the theorem, because \(\eta\) is an embedding from \(\langle\mathbb{A},\alpha^{-1}\rangle\) to \(\langle\frac{\mathcal{P}(\omega)}{\mathrm{Fin}},\sigma^{-1}\rangle\) if and only if it is also an embedding from \(\langle\mathbb{A},\alpha\rangle\) to \(\langle\frac{\mathcal{P}(\omega)}{\mathrm{Fin}},\sigma\rangle\). (This is because \(\eta \circ \alpha^{-1} = \sigma^{-1} \circ \eta\) implies \(\sigma\circ \eta = \sigma\circ (\eta \circ \alpha^{-1}) \circ \alpha= \sigma\circ (\sigma^{-1} \circ \eta) \circ \alpha= \eta \circ \alpha\), and similarly \(\sigma\circ \eta = \eta \circ \alpha\) implies \(\eta \circ \alpha^{-1} = \sigma^{-1} \circ \eta\).) ◻

Proof. We’ve proved already that \((1) \Leftrightarrow (2)\): that \((2) \Rightarrow (1)\) follows from Theorem 13, and that \((1) \Rightarrow (2)\) follows from Theorem 13 together with Theorem 11(2). It remains to prove \((2) \Leftrightarrow (3)\).

To see that \((3) \Rightarrow (2)\), suppose \(\left\langle a_n \colon n \in \omega \right\rangle\) satisfies condition \((3)\). Let \(\mathcal{U}\) be a partition of \(\mathbb{A}\). Because \(\left\langle a_n \colon n \in \omega \right\rangle\) is eventually small, \(a_{n+1}\) and \(\alpha(a_n)\) are both below \(\mathcal{U}\) for sufficiently large \(n\). Because \(\alpha(a_n) \wedge a_{n+1} \neq \mathbf{0}\), this implies \(a_{n+1}\) and \(\alpha(a_n)\) are below the same member of \(\mathcal{U}\) for sufficiently large \(n\). Hence \(\alpha(a_n) \approx_\mathcal{U}^* a_{n+1}\). As \(\mathcal{U}\) was arbitrary, this shows that \(\left\langle \alpha(a_n) \colon n \in \omega \right\rangle \approx \left\langle a_{n+1} \colon n \in \omega \right\rangle\).

To see that \((2) \Rightarrow (3)\), suppose \(\left\langle a_n \colon n \in \omega \right\rangle\) satisfies condition \((2)\). Let \(\mathcal{U}_0,\mathcal{U}_1,\mathcal{U}_2,\dots\) be a sequence of partitions of \(\mathbb{A}\) with the properties stated in Lemma 1. For every \(k \in \omega\), let \(\mathcal{V}_k\) be the partition of \(\mathbb{A}\) generated by the (finite) set \(\mathcal{U}_k \cup \left\lbrace \alpha^{-1}(u) \colon u \in \mathcal{U}_k \right\rbrace\). Because \(\left\langle a_n \colon n \in \omega \right\rangle\) is eventually small, for every \(k \in \omega\) there is some \(N_k \in \omega\) such that \(a_n\) is below \(\mathcal{V}_k\) for all \(n \geq N_k\). By our choice of \(\mathcal{V}_k\), this implies that both \(\alpha(a_n)\) and \(a_{n+1}\) are below \(\mathcal{U}_k\) whenever \(n \geq N_k\). Furthermore, because \(\left\langle \alpha(a_n) \colon n \in \omega \right\rangle \approx \left\langle a_{n+1} \colon n \in \omega \right\rangle\), \(\alpha(a_n)\) and \(a_{n+1}\) are below the same member of \(\mathcal{U}_k\) whenever \(n \geq N_k\).

Define a new sequence \(\left\langle b_n \colon n \in \omega \right\rangle\) in \(\mathbb{A}\) by setting \(b_n\) equal to the unique \(u \in \mathcal{U}_k\) with \(a_n \leq u\) whenever \(n \in [N_k,N_{k+1})\), and \(b_n = \mathbf{1}\) whenever \(n < N_0\). By the conclusion of the previous paragraph, this new sequence satisfies the condition in \((3)\). ◻

Proof. We begin by describing a particular instance of the lifting problem for \(\langle \frac{\mathcal{P}(\omega)}{\mathrm{Fin}},\sigma\rangle\). Recall that an instance of the lifting problem consists of two countable incompressible dynamical systems \(\langle\mathbb{A},\alpha\rangle\) and \(\langle\mathbb{B},\beta\rangle\), an embedding \(\iota\) from \(\langle\mathbb{A},\alpha\rangle\) into \(\langle\mathbb{B},\beta\rangle\), and an embedding \(\eta\) from \(\langle \mathbb{A},\alpha\rangle\) into \(\langle \frac{\mathcal{P}(\omega)}{\mathrm{Fin}},\sigma\rangle\). Let us start by describing the Stone duals of \(\mathbb{A}\) and \(\mathbb{B}\).

The topological space \(X\) (whose Stone dual gives us \(\mathbb{A}\)) is a \(3\)-point compactification of \(4\) copies of \(\mathbb{Z}\): \[X \,=\, \big( \{0,1,2,3\} \times \mathbb{Z}\big) \cup \{ a,b,c \}\] where points of the form \((i,n)\) are discrete, the basic neighborhoods of \(a\) have the form \(\{a\} \cup \big( \{0,1\} \times (-\infty,n] \big)\), the basic neighborhoods of \(c\) have the form \(\{c\} \cup \big( \{2,3\} \times [n,\infty) \big)\), and the basic neighborhoods of \(b\) have the form \(\{b\} \cup \big(\{0,1\} \times [n,\infty) \big) \cup \big( \{2,3\} \times (-\infty,n] \big)\).

Let \(\mathbb{A}\) denote the Boolean algebra of clopen subsets of \(X\). Define a homeomorphism \(f: X \to X\) by setting \[f(a) = a, \quad f(b) = b, \quad f(c) = c,\] \[f(i,n) = (i,n+1) \text{ for i = 0,2},\] \[f(i,n) = (i,n-1) \text{ for i = 1,3}.\]

Define \(\alpha: \mathbb{A}\to \mathbb{A}\) by setting \(\alpha(A) = f[A]\) (where \(f[A]\) denotes the image of \(A\) under the map \(f\)). This is well-defined, because homeomorphisms map clopen sets to clopen sets, and it is an automorphism of \(\mathbb{A}\). So \(\langle \mathbb{A},\alpha\rangle\) is an algebraic dynamical system.

The topological space \(Y\) (whose Stone dual gives us \(\mathbb{B}\)) is a \(4\)-point compactification of \(6\) copies of \(\mathbb{Z}\): \[Y \,=\, \big( \{0,1,2,3,4,5\} \times \mathbb{Z}\big) \cup \{ a,b,c,d \}\] where points of the form \((i,n)\) are discrete, the basic neighborhoods of \(a\) have the form \(\{a\} \cup \big( \{0,1\} \times (-\infty,n] \big)\), the basic neighborhoods of \(d\) have the form \(\{d\} \cup \big( \{4,5\} \times [n,\infty) \big)\), the basic neighborhoods of \(b\) have the form \(\{b\} \cup \big( \{0,1\} \times [n,\infty) \big) \cup \big( \{2,3\} \times (-\infty,n] \big)\), and the basic neighborhoods of \(c\) have the form \(\{c\} \cup \big( \{2,3\} \times [n,\infty) \big) \cup \big( \{4,5\} \times (-\infty,n] \big)\).

Let \(\mathbb{B}\) denote the Boolean algebra of clopen subsets of \(Y\). Define a homeomorphism \(g: Y \to Y\) by setting \[g(a) = a, \quad g(b) = b, \quad g(c) = c, \quad g(d) = d,\] \[g(i,n) = (i,n+1) \text{ for i = 0,2,4},\] \[g(i,n) = (i,n-1) \text{ for i = 1,3,5}.\]

Define \(\beta: \mathbb{B}\to \mathbb{B}\) by setting \(\beta(B) = g[B]\). This is an automorphism of \(\mathbb{B}\), so \(\langle \mathbb{B},\beta\rangle\) is an algebraic dynamical system.

Note that \(X\) and \(Y\) have been defined so that \(X \subseteq Y\), and \(f = g \!\restriction\!X\). Define a projection map \(\pi: Y \to X\) by setting \(\pi(x) = x\) for all \(x \in X\), and otherwise set \[\pi(d) = b, \qquad \pi(4,n) = (3,-n), \qquad \pi(5,n) = (2,-n).\] Roughly speaking, \(\pi\) takes the rightmost third of \(Y\) from our picture, and rotates it around the point \(c\) precisely one half turn, until it sits on top of the middle third. We then define \(\iota(A) = \pi^{-1}(A)\) for all \(A \in \mathbb{A}\). This is a Boolean-algebraic embedding (the Stone dual of \(\pi\)). On the topological side, we have \(\pi \circ g = f \circ \pi\), and it follows that \(\iota \circ \alpha= \beta\circ \iota\) on the algebraic side. Hence \(\iota\) is an embedding of \(\langle \mathbb{A},\alpha\rangle\) into \(\langle \mathbb{B},\beta\rangle\).

To finish our description of the counterexample, we must define an embedding \(\eta\) from \(\langle \mathbb{A},\alpha\rangle\) into \(\langle \frac{\mathcal{P}(\omega)}{\mathrm{Fin}},\sigma\rangle\). We do this by describing an eventually small, eventually dense sequence \(\left\langle a_n \colon n \in \omega \right\rangle\) of members of \(\mathbb{A}\) such that \(\left\langle \alpha(a_n) \colon n \in \omega \right\rangle \approx \left\langle a_{n+1} \colon n \in \omega \right\rangle\).

The sequence is chosen so that each \(a_n\) is a clopen singleton in \(X\). The pattern of the sequence is depicted below. Roughly, the idea is to follow the action of \(\alpha\) for increasingly long stretches along each of the \(4\) copies of \(\mathbb{Z}\) in \(X\), jumping to the next stretch at some prescribed time.

More precisely, define the first \(4\) elements of the sequence as: \[a_0 = \{(0,0)\}, \quad a_1 = \{(2,0)\}, \quad a_2 = \{(3,0)\}, \quad a_3 = \{(1,0)\}.\] Then define the next \(12\) elements of the sequence by taking \[a_5 = a_0, \quad a_8 = a_1, \quad a_{11} = a_2, \quad a_{14} = a_3,\] and then defining \(a_{i-1} = \alpha^{-1}(a_i)\) and \(a_{i+1} = \alpha(a_i)\) for \(i = 5,8,11,14\). Then define the next \(20\) members of the sequence similarly: \[a_{18} = a_0, \quad a_{23} = a_1, \quad a_{28} = a_2, \quad a_{33} = a_3,\] and \(a_{i + j} = \alpha^{j}(a_i)\) for \(i = 18,23,28,33\) and \(j = \pm1,\pm2\). The remainder of the sequence is defined similarly.

This sequence is eventually small. In fact, every member of this sequence is an atom of \(\mathbb{A}\), and so every member of this sequence is below every partition of \(\mathbb{A}\).

This sequence is eventually dense. Indeed, note that for any isolated \(p \in X\), there are infinitely many \(n\) such that \(a_n = \{p\}\). If \(A \in \mathbb{A}\), then there is some isolated \(p \in X\) with \(\{p\} \subseteq A\), and therefore we have infinitely many \(n\) with \(a_n = \{p\} \subseteq A\).

Finally, \(\left\langle \alpha(a_n) \colon n \in \omega \right\rangle \approx \left\langle a_{n+1} \colon n \in \omega \right\rangle\). To see this, let \(\mathcal{U}\) be a partition of \(\mathbb{A}\). For many values of \(n\), we defined \(a_{n+1} = \alpha(a_n)\), and for these values of \(n\) we have \(a_{n+1} \approx_\mathcal{U}\alpha(a_n)\). For the other values of \(n\), either

• \(a_n = \{(0,k)\}\) and \(a_{n+1} = \{(2,-k)\}\), or

• \(a_n = \{(2,k)\}\) and \(a_{n+1} = \{(3,k)\}\), or

• \(a_n = \{(3,-k)\}\) and \(a_{n+1} = \{(1,k)\}\), or

• \(a_n = \{(1,-k)\}\) and \(a_{n+1} = \{(0,-k-1)\}\).

The partition \(\mathcal{U}\) consists of finitely many clopen subsets of \(X\), including some \(A \ni a\), \(B \ni b\), and \(C \ni c\). For large enough values of \(n\), the corresponding \(k\)-values in the bulleted list above will also be large, large enough that \((0,k)\) and \((2,-k)\) are both in \(B\), and \((2,k)\) and \((3,k)\) are both in \(C\), etc. Thus for large enough \(n\), we still have \(a_{n+1} \approx_\mathcal{U}\alpha(a_n)\) even when we do not have \(a_{n+1} = \alpha(a_n)\). Because this is true for any partition \(\mathcal{U}\), this shows that \(\left\langle \alpha(a_n) \colon n \in \omega \right\rangle \approx \left\langle a_{n+1} \colon n \in \omega \right\rangle\) as claimed.

By Theorem 13, the sequence \(\left\langle a_n \colon n \in \omega \right\rangle\) induces an embedding of \(\langle \mathbb{A},\alpha\rangle\) into \(\langle \frac{\mathcal{P}(\omega)}{\mathrm{Fin}},\sigma\rangle\). Let \(\eta\) denote this embedding.

This completes our description of the counterexample: \((\langle\mathbb{A},\alpha\rangle,\langle\mathbb{B},\beta\rangle,\iota,\eta)\) is an instance of the lifting problem for \(\langle \frac{\mathcal{P}(\omega)}{\mathrm{Fin}},\sigma\rangle\). It remains to prove that this instance of the lifting problem has no solution.

Suppose, aiming for a contradiction, that \(\bar \eta\) is a lifting of \(\eta\) to \(\langle\mathbb{B},\beta\rangle\), so that \(\eta = \bar \eta \circ \iota\). By Theorem 13, there is some eventually small, eventually dense sequence \(\left\langle b_n \colon n \in \omega \right\rangle\) in \(\mathbb{B}\) that induces the embedding \(\bar \eta\), with the property that \(\beta(b_n) \wedge b_{n+1} \neq \mathbf{0}\) for all \(n\).

Roughly, the problem here is that to be eventually dense, the sequence \(\left\langle b_n \colon n \in \omega \right\rangle\) must get close to \(d\) infinitely often. The only way to do this is to enter the region near \(d\) from the region near \(c\), and then to exit again into the region near \(c\). Using the fact that \(\eta = \bar \eta \circ \iota\), this means that the sequence \(\left\langle a_n \colon n \in \omega \right\rangle\) must infinitely often be going near \(c\), and then near \(b = \pi(d)\), and then near \(c\) again. But the sequence of \(a_n\)’s does not behave this way: it was chosen so that whenever it goes from near \(c\) to near \(b\), it will, every time, continue on in the direction of \(a\), not back towards \(c\).

Let us make this idea more precise. Let \(\mathcal{U}= \{ A,B,C \}\) be a partition of \(\mathbb{A}\) into three elements, with \(a \in A\) and \(b \in B\), and \(c \in C\). Note that \(\iota(B) = \pi^{-1}(B) \in \mathbb{B}\), and \(b,d \in \iota(B)\). Fix some \(\bar B,\bar D \in \mathbb{B}\) such that \(\bar B \cup \bar D = \iota(B)\), with \(b \in \bar B\) and \(d \in \bar D\). Let \(\bar A = \iota(A)\) and \(\bar C = \iota(C)\), and let \(\mathcal{V}= \{ \bar A,\bar B,\bar C,\bar D \}\). Thus \(\mathcal{V}\) is a partition of \(\mathbb{B}\) into four elements, with \(a \in \bar A\), \(b \in \bar B\), \(c \in \bar C\), and \(d \in \bar D\).

Because \(\left\langle a_n \colon n \in \omega \right\rangle\) and \(\left\langle b_n \colon n \in \omega \right\rangle\) are eventually small, \(a_n\) is below \(\mathcal{U}\) and \(b_n\) is below \(\mathcal{V}\) for sufficiently large \(n\). Furthermore, because \(\eta = \bar \eta \circ \iota\), \[\begin{align} [\left\lbrace n \in \omega \colon a_n \leq A \right\rbrace] &\,=\, \eta(A) \,=\, \bar \eta \circ \iota(A) \,=\, \bar \eta(\bar A) \,=\, [\left\lbrace n \in \omega \colon b_n \leq \bar A \right\rbrace], \end{align}\] which means that \(\left\lbrace n \in \omega \colon a_n \in A \right\rbrace =^* \left\lbrace n \in \omega \colon b_n \in \bar A \right\rbrace\), and so \[a_n \leq A \quad \text{if and only if} \quad b_n \leq \bar A\] for sufficiently large \(n\). Because \(\iota\) is an embedding \(\mathbb{A}\to \mathbb{B}\), \(a_n \leq A\) if and only if \(\iota(a_n) \leq \iota(A) = \bar A\). Hence \[\iota(a_n) \leq \bar A \quad \text{if and only if} \quad b_n \leq \bar A\] for sufficiently large \(n\). Similarly, \[\iota(a_n) \leq \bar B \cup \bar D \quad \text{if and only if} \quad b_n \leq \bar B \cup \bar D, \text{ and}\] \[\iota(a_n) \leq \bar C \quad \text{if and only if} \quad b_n \leq \bar C\] for sufficiently large \(n\). Because \(a_n\) is below \(\mathcal{U}\) and \(b_n\) below \(\mathcal{V}\) for sufficiently large \(n\), this means each of \(\iota(a_n)\) and \(b_n\) is \(\leq\) exactly one of \(\bar A\), \(\bar B \cup \bar D\), and \(\bar C\) for large enough \(n\). Combined with the three displayed assertions above, this implies \(\iota(a_n) \approx_\mathcal{V}b_n\) for sufficiently large \(n\). Fix \(N \in \omega\) such that \(n \geq N\) implies \(\iota(a_n) \approx_\mathcal{V}b_n\).

Using the fact that \(\left\langle b_n \colon n \in \omega \right\rangle\) is eventually dense, fix some \(i \geq N\) such that \(b_i \not\leq \bar D\) and some \(k > i\) such that \(b_k \leq \bar D\).

Let \(j\) denote the maximum integer \(<\! k\) such that \(b_j \not\leq \bar D\). (Note that \(N \leq i \leq j < k\).) Let \(\ell\) denote the minimum integer \(>\! k\) such that \(b_\ell \not\leq \bar D\). (Some such \(k\) must exist because \(\left\langle b_n \colon n \in \omega \right\rangle\) is eventually dense, and so infinitely often \(b_n \leq \mathbf{1} - \bar D\).) Thus \(b_j \not\leq \bar D\) and \(b_\ell \not\leq \bar D\), but \(b_n \leq \bar D\) for every \(n \in (j,\ell)\). In fact, because \(b_j\) and \(b_\ell\) are below \(\mathcal{V}\), we have \(b_j \wedge \bar D = b_\ell \wedge \bar D = \mathbf{0}\).

Recall that \(\beta(b_n) \wedge b_{n+1} \neq \mathbf{0}\) for all \(n\). Because \(b_{\ell-1} \leq \bar D\), we must have \(b_\ell \wedge \beta(\bar D) \neq \mathbf{0}\). But \(\beta(\bar D) \leq \bar D \vee \bar C\) and \(b_\ell \wedge \bar D = \mathbf{0}\), so this implies \(b_\ell \wedge \bar C \neq \mathbf{0}\). Because \(b_\ell\) is below \(\mathcal{V}\), we see that \(b_\ell \leq \bar C\). Similarly, because \(b_{j+1} \leq \bar D\) we must have \(b_j \wedge \beta^{-1}(\bar D) \neq \mathbf{0}\). But \(\beta^{-1}(\bar D) \leq \bar D \vee \bar C\) and \(b_j \wedge \bar D = \mathbf{0}\), so this implies \(b_j \wedge \bar C \neq \mathbf{0}\). Because \(b_j\) is below \(\mathcal{V}\), we get \(b_j \leq \bar C\).

Hence \(b_j,b_\ell \leq \bar C\), and \(b_n \leq \bar D\) for all \(n \in (j,\ell)\). Because \(\iota(a_n) \approx_\mathcal{V}b_n\) for all \(n \geq N\), this means that \(\iota(a_j) \wedge \bar C \neq \mathbf{0}\), \(\iota(a_\ell) \wedge \bar C \neq \mathbf{0}\), and \(\iota(a_n) \wedge \bar D \neq \mathbf{0}\) for all \(n \in (j,\ell)\). But \(a_n\) is below \(\mathcal{U}\) for all \(n \in [j,\ell]\), so the only way for this to happen is if \(a_j \leq C\), then \(a_n \leq B\) for all \(n \in (j,\ell)\), and then \(a_\ell \leq C\).

We have arrived at our sought-after contradiction, because the sequence \(\left\langle a_n \colon n \in \omega \right\rangle\) never exhibits this behavior. If \(a_j \leq C\) and \(a_n \leq B\) for all \(n \in (j,\ell)\), then (by our definition of the \(a_n\)’s), we must have either \(a_\ell \leq B\) or \(a_\ell \leq A\). ◻

Proof. If \((\langle\mathbb{A},\alpha\rangle,\langle\mathbb{B},\beta\rangle,\iota,\eta)\) is an instance of the lifting problem for
\(\langle \frac{\mathcal{P}(\omega)}{\mathrm{Fin}},\sigma^{-1} \rangle\), then \((\langle \mathbb{A},\alpha^{-1} \rangle,\langle \mathbb{B},\beta^{-1} \rangle,\iota,\eta)\) is an instance of the lifting problem for \(\langle \frac{\mathcal{P}(\omega)}{\mathrm{Fin}},\sigma\rangle\). Furthermore, if the image of \(\langle \mathbb{A},\alpha\rangle\) under \(\eta\) is an elementary substructure of \(\langle \frac{\mathcal{P}(\omega)}{\mathrm{Fin}},\sigma\rangle\), then the image of \(\langle \mathbb{A},\alpha^{-1} \rangle\) under \(\eta\) is an elementary substructure of \(\langle \frac{\mathcal{P}(\omega)}{\mathrm{Fin}},\sigma^{-1} \rangle\). (In fact the images coincide, and this assertion really just amounts to the fact that if \(\eta\) transforms true sentences about \(\langle \mathbb{A},\alpha\rangle\) into true sentences about \(\langle \frac{\mathcal{P}(\omega)}{\mathrm{Fin}},\sigma\rangle\), then it must also transform true sentences about \(\langle \mathbb{A},\alpha^{-1} \rangle\) into true sentences about \(\langle \frac{\mathcal{P}(\omega)}{\mathrm{Fin}},\sigma^{-1} \rangle\). This is obvious, because these two classes of sentences are the same.) So assuming Lemma 2, there is an embedding \(\bar \eta\) of \(\langle \mathbb{A},\alpha^{-1} \rangle\) into \(\langle \frac{\mathcal{P}(\omega)}{\mathrm{Fin}},\sigma\rangle\) that solves the instance \((\langle\mathbb{A},\alpha^{-1}\rangle,\langle\mathbb{B},\beta^{-1}\rangle,\iota,\eta)\) of the lifting problem for \(\langle \frac{\mathcal{P}(\omega)}{\mathrm{Fin}},\sigma\rangle\). But then \(\bar \eta\) is also a solution to the instance \((\langle\mathbb{A},\alpha\rangle,\langle\mathbb{B},\beta\rangle,\iota,\eta)\) of the lifting problem for \(\langle \frac{\mathcal{P}(\omega)}{\mathrm{Fin}},\sigma^{-1} \rangle\). ◻

Proof. We repeat the proof of Theorem 4 with a few important differences. Given \(X \subseteq\frac{\mathcal{P}(\omega)}{\mathrm{Fin}}\) with \(X\) countable, let \(\langle\langle X \rangle\rangle\) denote not merely the subalgebra generated by \(X\), but some countable subalgebra of \(\frac{\mathcal{P}(\omega)}{\mathrm{Fin}}\) with \(X \subseteq\langle\langle X \rangle\rangle\) such that \(\big\langle \langle\langle X \rangle\rangle,\sigma\!\!\restriction\!\! \langle\langle X \rangle\rangle \big\rangle\) is an elementary substructure of \(\langle \frac{\mathcal{P}(\omega)}{\mathrm{Fin}},\sigma\rangle\). (Clearly this contains the subalgebra generated by \(X\), but it may be larger.) More precisely, let us fix for the remainder of the proof a map \(X \mapsto \langle\langle X \rangle\rangle\) that sends a countable \(X \subseteq\mathcal{P}(\omega)/\mathrm{Fin}\) to a set \(\langle\langle X \rangle\rangle\) as described above. This map is well-defined by the downward Löwenheim-Skolem theorem, which asserts that some such set exists, and the Axiom of Choice. (It is possible to avoid simply “choosing” \(\langle\langle X \rangle\rangle\) by describing a canonical way of obtaining \(\langle\langle X \rangle\rangle\) from \(X\), analogous to the closure of \(X\) under algebraic operations to obtain the subalgebra generated by \(X\). This process is called Skolemization, but defining it precisely is not necessary to our proof.) In what follows, we will write \(\big\langle \langle\langle X \rangle\rangle,\sigma \big\rangle\) and \(\big\langle \langle\langle X \rangle\rangle,\sigma^{-1} \big\rangle\) instead of \(\big\langle \langle\langle X \rangle\rangle,\sigma\!\!\restriction\!\! \langle\langle X \rangle\rangle \big\rangle\) and \(\big\langle \langle\langle X \rangle\rangle,\sigma^{-1} \!\!\restriction\!\! \langle\langle X \rangle\rangle \big\rangle\).

Generally \(\left\lvert \frac{\mathcal{P}(\omega)}{\mathrm{Fin}} \right\rvert = \mathfrak{c}\), so \(\left\lvert \frac{\mathcal{P}(\omega)}{\mathrm{Fin}} \right\rvert = \aleph_1\) because we are assuming \(\mathsf{CH}\). Let \(\left\langle a_\xi \colon \xi < \omega_1 \right\rangle\) be an enumeration of \(\frac{\mathcal{P}(\omega)}{\mathrm{Fin}}\) in order type \(\omega_1\).

Using transfinite recursion, we now build a sequence \(\left\langle \phi_\alpha \colon \alpha< \omega_1 \right\rangle\) of maps such that each \(\phi_\alpha\) is a conjugacy from its domain (which we denote \(\mathbb{A}_\alpha\)) to its codomain (which we denote \(\mathbb{B}_\alpha\)), or more precisely from \(\langle \mathbb{A}_\alpha,\sigma\rangle\) to \(\langle \mathbb{B}_\alpha,\sigma^{-1} \rangle\). Furthermore, the following will hold at every stage \(\alpha\) of the recursion:

• \(\mathbb{A}_\xi \subseteq\mathbb{A}_\alpha\) and \(\mathbb{B}_\xi \subseteq\mathbb{B}_\alpha\) for all \(\xi \leq \alpha\),

• \(\mathbb{A}_\alpha= \bigcup_{\xi < \alpha}\mathbb{A}_\xi\) and \(\mathbb{B}_\alpha= \bigcup_{\xi < \alpha}\mathbb{B}_\xi\) for limit \(\alpha\),

• the \(\phi_\xi\)’s are coherent, i.e., \(\phi_\xi = \phi_\zeta\!\restriction\!\mathbb{A}_\xi\) whenever \(\xi \leq \zeta\leq \alpha\),

• \(\langle \mathbb{A}_\alpha,\sigma\rangle\) is an elementary substructure of \(\langle \frac{\mathcal{P}(\omega)}{\mathrm{Fin}},\sigma\rangle\).

For the base case of the recursion, let \(\mathbb{A}_0 = \langle\langle \emptyset \rangle\rangle\). (In other words, \(\mathbb{A}_0\) is some countable subalgebra of \(\frac{\mathcal{P}(\omega)}{\mathrm{Fin}}\) such that \(\langle \mathbb{A}_0,\sigma\rangle\) is an elementary substructure of \(\langle \frac{\mathcal{P}(\omega)}{\mathrm{Fin}},\sigma\rangle\).) Because incompressibility is expressible by a first-order sentence and \(\langle \frac{\mathcal{P}(\omega)}{\mathrm{Fin}},\sigma\rangle\) is incompressible, elementarity implies \(\langle \mathbb{A}_0,\sigma\rangle\) is also incompressible. Recall that every countable incompressible dynamical system embeds in \(\langle \frac{\mathcal{P}(\omega)}{\mathrm{Fin}},\sigma^{-1} \rangle\). (This was mentioned in Section 3. It is proved, in dual form, in [19]; it is also proved below as Theorem 21.) Let \(\phi_0\) be an embedding from \(\langle \mathbb{A}_0,\sigma\rangle\) into \(\langle \frac{\mathcal{P}(\omega)}{\mathrm{Fin}},\sigma^{-1} \rangle\). Let \(\mathbb{B}_0\) denote the image of \(\mathbb{A}_0\) under \(\phi_0\). Thus \(\phi_0\) is a conjugacy from \(\langle \mathbb{A}_0,\sigma\rangle\) to \(\langle \mathbb{B}_0,\sigma^{-1} \rangle\), and \(\phi_0^{-1}\) is a conjugacy from \(\langle \mathbb{B}_0,\sigma^{-1} \rangle\) to \(\langle \mathbb{A}_0,\sigma\rangle\).

At limit stages of the recursion there is nothing to do: take \(\mathbb{A}_\alpha= \bigcup_{\xi < \alpha}\mathbb{A}_\xi\), \(\mathbb{B}_\alpha= \bigcup_{\xi < \alpha}\mathbb{B}_\xi\), and \(\phi_\alpha= \bigcup_{\xi < \alpha}\phi_\xi\), which is well-defined because the \(\phi_\xi\) are coherent. Recall that an increasing union of elementary substructures is itself an elementary substructure, so taking unions like this preserves the hypotheses of the recursion through limit stages.

At successor steps we obtain \(\phi_{\alpha+1}\) from \(\phi_\alpha\) using Lemmas 2 and 3. First, let \(\mathbb{B}_{\alpha+1}^0 = \langle\langle \mathbb{B}_\alpha\cup \{a_\alpha\} \rangle\rangle\) and observe that \[(\langle\mathbb{B}_\alpha,\sigma^{-1}\rangle,\langle\mathbb{B}^0_{\alpha+1},\sigma^{-1}\rangle,\iota,\phi_\alpha^{-1})\] is an instance of the lifting problem for \(\langle \frac{\mathcal{P}(\omega)}{\mathrm{Fin}},\sigma\rangle\), where \(\iota\) denotes the inclusion \(\mathbb{B}_\alpha\xhookrightarrow{} \mathbb{B}_{\alpha+1}^0\). Furthermore, the image of \(\phi^{-1}_\alpha\), namely \(\langle \mathbb{A}_\alpha,\sigma\rangle\), is an elementary substructure of \(\langle \frac{\mathcal{P}(\omega)}{\mathrm{Fin}},\sigma\rangle\). By Lemma 2, there is an embedding \(\phi^0_{\alpha+1}\) from \(\langle \mathbb{B}_{\alpha+1}^0,\sigma^{-1} \rangle\) into \(\langle \frac{\mathcal{P}(\omega)}{\mathrm{Fin}},\sigma\rangle\). Let \(\mathbb{A}^0_{\alpha+1}\) denote the image of this embedding. (Note that there is no obvious reason why \(\langle \mathbb{A}^0_{\alpha+1},\sigma\rangle\) should be an elementary substructure of \(\langle \frac{\mathcal{P}(\omega)}{\mathrm{Fin}},\sigma\rangle\). Instead, we now have elementarity on the other side of our mappings, with \(\mathbb{B}_{\alpha+1}^0 = \langle\langle \mathbb{B}_\alpha\cup \{a_\alpha\} \rangle\rangle\).) Because \(\phi^0_{\alpha+1}\) is a conjugacy from \(\langle \mathbb{B}^0_{\alpha+1},\sigma^{-1} \rangle\) to \(\langle \mathbb{A}^0_{\alpha+1},\sigma\rangle\), \((\phi^0_{\alpha+1})^{-1}\) is a conjugacy from \(\langle \mathbb{A}^0_{\alpha+1},\sigma\rangle\) to \(\langle \mathbb{B}^0_{\alpha+1},\sigma^{-1} \rangle\).

Second, let \(\mathbb{A}_{\alpha+1} = \langle\langle \mathbb{A}_\alpha^0 \cup \{a_\alpha\} \rangle\rangle\) and observe that \[(\langle\mathbb{A}^0_{\alpha+1},\sigma\rangle,\langle\mathbb{A}_{\alpha+1},\sigma\rangle,\iota,(\phi_\alpha^0)^{-1})\] is an instance of the lifting problem for \(\langle \frac{\mathcal{P}(\omega)}{\mathrm{Fin}},\sigma^{-1} \rangle\), where \(\iota\) denotes the inclusion \(\mathbb{A}^0_{\alpha+1} \xhookrightarrow{} \mathbb{A}_{\alpha+1}\). Furthermore, the image of \((\phi^0_{\alpha+1})^{-1}\), namely \(\langle \mathbb{B}_{\alpha+1}^0,\sigma^{-1} \rangle\), is an elementary substructure of \(\langle \frac{\mathcal{P}(\omega)}{\mathrm{Fin}},\sigma^{-1} \rangle\). By Lemma 2, there is an embedding \(\phi_{\alpha+1}\) from \(\langle \mathbb{A}_{\alpha+1},\sigma\rangle\) into \(\langle \frac{\mathcal{P}(\omega)}{\mathrm{Fin}},\sigma^{-1} \rangle\). Let \(\mathbb{B}_{\alpha+1}\) denote the image of this embedding, so that \(\phi_{\alpha+1}\) is a conjugacy from \(\langle \mathbb{A}_{\alpha+1},\sigma\rangle\) to \(\langle \mathbb{B}_{\alpha+1},\sigma^{-1} \rangle\).

This completes the recursion. Because the \(\phi_\alpha\) are coherent conjugacies from substructures of \(\langle \frac{\mathcal{P}(\omega)}{\mathrm{Fin}},\sigma\rangle\) to substructures of \(\langle \frac{\mathcal{P}(\omega)}{\mathrm{Fin}},\sigma^{-1} \rangle\), \(\phi = \bigcup_{\alpha< \omega_1}\phi_\alpha\) is a conjugacy from \(\big\langle \bigcup_{\alpha< \omega_1} \mathbb{A}_\alpha,\sigma\big\rangle\) to \(\big\langle \bigcup_{\alpha< \omega_1} \mathbb{B}_\alpha,\sigma^{-1} \big\rangle\). But \(\bigcup_{\alpha< \omega_1} \mathbb{A}_\alpha= \frac{\mathcal{P}(\omega)}{\mathrm{Fin}}\) and \(\bigcup_{\alpha< \omega_1} \mathbb{B}_\alpha= \frac{\mathcal{P}(\omega)}{\mathrm{Fin}}\), because we ensured at stage \(\alpha+1\) of the recursion that \(a_\alpha\in \mathbb{A}_{\alpha+1}\) and \(a_\alpha\in \mathbb{B}_{\alpha+1}\). ◻

Proof. Because \(\mathcal{B}\) is a partition refining \(\mathcal{A}\), for every \(a \in \mathcal{A}\) there is at least one \(b \in \mathcal{B}\) with \(b \leq a\), i.e., with \(\pi(b) = a\). Thus \(\pi\) is a surjection \(\mathcal{B}\to \mathcal{A}\).

Suppose \(b,b' \in \mathcal{B}\) and \(b \xrightarrow{\scalebox{.9}{\,{}_{\alpha}\,}}b'\). This means \(\alpha(b) \wedge b' \neq \mathbf{0}\), which implies \(\alpha(\pi(b)) \wedge \pi(b') \neq \mathbf{0}\) (because \(b \leq \pi(b)\) and \(b' \leq \pi(b')\)), i.e. \(\pi(b) \xrightarrow{\scalebox{.9}{\,{}_{\alpha}\,}}\pi(b')\).

On the other hand, suppose that \(a,a' \in \mathcal{A}\) and \(a \xrightarrow{\scalebox{.9}{\,{}_{\alpha}\,}}a'\). This means \(\alpha(a) \wedge a' \neq \mathbf{0}\), or equivalently, \(a \wedge \alpha^{-1}(a') \neq \mathbf{0}\). This implies that there is some \(b \in \mathcal{B}\) with \(b \wedge a \wedge \alpha^{-1}(a') \neq \mathbf{0}\). Hence \(b \wedge a \neq \mathbf{0}\) and \(\alpha(b) \wedge a' \neq \mathbf{0}\). The fact that \(b \wedge a \neq \mathbf{0}\) implies \(\pi(b) = a\). The fact that \(\alpha(b) \wedge a' \neq \mathbf{0}\) implies there is some \(b' \in \mathcal{B}\) with \(b' \wedge \alpha(b) \wedge a' \neq \mathbf{0}\). But \(b' \wedge a' \neq \mathbf{0}\) implies \(\pi(b') = a'\), and \(b' \wedge \alpha(b) \neq \mathbf{0}\) means \(b \xrightarrow{\scalebox{.9}{\,{}_{\alpha}\,}}b'\). Thus there are \(b,b' \in \mathcal{B}\) such that \(\pi(b) = a\), \(\pi(b') = a'\), and \(b \xrightarrow{\scalebox{.9}{\,{}_{\alpha}\,}}b'\). ◻

Proof. For the forward implication, suppose \(\langle \mathbb{A},\alpha\rangle\) is an incompressible dynamical system, and let \(\mathcal{A}\) be a partition of \(\mathbb{A}\). Fix \(a \in \mathcal{A}\), and let \[C_a = \left\lbrace b \in \mathcal{A} \colon \text{there is a walk in \langle \mathcal{A},\xrightarrow{\scalebox{.9}{\,{}_{\alpha}\,}}\rangle from a to b} \right\rbrace.\] If \(b \in C_a\) and \(b \xrightarrow{\scalebox{.9}{\,{}_{\alpha}\,}}c\), then any walk from \(a\) to \(b\) can be extended to a walk from \(a\) to \(c\), and it follows that \(c \in C_a\). Thus \(\alpha(b) \leq \bigvee C_a\) for every \(b \in C_a\). It follows that \(\alpha(\bigvee C_a) = \bigvee \left\lbrace \alpha(b) \colon b \in C_a \right\rbrace \leq \bigvee C_a\). Because \(\langle \mathbb{A},\alpha\rangle\) is incompressible (and \(C_a \neq \emptyset\)), this implies \(\bigvee C_a = \mathbf{1}\). Thus \(C_a = \mathcal{A}\), which means there is a walk in \(\langle \mathcal{A},\xrightarrow{\scalebox{.9}{\,{}_{\alpha}\,}}\rangle\) from \(a\) to any other member of \(\mathcal{A}\). But \(a\) was arbitrary, so this means \(\langle \mathcal{A},\xrightarrow{\scalebox{.9}{\,{}_{\alpha}\,}}\rangle\) is strongly connected.

For the reverse implication, suppose \(\langle \mathbb{A},\alpha\rangle\) is not incompressible, which means there is some \(x \in \mathbb{A}\setminus \{\mathbf{0},\mathbf{1}\}\) such that \(\alpha(x) \leq x\). Let \(\mathcal{A}= \{ x,\mathbf{1}-x \}\).

The digraph \(\langle \mathcal{A},\xrightarrow{\scalebox{.9}{\,{}_{\alpha}\,}}\rangle\) is not strongly connected: because \(x \leq \alpha(x)\), we do not have \(x \xrightarrow{\scalebox{.9}{\,{}_{\alpha}\,}}\mathbf{1}-x\), and there is no walk from \(x\) to \(\mathbf{1}-x\). ◻

Proof. Fix an enumeration \(\left\lbrace (a_i,b_i) \colon i \leq k \right\rbrace\) of (the ordered pairs in) the edge relation \(\to\), such that \(a_0 = v\) and \(b_k = w\). To get the desired walk, first let \(v_0 = a_0\) and \(v_1 = b_0\). Because \(\langle \mathcal{V},\to \rangle\) is strongly connected, there is a walk from \(b_0\) to \(a_1\); so we may define \(v_2,v_3, \dots, v_{\ell_1}\) (for some \(\ell_1\)) so that \(\langle b_0,v_2,v_3,\dots,v_{\ell_1},a_1 \rangle\) is a walk from \(b_0\) to \(a_1\). Take \(v_{\ell_1+1} = a_1\) and \(v_{\ell_1+2} = b_1\), and then define \(v_{\ell_1+3},v_{\ell_1+4}, \dots, v_{\ell_2}\) (for some \(\ell_2 \geq \ell_1+3\)) so that \(\langle b_1,v_{\ell_1+3},v_{\ell_1+4},\dots,v_{\ell_2},a_2 \rangle\) is a walk from \(b_1\) to \(a_2\). Take \(v_{\ell_2+1} = a_2\) and \(v_{\ell_2+2} = b_2\), and then choose the next few \(v_i\) to form a walk to \(a_3\). Continuing in this way, we find a walk from \(a_0 = v\) to \(b_k = w\) such that every arrow in the digraph is represented in the walk. ◻

Proof. \((3) \Rightarrow (2)\) because \(\langle \frac{\mathcal{P}(\omega)}{\mathrm{Fin}},\sigma\rangle\) is incompressible (by Theorem 5). \((2) \Rightarrow (1)\) by Theorem 19.

To prove \((1) \Rightarrow (3)\), fix some \(w \in \mathcal{V}\) and then, applying the previous lemma, fix a walk \(\left\langle v_i \colon i \leq n \right\rangle\) in \(\langle \mathcal{V},\to \rangle\) such that \(v_0 = v_n = w\) and such that every arrow in the digraph is represented in the walk. For each \(v \in \mathcal{V}\), define \[A_v = \left\lbrace nk+i \colon k \geq 0 \text{ and } v_i = v \right\rbrace\] and let \(\mathcal{A}= \left\lbrace [A_v] \colon v \in \mathcal{V} \right\rbrace\). We claim that \(\mathcal{A}= \left\lbrace [A_v] \colon v \in \mathcal{V} \right\rbrace\) is a partition of \(\frac{\mathcal{P}(\omega)}{\mathrm{Fin}}\) and \(\langle \mathcal{A},\xrightarrow{\text{\tiny \,\sigma\,}}\rangle \cong\langle \mathcal{V},\to \rangle\).

Because \(\langle \mathcal{V},\to \rangle\) is strongly connected, every \(v \in \mathcal{V}\) has in-degree and out-degree \(>\!0\), and this implies (as every arrow is represented in our path) that \(v = v_i\) for at least one \(i \leq n\). Thus \(A_v\) is infinite. Furthermore, it is clear that \(A_u \cap A_v = \emptyset\) whenever \(u \neq v\), and that \(\bigcup_{v \in \mathcal{V}}A_v = \omega\). Hence \(\mathcal{A}= \left\lbrace [A_v] \colon v \in \mathcal{V} \right\rbrace\) is a partition of \(\frac{\mathcal{P}(\omega)}{\mathrm{Fin}}\).

To finish the proof, we show that the map \(v \mapsto [A_v]\) is an isomorphism from \(\langle \mathcal{V},\to \rangle\) to \(\langle \mathcal{A},\xrightarrow{\text{\tiny \,\sigma\,}}\rangle\). This map is clearly bijective, so we must show that it preserves the edge relation. If \(u,v \in \mathcal{V}\) and \(u \to v\), then there is some \(i < n\) such that \(v_i = u\) and \(v_{i+1} = v\). So \((A_u+1) \cap A_v \supseteq \left\lbrace nk+i+1 \colon k \geq 0 \right\rbrace,\) and it follows that \(\sigma([A_u]) \wedge [A_v] = [(A_u+1) \cap A_v] \geq [\left\lbrace nk+i+1 \colon k \geq 0 \right\rbrace] \neq \mathbf{0}\), which means \([A_u] \xrightarrow{\text{\tiny \,\sigma\,}}[A_v]\). Conversely, if \(u,v \in \mathcal{V}\) and \([A_u] \xrightarrow{\text{\tiny \,\sigma\,}}[A_v]\), then we have \(j+1 \in A_v\) for infinitely many \(j \in A_u\). By our definition of \(A_u\) and \(A_v\), this means that \(u = v_i\) and \(v = v_{i+1}\) for some \(i < n\). Because \(\left\langle v_j \colon j \leq n \right\rangle\) is a walk, this implies \(u \to v\). ◻

Proof. The forward direction was proved already: every dynamical system that embeds in \(\langle \frac{\mathcal{P}(\omega)}{\mathrm{Fin}},\sigma\rangle\) is incompressible by Theorem 6.

For the reverse direction, fix a sequence \(\left\langle \mathcal{A}_n \colon n \in \omega \right\rangle\) of partitions of \(\mathbb{A}\) satisfying the conclusion of Lemma 1: that is, \(\mathcal{A}_n\) refines \(\mathcal{A}_m\) whenever \(m \leq n\), and for every partition \(\mathcal{V}\) of \(\mathbb{A}\), \(\mathcal{A}_n\) refines \(\mathcal{V}\) for all sufficiently large \(n\). Because \(\langle \mathbb{A},\alpha\rangle\) is incompressible, Theorem 19 tells us that \(\langle \mathcal{A}_n,\xrightarrow{\scalebox{.9}{\,{}_{\alpha}\,}}\rangle\) is strongly connected for every \(n\).

Let \(\mathcal{U}\) be an ultrafilter on \(\mathbb{A}\), and for each \(n \in \omega\) let \(a^n_0\) be the (unique) member of \(\mathcal{A}_n\) in \(\mathcal{U}\). (This implies \(a^0_0 \geq a^1_0 \geq a^2_0 \geq \dots\).) Applying Lemma 5, for each \(n\) let \(\left\langle a^n_i \colon i \leq \ell_n \right\rangle\) be a walk in \(\langle \mathcal{A}_n,\xrightarrow{\scalebox{.9}{\,{}_{\alpha}\,}}\rangle\) such that, for every \(n\), \(a^n_0 = a^n_{\ell_n} = a^n_0\) and every arrow in \(\langle \mathcal{A}_n,\xrightarrow{\scalebox{.9}{\,{}_{\alpha}\,}}\rangle\) is represented in the walk.

Let \(\left\langle b_i \colon i \in \omega \right\rangle\) be the infinite sequence of members of \(\mathbb{A}\) obtained by concatenating the walks \(\left\langle a^0_i \colon i < \ell_0 \right\rangle\), \(\left\langle a^1_i \colon i < \ell_1 \right\rangle\), \(\left\langle a^2_i \colon i < \ell_2 \right\rangle\), etc., in that order. In other words, \(b_i = a^n_j\) if and only if \(i = \ell_0+\ell_1+\dots+\ell_{n-1}+j\) for some \(j < \ell_n\).

If \(\mathcal{V}\) is a partition of \(\mathbb{A}\), then \(\mathcal{A}_n\) refines \(\mathcal{V}\) for sufficiently large \(n\), which means \(b_i\) is below \(\mathcal{V}\) for sufficiently large \(i\). Hence \(\left\langle b_i \colon i \in \omega \right\rangle\) is eventually small. If \(a \in \mathbb{A}\setminus \{\mathbf{0}\}\) then for all sufficiently large \(n\) there is some \(a' \in \mathcal{A}_n\) with \(a' \leq a\), which implies there is some \(j < \ell_n\) with \(a^n_j = a' \leq a\). Hence there are infinitely many \(i\) with \(b_i \leq a\), and as \(a\) was arbitrary, this shows \(\left\langle b_i \colon i \in \omega \right\rangle\) is eventually dense.

Finally, fix a partition \(\mathcal{V}\) of \(\mathbb{A}\), and suppose \(n\) is large enough that \(\mathcal{A}_n\) refines \(\mathcal{V}\). If \(b_i = a^n_j\) and \(b_{i+1} = a^n_{j+1}\), then \(b_i \xrightarrow{\scalebox{.9}{\,{}_{\alpha}\,}}b_{i+1}\) because \(\langle a^n_j :\, j \leq \ell_n \rangle\) is a walk. Because \(\mathcal{A}_n\) refines \(\mathcal{V}\), this implies \(\alpha(b_i) \approx_\mathcal{V}b_{i+1}\). If instead \(b_i = a^n_{\ell_n-1}\) and \(b_{i+1} = a^{n+1}_0\), then \(\alpha(b_i) \approx_{\mathcal{A}_n} b_{i+1}\) because \[b_i \,=\, a^n_{\ell_n-1} \,\xrightarrow{\scalebox{.9}{\,{}_{\alpha}\,}}\, a^n_{\ell_n} \,=\, a^n_0 \,\geq\, a^{n+1}_0 \,=\, b_{i+1}.\] Because \(\mathcal{A}_n\) refines \(\mathcal{V}\), we have \(\alpha(b_i) \approx_\mathcal{V}b_{i+1}\) in this case as well. In either case, \(b_i \approx_\mathcal{V}b_{i+1}\) for all sufficiently large \(n\). As \(\mathcal{V}\) was an arbitrary partition of \(\mathbb{A}\), this means \(\left\langle \alpha(b_i) \colon i \in \omega \right\rangle \approx \left\langle b_{i+1} \colon i \in \omega \right\rangle\). By Theorem 15, \(\left\langle b_i \colon i \in \omega \right\rangle\) induces an embedding of \(\langle \mathbb{A},\alpha\rangle\) into \(\langle \frac{\mathcal{P}(\omega)}{\mathrm{Fin}},\sigma\rangle\). ◻

Proof. If \(\langle \mathcal{V},\to \rangle\) is strongly connected, then clearly it has no isolated points. Furthermore, by Lemma 5 there is a walk \(\langle v_0,v_1,\dots,v_k\rangle\) through \(\langle \mathcal{V},\to \rangle\) such that \(v_k = v_0\), and for each \(v,w \in \mathcal{V}\) with \(v \to w\), there is some \(i < k\) such that \(v_i = v\) and \(v_{i+1} = w\). For each \(n \in \omega\), let \(v_n = v_i\) if and only if \(i \equiv n\) modulo \(k\). Then \(\left\langle v_n \colon n \in \omega \right\rangle\) is a diligent walk through \(\langle \mathcal{V},\to \rangle\).

Conversely, suppose \(\langle \mathcal{V},\to \rangle\) has no isolated points, and \(\left\langle v_n \colon n \in \omega \right\rangle\) is a diligent walk through \(\langle \mathcal{V},\to \rangle\). Let \(u,v \in \mathcal{V}\). Because \(u\) and \(v\) are not isolated in \(\langle \mathcal{V},\to \rangle\), the definition of “diligent” implies \(u\) and \(v\) both appear infinitely often in \(\left\langle v_n \colon n \in \omega \right\rangle\). Consequently, there is some \(m \in \omega\) with \(v_m = u\) and some \(n > m\) with \(v_n = v\). But then \(\langle v_m,v_{m+1},\dots,v_n\rangle\) is a walk from \(u\) to \(v\) in \(\langle \mathcal{V},\to \rangle\). As \(u\) and \(v\) were arbitrary, \(\langle \mathcal{V},\to \rangle\) is strongly connected. ◻

Proof. Let \(\langle \mathcal{V},\to \rangle\) be a strongly connected digraph, let \(\left\langle v_n \colon n \in \omega \right\rangle\) a diligent walk through \(\langle \mathcal{V},\to \rangle\), and let \(\mathcal{A}= \left\lbrace A_v \colon v \in \mathcal{V} \right\rbrace\) be the partition of \(\frac{\mathcal{P}(\omega)}{\mathrm{Fin}}\) associated to this walk. The map \(v \mapsto A_v\) is clearly a bijection. If \(v \to w\), then (by the definition of a diligent walk) there are infinitely many \(n\) such that \(v_n = v\) and \(v_{n+1} = w\), and this implies \(A_v \xrightarrow{\text{\tiny \,\sigma\,}}A_w\). Conversely, if \(A_v \xrightarrow{\text{\tiny \,\sigma\,}}A_w\), then this means that \[\begin{align} [\left\lbrace n \colon v_n = v \text{ and }v_{n+1}=w \right\rbrace] & \,=\, [\left\lbrace n \colon v_n=v \right\rbrace] \wedge [\left\lbrace n \colon v_{n+1}=w \right\rbrace] \\ &\,=\, [\left\lbrace n \colon v_n=v \right\rbrace] \wedge [\left\lbrace n-1 \colon v_n=w \right\rbrace] \\ &\,=\, A_v \wedge \sigma^{-1}(A_w) \,\neq\, [\emptyset]. \end{align}\] In other words, there are infinitely many \(n\) such that \(v_n = v\) and \(v_{n+1} = w\), which implies \(v \to w\). Hence \(v \to w\) if and only if \(A_v \xrightarrow{\text{\tiny \,\sigma\,}}A_w\). ◻

Proof. Let \(\mathcal{A}\) be a partition of \(\frac{\mathcal{P}(\omega)}{\mathrm{Fin}}\), let \(\langle \mathcal{V},\to \rangle\) be a digraph, and let \(\phi\) be an isomorphism from \(\langle \mathcal{V},\to \rangle\) to \(\langle \mathcal{A},\xrightarrow{\text{\tiny \,\sigma\,}}\rangle\). Note that this implies \(\langle \mathcal{V},\to \rangle\) is strongly connected by Theorem 20.

For each \(a \in \mathcal{A}\) fix some \(X_a \subseteq\omega\) such that \(a = [X_a]\). If \(a \neq b\) then \(a \wedge b = [\emptyset]\), which means that \(X_a \cap X_b\) is finite. Also, because \(\bigvee \mathcal{A}= [\omega]\), \(\left\lbrace n \in \omega \colon n \notin \bigcup_{a \in \mathcal{A}}X_a \right\rbrace\) is finite. Similarly, if it is not the case that \(a \xrightarrow{\text{\tiny \,\sigma\,}}b\) then \(\left\lbrace n \colon n \in X_a \text{ and } n+1 \in X_b \right\rbrace\) is finite, but if it is the case that \(a \xrightarrow{\text{\tiny \,\sigma\,}}b\) then \(\left\lbrace n \colon n \in X_a \text{ and } n+1 \in X_b \right\rbrace\) is infinite.

Consequently, there is some sufficiently large value of \(N \in \omega\) such that

• If \(n \geq N\) then there is exactly one \(a \in \mathcal{A}\) such that \(n \in X_a\), and

• The following are equivalent for any \(a,b \in \mathcal{A}\):

  • \(n \in X_a\) and \(n+1 \in X_b\) for some \(n \geq N\)

  • \(n \in X_a\) and \(n+1 \in X_b\) for infinitely many \(n \geq N\)

  • \(a \xrightarrow{\text{\tiny \,\sigma\,}}b\).

By modifying each of the \(X_a\) below \(N\) (which does not change the equality \([X_a]=a\)), we may (and do) assume that these two properties hold with \(N = 0\). (More precisely, to see how these modifications can be accomplished, fix a length-\(N\) walk \(\left\langle a_i \colon i \leq N \right\rangle\) in \(\langle \mathcal{A},\xrightarrow{\text{\tiny \,\sigma\,}}\rangle\) with \(a_N = [X_{a_N}]\). Some such walk exists because \(\langle \mathcal{A},\xrightarrow{\text{\tiny \,\sigma\,}}\rangle\) is strongly connected, by Theorem 20. Then modify the \(X_a\) by putting \(i \in X_a\) if and only if \(a = a_i\) for all \(i \leq N\).)

For each \(k \in \omega\), let \(a_k\) denote the unique \(a \in \mathcal{A}\) such that \(k \in X_a\). For each \(n \in \omega\), let \(v_n = \phi^{-1}(a_n)\). We claim \(\left\langle v_n \colon n \in \omega \right\rangle\) is a diligent walk through \(\langle\mathcal{V},\to\rangle\), and \(\phi\) is the natural isomorphism associated to this walk.

To see that this is a diligent walk, first note that \(a_n \xrightarrow{\text{\tiny \,\sigma\,}}a_{n+1}\) for all \(n\) (because \(n \in X_a\) and \(n+1 \in X_b\) is equivalent to \(a \xrightarrow{\text{\tiny \,\sigma\,}}b\)). Because \(\phi\) is an isomorphism, this implies \(\phi^{-1}(a_n) \to \phi^{-1}(a_{n+1})\) for all \(n\). Thus \(\left\langle v_n \colon n \in \omega \right\rangle\) is an infinite walk. Furthermore, if \(v,w \in \mathcal{V}\) with \(v \to w\), then \(\phi(v) \xrightarrow{\text{\tiny \,\sigma\,}}\phi(w)\), which means there are infinitely many \(n\) with \(n \in X_{\phi(v)}\) and \(n+1 \in X_{\phi(w)}\). Thus there are infinitely many \(n\) such that \(v_n = v\) and \(v_{n+1} = w\). Thus \(\left\langle v_n \colon n \in \omega \right\rangle\) is a diligent walk.

Finally, we claim that \(\phi\) is the natural isomorphism associated to this diligent walk. Our definition of the walk implies that for all \(v \in \mathcal{V}\), \[A_v \,=\, [\left\lbrace n \colon v_n = v \right\rbrace] \,=\, [\left\lbrace n \colon a_{n} = \phi(v) \right\rbrace] \,=\, [X_{\phi(v)}] \,=\, \phi(v).\] Thus \(A_v = \phi(v)\) for all \(v \in \mathcal{V}\). ◻

Proof. Fix \(\chi: [\omega]^2 \to \omega\), an \(\omega\)-coloring of \(K_\omega\), and assume that all monochromatic cliques are finite. Now suppose \(X \subseteq\omega\) is infinite. If only finitely many colors are taken by \(\chi\) in the graph \([X]^2\), then Ramsey’s Theorem (the infinitary version) implies that there is an infinite monochromatic clique for \(\chi\) in \([X]^2\), contradicting our assumption about \(\chi\). Thus if \(X \subseteq\omega\) is infinite, then the image of \([X]^2\) under \(\chi\) is infinite.

We now construct an \(\omega\)-sequence of infinite subsets of \(\omega\) by recursion. Let \(X_0 = \omega\). Given \(X_n\), define a \(2\)-coloring \(\chi_n\) of \([X_n]^2\) by setting \[\chi_n(a,b) \,=\, \begin{cases} 0 \;\text{ if } \chi(a,b) < n+1, \\ 1 \;\text{ if } \chi(a,b) \geq n+1. \end{cases}\] By the previous paragraph, \([X_n]^2\) does not have any infinite monochromatic cliques with color \(0\). But by Ramsey’s Theorem, \([X_n]^2\) does have an infinite monochromatic clique. Let \(X_{n+1}\) be any infinite subset of \(X_n\) such that \(\chi_n(a,b) \geq n+1\) for all \(a,b \in X_{n+1}\). This completes the recursion.

For each \(k \in \omega\), let \(n_k \in X_k \setminus \max \{n_0,n_1,\dots,n_{k-1}\}\). Then \(n_k,n_{k+1} \in X_k\), which implies \(\chi(n_k,n_{k+1}) > k\), for all \(k\). ◻

Proof. Clearly \(\eta\) is a bijection \(\mathcal{A}\to \eta[\mathcal{A}]\). Furthermore, because \(\eta\) is an embedding, given any \(a,b \in \mathcal{A}\), we have \(a \xrightarrow{\scalebox{.9}{\,{}_{\alpha}\,}}b\) if and only if \(\eta(a) \xrightarrow{\scalebox{.8}{\,{}_{\beta}\,}}\eta(b)\). It follows that \(\eta\) is a digraph isomorphism from \(\langle \mathcal{A},\xrightarrow{\scalebox{.9}{\,{}_{\alpha}\,}}\rangle\) to \(\langle \eta[\mathcal{A}],\xrightarrow{\scalebox{.8}{\,{}_{\beta}\,}}\rangle\). ◻

Proof. The “only if” direction of the theorem is relatively easy. Suppose that \(\bar \eta\) is a solution to \((\langle \mathbb{A},\alpha\rangle,\langle \mathbb{B},\beta\rangle,\iota,\eta)\). To show that \((\dagger)\) holds, fix a partition \(\mathcal{A}\) of \(\mathbb{A}\) and a partition \(\mathcal{B}\) of \(\mathbb{B}\) that refines \(\iota[\mathcal{A}]\). Let \(\mathcal{C}= \bar \eta[\mathcal{B}]\). Taking \(\tilde{\eta} = \bar \eta\) gives an isomorphism from \(\langle \mathcal{B},\xrightarrow{\scalebox{.8}{\,{}_{\beta}\,}}\rangle\) to \(\langle \mathcal{C},\xrightarrow{\text{\tiny \,\sigma\,}}\rangle\) by Lemma 10, and because \(\bar \eta\) is a lifting of \(\eta\), we have \(\tilde{\eta} \circ \iota = \bar \eta \circ \iota = \eta\).

For the “if” direction, suppose \((\dagger)\) holds. We aim to find a solution \(\bar \eta\) to \((\langle \mathbb{A},\alpha\rangle,\langle \mathbb{B},\beta\rangle,\iota,\eta)\). The plan is to obtain \(\bar \eta\) by finding an eventually small, eventually dense sequence in \(\mathbb{B}\) and then applying Theorem 15.

Let \(\left\langle \mathcal{A}_n \colon n \in \omega \right\rangle\) be a sequence of partitions of \(\mathbb{A}\) satisfying the conclusion of Lemma 1, and likewise let \(\left\langle \mathcal{B}_n \colon n \in \omega \right\rangle\) be a sequence of partitions of \(\mathbb{B}\) satisfying the conclusion of Lemma 1. Furthermore, we may assume for convenience that \(\mathcal{B}_0 = \{\mathbf{1}\}\) and, by thinning out the sequence \(\left\langle \mathcal{B}_n \colon n \in \omega \right\rangle\) if necessary, we may (and do) assume that \(\mathcal{B}_n\) refines \(\iota[\mathcal{A}_n]\) for all \(n\).

For each \(n\), property \((\dagger)\) gives us a partition \(\mathcal{C}_n\) of \(\frac{\mathcal{P}(\omega)}{\mathrm{Fin}}\), with \(\mathcal{C}_n \supseteq \eta[\mathcal{A}_n]\), and an isomorphism \(\tilde{\eta}_n\) from \(\langle \mathcal{B}_n,\xrightarrow{\scalebox{.8}{\,{}_{\beta}\,}}\rangle\) to \(\langle \mathcal{C}_n,\xrightarrow{\text{\tiny \,\sigma\,}}\rangle\) such that \(\tilde{\eta}_n \circ \iota = \eta\). Applying Lemma 8, for each \(n \in \omega\) there is a diligent walk \(\left\langle b^n_i \colon i \in \omega \right\rangle\) through \(\langle \mathcal{B}_n,\xrightarrow{\scalebox{.8}{\,{}_{\beta}\,}}\rangle\) such that \(\tilde{\eta}_n\) is the natural isomorphism associated with the walk \(\left\langle b^n_i \colon i \in \omega \right\rangle\).

The plan of the proof is to diagonalize across the sequences \(\left\langle b^n_i \colon i \in \omega \right\rangle\) in order to obtain a single sequence \(\left\langle d_n \colon n \in \omega \right\rangle\) in \(\mathbb{B}\). This diagonal sequence will be eventually small and eventually dense, so that it induces an embedding \(\mathbb{B}\to \frac{\mathcal{P}(\omega)}{\mathrm{Fin}}\), and the embedding it induces will be the desired solution \(\bar \eta\) to the lifting problem.

Not all the sequences \(\left\langle b^n_i \colon i \in \omega \right\rangle\) are used in our diagonalization, but only a selection of them. In order to decide which sequences to use, we employ Lemma 9. Recall that if \(\mathcal{B}\) is a partition of \(\mathbb{B}\) and \(b,b' \in \mathbb{B}\), then \(b \approx_\mathcal{B}b'\) means \(b \wedge u \neq \mathbf{0}\) if and only if \(b' \wedge u \neq \mathbf{0}\) for all \(u \in \mathcal{B}\). Define a function \(\chi: [\omega]^2 \to \omega\) as follows. For every \(k,\ell \in \omega\) with \(k < \ell\), define \[\begin{align} \chi(k,\ell) \,=\, \max \left\lbrace j \leq k \colon \beta(b^k_n) \approx_{\mathcal{B}_j} b^\ell_{n+1} \text{ for infinitely many }n \right\rbrace. \end{align}\] Our assumption that \(\mathcal{B}_0 = \{\mathbf{1}\}\) means the set in this definition is nonempty, as it contains \(0\); hence \(\chi\) is well-defined.

Roughly, the idea motivating the definition of \(\chi\) is as follows. In our diagonal sequence \(\left\langle d_i \colon i \in \omega \right\rangle\) that we are planning to construct, we will have long stretches of indices \(i\) where \(d_i = b^k_i\), i.e., where the diagonal sequence just copies \(\left\langle b^k_i \colon i \in \omega \right\rangle\), for some \(k\). Then at some point we stop copying \(\left\langle b^k_i \colon i \in \omega \right\rangle\) and “jump” to copying another sequence \(\left\langle b^\ell_i \colon i \in \omega \right\rangle\) with \(\ell > k\). In particular, for some \(i \in \omega\) (the jump time) our diagonal sequence will have \(d_i = b^k_i\) and then \(d_{i+1} = b^\ell_{i+1}\). In the end, Theorem 15 requires that we have \(\left\langle \beta(d_i) \colon i \in \omega \right\rangle \approx \left\langle d_{i+1} \colon i \in \omega \right\rangle\). Thus we need \(\beta(d_i) \approx_{\mathcal{B}_j} d_{i+1}\) for larger and larger \(j\) as we go along. In some sense, the \(j\) in this expression is measuring the degree of error in the jump: the bigger the \(j\), the less the error between \(\beta(d_i)\) and \(d_{i+1}\). Because we cannot control these jump times very well in the diagonalization, we would like to have infinitely many opportunities to jump from one sequence to another with small error (large \(j\)). The number \(\chi(k,\ell)\) tells us what error we can expect to see when jumping from \(\left\langle b^k_i \colon i \in \omega \right\rangle\) to \(\left\langle b^\ell_i \colon i \in \omega \right\rangle\).

In the parlance of Ramsey theory, \(\chi\) is a coloring \([\omega]^2 \to \omega\). We claim that all the monochromatic cliques for this coloring are finite. To see this, fix \(j \in \omega\), and suppose \(C \subseteq\omega\) is a clique with color \(j\), i.e., \(\chi(k,\ell) = j\) for all \(k,\ell \in C\). Let \(m\) be large enough that \(\mathcal{B}_{m}\) refines the partition generated by \(\mathcal{B}_{j+1} \cup \left\lbrace \beta^{-1}(b) \colon b \in \mathcal{B}_{j+1} \right\rbrace\). We claim \(|C| \leq |\mathcal{B}_m|+m+1\). Aiming for a contradiction, suppose that \(|C| > |\mathcal{B}_m|+m+1\). For every \(b \in \mathbb{B}\) that is below \(\mathcal{B}_m\), let \(\pi_m(b)\) denote the (unique) member of \(\mathcal{B}_m\) with \(b \leq \pi_m(b)\). Fix \(k_0,k_1,\dots,k_{|\mathcal{B}_m|} \in C\) such that \(m \leq k_0 < k_1 < \dots < k_{|\mathcal{B}_m|}\). (Note that some such members of \(C\) exist by our assumption \(|C| > |\mathcal{B}_m|+m+1\).) For any given \(k \geq m\) and \(n \in \omega\), \(b^k_n\) is below \(\mathcal{B}_m\), so that \(\pi_m(b^k_n)\) is well-defined, and there are only \(|\mathcal{B}_m|\) possible values for \(\pi_m(b^k_n)\). In particular, by the pigeonhole principle, for every \(n \in \omega\) at least two of \[\pi_m(b^{k_0}_n),\, \pi_m(b^{k_1}_n),\, \pi_m(b^{k_2}_n),\, \dots,\, \pi_m(b^{k_{|\mathcal{B}_m|}}_n)\] are the same. More precisely, for each \(n \in \omega\) there is a pair \(i_n,i'_n\) with \(i_n < i'_n \leq |\mathcal{B}_m|\) such that \(\pi_m(b^{k_{i_n}}_n) = \pi_m(b^{k_{i'_n}}_n)\). Applying the pigeonhole principle again, there are some particular \(i < i' \leq |\mathcal{B}_m|\) such that \(i = i_n\) and \(i' = i'_n\) for infinitely many \(n\). But \(\pi_m(b^{k_{i'}}_n) \xrightarrow{\scalebox{.8}{\,{}_{\beta}\,}}\pi_m(b^{k_{i'}}_{n+1})\) for any \(n\) (because \(b^{k_{i'}}_n \xrightarrow{\scalebox{.8}{\,{}_{\beta}\,}}b^{k_{i'}}_{n+1}\)), and and therefore \(\pi_m(b^{k_i}_n) \xrightarrow{\scalebox{.8}{\,{}_{\beta}\,}}\pi_m(b^{k_{i'}}_{n+1})\) whenever \(\pi_m(b^{k_i}_{n}) = \pi_m(b^{k_{i'}}_{n})\). Hence \(\pi_m(b^{k_i}_n) \xrightarrow{\scalebox{.8}{\,{}_{\beta}\,}}\pi_m(b^{k_{i'}}_{n+1})\) for infinitely many \(n\). Now recall that \(m \leq k_i < k_{i'}\), which means all members of the sequences \(\left\langle b^{k_i}_n \colon n \in \omega \right\rangle\) and \(\big \langle b^{k_{i'}}_n :\, n \in \omega\big \rangle\) are below \(\mathcal{B}_m\). By our choice of \(m\), if \(b,b'\) are below \(\mathcal{B}_m\) then both \(\beta(b)\) and \(b'\) are below \(\mathcal{B}_{j+1}\); and if \(b \xrightarrow{\scalebox{.8}{\,{}_{\beta}\,}}b'\), then this means \(\beta(b)\) and \(b'\) are below the same member of \(\mathcal{B}_{j+1}\) (that is, \(\beta(b),b' \leq u\) for some \(u \in \mathcal{B}_{j+1}\)), which implies \(\beta(b) \approx_{\mathcal{B}_{j+1}} b'\). In particular, because \(\pi_m(b^{k_i}_n) \xrightarrow{\scalebox{.8}{\,{}_{\beta}\,}}\pi_m(b^{k_{i'}}_{n+1})\) for infinitely many \(n\), this means \(\beta(b^{k_i}_n) \approx_{\mathcal{B}_{j+1}} b^{k_{i'}}_{n+1}\) for infinitely many \(n \in \omega\). Thus \(\chi(k_i,k_{i'}) \geq j+1\). Contradiction!

As all the monochromatic cliques for \(\chi\) are finite, Lemma 9 gives us an increasing sequence \(\left\langle n_k \colon k \in \omega \right\rangle\) such that \(\chi(n_k,n_{k+1}) > k\) for all \(k\).

Next we define a sequence \(J_0,J_1,J_2,\dots\) of integers (our jump times) by recursion. For each \(a \in \mathbb{A}\), fix some \(X_a \subseteq\omega\) such that \(\eta(a) = [X_a]\). Let \(J_0 = 0\), and given some \(J_k\), \(k \in \omega\), choose \(J_{k+1}\) such that

• for every \(b \in \mathcal{B}_{n_k}\), there is some \(i \in [J_k,J_{k+1})\) such that \(b^{n_k}_i = b\),

• \(\beta\big( b^{n_k}_{J_k-1} \big) \approx_{\mathcal{B}_k} b^{n_{k+1}}_{J_k}\), and

• if \(a\) is a member of the finite subalgebra of \(\mathbb{A}\) generated by \(\mathcal{A}_{n_{k+1}}\), then \(X_a \setminus J_{k+1} = \left\lbrace i \colon b^{n_{k+1}}_i \leq \iota(a) \right\rbrace \setminus J_{k+1}\).

To see that some such \(J_{k+1}\) exists: the first condition is satisfied by all sufficiently large choices of \(J_{k+1}\), because the sequence \(\left\langle b^{n_k}_i \colon i \in \omega \right\rangle\) is a diligent walk and therefore contains each member of \(\mathcal{B}_{n_k}\) infinitely many times; the second condition is satisfied infinitely often, because \(\chi(n_k,n_{k+1}) > k\); the third condition is satisfied by all sufficiently large choices of \(J_{k+1}\) because, by the fact that \(\tilde{\eta}_{n_{k+1}} \circ \iota = \eta\) (and by our notational abuse that extends \(\tilde{\eta}_{n_{k+1}}\) to the subalgebra of \(\mathbb{A}\) generated by \(\mathcal{A}_{n_{k+1}}\)), \[[\{ i :\, b^{n_{k+1}}_i \leq \iota(a) \}] \,=\, \tilde{\eta}_{n_{k+1}}(\iota(a)) \,=\, (\tilde{\eta}_{n_{k+1}} \circ \iota)(a) \,=\, \eta(a) \,=\, [X_a]\] for every \(a\) in the finite subalgebra of \(\mathbb{A}\) generated by \(\mathcal{A}_{n_{k+1}}\).

Define the diagonal sequence \(\left\langle d_n \colon n \in \omega \right\rangle\) in \(\mathbb{B}\) by setting \[d_i \,=\, b^{n_k}_i \quad \text{ whenever J_k \leq i < J_{k+1}}.\] The sequence \(\left\langle d_i \colon i \in \omega \right\rangle\) is eventually small in \(\mathbb{B}\) by our choice of the \(\mathcal{B}_n\)’s, and because the \(n_k\) are increasing and each \(b^{n_k}_i\) is in \(\mathcal{B}_{n_k}\). The sequence is eventually dense by the condition that for every \(b \in \mathcal{B}_{n_k}\) there is some \(i \in [J_k,J_{k+1})\) such that \(b^{n_k}_i = b\). By our choice of the \(\mathcal{B}_n\)’s, this implies that for any given \(x \in \mathbb{B}\), if \(k\) is sufficiently large then some \(b \in \mathcal{B}_{n_k}\) has \(b \leq x\), and so there is some \(d_i = b \leq x\) with \(J_k \leq i < J_{k+1}\).

Furthermore, we claim \(\left\langle \beta(d_i) \colon i \in \omega \right\rangle \approx \left\langle d_{i+1} \colon i \in \omega \right\rangle\). Let \(\mathcal{V}\) be a partition of \(\mathbb{B}\), and fix \(K\) large enough that \(\mathcal{B}_K\) refines the partition generated by \(\mathcal{V}\cup \left\lbrace \beta^{-1}(b) \colon b \in \mathcal{V} \right\rbrace\). If \(i \neq J_\ell-1\) for any \(\ell\), then there are some \(k,j\) such that \(d_i = b^k_j\) and \(d_{i+1} = b^k_{j+1}\). But \(\langle b^k_j :\, j \in \omega\rangle\) is is a diligent walk through \(\langle \mathcal{B}_k,\xrightarrow{\scalebox{.8}{\,{}_{\beta}\,}}\rangle\), so \(b^k_j \xrightarrow{\scalebox{.8}{\,{}_{\beta}\,}}b^k_{j+1}\). If \(k \geq K\), then \(\beta(b^k_j)\) and \(b^k_{j+1}\) are both below \(\mathcal{V}\), and because \(b^k_j \xrightarrow{\scalebox{.8}{\,{}_{\beta}\,}}b^k_{j+1}\), they are both below the same member of \(\mathcal{V}\). Thus \(\beta(d_i) = \beta(b^k_j) \approx_{\mathcal{V}} b^k_{j+1} = d_{i+1}\). Hence \(\beta(d_i) \approx_{\mathcal{V}} d_{i+1}\) for sufficiently large \(i\), provided that \(i \neq J_\ell-1\) for any \(\ell\). On the other hand, suppose \(i = J_\ell-1\) for some \(\ell \geq K\). Then \(\beta(d_i) \approx_{\mathcal{B}_\ell} d_{i+1}\) by the second condition listed above in our definition of the \(J_k\). Because \(\ell \geq K\), \(\mathcal{B}_\ell\) refines \(\mathcal{V}\), so \(\beta(d_i) \approx_{\mathcal{B}_\ell} d_{i+1}\) implies \(\beta(d_i) \approx_{\mathcal{V}} d_{i+1}\). Thus, in either case, \(\beta(d_i) \approx_{\mathcal{V}} d_{i+1}\) for all sufficiently large \(i\). Because \(\mathcal{V}\) was an arbitrary partition of \(\mathbb{B}\), this shows \(\left\langle \beta(d_i) \colon i \in \omega \right\rangle \approx \left\langle d_{i+1} \colon i \in \omega \right\rangle\) as claimed.

Applying Theorem 15, \(\left\langle d_i \colon i \in \omega \right\rangle\) induces an embedding of \(\langle \mathbb{B},\beta\rangle\) into \(\langle \frac{\mathcal{P}(\omega)}{\mathrm{Fin}},\sigma\rangle\). Call this embedding \(\bar \eta\). We claim that \(\bar \eta\) is a lifting of \(\eta\).

To see this, fix \(a \in \mathbb{A}\). There is some \(K\) large enough that \(a\) is in the finite subalgebra of \(\mathbb{A}\) generated by \(\mathcal{A}_k\) for all \(k \geq K\). Given \(k \geq K\), \(\mathcal{B}_k\) refines \(\iota[\mathcal{A}_k]\), and thus \(\iota(a) = \bigvee \left\lbrace d \in \mathcal{B}_k \colon d \leq \iota(a) \right\rbrace\). Combining this with the third bullet point in our choice of the \(J_k\), if \(J_k \leq i < J_{k+1}\) then \(d_i = b^{n_k}_i \leq \iota(a)\) if and only if \(i \in X_a\). Consequently, \[(\bar \eta \circ \iota)(a) \,=\, \bar \eta(\iota(a)) \,=\, [\left\lbrace i \colon d_i \leq \iota(a) \right\rbrace] \,=\, [X_a] \,=\, \eta(a).\] As \(a\) was arbitrary, it follows that \(\eta = \bar \eta \circ \iota\) as claimed. ◻

Proof. Suppose \(\iota\) is an elementary embedding from \(\langle \mathbb{A},\alpha\rangle\) into \(\langle \mathbb{B},\beta\rangle\). Let \(\mathcal{A}\) be a partition of \(\mathbb{A}\) and let \(\mathcal{B}\) be a partition of \(\mathbb{B}\) that refines \(\iota[\mathcal{A}]\). We aim to show that condition \((\dagger)\) from Theorem 22 holds.

Let \(\varphi\) be the first-order sentence about \(\langle \mathbb{B},\beta\rangle\) obtained as the conjunction of all true assertions of the following form:

• \(\bigvee \mathcal{B}= \mathbf{1}\) and \(b \wedge b' = \mathbf{0}\) whenever \(b,b' \in \mathcal{B}\) and \(b \neq b'\),

• \(\bigvee \iota[\mathcal{A}] = \mathbf{1}\) and \(b \wedge b' = \mathbf{0}\) whenever \(b,b' \in \iota[\mathcal{A}]\) and \(b \neq b'\),

• \(b \xrightarrow{\scalebox{.8}{\,{}_{\beta}\,}}b'\) for some \(b,b' \in \mathcal{B}\) or some \(b,b' \in \iota[\mathcal{A}]\),

• \(\neg(b \xrightarrow{\scalebox{.8}{\,{}_{\beta}\,}}b')\) for some \(b,b' \in \mathcal{B}\) or some \(b,b' \in \iota[\mathcal{A}]\),

• \(b \leq b'\) for some \(b \in \mathcal{B}\) and \(b' \in \iota[\mathcal{A}]\).

In other words, \(\varphi\) asserts that \(\iota[\mathcal{A}]\) and \(\mathcal{B}\) are partitions of \(\mathbb{B}\), it describes precisely the digraphs \(\langle \mathcal{B},\xrightarrow{\scalebox{.8}{\,{}_{\beta}\,}}\rangle\) and \(\langle \iota[\mathcal{A}],\xrightarrow{\scalebox{.8}{\,{}_{\beta}\,}}\rangle\), and it records which members of \(\mathcal{B}\) are below which members of \(\iota[\mathcal{A}]\).

Fix an enumeration \(\mathcal{A}= \{a_1,a_2,\dots,a_m\}\) of \(\mathcal{A}\) and an enumeration \(\mathcal{B}= \{b_1,b_2,\dots,b_n\}\) of \(\mathcal{B}\). Let \(\psi(\iota(a_1),\dots,\iota(a_m),x_1,\dots,x_n,\beta)\) be the formula about \(\langle \mathbb{B},\beta\rangle\) obtained from \(\varphi\) by replacing every instance of \(b_i\) with the variable \(x_i\), and let \(\bar \psi\) be the formula \[\exists x_1 \exists x_2 \dots \exists x_n \psi(\iota(a_1),\dots,\iota(a_m),x_1,\dots,x_n,\beta).\] This is a true assertion about \(\langle \mathbb{B},\beta\rangle\), because \(\psi(\iota(a_1),\dots,\iota(a_m),b_1,\dots,b_n,\beta)\) is true.

Now consider the formula \[\exists x_1 \exists x_2 \dots \exists x_n \psi(a_1,\dots,a_n,x_1,\dots,x_n,\alpha)\] about \(\langle \mathbb{A},\alpha\rangle\) obtained from \(\bar \psi\) by replacing every instance of \(\iota(a_i)\) with \(a_i\) and every instance of \(\beta\) with \(\alpha\). Because \(\iota\) is an elementary emedding, this formula must be true in \(\langle \mathbb{A},\alpha\rangle\), as the corresponding formula (the original \(\bar \psi\)) is true in \(\langle \mathbb{B},\beta\rangle\). Hence there exist some \(\tilde{b}_1, \tilde{b}_2, \dots, \tilde{b}_n \in \mathbb{A}\) such that \[\langle \mathbb{A},\alpha\rangle \models \psi(a_1,\dots,a_m,\tilde{b}_1, \dots, \tilde{b}_n,\alpha).\] Define \(\tilde{\eta}: \mathcal{B}\to \frac{\mathcal{P}(\omega)}{\mathrm{Fin}}\) by setting \(\tilde{\eta}(b_i) = \eta(\tilde{b}_i)\) for all \(i \leq n\).

Let \(\tilde{\mathcal{B}}= \{ \tilde{b}_i :\, i \leq n \}\) and let \(\mathcal{C}= \tilde{\eta}[\tilde{\mathcal{B}}]\). Observe that \(\tilde{\mathcal{B}}\) is a partition of \(\mathbb{A}\), because \(\psi(a_1,\dots,a_m,\tilde{b}_1, \dots, \tilde{b}_n,\alpha)\) asserts that it is. Similarly, \(\langle \tilde{\mathcal{B}}, \xrightarrow{\scalebox{.9}{\,{}_{\alpha}\,}}\rangle\) is isomorphic to \(\langle \mathcal{B},\xrightarrow{\scalebox{.8}{\,{}_{\beta}\,}}\rangle\), and \(\tilde{\mathcal{B}}\) refines \(\mathcal{A}\), and the natural map \(\tilde{\mathcal{B}}\to \mathcal{A}\) matches the natural map \(\mathcal{B}\to \iota[\mathcal{A}]\) (in the sense that the former sends \(\tilde{b}_i\) to \(a_j\) if and only if the latter sends \(b_i\) to \(\iota(a_j)\)). Because \(\tilde{\mathcal{B}}\) is a partition of \(\mathbb{A}\), \(\mathcal{C}= \eta[\tilde{\mathcal{B}}]\) is a partition of \(\frac{\mathcal{P}(\omega)}{\mathrm{Fin}}\), and \(\eta\) is an isomorphism from \(\langle \tilde{B},\xrightarrow{\scalebox{.9}{\,{}_{\alpha}\,}}\rangle\) to \(\langle \eta[\tilde{\mathcal{B}}],\xrightarrow{\text{\tiny \,\sigma\,}}\rangle\) by Lemma 10. It follows that \(\tilde{\eta}\) is an isomorphism from \(\langle \mathcal{B},\xrightarrow{\scalebox{.8}{\,{}_{\beta}\,}}\rangle\) to \(\langle \eta[\tilde{\mathcal{B}}],\xrightarrow{\text{\tiny \,\sigma\,}}\rangle\). Furthermore, because the natural map \(\tilde{\mathcal{B}}\to \mathcal{A}\) matches the natural map \(\mathcal{B}\to \iota[\mathcal{A}]\), we have \(\tilde{\eta} \circ \iota(a) = \eta(a)\) for all \(a \in \mathcal{A}\).

In other words, this map \(\tilde{\eta}\) witnesses that \((\dagger)\) is satisfied for \(\mathcal{A}\) and \(\mathcal{B}\). As \(\mathcal{A}\) and \(\mathcal{B}\) were arbitrary partitions, \((\dagger)\) holds. ◻

Proof. We prove the theorem first for \(\langle \frac{\mathcal{P}(\omega)}{\mathrm{Fin}},\sigma\rangle\). Every countable incompressible dynamical system embeds in \(\langle \frac{\mathcal{P}(\omega)}{\mathrm{Fin}},\sigma\rangle\) by Theorem 21, so it suffices to consider systems of size \(\aleph_1\).

Let \(\langle \mathbb{A},\alpha\rangle\) be an incompressible dynamical system with \(|\mathbb{A}| = \aleph_1\). Applying the downward Löwenheim-Skolem theorem \(\omega_1\) times, there is an increasing sequence \(\left\langle \mathbb{A}_\beta \colon \beta< \omega_1 \right\rangle\) of countable subalgebras of \(\mathbb{A}\) such that

• \(\langle \mathbb{A}_\beta,\alpha\rangle\) is an elementary substructure of \(\langle \mathbb{A},\alpha\rangle\) for all \(\beta< \omega_1\),

• \(\mathbb{A}_\beta= \bigcup_{\xi < \beta} \mathbb{A}_\xi\) whenever \(\beta\) is a limit ordinal, and

• \(\bigcup_{\beta< \omega_1} \mathbb{A}_\beta= \mathbb{A}\).

We now construct, via transfinite recursion, a sequence \(\left\langle \eta_\beta \colon \beta< \omega_1 \right\rangle\) of maps such that each \(\eta_\beta\) is an embedding from \(\langle \mathbb{A}_\beta,\alpha\rangle\) into \(\langle \frac{\mathcal{P}(\omega)}{\mathrm{Fin}},\sigma\rangle\), and the \(\eta_\beta\) are coherent in the sense that \(\eta_\beta= \eta_\gamma\!\restriction\!\mathbb{A}_\beta\) whenever \(\beta< \gamma\).

To begin, fix an embedding \(\eta_0\) from \(\langle \mathbb{A}_0,\alpha\rangle\) into \(\langle \frac{\mathcal{P}(\omega)}{\mathrm{Fin}},\sigma\rangle\). (Some such embedding exists by Theorem 21, and because elementarity implies \(\langle \mathbb{A}_0,\alpha\rangle\) is incompressible.) At a limit stage \(\beta\) of the recursion, let \(\eta_\beta= \bigcup_{\xi < \beta}\eta_\xi\). This is an embedding from \(\langle \mathbb{A}_\beta,\alpha\rangle\) into \(\langle \frac{\mathcal{P}(\omega)}{\mathrm{Fin}},\sigma\rangle\), because the \(\eta_\xi\) are coherent embeddings and \(\mathbb{A}_\beta= \bigcup_{\xi < \beta}\mathbb{A}_\xi\).

For the successor step, suppose \(\gamma= \beta+1\) and suppose that we already have an embedding \(\eta_\beta\) from \(\langle \mathbb{A}_\beta,\alpha\rangle\) into \(\langle \frac{\mathcal{P}(\omega)}{\mathrm{Fin}},\sigma\rangle\). Let \(\iota\) denote the inclusion map \(\mathbb{A}_\beta\xhookrightarrow{} \mathbb{A}_\gamma\). Then \((\langle\mathbb{A}_\beta,\alpha\rangle,\langle\mathbb{A}_\gamma,\alpha\rangle,\iota,\eta_\beta)\) is an instance of the lifting problem for \(\langle \frac{\mathcal{P}(\omega)}{\mathrm{Fin}},\sigma\rangle\), and furthermore \(\iota\) is an elementary embedding. By Lemma 11, there is an embedding \(\eta_\gamma\) from \(\langle \mathbb{A}_\gamma,\alpha\rangle\) into \(\langle \frac{\mathcal{P}(\omega)}{\mathrm{Fin}},\sigma\rangle\) such that \(\eta_\gamma\circ \iota = \eta_\beta\). Because \(\iota\) is the inclusion map \(\mathbb{A}_\beta\xhookrightarrow{} \mathbb{A}_\gamma\), this last condition just means that \(\eta_\beta= \eta_\gamma\!\restriction\!\mathbb{A}_\beta\), i.e., the coherence of the maps is preserved.

In the end, let \(\eta = \bigcup_{\beta< \omega_1}\eta_\beta\). Because the \(\eta_\beta\) are coherent embeddings and \(\mathbb{A}= \bigcup_{\beta< \omega_1}\mathbb{A}_\beta\), \(\eta\) is an embedding from \(\langle \mathbb{A},\alpha\rangle\) to \(\langle \frac{\mathcal{P}(\omega)}{\mathrm{Fin}},\sigma\rangle\).

It remains to show that we can also obtain an embedding from \(\langle \mathbb{A},\alpha\rangle\) to \(\langle \frac{\mathcal{P}(\omega)}{\mathrm{Fin}},\sigma^{-1} \rangle\). Of course one could repeat the above proof, mutatis mutandis, but this is not necessary. Recall that \(\langle \mathbb{A},\alpha\rangle\) is incompressible if and only if \(\langle \mathbb{A},\alpha^{-1} \rangle\) is. Thus, by the preceding argument, there is an embedding \(\eta'\) from \(\langle \mathbb{A},\alpha^{-1} \rangle\) into \(\langle \frac{\mathcal{P}(\omega)}{\mathrm{Fin}},\sigma\rangle\). But then the same map \(\eta'\) is also an embedding from \(\langle \mathbb{A},\alpha\rangle\) into \(\langle \frac{\mathcal{P}(\omega)}{\mathrm{Fin}},\sigma^{-1} \rangle\). ◻

Proof. This follows from Theorem 23, because \(\mathsf{CH}\) implies \(\left\lvert \frac{\mathcal{P}(\omega)}{\mathrm{Fin}} \right\rvert = \aleph_1\), and both \(\langle \frac{\mathcal{P}(\omega)}{\mathrm{Fin}},\sigma\rangle\) and \(\langle \frac{\mathcal{P}(\omega)}{\mathrm{Fin}},\sigma^{-1} \rangle\) are incompressible. ◻

Proof. Note that \(\phi\) is well-defined, because \(\mathcal{B}\) refines \(\iota[\mathcal{A}]\), and is clearly a surjection \(\mathcal{B}\to \mathcal{A}\). If \(a,a' \in \mathcal{A}\) and \(a \xrightarrow{\scalebox{.9}{\,{}_{\alpha}\,}}a'\), then \(\iota(a) \xrightarrow{\scalebox{.8}{\,{}_{\beta}\,}}\iota(a')\) (because \(\iota\) is an embedding), and this implies that \(b \xrightarrow{\scalebox{.8}{\,{}_{\beta}\,}}b'\) for some \(b \leq \iota(a)\) and \(b' \leq \iota(a')\). In other words, there are \(b,b' \in \mathcal{B}\) such that \(\phi(b) = a\), \(\phi(b') = a'\), and \(b \xrightarrow{\scalebox{.8}{\,{}_{\beta}\,}}b'\). On the other hand, it is clear that \(b \xrightarrow{\scalebox{.8}{\,{}_{\beta}\,}}b'\) implies \(\phi(b) \xrightarrow{\scalebox{.9}{\,{}_{\alpha}\,}}\phi(b')\). ◻

Proof. Let \(\mathcal{B}'\) be any partition of \(\mathbb{B}\) refining both \(\mathcal{B}\) and \(\iota[\mathcal{A}']\). We claim that the digraph \(\langle \mathcal{B}',\xrightarrow{\scalebox{.8}{\,{}_{\beta}\,}}\rangle\), along with the appropriate natural epimorphisms, witnesses the compatibility of the two virtual refinements in question. In short, the proof works because the composition of two natural maps is again a natural map (with the appropriate domain and co-domain).

More precisely, let \(\phi\) denote the natural map from \(\mathcal{A}'\) to \(\mathcal{A}\), and let \(\psi\) denote the natural epimorphism from \(\langle \mathcal{B},\xrightarrow{\scalebox{.8}{\,{}_{\beta}\,}}\rangle\) onto \(\langle \mathcal{A},\xrightarrow{\scalebox{.9}{\,{}_{\alpha}\,}}\rangle\). Let \(\bar \phi\) denote the natural epimorphism from \(\langle \mathcal{B}',\xrightarrow{\scalebox{.8}{\,{}_{\beta}\,}}\rangle\) onto \(\langle \mathcal{A}',\xrightarrow{\scalebox{.9}{\,{}_{\alpha}\,}}\rangle\) and let \(\bar \psi\) denote the natural map from \(\mathcal{B}'\) to \(\mathcal{B}\). The definitions of these various maps give us that both \(\phi \circ \bar \phi\) and \(\psi \circ \bar \psi\) are equal to the function \(\mathcal{B}' \to \mathcal{A}\) given by \[b \,\mapsto\, \text{the unique member of \mathcal{A} with } b \leq \iota(a),\] or in other words, the natural epimorphism from \(\langle \mathcal{B}',\xrightarrow{\scalebox{.8}{\,{}_{\beta}\,}}\rangle\) onto \(\langle \mathcal{A},\xrightarrow{\scalebox{.9}{\,{}_{\alpha}\,}}\rangle\). ◻

Proof. In order to prove that \((\langle \mathbb{A},\alpha\rangle,\langle \mathbb{B},\beta\rangle,\iota,\eta)\) has a solution, it suffices to prove that condition \((\dagger)\) from Theorem 22 holds. Let \(\mathcal{A}\) be a partition of \(\mathbb{A}\), and let \(\mathcal{B}\) be a partition of \(\mathcal{B}\) that refines \(\iota[\mathcal{A}]\).

Let \(\phi\) denote the natural epimorphism from \(\langle \mathcal{B},\xrightarrow{\scalebox{.8}{\,{}_{\beta}\,}}\rangle\) onto \(\langle \mathcal{A},\xrightarrow{\scalebox{.9}{\,{}_{\alpha}\,}}\rangle\). By Lemma 12, \((\phi,\langle \mathcal{B},\xrightarrow{\scalebox{.8}{\,{}_{\beta}\,}}\rangle)\) is a virtual refinement of \(\langle \mathcal{A},\xrightarrow{\scalebox{.9}{\,{}_{\alpha}\,}}\rangle\).

Let \(\tilde{\mathcal{A}}\) be any partition of \(\mathbb{A}\) refining \(\mathcal{A}\), and let \(\tilde{\pi}\) denote the natural map \(\tilde{\mathcal{A}}\to \mathcal{A}\). Then \((\tilde{\pi},\langle \tilde{\mathcal{A}},\xrightarrow{\scalebox{.9}{\,{}_{\alpha}\,}}\rangle)\) is a virtual refinement of \(\langle \mathcal{A},\xrightarrow{\scalebox{.9}{\,{}_{\alpha}\,}}\rangle\) by Lemma 4, and this virtual refinement is compatible with \((\phi,\langle\mathcal{B},\xrightarrow{\scalebox{.8}{\,{}_{\beta}\,}}\rangle)\), by Lemma 13. Consequently, case \((2)\) of Definition 17 is not true of \(\mathcal{A}\) and \((\phi,\langle\mathcal{B},\xrightarrow{\scalebox{.8}{\,{}_{\beta}\,}}\rangle)\). Because \(\mathcal{A}\) is a polarized partition, this means that case \((1)\) must be true: there is a partition \(\mathcal{A}'\) of \(\mathbb{A}\) that realizes \((\phi,\langle\mathcal{B},\xrightarrow{\scalebox{.8}{\,{}_{\beta}\,}}\rangle)\). Letting \(\pi\) denote the natural map from \(\mathcal{A}'\) onto \(\mathcal{A}\), this means that there is an isomorphism \(\phi'\) from \(\langle \mathcal{B},\xrightarrow{\scalebox{.8}{\,{}_{\beta}\,}}\rangle\) onto \(\langle \mathcal{A}',\xrightarrow{\scalebox{.9}{\,{}_{\alpha}\,}}\rangle\) such that \(\pi \circ \phi' = \phi\).

The remainder of the argument imitates the proof of Lemma 11, but with the members of \(\mathcal{A}'\) playing the part that the \(\tilde{b}_i\) played in that proof.

Define \(\tilde{\eta}(b) = \eta \circ \phi'(b)\) for all \(b \in \mathcal{B}\), and let \(\mathcal{C}= \tilde{\eta}[\mathcal{B}]\). Because \(\phi'\) is a digraph isomorphism from \(\langle \mathcal{B},\xrightarrow{\scalebox{.8}{\,{}_{\beta}\,}}\rangle\) to \(\langle \mathcal{A}',\xrightarrow{\scalebox{.9}{\,{}_{\alpha}\,}}\rangle\) and \(\eta\) is a digraph isomorphism from \(\langle \mathcal{A}',\xrightarrow{\scalebox{.9}{\,{}_{\alpha}\,}}\rangle\) to \(\langle \mathcal{C},\xrightarrow{\text{\tiny \,\sigma\,}}\rangle\) (by Lemma 10), \(\tilde{\eta}\) is an isomorphism from \(\langle \mathcal{B},\xrightarrow{\scalebox{.8}{\,{}_{\beta}\,}}\rangle\) to \(\langle \mathcal{C},\xrightarrow{\text{\tiny \,\sigma\,}}\rangle\). Also, \(\mathcal{C}= \tilde{\eta}[\mathcal{B}] = \eta[\phi'[\mathcal{B}]] = \eta[\mathcal{A}']\); because \(\mathcal{A}'\) refines \(\mathcal{A}\), this implies that \(\mathcal{C}\) refines \(\eta[\mathcal{A}]\). It remains to check that \(\eta = \tilde{\eta} \circ \iota\).

Let \(a \in \mathcal{A}\). Recall that \(\iota(a)\) may not be in \(\mathcal{B}\) (the domain of \(\tilde{\eta}\)), but extending (or abusing) our notation in the natural way, we define \(\tilde{\eta} \circ \iota(a) = \bigvee \left\lbrace \tilde{\eta}(b) \colon b \in \mathcal{B}\text{ and }b \leq \iota(a) \right\rbrace\). Similarly, (with the same notational abuse) we define \(\phi' \circ \iota(a) = \bigvee \left\lbrace \phi'(b) \colon b \in \mathcal{B}\text{ and }b \leq \iota(a) \right\rbrace\). Because \(\pi \circ \phi' = \phi\) and \(\pi(\phi'(b)) = a\) if and only if \(\phi'(b) \leq a\), \[\begin{align} \phi' \circ \iota(a) &\,=\, \textstyle \bigvee \left\lbrace \phi'(b) \colon b \in \mathcal{B}\text{ and }b \leq \iota(a) \right\rbrace \\ & \textstyle \,=\, \bigvee \left\lbrace \phi'(b) \colon b \in \mathcal{B}\text{ and } \phi'(b) \leq a \right\rbrace \\ & \textstyle \,=\, \bigvee \left\lbrace c \colon c \in \mathcal{A}' \text{ and } c \leq a \right\rbrace \,=\, a. \end{align}\] Consequently, \(\eta(a) = \eta \circ \phi' \circ \iota(a) = \tilde{\eta} \circ \iota(a).\) As \(a\) was an arbitrary member of \(\mathcal{A}\), this shows that \(\eta = \tilde{\eta} \circ \iota\) as required. ◻

Proof. Suppose \(\left\langle c_n \colon n \in \omega \right\rangle\) is a diligent walk through \(\langle \mathcal{C},\xrightarrow{\scalebox{.75}{\,{}_{\mathcal{C}}\,}}\rangle\) that almost projects onto \(\left\langle a_n \colon n \in \omega \right\rangle\). The existence of a diligent walk through \(\langle \mathcal{C},\xrightarrow{\scalebox{.75}{\,{}_{\mathcal{C}}\,}}\rangle\) implies \(\langle \mathcal{C},\xrightarrow{\scalebox{.75}{\,{}_{\mathcal{C}}\,}}\rangle\) is strongly connected, by Lemma 6. To prove the lemma, we must show \(\psi\) is an epimorphism. Fix some \(N \in \omega\) sufficiently large that if \(n \geq N\) then \(\psi(c_n) = a_n\).

Let \(a \in \mathcal{A}\). Because \(\left\langle a_n \colon n \in \omega \right\rangle\) is diligent, there are infinitely many \(n \in \omega\) such that \(a_n = a\); in particular, \(a_n = a\) for some \(n \geq N\). Hence \(\psi(c_n) = a_n = a\), and as \(a\) was arbitrary, it follows that \(\psi\) is surjective.

Fix \(c,c' \in \mathcal{C}\) such that \(c \xrightarrow{\scalebox{.75}{\,{}_{\mathcal{C}}\,}}c'\). Because \(\left\langle c_n \colon n \in \omega \right\rangle\) is diligent, there is some \(n \geq N\) such that \(c = c_n\) and \(c' = c_{n+1}\). Because \(n \geq N\), this implies \(\psi(c) = a_n \xrightarrow{\scalebox{.75}{\,{}_{\mathcal{A}}\,}}a_{n+1} = \psi(c')\).

Lastly, fix \(a,a' \in \mathcal{A}\) such that \(a \xrightarrow{\scalebox{.75}{\,{}_{\mathcal{A}}\,}}a'\). Because \(\left\langle a_n \colon n \in \omega \right\rangle\) is diligent, there is some \(n \geq N\) such that \(a = a_n\) and \(a' = a_{n+1}\). Because \(n \geq N\), this implies \(\psi(c_n) = a\) and \(\psi(c_{n+1}) = a'\). But \(c_n \xrightarrow{\scalebox{.75}{\,{}_{\mathcal{C}}\,}}c_{n+1}\) (because \(\left\langle c_n \colon n \in \omega \right\rangle\) is a walk), so this shows there are \(c,c' \in \mathcal{C}\) such that \(\psi(c) = a\), \(\psi(c') = a'\), and \(c \xrightarrow{\scalebox{.75}{\,{}_{\mathcal{C}}\,}}c'\). ◻

Proof. The “only if” direction is obvious: if \(\left\langle b_n \colon n \in \omega \right\rangle\) is an infinite walk in \(\langle \mathcal{B},\xrightarrow{\scalebox{.75}{\,{}_{\mathcal{B}}\,}}\rangle\) that projects onto \(\left\langle a_n \colon n \in \omega \right\rangle\), then \(\langle b_0,b_1,\dots,b_k\rangle\) projects onto \(\langle a_0,a_1,\dots,a_k\rangle\) for every \(k \in \omega\).

The “if” direction is a consequence of Kőnig’s Tree Lemma. To see this, consider the set \(\mathcal{T}\) of all finite walks \(\langle b_0,b_1,\dots,b_k\rangle\) in \(\langle \mathcal{B},\xrightarrow{\scalebox{.75}{\,{}_{\mathcal{B}}\,}}\rangle\) that project onto the initial segment \(\langle a_0,a_1,\dots,a_k\rangle\) of \(\left\langle a_n \colon n \in \omega \right\rangle\) with the same length. When ordered in the natural way, by end-extension, this set \(\mathcal{T}\) is a tree. Because \(\mathcal{B}\) is finite, this tree is finitely branching (specifically, each member of \(\mathcal{T}\) has at most \(|\mathcal{B}|\) immediate successors).

Now suppose that for every \(k \in \omega\) there is a length-\(k\) walk \(\langle b_0,b_1,\dots,b_k\rangle\) in \(\langle \mathcal{B},\xrightarrow{\scalebox{.75}{\,{}_{\mathcal{B}}\,}}\rangle\) that projects onto \(\langle a_0,a_1,\dots,a_k\rangle\). This implies \(\mathcal{T}\) is infinite. Consequently, Kőnig’s Tree Lemma implies that \(\mathcal{T}\) has an infinite branch \(\big\langle \emptyset,\langle b_0\rangle,\langle b_0,b_1\rangle,\langle b_0,b_1,b_2\rangle,\dots \big\rangle.\) The union of this branch is an infinite sequence \(\langle b_0,b_1,b_2,\dots\rangle\) in \(\mathcal{B}\), and this sequence is an infinite walk in \(\langle \mathcal{B},\xrightarrow{\scalebox{.75}{\,{}_{\mathcal{B}}\,}}\rangle\) that projects onto \(\left\langle a_n \colon n \in \omega \right\rangle\). ◻

Proof. It is clear that \(\mathrm{S}^{\bar a}_0 = \phi^{-1}(a_0)\), because \(\langle b\rangle\) is a length-\(0\) walk projecting onto \(\langle a_0\rangle\) if and only if \(\phi(b) = a_0\). For the general step of the recursion, observe that \(\langle b_0,b_1,\dots,b_k,b_{k+1} \rangle\) is a length-\((k+1)\) walk projecting onto \(\langle a_0,a_1,\dots,a_k,a_{k+1} \rangle\) if and only if \((1)\) \(\langle b_0,b_1,\dots,b_k \rangle\) is a length-\(k\) walk projecting onto \(\langle a_0,a_1,\dots,a_k \rangle\), \((2)\) \(b_k \xrightarrow{\scalebox{.75}{\,{}_{\mathcal{B}}\,}}b_{k+1}\), and \((3)\) \(\phi(b_{k+1}) = a_{k+1}\). Thus \(b \in \mathrm{S}^{\bar a}_{k+1}\) if and only if \(\phi(b) = a_{k+1}\) and there is some length-\(k\) walk \(\langle b_0,b_1,\dots,b_k \rangle\) projecting onto \(\langle a_0,a_1,\dots,a_k \rangle\) such that \(b_k \xrightarrow{\scalebox{.75}{\,{}_{\mathcal{B}}\,}}b\). ◻

Proof. Let \(\langle \mathcal{A},\xrightarrow{\scalebox{.75}{\,{}_{\mathcal{A}}\,}}\rangle\) and \(\langle \mathcal{B},\xrightarrow{\scalebox{.75}{\,{}_{\mathcal{B}}\,}}\rangle\) be strongly connected digraphs, and let \(\phi\) be an epimorphism from \(\langle \mathcal{B},\xrightarrow{\scalebox{.75}{\,{}_{\mathcal{B}}\,}}\rangle\) onto \(\langle \mathcal{A},\xrightarrow{\scalebox{.75}{\,{}_{\mathcal{A}}\,}}\rangle\). Fix an infinite walk \(\bar a = \left\langle a_n \colon n \in \omega \right\rangle\) through \(\langle \mathcal{A},\xrightarrow{\scalebox{.75}{\,{}_{\mathcal{A}}\,}}\rangle\). For each \(m \in \omega\), let \(\bar a_m = \left\langle a_{n+m} \colon n \in \omega \right\rangle\) (i.e., \(\bar a_m\) is the sequence \(\bar a\) with the first \(m\) entries removed).

To begin, suppose there is some \(m \in \omega\) such that \(\mathrm{S}^{\bar a_m}_k \neq \emptyset\) for all \(k\). Applying Lemma 15, this implies there is an infinite walk \(\left\langle b_n \colon n \in \omega \right\rangle\) through \(\langle\mathcal{B},\xrightarrow{\scalebox{.75}{\,{}_{\mathcal{B}}\,}}\rangle\) that projects onto \(\bar a_m\). Using the fact that \(\langle \mathcal{B},\xrightarrow{\scalebox{.75}{\,{}_{\mathcal{B}}\,}}\rangle\) is strongly connected, fix some length-\(m\) walk \(\langle b'_0,b'_1,\dots,b'_m\rangle\) in \(\langle \mathcal{B},\xrightarrow{\scalebox{.75}{\,{}_{\mathcal{B}}\,}}\rangle\) such that \(b'_m = b_0\). Define a new walk \(\langle \tilde{b}_0,\tilde{b}_1,\tilde{b}_2,\dots \rangle\) by concatenating these two walks: \[\tilde{b}_i \,=\, \begin{cases} b_i' & \text{ if } i \leq m, \\ b_{i-m} & \text{ if } i \geq m. \end{cases}\] Then \(\langle \tilde{b}_0,\tilde{b}_1,\tilde{b}_2,\dots \rangle\) is an infinite walk through \(\langle \mathcal{B},\xrightarrow{\scalebox{.75}{\,{}_{\mathcal{B}}\,}}\rangle\) that almost projects onto \(\bar a\) via \(\phi\), because \(\phi(b_n) = a_n\) whenever \(n \geq m\).

Therefore, if there is some \(m \in \omega\) such that \(\mathrm{S}^{\bar a_m}_k \neq \emptyset\) for all \(k\), then alternative \((1)\) from the statement of the theorem holds. To prove the theorem, it suffices to show that if this is not the case then alternative \((2)\) holds.

Let us suppose, then, that for every \(m \in \omega\) there is some \(k \in \omega\) such that \(\mathrm{S}^{\bar a_m}_{k} = \emptyset\). For each \(m\), let \(k_m\) denote the least number with this property, so that \(\mathrm{S}^{\bar a_m}_i \neq \emptyset\) for all \(i < k_m\), but \(\mathrm{S}^{\bar a_m}_{k_m} = \emptyset\). Note that \(k_m > 0\) for all \(m\), because \(\mathrm{S}^{\bar a_m}_0 = \phi^{-1}(a_m) \neq \emptyset\).

Because \(\mathcal{S}^\phi\) and \(\mathcal{A}\) are both finite, there are some particular \(\mathcal{C}_0 \subseteq\mathcal{S}^\phi\), and \(\mathcal{E}_0 \subseteq\;\xrightarrow{\scalebox{.75}{\,{}_{\mathcal{S}^\phi}\,}}\), and \(\mathrm{S}_\text{in} \in \mathcal{S}^\phi\), and \(a_\text{in},a_\text{end},a_\text{out} \in \mathcal{A}\), such that

• \(\left\lbrace \mathrm{S}^{\bar a_m}_i \colon i \leq k_m \right\rbrace \,=\, \mathcal{C}_0\),

• \(\left\lbrace (\mathrm{S}^{\bar a_m}_i,\mathrm{S}^{\bar a_m}_{i+1}) \colon i < k_m \right\rbrace \,=\, \mathcal{E}_0\),

• \(\mathrm{S}^{\bar a_m}_0 \,=\, \mathrm{S}_\text{in}\),

• \(a_{m-1} \,=\, a_\text{in}\),

• \(a_{k_m} \,=\, a_\text{end}\),

• \(a_{k_m+1} \,=\, a_\text{out}\)

for infinitely many \(m > 0\). (We exclude \(m=0\) from consideration so that \(a_{m-1}\) is well-defined.) Let \(D\) denote the set of all \(m > 0\) satisfying the six properties listed above.

We are now ready to describe the digraph \(\langle \mathcal{C},\xrightarrow{\scalebox{.75}{\,{}_{\mathcal{C}}\,}}\rangle\) and the epimorphism \(\psi\) that witness alternative \((2)\) from the statement of the theorem. First define \(\mathcal{C}\,=\, \mathcal{A}\cup \mathcal{C}_0\). (We are assuming, without loss of generality, that \(\mathcal{A}\cap \mathcal{C}_0 = \emptyset\). This is true automatically unless the members of \(\mathcal{A}\) are labeled in an unreasonable way.) Define the edge relation on \(\mathcal{C}\) as follows: \[\begin{align} x \xrightarrow{\scalebox{.75}{\,{}_{\mathcal{C}}\,}}y \quad \;\Longleftrightarrow \quad \;& x,y \in \mathcal{A}\text{ and } x \xrightarrow{\scalebox{.75}{\,{}_{\mathcal{A}}\,}}y \text{, or} \\ & x,y \in \mathcal{C}_0 \text{ and } (x,y) \in \mathcal{E}_0 \text{, or} \\ & x=a_\text{in} \text{ and } y = \mathrm{S}_\text{in} \text{, or} \\ & x = \emptyset \text{ and } y = a_{\mathrm{out}}. \end{align}\]

Define \(\psi: \mathcal{C}\to \mathcal{A}\) as follows: \[\psi(x) = \begin{cases} x & \text{ if } x \in \mathcal{A}, \\ \Pi_\phi(\mathrm{S}) & \text{ if } \mathrm{S}\in \mathcal{C}_0 \setminus \{\emptyset\}, \\ a_\text{end} & \text{ if } x = \emptyset. \end{cases}\]

This completes the definition of \(\langle \mathcal{C},\xrightarrow{\scalebox{.75}{\,{}_{\mathcal{C}}\,}}\rangle\) and \(\psi\). To finish the proof, we need to show that \(\langle \mathcal{C},\xrightarrow{\scalebox{.75}{\,{}_{\mathcal{C}}\,}}\rangle\) is strongly connected, that \(\psi\) is an epimorphism from \(\langle \mathcal{C},\xrightarrow{\scalebox{.75}{\,{}_{\mathcal{C}}\,}}\rangle\) to \(\langle \mathcal{A},\xrightarrow{\scalebox{.75}{\,{}_{\mathcal{A}}\,}}\rangle\), that there is a diligent walk through \(\langle \mathcal{C},\xrightarrow{\scalebox{.75}{\,{}_{\mathcal{C}}\,}}\rangle\) projecting onto \(\left\langle a_n \colon n \in \omega \right\rangle\) via \(\psi\), and that \(\psi\) is incompatible with \(\phi\).

We can verify the first three of these four things all at once by applying Lemma 14. To do this, we must define a diligent walk \(\left\langle c_i \colon i \in \omega \right\rangle\) through \(\langle \mathcal{C},\xrightarrow{\scalebox{.75}{\,{}_{\mathcal{C}}\,}}\rangle\) that projects onto \(\left\langle a_i \colon i \in \omega \right\rangle\) via \(\psi\). We define this walk via recursion, obtaining at each stage not a single \(c_i\), but a long piece of the walk.

To begin, recall that for every edge \((a,a')\) in \(\xrightarrow{\scalebox{.75}{\,{}_{\mathcal{A}}\,}}\), there are infinitely many \(i \in \omega\) such that \((a_i,a_{i+1}) = (a,a')\). Fix some \(m_0 \in D\) large enough that for every \((a,a')\) in \(\xrightarrow{\scalebox{.75}{\,{}_{\mathcal{A}}\,}}\), there is at least one \(i+1 < m_0\) such that \((a_i,a_{i+1}) = (a,a')\). Then define \[\begin{align} c_i &\,=\, a_i \qquad \quad \;\;\, \text{for all } i < m_0 \text{, and} \\ c_i &\,=\, \mathrm{S}^{\bar a_{m_0}}_{i-m_0} \qquad \text{whenever } m_0 \leq i \leq m_0+k_{m_0}. \end{align}\] This completes the base step of the recursion.

Later stages of the recursion are similar. At stage \(n\), suppose that there is some \(m_{n-1} \in A\) such that \(c_i\) is already defined for all \(i \leq m_{n-1}+k_{m_{n-1}}\). Fix some \(m_n \in D\) large enough that for every \((a,a') \in \;\xrightarrow{\scalebox{.75}{\,{}_{\mathcal{A}}\,}}\) there is some \(i\) with \(m_{n-1}+k_{m_{n-1}} \leq i < m_n-1\) such that \((a_i,a_{i+1}) = (a,a')\). Then define \[\begin{align} c_i &\,=\, a_i \qquad \quad \;\;\, \text{whenever } m_{n-1}+k_{m_{n-1}} \leq i < m_n \text{, and} \\ c_i &\,=\, \mathrm{S}^{\bar a_{m_n}}_{i-m_n} \qquad \text{whenever } m_n \leq i \leq m_n+k_{m_n}. \end{align}\] This completes the recursion.

Next, we check that \(\left\langle c_i \colon i \in \omega \right\rangle\) is a diligent walk through \(\langle \mathcal{C},\xrightarrow{\scalebox{.75}{\,{}_{\mathcal{C}}\,}}\rangle\) that projects onto \(\left\langle a_i \colon i \in \omega \right\rangle\) via \(\psi\).

Every \(i \in \omega\) fits into one of the following four cases:

• \(c_i = a_i\) and \(c_{i+1} = a_{i+1}\),

• \(c_i = a_{m_n-1} = a_\text{in}\) and \(c_{i+1} = \mathrm{S}^{\bar a_{m_n}}_0 = \mathrm{S}_\text{in}\) for some \(m_n \in D\),

• \(c_i = \mathrm{S}^{\bar a_{m_n}}_j\) and \(c_{i+1} = \mathrm{S}^{\bar a_{m_n}}_{j+1}\) for some \(m_n \in D\) and some \(j < m_n\), or

• \(c_i = \emptyset\) and \(c_{i+1} = a_{m_n + k_{m_n}+1} = a_\text{out}\) for some \(m_n \in D\).

In any of these four cases, it follows immediately from the definition of \(\xrightarrow{\scalebox{.75}{\,{}_{\mathcal{C}}\,}}\) that \(c_i \xrightarrow{\scalebox{.75}{\,{}_{\mathcal{C}}\,}}c_{i+1}\). Hence \(\left\langle c_i \colon i \in \omega \right\rangle\) is an infinite walk in \(\langle \mathcal{C},\xrightarrow{\scalebox{.75}{\,{}_{\mathcal{C}}\,}}\rangle\).

Furthermore, at stage \(n\) of the recursion we chose the new \(c_i\)’s (that is, those \(c_i\) for which \(m_{n-1}+k_{m_{n-1}} \leq i \leq m_n+k_{m_n}\)) so that:

• for every \((a,a')\) in \(\xrightarrow{\scalebox{.75}{\,{}_{\mathcal{A}}\,}}\) there is some new \(c_i\) with \((c_i,c_{i+1}) = (a,a')\),

• for every \((\mathrm{S},\mathrm{S}')\) in \(\mathcal{E}_0\) there is some new \(c_i\) with \((c_i,c_{i+1}) = (\mathrm{S},\mathrm{S}')\),

• there is some new \(c_i\) with \((c_i,c_{i+1}) = (a_\text{in},\mathrm{S}_\text{in})\), and

• there is some new \(c_i\) with \((c_i,c_{i+1}) = (\emptyset,a_\text{out})\).

In other words, for every \((c,c')\) in \(\xrightarrow{\scalebox{.75}{\,{}_{\mathcal{C}}\,}}\) there is some new \(c_i\) with \((c_i,c_{i+1}) = (c,c')\). It follows that \(\left\langle c_i \colon i \in \omega \right\rangle\) is a diligent walk through \(\langle \mathcal{C},\xrightarrow{\scalebox{.75}{\,{}_{\mathcal{C}}\,}}\rangle\).

For each \(i \in \omega\), either \(c_i \in \mathcal{A}\) or \(c_i \in \mathcal{C}_0\). If \(c_i \in \mathcal{A}\) then \(\psi(c_i) = a_i\) by construction. If \(c_i = \mathrm{S}\in \mathcal{C}_0\) then either

• \(c_i = \mathrm{S}^{\bar a_{m_n}}_{i-m_n}\) for some \(n\) with \(m_n \leq i < m_n+k_{m_n}\), in which case we have \(\mathrm{S}^{\bar a_{m_n}}_{i-m_n} \neq \emptyset\) and \(\mathrm{S}^{\bar a_{m_n}}_{i-m_n} \subseteq\phi^{-1}(a_{i-m_n})\), which implies that \(\psi(c_i) = \Pi_\phi(\mathrm{S}^{\bar a_{m_n}}_{i-m_n}) = a_i\); or

• \(c_i = \mathrm{S}^{\bar a_{m_n}}_{k_{m_n}} = \emptyset\) for some \(m_n \in D\), in which case \(\psi(c_i) = a_\text{end} = a_{m_n+k_{m_n}} = a_i\).

In either case, \(\psi(c_i) = a_i\). This holds for all \(i \in \omega\).

By Lemma 14, \(\langle \mathcal{C},\xrightarrow{\scalebox{.75}{\,{}_{\mathcal{C}}\,}}\rangle\) is strongly connected, \(\psi\) is an epimorphism from \(\langle \mathcal{C},\xrightarrow{\scalebox{.75}{\,{}_{\mathcal{C}}\,}}\rangle\) to \(\langle \mathcal{A},\xrightarrow{\scalebox{.75}{\,{}_{\mathcal{A}}\,}}\rangle\), and \(\left\langle c_i \colon i \in \omega \right\rangle\) is a diligent walk through \(\langle \mathcal{C},\xrightarrow{\scalebox{.75}{\,{}_{\mathcal{C}}\,}}\rangle\) that projects via \(\psi\) onto \(\left\langle a_i \colon i \in \omega \right\rangle\).

It remains to show that \(\psi\) is incompatible with \(\phi\). Suppose, aiming for a contradiction, that \(\psi\) is compatible with \(\phi\). That is, suppose that there is a strongly connected digraph \(\langle \mathcal{W},\xrightarrow{\scalebox{.75}{\,{}_{\mathcal{W}}\,}}\rangle\) and epimorphisms \(\bar \phi\) and \(\bar \psi\) from \(\langle \mathcal{W},\xrightarrow{\scalebox{.75}{\,{}_{\mathcal{W}}\,}}\rangle\) to \(\langle \mathcal{B},\xrightarrow{\scalebox{.75}{\,{}_{\mathcal{B}}\,}}\rangle\) and \(\langle \mathcal{C},\xrightarrow{\scalebox{.75}{\,{}_{\mathcal{C}}\,}}\rangle\), respectively, such that \(\phi \circ \bar \phi = \psi \circ \bar \psi\).

Because \(\bar \psi\) is a surjection \(\mathcal{W}\to \mathcal{C}\), the fibers \(\bar \psi^{-1}(\mathrm{S}_\text{in})\) and \(\bar \psi^{-1}(\emptyset)\) are both nonempty. Using the fact that \(\langle \mathcal{W},\xrightarrow{\scalebox{.75}{\,{}_{\mathcal{W}}\,}}\rangle\) is strongly connected, fix a walk \(\langle w_0,w_1,w_2,\dots,w_n \rangle\) in \(\langle \mathcal{W},\xrightarrow{\scalebox{.75}{\,{}_{\mathcal{W}}\,}}\rangle\) from some \(w_0 \in \bar \psi^{-1}(\mathrm{S}_\text{in})\) to some \(w_n \in \bar \psi^{-1}(\emptyset)\).

Because \(\bar \psi\) is an epimorphism, \(\langle \bar \psi(w_0),\bar \psi(w_1),\bar \psi(w_2),\dots,\bar \psi(w_n) \rangle\) is a walk in \(\langle \mathcal{C},\xrightarrow{\scalebox{.75}{\,{}_{\mathcal{C}}\,}}\rangle\) from \(\bar \psi(w_0) = \mathrm{S}_\text{in}\) to \(\bar \psi(w_n) = \emptyset\). Without loss of generality, we may (and do) assume that \(\bar \psi(w_k) \neq \emptyset\) for any \(k < n\). (If we did have \(\bar \psi(w_k) = \emptyset\) for some \(k < n\), then we could just consider the shorter walk \(\langle w_0,w_1,w_2,\dots,w_k \rangle\) instead of the original walk \(\langle w_0,w_1,w_2,\dots,w_n \rangle\).) But observe that every walk in \(\langle \mathcal{C},\xrightarrow{\scalebox{.75}{\,{}_{\mathcal{C}}\,}}\rangle\) from \(\mathrm{S}_\text{in}\) to a vertex in \(\mathcal{A}\) must include the vertex \(\emptyset\), because \((\emptyset,a_\text{out})\) is the only member of \(\xrightarrow{\scalebox{.75}{\,{}_{\mathcal{C}}\,}}\) going from a member of \(\mathcal{C}_0\) to a member of \(\mathcal{A}\). Because we are assuming \(\bar \psi(w_i) \neq \emptyset\) for all \(i < n\), this implies \(\bar \psi(w_i) \in \mathcal{C}_0\) for all \(i \leq n\).

Because \(\bar \phi\) is an epimorphism, \(\langle \bar \phi(w_0),\bar \phi(w_1),\bar \phi(w_2),\dots,\bar \phi(w_n) \rangle\) is a walk in \(\langle \mathcal{B},\xrightarrow{\scalebox{.75}{\,{}_{\mathcal{B}}\,}}\rangle\). We now prove, by induction on \(i\), that \(\bar \phi(w_i) \in \bar \psi(w_i)\) for all \(i \leq n\). (By the previous paragraph, \(\bar \psi(w_i) \in \mathcal{C}_0 \in \mathcal{S}^\phi\) whenever \(i \leq n\). Therefore the assertion \(\bar \phi(w_i) \in \bar \psi(w_i)\) at least makes sense: we have \(\bar \phi(w_i) \in \mathcal{B}\) and \(\bar \psi(w_i) \subseteq\mathcal{B}\) whenever \(i \leq n\).)

For the base case \(i=0\), observe that \[\phi \circ \bar \phi(w_0) \,=\, \psi \circ \bar \psi(w_0) \,=\, \psi(\mathrm{S}_\text{in}) \,=\, \Pi_\phi(\mathrm{S}_\text{in}).\] Consequently, \(\bar \phi(w_0) \in \phi^{-1}(\Pi_\phi(\mathrm{S}_\text{in}))\). Now fix some \(m \in D\). Recall that \(\mathrm{S}_\text{in} = \mathrm{S}^{\bar a_m}_0 = \phi^{-1}(a_m) \neq \emptyset\), which means \(\Pi_\phi(\mathrm{S}_\text{in}) = a_m\). Consequently, \(\phi^{-1}(\Pi_\phi(\mathrm{S}_\text{in})) = \phi^{-1}(a_m) = \mathrm{S}_\text{in}\). Hence \[\bar \phi(w_0) \,\in\, \phi^{-1}(\Pi_\phi(\mathrm{S}_\text{in})) \,=\, \mathrm{S}_\text{in} \,=\, \bar \psi(w_0).\]

For the successor step, fix \(i < n\) and suppose (the inductive hypothesis) that \(\bar \phi(w_i) \in \bar \psi(w_i)\); we wish to show \(\bar \phi(w_{i+1}) \in \bar \psi(w_{i+1})\). Because \(\bar \psi\) is an epimorphism and \(w_i \xrightarrow{\scalebox{.75}{\,{}_{\mathcal{W}}\,}}w_{i+1}\), \(\bar \psi(w_i) \xrightarrow{\scalebox{.75}{\,{}_{\mathcal{C}}\,}}\bar \psi(w_{i+1})\). Because \(\bar \psi(w_i),\bar \psi(w_{i+1}) \in \mathcal{C}_0\) (rather than \(\mathcal{A}\)), this means \((\bar \psi(w_i),\bar \psi(w_{i+1})) \in \mathcal{E}_0\), which is to say that for some (any) \(m \in D\) there is some \(k < k_m\) such that \(\bar \psi(w_i) = \mathrm{S}^{\bar a_m}_k\) and \(\bar \psi(w_{i+1}) = \mathrm{S}^{\bar a_m}_{k+1}\). But then \[\phi \circ \bar \phi(w_i) \,=\, \psi \circ \bar \psi(w_i) \,=\, \psi(\mathrm{S}^{\bar a_m}_k) \,=\, a_{m+k} \text{, and}\] \[\phi \circ \bar \phi(w_{i+1}) \,=\, \psi \circ \bar \psi(w_{i+1}) \,=\, \psi(\mathrm{S}^{\bar a_m}_{k+1}) \,=\, a_{m+k+1}.\] In particular, \(\bar \phi(w_{i+1}) \in \phi^{-1}(a_{m+k+1})\). Furthermore, \(\bar \phi(w_i) \xrightarrow{\scalebox{.75}{\,{}_{\mathcal{B}}\,}}\bar \phi(w_{i+1})\) (because \(w_i \xrightarrow{\scalebox{.75}{\,{}_{\mathcal{W}}\,}}w_{i+1}\) and \(\bar \phi\) is an epimorphism), and \(\bar \phi(w_i) \in \bar \psi(w_i) = \mathrm{S}^{\bar a_m}_k\) (by the inductive hypothesis). But by Lemma 16, \[\mathrm{S}^{\bar a_m}_{k+1} \,=\, \left\lbrace b \in \phi^{-1}(a_{m+k+1}) \colon \exists x \in \mathrm{S}^{\bar a_m}_k \text{ such that } x \xrightarrow{\scalebox{.75}{\,{}_{\mathcal{B}}\,}}y \right\rbrace,\] so this means that \(\bar \phi(w_{i+1}) \in \mathrm{S}^{\bar a_m}_{k+1} = \bar \psi(w_{i+1})\). This completes the induction.

This shows that \(\bar \phi(w_i) \in \bar \psi(w_i)\) for all \(i \leq n\). In particular, \(\bar \phi(w_n) \in \bar \psi(w_n)\). But \(\bar \psi(w_n) = \emptyset\). Contradiction! ◻

Proof of Theorem 25. Let \(\langle \mathcal{A},\xrightarrow{\scalebox{.75}{\,{}_{\mathcal{A}}\,}}\rangle\) and \(\langle \mathcal{B},\xrightarrow{\scalebox{.75}{\,{}_{\mathcal{B}}\,}}\rangle\) be strongly connected digraphs, let \(\phi\) be an epimorphism from \(\langle \mathcal{B},\xrightarrow{\scalebox{.75}{\,{}_{\mathcal{B}}\,}}\rangle\) onto \(\langle \mathcal{A},\xrightarrow{\scalebox{.75}{\,{}_{\mathcal{A}}\,}}\rangle\), and let \(\bar a = \left\langle a_n \colon n \in \omega \right\rangle\) be a diligent walk through \(\langle \mathcal{A},\xrightarrow{\scalebox{.75}{\,{}_{\mathcal{A}}\,}}\rangle\).

By Theorem 26, if there is no infinite walk in \(\langle \mathcal{B},\xrightarrow{\scalebox{.75}{\,{}_{\mathcal{B}}\,}}\rangle\) that almost projects onto \(\bar a\), then alternative \((2)\) from the statement of Theorem 26 holds. But alternative \((2)\) from the statement of Theorem 26 implies alternative \((2)\) from the statement of Theorem 25. Therefore, if there is no infinite walk in \(\langle \mathcal{B},\xrightarrow{\scalebox{.75}{\,{}_{\mathcal{B}}\,}}\rangle\) that almost projects onto \(\bar a\), then alternative \((2)\) holds and we are done. Thus, for the remainder of the proof, we may (and do) assume that there is an infinite walk in \(\langle \mathcal{B},\xrightarrow{\scalebox{.75}{\,{}_{\mathcal{B}}\,}}\rangle\) that almost projects onto \(\left\langle a_n \colon n \in \omega \right\rangle\).

For each \(\ell,m \in \omega\) with \(\ell < m\), define a relation \(\mathcal{R}_{\ell,m} \subseteq\mathcal{B}\times \mathcal{B}\) as follows: \[\begin{align} (v,w) \in \mathcal{R}_{\ell,m} \qquad \Leftrightarrow \qquad &\text{there is a walk \langle b_\ell,b_{\ell+1},\dots,b_m \rangle in \langle \mathcal{B},\xrightarrow{\scalebox{.75}{\,{}_{\mathcal{B}}\,}}\rangle} \\ &\text{from v to w that projects onto \langle a_\ell,a_{\ell+1},\dots,a_m \rangle.} \end{align}\] This relation expresses the “walkability” between the members of \(\mathcal{B}\), using correctly projecting walks beginning at time \(\ell\) and ending at time \(m\).

Because \(\mathcal{B}\) is finite, the mapping \(\chi: [\omega]^2 \to \mathcal{P}(\mathcal{B}\times \mathcal{B})\) defined by \[\chi(\ell,m) \,=\, \mathcal{R}_{\min\{\ell,m\},\max\{\ell,m\}}\] is a finite coloring of \([\omega]^2\). By the infinite version of Ramsey’s Theorem, there is some particular \(\mathcal{R} \subseteq\mathcal{B}\times \mathcal{B}\) and an infinite \(D \subseteq\omega\) such that if \(\ell,m \in D\) and \(\ell < m\), then \(\mathcal{R}_{\ell,m} = \mathcal{R}\). We may (and do) assume \(D\) does not contain two consecutive integers. Henceforth, let \(m_k\) denote the \(k^\mathrm{th}\) member of \(D\). Before moving on, let us make some observations concerning this set \(D\) and this relation \(\mathcal{R}\), both of which play an important part in the remainder of the proof.

Observation: \(\mathcal{R}\) is not the empty relation.

Proof of Observation: By the assumption at the beginning of the proof, there is an infinite walk \(\left\langle b^0_i \colon i \in \omega \right\rangle\) in \(\langle \mathcal{B},\xrightarrow{\scalebox{.75}{\,{}_{\mathcal{B}}\,}}\rangle\) that almost projects onto \(\left\langle a_i \colon i \in \omega \right\rangle\). From our definition of \(\mathcal{R}_{\ell,m}\), it follows that \((b^0_\ell,b^0_m) \in \mathcal{R}_{\ell,m}\) for all sufficiently large \(\ell,m \in \omega\) with \(\ell < m\). In particular, because \(D\) is infinite this is true for some \(\ell,m \in D\), and consequently \(\mathcal{R} \neq \emptyset\). \(\dashv\)

In what follows, let \(\mathrm{T}\) denote the domain of this relation \(\mathcal{R}\), i.e., \(\mathrm{T}= \left\lbrace v \in \mathcal{V} \colon (v,v') \in \mathcal{R} \text{ for some }v' \right\rbrace\).

Observation: \(\mathcal{R}\) is a transitive relation.

Proof of Observation: If \(k,\ell,m \in D\) with \(k < \ell < m\), then \[\qquad\qquad\qquad\qquad\, \mathcal{R} \,=\, \mathcal{R}_{k,m} \,=\, \mathcal{R}_{\ell,m} \circ \mathcal{R}_{k,\ell} \,=\, \mathcal{R} \circ \mathcal{R}. \qquad\qquad\qquad\qquad \dashv\]

Observation: There is some \(v \in \mathcal{B}\) such that \((v,v) \in \mathcal{R}\).

Proof of Observation: By assumption, there is an infinite walk \(\left\langle b^0_i \colon i \in \omega \right\rangle\) in \(\langle \mathcal{B},\xrightarrow{\scalebox{.75}{\,{}_{\mathcal{B}}\,}}\rangle\) that almost projects onto \(\left\langle a_i \colon i \in \omega \right\rangle\). By the pigeonhole principle, there is some \(v \in \mathcal{B}\) such that \(b_m = v\) for infinitely many \(m \in D\). As in the proof of our first observation above, \((b_\ell,b_m) \in \mathcal{R}\) for sufficiently large \(\ell < m\) with \(\ell,m \in D\). Therefore \((v,v) \in \mathcal{R}\). \(\dashv\)

Observation: If \(\ell,m \in D\), then \(a_\ell = a_m\).

Proof of Observation: Fix some \(v \in \mathcal{B}\) such that \((v,v) \in \mathcal{R}\), and let \(\ell,m \in D\) with \(\ell < m\). Because \((v,v) \in \mathcal{R} = \mathcal{R}_{\ell,m}\), the definition of \(\mathcal{R}_{\ell,m}\) implies there is a walk \(\langle b_\ell,\dots,b_m \rangle\) in \(\langle \mathcal{B},\xrightarrow{\scalebox{.75}{\,{}_{\mathcal{B}}\,}}\rangle\) from \(v = b_\ell\) to \(v = b_m\) that projects onto \(\langle a_\ell,\dots,a_m \rangle\). But (by the definition of “projects") this means \(a_\ell = \phi(b_\ell) = \phi(v)\) and \(a_m = \phi(b_m) = \phi(v)\). \(\dashv\)

Let us write \(a_D\) to denote the unique member of \(\left\lbrace a_m \colon m \in D \right\rbrace\).

Next, we associate to each “time" \(i \in \omega\setminus \{0,1,\dots,m_0\}\) two relations \(\mathcal{P}^i\) and \(\mathcal{F}^i\) (for Past and Future) that generalize the walkability relation \(\mathcal{R}\).

If \(i \in D\), let \(\mathcal{P}^i = \mathcal{F}^i = \mathcal{R}\). If \(i \notin D\) and \(i > m_0 = \min D\), then define: \[\begin{align} (v,b) \in \mathcal{P}^i \quad \Leftrightarrow \quad &\text{v \in \mathcal{B} and for some m \in D with m < i there is} \\ &\text{a walk \langle b_{m},b_{m+1},\dots,b_i \rangle in \langle \mathcal{B},\xrightarrow{\scalebox{.75}{\,{}_{\mathcal{B}}\,}}\rangle from v = b_m} \\ &\text{to b = b_i that projects onto \langle a_{m},a_{m+1},\dots,a_i \rangle.} \\ \vphantom{f^{f^{f^{f^f}}}} (b,v) \in \mathcal{F}^i \quad \Leftrightarrow \quad &\text{v \in \mathcal{B} and for some m \in D with m > i there is} \\ &\text{a walk \langle b_{i},b_{i+1},\dots,b_{m} \rangle in \langle \mathcal{B},\xrightarrow{\scalebox{.75}{\,{}_{\mathcal{B}}\,}}\rangle from b=b_i} \\ &\text{to v = b_m that projects onto \langle a_i,a_{i+1},\dots,a_{m} \rangle.} \end{align}\]

This defines \(\mathcal{P}^i\) and \(\mathcal{F}^i\) for \(i \geq m_0\). It is not necessary to define \(\mathcal{P}^i\) and \(\mathcal{F}^i\) for \(i < m_0\), or if desired, one may define them there arbitrarily.

Observation: \(\mathcal{F}^i \supseteq \mathcal{F}^i \circ \mathcal{R}\) for any \(i \geq m_0\).

Proof of Observation: If \(i \in D\) then this follows from our observation that \(\mathcal{R} = \mathcal{R} \circ \mathcal{R}\), so fix \(i \notin D\). Suppose \((b,v) \in \mathcal{F}^i\) and \((v,v') \in \mathcal{R}\). The former means that, for some \(m \in D\) with \(m > i\), there is a walk \(\langle b_i,\dots,b_m \rangle\) from \(b = b_i\) to \(v = b_m\) that projects onto \(\langle a_i,\dots,a_m \rangle\); the latter means that, for some \(m' \in D\) with \(m' > m\), there is a walk \(\langle b_m,\dots,b_{m'} \rangle\) from \(v = b_m\) to \(v' = b_{m'}\) that projects onto \(\langle a_m,\dots,a_{m'} \rangle\). Concatenating these two walks gives us a walk \(\langle b_i,\dots,b_{m'} \rangle\) from \(b = b_i\) to \(v' = b_{m'}\) that projects onto \(\langle a_i,\dots,a_{m'} \rangle\). But this means \((b,v') \in \mathcal{F}^i\). \(\dashv\)

Observation: If \(i \geq m_2\), then \(\mathcal{P}^i \supseteq \mathcal{R} \circ \mathcal{P}^i\).

Proof of Observation: If \(i \in D\) then this follows from our observation that \(\mathcal{R} = \mathcal{R} \circ \mathcal{R}\), so fix \(i \notin D\) with \(i > m_2\). Suppose \((v,b) \in \mathcal{P}^i\) and \((v',v) \in \mathcal{R}\).

Because \((v,b) \in \mathcal{P}^i\), for some \(m \in D\) with \(m < i\) there is a walk \(\langle b_m,\dots,b_i \rangle\) from \(v = b_m\) to \(b = b_i\) that projects onto \(\langle a_m,\dots,a_i \rangle\). We claim that, without loss of generality, we may take \(m > m_0\). To see this, suppose instead that \(m = m_0\). Recalling that \(i > m_2\), the truncated walk \(\langle b_{m_0},\dots,b_{m_2} \rangle\) witnesses \((b_{m_0},b_{m_2}) \in \mathcal{R}_{m_0,m_2} = \mathcal{R}\). But \(\mathcal{R} = \mathcal{R}_{m_1,m_2}\) as well, so there is a walk \(\langle b'_{m_1},\dots,b'_{m_2} \rangle\) from \(b'_{m_1} = b_{m_0}\) to \(b'_{m_2} = b_{m_2}\) that projects onto \(\langle a_{m_1},\dots,a_{m_2} \rangle\). Consequently, \(\langle b'_{m_1},\dots,b'_{m_2} = b_{m_2},b_{m_2+1},\dots,b_i \rangle\) is a walk from \(b_{m_0} = b'_{m_1}\) to \(v = b_i\) that projects onto \(\langle a_{m_1},\dots,a_i \rangle\).

Thus for some \(m \in D \setminus \{m_0\}\) with \(m < i\) there is a walk \(\langle b_m,\dots,b_i \rangle\) from \(v = b_m\) to \(b = b_i\) that projects onto \(\langle a_m,\dots,a_i \rangle\). Furthermore, because \((v',v) \in \mathcal{R}\) and \(m > m_0\), there is a walk \(\langle b_{m_0},\dots,b_{m} \rangle\) from \(v' = b_{m_0}\) to \(v = b_{m}\) that projects onto \(\langle a_{m_0},\dots,a_{m} \rangle\). Concatenating these two walks gives us a walk \(\langle b_{m_0},\dots,b_{i} \rangle\) from \(v' = b_{m_0}\) to \(b = b_{i}\) that projects onto \(\langle a_{m_0},\dots,a_{i} \rangle\). Therefore \((v',b) \in \mathcal{P}^i\). \(\dashv\)

For notational convenience in what follows, if \(v \in \mathcal{B}\) then define \[\begin{align} \mathcal{P}^i_v &\,=\, \left\lbrace b \in \mathcal{B} \colon (v,b) \in \mathcal{P}^i \right\rbrace \qquad \text{and} \qquad \mathcal{F}^i_v &\,=\, \left\lbrace b \in \mathcal{B} \colon (b,v) \in \mathcal{F}^i \right\rbrace. \end{align}\] Thus we may write \(b \in \mathcal{P}^i_v\) rather than \((v,b) \in \mathcal{P}^i\) (this can be read as “\(b\) has \(v\) in its past at time \(i\)”); and we may write \(b \in \mathcal{F}^i_v\) rather than \((b,v) \in \mathcal{F}^i\) (which can be read as “\(b\) has \(v\) in its future at time \(i\)”). By the previous observation, if \(b \in \mathcal{P}^i_v\) and \((v',v) \in \mathcal{R}\), then \(b \in \mathcal{P}^i_{v'}\) (provided \(i \geq m_2\)) and if \(b \in \mathcal{F}^i_v\) and \((v,v') \in \mathcal{R}\), then \(b \in \mathcal{F}^i_{v'}\)

Observation: If \(i \geq m_0\), then \(\mathcal{P}^i\) and \(\mathcal{F}^i\) are nonempty.

Proof of Observation: We have already showed \(\mathcal{R} \neq \emptyset\), and we defined \(\mathcal{F}^i = \mathcal{P}^i = \mathcal{R}\) for \(i \in D\). If \(i > m_0\) and \(i \notin D\), then fix some \(m > i\) with \(m \in D\). Because \(\mathcal{R}_{m_0,m} = \mathcal{R} \neq \emptyset\), there is a walk \(\langle b_{m_0},\dots,b_m \rangle\) in \(\langle\mathcal{B},\xrightarrow{\scalebox{.75}{\,{}_{\mathcal{B}}\,}}\rangle\) that projects onto \(\langle a_{m_0},\dots,a_m \rangle\). Then \((b_{m_0},b_i) \in \mathcal{P}^i\) and \((b_i,b_m) \in \mathcal{F}^i\). \(\dashv\)

Observation: If \(i,i' \in \omega\) and \(\mathcal{P}^i = \mathcal{P}^{i'} \neq \emptyset\), then \(a_i = a_{i'}\). Similarly, if \(i,i' \in \omega\) and \(\mathcal{F}^i = \mathcal{F}^{i'} \neq \emptyset\), then \(a_i = a_{i'}\).

Proof of Observation: Suppose \(\emptyset \neq \mathcal{P}^i = \mathcal{P}^{i'}\). If \((v,b) \in \mathcal{P}^i = \mathcal{P}^{i'}\), then the definition of \(\mathcal{P}^i\) implies \(\phi(b) = a_i\), and likewise the definition of \(\mathcal{F}^{i'}\) implies \(\phi(b) = a_{i'}\), so \(a_i = a_{i'}\). The argument is essentially the same for \(\mathcal{F}^i,\mathcal{F}^{i'}\). \(\dashv\)

If \(\mathcal{P}\subseteq\mathcal{B}\times \mathcal{B}\) and \(\mathcal{P}= \mathcal{P}^i \neq \emptyset\) for some \(i \in \omega\), define \(\Pi(\mathcal{P}) = a_i\). Similarly, if \(\mathcal{F}\subseteq\mathcal{B}\times \mathcal{B}\) and \(\mathcal{F}= \mathcal{F}^i \neq \emptyset\) for some \(i \in \omega\), define \(\Pi(\mathcal{F}) = a_i\). Note that this mapping \(\Pi\) is well-defined by the previous observation.

With these preliminaries in place, we now move on to the main line of argument. Consider the following statement:

• There is some \(v \in \mathrm{T}\) with \((v,v) \in \mathcal{R}\), such that for every edge \(e\) in \(\xrightarrow{\scalebox{.75}{\,{}_{\mathcal{B}}\,}}\), there are infinitely many \(\ell \in D\) such that for some \(m \in D\) with \(m > \ell\) there is a walk \(\langle b_{\ell},b_{\ell+1},b_{\ell+2},\dots,b_{m} \rangle\) in \(\langle \mathcal{B},\xrightarrow{\scalebox{.75}{\,{}_{\mathcal{B}}\,}}\rangle\) from \(b_{\ell} = v\) to \(b_{m} = v\) such that this walk projects onto \(\langle a_{\ell},a_{\ell+1},a_{\ell+2},\dots,a_{m} \rangle\), and this walk traverses \(e\), in the sense that \((b_i,b_{i+1}) = e\) for some \(i\) with \(\ell \leq i < m\).

As we shall see in what follows, this statement \((\ddagger)\) is a sharp dividing line between alternatives \((1)\) and \((2)\) in the statement of the theorem: if \((\ddagger)\) is true then \((1)\) holds, and if not then \((2)\) holds.

To see that \((\ddagger) \Rightarrow (1)\), we construct by recursion a diligent walk through \(\langle \mathcal{B},\xrightarrow{\scalebox{.75}{\,{}_{\mathcal{B}}\,}}\rangle\) that almost projects onto \(\left\langle a_n \colon n \in \omega \right\rangle\). At step \(n\) of the recursion, we add not just one point to our walk, but a long string of points with indices between some \(m_{k_{n-1}}\) and \(m_{k_n}\). (These indices \(k_0,k_1,\dots\) are chosen along the way, as part of the construction.) Fix an enumeration of the edges of \(\langle\mathcal{B},\xrightarrow{\scalebox{.75}{\,{}_{\mathcal{B}}\,}}\rangle\), say \(\xrightarrow{\scalebox{.75}{\,{}_{\mathcal{B}}\,}}\;= \{e_0,e_1,\dots,e_{M-1}\}\), and fix some \(v \in \mathrm{T}\) witnessing \((\ddagger)\).

For the base step of the recursion, let \(k_0=0\) and let \(\langle b_0,b_1,b_2,\dots,b_{m_0} \rangle\) be a walk in \(\langle \mathcal{B},\xrightarrow{\scalebox{.75}{\,{}_{\mathcal{B}}\,}}\rangle\) ending at \(v = b_{m_0} = b_{m_{k_0}}\). Some such walk exists because \(\langle \mathcal{B},\xrightarrow{\scalebox{.75}{\,{}_{\mathcal{B}}\,}}\rangle\) is strongly connected.

At step \(n > 0\) of the recursion, we begin with a walk \(\langle b_0,b_1,\dots,b_{m_{k_{n-1}} }\rangle\) in \(\langle \mathcal{B},\xrightarrow{\scalebox{.75}{\,{}_{\mathcal{B}}\,}}\rangle\) such that \(b_{m_{k_{n-1}}} = v\). Let \(j\) denote the unique member of \(\{0,1,2,\dots,M-1\}\) such that \(n \equiv j\) (mod \(M\)). Because \(b_{m_{k_{n-1}}} = v\), and because \(v\) witnesses \((\ddagger)\), there is some \(k_n > k_{n-1}\) such that there is a walk \(\langle b_{m_{k_{n-1}}},b_{m_{k_{n-1}}+1},b_{m_{k_{n-1}}+2},\dots,b_{m_{k_n}} \rangle\) in \(\langle \mathcal{B},\xrightarrow{\scalebox{.75}{\,{}_{\mathcal{B}}\,}}\rangle\) from \(v = b_{m_{k_{n-1}}}\) to \(v = b_{m_{k_n}}\) that projects onto \(\langle a_{m_{k_{n-1}}},a_{m_{k_{n-1}}+1},a_{m_{k_{n-1}}+2},\dots,a_{m_{k_n}} \rangle\), and such that \(e_j = (b_i,b_{i+1})\) for some \(i\) with \(m_{k_{n-1}} \leq i < m_{k_n}\). We take this walk to define \(b_i\) when \(m_{k_{n-1}} < i \leq m_{k_n}\). We claim that the sequence \(\left\langle b_i \colon i \in \omega \right\rangle\) produced by this recursion is a diligent walk through \(\langle \mathcal{B},\xrightarrow{\scalebox{.75}{\,{}_{\mathcal{B}}\,}}\rangle\) that almost projects onto \(\left\langle a_i \colon i \in \omega \right\rangle\).

It is clear that \(\left\langle b_i \colon i \in \omega \right\rangle\) is an infinite walk in \(\langle \mathcal{B},\xrightarrow{\scalebox{.75}{\,{}_{\mathcal{B}}\,}}\rangle\). Furthermore, this walk is diligent because for any given \(e_j\) in \(\xrightarrow{\scalebox{.75}{\,{}_{\mathcal{B}}\,}}\), if \(n \equiv j\) (mod \(M\)) then \((b_i,b_{i+1}) = e_j\) for some \(i\) with \(m_{k_{n-1}} \leq i < m_{k_n}\), so that every member of \(\xrightarrow{\scalebox{.75}{\,{}_{\mathcal{B}}\,}}\) is equal to \((b_i,b_{i+1})\) for infinitely many \(i \in \omega\). Finally, our construction guarantees that \(\phi(b_i) = a_i\) for all \(i \geq m_0\), which means \(\left\langle b_i \colon i \in \omega \right\rangle\) almost projects onto \(\left\langle a_i \colon i \in \omega \right\rangle\). This completes the proof that \((\ddagger)\) implies alternative \((1)\) from the statement of the theorem.

It remains to show that if \((\ddagger)\) fails then alternative \((2)\) from the statement of the theorem holds. As in the proof of Theorem 26, this involves the construction of a digraph \(\langle \mathcal{C},\xrightarrow{\scalebox{.75}{\,{}_{\mathcal{C}}\,}}\rangle\). For each \(k > 0\), define \[\begin{align} \mathcal{L}^k &\,=\, \left\lbrace ( \mathcal{P}^i,\mathcal{F}^i ) \colon m_k < i < m_{k+1} \right\rbrace, \\ \mathcal{E}^k &\,=\, \left\lbrace \big( (\mathcal{P}^i,\mathcal{F}^i),(\mathcal{P}^{i+1},\mathcal{F}^{i+1}) \big) \colon m_k < i < m_{k+1}-1 \right\rbrace, \\ c^k_\text{in} &\,=\, \big( \mathcal{P}^{m_k+1},\mathcal{F}^{m_k+1} \big), \\ c^k_\text{out} &\,=\, \big( \mathcal{P}^{m_{k+1}-1},\mathcal{F}^{m_{k+1}-1} \big). \end{align}\]

A \(4\)-tuple \((\mathcal{L},\mathcal{E},c_\text{in},c_\text{out})\) is used infinitely often if there are infinitely many \(k > 0\) with \((\mathcal{L},\mathcal{E},c_\text{in},c_\text{out}) = (\mathcal{L}^k,\mathcal{E}^k,c^k_\text{in},c^k_\text{out}).\) Because there are only finitely many possibilities for the \(4\)-tuple \((\mathcal{L}^k,\mathcal{E}^k,c^k_\text{in},c^k_\text{out})\), there is some \(K > 0\) such that \((\mathcal{L}^k,\mathcal{E}^k,c^k_\text{in},c^k_\text{out})\) is used infinitely often for every \(k \geq K\).

Let \(N\) denote the number of \(4\)-tuples that are used infinitely often, and fix indices \(k_0,k_1,\dots,k_N\) such that \[(\mathcal{L}^{k_0},\mathcal{E}^{k_0},c^{k_0}_\text{in}c^{k_0}_\text{out}),\dots,(\mathcal{L}^{k_N},\mathcal{E}^{k_N},c^{k_N}_\text{in},c^{k_N}_\text{out})\] is a complete list of all the \(4\)-tuples used infinitely often. For each \(j \leq N\) let \[\begin{align} \mathcal{C}_j &\,=\, \{j\} \times \mathcal{L}^{k_j}, \\ \mathcal{E}_j &\,=\, \left\lbrace \big( (j,t),(j,t') \big) \colon (t,t') \in \mathcal{E}^{k_j} \right\rbrace, \\ c^j_\text{in} &\,=\, \big( j,c^{k_j}_\text{in} \big), \\ c^j_\text{out} &\,=\, \big( j,c^{k_j}_\text{out} \big). \end{align}\] In other words, these are the \(4\)-tuples described above, only we have modified the vertex sets of the \(\mathcal{L}^{k_j}\) so that all the different \(\mathcal{C}_j\)’s are disjoint. Furthermore let us assume, without loss of generality, that \(\mathrm{dom}(\mathcal{R}) = \mathrm{T}\notin \bigcup_{j \leq N}\mathcal{C}_j\). (This is true automatically unless the vertices of \(\mathcal{B}\) are labelled in an unreasonable way.)

We are now ready to define the digraph \(\langle \mathcal{C},\xrightarrow{\scalebox{.75}{\,{}_{\mathcal{C}}\,}}\rangle\) that will witness alternative \((2)\) from the statement of the theorem. First, let \[\mathcal{C}\,=\, \{\mathrm{T}\} \cup \mathcal{C}_0 \cup \mathcal{C}_1 \cup \dots \cup \mathcal{C}_N.\] Then define the edge relation on \(\mathcal{C}\) as follows: \[\begin{align} x \xrightarrow{\scalebox{.75}{\,{}_{\mathcal{C}}\,}}y \quad \;\Longleftrightarrow \quad \;& x,y \in \mathcal{C}_j \text{ and } (x,y) \in \mathcal{E}_j \text{ for some j \leq N, or} \\ & x=\mathrm{T}\text{ and } y = c^j_\text{in} \text{ for some j \leq N, or} \\ & x = c^j_{\mathrm{out}} \text{ and } y = \mathrm{T}\text{ for some j \leq N}. \end{align}\]

Define \(\psi: \mathcal{C}\to \mathcal{A}\) by setting \(\psi(\mathrm{T}) = a_D\), and \(\psi(j,(\mathcal{P},\mathcal{F})) = \Pi(\mathcal{P}) = \Pi(\mathcal{F})\). (To see that this last equality is true, observe that if \((j,(\mathcal{P},\mathcal{F})) \in \mathcal{C}_j\), then \((\mathcal{P},\mathcal{F}) = (\mathcal{P}^i,\mathcal{F}^i)\) for some \(i\), and this implies \(\Pi(\mathcal{P}_i) = \Pi(\mathcal{F}_i) = a_i\).)

This completes the definition of \(\langle \mathcal{C},\xrightarrow{\scalebox{.75}{\,{}_{\mathcal{C}}\,}}\rangle\) and \(\psi\). To finish the proof, we need to show that \(\langle \mathcal{C},\xrightarrow{\scalebox{.75}{\,{}_{\mathcal{C}}\,}}\rangle\) is strongly connected, that \(\psi\) is an epimorphism from \(\langle \mathcal{C},\xrightarrow{\scalebox{.75}{\,{}_{\mathcal{C}}\,}}\rangle\) to \(\langle \mathcal{A},\xrightarrow{\scalebox{.75}{\,{}_{\mathcal{A}}\,}}\rangle\), that there is a diligent walk through \(\langle \mathcal{C},\xrightarrow{\scalebox{.75}{\,{}_{\mathcal{C}}\,}}\rangle\) projecting onto \(\left\langle a_n \colon n \in \omega \right\rangle\) via \(\psi\), and that \(\psi\) is incompatible with \(\phi\).

Like in the proof of Theorem 26, we can verify the first three of these four things all at once via Lemma 14. To do this, we must define a diligent walk \(\left\langle c_i \colon i \in \omega \right\rangle\) through \(\langle \mathcal{C},\xrightarrow{\scalebox{.75}{\,{}_{\mathcal{C}}\,}}\rangle\) that almost projects onto \(\left\langle a_i \colon i \in \omega \right\rangle\) via \(\psi\). Recall that \(K\) was chosen sufficiently large so that if \(k \geq K\) then \((\mathcal{L}^k,\mathcal{E}^k,c^k_\text{in},c^k_\text{out})\) is used infinitely often. Given \(i \geq m_0\), let \(k(i)\) be the (unique) index with \(m_{k(i)} \leq i < m_{k(i)+1}\). Furthermore, if \(i \geq m_K\) then define \(j(i)\) to be the (unique) index \(\leq\! N\) with \[\big( \mathcal{L}^{k(i)},\mathcal{E}^{k(i)},c^{k(i)}_\text{in},c^{k(i)}_\text{out} \big) \,=\, \big( \mathcal{L}^{k_{j(i)}},\mathcal{E}^{k_{j(i)}},c^{k_{j(i)}}_\text{in},c^{k_{j(i)}}_\text{out} \big).\] For all \(i \geq m_K\), define \[c_i \,=\, \begin{cases} \mathrm{T}&\text{ if } i \in D, \\ \big( j(i),(\mathcal{P}^i,\mathcal{F}^i) \big) &\text{ otherwise.} \end{cases}\]

Let us check that this sequence is a walk through \(\langle \mathcal{C},\xrightarrow{\scalebox{.75}{\,{}_{\mathcal{C}}\,}}\rangle\). For the first case, suppose \(i,i+1 \notin D\). This implies \(k(i) = k(i+1)\) and \(j(i) = j(i+1)\), which means \(c_i,c_{i+1} \in \mathcal{C}_{j(i)}\) and furthermore, \(\big( (\mathcal{P}^i,\mathcal{F}^i),(\mathcal{P}^{i+1},\mathcal{F}^{i+1}) \big) \in \mathcal{E}^{k(i)}\) (by the definition of \(\mathcal{E}^{k(i)}\)), which gives \((c_i,c_{i+1}) \in \mathcal{E}_{j(i)}\) (by the definition of \(\mathcal{E}_{j(i)}\)). Hence \(c_i \xrightarrow{\scalebox{.75}{\,{}_{\mathcal{C}}\,}}c_{i+1}\) in this case. For the second case, suppose \(i \in D\) but \(i+1 \notin D\). Then \(i = m_{k(i)} = m_{k(i+1)}\) and \(i+1 = m_{k(i)}+1\), which means \(c_{i+1} \,=\, \big( j(i+1), (\mathcal{P}^{m_{k(i)}+1},\mathcal{F}^{m_{k(i)}+1} ) \big) \,=\, c^{j(i+1)}_\text{in},\) while \(c_i = \mathrm{T}\). Thus \(c_i \xrightarrow{\scalebox{.75}{\,{}_{\mathcal{C}}\,}}c_{i+1}\) in this case also. For the third case, suppose \(i \notin D\) but \(i+1 \in D\). Then \(i+1 = m_{k(i+1)}\) and \(k(i) = k(i+1)-1\), which implies (like in the previous case) that \(c_i = c^{j(i)}_\text{out},\) while \(c_{i+1} = \mathrm{T}\). Thus \(c_i \xrightarrow{\scalebox{.75}{\,{}_{\mathcal{C}}\,}}c_{i+1}\) in this case also. These three cases are exhaustive, by our assumption near the beginning of the proof that \(D\) does not contain two consecutive integers. Hence \(\left\langle c_i \colon i \geq m_K \right\rangle\) is a walk.

To see that this walk is diligent, fix some edge \((c,c')\) in \(\xrightarrow{\scalebox{.75}{\,{}_{\mathcal{C}}\,}}\). There is some \(j \leq N\) such that either \((1)\) \((c,c') \in \mathcal{E}_j\), or \((2)\) \(c = \mathrm{T}\) and \(c' = c^j_\text{in}\), or \((3)\) \(c = c^j_\text{out}\) and \(c' = \mathrm{T}\). Because \(\big( \mathcal{L}^{k_j},\mathcal{E}^{k_j},c^{k_j}_\text{in}c^{k_j}_\text{out} \big)\) is used infinitely often, there are arbitrarily large values of \(k \in \omega\) such that \(j(m_k) = j\). But then there is some \(i\) with \(k(i) = k\) and \(m_{k(i)} \leq i \leq m_{k(i)+1}\) such that \((c_i,c_{i+1}) = (c,c')\). Thus \((c,c') = (c_i,c_{i+1})\) for arbitrarily large values of \(i\), and this shows that \(\left\langle c_i \colon i \geq m_K \right\rangle\) is a diligent walk.

Furthermore, if \(i \in D\), then \(a_i = a_D = \psi(c_i) = a_D\); and if \(i \notin D\), then \(\Pi_\phi(c_i) = \psi \big( j(i),(\mathcal{P}^i,\mathcal{F}^i) \big) = \Pi(\mathcal{P}^i) = \Pi(\mathcal{F}^i) = a_i.\) Therefore this walk projects onto \(\left\langle a_i \colon i \geq m_K \right\rangle\). Because \(\left\langle a_i \colon i \in \omega \right\rangle\) is a diligent walk through \(\langle \mathcal{A},\xrightarrow{\scalebox{.75}{\,{}_{\mathcal{A}}\,}}\rangle\), the tail sequence \(\left\langle a_i \colon i \geq m_K \right\rangle\) is also a diligent walk through \(\langle \mathcal{A},\xrightarrow{\scalebox{.75}{\,{}_{\mathcal{A}}\,}}\rangle\). We have thus showed that \(\left\langle c_i \colon i \geq m_K \right\rangle\) is a diligent walk through \(\langle \mathcal{C},\xrightarrow{\scalebox{.75}{\,{}_{\mathcal{C}}\,}}\rangle\) that projects onto a diligent walk \(\left\langle a_i \colon i \geq m_K \right\rangle\) through \(\langle \mathcal{A},\xrightarrow{\scalebox{.75}{\,{}_{\mathcal{A}}\,}}\rangle\). By Lemma 14, \(\langle \mathcal{C},\xrightarrow{\scalebox{.75}{\,{}_{\mathcal{C}}\,}}\rangle\) is strongly connected, and \(\psi\) is an epimorphism from \(\langle \mathcal{C},\xrightarrow{\scalebox{.75}{\,{}_{\mathcal{C}}\,}}\rangle\) onto \(\langle \mathcal{A},\xrightarrow{\scalebox{.75}{\,{}_{\mathcal{A}}\,}}\rangle\).

Now that we know \(\langle \mathcal{C},\xrightarrow{\scalebox{.75}{\,{}_{\mathcal{C}}\,}}\rangle\) is strongly connected, we can use this fact to find a length-\(m_K\) walk \(\langle c^0,c^1,\dots,c^{m_K}\rangle\) in \(\langle \mathcal{C},\xrightarrow{\scalebox{.75}{\,{}_{\mathcal{C}}\,}}\rangle\) such that \(c^{m_K} = c_{m_K} = \mathrm{T}\). And then \(\langle c^0,c^1,\dots,c^{m_K}=c_{m_K},c_{m_K+1},c_{m_K+2},\dots \rangle\) is a diligent walk through \(\langle \mathcal{C},\xrightarrow{\scalebox{.75}{\,{}_{\mathcal{C}}\,}}\rangle\) that almost projects onto \(\left\langle a_i \colon i \in \omega \right\rangle\).

To finish the proof, it remains only to show that if \((\ddagger)\) fails then \(\psi\) is incompatible with \(\phi\). We do this by proving the contrapositive: if \(\psi\) and \(\phi\) are compatible, then \((\ddagger)\) holds.

To this end, let us suppose \(\psi\) is compatible with \(\phi\). That is, suppose there is a strongly connected digraph \(\langle \mathcal{W},\xrightarrow{\scalebox{.75}{\,{}_{\mathcal{W}}\,}}\rangle\) and epimorphisms \(\bar \phi\) and \(\bar \psi\) from \(\langle \mathcal{W},\xrightarrow{\scalebox{.75}{\,{}_{\mathcal{W}}\,}}\rangle\) to \(\langle \mathcal{B},\xrightarrow{\scalebox{.75}{\,{}_{\mathcal{B}}\,}}\rangle\) and \(\langle \mathcal{C},\xrightarrow{\scalebox{.75}{\,{}_{\mathcal{C}}\,}}\rangle\), respectively, such that \(\phi \circ \bar \phi = \psi \circ \bar \psi\).

For each \(c \in \mathcal{C}\) and \(v \in \mathcal{B}\), define \[\mathcal{P}_v(c) \,=\, \begin{cases} \left\lbrace b \in \mathcal{B} \colon (v,b) \in \mathcal{R} \right\rbrace &\text{ if }c = \mathrm{T}, \\ \,\mathcal{P}^i_v &\text{ if c = (j(i),(\mathcal{P}^i,\mathcal{F}^i)) for some i \notin D.} \end{cases}\] \[\mathcal{F}_v(c) \,=\, \begin{cases} \left\lbrace b \in \mathcal{B} \colon (b,v) \in \mathcal{R} \right\rbrace &\text{ if }c = \mathrm{T}, \\ \,\mathcal{F}^i_v &\text{ if c = (j(i),(\mathcal{P}^i,\mathcal{F}^i)) for some i \notin D.} \end{cases}\]

Claim: Suppose \(\langle w_0,w_1,\dots,w_\ell\rangle\) is a walk in \(\langle \mathcal{W},\xrightarrow{\scalebox{.75}{\,{}_{\mathcal{W}}\,}}\rangle\) with \(\bar \psi(w_\ell) = \mathrm{T}\), and let \(v = \bar \phi(w_\ell)\). Then \(\bar \phi(w_i) \in \mathcal{F}_{v}(\bar \psi(w_i))\) for all \(i < \ell\).

Proof of Claim: This claim is proved by a backwards inductive argument: we take \(i = \ell-1\) as the base case, and prove for the inductive step that if \(0 < i < \ell\) and \(\bar \phi(w_i) \in \mathcal{F}_v(\bar \psi(w_i))\), then \(\bar \phi(w_{i-1}) \in \mathcal{F}_v(\bar \psi(w_{i-1}))\). For the base case \(i = \ell-1\), recall that we are assuming \(\bar \psi(w_\ell) = \mathrm{T}\). Thus \[\phi \circ \bar \phi(w_\ell) \,=\, \psi \circ \bar \psi(w_\ell) \,=\, \psi(\mathrm{T}) \,=\, a_D,\] and therefore \(\bar \phi(w_\ell) \in \phi^{-1}(a_D)\). Because \(w_{\ell-1} \xrightarrow{\scalebox{.75}{\,{}_{\mathcal{W}}\,}}w_\ell\) and \(\bar \psi\) is an epimorphism, \(\bar \psi(w_{\ell-1}) \xrightarrow{\scalebox{.75}{\,{}_{\mathcal{C}}\,}}\bar \psi(w_\ell)\). Because \(\bar \psi(w_\ell) = \mathrm{T}\), this means \(\bar \psi(w_{\ell-1}) = (j,c^j_{\text{out}})\) for some \(j \leq N\), which means \(\bar \psi(w_{\ell-1}) = \big( j,(\mathcal{P}^{m_k-1},\mathcal{F}^{m_k-1}) \big)\) for some \(k \geq K\). Furthermore, \(\bar \phi(w_{\ell-1}) \xrightarrow{\scalebox{.75}{\,{}_{\mathcal{B}}\,}}\bar \phi(w_\ell)\), because \(w_{\ell-1} \xrightarrow{\scalebox{.75}{\,{}_{\mathcal{W}}\,}}w_\ell\) and \(\bar \phi\) is an epimorphism. Thus \(\langle \bar \phi(w_{\ell-1}),\bar \phi(w_\ell) \rangle\) is a walk in \(\langle \mathcal{B},\xrightarrow{\scalebox{.75}{\,{}_{\mathcal{B}}\,}}\rangle\) from \(\bar \phi(w_{\ell-1})\) to \(\bar \phi(w_\ell) = v\), and this walk projects onto \(\langle a_{m_k-1},a_{m_k}\rangle\) because \[\phi \circ \bar \phi(w_\ell) \,=\, \psi \circ \bar \psi(w_\ell) \,=\, \psi(\mathrm{T}) \,=\, a_D \,=\, a_{m_k} \text{ and} \,\] \[\phi \circ \bar \phi(w_{\ell-1}) \,=\, \psi \circ \bar \psi(w_{\ell-1}) \,=\, \Pi(\mathcal{F}^{m_k-1}) \,=\, a_{m_k-1}.\] Consequently, by the definition of \(\mathcal{F}\), \(\bar \phi(w_{\ell-1}) \in \mathcal{F}_v^{m_k-1} = \mathcal{F}_v(\bar \psi(w_{\ell-1}))\).

For the inductive step, fix \(i\) with \(0 < i < \ell\) and suppose, as an inductive hypothesis, that \(\bar \phi(w_i) \in \mathcal{F}_{v}(\bar \psi(w_i))\). We consider two cases. For the first case, suppose \(\bar \psi(w_i) = \mathrm{T}\). In this case, the inductive hypothesis states that \(\bar \phi(w_i) \in \mathcal{F}_v(\mathrm{T})\). This means that \((\bar \phi(w_i),v) \in \mathcal{R}\), which implies in particular that \(\bar \phi(w_i) \in \mathrm{T}\subseteq\phi^{-1}(a_D)\). Once this is known, we may reason exactly as in the previous paragraph (replacing each instance of \(\ell\) with an \(i\)) and deduce that \(\bar \phi(w_{i-1}) \in \mathcal{F}_{\bar \phi(w_i)}(\bar \psi(w_{i-1}))\). Because \((\bar \phi(w_i),v) \in \mathcal{R}\), this implies (via the two observations following the definition of \(\mathcal{P}\) and \(\mathcal{F}\) and the comments following those observations) that \(\bar \phi(w_{i-1}) \in \mathcal{F}_v(\bar \psi(w_{i-1}))\).

For the second case, suppose \(\bar \psi(w_i) \neq \mathrm{T}\). Because \(w_{i-1} \xrightarrow{\scalebox{.75}{\,{}_{\mathcal{W}}\,}}w_i\) and \(\bar \psi\) is an epimorphism, \(\bar \psi(w_{i-1}) \xrightarrow{\scalebox{.75}{\,{}_{\mathcal{C}}\,}}\bar \psi(w_i)\). By our definition of \(\langle\mathcal{C},\xrightarrow{\scalebox{.75}{\,{}_{\mathcal{C}}\,}}\rangle\), this means there is some \(j \leq N\) and some \(p\) with \(m_{k_j} < p < m_{k_j+1}\) such that \(\mathcal{F}(\bar \psi(w_i)) = \mathcal{F}^p\) and \(\mathcal{F}(\bar \psi(w_{i-1})) = \mathcal{F}^{p-1}\). (The fact that \(\bar \psi(w_i) \neq \mathrm{T}\) rules out the possibility that \(p \in D\).) By definition, \(\bar \phi(w_i) \in \mathcal{F}_v(\bar \psi(w_i)) = \mathcal{F}_v^p\) means there is a walk \(\langle b_p,b_{p+1},\dots,\dots,b_{m'} \rangle\) in \(\langle \mathcal{B},\xrightarrow{\scalebox{.75}{\,{}_{\mathcal{B}}\,}}\rangle\), for some \(m' \in D\) with \(m' \geq m_{k_{j+1}}\), that goes from \(b_p = \bar \phi(w_i)\) to \(v = b_{m'}\) and projects onto \(\langle a_p,a_{p+1},\dots,a_{m'} \rangle\). Furthermore, \[\phi \circ \bar \phi(w_i) \,=\, \psi \circ \bar \psi(w_i) \,=\, \Pi(\mathcal{F}^p) \,=\, a_p \text{, and} \,\] \[\phi \circ \bar \phi(w_{i-1}) \,=\, \psi \circ \bar \psi(w_{i-1}) \,=\, \Pi(\mathcal{F}^{p-1}) \,=\, a_{p-1}.\] In particular, \(\phi \big( \bar \phi(w_{i-1}) \big) = a_{p-1}\), and of course \(\bar \phi(w_{i-1}) \xrightarrow{\scalebox{.75}{\,{}_{\mathcal{B}}\,}}\bar \phi(w_i)\) (because \(w_{i-1} \xrightarrow{\scalebox{.75}{\,{}_{\mathcal{W}}\,}}w_i\) and \(\bar \phi\) is an epimorphism). But then this shows that \[\langle \bar \phi(w_{i-1}),\bar \phi(w_{i})=b_p,b_{p+1},\dots,b_{m'} \rangle\] is a walk in \(\langle \mathcal{B},\xrightarrow{\scalebox{.75}{\,{}_{\mathcal{B}}\,}}\rangle\) from \(\bar \phi(w_{i-1})\) to \(b_{m'} = v\), and this walk projects onto \(\langle a_{p-1},a_p,a_{p+1},\dots,a_{m'} \rangle\). Hence \(\bar \phi(w_{i-1}) \in \mathcal{F}_v^{p-1} = \mathcal{F}_v(\bar \psi(w_{i-1}))\). \(\dashv\)

Claim: If \(w \in \mathcal{W}\) and \(\bar \psi(w) = \mathrm{T}\), then \(\bar \phi(w) \in \mathrm{T}\) and \((\bar \phi(w),\bar \phi(w)) \in \mathcal{R}\).

Proof of Claim: Fix \(w \in \mathcal{W}\) with \(\bar \psi(w) = \mathrm{T}\). Because \(\langle \mathcal{W},\xrightarrow{\scalebox{.75}{\,{}_{\mathcal{W}}\,}}\rangle\) is strongly connected, there is a walk \(\langle w_0,w_1,\dots,w_\ell \rangle\) with length \(\ell > 0\) from \(w = w_0\) to \(w = w_\ell\). Letting \(v = \bar \phi(w_\ell)\), the previous claim gives \(\bar \phi(w_0) \in \mathcal{F}_v(\bar \psi(w_0))\). By the definition of \(\mathcal{F}_v(\bar \psi(w_0))\), this means \((\bar \phi(w_0),v) \in \mathcal{R}\). But \(\bar \phi(w_0) = \bar \phi(w)\) and \(v = \bar \phi(w_\ell) = \bar \phi(w)\), so \((\bar \phi(w),\bar \phi(w)) \in \mathcal{R}\). \(\dashv\)

Claim: Suppose \(\langle w_0,w_1,\dots,w_\ell\rangle\) is a walk in \(\langle \mathcal{W},\xrightarrow{\scalebox{.75}{\,{}_{\mathcal{W}}\,}}\rangle\) with \(\bar \psi(w_0) = \mathrm{T}\), and let \(v = \bar \phi(w_0)\). Then \(\bar \phi(w_i) \in \mathcal{P}_{v}(\bar \psi(w_i))\) for all \(i > 0\).

Proof of Claim: This claim is the mirror image of the one above concerning \(\mathcal{F}\). It is proved in almost the same way, but by a regular induction (starting at \(1\), not \(0\)) rather than a backward induction.

For the base case \(i = 1\), recall that we are assuming \(\bar \psi(w_0) = \mathrm{T}\). Thus \[\phi \circ \bar \phi(w_0) \,=\, \psi \circ \bar \psi(w_0) \,=\, \psi(\mathrm{T}) \,=\, a_D,\] and therefore \(\bar \phi(w_0) \in \phi^{-1}(a_D)\). Because \(w_0 \xrightarrow{\scalebox{.75}{\,{}_{\mathcal{W}}\,}}w_1\) and \(\bar \psi\) is an epimorphism, \(\bar \psi(w_0) \xrightarrow{\scalebox{.75}{\,{}_{\mathcal{C}}\,}}\bar \psi(w_1)\). Because \(\bar \psi(w_0) = \mathrm{T}\), this means \(\bar \psi(w_1) = (j,c^j_{\text{in}})\) for some \(j \leq N\), which means \(\bar \psi(w_1) = (j,(\mathcal{P}^{m_k+1},\mathcal{F}^{m_k+1})\) for some \(k \geq K\). Furthermore, \(\bar \phi(w_0) \xrightarrow{\scalebox{.75}{\,{}_{\mathcal{B}}\,}}\bar \phi(w_1)\), because \(w_0 \xrightarrow{\scalebox{.75}{\,{}_{\mathcal{W}}\,}}w_1\) and \(\bar \phi\) is an epimorphism. Thus \(\langle \bar \phi(w_0),\bar \phi(w_1) \rangle\) is a walk in \(\langle \mathcal{B},\xrightarrow{\scalebox{.75}{\,{}_{\mathcal{B}}\,}}\rangle\) from \(v=\bar \phi(w_0)\) to \(\bar \phi(w_1)\), and this walk projects onto \(\langle a_{m_k},a_{m_k+1}\rangle\) because \[\phi \circ \bar \phi(w_0) \,=\, \psi \circ \bar \psi(w_0) \,=\, \psi(\mathrm{T}) \,=\, a_D \,=\, a_{m_k} \text{ and} \,\] \[\phi \circ \bar \phi(w_{1}) \,=\, \psi \circ \bar \psi(w_{1}) \,=\, \Pi(\mathcal{P}^{m_k+1}) \,=\, a_{m_k+1}.\] Consequently, by the definition of \(\mathcal{P}\), \(\bar \phi(w_{1}) \in \mathcal{P}_v^{m_k+1} = \mathcal{P}_v(\bar \psi(w_{1}))\).

For the inductive step, fix \(i\) with \(0 < i < \ell\) and suppose, as an inductive hypothesis, that \(\bar \phi(w_i) \in \mathcal{P}_{v}(\bar \psi(w_i))\). We consider two cases. For the first case, suppose \(\bar \psi(w_i) = \mathrm{T}\). In this case, the inductive hypothesis states that \(\bar \phi(w_i) \in \mathcal{P}_v(\mathrm{T})\). This means \((v,\bar \phi(w_i)) \in \mathcal{R}\), which implies \(\bar \phi(w_i) \in \mathrm{T}\subseteq\phi^{-1}(a_D)\). Once this is known, we may reason as in the previous paragraph (replacing \(0\) with \(i\) and \(1\) with \(i+1\)) and deduce \(\bar \phi(w_{i+1}) \in \mathcal{P}_{\bar \phi(w_i)}(\bar \psi(w_{i+1}))\). Because \((v,\bar \phi(w_i)) \in \mathcal{R}\), this implies \(\bar \phi(w_{i-1}) \in \mathcal{P}_v(\bar \psi(w_{i-1}))\).

For the second case, suppose \(\bar \psi(w_i) \neq \mathrm{T}\). Because \(w_i \xrightarrow{\scalebox{.75}{\,{}_{\mathcal{W}}\,}}w_{i+1}\) and \(\bar \psi\) is an epimorphism, \(\bar \psi(w_i) \xrightarrow{\scalebox{.75}{\,{}_{\mathcal{C}}\,}}\bar \psi(w_{i+1})\). By our definition of \(\langle\mathcal{C},\xrightarrow{\scalebox{.75}{\,{}_{\mathcal{C}}\,}}\rangle\), this means there is some \(j \leq N\) and some \(p\) with \(m_{k_j} < p < m_{k_j+1}\) such that \(\mathcal{P}(\bar \psi(w_i)) = \mathcal{P}^p\) and \(\mathcal{P}(\bar \psi(w_{i+1})) = \mathcal{P}^{p+1}\). (The fact that \(\bar \psi(w_i) \neq \mathrm{T}\) rules out the possibility that \(p \in D\).) By definition, \(\bar \phi(w_i) \in \mathcal{P}_v(\bar \psi(w_i)) = \mathcal{P}_v^p\) means there is a walk \(\langle b_{m'},b_{m'+1},\dots,b_{p} \rangle\) in \(\langle \mathcal{B},\xrightarrow{\scalebox{.75}{\,{}_{\mathcal{B}}\,}}\rangle\), for some \(m' \in D\) with \(m' \leq m_{k_j}\), that goes from \(v = b_{m'}\) to \(\bar \phi(w_i) = b_p\) and projects onto \(\langle a_{m'},a_{m'+1},\dots,a_{p} \rangle\). Furthermore, \[\phi \circ \bar \phi(w_i) \,=\, \psi \circ \bar \psi(w_i) \,=\, \Pi(\mathcal{P}^p) \,=\, a_p \text{, and} \,\] \[\phi \circ \bar \phi(w_{i+1}) \,=\, \psi \circ \bar \psi(w_{i+1}) \,=\, \Pi(\mathcal{P}^{p+1}) \,=\, a_{p+1}.\] In particular, \(\phi \big( \bar \phi(w_{i+1}) \big) = a_{p+1}\), and of course \(\bar \phi(w_i) \xrightarrow{\scalebox{.75}{\,{}_{\mathcal{B}}\,}}\bar \phi(w_{i+1})\) (because \(w_{i} \xrightarrow{\scalebox{.75}{\,{}_{\mathcal{W}}\,}}w_{i+1}\) and \(\bar \phi\) is an epimorphism). But then this shows that \[\langle b_{m'},b_{m'+1},\dots,b_p = \bar \phi(w_i),\bar \phi(w_{i+1}) \rangle\] is a walk in \(\langle \mathcal{B},\xrightarrow{\scalebox{.75}{\,{}_{\mathcal{B}}\,}}\rangle\) from \(b_{m'} = v\) to \(\bar \phi(w_{i+1})\), and this walk projects onto \(\langle a_{m'},\dots,a_{p},a_{p+1} \rangle\). Hence \(\bar \phi(w_{i+1}) \in \mathcal{P}_v^{p+1} = \mathcal{P}_v(\bar \psi(w_{i+1}))\). \(\dashv\)

With these claims established, we are ready to finish the proof. Because \(\bar \psi\) is an epimorphism, there is some \(w \in \mathcal{W}\) such that \(\bar \psi(w) = \mathrm{T}\). We claim that \(v = \bar \phi(w)\) witnesses \((\ddagger)\).

From the second of the three claims above, \(v \in \mathrm{T}\) and \((v,v) \in \mathcal{R}\).

Fix an edge \(e = (b,b')\) in \(\xrightarrow{\scalebox{.75}{\,{}_{\mathcal{B}}\,}}\). Because \(\bar \phi\) is an epimorphism, there exist some \(w,w' \in \mathcal{W}\) such that \(w \xrightarrow{\scalebox{.75}{\,{}_{\mathcal{W}}\,}}w'\) and \((b,b') = (\bar \phi(w),\bar \phi(w'))\). Using the fact that \(\langle \mathcal{W},\xrightarrow{\scalebox{.75}{\,{}_{\mathcal{W}}\,}}\rangle\) is strongly connected, there is a walk \(\langle w_0,w_1,\dots,w_\ell \rangle\) in \(\langle \mathcal{W},\xrightarrow{\scalebox{.75}{\,{}_{\mathcal{W}}\,}}\rangle\) with \(w_0 = w_\ell = v\) such that \((w,w') = (w_i,w_{i+1})\) for some \(i < \ell\).

Using the first and third of our three claims above, \(\bar \phi(w_i) \in \mathcal{P}_v(\bar \psi(w_i))\) and \(\bar \phi(w_{i+1}) \in \mathcal{F}_v(\bar \psi(w_{i+1}))\).

There is some \(j \leq N\) such that either \(\bar \psi(w_i) \in \mathcal{C}_j\) or \(\bar \psi(w_{i+1}) \in \mathcal{C}_j\) (or both). Fix any \(k \geq K\) with \(j(m_k) = j\). Because \(\bar \psi(w_i) \xrightarrow{\scalebox{.75}{\,{}_{\mathcal{C}}\,}}\bar \psi(w_{i+1})\), our definition of \(\mathcal{E}_j\) implies there is some \(p\) with \(m_k \leq p < m_{k+1}\) such that \(\bar \psi(w_i) = \big( j,(\mathcal{P}^p,\mathcal{F}^p) \big)\) and \(\bar \psi(w_{i+1}) = \big( j,(\mathcal{P}^{p+1},\mathcal{F}^{p+1}) \big)\). Hence \[b \,=\, \bar \phi(w_i) \,\in\, \mathcal{P}^p_v \qquad \text{ and } \qquad b' \,=\, \bar \phi(w_{i+1}) \,\in\, \mathcal{F}^{p+1}_v.\] By definition, this means

• for some \(\ell \in D\) with \(\ell \leq m_k\), there is a walk \(\langle b_\ell,b_{\ell+1},\dots,b_p \rangle\) in \(\langle \mathcal{B},\xrightarrow{\scalebox{.75}{\,{}_{\mathcal{B}}\,}}\rangle\) from \(b_\ell = v\) to \(b_p = \bar \phi(w_i) = b\) that projects onto \(\langle a_{m_k},a_{m_k+1},\dots,a_p \rangle\); and

• for some \(m \in D\) with \(m \geq m_{k+1}\), there is a walk \(\langle b_{p+1},b_{p+2},\dots,b_m \rangle\) in \(\langle \mathcal{B},\xrightarrow{\scalebox{.75}{\,{}_{\mathcal{B}}\,}}\rangle\) from \(b_{p+1} = \bar \phi(w_{i+1}) = b'\) to \(b_m = v\) that projects onto \(\langle a_{p+1},a_{p+2},\dots,a_m \rangle\).

But then, concatenating these two walks, \[\langle b_\ell,b_{\ell+1},\dots,b_p,b_{p+1},b_{p+2},\dots,b_m \rangle\] is a walk in \(\langle \mathcal{B},\xrightarrow{\scalebox{.75}{\,{}_{\mathcal{B}}\,}}\rangle\) from \(v\) to \(v\) that projects onto \(\langle a_\ell,\dots,a_m \rangle\) and has \((b_p,b_{p+1}) = (b,b') = e\) for some \(p\) with \(\ell \leq p < m\).

This nearly proves that \(v\) witnesses \((\ddagger)\) for \(e\), except that we must show it is possible for the parameter \(\ell\) to be arbitrarily large in such walks.

In the above argument, we took \(k \geq K\) subject only to the condition that \(j(m_k) = j\). There are infinitely many such \(k\), because \((\mathcal{L}^{k_j},\mathcal{E}^{k_j},c^{k_j}_\text{in}c^{k_j}_\text{out})\) is used infinitely often. Consequently, the value of \(k\) in the preceding argument may be taken arbitrarily large. To finish the proof, we show that the value of \(\ell\) in the preceding argument may be taken to be either \(m_k\) or \(m_{k-1}\).

If \(\ell = m_k\) we are done, so suppose \(\ell < m_k\). Then \(\langle b_\ell,b_{\ell+1},\dots,b_{m_k} \rangle\) (the truncation of the walk constructed above) is a walk in \(\langle \mathcal{B},\xrightarrow{\scalebox{.75}{\,{}_{\mathcal{B}}\,}}\rangle\) that projects onto \(\langle a_\ell,a_{\ell+1},\dots,a_{m_k} \rangle\). Consequently, \((b_\ell,b_{m_k}) = (v,b_{m_k}) \in \mathcal{R}\). But by our choice of \(\mathcal{R}\), and our work near the beginning of the proof, it follows that there is a walk \(\langle b^{m_{k-1}},b^{m_{k-1}+1},\dots,b^{m_k} \rangle\) in \(\langle \mathcal{B},\xrightarrow{\scalebox{.75}{\,{}_{\mathcal{B}}\,}}\rangle\) from \(v = b^{m_{k-1}}\) to \(b_{m_k} = b^{m_k}\) that projects onto \(\langle a_{m_{k-1}},\dots,a_{m_k} \rangle\). Thus \[\langle b^{m_{k-1}},b^{m_{k-1}+1},\dots,b^{m_k} = b_{m_k},\dots,b_p,b_{p+1},b_{p+2},\dots,b_m \rangle\] is a walk in \(\langle \mathcal{B},\xrightarrow{\scalebox{.75}{\,{}_{\mathcal{B}}\,}}\rangle\) from \(v\) to \(v\) that projects onto \(\langle a_{m_{k-1}},\dots,a_m \rangle\) and has \((b_p,b_{p+1}) = (b,b') = e\) for some \(p\) with \(m_{k-1} \leq p < m\). Therefore \(v\) witnesses \((\ddagger)\) for \(e\). Because \(e\) was arbitrary, \(v\) witnesses \((\ddagger)\), as claimed. ◻

Proof. Consider the special case of Lemma 8 with \(\langle \mathcal{V},\to \rangle = \langle \mathcal{A},\xrightarrow{\text{\tiny \,\sigma\,}}\rangle\) and with the isomorphism \(\phi\) taken to be the identity map. The lemma asserts there is an infinite walk \(\left\langle a_n \colon n \in \omega \right\rangle\) through \(\langle \mathcal{A},\xrightarrow{\text{\tiny \,\sigma\,}}\rangle\) such that the natural map associated to this walk is the identity: that is, \(a = [\left\lbrace n \in \omega \colon a_n = a \right\rbrace]\) for all \(a \in \mathcal{A}\). Thus taking \(X_a = \left\lbrace n \in \omega \colon a_n = a \right\rbrace\) works. ◻

Proof. Let \(\mathcal{A}\) be a partition of \(\frac{\mathcal{P}(\omega)}{\mathrm{Fin}}\), and let \((\phi,\langle\mathcal{V},\to\rangle)\) be a virtual refinement of \(\langle \mathcal{A},\xrightarrow{\text{\tiny \,\sigma\,}}\rangle\).

Applying the previous lemma, there is a partition \(\left\lbrace X_a \colon a \in \mathcal{A} \right\rbrace\) of \(\omega\) into infinite sets such that \([X_a] = a\) for all \(a \in \mathcal{A}\), and for every \(n \in \omega\), if \(n \in X_a\) and \(n+1 \in X_{a'}\) then \(a \xrightarrow{\text{\tiny \,\sigma\,}}a'\). As in the proof of the previous lemma, there is an infinite walk through \(\langle \mathcal{A},\xrightarrow{\text{\tiny \,\sigma\,}}\rangle\) associated to this partition: for every \(n \in \omega\), let \(X(n)\) denote the unique member of \(\left\lbrace X_a \colon a \in \mathcal{A} \right\rbrace\) containing \(n\), and then let \(a_n = [X(n)]\).

Applying Theorem 25 with \(\langle \mathcal{B},\xrightarrow{\scalebox{.75}{\,{}_{\mathcal{B}}\,}}\rangle = \langle \mathcal{V},\to \rangle\), either

1. there is a diligent walk through \(\langle \mathcal{V},\to \rangle\) that almost projects (via \(\phi\)) onto \(\left\langle a_n \colon n \in \omega \right\rangle\), or

2. there is a strongly connected digraph \(\langle \mathcal{C},\xrightarrow{\scalebox{.75}{\,{}_{\mathcal{C}}\,}}\rangle\) and an epimorphism \(\psi\) from \(\langle \mathcal{C},\xrightarrow{\scalebox{.75}{\,{}_{\mathcal{C}}\,}}\rangle\) onto \(\langle \mathcal{A},\xrightarrow{\text{\tiny \,\sigma\,}}\rangle\) such that \(\psi\) is incompatible with \(\phi\), and there is a diligent walk \(\left\langle c_n \colon n \in \omega \right\rangle\) through \(\langle \mathcal{C},\xrightarrow{\scalebox{.75}{\,{}_{\mathcal{C}}\,}}\rangle\) that almost projects (via \(\psi\)) onto \(\left\langle a_n \colon n \in \omega \right\rangle\).

First, suppose case \((1)\) holds. Fix a diligent walk \(\left\langle v_n \colon n \in \omega \right\rangle\) through \(\langle \mathcal{V},\to \rangle\) such that \(\phi(v_n) = a_n\) for all but finitely many \(n \in \omega\). As in Definition 13, let \(A_v = [\left\lbrace n \in \omega \colon v_n = v \right\rbrace]\) for each \(v \in \mathcal{V}\). Let \(\mathcal{A}' = \left\lbrace A_v \colon v \in \mathcal{V} \right\rbrace.\) We claim that this partition of \(\frac{\mathcal{P}(\omega)}{\mathrm{Fin}}\) realizes \((\phi,\langle \mathcal{V},\to \rangle)\). First, note that because \(\phi(v_n) = a_n\) for all but finitely many \(n \in \omega\), \[\begin{align} \textstyle \bigvee \left\lbrace A_v \colon \phi(v) = a \right\rbrace &\textstyle \,=\, [\bigcup_{v \in \phi^{-1}(a)} \left\lbrace n \in \omega \colon v_n = v \right\rbrace] \\ &\,=\, [\left\lbrace n \in \omega \colon \phi(v_n) = a \right\rbrace] \,=\, [\left\lbrace n \in \omega \colon a_n = a \right\rbrace] \,=\, a \end{align}\] for every \(a \in \mathcal{A}\). Thus \(\mathcal{A}'\) refines \(\mathcal{A}\). For each \(v \in \mathcal{V}\), let \(\phi'(v) = A_v\). By Lemma 7, \(\phi'\) is an isomorphism from \(\langle \mathcal{V},\to \rangle\) to \(\langle \mathcal{A}',\xrightarrow{\text{\tiny \,\sigma\,}}\rangle\) (the natural isomorphism). If \(v \in \mathcal{V}\) and \(\phi(v) = a\), then \[\begin{align} \phi'(v) \,=\, [\left\lbrace n \in \omega \colon v_n = v \right\rbrace] &\,\leq\, [\left\lbrace n \in \omega \colon \phi(v_n) = a \right\rbrace] \\ &\,=\, [\left\lbrace n \in \omega \colon a_n = a \right\rbrace] \,=\, a. \end{align}\] Recall that the natural map \(\pi: \mathcal{A}' \to \mathcal{A}\) sends \(\phi(v)\) to \(a\) whenever \(\phi(v) \leq a\). The foregoing computation shows \(\pi \circ \phi'(v) = \phi(v)\). As \(v \in \mathcal{V}\) was arbitrary, \(\pi \circ \phi' = \phi\). Thus \(\langle \mathcal{A}',\xrightarrow{\text{\tiny \,\sigma\,}}\rangle\) realizes the virtual extension \((\phi,\langle \mathcal{V},\to \rangle)\), and so alternative \((1)\) of Definition 17 holds.

Next, suppose case \((2)\) holds in the Theorem 25 dichotomy. Fix a strongly connected digraph \(\langle \mathcal{C},\xrightarrow{\scalebox{.75}{\,{}_{\mathcal{C}}\,}}\rangle\) and an epimorphism \(\psi\) from \(\langle \mathcal{C},\xrightarrow{\scalebox{.75}{\,{}_{\mathcal{C}}\,}}\rangle\) onto \(\langle \mathcal{A},\xrightarrow{\text{\tiny \,\sigma\,}}\rangle\) such that \(\psi\) is incompatible with \(\phi\), and there is a diligent walk \(\left\langle c_n \colon n \in \omega \right\rangle\) through \(\langle \mathcal{C},\xrightarrow{\scalebox{.75}{\,{}_{\mathcal{C}}\,}}\rangle\) that almost projects (via \(\psi\)) onto \(\left\langle a_n \colon n \in \omega \right\rangle\). Like in the previous paragraph, let \(A_c = [\left\lbrace n \in \omega \colon c_n = c \right\rbrace]\) for each \(c \in \mathcal{C}\), and let \(\mathcal{A}' = \left\lbrace A_c \colon c \in \mathcal{C} \right\rbrace.\) Because \(\psi(c_n) = a_n\) for all sufficiently large \(n \in \omega\), \[\begin{align} \textstyle \bigvee \left\lbrace A_c \colon \psi(c) = a \right\rbrace &\textstyle \,=\, [\bigcup_{c \in \psi^{-1}(a)} \left\lbrace n \in \omega \colon c_n = c \right\rbrace] \\ &\,=\, [\left\lbrace n \in \omega \colon \psi(c_n) = a \right\rbrace] \,=\, [\left\lbrace n \in \omega \colon a_n = a \right\rbrace] \,=\, a \end{align}\] for every \(a \in \mathcal{A}\). Thus \(\mathcal{A}'\) refines \(\mathcal{A}\). For each \(c \in \mathcal{C}\), let \(\psi'(c) = A_c\), and note that \(\psi'\) is an isomorphism from \(\langle \mathcal{C},\xrightarrow{\scalebox{.75}{\,{}_{\mathcal{C}}\,}}\rangle\) to \(\langle \mathcal{A}',\xrightarrow{\text{\tiny \,\sigma\,}}\rangle\) by Lemma 7. If \(c \in \mathcal{C}\) and \(\phi(c) = a\), then (as above) \[\begin{align} \psi'(c) \,=\, [\left\lbrace n \in \omega \colon c_n = c \right\rbrace] &\,\leq\, [\left\lbrace n \in \omega \colon \phi(c_n) = a \right\rbrace] \\ &\,=\, [\left\lbrace n \in \omega \colon a_n = a \right\rbrace] \,=\, a. \end{align}\] Thus the natural map \(\pi: \mathcal{A}' \to \mathcal{A}\) sends \(\psi'(c)\) to \(a\) for every \(c \in \mathcal{C}\). Hence \(\langle \mathcal{A}',\xrightarrow{\text{\tiny \,\sigma\,}}\rangle\) realizes the virtual extension \((\psi,\langle \mathcal{C},\xrightarrow{\scalebox{.75}{\,{}_{\mathcal{C}}\,}}\rangle)\). Because \(\psi\) is incompatible with \(\phi\), this implies that alternative \((2)\) of Definition 17 holds.

Thus, for the virtual refinement \((\phi,\langle \mathcal{V},\to \rangle)\), the two alternatives in Theorem 25 correspond exactly to the two alternatives in Definition 17, and consequently, \((\phi,\langle \mathcal{V},\to \rangle)\) is polarized. Because \((\phi,\langle \mathcal{V},\to \rangle)\) was an arbitrary virtual partition of an arbitrary partition of \(\langle \frac{\mathcal{P}(\omega)}{\mathrm{Fin}},\sigma\rangle\), this shows that \(\langle \frac{\mathcal{P}(\omega)}{\mathrm{Fin}},\sigma\rangle\) is polarized. ◻

Proof. The proof strategy can be summarized in a sentence: This follows from the previous theorem, because polarization descends to elementary substructures. However, it is not necessarily obvious that this property descends to elementary substructures, because polarization is not obviously expressible in a first-order sentence. So let us check the details.

Let \(\langle \mathbb{A},\sigma\rangle\) be an elementary substructure of \(\langle \frac{\mathcal{P}(\omega)}{\mathrm{Fin}},\sigma\rangle\), let \(\mathcal{A}\) be a partition of \(\mathbb{A}\), and let \((\phi,\langle \mathcal{V},\to \rangle)\) be a virtual refinement of \(\langle \mathcal{A},\xrightarrow{\text{\tiny \,\sigma\,}}\rangle\). By the previous theorem, \((\phi,\langle \mathcal{V},\to \rangle)\) is polarized in the larger dynamical system \(\langle \frac{\mathcal{P}(\omega)}{\mathrm{Fin}},\sigma\rangle\). Thus one of two things happens:

1. there is a partition \(\mathcal{A}'\) of \(\mathbb{A}\) that realizes \((\phi,\langle\mathcal{V},\to\rangle)\), or

2. there is a partition \(\mathcal{A}'\) of \(\mathbb{A}\) refining \(\mathcal{A}\) such that \((\pi,\langle \mathcal{A}',\xrightarrow{\text{\tiny \,\sigma\,}}\rangle)\) is incompatible with \((\phi,\langle \mathcal{V},\to \rangle)\), where \(\pi\) denotes the natural map from \(\mathcal{A}'\) onto \(\mathcal{A}\).

First suppose case \((1)\) holds. Fix an enumeration \(\mathcal{A}= \{a_1,a_2,\dots,a_m\}\) of \(\mathcal{A}\) and an enumeration \(\mathcal{A}' = \{a_1',a_2',\dots,a_n'\}\) of \(\mathcal{A}'\). Like in the proof of Lemma 11, there is a first-order sentence \(\varphi(a_1,\dots,a_m,a_1',\dots,a_n',\sigma)\) about \(\langle \frac{\mathcal{P}(\omega)}{\mathrm{Fin}},\sigma\rangle\) that records precisely the structure of the digraphs \(\langle \mathcal{A},\xrightarrow{\text{\tiny \,\sigma\,}}\rangle\) and \(\langle \mathcal{A}',\xrightarrow{\text{\tiny \,\sigma\,}}\rangle\), and also records which members of \(\mathcal{A}'\) are below which members of \(\mathcal{A}\) (i.e., it records the action of the natural map \(\pi: \mathcal{A}' \to \mathcal{A}\)). Let \(\bar \varphi\) be the formula \[\exists x_1 \exists x_2 \dots \exists x_n \varphi(a_1,\dots,a_m,x_1,\dots,x_n,\sigma).\] This is a true assertion about \(\langle \frac{\mathcal{P}(\omega)}{\mathrm{Fin}},\sigma\rangle\), witnessed by setting \(x_i = a'_i\) for each \(i \leq n\). By elementarity, \(\bar \varphi\) must also be a true assertion about \(\langle \mathbb{A},\sigma\rangle\). Therefore \(\langle \mathbb{A},\sigma\rangle \models \varphi(a_1,\dots,a_m,\bar a_1,\dots,\bar a_n,\sigma)\) for some \(\bar a_1, \bar a_2,\dots, \bar a_n \in \mathbb{A}\). Because of our choice of \(\varphi\), this means that \(\bar \mathcal{A}= \{\bar a_1, \bar a_2,\dots, \bar a_n\}\) is a partition of \(\mathbb{A}\) refining \(\mathcal{A}\) and \((\pi,\langle \bar \mathcal{A},\xrightarrow{\text{\tiny \,\sigma\,}}\rangle)\) is identical to \((\pi,\langle \mathcal{A}',\xrightarrow{\text{\tiny \,\sigma\,}}\rangle)\), where in each case \(\pi\) denotes the natural map. Consequently, \((\pi,\langle \bar \mathcal{A},\xrightarrow{\text{\tiny \,\sigma\,}}\rangle)\) realizes \((\phi,\langle \mathcal{V},\to \rangle)\), because \((\pi,\langle \mathcal{A}',\xrightarrow{\text{\tiny \,\sigma\,}}\rangle)\) does. Thus the first case of Definition 17 holds for \(\langle \mathcal{V},\to \rangle\).

Next suppose case \((2)\) holds. As in case \((1)\), fix an enumeration \(\mathcal{A}= \{a_1,a_2,\dots,a_m\}\) of \(\mathcal{A}\) and an enumeration \(\mathcal{A}' = \{a_1',a_2',\dots,a_n'\}\) of \(\mathcal{A}'\), and fix a first-order sentence \(\varphi(a_1,\dots,a_m,a_1',\dots,a_n',\sigma)\) about \(\langle \frac{\mathcal{P}(\omega)}{\mathrm{Fin}},\sigma\rangle\) that records precisely the structure of \(\langle \mathcal{A},\xrightarrow{\text{\tiny \,\sigma\,}}\rangle\) and \(\langle \mathcal{A}',\xrightarrow{\text{\tiny \,\sigma\,}}\rangle\), and the action of the natural map \(\pi: \mathcal{A}' \to \mathcal{A}\). Let \(\bar \varphi\) be the formula \[\exists x_1 \exists x_2 \dots \exists x_n \varphi(a_1,\dots,a_m,x_1,\dots,x_n,\sigma).\] This is a true assertion about \(\langle \frac{\mathcal{P}(\omega)}{\mathrm{Fin}},\sigma\rangle\), so by elementarity, \(\langle \mathbb{A},\sigma\rangle \models \varphi(a_1,\dots,a_m,\bar a_1,\dots,\bar a_n,\sigma)\) for some \(\bar a_1, \bar a_2,\dots, \bar a_n \in \mathbb{A}\). By our choice of \(\varphi\), this means that \(\bar \mathcal{A}= \{\bar a_1, \bar a_2,\dots, \bar a_n\}\) is a partition of \(\mathbb{A}\) refining \(\mathcal{A}\) and \((\pi,\langle \bar \mathcal{A},\xrightarrow{\text{\tiny \,\sigma\,}}\rangle)\) is identical to \((\pi,\langle \mathcal{A}',\xrightarrow{\text{\tiny \,\sigma\,}}\rangle)\), where in each case \(\pi\) denotes the natural map. Consequently, \((\pi,\langle \bar \mathcal{A},\xrightarrow{\text{\tiny \,\sigma\,}}\rangle)\) is incompatible with \((\phi,\langle \mathcal{V},\to \rangle)\), and the second case of Definition 17 holds for \((\phi,\langle \mathcal{V},\to \rangle)\).

Thus the two cases listed at the beginning of the proof correspond exactly to the two cases in Definition 17, and \((\phi,\langle \mathcal{V},\to \rangle)\) is polarized in \(\langle \mathbb{A},\sigma\rangle\). Because \((\phi,\langle \mathcal{V},\to \rangle)\) was an arbitrary virtual partition of an arbitrary partition of \(\langle \mathbb{A},\sigma\rangle\), this shows that \(\langle \mathbb{A},\sigma\rangle\) is polarized. ◻

Proof of Lemma 2. Let \((\langle\mathbb{A},\alpha\rangle,\langle\mathbb{B},\beta\rangle,\iota,\eta)\) be an instance of the lifting problem for \(\langle \frac{\mathcal{P}(\omega)}{\mathrm{Fin}},\sigma\rangle\), and suppose that the image of \(\eta\) is an elementary substructure of \(\langle \frac{\mathcal{P}(\omega)}{\mathrm{Fin}},\sigma\rangle\). In other words, \(\eta\) is a conjugacy from \(\langle \mathbb{A},\alpha\rangle\) onto \(\langle \eta[A],\sigma\rangle \preceq \langle \frac{\mathcal{P}(\omega)}{\mathrm{Fin}},\sigma\rangle\). The previous theorem implies that \(\langle \mathbb{A},\alpha\rangle\) is polarized, because this property is preserved by conjugacies. Consequently, \((\langle\mathbb{A},\alpha\rangle,\langle\mathbb{B},\beta\rangle,\iota,\eta)\) has a solution by Theorem 24. ◻

Proof. We provide two proofs of this theorem. The first proof uses the technique of forcing, and is in some sense “slicker” because it gives the present theorem as a nearly immediate immediate consequence of Theorem 18. The second proof is forcing-free, and more direct. It gives the theorem not as a consequence of Theorem 18, but rather as a consequence of the technique used in its proof.

For the first proof, let \(\mathbb{P}\) denote the poset of countable partial functions \(\omega_1 \times \omega\to \omega\), ordered by extension, i.e., the usual poset for forcing \(\mathsf{CH}\) with countable conditions. Let \(G\) be a \(V\)-generic filter on \(\mathbb{P}\). Because \(\mathbb{P}\) is a countably closed notion of forcing, no new subsets of \(\omega\) are added by \(\mathbb{P}\), which means that \(V \cap \frac{\mathcal{P}(\omega)}{\mathrm{Fin}}= V[G] \cap \frac{\mathcal{P}(\omega)}{\mathrm{Fin}}\). Furthermore, because \(\sigma\) is definable by the simple formula \(\sigma([A]) = [A+1]\), the action of \(\sigma\) is the same in \(V\) and in \(V[G]\). Thus the structures \(\langle \frac{\mathcal{P}(\omega)}{\mathrm{Fin}},\sigma\rangle^V\) and \(\langle \frac{\mathcal{P}(\omega)}{\mathrm{Fin}},\sigma\rangle^{V[G]}\) are one in the same. Thus (by the “absoluteness of the satisfaction relation”) the theory of \(\langle \frac{\mathcal{P}(\omega)}{\mathrm{Fin}},\sigma\rangle\) is the same in \(V\) and in \(V[G]\). The same argument applies to \(\langle \frac{\mathcal{P}(\omega)}{\mathrm{Fin}},\sigma^{-1} \rangle\), so the theory of \(\langle \frac{\mathcal{P}(\omega)}{\mathrm{Fin}},\sigma^{-1} \rangle\) is also the same in \(V\) and in \(V[G]\). Because \(V[G] \models \mathsf{CH}\), Theorem 18 implies \(\langle \frac{\mathcal{P}(\omega)}{\mathrm{Fin}},\sigma\rangle\) and \(\langle \frac{\mathcal{P}(\omega)}{\mathrm{Fin}},\sigma^{-1} \rangle\) are conjugate in \(V[G]\). In particular, \(\langle \frac{\mathcal{P}(\omega)}{\mathrm{Fin}},\sigma\rangle\) and \(\langle \frac{\mathcal{P}(\omega)}{\mathrm{Fin}},\sigma^{-1} \rangle\) are elementarily equivalent in \(V[G]\). To summarize: the theory of \(\langle \frac{\mathcal{P}(\omega)}{\mathrm{Fin}},\sigma\rangle\) is the same in \(V\) as in \(V[G]\), the theory of \(\langle \frac{\mathcal{P}(\omega)}{\mathrm{Fin}},\sigma^{-1} \rangle\) is the same in \(V\) as in \(V[G]\), and in \(V[G]\) these two structures have the same theory. Consequently, they have the same theory in \(V\).

For the second proof, let us take a closer look at the proof of Theorem 18 earlier in the paper. In that proof, we construct a coherent sequence \(\left\langle \phi_\alpha \colon \alpha< \omega_1 \right\rangle\) of maps, where each \(\phi_\alpha\) is a conjugacy from \(\langle \mathbb{A}_\alpha,\sigma\rangle\) to \(\langle \mathbb{B}_\alpha,\sigma^{-1} \rangle\), where \(\mathbb{A}_\alpha\) and \(\mathbb{B}_\alpha\) are subalgebras of \(\frac{\mathcal{P}(\omega)}{\mathrm{Fin}}\). In fact, each \(\mathbb{A}_\alpha\) had the property that \(\langle \mathbb{A}_\alpha,\sigma\rangle\) is a countable elementary substructure of \(\langle \frac{\mathcal{P}(\omega)}{\mathrm{Fin}},\sigma\rangle\), and each \(\mathbb{B}_\alpha\) had the property that there is some subalgebra \(\mathbb{B}^0_{\alpha+1}\) with \(\mathbb{B}_\alpha\subseteq\mathbb{B}^0_{\alpha+1} \subseteq\mathbb{B}_{\alpha+1}\) such that \(\langle \mathbb{B}_{\alpha+1}^0,\sigma^{-1} \rangle\) is a countable elementary substructure of \(\langle \frac{\mathcal{P}(\omega)}{\mathrm{Fin}},\sigma^{-1} \rangle\).

Note that the existence of these \(\phi_\alpha\)’s and \(\mathbb{A}_\alpha\)’s, \(\mathbb{B}_\alpha\)’s and \(\mathbb{B}^0_{\alpha+1}\)’s does not depend on \(\mathsf{CH}\): the construction of the sequence can be carried out in \(\mathsf{ZFC}\). The assumption of \(\mathsf{CH}\) was used only to arrange the construction so that \(\bigcup_{\alpha< \omega_1} \mathbb{A}_\alpha= \bigcup_{\beta< \omega_1} \mathbb{B}_\alpha= \frac{\mathcal{P}(\omega)}{\mathrm{Fin}}\).

Without \(\mathsf{CH}\), we still get a map \(\phi_\omega: \mathbb{A}_\omega\to \mathbb{B}_\omega\). This map is a conjugacy from \(\langle \mathbb{A}_\omega,\sigma\rangle\) to \(\langle \mathbb{B}_\omega,\sigma^{-1} \rangle\). Now recall that an increasing union of elementary substructures is also an elementary substructure (by the Tarski-Vaught criterion). In particular, \(\langle \mathbb{A}_\omega,\sigma\rangle\) and \(\langle \mathbb{B}_\omega,\sigma^{-1} \rangle\) are elementary substructures of \(\langle \frac{\mathcal{P}(\omega)}{\mathrm{Fin}},\sigma\rangle\) and \(\langle \frac{\mathcal{P}(\omega)}{\mathrm{Fin}},\sigma^{-1} \rangle\), respectively, because \(\mathbb{A}_\omega= \bigcup_{n < \omega}\mathbb{A}_n\) and \(\mathbb{B}_\omega= \bigcup_{n < \omega}\mathbb{B}_{n+1}^0\). Because \(\langle \frac{\mathcal{P}(\omega)}{\mathrm{Fin}},\sigma\rangle\) and \(\langle \frac{\mathcal{P}(\omega)}{\mathrm{Fin}},\sigma^{-1} \rangle\) have elementary substructures that are conjugate to one another, they are elementarily equivalent. ◻

Proof. We repeat the proof of Theorem 18 with a few minor differences. As in that proof, if \(X \subseteq\frac{\mathcal{P}(\omega)}{\mathrm{Fin}}\) and \(|X| \leq \aleph_0\), then \(\langle\langle X \rangle\rangle\) denotes some countable subalgebra of \(\frac{\mathcal{P}(\omega)}{\mathrm{Fin}}\) with \(X \subseteq\langle\langle X \rangle\rangle\) such that \(\big\langle \langle\langle X \rangle\rangle,\sigma\!\!\restriction\!\! \langle\langle X \rangle\rangle \big\rangle\) is an elementary substructure of \(\langle \frac{\mathcal{P}(\omega)}{\mathrm{Fin}},\sigma\rangle\). Also as in that proof, we write \(\langle \mathbb{A},\sigma\rangle\) to abbreviate \(\langle \mathbb{A},\sigma\!\restriction\!\mathbb{A}\rangle\).

Let \(\left\langle a_\xi \colon \xi < \omega_1 \right\rangle\) be an enumeration of \(\frac{\mathcal{P}(\omega)}{\mathrm{Fin}}\) in order type \(\omega_1\). Using transfinite recursion, we now build a coherent sequence \(\left\langle \phi_\alpha \colon \alpha< \omega_1 \right\rangle\) of maps such that each \(\phi_\alpha\) is a conjugacy from its domain \(\langle \mathbb{A}_\alpha,\sigma\rangle\) to its co-domain \(\langle \mathbb{B}_\alpha,\sigma\rangle\); furthermore, we shall have \(\mathbb{A}_\alpha\subseteq\mathbb{A}_\beta\) and \(\mathbb{B}_\alpha\subseteq\mathbb{B}_\beta\) whenever \(\alpha\leq \beta\), and \(\mathbb{A}_\alpha= \bigcup_{\xi < \alpha}\mathbb{A}_\xi\) and \(\mathbb{B}_\alpha= \bigcup_{\xi < \alpha}\mathbb{B}_\xi\) for limit \(\alpha\).

Let \(\langle \mathbb{A},\sigma\rangle\) be a countable elementary substructure of \(\langle \frac{\mathcal{P}(\omega)}{\mathrm{Fin}},\sigma\rangle\), and let \(\eta\) be an embedding of \(\langle \mathbb{A},\sigma\rangle\) into \(\langle \frac{\mathcal{P}(\omega)}{\mathrm{Fin}},\sigma\rangle\). For the base case of the recursion, let \(\mathbb{A}_0 = \mathbb{A}\), let \(\phi_0 = \eta\), and let \(\mathbb{B}_0 = \phi_0[\mathbb{A}_0]\).

The remaining stages of the recursion proceed as in the proof of Theorem 18. At limit stages there is nothing to do: simply take \(\mathbb{A}_\alpha= \bigcup_{\xi < \alpha}\mathbb{A}_\xi\), \(\mathbb{B}_\alpha= \bigcup_{\xi < \alpha}\mathbb{B}_\xi\), and \(\phi_\alpha= \bigcup_{\xi < \alpha}\phi_\xi\). At successor steps, to obtain \(\mathbb{A}_{\alpha+1}\) and \(\phi_{\alpha+1}\), first let \(\mathbb{B}_{\alpha+1}^0 = \langle\langle \mathbb{B}_\alpha\cup \{a_\alpha\} \rangle\rangle\) and observe that \[(\langle\mathbb{B}_\alpha,\sigma\rangle,\langle\mathbb{B}^0_{\alpha+1},\sigma\rangle,\iota,\phi_\alpha^{-1})\] is an instance of the lifting problem for \(\langle \frac{\mathcal{P}(\omega)}{\mathrm{Fin}},\sigma\rangle\), where \(\iota\) denotes the inclusion \(\mathbb{B}_\alpha\xhookrightarrow{} \mathbb{B}_{\alpha+1}^0\). Furthermore, the image of \(\phi^{-1}_\alpha\), namely \(\langle \mathbb{A}_\alpha,\sigma\rangle\), is an elementary substructure of \(\langle \frac{\mathcal{P}(\omega)}{\mathrm{Fin}},\sigma\rangle\). By Lemma 2, there is an embedding \(\phi^0_{\alpha+1}\) from \(\langle \mathbb{B}_{\alpha+1}^0,\sigma\rangle\) into \(\langle \frac{\mathcal{P}(\omega)}{\mathrm{Fin}},\sigma\rangle\). Let \(\mathbb{A}^0_{\alpha+1}\) denote the image of this embedding, so that \(\phi^0_{\alpha+1}\) is a conjugacy from \(\langle \mathbb{B}^0_{\alpha+1},\sigma\rangle\) to \(\langle \mathbb{A}^0_{\alpha+1},\sigma\rangle\), and \((\phi^0_{\alpha+1})^{-1}\) is a conjugacy from \(\langle \mathbb{A}^0_{\alpha+1},\sigma\rangle\) to \(\langle \mathbb{B}^0_{\alpha+1},\sigma\rangle\).

Second, let \(\mathbb{A}_{\alpha+1} = \langle\langle \mathbb{A}_\alpha^0 \cup \{a_\alpha\} \rangle\rangle\) and observe that \[(\langle\mathbb{A}^0_{\alpha+1},\sigma\rangle,\langle\mathbb{A}_{\alpha+1},\sigma\rangle,\iota,(\phi_\alpha^0)^{-1})\] is another instance of the lifting problem for \(\langle \frac{\mathcal{P}(\omega)}{\mathrm{Fin}},\sigma\rangle\), where \(\iota\) denotes the inclusion \(\mathbb{A}^0_{\alpha+1} \xhookrightarrow{} \mathbb{A}_{\alpha+1}\). Furthermore, the image of \((\phi^0_{\alpha+1})^{-1}\), namely \(\langle \mathbb{B}_{\alpha+1}^0,\sigma\rangle\), is an elementary substructure of \(\langle \frac{\mathcal{P}(\omega)}{\mathrm{Fin}},\sigma\rangle\). By Lemma 2, there is an embedding \(\phi_{\alpha+1}\) from \(\langle \mathbb{A}_{\alpha+1},\sigma\rangle\) into \(\langle \frac{\mathcal{P}(\omega)}{\mathrm{Fin}},\sigma\rangle\). Let \(\mathbb{B}_{\alpha+1}\) denote the image of this embedding, so that \(\phi_{\alpha+1}\) is a conjugacy from \(\langle \mathbb{A}_{\alpha+1},\sigma\rangle\) to \(\langle \mathbb{B}_{\alpha+1},\sigma\rangle\), and \((\phi_{\alpha+1})^{-1}\) is a conjugacy from \(\langle \mathbb{B}_{\alpha+1},\sigma\rangle\) to \(\langle \mathbb{A}_{\alpha+1},\sigma\rangle\).

This completes the recursion. In the end, \(\phi = \bigcup_{\alpha< \omega_1}\phi_\alpha\) is a conjugacy from \(\langle \frac{\mathcal{P}(\omega)}{\mathrm{Fin}},\sigma\rangle\) to \(\langle \frac{\mathcal{P}(\omega)}{\mathrm{Fin}},\sigma\rangle\), and clearly \(\phi \!\restriction\!\mathbb{A}= \phi \!\restriction\!\mathbb{A}_0 = \phi_0 = \eta\). ◻

Proof. First let us show that this is true assuming \(\mathsf{CH}\). (This will enable us afterward to deduce the general result without \(\mathsf{CH}\).)

Let \(\langle \mathbb{A},\sigma\rangle\) be a countable elementary substructure of \(\langle \frac{\mathcal{P}(\omega)}{\mathrm{Fin}},\sigma\rangle\), and let \(\eta\) be an embedding of \(\langle \mathbb{A},\sigma\rangle\) into \(\langle \frac{\mathcal{P}(\omega)}{\mathrm{Fin}},\sigma\rangle\). By the previous theorem, \(\mathsf{CH}\) implies there is a conjugacy map \(\phi\) from \(\langle \frac{\mathcal{P}(\omega)}{\mathrm{Fin}},\sigma\rangle\) to itself such that \(\phi \!\restriction\!\mathbb{A}= \eta\). But conjugacy maps preserve the truth of all sentences in the language of dynamical systems (because they are the isomorphisms of this category). From this and the fact that \(\langle \mathbb{A},\sigma\rangle\) is an elementary substructure of \(\langle \frac{\mathcal{P}(\omega)}{\mathrm{Fin}},\sigma\rangle\), it follows that \(\phi \!\restriction\!\mathbb{A}= \eta\) is an elementary embedding: for any first-order sentence \(\psi\) and any \(a_1,\dots,a_n \in \mathbb{A}\), \[\begin{align} \langle \mathbb{A},\sigma\rangle \models \psi(a_1,\dots,a_n,\sigma) & \;\Leftrightarrow \;\langle \frac{\mathcal{P}(\omega)}{\mathrm{Fin}},\sigma\rangle \models \psi(a_1,\dots,a_n,\sigma) \\ & \;\Leftrightarrow \;\langle \frac{\mathcal{P}(\omega)}{\mathrm{Fin}},\sigma\rangle \models \psi(\phi(a_1),\dots,\phi(a_n),\sigma) \\ & \;\Leftrightarrow \;\langle \frac{\mathcal{P}(\omega)}{\mathrm{Fin}},\sigma\rangle \models \psi(\eta(a_1),\dots,\eta(a_n),\sigma). \end{align}\]

Thus the corollary is true assuming \(\mathsf{CH}\). To get rid of this assumption, we use the same forcing trick as in the proof of Theorem 29. Let \(\langle \mathbb{A},\sigma\rangle\) be a countable elementary substructure of \(\langle \frac{\mathcal{P}(\omega)}{\mathrm{Fin}},\sigma\rangle\), and let \(\eta\) be an embedding of \(\langle \mathbb{A},\sigma\rangle\) into \(\langle \frac{\mathcal{P}(\omega)}{\mathrm{Fin}},\sigma\rangle\). As in the proof of Theorem 29, there is a forcing extension \(V[G]\) such that \(V[G] \models \mathsf{CH}\), and such that the theory of \(\langle \mathbb{A},\sigma\rangle\) or \(\langle \eta[\mathbb{A}],\sigma\rangle\) or \(\langle \frac{\mathcal{P}(\omega)}{\mathrm{Fin}},\sigma\rangle\) is the same in \(V\) and in \(V[G]\). By the previous paragraph, \(\eta\) is an elementary embedding in \(V[G]\). But because the theory of \(\langle \mathbb{A},\sigma\rangle\) and \(\langle \eta[\mathbb{A}],\sigma\rangle\) and \(\langle \frac{\mathcal{P}(\omega)}{\mathrm{Fin}},\sigma\rangle\) is the same in \(V\) and in \(V[G]\), this implies \(\eta\) is an elementary embedding in \(V\) as well. ◻

Proof. Let \(\langle \mathbb{A},\sigma\rangle\) and \(\langle \mathbb{B},\sigma\rangle\) be elementary substructures of \(\langle \frac{\mathcal{P}(\omega)}{\mathrm{Fin}},\sigma\rangle\), and suppose \(\eta\) is an embedding of \(\langle \mathbb{A},\sigma\rangle\) into \(\langle \mathbb{B},\sigma\rangle\). Let \(\psi\) be any first-order sentence in the language of dynamical systems, let \(a_1,\dots,a_n \in \mathbb{A}\), and suppose \(\langle \mathbb{A},\sigma\rangle \models \psi(a_1,\dots,a_n,\sigma)\). Let \(\langle \mathbb{A}_0,\sigma\rangle\) be a countable elementary substructure of \(\langle \mathbb{A},\sigma\rangle\) with \(a_1,\dots,a_n \in \mathbb{A}_0\). Then \(\langle \mathbb{A}_0,\sigma\rangle \models \psi(a_1,\dots,a_n,\sigma)\), by elementarity. By the previous theorem, \(\eta \!\restriction\!\mathbb{A}_0\) is an elementary embedding of \(\langle \mathbb{A}_0,\sigma\rangle\) into \(\langle \frac{\mathcal{P}(\omega)}{\mathrm{Fin}},\sigma\rangle\). Thus \(\langle \frac{\mathcal{P}(\omega)}{\mathrm{Fin}},\sigma\rangle \models \psi(\eta(a_1),\dots,\eta(a_n),\sigma)\). Because \(\langle \mathbb{B},\sigma\rangle\) is an elementary substructure of \(\langle \frac{\mathcal{P}(\omega)}{\mathrm{Fin}},\sigma\rangle\), this implies \(\langle \mathbb{B},\sigma\rangle \models \psi(\eta(a_1),\dots,\eta(a_n),\sigma)\) as well. Hence \(\langle \mathbb{A},\sigma\rangle \models \psi(a_1,\dots,a_n,\sigma)\) implies \(\langle \mathbb{B},\sigma\rangle \models \psi(\eta(a_1),\dots,\eta(a_n),\sigma)\); i.e., \(\eta\) is an elementary embedding. ◻

Proof. Suppose \(\mathbb{A}\) is a countably infinite subalgebra of \(\frac{\mathcal{P}(\omega)}{\mathrm{Fin}}\) that is closed under \(\sigma\) and \(\sigma^{-1}\). Let \(\mathcal{S} = \left\lbrace A \subseteq\omega \colon [A] \in \mathbb{A}\setminus [\emptyset] \right\rbrace\). Then \(\mathcal{S}\) is a countable set of infinite subsets of \(\omega\). By a standard diagonalization argument, \(\mathcal{S}\) is not a splitting family; i.e., there is some infinite \(D \subseteq\omega\) such that for all \(A \in \mathcal{S}\) either \(D \cap A\) is finite or \(D \setminus A\) is finite.

We now define a permutation \(h: \omega\to \omega\) by permuting some intervals associated to \(D\). Specifically, let \(d_0 = 0\) and let \(\left\lbrace d_i \colon i > 0 \right\rbrace\) be an increasing enumeration of the set \(D+1\). Define \(h\) by setting \[h(i) = \begin{cases} i + d_{2n+2} - d_{2n+1} & \text{ if }i \in [d_{2n},d_{2n+1}) \text{ for some n}, \\ i - d_{2n+1} + d_{2n} & \text{ if }i \in [d_{2n+1},d_{2n+2}) \text{ for some n}. \end{cases}\] In other words, if we set \(I_n = [d_n,d_{n+1})\) for all \(n\), then \(h\) is the map that simply swaps the intervals \(I_{2n}\) and \(I_{2n+1}\) for all \(n\).

Define \(s: \omega\to \omega\) by setting \(s(i) = h^{-1}(h(i)+1)\) for all \(i \in \omega\). Checking a few cases, we see that \[s(i) = \begin{cases} i + 1 & \text{ if } i \in [d_{2n},d_{2n+1}-1) \text{ for some n}, \\ d_{2n} & \text{ if } i = d_{2n+2}-1 \text{ for some n}, \\ d_{2n+3} & \text{ if } i = d_{2n+1}-1 \text{ for some n}. \end{cases}\] In particular, \(s(i) = i+1\) for all \(i \notin D\), and \(s[D] = \{0\} \cup (D+1) \setminus \{d_1\}\).

As was mentioned in Section 3, a function \(f: \omega\to \omega\) naturally induces a function \(\frac{\mathcal{P}(\omega)}{\mathrm{Fin}}\to \frac{\mathcal{P}(\omega)}{\mathrm{Fin}}\), namely \(f^*([A]) = [\left\lbrace f(n) \colon n \in A \right\rbrace]\). Let \(h^*\) denote the function \(\frac{\mathcal{P}(\omega)}{\mathrm{Fin}}\to \frac{\mathcal{P}(\omega)}{\mathrm{Fin}}\) induced by \(h\), i.e., \(h^*([A]) = [\left\lbrace h(n) \colon n \in \omega \right\rbrace]\) for all \(A \subseteq\omega\). Note that \(h^*\) is an automorphism of \(\frac{\mathcal{P}(\omega)}{\mathrm{Fin}}\), because \(h\) is a bijection \(\omega\to \omega\).

We shall finish the proof of the lemma by showing that \(\eta = h^* \!\restriction\!\mathbb{A}\) is the desired embedding. Because \(\eta\) is the restriction to \(\mathbb{A}\) of an automorphism \(\frac{\mathcal{P}(\omega)}{\mathrm{Fin}}\to \frac{\mathcal{P}(\omega)}{\mathrm{Fin}}\), it is automatically an embedding of Boolean algebras \(\mathbb{A}\to \frac{\mathcal{P}(\omega)}{\mathrm{Fin}}\). We must check that \(\eta \circ \sigma(a) = \sigma\circ \eta(a)\) for all \(a \in \mathbb{A}\), and that \(\eta \neq \sigma^p \!\restriction\!\mathbb{A}\) for any \(p \in \mathbb{Z}\).

Let \(a \in \frac{\mathcal{P}(\omega)}{\mathrm{Fin}}\), and fix some \(A \subseteq\omega\) with \(a = [A]\). Then, using the fact that \(s(n) = h^{-1}(h(n)+1)\) for all \(n\), \[\begin{align} \sigma\circ \eta(a) &\,=\, \sigma([\left\lbrace h(n) \colon n \in A \right\rbrace]) \,=\, [\left\lbrace h(n)+1 \colon n \in A \right\rbrace] \\ & \,=\, [\left\lbrace h(s(n)) \colon n \in A \right\rbrace] \,=\, \eta([\left\lbrace s(n) \colon n \in A \right\rbrace]). \end{align}\] If \(a \in \mathbb{A}\), then by our choice of \(D\) either \(D \setminus A\) is finite or \(D \cap A\) is finite. If \(D \cap A\) is finite, then, using the fact that \(s(i) = i+1\) when \(i \notin D\), \[[\left\lbrace s(n) \colon n \in A \right\rbrace] = [\left\lbrace s(n) \colon n \in A \setminus D \right\rbrace] = [\left\lbrace n+1 \colon n \in A \setminus D \right\rbrace] = [A+1].\] On the other hand, if \(D \setminus A\) is finite then, using the fact that \(s(i) = i+1\) when \(i \notin D\) and the fact that \(s[D] = \{0\} \cup (D+1) \setminus \{d_1\}\), \[\begin{align} [\left\lbrace s(n) \colon n \in A \right\rbrace] &\,=\, [\left\lbrace s(n) \colon n \in A \setminus D \right\rbrace \cup \left\lbrace s(n) \colon n \in D \right\rbrace] \\ &\,=\, [\left\lbrace n+1 \colon n \in A \setminus D \right\rbrace \cup (D+1)] \,=\, [A+1]. \end{align}\] In either case, if \(a \in \mathbb{A}\) then \(\sigma\circ \eta (a) = \eta([\left\lbrace s(n) \colon n \in A \right\rbrace]) = [A+1] = \eta \circ \sigma(a).\)

Finally, we must show that \(\eta \neq \sigma^p \!\restriction\!\mathbb{A}\) for any \(p \in \mathbb{Z}\).

Let \(N \in \omega\) with \(N > 0\), and for each \(j \in \{0,1,\dots,N-1\}\) let \(N\omega+j = \left\lbrace Nk+j \colon k \in \omega \right\rbrace\). By hypothesis, \(\mathbb{A}\) contains \([N\omega]\). Furthermore, because \(\mathbb{A}\) is closed under \(\sigma\), \(\mathbb{A}\) contains \([N\omega+j] = \sigma^j([N\omega])\) for all \(j \in \{0,1,\dots,N-1\}\). For any such \(j\), either \(D \setminus (N\omega+j)\) is finite or \(D \cap (N\omega+j)\) is finite. Because the sets \(N\omega+0, N\omega+1,\dots,N\omega+N-1\) are disjoint, the first alternative must hold for precisely one of them: i.e., there is some particular \(j < N\) such that \(D \setminus (N\omega+j)\) is finite. If \(n\) is large enough that all members of \(D \setminus (N\omega+j)\) are below \(d_{2n}\), then for \(i \in [d_{2n},d_{2n+1})\) we have \(h(i) = i + d_{2n+2} - d_{2n+1} \equiv_N i\) (because \(d_{2n+2} \equiv_N d_{2n+1}\)); and similarly, for \(i \in [d_{2n+1},d_{2n})\) we have \(h(i) = i - d_{2n+1}+d_{2n} \equiv_N i\) (because \(d_{2n+1} \equiv_N d_{2n}\)). Hence \(h(i) \equiv_N i\) for all sufficiently large \(i\). Consequently, \(\eta([N\omega]) \leq [N\omega]\).

Now fix \(p \in \mathbb{Z}\). If \(p \neq 0\), then for any \(N > p\) we have \((N\omega) \cap (N\omega+p) = \emptyset\) and consequently, \[\sigma^p([N\omega]) \wedge [N\omega] \,=\, [N\omega+p] \wedge [N\omega] \,=\, [(N\omega) \cap (N\omega+p)] \,=\, [\emptyset].\] In particular, \(\sigma^p([N\omega]) \not\leq [N\omega]\). Combined with the previous paragraph, this shows \(\eta([N\omega]) \neq \sigma^p([N\omega])\). Because \([N\omega] \in \mathbb{A}\), this means \(\eta \neq \sigma^p \!\restriction\!\mathbb{A}\).

For the remaining case \(p = 0\), we must find some \(a \in \mathbb{A}\) with \(\eta(a) \neq a\). This is where we use the hypothesis that \([E],[F] \in \mathbb{A}\). Because \(\mathbb{A}\) is closed under \(\sigma^{-1}\), we have \([E-1],[F-1] \in \mathbb{A}\). Because \(E\) and \(F\) partition \(\omega\), and because of our choice of \(D\), exactly one of \(D \cap (E-1)\) and \(D \cap (F-1)\) is finite; equivalently, exactly one of \((D+1) \cap E\) and \((D+1) \cap F\) is finite.

Suppose \((D+1) \cap F\) is finite. Fix \(m\) large enough that \(d_n \in E\) for all \(n \geq m\). There are infinitely many \(n \geq m\) such that \([d_n,d_{n+1}] \not\subseteq E\): this is the case whenever some \(d_n\) is the last member of \(D+1\) in one of the intervals comprising \(E\), and the next member of \(D+1\) is in the next interval of \(E\). When this happens, one of the intervals comprising \(F\) is sandwiched between two consecutive members of \(D+1\). Thus, for infinitely many \(n\), there is an odd \(k\) such that \([2^k,2^{k+1}) \subseteq(d_n,d_{n+1})\).

If \(n\) is odd, then \(h\) shifts the interval \([2^k,2^{k+1})\) down by \(\ell = d_n-d_{n-1} > 0\), so that \(h[F]\) contains, and \(h[E]\) is disjoint from, the interval \([2^k-\ell,2^{k+1}-\ell)\). But \(E\) is not disjoint from any intervals of length \(2^k\) that begin below \(2^k\), so this means there is some \(i \geq 2^k-\ell > d_{n-1}\) with \(i \in E \setminus h[E]\).

If \(n\) is even, then \(h\) shifts \([2^k,2^{k+1})\) up by \(\ell = d_{n+2}-d_{n+1} > 0\), so that \(h[F]\) contains, and \(h[E]\) is disjoint from, the interval \([2^k+\ell,2^{k+1}+\ell)\). But also \(2^k-1,2^{k+1} \in E\), so \(2^k-1+\ell, 2^{k+1}+\ell \in h[E]\). Thus \(h[E]\) contains a gap of length precisely \(2^k\) beginning at \(2^k+\ell > 2^k\). Because every gap in \(E\) beginning above \(2^k\) has length \(>\!2^k\), this means there is some \(i \geq 2^k > d_n\) with \(i \in h[E] \setminus E\).

Put together, the previous two paragraphs show that there are arbitrarily large values of \(i\) that are either in \(E \setminus h[E]\) or in \(h[E] \setminus E\). It follows that \([E] \neq [\left\lbrace h(i) \colon i \in E \right\rbrace] = \eta([E])\). Thus, in the case that \((D+1) \cap F\) is finite, \(\eta\) is not the identity map on \(\mathbb{A}\). A similar argument, interchanging the roles of \(E\) and \(F\), shows that if \([F] \neq \eta([F])\), hence \(\eta\) is not the identity map on \(\mathbb{A}\), in the case that \((D+1) \cap E\) is finite. ◻

Proof. Let \(\langle \mathbb{A},\sigma\rangle\) be a countable elementary substructure of \(\langle\frac{\mathcal{P}(\omega)}{\mathrm{Fin}},\sigma\rangle\) such that \([E],[F] \in \mathbb{A}\). Applying the previous lemma, let \(\eta\) be an embedding of \(\langle \mathbb{A},\sigma\rangle\) into \(\langle \frac{\mathcal{P}(\omega)}{\mathrm{Fin}},\sigma\rangle\) such that \(\eta \neq \sigma^n \!\restriction\!\mathbb{A}\) for any \(n \in \mathbb{Z}\). By Theorem 31, there is a conjugacy map \(\phi\) from \(\langle\frac{\mathcal{P}(\omega)}{\mathrm{Fin}},\sigma\rangle\) to itself such that \(\phi \!\restriction\!\mathbb{A}= \eta\). Thus \(\phi \circ \sigma= \sigma\circ \phi\), but \(\phi \neq \sigma^n\) for any \(n \in \mathbb{Z}\), because \(\phi \!\restriction\!\mathbb{A}= \eta \neq \sigma^n \!\restriction\!\mathbb{A}\) for any \(n \in \mathbb{Z}\). ◻

Proof. Aiming for a contradiction, suppose there is a map \(t: \mathbb{Z}\to \mathbb{Z}\) that induces an automorphism \(\tau\) of \(\frac{\mathcal{P}(\mathbb{Z})}{\mathrm{Fin}}\) with \(\tau\circ \tau= \sigma\), in the sense that \(\tau([A]) = [t(A)]\) for all \(A \subseteq\mathbb{Z}\).

There is some finite \(F \subseteq\mathbb{Z}\) such that \(t \!\restriction\!(\mathbb{Z}\setminus F)\) is injective, since otherwise \(t\) would not induce an automorphism in the manner described in the previous paragraph. Similarly, there is some finite \(G \subseteq\mathbb{Z}\) such that \(t \circ t(n) = n+1\) for all \(n \notin G\). (Otherwise there one can find an infinite \(A \subseteq\mathbb{Z}\) such that \(t \circ t(A) \cap (A+1) = \emptyset\), which means \(\tau\circ \tau([A]) \wedge [A] = [\emptyset]\) and in particular, because \([A] \neq [\emptyset]\), \(\tau\circ \tau([A]) \neq [A]\).)

Let \(n > \max (F \cup G \cup t(F) \cup t^{-1}(F) \cup t^{-1}(G))\). Observe that \(t(n) > \max G\), because \(n > \max ( t^{-1}(G))\).

We claim that \(t^{2k}(n) = n+k\) for all \(k \geq 0\). This is proved by a simple induction on \(k\): the base case is trivial, and assuming it is true for \(k\), then \(t^{2k}(n) = n+k > n > \max G\), and this implies that \(t^{2(k+1)}(n) = t \circ t (t^{2k}(n)) = t^{2k}(n)+1 = n+k+1\). By an essentially identical inductive argument, we also have \(t^{2k+1}(n) = t^{2k}(t(n)) = t(n)+k\) for all \(k \geq 0\).

If \(n < t(n)\), then there is some \(k>0\) such that \(t(n) = n+k = t^{2k}(n)\), and in particular \(t(n) = t(t^{2k-1}(n))\). If \(n > t(n)\), then there is some \(k>0\) such that \(n = t(n)+k = t^{2k+1}(n)\), and in particular, \(t(t^{-1}(n)) = t(t^{2k}(n))\). However, \(n,t^{-1}(n) > \max F\), and \(t^{2k}(n) = n+k, t^{2k-1}(n) = t(n)+k-1 > \max F\), so this contradicts our choice of \(F\). ◻

Proof. Let \(t\) be a bijection on \(\omega\) with one \(\mathbb{Z}\)-like orbit: for concreteness, take \(t(0)=1\), otherwise \(t(2n) = 2n-2\), and \(t(2n+1) = 2n+3\). Let \(\tau\) be the automorphism of \(\frac{\mathcal{P}(\omega)}{\mathrm{Fin}}\) induced by \(t\). Then \(\langle \frac{\mathcal{P}(\omega)}{\mathrm{Fin}},\tau\rangle\) is conjugate to \(\langle \frac{\mathcal{P}(\mathbb{Z})}{\mathrm{Fin}},\sigma\rangle\). Observe that \(\sigma^2\) is the automorphism of \(\frac{\mathcal{P}(\omega)}{\mathrm{Fin}}\) induced by the function \(n \mapsto n+2\) on \(\omega\). This function has two \(\mathbb{N}\)-like orbits. Supposing \(\langle \frac{\mathcal{P}(\omega)}{\mathrm{Fin}},\sigma\rangle\) and \(\langle \frac{\mathcal{P}(\omega)}{\mathrm{Fin}},\sigma^{-1} \rangle\) are conjugate (e.g., under \(\mathsf{CH}\)), it is clear that \(\langle \frac{\mathcal{P}(\omega)}{\mathrm{Fin}},\tau\rangle\) and \(\langle \frac{\mathcal{P}(\omega)}{\mathrm{Fin}},\sigma^2 \rangle\) are also conjugate. Let \(\phi\) be an automorphism of \(\frac{\mathcal{P}(\omega)}{\mathrm{Fin}}\) such that \(\phi \circ \tau= \sigma^2 \circ \phi\). Define \(\zeta= \phi^{-1} \circ \sigma\circ \phi\). Then \[\begin{align} \zeta\circ \zeta&\,=\, \phi^{-1} \circ \sigma\circ \phi \circ \phi^{-1} \circ \sigma\circ \phi \,=\, \phi^{-1} \circ \sigma^2 \circ \phi \,=\, \tau. \end{align}\] Because \(\langle \frac{\mathcal{P}(\omega)}{\mathrm{Fin}},\tau\rangle\) is conjugate to \(\langle \frac{\mathcal{P}(\mathbb{Z})}{\mathrm{Fin}},\sigma\rangle\), this implies via the previous lemma that \(\zeta\) is a nontrivial automorphism of \(\frac{\mathcal{P}(\omega)}{\mathrm{Fin}}\). And \(\langle \frac{\mathcal{P}(\omega)}{\mathrm{Fin}},\sigma\rangle\) is conjugate to \(\langle \frac{\mathcal{P}(\omega)}{\mathrm{Fin}},\zeta\rangle\), because \(\phi \circ \zeta= \sigma\circ \phi\). ◻

Proof. Suppose there is a nontrivial automorphism \(\phi\) of \(\frac{\mathcal{P}(\omega)}{\mathrm{Fin}}\), and let \(\psi = \phi \circ \sigma\circ \phi^{-1}\). Observe that \(\psi\) is an automorphism of \(\frac{\mathcal{P}(\omega)}{\mathrm{Fin}}\), and that \(\langle \frac{\mathcal{P}(\omega)}{\mathrm{Fin}},\psi \rangle\) is conjugate to \(\langle \frac{\mathcal{P}(\omega)}{\mathrm{Fin}},\sigma\rangle\), with \(\phi\) as the conjugacy map, because \[\phi \circ \sigma\,=\, \phi \circ \sigma\circ \phi^{-1} \circ \phi \,=\, \psi \circ \phi.\] If \(\psi\) is nontrivial then the second alternative of the theorem holds, and we are done. So suppose \(\psi\) is trivial. Because \(\langle \frac{\mathcal{P}(\omega)}{\mathrm{Fin}},\sigma\rangle\) is incompressible and \(\langle \frac{\mathcal{P}(\omega)}{\mathrm{Fin}},\psi \rangle\) is conjugate to \(\langle \frac{\mathcal{P}(\omega)}{\mathrm{Fin}},\sigma\rangle\) by the previous paragraph, \(\langle \frac{\mathcal{P}(\omega)}{\mathrm{Fin}},\psi \rangle\) is incompressible. But, up to a bijection on \(\omega\), there are only two incompressible trivial automorphisms of \(\frac{\mathcal{P}(\omega)}{\mathrm{Fin}}\), namely \(\sigma\) and \(\sigma^{-1}\) (see [25]). More precisely, there is a trivial automorphism \(\tau\) of \(\frac{\mathcal{P}(\omega)}{\mathrm{Fin}}\) such that either \(\psi = \tau^{-1} \circ \sigma\circ \tau\), or else \(\psi = \tau^{-1} \circ \sigma^{-1} \circ \tau\). But then \[\phi \circ \sigma\circ \phi^{-1} \,=\, \psi \,=\, \tau^{-1} \circ \sigma^{\pm 1} \circ \tau,\] which implies that \[\sigma\,=\, \phi^{-1} \circ \tau^{-1} \circ \sigma^{\pm 1} \circ \tau\circ \phi \,=\, (\tau\circ \phi)^{-1} \circ \sigma^{\pm 1} \circ (\tau\circ \phi),\] i.e., \(\sigma\) is conjugate to either \(\sigma\) or \(\sigma^{-1}\) via \(\tau\circ \phi\). If \(\sigma\) is conjugate to \(\sigma^{-1}\), then Theorem 36 implies the second alternative of the theorem. If not, then observe that the composition of a trivial and nontrivial automorphism is nontrivial, so \(\tau\circ \phi\) is a nontrivial automorphism commuting with \(\sigma\). ◻