by $\mathcal{C}$, and we abuse notation by denoting this extension also by
$\eta$. This abuse occurs in the statement of $(\dagger)$ in the following
theorem when speaking of the map $\tilde{\eta}\circ\iota$. In general we may
not have $\iota(a)\in\mathcal{B}$ (although we do have
$\iota(a)=\bigvee\left\\{b\in\mathcal{B}\colon b\leq\iota(a)\right\\}$), so
$\tilde{\eta}(\iota(a))$ is only well-defined via this notational abuse.

######  Theorem 8.8.

Suppose
$(\langle\mathbb{A},\alpha\rangle,\langle\mathbb{B},\beta\rangle,\iota,\eta)$
is an instance of the lifting problem for
$\langle\nicefrac{{\mathcal{P}(\omega)}}{{\mathrm{fin}}},\sigma\rangle$. This
instance of the lifting problem has a solution if and only if the following
condition holds:

  * $(\dagger)$

For every partition $\mathcal{A}$ of $\mathbb{A}$ and every partition
$\mathcal{B}$ of $\mathbb{B}$ that refines $\iota[\mathcal{A}]$, there is a
partition $\mathcal{C}$ of $\nicefrac{{\mathcal{P}(\omega)}}{{\mathrm{fin}}}$
refining $\eta[\mathcal{A}]$, and an isomorphism $\tilde{\eta}$ from
$\langle\mathcal{B},\xrightarrow{\scalebox{0.8}{$\,{}_{\beta}\,$}}\rangle$ to
$\langle\mathcal{C},\xrightarrow{\text{\tiny$\,\sigma\,$}}\rangle$ such that
$\tilde{\eta}\circ\iota=\eta$

$\langle\mathcal{A},\xrightarrow{\scalebox{0.9}{$\,{}_{\alpha}\,$}}\rangle$$\langle\mathcal{B},\xrightarrow{\scalebox{0.8}{$\,{}_{\beta}\,$}}\rangle$$\langle\mathcal{C},\xrightarrow{\text{\tiny$\,\sigma\,$}}\rangle$$\iota$$\eta$$\tilde{\eta}$

Roughly, this theorem asserts that
$(\langle\mathbb{A},\alpha\rangle,\langle\mathbb{B},\beta\rangle,\iota,\eta)$
has a solution if and only if every finitary fragment
$(\langle\mathcal{A},\xrightarrow{\scalebox{0.9}{$\,{}_{\alpha}\,$}}\rangle,\langle\mathcal{B},\xrightarrow{\scalebox{0.8}{$\,{}_{\beta}\,$}}\rangle,\iota,\eta)$
of it has a solution.

###### 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{0.8}{$\,{}_{\beta}\,$}}\rangle$ to
$\langle\mathcal{C},\xrightarrow{\text{\tiny$\,\sigma\,$}}\rangle$ by Lemma
8.2, 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 4.10.

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 4.4, 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 4.4.
Furthermore, 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
$\nicefrac{{\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{0.8}{$\,{}_{\beta}\,$}}\rangle$
to $\langle\mathcal{C}_{n},\xrightarrow{\text{\tiny$\,\sigma\,$}}\rangle$ such
that $\tilde{\eta}_{n}\circ\iota=\eta$. Applying Lemma 8.7, 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{0.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 plane 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\nicefrac{{\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 8.1. Define a function
$\chi:[\omega]^{2}\to\omega$ as follows. For every $k,\ell\in\omega$ with
$k<\ell$, define

$\displaystyle\chi(k,\ell)=\sup\left\\{j\leq
k\colon\beta(b^{k}_{n})\approx_{\mathcal{B}_{j}}b^{\ell}_{n+1}\text{ for
infinitely many }n\right\\}.$

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 longs 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 4.10 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, this function $\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 $j^{\prime}$ be large enough that
$\mathcal{B}_{j^{\prime}}$ refines the partition generated by
$\mathcal{B}_{j}\cup\left\\{\beta(b)\colon b\in\mathcal{B}_{j}\right\\}$. We
claim that $|C|\leq|\mathcal{B}_{j^{\prime}}|+1$. Aiming for a contradiction,
let $J=|\mathcal{B}_{j^{\prime}}|$ and suppose that $|C|>J+1$. For every
$b\in\mathbb{B}$ that is below $\mathcal{B}_{j^{\prime}}$, let
$\pi_{j^{\prime}}(b)$ denote the (unique) member of $\mathcal{B}_{j^{\prime}}$
with $b\leq\pi_{j^{\prime}}(b)$. Because $k\geq{j^{\prime}}-1$ for all $k\in
C$ (by our definition of $\chi$), this means there are distinct points
$k_{0},k_{1},\dots,k_{J}\in C$ such that $k_{i}\geq{j^{\prime}}$ for all
$i\leq J$. For any given $k\geq{j^{\prime}}$ and any $n$, there are only
$|\mathcal{B}_{j^{\prime}}|=J$ possibilities for
$\pi_{j^{\prime}}(b^{k}_{n})$. In particular, by the pigeonhole principle, at
least two of the $\pi_{j^{\prime}}(b^{k_{i}}_{n})$ (where $0\leq i\leq J$)
must be the same for every $n$. Consequently, there are some $i,i^{\prime}\leq
J$ such that $\pi_{j}(b^{k_{i}}_{n})$ and
$\pi_{j^{\prime}}(b^{k_{i^{\prime}}}_{n})$ are the same infinitely often. But
(assuming without loss of generality that $i<i^{\prime}$), this implies
$\pi_{j^{\prime}}(b^{k_{i}}_{n})\xrightarrow{\scalebox{0.8}{$\,{}_{\beta}\,$}}\pi_{j^{\prime}}(b^{k_{i^{\prime}}}_{n+1})$
for infinitely many $n$, because
$\pi_{j^{\prime}}(b^{k_{i^{\prime}}}_{n})\xrightarrow{\scalebox{0.8}{$\,{}_{\beta}\,$}}\pi_{j^{\prime}}(b^{k_{i^{\prime}}}_{n+1})$
for any $n$ and
$\pi_{j^{\prime}}(b^{k_{i}}_{n+1})=\pi_{j^{\prime}}(b^{k_{i^{\prime}}}_{n+1})$.
By our choice of $j^{\prime}$,
$\pi_{j^{\prime}}(b^{k_{i}}_{n})\xrightarrow{\scalebox{0.8}{$\,{}_{\beta}\,$}}\pi_{j^{\prime}}(b^{k_{i^{\prime}}}_{n+1})$
implies
$\beta(b^{k_{i}}_{n})\approx_{\mathcal{B}_{j}}b^{k_{i^{\prime}}}_{n+1}$ Thus
$\beta(b^{k_{i}}_{n})\approx_{\mathcal{B}_{j}}b^{k_{i^{\prime}}}_{n+1}$ for
infinitely many $n$, which means $\chi(k_{i},k_{i^{\prime}})>j$, a
contradiction.

As all the monochromatic cliques for $\chi$ are finite, Lemma 8.1 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. Let $J_{0}=0$, and given some $J_{k}$, $k\in\omega$,
choose $J_{k+1}$ such that

  * $\circ$

$J_{k+1}>J_{k}$,

  * $\circ$

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$,

  * $\circ$

$\beta\big{(}b^{n_{k}}_{J_{k}-1}\big{)}\approx_{\mathcal{B}_{k}}b^{n_{k+1}}_{J_{k}}$.

To see that some such $J_{k+1}$ exists: the first condition is satisfied by
all sufficiently large choices of $J_{k+1}$; the second condition is as well,
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 third condition is
satisfied infinitely often, because $\chi(n_{k},n_{k+1})>k$.

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 $b\in\mathcal{B}$, if $k$ is sufficiently large then there
is some $d_{i}\leq b$ with $J_{k}\leq i<J_{k+1}$.

Finally, 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\\{\beta(b)\colon b\in\mathcal{V}\right\\}$.
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{0.8}{$\,{}_{\beta}\,$}}\rangle$,
and so has
$b^{k}_{j}\xrightarrow{\scalebox{0.8}{$\,{}_{\beta}\,$}}b^{k}_{j+1}$ for all
$j$. Thus $d_{i}\xrightarrow{\scalebox{0.8}{$\,{}_{\beta}\,$}}b_{i+1}$. If
$k\geq K$, then this implies $\beta(d_{i})\approx_{\mathcal{V}}d_{i+1}$. Thus
$\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 third condition
listed above in our definition of the $J_{k}$. Because $\ell\geq K$,
$\mathcal{B}_{\ell}$ refines $\mathcal{V}$, and this 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 4.10, $\left\langle d_{i}\colon i\in\omega\right\rangle$
induces an embedding of $\langle\mathbb{B},\beta\rangle$ into
$\langle\nicefrac{{\mathcal{P}(\omega)}}{{\mathrm{fin}}},\sigma\rangle$. Call
this embedding $\bar{\eta}$. We claim that $\bar{\eta}$ is a lifting of
$\eta$.

Fix $a\in\mathbb{A}$. There is some $k\in\omega$ such that $\mathcal{A}_{k}$
refines $\\{a,\mathbf{1}-a\\}$, and this implies
$a=\bigvee\left\\{c\in\mathcal{A}_{k}\colon c\leq a\right\\}$. In fact
$a=\bigvee\left\\{c\in\mathcal{A}_{\ell}\colon c\leq a\right\\}$ for all
$\ell\geq k$ because $\mathcal{A}_{\ell}$ refines $\mathcal{A}_{k}$. If
$\ell\geq k$, then $\mathcal{B}_{\ell}$ refines $\iota[\mathcal{A}_{\ell}]$,
and thus if $d\in\mathcal{B}_{\ell}$ then
$\iota(a)=\bigvee\left\\{d\in\mathcal{B}_{\ell}\colon d\leq\iota(a)\right\\}$.
Consequently, for all $\ell\geq k$,

$\eta(a)\,=\,\tilde{\eta}_{\ell}\circ\iota(a)\,=\,\tilde{\eta}_{\ell}(\iota(a))\,=\,[\\{i:\,b^{\ell}_{i}\leq\iota(a)\\}].$

But if $i\geq J_{k}$, then $d_{i}=\pi_{\ell}(b^{n_{\ell}}_{i})$ for some
$\ell\geq k$, and it follows that $\left\\{i\geq
J_{k}\colon\pi_{\ell}(b^{n_{\ell}}_{i})\leq\iota(a)\right\\}=\left\\{i\geq
J_{k}\colon b^{n_{\ell}}_{i}\leq\iota(a)\right\\}$. Therefore

$\eta(a)\,=\,[\\{i:\,b^{\ell}_{i}\leq\iota(a)\\}]\,=\,[\left\\{i\colon
d_{i}\leq\iota(a)\right\\}]\,=\,\bar{\eta}(\iota(a)).$

(This last equality applies the abuse of notation mentioned before the
statement of the theorem.) As $a$ was arbitrary, this shows
$\eta=\bar{\eta}\circ\iota$ as claimed. ∎

Of course, one could prove an analogous result concerning the lifting problem
for
$\langle\nicefrac{{\mathcal{P}(\omega)}}{{\mathrm{fin}}},\sigma^{-1}\rangle$.
However, we have no need to do so. The purpose of Theorem 8.8 is that it
brings us one step closer to proving the Lifting Lemma. We have already proved
that an “inverse” version of the Lifting Lemma (Lemma 6.3) follows from the
original version, so there is no need for an inverse version of Theorem 8.8.

The main theorem of [4] (translated from the topological to the algebraic
category) states that every incompressible dynamical system of size
$\leq\\!\aleph_{1}$ embeds in
$\langle\nicefrac{{\mathcal{P}(\omega)}}{{\mathrm{fin}}},\sigma\rangle$ and in
$\langle\nicefrac{{\mathcal{P}(\omega)}}{{\mathrm{fin}}},\sigma^{-1}\rangle$.
To end this section, we derive this theorem as a relatively straightforward
consequence of Theorem 8.8. In addition to giving an interesting application
of Theorem 8.8, the proof also shows how elementarity can be used to achieve a
version of Theorem 2.3 in the dynamical category. This is similar to the proof
of our main theorem, which shows how elementarity can be used to achieve a
version of Theorem 2.4 in the dynamical category. The remainder of this
section is not part of the proof of the Lifting Lemma, and the reader who
wishes to may skip them without losing the thread of the argument.

######  Lemma 8.9.

Suppose
$(\langle\mathbb{A},\alpha\rangle,\langle\mathbb{B},\beta\rangle,\iota,\eta)$
is an instance of the lifting problem for
$\langle\nicefrac{{\mathcal{P}(\omega)}}{{\mathrm{fin}}},\sigma\rangle$. If
$\iota$ is an elementary embedding of $\langle\mathbb{A},\alpha\rangle$ into
$\langle\mathbb{B},\beta\rangle$, then condition $(\dagger)$ from Theorem 8.8
is satisfied, and this instance of the lifting problem has a solution.

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

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:

  * $\circ$

$\bigvee\mathcal{B}=\mathbf{1}$ and $b\wedge b^{\prime}=\mathbf{0}$ whenever
$b,b^{\prime}\in\mathcal{B}$ and $b\neq b^{\prime}$,

  * $\circ$

$\bigvee\iota[\mathcal{A}]=\mathbf{1}$ and $b\wedge b^{\prime}=\mathbf{0}$
whenever $b,b^{\prime}\in\iota[\mathcal{A}]$ and $b\neq b^{\prime}$,

  * $\circ$

$b\xrightarrow{\scalebox{0.8}{$\,{}_{\beta}\,$}}b^{\prime}$ for some
$b,b^{\prime}\in\mathcal{B}$ or some $b,b^{\prime}\in\iota[\mathcal{A}]$,

  * $\circ$

$\neg(b\xrightarrow{\scalebox{0.8}{$\,{}_{\beta}\,$}}b^{\prime})$ for some
$b,b^{\prime}\in\mathcal{B}$ or some $b,b^{\prime}\in\iota[\mathcal{A}]$,

  * $\circ$

$b\leq b^{\prime}$ for some $b\in\mathcal{B}$ and
$b^{\prime}\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{0.8}{$\,{}_{\beta}\,$}}\rangle$ and
$\langle\iota[\mathcal{A}],\xrightarrow{\scalebox{0.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 a true
assertion about $\langle\mathbb{B},\beta\rangle$.

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\nicefrac{{\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{0.9}{$\,{}_{\alpha}\,$}}\rangle$
is isomorphic to
$\langle\mathcal{B},\xrightarrow{\scalebox{0.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
$\nicefrac{{\mathcal{P}(\omega)}}{{\mathrm{fin}}}$, and $\eta$ is an
isomorphism from
$\langle\tilde{B},\xrightarrow{\scalebox{0.9}{$\,{}_{\alpha}\,$}}\rangle$ to
$\langle\eta[\tilde{\mathcal{B}}],\xrightarrow{\text{\tiny$\,\sigma\,$}}\rangle$
by Lemma 8.2. It follows that $\tilde{\eta}$ is an isomorphism from
$\langle\mathcal{B},\xrightarrow{\scalebox{0.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}$. ∎

######  Theorem 8.10.

Every incompressible dynamical system of size $\aleph_{1}$ embeds in
$\langle\nicefrac{{\mathcal{P}(\omega)}}{{\mathrm{fin}}},\sigma\rangle$ and in
$\langle\nicefrac{{\mathcal{P}(\omega)}}{{\mathrm{fin}}},\sigma^{-1}\rangle$.

###### Proof.

We prove the theorem first for
$\langle\nicefrac{{\mathcal{P}(\omega)}}{{\mathrm{fin}}},\sigma\rangle$. Every
countable incompressible dynamical system embeds in
$\langle\nicefrac{{\mathcal{P}(\omega)}}{{\mathrm{fin}}},\sigma\rangle$ by
Theorem 7.9, so it suffices to consider systems of size $\aleph_{1}$. Let
$\langle\mathbb{A},\alpha\rangle$ be an incompressible dynamical system with
$\left\lvert\mathbb{A}\right\rvert\leq\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

  * $\circ$

$\langle\mathbb{A}_{\beta},\alpha\rangle$ is an elementary substructure of
$\langle\mathbb{A},\alpha\rangle$ for all $\beta<\omega_{1}$,

  * $\circ$

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

  * $\circ$

$\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\nicefrac{{\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\nicefrac{{\mathcal{P}(\omega)}}{{\mathrm{fin}}},\sigma\rangle$. (Some
such embedding exists by Theorem 7.9, 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\nicefrac{{\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\nicefrac{{\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\nicefrac{{\mathcal{P}(\omega)}}{{\mathrm{fin}}},\sigma\rangle$, and
furthermore $\iota$ is an elementary embedding. By Lemma 8.9, there is an
embedding $\eta_{\gamma}$ from $\langle\mathbb{A}_{\gamma},\alpha\rangle$ into
$\langle\nicefrac{{\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\nicefrac{{\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\nicefrac{{\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^{\prime}$ from
$\langle\mathbb{A},\alpha^{-1}\rangle$ into
$\langle\nicefrac{{\mathcal{P}(\omega)}}{{\mathrm{fin}}},\sigma\rangle$. But
this implies that $\eta^{\prime}$ is also an embedding from
$\langle\mathbb{A},\alpha\rangle$ into
$\langle\nicefrac{{\mathcal{P}(\omega)}}{{\mathrm{fin}}},\sigma^{-1}\rangle$.
∎

######  Corollary 8.11.

Assuming the Continuum Hypothesis,
$\langle\nicefrac{{\mathcal{P}(\omega)}}{{\mathrm{fin}}},\sigma\rangle$ embeds
in
$\langle\nicefrac{{\mathcal{P}(\omega)}}{{\mathrm{fin}}},\sigma^{-1}\rangle$
and vice versa.

###### Proof.

This follows from Theorem 8.10, because $\mathsf{CH}$ implies
$\left\lvert\nicefrac{{\mathcal{P}(\omega)}}{{\mathrm{fin}}}\right\rvert=\aleph_{1}$,
and both
$\langle\nicefrac{{\mathcal{P}(\omega)}}{{\mathrm{fin}}},\sigma\rangle$ and
$\langle\nicefrac{{\mathcal{P}(\omega)}}{{\mathrm{fin}}},\sigma^{-1}\rangle$
are incompressible. ∎

As noted in the introduction, the conclusion of this corollary is independent
of $\mathsf{ZFC}$: assuming $\mathsf{OCA+MA}$, there is no embedding from
$\langle\nicefrac{{\mathcal{P}(\omega)}}{{\mathrm{fin}}},\sigma\rangle$ into
$\langle\nicefrac{{\mathcal{P}(\omega)}}{{\mathrm{fin}}},\sigma^{-1}\rangle$
or from
$\langle\nicefrac{{\mathcal{P}(\omega)}}{{\mathrm{fin}}},\sigma^{-1}\rangle$
into $\langle\nicefrac{{\mathcal{P}(\omega)}}{{\mathrm{fin}}},\sigma\rangle$.
This was proved in [4] as a relatively straightforward corollary to the
extensive work of Farah in [9] on how $\mathsf{OCA+MA}$ restricts the
continuous self-maps of $\omega^{*}$.

##  9\. The Lifting Lemma, part 4: realization or incompatibility

The Lifting Lemma guarantees that an instance
$(\langle\mathbb{A},\alpha\rangle,\langle\mathbb{B},\beta\rangle,\iota,\eta)$
of the lifting problem has a solution assuming the image of
$\langle\mathbb{A},\alpha\rangle$ under $\eta$ is an elementary substructure
of $\langle\nicefrac{{\mathcal{P}(\omega)}}{{\mathrm{fin}}},\sigma\rangle$.
Note that this puts no conditions whatsoever on the embedding $\iota$. This
lack of conditions on $\iota$ (how $\mathbb{A}$ sits inside of $\mathbb{B}$)
seems necessary, because in the proof of Theorem 6.4 our back-and-forth
argument gives us no control over the $\iota$’s that arise over the course of
the recursion: we only control the $\langle\mathbb{A},\alpha\rangle$’s. In the
previous section we formulated a condition $(\dagger)$ that is necessary and
sufficient for a solution to the lifting problem. In this section we use
$(\dagger)$ to provide a different sufficient condition (called
“polarization”) for the existence of a solution, one that makes no mention of
$\iota$ but relies solely on the structure of
$\langle\mathbb{A},\alpha\rangle$. The two sections after this one are then
devoted to showing that elementary substructures of
$\langle\nicefrac{{\mathcal{P}(\omega)}}{{\mathrm{fin}}},\sigma\rangle$ are
polarized, so that the hypotheses of the Lifting Lemma actually imply
$\langle\mathbb{A},\alpha\rangle$ has this property.

######  Definition 9.1.

Let $\langle\mathbb{A},\alpha\rangle$ be an incompressible dynamical system
and let $\mathcal{A}$ be a partition of $\mathbb{A}$. A _virtual refinement_
of $\langle\mathcal{A},\xrightarrow{\scalebox{0.9}{$\,{}_{\alpha}\,$}}\rangle$
is a pair $(\phi,\langle\mathcal{V},\to\rangle)$, where
$\langle\mathcal{V},\to\rangle$ is a strongly connected digraph and $\phi$ is
an epimorphism from $\langle\mathcal{V},\to\rangle$ to
$\langle\mathcal{A},\xrightarrow{\scalebox{0.9}{$\,{}_{\alpha}\,$}}\rangle$.

A partition $\mathcal{A}^{\prime}$ of $\mathbb{A}$ _realizes_
$(\phi,\langle\mathcal{V},\to\rangle)$ if $\mathcal{A}^{\prime}$ refines
$\mathcal{A}$ and there is an isomorphism $\phi^{\prime}$ from
$\langle\mathcal{V},\to\rangle$ to
$\langle\mathcal{A}^{\prime},\xrightarrow{\scalebox{0.9}{$\,{}_{\alpha}\,$}}\rangle$
such that $\pi\circ\phi^{\prime}=\phi$, where $\pi$ is the natural map from
$\mathcal{A}^{\prime}$ to $\mathcal{A}$. ☕

The following lemma says virtual refinements generalize actual refinements.
This lemma has Lemma 7.4 as a special case (by taking
$\iota=\mathrm{id}_{\mathbb{A}}$).

######  Lemma 9.2.

Suppose $\langle\mathbb{A},\alpha\rangle$ and $\langle\mathbb{B},\beta\rangle$
are dynamical systems, and $\iota$ is an embedding of
$\langle\mathbb{A},\alpha\rangle$ into $\langle\mathbb{B},\beta\rangle$. Given
a partition $\mathcal{A}$ of $\mathbb{A}$ and any partition $\mathcal{B}$ of
$\mathbb{B}$ that refines $\iota[\mathcal{A}]$, define the map

$\phi(b)\,=\,\text{the unique member of $\mathcal{A}$ with }b\leq\iota(a).$

Then
$(\phi,\langle\mathcal{B},\xrightarrow{\scalebox{0.8}{$\,{}_{\beta}\,$}}\rangle)$
is a virtual refinement of
$\langle\mathcal{A},\xrightarrow{\scalebox{0.9}{$\,{}_{\alpha}\,$}}\rangle$.

###### 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^{\prime}\in\mathcal{A}$ and
$a\xrightarrow{\scalebox{0.9}{$\,{}_{\alpha}\,$}}a^{\prime}$, then
$\iota(a)\xrightarrow{\scalebox{0.8}{$\,{}_{\beta}\,$}}\iota(a^{\prime})$
(because $\iota$ is an embedding), and this implies that
$b\xrightarrow{\scalebox{0.8}{$\,{}_{\beta}\,$}}b^{\prime}$ for some
$b\leq\iota(a)$ and $b^{\prime}\leq\iota(a^{\prime})$. In other words, there
are $b,b^{\prime}\in\mathcal{B}$ such that $\phi(b)=a$,
$\phi(b^{\prime})=a^{\prime}$, and
$b\xrightarrow{\scalebox{0.8}{$\,{}_{\beta}\,$}}b^{\prime}$. On the other
hand, it is clear that
$b\xrightarrow{\scalebox{0.8}{$\,{}_{\beta}\,$}}b^{\prime}$ implies
$\phi(b)\xrightarrow{\scalebox{0.9}{$\,{}_{\alpha}\,$}}\phi(b^{\prime})$. ∎

Henceforth, if the conditions of this lemma hold then the function

$\phi(b)\,=\,\text{the unique member of $\mathcal{A}$ with }b\leq\iota(a)$

is called the _natural epimorphism_ from
$\langle\mathcal{B},\xrightarrow{\scalebox{0.8}{$\,{}_{\beta}\,$}}\rangle$
onto
$\langle\mathcal{A},\xrightarrow{\scalebox{0.9}{$\,{}_{\alpha}\,$}}\rangle$.

######  Definition 9.3.

Let
$\langle\mathcal{A},\xrightarrow{\scalebox{0.75}{$\,{}_{\mathcal{A}}\,$}}\rangle$,
$\langle\mathcal{U},\xrightarrow{\scalebox{0.75}{$\,{}_{\mathcal{U}}\,$}}\rangle$,
and
$\langle\mathcal{V},\xrightarrow{\scalebox{0.75}{$\,{}_{\mathcal{V}}\,$}}\rangle$
be strongly connected digraphs, and suppose that $\phi$ and $\psi$ are
epimorphisms from
$\langle\mathcal{U},\xrightarrow{\scalebox{0.75}{$\,{}_{\mathcal{U}}\,$}}\rangle$
onto
$\langle\mathcal{A},\xrightarrow{\scalebox{0.75}{$\,{}_{\mathcal{A}}\,$}}\rangle$
and from
$\langle\mathcal{V},\xrightarrow{\scalebox{0.75}{$\,{}_{\mathcal{V}}\,$}}\rangle$
onto
$\langle\mathcal{A},\xrightarrow{\scalebox{0.75}{$\,{}_{\mathcal{A}}\,$}}\rangle$,
respectively. These two epimorphisms are _compatible_ if there is a strongly
connected digraph
$\langle\mathcal{W},\xrightarrow{\scalebox{0.75}{$\,{}_{\mathcal{W}}\,$}}\rangle$,
and there are epimorphisms $\bar{\phi}$ and $\bar{\psi}$ from
$\langle\mathcal{W},\xrightarrow{\scalebox{0.75}{$\,{}_{\mathcal{W}}\,$}}\rangle$
onto
$\langle\mathcal{U},\xrightarrow{\scalebox{0.75}{$\,{}_{\mathcal{U}}\,$}}\rangle$
and
$\langle\mathcal{V},\xrightarrow{\scalebox{0.75}{$\,{}_{\mathcal{V}}\,$}}\rangle$,
respectively, such that $\phi\circ\bar{\phi}=\psi\circ\bar{\psi}$.

$\langle\mathcal{A},\xrightarrow{\scalebox{0.75}{$\,{}_{\mathcal{A}}\,$}}\rangle$$\langle\mathcal{U},\xrightarrow{\scalebox{0.75}{$\,{}_{\mathcal{U}}\,$}}\rangle$$\langle\mathcal{V},\xrightarrow{\scalebox{0.75}{$\,{}_{\mathcal{V}}\,$}}\rangle$$\langle\mathcal{W},\xrightarrow{\scalebox{0.75}{$\,{}_{\mathcal{W}}\,$}}\rangle$$\psi$$\phi$$\bar{\psi}$$\bar{\phi}$

Otherwise $\phi$ and $\psi$ are _incompatible_. By extension, if
$\langle\mathbb{A},\alpha\rangle$ is a dynamical system and $\mathcal{A}$ is a
partition of $\mathbb{A}$, then two virtual refinements
$(\phi,\langle\mathcal{U},\xrightarrow{\scalebox{0.75}{$\,{}_{\mathcal{U}}\,$}}\rangle)$
and
$(\psi,\langle\mathcal{V},\xrightarrow{\scalebox{0.75}{$\,{}_{\mathcal{V}}\,$}}\rangle)$
of $\langle\mathcal{A},\xrightarrow{\scalebox{0.9}{$\,{}_{\alpha}\,$}}\rangle$
are (in)compatible if the epimorphisms $\phi$ and $\psi$ are (in)compatible. ☕

Note the requirement in this definition that
$\langle\mathcal{W},\xrightarrow{\scalebox{0.75}{$\,{}_{\mathcal{W}}\,$}}\rangle$
be strongly connected. Without this requirement, any two digraphs would be
compatible: just take
$\langle\mathcal{W},\xrightarrow{\scalebox{0.75}{$\,{}_{\mathcal{W}}\,$}}\rangle$
to be a product of
$\langle\mathcal{U},\xrightarrow{\scalebox{0.75}{$\,{}_{\mathcal{U}}\,$}}\rangle$
and
$\langle\mathcal{V},\xrightarrow{\scalebox{0.75}{$\,{}_{\mathcal{V}}\,$}}\rangle$,
with $\bar{\phi}$ and $\bar{\psi}$ being the standard projections. (There are
several different ways to define the product of two digraphs, and just about
any of them works for this.) However, the product of two strongly connected
digraphs need not be strongly connected, so a product of
$\langle\mathcal{U},\xrightarrow{\scalebox{0.75}{$\,{}_{\mathcal{U}}\,$}}\rangle$
and
$\langle\mathcal{V},\xrightarrow{\scalebox{0.75}{$\,{}_{\mathcal{V}}\,$}}\rangle$
may not be eligible to witness compatibility in the sense of Definition 9.3.

######  Lemma 9.4.

Suppose $\langle\mathbb{A},\alpha\rangle$ and $\langle\mathbb{B},\beta\rangle$
are dynamical systems, and $\iota$ is an embedding of
$\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}$ refining $\iota[\mathcal{A}]$. Then for any
partition $\mathcal{A}^{\prime}$ of $\mathbb{A}$ refining $\mathcal{A}$, the
natural map from
$\langle\mathcal{A}^{\prime},\xrightarrow{\scalebox{0.9}{$\,{}_{\alpha}\,$}}\rangle$
to $\langle\mathcal{A},\xrightarrow{\scalebox{0.9}{$\,{}_{\alpha}\,$}}\rangle$
and the natural epimorphism from
$\langle\mathcal{B},\xrightarrow{\scalebox{0.8}{$\,{}_{\beta}\,$}}\rangle$ to
$\langle\mathcal{A},\xrightarrow{\scalebox{0.9}{$\,{}_{\alpha}\,$}}\rangle$
are compatible.

###### Proof.

Let $\mathcal{B}^{\prime}$ be any partition of $\mathbb{B}$ refining both
$\mathcal{B}$ and $\iota[\mathcal{A}^{\prime}]$. We claim that the digraph
$\langle\mathcal{B}^{\prime},\xrightarrow{\scalebox{0.8}{$\,{}_{\beta}\,$}}\rangle$,
along with the appropriate natural epimorphisms, witnesses the
$p$-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}^{\prime}$
to $\mathcal{A}$, and let $\psi$ denote the natural epimorphism from
$\langle\mathcal{B},\xrightarrow{\scalebox{0.8}{$\,{}_{\beta}\,$}}\rangle$
onto
$\langle\mathcal{A},\xrightarrow{\scalebox{0.9}{$\,{}_{\alpha}\,$}}\rangle$.
Let $\bar{\phi}$ denote the natural epimorphism from
$\langle\mathcal{B}^{\prime},\xrightarrow{\scalebox{0.8}{$\,{}_{\beta}\,$}}\rangle$
onto
$\langle\mathcal{A}^{\prime},\xrightarrow{\scalebox{0.9}{$\,{}_{\alpha}\,$}}\rangle$
and let $\bar{\psi}$ denote the natural map from $\mathcal{B}^{\prime}$ 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}^{\prime}\to\mathcal{A}$ given by

$b\,\mapsto\,\text{the unique member of $\mathcal{A}$ with }b\leq\iota(a),$

in other words, the natural epimorphism from
$\langle\mathcal{B}^{\prime},\xrightarrow{\scalebox{0.8}{$\,{}_{\beta}\,$}}\rangle$
onto
$\langle\mathcal{A},\xrightarrow{\scalebox{0.9}{$\,{}_{\alpha}\,$}}\rangle$. ∎

In other words, this lemma states that a virtual refinement of
$\langle\mathcal{A},\xrightarrow{\scalebox{0.9}{$\,{}_{\alpha}\,$}}\rangle$
that comes from an embedding (in the way that
$\langle\mathcal{B},\xrightarrow{\scalebox{0.8}{$\,{}_{\beta}\,$}}\rangle$
does in the statement of the lemma) is always compatible with actual
refinements of $\mathcal{A}$.

Similarly, when two virtual refinements come from embeddings that form a
commutative triangle, in the sense of the lifting problem for
$\langle\nicefrac{{\mathcal{P}(\omega)}}{{\mathrm{fin}}},\sigma\rangle$ and
Lemma 6.2, then the two corresponding virtual refinements are compatible:

######  Observation 9.5.

Suppose $\langle\mathbb{A},\alpha\rangle$, $\langle\mathbb{B},\beta\rangle$,
and $\langle\mathbb{C},\gamma\rangle$ are dynamical systems, and $\iota$ and
$\eta$ are embeddings of $\langle\mathbb{A},\alpha\rangle$ into
$\langle\mathbb{B},\beta\rangle$ and $\langle\mathbb{C},\gamma\rangle$,
respectively. Let $\mathcal{A}$ be a partition of $\mathbb{A}$, let
$\mathcal{B}$ be a partition of $\mathbb{B}$ refining $\iota[\mathcal{A}]$,
and let $\mathcal{C}$ be a partition of $\mathbb{C}$ refining
$\eta[\mathcal{A}]$. If there is an embedding $\bar{\eta}$ from
$\langle\mathbb{B},\beta\rangle$ to $\langle\mathbb{C},\gamma\rangle$ with
$\bar{\eta}\circ\iota=\eta$, then the natural epimorphisms from
$\langle\mathcal{B},\xrightarrow{\scalebox{0.8}{$\,{}_{\beta}\,$}}\rangle$ to
$\langle\mathcal{A},\xrightarrow{\scalebox{0.9}{$\,{}_{\alpha}\,$}}\rangle$
and from
$\langle\mathcal{C},\xrightarrow{\scalebox{0.8}{$\,{}_{\gamma}\,$}}\rangle$ to
$\langle\mathcal{A},\xrightarrow{\scalebox{0.9}{$\,{}_{\alpha}\,$}}\rangle$
are compatible.

###### Proof.

Let $\mathcal{C}^{\prime}$ be a partition of $\mathbb{C}$ that refines all
three of $\mathcal{C}$, $\bar{\eta}[\mathcal{B}]$, and
$\eta[\mathcal{A}^{p}]$. Let $\bar{\phi}$ be the natural epimorphism (induced
by $\bar{\eta}$) from
$\langle\mathcal{C}^{\prime},\xrightarrow{\scalebox{0.8}{$\,{}_{\gamma}\,$}}\rangle$
to $\langle\mathcal{B},\xrightarrow{\scalebox{0.8}{$\,{}_{\beta}\,$}}\rangle$.
Let $\bar{\psi}$ be the natural projection
$\mathcal{C}^{\prime}\to\mathcal{C}$.

Just as in the proof of Lemma 9.4,
$\langle\mathcal{C}^{\prime},\xrightarrow{\scalebox{0.8}{$\,{}_{\gamma}\,$}}\rangle$,
along with these various maps, witnesses compatibility. As before, this works
essentially because the composition of natural maps, when defined, is another
natural map. ∎

This observation suggests one reason that an instance
$(\langle\mathbb{A},\alpha\rangle,\langle\mathbb{B},\beta\rangle,\iota,\eta)$
of the lifting problem for
$\langle\nicefrac{{\mathcal{P}(\omega)}}{{\mathrm{fin}}},\sigma\rangle$ might
fail to have a solution: the reason could be that there are partitions
$\mathcal{A}$, $\mathcal{B}$, and $\mathcal{C}$ of $\mathbb{A}$, $\mathbb{B}$,
and $\nicefrac{{\mathcal{P}(\omega)}}{{\mathrm{fin}}}$ such that (together
with the natural maps corresponding to $\iota$ and $\eta$) the digraphs
$\langle\mathcal{B},\xrightarrow{\scalebox{0.8}{$\,{}_{\beta}\,$}}\rangle$ and
$\langle\mathcal{C},\xrightarrow{\text{\tiny$\,\sigma\,$}}\rangle$ are
incompatible virtual refinements of
$\langle\mathcal{A},\xrightarrow{\scalebox{0.9}{$\,{}_{\alpha}\,$}}\rangle$.

Indeed, this is precisely what happens in the proof of Theorem 5.1. Let
$\langle\mathbb{A},\alpha\rangle$ and $\langle\mathbb{B},\beta\rangle$ denote
the dynamical systems constructed there. There is a partition $\mathcal{A}$ of
$\mathbb{A}$ such that the digraph
$\langle\mathcal{A},\xrightarrow{\scalebox{0.9}{$\,{}_{\alpha}\,$}}\rangle$
looks like this:

$U$$V$$W$

There is a partition of $\mathbb{B}$ that refines $\iota[\mathcal{A}]$
(separating the points $a$, $b$, $c$, and $d$ into four disjoint clopen sets)
with the following picture:

$\bullet$$\bullet$$\bullet$$\bullet$

Finally, consider the embedding $\eta$ of $\langle\mathbb{A},\alpha\rangle$
into $\langle\nicefrac{{\mathcal{P}(\omega)}}{{\mathrm{fin}}},\sigma\rangle$
described in the proof of Theorem 5.1. This embedding is described via an
eventually small, eventually dense sequence $\left\langle a_{n}\colon
n\in\omega\right\rangle$ in $\mathbb{A}$. Consider the following partition of
$\omega$ (where $U$, $V$, and $W$ refer to the members of $\mathcal{A}$):

$A\,=\,\left\\{n\in\omega\colon a_{n}\in U\right\\},\ \
B\,=\,\left\\{n\in\omega\colon a_{n}\in W\right\\},$
$C\,=\,\left\\{n\in\omega\colon a_{n}\in V\text{ and if $m>n$ is minimal with
$a_{m}\notin V$, }a_{m}\in W\right\\},$ $D\,=\,\left\\{n\in\omega\colon
a_{n}\in V\text{ and if $m>n$ is minimal with $a_{m}\notin V$, }a_{m}\in
U\right\\}.$

This partition of $\nicefrac{{\mathcal{P}(\omega)}}{{\mathrm{fin}}}$ refines
$\eta[\mathcal{A}]$ and is pictured as follows:

$A$$B$$C$$D$$\bullet$$\bullet$$\bullet$$\bullet$

Thus we have two different virtual refinements of
$\langle\mathcal{A},\xrightarrow{\scalebox{0.9}{$\,{}_{\alpha}\,$}}\rangle$,
arising from these partitions $\mathcal{B}$ and $\mathcal{C}$ of $\mathbb{B}$
and $\nicefrac{{\mathcal{P}(\omega)}}{{\mathrm{fin}}}$, respectively, and
their associated natural epimorphisms:

$\bullet$$\bullet$$\bullet$$\bullet$$\bullet$$\bullet$$\bullet$$\bullet$

These two refinements are incompatible. (Why? Let $m$ denote the higher of the
two vertices in the middle of $\mathcal{B}$, and let $r$ denote the vertex on
the right of $\mathcal{B}$. Suppose, aiming for a contradiction, that
$\langle\mathcal{W},\xrightarrow{\scalebox{0.75}{$\,{}_{\mathcal{W}}\,$}}\rangle$,
$\bar{\phi}$, and $\bar{\psi}$ witness the compatibility of
$\langle\mathcal{B},\xrightarrow{\scalebox{0.8}{$\,{}_{\beta}\,$}}\rangle$ and
$\langle\mathcal{C},\xrightarrow{\text{\tiny$\,\sigma\,$}}\rangle$. Because
$\bar{\phi}$ is surjective, $\bar{\phi}^{-1}(m)\neq\emptyset$ and
$\bar{\phi}^{-1}(r)\neq\emptyset$. Because
$\langle\mathcal{W},\xrightarrow{\scalebox{0.75}{$\,{}_{\mathcal{W}}\,$}}\rangle$
is strongly connected, there is a walk $\langle
w_{0},w_{1},\dots,w_{n}\rangle$ in
$\langle\mathcal{W},\xrightarrow{\scalebox{0.75}{$\,{}_{\mathcal{W}}\,$}}\rangle$
from $\bar{\phi}^{-1}(r)$ to $\bar{\phi}^{-1}(m)$ and then back to
$\bar{\phi}^{-1}(r)$. By truncating this walk at the front and back if
necessary, we may assume, without loss of generality, this walk begins in
$\bar{\phi}^{-1}(r)$, then moves to $\bar{\phi}^{-1}(m)$, and then returns to
$\bar{\phi}^{-1}(r)$, without visiting any other regions of $\mathcal{W}$.
Because $\bar{\psi}$ is an epimorphism,
$\langle\bar{\psi}(w_{0}),\bar{\psi}(w_{1}),\dots,\bar{\psi}(w_{n})\rangle$ is
a walk in $\langle\mathcal{C},\xrightarrow{\text{\tiny$\,\sigma\,$}}\rangle$.
Similarly,
$\langle\phi\circ\bar{\phi}(w_{0}),\phi\circ\bar{\phi}(w_{1}),\dots,\phi\circ\bar{\phi}(w_{n})\rangle$
is a walk in
$\langle\mathcal{A},\xrightarrow{\scalebox{0.9}{$\,{}_{\alpha}\,$}}\rangle$.
By our assumptions about the “shape” of the walk in
$\langle\mathcal{W},\xrightarrow{\scalebox{0.75}{$\,{}_{\mathcal{W}}\,$}}\rangle$,
this walk in
$\langle\mathcal{A},\xrightarrow{\scalebox{0.9}{$\,{}_{\alpha}\,$}}\rangle$
begins at the rightmost vertex, then moves to the middle, and then moves back
to the right. Because $\bar{\phi}\circ\phi=\bar{\psi}\circ\psi$, this implies
that the walk
$\langle\bar{\psi}(w_{0}),\bar{\psi}(w_{1}),\dots,\bar{\psi}(w_{n})\rangle$ in
begins at the rightmost vertex of $\mathcal{C}$, moves to one/both of the
middle vertices for a while, and then returns to the right. But there are no
walks like this in
$\langle\mathcal{C},\xrightarrow{\scalebox{0.8}{$\,{}_{\gamma}\,$}}\rangle$. A
contradiction!)

Thus Observation 9.5 gives us another way of seeing what was proved
differently in Theorem 5.1:
$(\langle\mathbb{A},\alpha\rangle,\langle\mathbb{B},\beta\rangle,\iota,\eta)$
has no solution.

Our definition of “polarized” is motivated by this observation. It says
roughly that every virtual refinement of
$\langle\mathcal{A},\xrightarrow{\scalebox{0.9}{$\,{}_{\alpha}\,$}}\rangle$
either is realized by a further refinement of $\mathbb{A}$, or is incompatible
with a further refinement of $\mathbb{A}$.

######  Definition 9.6.

Let $\langle\mathbb{A},\alpha\rangle$ be an incompressible dynamical system. A
partition $\mathcal{A}$ of $\mathbb{A}$ is called _polarized_ if for every
virtual refinement $(\phi,\langle\mathcal{V},\to\rangle)$ of
$\langle\mathcal{A},\xrightarrow{\scalebox{0.9}{$\,{}_{\alpha}\,$}}\rangle$,
either

  1. (1)

there is a partition $\mathcal{A}^{\prime}$ of $\mathbb{A}$ that realizes
$(\phi,\langle\mathcal{V},\to\rangle)$, or

  2. (2)

there is a partition $\mathcal{A}^{\prime}$ of $\mathbb{A}$ refining
$\mathcal{A}$ such that $(\phi,\langle\mathcal{V},\to\rangle)$ and
$(\pi,\langle\mathcal{A}^{\prime},\xrightarrow{\scalebox{0.9}{$\,{}_{\alpha}\,$}}\rangle)$
are incompatible, where $\pi$ denotes the natural projection from
$\mathcal{A}^{\prime}$ onto $\mathcal{A}$.

By extension, we say that the dynamical system
$\langle\mathbb{A},\alpha\rangle$ itself is _polarized_ if every partition of
$\mathbb{A}$ is polarized. ☕

We end this section by verifying what was promised at its beginning: if the
$\langle\mathbb{A},\alpha\rangle$ in an instance of the lifting problem is
polarized, then this suffices to guarantee a lifting.

######  Theorem 9.7.

Suppose
$(\langle\mathbb{A},\alpha\rangle,\langle\mathbb{B},\beta\rangle,\iota,\eta)$
is an instance of the lifting problem for
$\langle\nicefrac{{\mathcal{P}(\omega)}}{{\mathrm{fin}}},\sigma\rangle$. If
$\langle\mathbb{A},\alpha\rangle$ is polarized, then this instance of the
lifting problem has a solution.

###### 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
8.8 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{0.8}{$\,{}_{\beta}\,$}}\rangle$
onto
$\langle\mathcal{A},\xrightarrow{\scalebox{0.9}{$\,{}_{\alpha}\,$}}\rangle$.
By Lemma 9.2,
$(\phi,\langle\mathcal{B},\xrightarrow{\scalebox{0.8}{$\,{}_{\beta}\,$}}\rangle)$
is a virtual refinement of
$\langle\mathcal{A},\xrightarrow{\scalebox{0.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{0.9}{$\,{}_{\alpha}\,$}}\rangle)$
is a virtual refinement of
$\langle\mathcal{A},\xrightarrow{\scalebox{0.9}{$\,{}_{\alpha}\,$}}\rangle$ by
Lemma 7.4, and this virtual refinement is compatible with
$(\phi,\langle\mathcal{B},\xrightarrow{\scalebox{0.8}{$\,{}_{\beta}\,$}}\rangle)$,
by Lemma 9.4. In other words, case $(2)$ of Definition 9.6 is not true of
$\mathcal{A}$ and
$(\phi,\langle\mathcal{B},\xrightarrow{\scalebox{0.8}{$\,{}_{\beta}\,$}}\rangle)$.
Because $\mathcal{A}$ is a polarized partition, this means that case $(1)$
must be true: there is a partition $\mathcal{A}^{\prime}$ of $\mathbb{A}$ that
realizes
$(\phi,\langle\mathcal{B},\xrightarrow{\scalebox{0.8}{$\,{}_{\beta}\,$}}\rangle)$.
Letting $\pi$ denote the natural map from $\mathcal{A}^{\prime}$ onto
$\mathcal{A}$, this means that there is an isomorphism $\phi^{\prime}$ from
$\langle\mathcal{B},\xrightarrow{\scalebox{0.8}{$\,{}_{\beta}\,$}}\rangle$
onto
$\langle\mathcal{A}^{\prime},\xrightarrow{\scalebox{0.9}{$\,{}_{\alpha}\,$}}\rangle$
such that $\pi\circ\phi^{\prime}=\phi$.

The remainder of the argument imitates the proof of Lemma 8.9, but using the
members of $\mathcal{A}^{\prime}$ in the place of the $\tilde{b}_{i}$.

Define $\tilde{\eta}(b)=\eta\circ\phi^{\prime}(b)$ for all $b\in\mathcal{B}$,
and let $\mathcal{C}=\tilde{\eta}[\mathcal{B}]$. Because $\phi^{\prime}$ is a
digraph isomorphism from
$\langle\mathcal{B},\xrightarrow{\scalebox{0.8}{$\,{}_{\beta}\,$}}\rangle$ to
$\langle\mathcal{A}^{\prime},\xrightarrow{\scalebox{0.9}{$\,{}_{\alpha}\,$}}\rangle$
and $\eta$ is a digraph isomorphism from
$\langle\mathcal{A}^{\prime},\xrightarrow{\scalebox{0.9}{$\,{}_{\alpha}\,$}}\rangle$
to $\langle\mathcal{C},\xrightarrow{\text{\tiny$\,\sigma\,$}}\rangle$ (by
Lemma 8.2), we see that $\tilde{\eta}$ is an isomorphism from
$\langle\mathcal{B},\xrightarrow{\scalebox{0.8}{$\,{}_{\beta}\,$}}\rangle$ to
$\langle\mathcal{C},\xrightarrow{\text{\tiny$\,\sigma\,$}}\rangle$. Also,
$\mathcal{C}=\tilde{\eta}[\mathcal{B}]=\eta[\phi^{\prime}[\mathcal{B}]]=\eta[\mathcal{A}^{\prime}]$;
because $\mathcal{A}^{\prime}$ 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\\{\tilde{\eta}(b)\colon
b\in\mathcal{B}\text{ and }b\leq\iota(a)\right\\}$. Similarly, (with the same
notational abuse) we define
$\phi^{\prime}\circ\iota(a)=\bigvee\left\\{\phi^{\prime}(b)\colon
b\in\mathcal{B}\text{ and }b\leq\iota(a)\right\\}$. Because
$\pi\circ\phi^{\prime}=\phi$ and $\pi(\phi^{\prime}(b))=a$ if and only if
$\phi^{\prime}(b)\leq a$,

$\displaystyle\phi^{\prime}\circ\iota(a)$
$\displaystyle\,=\,\textstyle\bigvee\left\\{\phi^{\prime}(b)\colon
b\in\mathcal{B}\text{ and }b\leq\iota(a)\right\\}$
$\displaystyle\textstyle\,=\,\bigvee\left\\{\phi^{\prime}(b)\colon
b\in\mathcal{B}\text{ and }\phi^{\prime}(b)\leq a\right\\}$
$\displaystyle\textstyle\,=\,\bigvee\left\\{c\colon
c\in\mathcal{A}^{\prime}\text{ and }c\leq a\right\\}\,=\,a.$

Consequently,
$\eta(a)=\eta\circ\phi^{\prime}\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. ∎

##  10\. The Lifting Lemma, part 5: the heart of the lemma

In this section, we prove a graph-theoretic result that is the combinatorial
heart and soul of the Lifting Lemma, and indeed, of the entire paper.

######  Definition 10.1.

Let
$\langle\mathcal{A},\xrightarrow{\scalebox{0.75}{$\,{}_{\mathcal{A}}\,$}}\rangle$
and
$\langle\mathcal{B},\xrightarrow{\scalebox{0.75}{$\,{}_{\mathcal{B}}\,$}}\rangle$
be strongly connected digraphs, and let $\phi$ be a function
$\mathcal{B}\to\mathcal{A}$ (usually assumed to be an epimorphism).

A length-$k$ walk $\langle b_{0},b_{1},\dots,b_{k}\rangle$ in
$\langle\mathcal{B},\xrightarrow{\scalebox{0.75}{$\,{}_{\mathcal{B}}\,$}}\rangle$
_projects_ onto a length-$k$ walk $\langle a_{0},a_{1},\dots,a_{k}\rangle$ in
$\langle\mathcal{A},\xrightarrow{\scalebox{0.75}{$\,{}_{\mathcal{A}}\,$}}\rangle$
(via $\phi$) if $\phi(b_{i})=a_{i}$ for all $i\leq k$. In the same way, an
infinite walk $\left\langle b_{n}\colon n\in\omega\right\rangle$ through
$\langle\mathcal{B},\xrightarrow{\scalebox{0.75}{$\,{}_{\mathcal{B}}\,$}}\rangle$
_projects_ (via $\phi$) onto an infinite walk $\left\langle a_{n}\colon
n\in\omega\right\rangle$ through
$\langle\mathcal{A},\xrightarrow{\scalebox{0.75}{$\,{}_{\mathcal{A}}\,$}}\rangle$
if $\phi(b_{n})=a_{n}$ for all $n$.

Likewise, $\left\langle b_{n}\colon n\in\omega\right\rangle$ _almost projects_
(via $\phi$) onto $\left\langle a_{n}\colon n\in\omega\right\rangle$ if
$\phi(b_{n})=a_{n}$ for all but finitely many $n\in\omega$. ☕

The main theorem of this section states:

######  Theorem 10.2.

Let
$\langle\mathcal{A},\xrightarrow{\scalebox{0.75}{$\,{}_{\mathcal{A}}\,$}}\rangle$
and
$\langle\mathcal{B},\xrightarrow{\scalebox{0.75}{$\,{}_{\mathcal{B}}\,$}}\rangle$
be strongly connected digraphs, and let $\phi$ be an epimorphism from
$\langle\mathcal{B},\xrightarrow{\scalebox{0.75}{$\,{}_{\mathcal{B}}\,$}}\rangle$
onto
$\langle\mathcal{A},\xrightarrow{\scalebox{0.75}{$\,{}_{\mathcal{A}}\,$}}\rangle$.
If $\left\langle a_{n}\colon n\in\omega\right\rangle$ is a diligent walk
through
$\langle\mathcal{A},\xrightarrow{\scalebox{0.75}{$\,{}_{\mathcal{A}}\,$}}\rangle$,
then either

  1. (1)

there is a diligent walk through
$\langle\mathcal{B},\xrightarrow{\scalebox{0.75}{$\,{}_{\mathcal{B}}\,$}}\rangle$
that almost projects onto $\left\langle a_{n}\colon n\in\omega\right\rangle$,
or

  2. (2)

there is a strongly connected digraph
$\langle\mathcal{C},\xrightarrow{\scalebox{0.75}{$\,{}_{\mathcal{C}}\,$}}\rangle$
and an epimorphism $\psi$ from
$\langle\mathcal{C},\xrightarrow{\scalebox{0.75}{$\,{}_{\mathcal{C}}\,$}}\rangle$
to
$\langle\mathcal{A},\xrightarrow{\scalebox{0.75}{$\,{}_{\mathcal{A}}\,$}}\rangle$
such that $\psi$ is incompatible with $\phi$, and furthermore there is a
diligent walk through
$\langle\mathcal{C},\xrightarrow{\scalebox{0.75}{$\,{}_{\mathcal{C}}\,$}}\rangle$
that almost projects onto $\left\langle a_{n}\colon n\in\omega\right\rangle$.

Note that the two alternatives in the statement of this theorem roughly
correspond to the two alternatives in Definition 9.6.

The proof of Theorem 10.2 naturally divides itself into two major stages. In
the first stage, we prove a weaker version of the theorem, where the “diligent
walk” from alternative $(1)$ is replaced by the weaker “infinite walk”
instead. This is stated as Theorem 10.8 below. The second stage of the proof
extends this weaker version of the theorem to the full version.

######  Lemma 10.3.

Let
$\langle\mathcal{A},\xrightarrow{\scalebox{0.75}{$\,{}_{\mathcal{A}}\,$}}\rangle$
and
$\langle\mathcal{B},\xrightarrow{\scalebox{0.75}{$\,{}_{\mathcal{B}}\,$}}\rangle$
be strongly connected digraphs, let $\phi$ be an epimorphism from
$\langle\mathcal{B},\xrightarrow{\scalebox{0.75}{$\,{}_{\mathcal{B}}\,$}}\rangle$
to
$\langle\mathcal{A},\xrightarrow{\scalebox{0.75}{$\,{}_{\mathcal{A}}\,$}}\rangle$,
and suppose $\left\langle a_{n}\colon n\in\omega\right\rangle$ is an infinite
walk through
$\langle\mathcal{A},\xrightarrow{\scalebox{0.75}{$\,{}_{\mathcal{A}}\,$}}\rangle$.
There is an infinite walk through
$\langle\mathcal{B},\xrightarrow{\scalebox{0.75}{$\,{}_{\mathcal{B}}\,$}}\rangle$
that projects onto $\left\langle a_{n}\colon n\in\omega\right\rangle$ if and
only if 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{0.75}{$\,{}_{\mathcal{B}}\,$}}\rangle$
that projects onto $\langle a_{0},a_{1},\dots,a_{k}\rangle$.

###### Proof.

The “only if” direction is obvious: if $\left\langle b_{n}\colon
n\in\omega\right\rangle$ is an infinite walk through
$\langle\mathcal{B},\xrightarrow{\scalebox{0.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{0.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 to prove the “if” direction of the theorem, let us 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{0.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{0.75}{$\,{}_{\mathcal{B}}\,$}}\rangle$
that projects onto $\left\langle a_{n}\colon n\in\omega\right\rangle$. ∎

######  Definition 10.4.

Let
$\langle\mathcal{A},\xrightarrow{\scalebox{0.75}{$\,{}_{\mathcal{A}}\,$}}\rangle$
and
$\langle\mathcal{B},\xrightarrow{\scalebox{0.75}{$\,{}_{\mathcal{B}}\,$}}\rangle$
be strongly connected digraphs, and let $\phi$ be an epimorphism from
$\langle\mathcal{B},\xrightarrow{\scalebox{0.75}{$\,{}_{\mathcal{B}}\,$}}\rangle$
to
$\langle\mathcal{A},\xrightarrow{\scalebox{0.75}{$\,{}_{\mathcal{A}}\,$}}\rangle$.
The _state space_ of $\phi$ is a digraph
$\langle\mathcal{S}^{\phi},\xrightarrow{\scalebox{0.75}{$\,{}_{\mathcal{S}^{\phi}}\,$}}\rangle$,
where

$\mathcal{S}^{\phi}\,=\,\left\\{\mathrm{S}\subseteq\mathcal{B}\colon|\phi[\mathrm{S}]|\leq
1\right\\},$

and given $\mathrm{S}_{0},\mathrm{S}_{1}\in\mathcal{S}^{\phi}$, we define
$\mathrm{S}_{0}\xrightarrow{\scalebox{0.75}{$\,{}_{\mathcal{S}^{\phi}}\,$}}\mathrm{S}_{1}$
if and only if there is some edge $(a_{0},a_{1})$ in
$\xrightarrow{\scalebox{0.75}{$\,{}_{\mathcal{A}}\,$}}$ such that
$\phi[\mathrm{S}_{0}]=\\{a_{0}\\}$, $\phi[\mathrm{S}_{1}]=\\{a_{1}\\}$, and

$\mathrm{S}_{1}\,=\,\left\\{y\in\phi^{-1}(a_{1})\colon\exists
x\in\mathrm{S}_{0}\text{ such that
}x\xrightarrow{\scalebox{0.75}{$\,{}_{\mathcal{B}}\,$}}y\right\\}.$

In this case we say that the edge $(a_{0},a_{1})$ in
$\xrightarrow{\scalebox{0.75}{$\,{}_{\mathcal{A}}\,$}}$ _induces_ the edge
$(\mathrm{S}_{0},\mathrm{S}_{1})$ in
$\xrightarrow{\scalebox{0.75}{$\,{}_{\mathcal{S}^{\phi}}\,$}}$. If
$\mathrm{S}\in\mathcal{S}^{\phi}\setminus\\{\emptyset\\}$, there is some
$a\in\mathcal{A}$ such that $\phi[\mathrm{S}]=\\{a\\}$. The _natural map_
$\Pi_{\phi}:\mathcal{S}^{\phi}\setminus\\{\emptyset\\}\to\mathcal{A}$ sends
each $\mathrm{S}\in\mathcal{S}^{\phi}$ to the unique member of
$\phi[\mathrm{S}]$. ☕

Drawn below are two examples of the state space
$\langle\mathcal{S}^{\phi},\xrightarrow{\scalebox{0.75}{$\,{}_{\mathcal{S}^{\phi}}\,$}}\rangle$
associated to some epimorphism $\phi$ from some
$\langle\mathcal{B},\xrightarrow{\scalebox{0.75}{$\,{}_{\mathcal{B}}\,$}}\rangle$
onto some
$\langle\mathcal{A},\xrightarrow{\scalebox{0.75}{$\,{}_{\mathcal{A}}\,$}}\rangle$.
To clarify the construction, we have labelled the members of
$\xrightarrow{\scalebox{0.75}{$\,{}_{\mathcal{A}}\,$}}$, and labelled each
member of $\xrightarrow{\scalebox{0.75}{$\,{}_{\mathcal{S}^{\phi}}\,$}}$ with
the member of $\xrightarrow{\scalebox{0.75}{$\,{}_{\mathcal{A}}\,$}}$ that
induces it.

$d$

$c$

$a$

$b$

$\langle\mathcal{A},\xrightarrow{\scalebox{0.75}{$\,{}_{\mathcal{A}}\,$}}\rangle$$\phi\,,\,\langle\mathcal{B},\xrightarrow{\scalebox{0.75}{$\,{}_{\mathcal{B}}\,$}}\rangle$$\langle\mathcal{S}^{\phi},\xrightarrow{\scalebox{0.75}{$\,{}_{\mathcal{S}^{\phi}}\,$}}\rangle$$\bullet$$\bullet$$\bullet$$\bullet$

$\bullet$

$\bullet$

$\bullet$

$\bullet$

$\bullet$

$\bullet$

$\emptyset$

$c$

$a$

$a$

$a$

$b$

$c$

$c$

$d$

$a$

$d$

$c$

$b$

$\langle\mathcal{A},\xrightarrow{\scalebox{0.75}{$\,{}_{\mathcal{A}}\,$}}\rangle$$\phi\,,\,\langle\mathcal{B},\xrightarrow{\scalebox{0.75}{$\,{}_{\mathcal{B}}\,$}}\rangle$$\langle\mathcal{S}^{\phi},\xrightarrow{\scalebox{0.75}{$\,{}_{\mathcal{S}^{\phi}}\,$}}\rangle$$\bullet$$\bullet$$\bullet$$\bullet$$\bullet$$\bullet$

$\bullet$

$\bullet$

$\bullet$

$\bullet$

$\bullet$

$\bullet$

$\bullet$

$\bullet$

$\bullet$

$\bullet$

$\bullet$

$\bullet$

$\emptyset$

$d$

$b$

$b$

$b$

$a$

$c$

$a$

$a$

$c$

$c$

$d$

$d$

The natural map
$\Pi_{\phi}:\mathcal{S}^{\phi}\setminus\\{\emptyset\\}\to\mathcal{A}$ is
indicated by the positions of the vertices of $\mathcal{S}^{\phi}$ in the
picture (although we have omitted the dotted circles as in the drawings of
$\langle\mathcal{B},\xrightarrow{\scalebox{0.75}{$\,{}_{\mathcal{B}}\,$}}\rangle$).

Observe that $\Pi_{\phi}$ is an epimorphism from the digraph
$\langle\mathcal{S}^{\phi}\setminus\\{\emptyset\\},\xrightarrow{\scalebox{0.75}{$\,{}_{\mathcal{S}^{\phi}}\,$}}\rangle$
to
$\langle\mathcal{A},\xrightarrow{\scalebox{0.75}{$\,{}_{\mathcal{A}}\,$}}\rangle$.
Observe also that
$\langle\mathcal{S}^{\phi},\xrightarrow{\scalebox{0.75}{$\,{}_{\mathcal{S}^{\phi}}\,$}}\rangle$
is not strongly connected, because the empty state $\emptyset$ has out-degree
$0$. Even the sub-digraph
$\langle\mathcal{S}^{\phi}\setminus\\{\emptyset\\},\xrightarrow{\scalebox{0.75}{$\,{}_{\mathcal{S}^{\phi}}\,$}}\rangle$
need not be strongly connected: for instance, in the second example
illustrated above, there is no path from a size-$1$ member of
$\mathcal{S}^{\phi}$ to a size-$2$ member.

######  Definition 10.5.

Let
$\langle\mathcal{A},\xrightarrow{\scalebox{0.75}{$\,{}_{\mathcal{A}}\,$}}\rangle$
and
$\langle\mathcal{B},\xrightarrow{\scalebox{0.75}{$\,{}_{\mathcal{B}}\,$}}\rangle$
be strongly connected digraphs, and let $\phi$ be an epimorphism from
$\langle\mathcal{B},\xrightarrow{\scalebox{0.75}{$\,{}_{\mathcal{B}}\,$}}\rangle$
to
$\langle\mathcal{A},\xrightarrow{\scalebox{0.75}{$\,{}_{\mathcal{A}}\,$}}\rangle$.
If $\bar{a}=\left\langle a_{n}\colon n\in\omega\right\rangle$ is an infinite
walk through
$\langle\mathcal{A},\xrightarrow{\scalebox{0.75}{$\,{}_{\mathcal{A}}\,$}}\rangle$,
then we associate to $\bar{a}$ an infinite sequence
$\left\langle\mathrm{S}_{n}^{\bar{a}}\colon n\in\omega\right\rangle$ in
$\mathcal{S}^{\phi}$, defined by taking

$\displaystyle\mathrm{S}^{\bar{a}}_{k}\,=\,\Big{\\{}b_{k}\in\mathcal{B}:\
\text{$b_{k}$ is the last member }$ of a length-$k$ walk in
$\langle\mathcal{B},\xrightarrow{\scalebox{0.75}{$\,{}_{\mathcal{B}}\,$}}\rangle$
$\displaystyle\text{ that projects onto }\langle
a_{1},a_{2},\dots,a_{k}\rangle\Big{\\}}$

for all $k\in\omega$. Each $\mathrm{S}^{\bar{a}}_{k}$ is well-defined (i.e.,
$\mathrm{S}^{\bar{a}}_{k}\in\mathcal{S}^{\phi}$) because
$\mathrm{S}^{\bar{a}}_{k}\subseteq\phi^{-1}(a_{k})$. This sequence is the
_state space sequence associated to $\bar{a}$_. ☕

To motivate Definition 10.5, suppose we have an epimorphism $\phi$ from some
strongly connected digraph
$\langle\mathcal{A},\xrightarrow{\scalebox{0.75}{$\,{}_{\mathcal{A}}\,$}}\rangle$
onto some other strongly connected digraph
$\langle\mathcal{B},\xrightarrow{\scalebox{0.75}{$\,{}_{\mathcal{B}}\,$}}\rangle$.
We wish to understand the following

_Question_ : Given an infinite walk $\left\langle a_{n}\colon
n\in\omega\right\rangle$ through
$\langle\mathcal{A},\xrightarrow{\scalebox{0.75}{$\,{}_{\mathcal{A}}\,$}}\rangle$,
is there an

infinite walk through
$\langle\mathcal{B},\xrightarrow{\scalebox{0.75}{$\,{}_{\mathcal{B}}\,$}}\rangle$
that projects onto it?

By Lemma 10.3, this question is equivalent to asking whether there are
arbitrarily long finite walks through
$\langle\mathcal{B},\xrightarrow{\scalebox{0.75}{$\,{}_{\mathcal{B}}\,$}}\rangle$
that project onto initial segments of $\left\langle a_{n}\colon
n\in\omega\right\rangle$. The state space sequence is simply a convenient way
of keeping track of what such walks might look like:
$\mathrm{S}^{\bar{a}}_{k}$ tells us the possibilities for $b_{k}$ in such a
walk, at least the possibilities not yet ruled out by looking at $\langle
a_{0},a_{1},\dots,a_{k}\rangle$. (They may be “ruled out” later, if there is
no extension to a longer walk that projects correctly.)

According to Lemma 10.3, there is an infinite walk through
$\langle\mathcal{B},\xrightarrow{\scalebox{0.75}{$\,{}_{\mathcal{B}}\,$}}\rangle$
projecting onto $\left\langle a_{n}\colon n\in\omega\right\rangle$ if and only
if the state space sequence associated to $\left\langle a_{n}\colon
n\in\omega\right\rangle$ never reaches the empty state $\emptyset$.

######  Lemma 10.6.

Let
$\langle\mathcal{A},\xrightarrow{\scalebox{0.75}{$\,{}_{\mathcal{A}}\,$}}\rangle$
and
$\langle\mathcal{B},\xrightarrow{\scalebox{0.75}{$\,{}_{\mathcal{B}}\,$}}\rangle$
be strongly connected digraphs, and let $\phi$ be an epimorphism from
$\langle\mathcal{B},\xrightarrow{\scalebox{0.75}{$\,{}_{\mathcal{B}}\,$}}\rangle$
to
$\langle\mathcal{A},\xrightarrow{\scalebox{0.75}{$\,{}_{\mathcal{A}}\,$}}\rangle$.
If $\bar{a}=\left\langle a_{n}\colon n\in\omega\right\rangle$ is an infinite
walk through
$\langle\mathcal{A},\xrightarrow{\scalebox{0.75}{$\,{}_{\mathcal{A}}\,$}}\rangle$,
then the state space sequence associated to $\bar{a}$ satisfies the following
recursion:

$\displaystyle\mathrm{S}^{\bar{a}}_{0}$ $\displaystyle\,=\,\phi^{-1}(a_{0}),$
$\displaystyle\mathrm{S}^{\bar{a}}_{k+1}$
$\displaystyle\,=\,\left\\{y\in\phi^{-1}(a_{k+1})\colon\exists
x\in\mathrm{S}^{\bar{a}}_{k}\text{ such that
}x\xrightarrow{\scalebox{0.75}{$\,{}_{\mathcal{B}}\,$}}y\right\\}.$

###### 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{0.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{0.75}{$\,{}_{\mathcal{B}}\,$}}b$. ∎

One immediate consequence of this lemma is that
$\mathrm{S}^{\bar{a}}_{k}\xrightarrow{\scalebox{0.75}{$\,{}_{\mathcal{S}^{\phi}}\,$}}\mathrm{S}^{\bar{a}}_{k+1}$
for every $k$, and this edge in
$\xrightarrow{\scalebox{0.75}{$\,{}_{\mathcal{S}^{\phi}}\,$}}$ is induced by
the edge $(a_{k},a_{k+1})$ in
$\xrightarrow{\scalebox{0.75}{$\,{}_{\mathcal{A}}\,$}}$. Or more precisely,
this is true unless $\mathrm{S}^{\bar{a}}_{k}=\emptyset$, in which case
$\mathrm{S}^{\bar{a}}_{n}=\emptyset$ for all $n\geq k$. Therefore,
$\left\langle\mathrm{S}^{\bar{a}}_{n}\colon n\in\omega\right\rangle$ either is
an infinite walk through
$\langle\mathcal{S}^{\phi},\xrightarrow{\scalebox{0.75}{$\,{}_{\mathcal{S}^{\phi}}\,$}}\rangle$
(in the case that $\mathrm{S}^{\bar{a}}_{k}\neq\emptyset$ for any $k$), or
else it is a finite walk through
$\langle\mathcal{S}^{\phi},\xrightarrow{\scalebox{0.75}{$\,{}_{\mathcal{S}^{\phi}}\,$}}\rangle$
followed an infinite sequence of $\emptyset$’s.

######  Lemma 10.7.

Suppose that
$\langle\mathcal{A},\xrightarrow{\scalebox{0.75}{$\,{}_{\mathcal{A}}\,$}}\rangle$
is a strongly connected digraph, and let $\left\langle a_{n}\colon
n\in\omega\right\rangle$ be a diligent walk through
$\langle\mathcal{A},\xrightarrow{\scalebox{0.75}{$\,{}_{\mathcal{A}}\,$}}\rangle$.
Suppose that
$\langle\mathcal{C},\xrightarrow{\scalebox{0.75}{$\,{}_{\mathcal{C}}\,$}}\rangle$
is any digraph, and let $\psi$ be a function $\mathcal{C}\to\mathcal{A}$. If
there is a diligent walk $\left\langle c_{n}\colon n\in\omega\right\rangle$
through
$\langle\mathcal{C},\xrightarrow{\scalebox{0.75}{$\,{}_{\mathcal{C}}\,$}}\rangle$
that almost projects via $\psi$ onto $\left\langle a_{n}\colon
n\in\omega\right\rangle$, then
$\langle\mathcal{C},\xrightarrow{\scalebox{0.75}{$\,{}_{\mathcal{C}}\,$}}\rangle$
is strongly connected and $\psi$ is an epimorphism.

###### Proof.

Suppose $\left\langle c_{n}\colon n\in\omega\right\rangle$ is a diligent walk
through
$\langle\mathcal{C},\xrightarrow{\scalebox{0.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{0.75}{$\,{}_{\mathcal{C}}\,$}}\rangle$
implies
$\langle\mathcal{C},\xrightarrow{\scalebox{0.75}{$\,{}_{\mathcal{C}}\,$}}\rangle$
is strongly connected, by Lemma 8.4. 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 $n\in\omega$ such
that $a_{n}=a$; in particular, $a_{n}=a$ for some $n\geq N$. Hence
$\psi(c_{n})=a_{n}$, and as $a$ was arbitrary, it follows that $\psi$ is
surjective.

Fix $c,c^{\prime}\in\mathcal{C}$ such that
$c\xrightarrow{\scalebox{0.75}{$\,{}_{\mathcal{C}}\,$}}c^{\prime}$. 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^{\prime}=c_{n+1}$. Because $n\geq N$,
this implies
$\psi(c)=a_{n}\xrightarrow{\scalebox{0.75}{$\,{}_{\mathcal{A}}\,$}}a_{n+1}=\psi(c^{\prime})$.

Lastly, fix $a,a^{\prime}\in\mathcal{A}$ such that
$a\xrightarrow{\scalebox{0.75}{$\,{}_{\mathcal{A}}\,$}}a^{\prime}$. 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^{\prime}=a_{n+1}$. Because $n\geq N$,
this implies $\psi(c_{n})=a$ and $c_{n+1}=a^{\prime}$. But
$c_{n}\xrightarrow{\scalebox{0.75}{$\,{}_{\mathcal{C}}\,$}}c_{n+1}$, so this
shows there are $c,c^{\prime}\in\mathcal{C}$ such that $\psi(c)=a$,
$\psi(c^{\prime})=a^{\prime}$, and
$c\xrightarrow{\scalebox{0.75}{$\,{}_{\mathcal{C}}\,$}}c^{\prime}$. ∎

######  Theorem 10.8.

Let
$\langle\mathcal{A},\xrightarrow{\scalebox{0.75}{$\,{}_{\mathcal{A}}\,$}}\rangle$
and
$\langle\mathcal{B},\xrightarrow{\scalebox{0.75}{$\,{}_{\mathcal{B}}\,$}}\rangle$
be strongly connected digraphs, and let $\phi$ be an epimorphism from
$\langle\mathcal{B},\xrightarrow{\scalebox{0.75}{$\,{}_{\mathcal{B}}\,$}}\rangle$
onto
$\langle\mathcal{A},\xrightarrow{\scalebox{0.75}{$\,{}_{\mathcal{A}}\,$}}\rangle$.
If $\left\langle a_{n}\colon n\in\omega\right\rangle$ is a diligent walk
through
$\langle\mathcal{A},\xrightarrow{\scalebox{0.75}{$\,{}_{\mathcal{A}}\,$}}\rangle$,
then either

  1. (1)

there is an infinite walk through
$\langle\mathcal{B},\xrightarrow{\scalebox{0.75}{$\,{}_{\mathcal{B}}\,$}}\rangle$
that almost projects onto $\left\langle a_{n}\colon n\in\omega\right\rangle$,
or

  2. (2)

there is a strongly connected digraph
$\langle\mathcal{C},\xrightarrow{\scalebox{0.75}{$\,{}_{\mathcal{C}}\,$}}\rangle$
and an epimorphism $\psi$ from
$\langle\mathcal{C},\xrightarrow{\scalebox{0.75}{$\,{}_{\mathcal{C}}\,$}}\rangle$
to
$\langle\mathcal{A},\xrightarrow{\scalebox{0.75}{$\,{}_{\mathcal{A}}\,$}}\rangle$
such that $\psi$ is incompatible with $\phi$, and there is a diligent walk
through
$\langle\mathcal{C},\xrightarrow{\scalebox{0.75}{$\,{}_{\mathcal{C}}\,$}}\rangle$
that projects onto $\left\langle a_{n}\colon n\in\omega\right\rangle$.

###### Proof.

Let
$\langle\mathcal{A},\xrightarrow{\scalebox{0.75}{$\,{}_{\mathcal{A}}\,$}}\rangle$
and
$\langle\mathcal{B},\xrightarrow{\scalebox{0.75}{$\,{}_{\mathcal{B}}\,$}}\rangle$
be strongly connected digraphs, and let $\phi$ be an epimorphism from
$\langle\mathcal{B},\xrightarrow{\scalebox{0.75}{$\,{}_{\mathcal{B}}\,$}}\rangle$
to
$\langle\mathcal{A},\xrightarrow{\scalebox{0.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{0.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 10.3,
this implies there is an infinite walk $\left\langle b_{n}\colon
n\in\omega\right\rangle$ through
$\langle\mathcal{B},\xrightarrow{\scalebox{0.75}{$\,{}_{\mathcal{B}}\,$}}\rangle$
that projects onto $\bar{a}_{m}$. Using the fact that
$\langle\mathcal{B},\xrightarrow{\scalebox{0.75}{$\,{}_{\mathcal{B}}\,$}}\rangle$
is strongly connected, fix some length-$m$ walk $\langle
b^{\prime}_{0},b^{\prime}_{1},\dots,b^{\prime}_{m}\rangle$ in
$\langle\mathcal{B},\xrightarrow{\scalebox{0.75}{$\,{}_{\mathcal{B}}\,$}}\rangle$
such that $b^{\prime}_{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}^{\prime}&\text{ if }i\leq m,\\\
b_{i-m}&\text{ if }i\geq m.\end{cases}$

It is not difficult to see that
$\langle\tilde{b}_{0},\tilde{b}_{1},\tilde{b}_{2},\dots\rangle$ is an infinite
walk through
$\langle\mathcal{B},\xrightarrow{\scalebox{0.75}{$\,{}_{\mathcal{B}}\,$}}\rangle$
that almost projects onto $\bar{a}$ via $\phi$: in fact, $\phi(b_{n})=a_{n}$
whenever $n\geq m$.

This shows that 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. Thus, to prove the theorem, it
suffices to show that if this is not the case, then alternative $(2)$ holds
instead.

Let us suppose, then, that for every $m\in\omega$ there is some $k>0$ 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$.

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{0.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

  * $\circ$

$\left\\{\mathrm{S}^{\bar{a}_{m}}_{i}\colon i\leq
k_{m}\right\\}\,=\,\mathcal{C}_{0}$,

  * $\circ$

$\left\\{(\mathrm{S}^{\bar{a}_{m}}_{i},\mathrm{S}^{\bar{a}_{m}}_{i+1})\colon
i<k_{m}\right\\}\,=\,\mathcal{E}_{0}$,

  * $\circ$

$\mathrm{S}^{\bar{a}_{m}}_{0}\,=\,\mathrm{S}_{\text{in}}$,

  * $\circ$

$a_{m-1}\,=\,a_{\text{in}}$,

  * $\circ$

$a_{k_{m}}\,=\,a_{\text{end}}$,

  * $\circ$

$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{0.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:

$\displaystyle x\xrightarrow{\scalebox{0.75}{$\,{}_{\mathcal{C}}\,$}}y\quad\
\Longleftrightarrow\quad\ $ $\displaystyle x,y\in\mathcal{A}\text{ and
}x\xrightarrow{\scalebox{0.75}{$\,{}_{\mathcal{A}}\,$}}y\text{, or}$
$\displaystyle x,y\in\mathcal{C}_{0}\text{ and }(x,y)\in\mathcal{E}_{0}\text{,
or}$ $\displaystyle x=a_{\text{in}}\text{ and }y=\mathrm{S}_{\text{in}}\text{,
or}$ $\displaystyle x=\emptyset\text{ and }y=a_{\mathrm{out}}.$

$\langle\mathcal{A},\xrightarrow{\scalebox{0.75}{$\,{}_{\mathcal{A}}\,$}}\rangle$$\bullet$

$a_{\text{in}}$

$\bullet$

$a_{\text{out}}$

$\langle\mathcal{C}_{0},\mathcal{E}_{0}\rangle$$\bullet$

$\mathrm{S}_{\text{in}}$

$\bullet$

$\emptyset$

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{0.75}{$\,{}_{\mathcal{C}}\,$}}\rangle$
and $\psi$. To finish the proof, we need to show that
$\langle\mathcal{C},\xrightarrow{\scalebox{0.75}{$\,{}_{\mathcal{C}}\,$}}\rangle$
is strongly connected, that $\psi$ is an epimorphism from
$\langle\mathcal{C},\xrightarrow{\scalebox{0.75}{$\,{}_{\mathcal{C}}\,$}}\rangle$
to
$\langle\mathcal{A},\xrightarrow{\scalebox{0.75}{$\,{}_{\mathcal{A}}\,$}}\rangle$,
that there is a diligent walk through
$\langle\mathcal{C},\xrightarrow{\scalebox{0.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 10.7. 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{0.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^{\prime})$ in
$\xrightarrow{\scalebox{0.75}{$\,{}_{\mathcal{A}}\,$}}$, there are infinitely
many $i\in\omega$ such that $(a_{i},a_{i+1})=(a,a^{\prime})$. Fix some
$m_{0}\in D$ large enough that for every $(a,a^{\prime})$ in
$\xrightarrow{\scalebox{0.75}{$\,{}_{\mathcal{A}}\,$}}$, there is at least one
$i+1<m_{0}$ such that $(a_{i},a_{i+1})=(a,a^{\prime})$. Then define

$\displaystyle c_{i}$ $\displaystyle\,=\,a_{i}\qquad\quad\ \ \,\text{for all
}i<m_{0}\text{, and}$ $\displaystyle c_{i}$
$\displaystyle\,=\,\mathrm{S}^{\bar{a}_{m_{0}}}_{i-m_{0}}\qquad\text{whenever
}m_{0}\leq i\leq m_{0}+k_{m_{0}}.$

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^{\prime})\in\ \xrightarrow{\scalebox{0.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^{\prime})$. Then define

$\displaystyle c_{i}$ $\displaystyle\,=\,a_{i}\qquad\quad\ \ \,\text{whenever
}m_{n-1}+k_{m_{n-1}}\leq i<m_{n}\text{, and}$ $\displaystyle c_{i}$
$\displaystyle\,=\,\mathrm{S}^{\bar{a}_{m_{n}}}_{i-m_{n}}\qquad\text{whenever
}m_{n}\leq i\leq m_{n}+k_{m_{n}}.$

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{0.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:

  * $\circ$

$c_{i}=a_{i}$ and $c_{i+1}=a_{i+1}$,

  * $\circ$

$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$,

  * $\circ$

$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

  * $\circ$

$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{0.75}{$\,{}_{\mathcal{C}}\,$}}$ that
$c_{i}\xrightarrow{\scalebox{0.75}{$\,{}_{\mathcal{C}}\,$}}c_{i+1}$. Hence
$\left\langle c_{i}\colon i\in\omega\right\rangle$ is an infinite walk through
$\langle\mathcal{C},\xrightarrow{\scalebox{0.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:

  * $\circ$

for every $(a,a^{\prime})$ in
$\xrightarrow{\scalebox{0.75}{$\,{}_{\mathcal{A}}\,$}}$ there is some new
$c_{i}$ with $(c_{i},c_{i+1})=(a,a^{\prime})$,

  * $\circ$

for every $(\mathrm{S},\mathrm{S}^{\prime})$ in $\mathcal{E}_{0}$ there is
some new $c_{i}$ with $(c_{i},c_{i+1})=(\mathrm{S},\mathrm{S}^{\prime})$,

  * $\circ$

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

  * $\circ$

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

In other words, for every $(c,c^{\prime})$ in
$\xrightarrow{\scalebox{0.75}{$\,{}_{\mathcal{C}}\,$}}$ there is some new
$c_{i}$ with $(c_{i},c_{i+1})=(c,c^{\prime})$. It follows that $\left\langle
c_{i}\colon i\in\omega\right\rangle$ is a diligent walk through
$\langle\mathcal{C},\xrightarrow{\scalebox{0.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

  * $\circ$

$c_{i}=\mathrm{S}^{\bar{a}_{m}}_{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}}_{i-m_{n}}\neq\emptyset$ and
$\mathrm{S}^{\bar{a}_{m}}_{i-m_{n}}\subseteq\phi^{-1}(a_{i-m_{n}})$, which
implies that
$\psi(c_{i})=\Pi_{\phi}(\mathrm{S}^{\bar{a}_{m}}_{i-m_{n}})=a_{i}$; or

  * $\circ$

$c_{i}=\mathrm{S}^{\bar{a}_{m}}_{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 10.7,
$\langle\mathcal{C},\xrightarrow{\scalebox{0.75}{$\,{}_{\mathcal{C}}\,$}}\rangle$
is strongly connected, $\psi$ is an epimorphism from
$\langle\mathcal{C},\xrightarrow{\scalebox{0.75}{$\,{}_{\mathcal{C}}\,$}}\rangle$
to
$\langle\mathcal{A},\xrightarrow{\scalebox{0.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{0.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{0.75}{$\,{}_{\mathcal{W}}\,$}}\rangle$
and epimorphisms $\bar{\phi}$ and $\bar{\psi}$ from
$\langle\mathcal{W},\xrightarrow{\scalebox{0.75}{$\,{}_{\mathcal{W}}\,$}}\rangle$
to
$\langle\mathcal{B},\xrightarrow{\scalebox{0.75}{$\,{}_{\mathcal{B}}\,$}}\rangle$
and
$\langle\mathcal{C},\xrightarrow{\scalebox{0.75}{$\,{}_{\mathcal{C}}\,$}}\rangle$,
respectively, such that $\phi\circ\bar{\phi}=\psi\circ\bar{\psi}$.

$\langle\mathcal{A},\xrightarrow{\scalebox{0.75}{$\,{}_{\mathcal{A}}\,$}}\rangle$$\langle\mathcal{B},\xrightarrow{\scalebox{0.75}{$\,{}_{\mathcal{B}}\,$}}\rangle$$\langle\mathcal{C},\xrightarrow{\scalebox{0.75}{$\,{}_{\mathcal{C}}\,$}}\rangle$$\langle\mathcal{W},\xrightarrow{\scalebox{0.75}{$\,{}_{\mathcal{W}}\,$}}\rangle$$\psi$$\phi$$\bar{\psi}$$\bar{\phi}$

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{0.75}{$\,{}_{\mathcal{W}}\,$}}\rangle$
is strongly connected, fix a path $\langle
w_{0},w_{1},w_{2},\dots,w_{n}\rangle$ in
$\langle\mathcal{W},\xrightarrow{\scalebox{0.75}{$\,{}_{\mathcal{W}}\,$}}\rangle$
from some member of $\bar{\psi}^{-1}(\mathrm{S}_{\text{in}})$ to some member
of $\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{0.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{0.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{0.75}{$\,{}_{\mathcal{C}}\,$}}$ going from a member of
$\mathcal{C}_{0}$ to a member of $\mathcal{A}$. Because we are assuming
$\bar{\psi}(w_{k})\neq\emptyset$ for all $k<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 path in
$\langle\mathcal{B},\xrightarrow{\scalebox{0.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}\subseteq\mathcal{S}^{\phi}$
whenever $i\leq n$. Therefore this assertion 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
recall that
$\mathrm{S}_{\text{in}}=\mathrm{S}^{\bar{a}_{m}}_{0}=\phi^{-1}(a_{m})$ for
some (any) $m\in D$. Thus $\Pi_{\phi}(\mathrm{S}_{\text{in}})=a_{m}$, and
$\phi^{-1}(\Pi_{\phi}(\mathrm{S}_{\text{in}}))=\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{0.75}{$\,{}_{\mathcal{W}}\,$}}w_{i+1}$,
$\bar{\psi}(w_{i})\xrightarrow{\scalebox{0.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{0.75}{$\,{}_{\mathcal{B}}\,$}}\bar{\phi}(w_{i+1})$
(because $w_{i}\xrightarrow{\scalebox{0.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 10.6,

$\mathrm{S}^{\bar{a}_{m}}_{k+1}\,=\,\left\\{b\in\phi^{-1}(a_{m+k+1})\colon\exists
x\in\mathrm{S}^{\bar{a}_{m}}_{k}\text{ such that
}x\xrightarrow{\scalebox{0.75}{$\,{}_{\mathcal{B}}\,$}}y\right\\},$

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! ∎

This completes the first stage of our proof of Theorem 10.2. The second stage
is similar in many ways: either some condition holds that (in a relatively
easy way) implies alternative $(1)$ of the theorem, or else we can use the
state space digraph to construct a digraph
$\langle\mathcal{C},\xrightarrow{\scalebox{0.75}{$\,{}_{\mathcal{C}}\,$}}\rangle$
witnessing alternative $(2)$. For the second stage of the proof, this
construction involves both the state space sequence defined above and a time-
reversed version of it.

######  Definition 10.9.

Let
$\langle\mathcal{A},\xrightarrow{\scalebox{0.75}{$\,{}_{\mathcal{A}}\,$}}\rangle$
and
$\langle\mathcal{B},\xrightarrow{\scalebox{0.75}{$\,{}_{\mathcal{B}}\,$}}\rangle$
be strongly connected digraphs, and let $\phi$ be an epimorphism from
$\langle\mathcal{B},\xrightarrow{\scalebox{0.75}{$\,{}_{\mathcal{B}}\,$}}\rangle$
to
$\langle\mathcal{A},\xrightarrow{\scalebox{0.75}{$\,{}_{\mathcal{A}}\,$}}\rangle$.
If $\bar{a}=\left\langle a_{n}\colon n\in\omega\right\rangle$ is an infinite
walk through
$\langle\mathcal{A},\xrightarrow{\scalebox{0.75}{$\,{}_{\mathcal{A}}\,$}}\rangle$
and $m\in\omega$, then we associate to $\bar{a}$ a length-$m$ sequence
$\left\langle\reflectbox{\text{S}}_{i}^{\bar{a},m}\colon i\leq m\right\rangle$
in $\mathcal{S}^{\phi}$, defined by taking

$\displaystyle\reflectbox{\text{S}}^{\bar{a},m}_{k}=\Big{\\{}b_{k}\in\mathcal{B}:\,\text{$b_{k}$
is the firs}$ t member of a length-$(m-k)$ walk in
$\langle\mathcal{B},\xrightarrow{\scalebox{0.75}{$\,{}_{\mathcal{B}}\,$}}\rangle$
$\displaystyle\text{ that projects onto }\langle
a_{k},a_{k+1},a_{k+2},\dots,a_{m}\rangle\Big{\\}}$

for all $k\leq m$. Each $\reflectbox{\text{S}}^{\bar{a},m}_{k}$ is well-
defined (i.e., $\reflectbox{\text{S}}^{\bar{a},m}_{k}\in\mathcal{S}^{\phi}$)
because $\reflectbox{\text{S}}^{\bar{a},m}_{k}\subseteq\phi^{-1}(a_{k})$. For
any given $m$, this is called the _reverse state space sequence associated to
$\bar{a}$ at $m$._ ☕

Just as the state space sequence $\left\langle\mathrm{S}^{\bar{a}}_{i}\colon
i\in\omega\right\rangle$ has its Lemma 10.6, the reverse state space sequence
also admits an inductive characterization:

######  Lemma 10.10.

Let
$\langle\mathcal{A},\xrightarrow{\scalebox{0.75}{$\,{}_{\mathcal{A}}\,$}}\rangle$
and
$\langle\mathcal{B},\xrightarrow{\scalebox{0.75}{$\,{}_{\mathcal{B}}\,$}}\rangle$
be strongly connected digraphs, and let $\phi$ be an epimorphism from
$\langle\mathcal{B},\xrightarrow{\scalebox{0.75}{$\,{}_{\mathcal{B}}\,$}}\rangle$
to
$\langle\mathcal{A},\xrightarrow{\scalebox{0.75}{$\,{}_{\mathcal{A}}\,$}}\rangle$.
If $\bar{a}=\left\langle a_{n}\colon n\in\omega\right\rangle$ is an infinite
walk through
$\langle\mathcal{A},\xrightarrow{\scalebox{0.75}{$\,{}_{\mathcal{A}}\,$}}\rangle$
and $m\in\omega$, then the reverse state space sequence associated to
$\bar{a}$ at $m$ satisfies the following recursion:

$\reflectbox{\text{S}}^{\bar{a},m}_{m}$ $\displaystyle\,=\,\phi^{-1}(a_{m}),$
$\reflectbox{\text{S}}^{\bar{a},m}_{i-1}$
$\displaystyle\,=\,\left\\{y\in\phi^{-1}(a_{i-1})\colon\exists
x\in\emph{$\reflectbox{\text{S}}^{\bar{a},m}_{i}$}\text{ such that
}y\xrightarrow{\scalebox{0.75}{$\,{}_{\mathcal{B}}\,$}}x\right\\}.$

###### Proof.

It is clear that $\reflectbox{\text{S}}^{\bar{a},m}_{m}=\phi^{-1}(a_{m})$,
because $\langle b\rangle$ is a length-$0$ walk projecting onto $\langle
a_{m}\rangle$ if and only if $\phi(b)=a_{m}$. For the general step of the
recursion, observe that $\langle b_{i-1},b_{i},\dots,b_{m}\rangle$ is a
length-$(m-i+1)$ walk projecting onto $\langle
a_{i-1},a_{i},\dots,a_{m}\rangle$ if and only if $(1)$ $\langle
b_{i},b_{i+1},\dots,b_{m}\rangle$ is a length-$(m-i)$ walk projecting onto
$\langle a_{i},a_{i+1},\dots,a_{m}\rangle$, $(2)$
$b_{i-1}\xrightarrow{\scalebox{0.75}{$\,{}_{\mathcal{B}}\,$}}b_{i}$, and $(3)$
$\phi(b_{i-1})=a_{i-1}$. Thus $b\in\reflectbox{\text{S}}^{\bar{a},m}_{i-1}$ if
and only if $\phi(b)=a_{i-1}$ and there is some length-$(m-i)$ walk $\langle
b_{i},b_{i+1},\dots,b_{m}\rangle$ projecting onto $\langle
a_{i},a_{i+1},\dots,a_{m}\rangle$ such that
$b\xrightarrow{\scalebox{0.75}{$\,{}_{\mathcal{B}}\,$}}b_{i}$. ∎

######  Definition 10.11.

Let
$\langle\mathcal{A},\xrightarrow{\scalebox{0.75}{$\,{}_{\mathcal{A}}\,$}}\rangle$
and
$\langle\mathcal{B},\xrightarrow{\scalebox{0.75}{$\,{}_{\mathcal{B}}\,$}}\rangle$
be strongly connected digraphs, let $\phi$ be an epimorphism from
$\langle\mathcal{B},\xrightarrow{\scalebox{0.75}{$\,{}_{\mathcal{B}}\,$}}\rangle$
to
$\langle\mathcal{A},\xrightarrow{\scalebox{0.75}{$\,{}_{\mathcal{A}}\,$}}\rangle$,
and let $\bar{a}=\left\langle a_{n}\colon n\in\omega\right\rangle$ be an
infinite walk through
$\langle\mathcal{A},\xrightarrow{\scalebox{0.75}{$\,{}_{\mathcal{A}}\,$}}\rangle$.

Following the standard practice among set theorists and logicians, if
$k\in\omega$ then $k=\\{0,1,\dots,k-1\\}$, and a function $\omega\to X$ or
$\omega\\!\setminus\\!k\to X$ to is an infinite sequence in $X$. For each
$k\in\omega$, let

$\displaystyle\mathcal{T}^{\bar{a}}_{k}\,=\,\Big{\\{}x\,:\ $ $\displaystyle
x\text{ is a function $\omega\\!\setminus\\!k\to\mathcal{B}$, $x$ is a walk in
$\langle\mathcal{B},\xrightarrow{\scalebox{0.75}{$\,{}_{\mathcal{B}}\,$}}\rangle$,
}$ $\displaystyle\qquad\qquad\qquad\qquad\ \text{and $\phi(x(i))=a_{i}$ for
all $i\geq k$}\Big{\\}}.$

In other words, $\mathcal{T}^{\bar{a}}_{k}$ is the set of all infinite walks
through
$\langle\mathcal{B},\xrightarrow{\scalebox{0.75}{$\,{}_{\mathcal{B}}\,$}}\rangle$
that project onto the tail $\langle a_{k},a_{k+1},\dots\rangle$ of $\bar{a}$.
These walks are indexed with $\omega\\!\setminus\\!k$, rather than $\omega$,
so that we may think of them as tails of longer walks in
$\langle\mathcal{B},\xrightarrow{\scalebox{0.75}{$\,{}_{\mathcal{B}}\,$}}\rangle$
that almost project onto $\bar{a}$.

For each $k\in\omega$, define $\mathrm{T}^{\bar{a}}_{k}=\left\\{x(k)\colon
x\in\mathcal{F}^{\bar{a}}_{k}\right\\}$. ☕

######  Lemma 10.12.

Let
$\langle\mathcal{A},\xrightarrow{\scalebox{0.75}{$\,{}_{\mathcal{A}}\,$}}\rangle$
and
$\langle\mathcal{B},\xrightarrow{\scalebox{0.75}{$\,{}_{\mathcal{B}}\,$}}\rangle$
be strongly connected digraphs, $\phi$ an epimorphism from
$\langle\mathcal{B},\xrightarrow{\scalebox{0.75}{$\,{}_{\mathcal{B}}\,$}}\rangle$
to
$\langle\mathcal{A},\xrightarrow{\scalebox{0.75}{$\,{}_{\mathcal{A}}\,$}}\rangle$,
and $\bar{a}=\left\langle a_{n}\colon n\in\omega\right\rangle$ an infinite
walk through
$\langle\mathcal{A},\xrightarrow{\scalebox{0.75}{$\,{}_{\mathcal{A}}\,$}}\rangle$.
Then $\mathrm{T}^{\bar{a}}_{k}=\emph{\reflectbox{\text{S}}}^{\bar{a},m}_{k}$
for all sufficiently large $m$.

###### Proof.

If $b\in\mathrm{T}^{\bar{a}}_{k}$, then there is some
$x\in\mathcal{T}^{\bar{a}}_{k}$ with $x(k)=b$. But then the walk $\langle
x(k),x(k+1),\dots,x(m)\rangle$ witnesses
$b\in\reflectbox{\text{S}}^{\bar{a},m}_{k}$ for all $m\geq k$.

For the reverse inclusion, suppose $b\in\reflectbox{\text{S}}^{\bar{a},m}_{k}$
for all sufficiently large $m$. Let $\mathcal{W}$ denote the set of finite
walks $\langle b_{k},b_{k+1},\dots,b_{m}\rangle$ in
$\langle\mathcal{B},\xrightarrow{\scalebox{0.75}{$\,{}_{\mathcal{B}}\,$}}\rangle$
with $b_{k}=b$ that project onto the initial segment $\langle
a_{k},a_{k+1},\dots,a_{m}\rangle$ of $\bar{a}_{k}=\left\langle a_{k+i}\colon
i\in\omega\right\rangle$ with the same length. Ordered in the natural way, by
end extension, $\mathcal{W}$ is a finitely-branching tree. (This is similar to
the situation in the proof of Lemma 10.3.) Our assumption (that
$b\in\reflectbox{\text{S}}^{\bar{a},m}_{k}$ for all sufficiently large $m$)
means $\mathcal{W}$ is infinite, and so $\mathcal{W}$ has an infinite branch
by Kőnig’s Tree Lemma. The union of this branch is an infinite walk $x=\langle
b_{k},b_{k+1},b_{k+2},\dots\rangle$ through
$\langle\mathcal{B},\xrightarrow{\scalebox{0.75}{$\,{}_{\mathcal{B}}\,$}}\rangle$
with $b_{k}=b$ that projects onto $\bar{a}_{k}$. In other words,
$x\in\mathrm{T}^{\bar{a}}_{k}$, and $x$ witnesses
$b\in\mathrm{T}^{\bar{a}}_{k}$. ∎

We are now ready to finish proving the main theorem of this section.

###### Proof of Theorem 10.2.

Let
$\langle\mathcal{A},\xrightarrow{\scalebox{0.75}{$\,{}_{\mathcal{A}}\,$}}\rangle$
and
$\langle\mathcal{B},\xrightarrow{\scalebox{0.75}{$\,{}_{\mathcal{B}}\,$}}\rangle$
be strongly connected digraphs, let $\phi$ be an epimorphism from
$\langle\mathcal{B},\xrightarrow{\scalebox{0.75}{$\,{}_{\mathcal{B}}\,$}}\rangle$
to
$\langle\mathcal{A},\xrightarrow{\scalebox{0.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{0.75}{$\,{}_{\mathcal{A}}\,$}}\rangle$.

By Theorem 10.8, if there is no infinite walk through
$\langle\mathcal{B},\xrightarrow{\scalebox{0.75}{$\,{}_{\mathcal{B}}\,$}}\rangle$
that almost projects onto $\bar{a}$, then there is a strongly connected
digraph
$\langle\mathcal{C},\xrightarrow{\scalebox{0.75}{$\,{}_{\mathcal{C}}\,$}}\rangle$
and an epimorphism $\psi$ from
$\langle\mathcal{C},\xrightarrow{\scalebox{0.75}{$\,{}_{\mathcal{C}}\,$}}\rangle$
to
$\langle\mathcal{A},\xrightarrow{\scalebox{0.75}{$\,{}_{\mathcal{A}}\,$}}\rangle$
such that $\psi$ is incompatible with $\phi$, and there is a diligent walk
through
$\langle\mathcal{C},\xrightarrow{\scalebox{0.75}{$\,{}_{\mathcal{C}}\,$}}\rangle$
that projects onto $\left\langle a_{n}\colon n\in\omega\right\rangle$. In
other words, if there is no infinite walk through
$\langle\mathcal{B},\xrightarrow{\scalebox{0.75}{$\,{}_{\mathcal{B}}\,$}}\rangle$
that almost projects onto $\bar{a}$, then alternative $(2)$ in the statement
of the theorem holds. Thus, for the remainder of the proof, we may (and do)
assume there is an infinite walk through
$\langle\mathcal{B},\xrightarrow{\scalebox{0.75}{$\,{}_{\mathcal{B}}\,$}}\rangle$
that almost projects onto $\left\langle a_{n}\colon n\in\omega\right\rangle$.

For each $m\in\omega$, let $\bar{a}_{m}=\left\langle a_{m+i}\colon
i\in\omega\right\rangle$. Our assumption that there is an infinite walk
through
$\langle\mathcal{B},\xrightarrow{\scalebox{0.75}{$\,{}_{\mathcal{B}}\,$}}\rangle$
that almost projects onto $\left\langle a_{n}\colon n\in\omega\right\rangle$
is equivalent to the assertion that $\mathcal{T}^{\bar{a}}_{k}$ and
$\mathrm{T}^{\bar{a}}_{k}$ are nonempty for sufficiently large values of $k$.

Fix some $a\in\mathcal{A}$ arbitrarily, and let
$D_{0}=\left\\{n\in\omega\colon a_{n}=a\right\\}$. Note that $D_{0}$ is
infinite, because $\left\langle a_{n}\colon n\in\omega\right\rangle$ is a
diligent walk through
$\langle\mathcal{A},\xrightarrow{\scalebox{0.75}{$\,{}_{\mathcal{A}}\,$}}\rangle$.
Thinning $D_{0}$ out if necessary, we may (and do) suppose $D_{0}$ does not
contain two consecutive integers.

Thinning $D_{0}$ out further, fix an infinite $D_{1}\subseteq D_{0}$ such that
for every $k\in D_{1}$, if $m\in D_{1}$ and $m>k$, then $m$ is large enough
that $\mathrm{T}^{\bar{a}}_{k}=\reflectbox{\text{S}}^{\bar{a},m}_{k}$. Such a
set is easily constructed by recursion, by beginning with $\min(D_{0})\in
D_{1}$ and using Lemma 10.12 to add some new, sufficiently large element of
$D_{0}$ to $D_{1}$ at every stage of the recursion.

Because $\phi^{-1}(a)$ is finite, there is some particular
$\mathrm{T}\subseteq\phi^{-1}(a)$ such that
$\mathrm{T}^{\bar{a}}_{k}=\mathrm{T}$ for infinitely many $k\in D_{1}$. Let
$D_{2}=\left\\{k\in D_{1}\colon\mathrm{T}^{\bar{a}}_{k}=\mathrm{T}\right\\}$.
Observe that $\mathrm{T}\neq\emptyset$, because as we mentioned above,
$\mathrm{T}^{\bar{a}}_{k}\neq\emptyset$ for sufficiently large values of $k$.

For each $\ell,m\in D_{2}$ with $\ell<m$, define a relation
$\mathcal{R}_{\ell,m}\subseteq\mathrm{T}\times\mathrm{T}$ as follows:

$\displaystyle(v,w)\in\mathcal{R}_{\ell,m}\qquad\Leftrightarrow\qquad$ there
is a walk $\langle b_{\ell},b_{\ell+1},\dots,b_{m}\rangle$ in
$\langle\mathcal{B},\xrightarrow{\scalebox{0.75}{$\,{}_{\mathcal{B}}\,$}}\rangle$
from $v$ to $w$ that projects onto $\langle
a_{\ell},a_{\ell+1},\dots,a_{m}\rangle$.

This relation expresses the “walkability” between the members of
$\mathrm{T}=\mathrm{T}^{\bar{a}}_{\ell}$ at stage $\ell$ and
$\mathrm{T}=\mathrm{T}^{\bar{a}}_{m}$ at stage $m$.

Because $\mathrm{T}$ is finite, the mapping
$\chi:[D_{2}]^{2}\to\mathrm{T}\times\mathrm{T}$ defined by

$\chi(\ell,m)\,=\,\mathcal{R}_{\min\\{\ell,m\\},\max\\{\ell,m\\}}$

is a finite coloring of $[D_{2}]^{2}$. By the infinite version of Ramsey’s
Theorem, there is some particular
$\mathcal{R}\subseteq\mathrm{T}\times\mathrm{T}$ and an infinite
$D_{3}\subseteq D_{2}$ such that if $\ell,m\in D_{3}$ and $\ell<m$, then
$\mathcal{R}_{\ell,m}=\mathcal{R}$.

This completes our trimming down of the set $D_{0}$. Let $D=D_{3}$, and let
$m_{k}$ denote the $k^{\mathrm{th}}$ member of $D_{3}$.

Observation: If $k,\ell,m\in D_{3}$ with $k<\ell<m$, then

$\mathcal{R}\,=\,\mathcal{R}_{k,m}\,=\,\mathcal{R}_{\ell,m}\circ\mathcal{R}_{k,\ell}\,=\,\mathcal{R}\circ\mathcal{R}.$

Consequently, $\mathcal{R}$ is a transitive relation, and
$\langle\mathrm{T},\mathcal{R}\rangle$ is a transitive digraph.

As with any digraph, let us say a nonempty $\text{X}\subseteq\mathrm{T}$ is a
_clique_ if $(v,w)\in\mathcal{R}$ for any $v,w\in\text{X}$, and X is maximal
with respect to this property. (We do not require, though some definitions of
“clique” in the literature do, that $|\text{X}|>2$; so for example, if
$(v,v)\in\mathcal{R}$, and there is no $w\neq v$ such that
$(v,w)\in\mathcal{R}$ and $(w,v)\in\mathcal{R}$, then $\\{v\\}$ is a clique.)

Observation: $v\in\mathrm{T}$ belongs to a clique in
$\langle\mathrm{T},\mathcal{R}\rangle$ if and only if $(v,v)\in\mathcal{R}$.

_Proof of Observation:_ Note on the one hand that if
$\text{X}\subseteq\mathrm{T}$ is a clique then $(v,w)\in\mathcal{R}$ for all
$v,w\in\text{X}$, and in particular $(v,v)\in\mathcal{R}$ for any
$v\in\text{X}$. Conversely, if $(v,v)\in\mathcal{R}$ then $\\{v\\}$ satisfies
the defining property of a clique, so any maximal superset of $\\{v\\}$ with
this property is a clique.

Observation: Every $v\in\mathrm{T}$ has nonzero out-degree in
$\langle\mathrm{T},\mathcal{R}\rangle$; i.e., there is some $w\in\mathrm{T}$
such that $(v,w)\in\mathcal{R}$.

_Proof of Observation:_ Fix any $v\in\mathrm{T}$, and fix any $\ell,m\in D$
with $\ell<m$. Then $v\in\mathrm{T}=\mathrm{T}^{\bar{a}}_{\ell}$, and this
means there is some $x\in\mathcal{T}^{\bar{a}}_{\ell}$ such that $x(\ell)=v$.
But then $x\\!\restriction\\!(\omega\setminus m)\in\mathcal{T}^{\bar{a}}_{m}$,
and $\langle x(\ell),x(\ell+1),\dots,x(m)\rangle$ is a walk in
$\langle\mathcal{B},\xrightarrow{\scalebox{0.75}{$\,{}_{\mathcal{B}}\,$}}\rangle$
from $v$ to some $w=x(m)\in\mathrm{T}^{\bar{a}}_{m}=\mathrm{T}$, and this walk
projects onto $\langle a_{\ell},a_{\ell+1},\dots,a_{m}\rangle$. In other
words, this walk witnesses $(v,w)\in\mathcal{R}$.

If $v\in\mathrm{T}$ and X is a clique in
$\langle\mathrm{T},\mathcal{R}\rangle$, let us say $v$ is _attracted_ to X if
there is a walk in $\langle\mathrm{T},\mathcal{R}\rangle$ from $v$ to a member
of X.

Observation: Every $v\in\mathrm{T}$ is attracted to a clique. In particular,
it follows that $\langle\mathrm{T},\mathcal{R}\rangle$ has cliques.

_Proof of Observation:_ Fix $v\in\mathrm{T}$. The previous observation implies
there is a walk in $\langle\mathrm{T},\mathcal{R}\rangle$ beginning at $v$ and
having length $>\\!|\mathrm{T}|$. Because of the length of the walk, there is
some $w\in\mathrm{T}$ appearing more than once in the walk. Because
$\mathcal{R}$ is transitive, this implies $(w,w)\in\mathcal{R}$. But this
means $w$ is part of a clique, and some initial segment of our walk (going
from $v$ to $w$) witnesses that $v$ is attracted to that clique.

Given $i>m_{0}$, we now define two functions $\vec{P}^{i}$ and $\vec{F}^{i}$
(for _Past_ and _Future_), each of which maps $\mathcal{P}(\mathrm{T})$ into
$\mathcal{P}(\mathcal{B})$. If $\text{X}\subseteq\mathrm{T}$, then
$\vec{P}^{i}(\text{X})$ and $\vec{F}^{i}(\text{X})$ are denoted by
$\vec{P}^{i}_{\text{X}}$ and $\vec{F}^{i}_{\text{X}}$, respectively. Given
$k\in\omega$ such that $m_{k}<i\leq m_{k+1}$, define:

$\displaystyle b\in\vec{P}^{i}_{\text{X}}\quad\Leftrightarrow\quad$ there is a
walk $\langle b_{m_{k}},b_{m_{k}+1},\dots,b_{i}\rangle$ in
$\langle\mathcal{B},\xrightarrow{\scalebox{0.75}{$\,{}_{\mathcal{B}}\,$}}\rangle$
from some $b_{m_{k}}\in\text{X}$ to $b_{i}=b$ that projects onto $\langle
a_{m_{k}},a_{m_{k}+1},\dots,a_{i}\rangle$.
$\displaystyle\vphantom{f^{f^{f^{f^{f}}}}}b\in\vec{F}^{i}_{\text{X}}\quad\Leftrightarrow\quad$
there is a walk $\langle b_{i},b_{i+1},\dots,b_{m_{k+1}}\rangle$ in
$\langle\mathcal{B},\xrightarrow{\scalebox{0.75}{$\,{}_{\mathcal{B}}\,$}}\rangle$
from $b_{i}=b$ to some $b_{m_{k+1}}\in\text{X}$ that projects onto $\langle
a_{i},a_{i+1},\dots,a_{m_{k+1}}\rangle$.

Observation: Let $b\in\mathrm{T}$ and
$\text{X}\subseteq\mathcal{P}(\mathrm{T})$. Then
$b\in\vec{F}^{m_{k}}_{\text{X}}$ if and only if $(b,b^{\prime})\in\mathcal{R}$
for some $b^{\prime}\in\text{X}$ (i.e., $b$ is attracted to X). Similarly,
$b\in\vec{P}^{m_{k}}_{\text{X}}$ if and only if $(b^{\prime},b)\in\mathcal{R}$
for some $b^{\prime}\in\text{X}$.

In particular, this observation shows that $\vec{P}^{m}$ and $\vec{F}^{m}$ are
constant on $D$, and are essentially just a reformulation of the relation
$\mathcal{R}$.

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

  * $(\ddagger)$

There is at least one clique X in $\langle\mathrm{T},\mathcal{R}\rangle$, and
there exist $b_{\text{st}},b_{\text{fin}}\in\text{X}$, such that for every
edge $e$ in $\xrightarrow{\scalebox{0.75}{$\,{}_{\mathcal{B}}\,$}}$, there are
infinitely many $k\in\omega$ such that for some $\ell>k$ there is a walk
$\langle b_{m_{k}},b_{m_{k}+1},b_{m_{k}+2},\dots,b_{m_{\ell}}\rangle$ in
$\langle\mathcal{B},\xrightarrow{\scalebox{0.75}{$\,{}_{\mathcal{B}}\,$}}\rangle$
from $b_{m_{k}}=b_{\text{st}}$ to $b_{m_{\ell}}=b_{\text{fin}}$ such that this
walk projects onto $\langle
a_{m_{k}},a_{m_{k}+1},a_{m_{k}+2},\dots,a_{m_{\ell}}\rangle$, and such that
$(b_{i},b_{i+1})=e$ for some $i$ with $m_{k}\leq i<m_{\ell}$.

We show that this statement $(\ddagger)$ is a sharp dividing line between
alternaties $(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 a diligent walk through
$\langle\mathcal{B},\xrightarrow{\scalebox{0.75}{$\,{}_{\mathcal{B}}\,$}}\rangle$
by recursion. At step $n$ of the recursion, we add not just one point to our
walk, but a string of points with indices between some $m_{\ell_{n-1}}$ and
$m_{\ell_{n}}$.

Fix an enumeration of $\xrightarrow{\scalebox{0.75}{$\,{}_{\mathcal{B}}\,$}}$,
say $\xrightarrow{\scalebox{0.75}{$\,{}_{\mathcal{B}}\,$}}\
=\\{e_{0},e_{1},\dots,e_{M-1}\\}$. Let X be a clique in
$\langle\mathrm{T},\mathcal{R}\rangle$ witnessing $(\ddagger)$. For the base
step of the recursion, let $\ell_{0}=0$ and let $\langle
b_{0},b_{1},b_{2},\dots,b_{m_{0}}\rangle$ be any walk in
$\langle\mathcal{B},\xrightarrow{\scalebox{0.75}{$\,{}_{\mathcal{B}}\,$}}\rangle$
ending at $b_{\text{fin}}=b_{m_{0}}$. Some such walk exists because
$\langle\mathcal{B},\xrightarrow{\scalebox{0.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_{\ell_{n-1}}}\rangle$ in
$\langle\mathcal{B},\xrightarrow{\scalebox{0.75}{$\,{}_{\mathcal{B}}\,$}}\rangle$
such that $b_{m_{\ell_{n-1}}}=b_{\text{fin}}\in\text{X}$. Let $j$ denote the
unique member of $\\{0,1,2,\dots,M-1\\}$ such that $k\equiv j$ (mod $M$).

First, because X is a clique in $\langle\mathrm{T},\mathcal{R}\rangle$ and
$b_{m_{\ell_{n-1}}},b_{\text{st}}\in\text{X}$, there is some
$m_{k_{n}}>m_{\ell_{n-1}}$ and a walk $\langle
b_{\ell_{n-1}},b_{\ell_{n-1}+1},b_{\ell_{n-1}+2}\dots,b_{k_{n}}\rangle$ in
$\langle\mathcal{B},\xrightarrow{\scalebox{0.75}{$\,{}_{\mathcal{B}}\,$}}\rangle$
from $b_{m_{\ell_{n-1}}}$ to $b_{\text{st}}=b_{k_{n}}$ that projects onto
$\langle
a_{\ell_{n-1}},a_{\ell_{n-1}+1},a_{\ell_{n-1}+2}\dots,a_{k_{n}}\rangle$. We
take this walk to define $b_{i}$ when $m_{\ell_{n-1}}<i\leq m_{k_{n}}$.

Next, because $b_{m_{k_{n}}}=b_{\text{st}}$, $(\ddagger)$ implies there is
some $m_{\ell_{n}}>m_{k_{n}}$ and a walk $\langle
b_{k_{n}},b_{k_{n}+1},b_{k_{n}+2}\dots,b_{m_{\ell_{n}}}\rangle$ in
$\langle\mathcal{B},\xrightarrow{\scalebox{0.75}{$\,{}_{\mathcal{B}}\,$}}\rangle$
from $b_{\text{st}}=b_{m_{k_{n}}}$ to $b_{\text{fin}}=b_{m_{\ell_{n}}}$ that
projects onto $\langle
a_{k_{n}},a_{k_{n}+1},a_{k_{n}+2}\dots,a_{m_{\ell_{n}}}\rangle$, and such that
$e_{j}=(b_{i},b_{i+1})$ for some $i$ with $m_{k_{n}}<i\leq m_{\ell_{n}}$. We
take this walk to define $b_{i}$ when $m_{k_{n}}<i\leq m_{\ell_{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{0.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 through
$\langle\mathcal{B},\xrightarrow{\scalebox{0.75}{$\,{}_{\mathcal{B}}\,$}}\rangle$.
Furthermore, this walk is diligent because for any given $e_{j}$ in
$\xrightarrow{\scalebox{0.75}{$\,{}_{\mathcal{B}}\,$}}$, if $n\equiv j$ (mod
$M$) then $(b_{i},b_{i+1})=e_{j}$ for some $i$ with $m_{k_{n}}<i\leq
m_{\ell_{n}}$. Thus every member of
$\xrightarrow{\scalebox{0.75}{$\,{}_{\mathcal{B}}\,$}}$ is equal to
$(b_{i},b_{i+1})$ for infinitely many $i\in\omega$. Finally, the construction
of this walk guarantees that $\phi(b_{i})=a_{i}$ for all $i\geq m_{0}$, and so
$\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 10.8, this involves
the construction of a digraph
$\langle\mathcal{C},\xrightarrow{\scalebox{0.75}{$\,{}_{\mathcal{C}}\,$}}\rangle$.

For each $i\in\omega$, let $k(i)$ denote the (unique) member of $\omega$ with
the property that $m_{k(i)}\leq i<m_{k(i)+1}$. Define

$\mathrm{S}_{i}\,=\,\mathrm{S}^{\bar{a}_{k(i)}}_{i},\qquad\text{ and
}\qquad\reflectbox{\text{S}}_{i}\,=\,\reflectbox{\text{S}}^{\bar{a}_{k(i)},m_{k(i)+1}}_{i}.$

Then, for each $k>0$, define

$\displaystyle\mathcal{L}^{k}$
$\displaystyle\,=\,\left\\{\big{(}\mathrm{S}_{i},\reflectbox{\text{S}}_{i},\vec{P}^{i},\vec{F}^{i}\big{)}\colon
m_{k}<i<m_{k+1}\right\\},$ $\displaystyle\mathcal{E}^{k}$
$\displaystyle\,=\,\left\\{\big{(}(\mathrm{S}_{i},\reflectbox{\text{S}}_{i},\vec{P}^{i},\vec{F}^{i}),(\mathrm{S}_{i+1},\reflectbox{\text{S}}_{i+1},\vec{P}^{i+1},\vec{F}^{i+1})\big{)}\colon
m_{k}<i<m_{k+1}-1\right\\},$ $\displaystyle c^{k}_{\text{in}}$
$\displaystyle\,=\,\big{(}\mathrm{S}_{m_{k}+1},\reflectbox{\text{S}}_{m_{k}+1},\vec{P}^{m_{k}+1},\vec{F}^{m_{k}+1}\big{)},$
$\displaystyle c^{k}_{\text{out}}$
$\displaystyle\,=\,\big{(}\mathrm{S}_{m_{k+1}-1},\reflectbox{\text{S}}_{m_{k+1}-1},\vec{P}^{m_{k+1}-1},\vec{F}^{m_{k+1}-1}\big{)}.$

In other words, $\langle\mathcal{L}^{k},\mathcal{E}^{k}\rangle$ is a digraph
recording the activity of the forward and backward state space sequences
between time $m_{k}$ and time $m_{k+1}$, as well as the values of the Past and
Future vectors at these times. Furthermore, we record two distinguished points
in this digraph, $c^{k}_{\text{in}}$ and $c^{k}_{\text{out}}$.

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}})$, at
least some $4$-tuples are used infinitely often. In fact, more is true: 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.
Furthermore, 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 that are used infinitely often.

For each $j\leq N$ let

$\displaystyle\mathcal{C}_{j}$
$\displaystyle\,=\,\\{j\\}\times\mathcal{L}^{k_{j}},$
$\displaystyle\mathcal{E}_{j}$
$\displaystyle\,=\,\left\\{((j,t),(j,t^{\prime}))\colon(t,t^{\prime})\in\mathcal{E}^{k_{j}}\right\\},$
$\displaystyle c^{j}_{\text{in}}$
$\displaystyle\,=\,\big{(}j,c^{k_{j}}_{\text{in}}\big{)},$ $\displaystyle
c^{j}_{\text{out}}$
$\displaystyle\,=\,\big{(}j,c^{k_{j}}_{\text{out}}\big{)}.$

In other words, these are the digraphs 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. We assume, without loss of generality, that
$\mathrm{T}\notin\bigcup_{j\leq N}\mathcal{C}_{j}$. (This is true
automatically if the vertices of $\mathcal{B}$ are labelled in a sensible
manner.)

We are now ready to define the digraph
$\langle\mathcal{C},\xrightarrow{\scalebox{0.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:

$\displaystyle x\xrightarrow{\scalebox{0.75}{$\,{}_{\mathcal{C}}\,$}}y\quad\
\Longleftrightarrow\quad\ $ $\displaystyle x,y\in\mathcal{C}_{j}\text{ and
}(x,y)\in\mathcal{E}_{j}\text{ for some $j\leq N$, or}$ $\displaystyle
x=\mathrm{T}\text{ and }y=c^{j}_{\text{in}}\text{ for some $j\leq N$, or}$
$\displaystyle x=c^{j}_{\mathrm{out}}\text{ and }y=\mathrm{T}\text{ for some
$j\leq N$}.$

$\bullet$

$\mathrm{T}$

$\bullet$$\bullet$

$\langle\mathcal{C}_{0},\mathcal{E}_{0}\rangle$

$\bullet$$\bullet$

$\langle\mathcal{C}_{1},\mathcal{E}_{1}\rangle$

$\bullet$$\bullet$

$\langle\mathcal{C}_{2},\mathcal{E}_{2}\rangle$

$\bullet$$\bullet$

$\langle\mathcal{C}_{3},\mathcal{E}_{3}\rangle$

$\dots$

Define $\psi:\mathcal{C}\to\mathcal{A}$ by setting
$\psi(\mathrm{T})=\Pi_{\phi}(\mathrm{T})=a$ and
$\psi(j,(\mathrm{S},\reflectbox{\text{S}},\vec{P},\vec{F}))=\Pi_{\phi}(\mathrm{S})=\Pi_{\phi}(\reflectbox{\text{S}})$
whenever
$(j,(\mathrm{S},\reflectbox{\text{S}},\vec{P},\vec{F}))\in\mathcal{C}_{j}$.
(To see that this last equality is true: observe that if
$(j,(\mathrm{S},\reflectbox{\text{S}},\vec{P},\vec{F}))\in\mathcal{C}_{j}$,
then
$(\mathrm{S},\reflectbox{\text{S}},\vec{P},\vec{F})=(\mathrm{S}_{i},\reflectbox{\text{S}}_{i},\vec{P}^{i},\vec{F}^{i})$
for some $i$, and this implies
$\Pi_{\phi}(\mathrm{S}_{i})=\Pi_{\phi}(\reflectbox{\text{S}}_{i})=a_{i}$.)

This completes the definition of
$\langle\mathcal{C},\xrightarrow{\scalebox{0.75}{$\,{}_{\mathcal{C}}\,$}}\rangle$
and $\psi$. To finish the proof, we need to show that
$\langle\mathcal{C},\xrightarrow{\scalebox{0.75}{$\,{}_{\mathcal{C}}\,$}}\rangle$
is strongly connected, that $\psi$ is an epimorphism from
$\langle\mathcal{C},\xrightarrow{\scalebox{0.75}{$\,{}_{\mathcal{C}}\,$}}\rangle$
to
$\langle\mathcal{A},\xrightarrow{\scalebox{0.75}{$\,{}_{\mathcal{A}}\,$}}\rangle$,
that there is a diligent walk through
$\langle\mathcal{C},\xrightarrow{\scalebox{0.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 10.8, we can verify the first three of these four
things all at once via Lemma 10.7. 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{0.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_{K}$, define $k(i)$, as above, to be the (unique) index with
$m_{k(i)}\leq n<m_{k(i)+1}$, and define $j(i)$ to be the number $\leq\\!N$
such that

$\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{)}.$

Note that this is well-defined whenever $k(i)\geq K$, i.e., whenever $i\geq
m_{K}$. For all $i\geq m_{K}$, define

$c_{i}\,=\,\begin{cases}\mathrm{T}&\text{ if }i\in D,\\\
\big{(}j(i),(\mathrm{S}_{i},\reflectbox{\text{S}}_{i},\vec{P}^{i},\vec{F}^{i})\big{)}&\text{
otherwise.}\end{cases}$

First, let us check that this sequence is a walk through
$\langle\mathcal{C},\xrightarrow{\scalebox{0.75}{$\,{}_{\mathcal{C}}\,$}}\rangle$.
For the first case, suppose $i,i+1\notin D$. Then $j(i)=j(i+1)$, and we have
$c_{i},c_{i+1}\in\mathcal{C}_{j(i)}$ and
$(c_{i},c_{i+1})\in\mathcal{E}^{j(i)}$ by the definition of
$\mathcal{E}_{j(i)}$. Hence
$c_{i}\xrightarrow{\scalebox{0.75}{$\,{}_{\mathcal{C}}\,$}}c_{i+1}$ in this
case. For the second case, suppose $i\in D$ but $i+1\notin D$. But then
$i=m_{k(i)}=m_{k(i+1)}$ and $i+1=m_{k(i)}+1$, which implies

$c_{i+1}\,=\,\big{(}j(i+1),(\mathrm{S}_{m_{k(i)}+1},\reflectbox{\text{S}}_{m_{k(i)}+1},\vec{P}^{m_{k(i)}+1},\vec{F}^{m_{k(i)}+1})\big{)}\,=\,c^{j(i)}_{\text{in}},$

while $c_{n}=\mathrm{T}$. Thus
$c_{i}\xrightarrow{\scalebox{0.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{0.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^{\prime})$ in
$\xrightarrow{\scalebox{0.75}{$\,{}_{\mathcal{C}}\,$}}$. There is some $j\leq
N$ such that either $(1)$ $(c,c^{\prime})\in\mathcal{E}_{j}$, or $(2)$
$c=\mathrm{T}$ and $c^{\prime}=c^{j}_{\text{in}}$, or $(3)$
$c=c^{j}_{\text{out}}$ and $c^{\prime}=\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^{\prime})$.
Thus $(c,c^{\prime})=(c_{i},c_{i+1})$ for arbitrarily large values of $i$.
Hence $\left\langle c_{i}\colon i\geq m_{K}\right\rangle$ is a diligent walk.

Next, we claim that this walk projects onto $\left\langle a_{i}\colon i\geq
m_{K}\right\rangle$. If $i\in D$, then $a_{i}=a$ and
$\psi(c_{i})=\Pi_{\phi}(\mathrm{T})=a$, so $a_{i}=\psi(c_{i})$. If $i\notin
D$, then again

$\displaystyle\Pi_{\phi}(c_{i})$
$\displaystyle\,=\,\psi\big{(}j(i),(\mathrm{S}_{i},\reflectbox{\text{S}}_{i},\vec{P}^{i},\vec{F}^{i})\big{)}\,=\,\Pi_{\phi}(\mathrm{S}_{i})\,=\,\Pi_{\phi}(\reflectbox{\text{S}}_{i})\,=\,a_{i}.$

Because $\left\langle a_{i}\colon i\in\omega\right\rangle$ is a diligent walk
through
$\langle\mathcal{A},\xrightarrow{\scalebox{0.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{0.75}{$\,{}_{\mathcal{A}}\,$}}\rangle$.
And we have just showed that $\left\langle c_{i}\colon i\geq
m_{K}\right\rangle$ is a diligent walk through
$\langle\mathcal{C},\xrightarrow{\scalebox{0.75}{$\,{}_{\mathcal{C}}\,$}}\rangle$
that projects onto this diligent walk. By Lemma 10.7,
$\langle\mathcal{C},\xrightarrow{\scalebox{0.75}{$\,{}_{\mathcal{C}}\,$}}\rangle$
is strongly connected, and $\psi$ is an epimorphism from
$\langle\mathcal{C},\xrightarrow{\scalebox{0.75}{$\,{}_{\mathcal{C}}\,$}}\rangle$
to
$\langle\mathcal{A},\xrightarrow{\scalebox{0.75}{$\,{}_{\mathcal{A}}\,$}}\rangle$.

Now that we know
$\langle\mathcal{C},\xrightarrow{\scalebox{0.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{0.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{0.75}{$\,{}_{\mathcal{C}}\,$}}\rangle$
that almost projects onto $\left\langle a_{i}\colon i\in\omega\right\rangle$.

It remains to show that the failure of $(\ddagger)$ implies $\psi$ is
incompatible with $\phi$. We prove this by proving the contrapositive: if
$\psi$ and $\phi$ are compatible, then $(\ddagger)$ holds.

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

$\langle\mathcal{A},\xrightarrow{\scalebox{0.75}{$\,{}_{\mathcal{A}}\,$}}\rangle$$\langle\mathcal{B},\xrightarrow{\scalebox{0.75}{$\,{}_{\mathcal{B}}\,$}}\rangle$$\langle\mathcal{C},\xrightarrow{\scalebox{0.75}{$\,{}_{\mathcal{C}}\,$}}\rangle$$\langle\mathcal{W},\xrightarrow{\scalebox{0.75}{$\,{}_{\mathcal{W}}\,$}}\rangle$$\psi$$\phi$$\bar{\psi}$$\bar{\phi}$

For each $c\in\mathcal{C}$, define

$\reflectbox{\text{S}}(c)\,=\,\begin{cases}\mathrm{T}&\text{ if
}c=\mathrm{T},\\\ \hskip 0.56905pt\reflectbox{\text{S}}&\text{ if
$c=(j,(\mathrm{S},\reflectbox{\text{S}},\vec{P},\vec{F}))\in\mathcal{C}_{j}$
for some $j\leq N$.}\end{cases}$

and similarly, define

$\mathrm{S}(c)\,=\,\begin{cases}\mathrm{T}&\text{ if }c=\mathrm{T},\\\ \hskip
0.56905pt\mathrm{S}&\text{ if
$c=(j,(\mathrm{S},\reflectbox{\text{S}},\vec{P},\vec{F}))\in\mathcal{C}_{j}$
for some $j\leq N$.}\end{cases}$

Observe that $\mathrm{S}(c),\reflectbox{\text{S}}(c)\subseteq\mathcal{B}$ for
every $c\in\mathcal{C}$, so that the statement of the following claim at least
makes sense.

Claim: Suppose $\langle w_{0},w_{1},\dots,w_{\ell}\rangle$ is a walk in
$\langle\mathcal{W},\xrightarrow{\scalebox{0.75}{$\,{}_{\mathcal{W}}\,$}}\rangle$
and $\bar{\psi}(w_{\ell})=\mathrm{T}$. Then $\bar{\phi}(w_{i})\in\hskip
0.56905pt\reflectbox{\text{S}}(\bar{\psi}(w_{i}))$ for all $i<\ell$.

_Proof of Claim:_ We prove something slightly stronger than what is claimed.
To state the stronger assertion, first define

$\reflectbox{\text{S}}^{\prime}(c)\,=\,\begin{cases}\phi^{-1}(a)&\text{ if
}c=\mathrm{T},\\\ \reflectbox{\text{S}}(c)&\text{ if
$c\neq\mathrm{T}$.}\end{cases}$

Observe that $\mathrm{T}\subseteq\phi^{-1}(a)$, and thus
$\reflectbox{\text{S}}(c)\subseteq\reflectbox{\text{S}}^{\prime}(c)$ for all
$c\in\mathcal{C}$. The stronger claim that we prove is:
$\bar{\phi}(w_{i})\in\hskip
0.56905pt\reflectbox{\text{S}}^{\prime}(\bar{\psi}(w_{i}))$ for all
$i\leq\ell$, and if $i<\ell$ then $\bar{\phi}(w_{i})\in\hskip
0.56905pt\reflectbox{\text{S}}(\bar{\psi}(w_{i}))$.

This stronger claim is proved by a backward inductive argument: we take
$i=\ell$ as the base case, and prove for the inductive step that if $i>0$ and
$\bar{\phi}(w_{i})\in\hskip
0.56905pt\reflectbox{\text{S}}^{\prime}(\bar{\psi}(w_{i}))$, then
$\bar{\phi}(w_{i-1})\in\hskip
0.56905pt\reflectbox{\text{S}}(\bar{\psi}(w_{i-1}))\subseteq\reflectbox{\text{S}}^{\prime}(\bar{\psi}(w_{i-1}))$.

For the base case $i=\ell$, we have

$\phi\circ\bar{\phi}(w_{\ell})\,=\,\psi\circ\bar{\psi}(w_{\ell})\,=\,\psi(\mathrm{T})\,=\,a,$

which means that
$\bar{\phi}(w_{\ell})\in\phi^{-1}(a)=\reflectbox{\text{S}}^{\prime}(\mathrm{T})=\reflectbox{\text{S}}^{\prime}(\bar{\psi}(w_{\ell}))$.

For the inductive step, fix $i$ with $0<i\leq\ell$ and suppose, as an
inductive hypothesis, that
$\bar{\psi}(w_{i})\in\reflectbox{\text{S}}^{\prime}(\bar{\psi}(w_{i}))$.
Because $\bar{\psi}$ is an epimorphism,
$\bar{\psi}(w_{i-1})\xrightarrow{\scalebox{0.75}{$\,{}_{\mathcal{C}}\,$}}\bar{\psi}(w_{i})$.
By our definition of
$\langle\mathcal{C},\xrightarrow{\scalebox{0.75}{$\,{}_{\mathcal{C}}\,$}}\rangle$,
this means there is some $j\leq N$ and some $p$ with $m_{k_{j}}<p\leq
m_{k_{j}+1}$ such that
$\reflectbox{\text{S}}^{\prime}(\bar{\psi}(w_{i}))=\reflectbox{\text{S}}_{p}$
and $\reflectbox{\text{S}}(\bar{\psi}(w_{i-1}))=\reflectbox{\text{S}}_{p-1}$.
(Note that this is true even when $\bar{\psi}(w_{i})=\mathrm{T}$, by taking
$p=m_{k_{j+1}}$, and when $\bar{\psi}(w_{i-1})=\mathrm{T}$, by taking
$p=m_{k_{j}}$.) But then

$\phi\circ\bar{\phi}(w_{i})\,=\,\psi\circ\bar{\psi}(w_{i})\,=\,\Pi_{\phi}(\reflectbox{\text{S}}_{p})\,=\,a_{p}\text{,
and}\,$
$\phi\circ\bar{\phi}(w_{i-1})\,=\,\psi\circ\bar{\psi}(w_{i-1})\,=\,\Pi_{\phi}(\reflectbox{\text{S}}_{p-1})\,=\,a_{p-1}.$

In particular, $\bar{\phi}(w_{i-1})\in\phi^{-1}(a_{p-1})$. Furthermore,
$\bar{\phi}(w_{i-1})\xrightarrow{\scalebox{0.75}{$\,{}_{\mathcal{B}}\,$}}\bar{\phi}(w_{i})$
because $\bar{\phi}$ is an epimorphism; and
$\bar{\phi}(w_{i})\in\reflectbox{\text{S}}^{\prime}(\bar{\psi}(w_{i}))$ by the
inductive hypothesis. But then by Lemma 10.10,

$\reflectbox{\text{S}}_{p-1}\,=\,\left\\{x\in\phi^{-1}(a_{p-1})\colon\exists
y\in\reflectbox{\text{S}}_{p}\text{ such that
}x\xrightarrow{\scalebox{0.75}{$\,{}_{\mathcal{B}}\,$}}y\right\\},$

so this means that $\bar{\phi}(w_{i-1})\in\reflectbox{\text{S}}_{p-1}$. If
$p-1\neq m_{k_{j}}$, then
$\reflectbox{\text{S}}_{p-1}=\reflectbox{\text{S}}(\bar{\psi}(w_{i-1}))$ and
we are done. If $p-1=m_{k_{j}}$, then
$\reflectbox{\text{S}}_{p-1}=\mathrm{T}$, by our choice of the set $D$. So in
this case too,
$\bar{\phi}(w_{i-1})\in\mathrm{T}=\reflectbox{\text{S}}(\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}$.

_Proof of Claim:_ Fix $w\in\mathcal{W}$ with $\bar{\psi}(w)=\mathrm{T}$.
Because
$\langle\mathcal{W},\xrightarrow{\scalebox{0.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}$. The previous claim then gives