Minimal Walks, Oscillation, and L- and S-Spaces

If $\alpha =\beta$ or $\beta =\gamma$, one upper and lower trace is empty by [F1], so both concatenation identities reduce to equality with the other trace. Hence suppose $\alpha <\beta <\gamma$ and $L(\beta ,\gamma )<L(\alpha ,\beta )$.

Let $\delta$ be a nonzero limit and $0<\xi <\delta$. The first lower-trace value for the walk from $\delta$ to $\xi$ is $\max (C_{\delta }\cap \xi )$, and all later values are running maxima containing that first intersection. Hence $\min L(\xi ,\delta )=\max (C_{\delta }\cap \xi )$. The same equality is harmless at $\xi =0$ under the explicit zero convention, although limits only concern a final tail.

Every member of $L(\alpha ,\beta )$ is below $\alpha$, so the separation hypothesis puts every member of $L(\beta ,\gamma )$ below $\alpha$. If $\zeta$ is a node of $\mathrm{Tr}(\beta ,\gamma )$, the running maximum that records $C_{\zeta }\cap \beta$ occurs in $L(\beta ,\gamma )$ or is bounded by a later recorded maximum. Thus $C_{\zeta }\cap \beta \subseteq \alpha$, and therefore $C_{\zeta }\cap \alpha =C_{\zeta }\cap \beta$. In particular $C_{\zeta }$ has no point in $[\alpha ,\beta )$, so $\min (C_{\zeta }\setminus \alpha )=\min (C_{\zeta }\setminus \beta )$.

Given $\eta <\delta$, cofinality of $C_{\delta }$ gives $c\in C_{\delta }$ with $\eta <c<\delta$. Since $\delta$ is a limit, ${\xi }_0=c+1<\delta$. Whenever ${\xi }_0<\xi <\delta$, one has $c\in C_{\delta }\cap \xi$, and step 1.2 gives $\eta <c\le \min L(\xi ,\delta )<\delta$. This is exactly the ordinal-limit assertion in clause 2.

Step 2.1 says that the walk aimed at $\alpha$ makes exactly the same choices as the walk aimed at $\beta$ until it reaches $\beta$. From that node onward its recursion is the walk from $\beta$ to $\alpha$. This proves the asserted upper-trace concatenation, with no repeated $\beta$ because the first trace excludes its terminal point and the second includes its starting point.

Along the first segment, step 2.1 identifies every initial intersection and hence every running maximum with the corresponding value in $L(\beta ,\gamma )$. All those values are below every value of $L(\alpha ,\beta )$. Consequently, after the walk reaches $\beta$, taking running maxima for the continued walk produces exactly the values of $L(\alpha ,\beta )$; no earlier value suppresses or changes one. The lower trace is therefore the ordered union $L(\beta ,\gamma )\cup L(\alpha ,\beta )$.

Steps 3.1 and 4.1 prove the two concatenation identities, including the endpoint reductions in step 1.1, and step 2.2 proves the exact limit-target control from step 1.2.

Fix $n<\omega$ and set $D=\{\alpha <\beta :e_{\beta }(\alpha )\le n\text{ or }{e}_{\beta }(\alpha )\mathrm{\ne }{e}_{{\beta }^{\mathrm{\prime }}}(\alpha )\}$. We prove that $D$ has no limit point at or below $\beta$.

Let $0<\delta \le \beta$ be a limit ordinal. The two traces $\mathrm{Tr}(\delta ,\beta )$ and $\mathrm{Tr}(\delta ,{\beta }^{\mathrm{\prime }})$ are finite. Local finiteness makes each $C_{\zeta }\cap \delta$ finite for a trace node $\zeta >\delta$. Choose ${\delta }_0<\delta$ above every member of all these intersections, and let $N$ be the maximum of $n$ and their finitely many cardinalities. Cofinality of $C_{\delta }$ permits enlarging ${\delta }_0$ so that $\mathrm{\mid }{C}_{\delta }\cap \alpha \mathrm{\mid }>N$ whenever ${\delta }_0<\alpha <\delta$.

For ${\delta }_0<\alpha <\delta$, no trace node above $\delta$ has a $C$-point in $[\alpha ,\delta )$. Hence the walks toward $\alpha$ first follow the walks toward $\delta$ and then the walk from $\delta$ to $\alpha$; this is the same splice calculation as [F2]. Moreover, every local weight on either upper segment is its stabilized value $\mathrm{\mid }{C}_{\zeta }\cap \delta \mathrm{\mid }\le N$, whereas the lower segment contains the weight $\mathrm{\mid }{C}_{\delta }\cap \alpha \mathrm{\mid }>N$.

Taking the maxima in [F1] therefore gives $e_{\beta }(\alpha )=e_{\delta }(\alpha )=e_{{\beta }^{\mathrm{\prime }}}(\alpha )>n$ for every ${\delta }_0<\alpha <\delta$. Such $\alpha$ is not in $D$, so $\delta$ is not a limit point of $D$. Zero and successor ordinals are not limit points from below, so $D$ has no limit point at or below $\beta$.

If $D$ were infinite, its well-order would recursively give a strictly increasing $\omega$-sequence from $D$. Its supremum is a nonzero limit ordinal $\delta \le \beta$ and every final segment below $\delta$ meets $D$, contradicting step 3.1. Hence $D$ is finite.

The set $\{\alpha <\beta :e_{\beta }(\alpha )=n\}$ lies in $D$, so every fiber of $e_{\beta }$ is finite. Taking, for example, $n=0$, the disagreement set between $e_{\beta }$ and $e_{{\beta }^{\mathrm{\prime }}}\upharpoonright \beta$ also lies in $D$ and is finite.

Step 5.1 proves finite-to-one behavior and coherence simultaneously. It also covers $\beta =0$, where the domain and disagreement set are empty, and $\beta ={\beta }^{\mathrm{\prime }}$, where disagreement is empty.

Fix a sufficiently large regular $\mathrm{\Theta }$ and Skolem functions for $H(\mathrm{\Theta })$. The ordinals $\delta =M\cap {\omega }_1$ obtained from countable $M\prec H(\mathrm{\Theta })$ containing $A,B$ and all fixed walk data contain a club: Skolem hulls of successively larger countable ordinal sets give unboundedly many such cuts, while the union of an increasing $\omega$-chain of such hulls is elementary and has cut the supremum of their cuts. This is the standard club-of-cuts refinement of [F4], and is closed and unbounded in the sense of [F5]. Fix such $M$ and put $\delta =M\cap {\omega }_1$. Notice that every $x\in M\cap {\omega }_1$ is below $\delta$, while $\delta \mathrm{\notin }M$.

Suppose first that $R$ is equality, and fix $a\in A\setminus \delta$, $b\in B\setminus \delta$. By coherence in [F1], there is ${\gamma }_0<\delta$ above every $L(\delta ,b(j))$ and above all disagreements below $\delta$ among the finitely many pairs $e_{a(i)},e_{b(j)}$. Hence $e_{a(i)}(\xi )=e_{b(j)}(\xi )$ whenever ${\gamma }_0<\xi <\delta$. By the limit clause of [F2], choose $\gamma <\delta$ so that $\gamma <\xi <\delta$ implies ${\gamma }_0<\min L(\xi ,\delta )$.

We repeatedly use the following reflection observation. If $X\subseteq {\omega }_1$ belongs to $M$ and $\delta \in X$, then $X$ is uncountable: otherwise elementarity provides in $M$ an enumeration of $X$ by $\omega$, whence $X\subseteq M$ and $\delta \in M$, a contradiction. Thus $X$ is unbounded in ${\omega }_1$. Likewise, an uncountable $X\in M$ has $X\cap \delta$ unbounded in $\delta$, by elementarity applied to arbitrarily large members of $X$.

For the strict branch, let $E$ be the set of limit $\nu <{\omega }_1$ with the following property: for every $a^0\in A\setminus \nu$, ${\nu }_0<\nu$, $\epsilon <{\omega }_1$, $n<\omega$, and finite $K\subseteq {\omega }_1\setminus \nu$, some $a^1\in A\setminus \epsilon$ satisfies ${\nu }_0\le \mathrm{\Delta }(e_{a^0(i)},e_{a^1(i)})$ and $e_{a^1(i)}(\xi )>n$ for every $i<k$ and $\xi \in K$. This set is definable from $A$ and the fixed sequence, so $E\in M$.

Let $X$ consist of those ${\delta }^{+}<{\omega }_1$ for which some $a^{+}\in A\setminus {\delta }^{+}$ and $b^{+}\in B\setminus {\delta }^{+}$ simultaneously preserve each $e_{a(i)}$ and $e_{b(j)}$ below ${\gamma }_0$, agree coordinatewise on $({\gamma }_0,{\delta }^{+})$, satisfy ${\gamma }_0<\min L(\xi ,{\delta }^{+})$ and $\mu (\xi ,{\delta }^{+})(\min L(\xi ,{\delta }^{+}))=w_{{\delta }^{+}}=w_{\delta }$ for $\gamma <\xi <{\delta }^{+}$, and satisfy $\mu ({\delta }^{+},b^{+}(j))=\mu (\delta ,b(j))$ for every $j<l$. All parameters in this definition belong to $M$. The space $C(2^{\omega },\omega )$ is countable and belongs to $M$, so $w_{\delta }\in M$. Each $L(\delta ,b(j))$ and labelled trace $\mu (\delta ,b(j))$ is finite with ordinal entries below $\delta$ and labels in that countable space, hence is an element of $M$. Finally the restrictions of the $e$-functions below ${\gamma }_0$ are finite modifications, by [F1], of restrictions coded in $M$. Thus $X\in M$ without using either $\delta$ or $b$ itself as a parameter. Taking ${\delta }^{+}=\delta$, $a^{+}=a$, and $b^{+}=b$ shows $\delta \in X$; the trace and label requirements are [F2] and the first-label clause retained in [F3]. By step 2.1 choose ${\delta }^{+}\in X$ above $\delta$, with witnesses $a^{+},b^{+}$.

The cut $\delta$ belongs to $E$. Indeed, for given data at $\delta$, finite-to-one behavior lets us enlarge ${\nu }_0<\delta$ above every $\xi <\delta$ at which some $e_{a^0(i)}(\xi )\le n$. The restriction tuple $⟨e_{a^0(i)}\upharpoonright {\nu }_0:i<k⟩$ belongs to $M$ by coherence. The definable set of ordinals $\eta$ for which some $a^1\in A\setminus \eta$ has these restrictions and has all values above $n$ on $({\nu }_0,\eta )$ belongs to $M$ and contains $\delta$ with witness $a^0$. Step 2.1 makes it unbounded, so choose such $\eta$ above $\epsilon$ and $\max K$ (with no maximum needed when $K$ is empty). Its witness $a^1$ proves the defining demand. Hence $\delta \in E$, and step 2.1 also makes $E$ uncountable.

Put $L^{+}=L(\delta ,{\delta }^{+})$. It is nonempty because $\delta <{\delta }^{+}$. Its minimum exceeds ${\gamma }_0$, and [F2] splices it above the common old trace $L({\delta }^{+},b^{+}(j))=L(\delta ,b(j))$. Preservation below ${\gamma }_0$ gives the two strict $\mathrm{\Delta }$ bounds; agreement on $L^{+}$ gives clause 3. The equality of the old labelled traces gives clause 4, and the label at the new minimum is $w_{{\delta }^{+}}=w_{\delta }$, giving clause 5. Thus all five conclusions hold in the equality branch.

Fix $a\in A\setminus \delta$ and $b\in B\setminus \delta$. Choose ${\gamma }_0\in E\cap \delta$ above every old trace $L(\delta ,b(j))$, possible by steps 2.1 and 3.2, and then choose $\gamma <\delta$ by [F2] as in step 1.2. Reflecting exactly the finite restrictions, trace-tail and labelled-trace type used in step 3.1, but requiring the candidate cut to be a limit, gives a limit ${\delta }^{+}>\delta$ and $b^{+}\in B\setminus {\delta }^{+}$ such that the $e_b$-restrictions below ${\gamma }_0$ agree, ${\gamma }_0<\min L(\xi ,{\delta }^{+})$ with first label $w_{{\delta }^{+}}=w_{\delta }$ for $\gamma <\xi <{\delta }^{+}$, and $\mu ({\delta }^{+},b^{+}(j))=\mu (\delta ,b(j))$.

Put $L^{+}=L(\delta ,{\delta }^{+})$ and let $n$ be the maximum of the finitely many values $e_{b^{+}(j)}(\xi )$ for $j<l$ and $\xi \in L^{+}$. Apply the defining property of ${\gamma }_0\in E$ with $a^0=a$, a bound ${\nu }_0<{\gamma }_0$ above every old trace, $K=L^{+}$, and $\epsilon =\delta$. It gives $a^{+}\in A\setminus \delta$ preserving every $e_{a(i)}$ on the old trace and satisfying $e_{a^{+}(i)}(\xi )>n\ge e_{b^{+}(j)}(\xi )$ on $L^{+}$. The preservation of $b$ below ${\gamma }_0$, the splice calculation, and the label calculation from step 4.1 now verify clauses 1, 2, 4 and 5; the displayed strict inequality verifies clause 3.

The completed equality and strict branches cover the two and only two allowed relations. The club of cuts from step 1.1 is independent of the later choices of $a,b,R$, so it is the required $D$. No choice is used after selecting the Skolem functions and fixed data; those ZFC selections are precisely the declared AC dependency.

Fix Skolem functions for a sufficiently large $H(\mathrm{\Theta })$. The cuts $M\cap {\omega }_1$ of countable elementary Skolem hulls containing the fixed parameters form a club $C$: larger countable ordinal parameter sets give unboundedly many cuts, and unions of increasing $\omega$-chains give closure. Intersect $C$ with the club supplied by F1. By F3 and F7 this intersection meets the stationary set $\{\delta :w_{\delta }=w\}$. Choose $M$ whose cut $\delta =M\cap {\omega }_1$ is such a point. This is the sole model-selection use of AC.

Choose initial $a\in A$ and $b\in B$ with every coordinate strictly above $\delta$; only finitely many members of either pairwise-disjoint family can contain $\delta$. Apply the strict branch of F1 to this pair and call its outputs $a_0,b_0$. The appended nonempty block is the final part of every $L(\delta ,b_0(j))$, and F1 makes the comparison strict on that block. Hence $e_{a_0(i)}(\max L(\delta ,b_0(j)))>e_{b_0(j)}(\max L(\delta ,b_0(j)))$ for all $i,j$.

Suppose $a_m,b_m$ have been chosen, the previously marked points lie below both first-disagreement bounds to the next stage, and the last point of $L(\delta ,b_m(j))$ has $e_{a_m(i)}>e_{b_m(j)}$ for every $i,j$. Apply [F1] first with equality, producing a common nonempty block $K_m^{=}$ on which the new $e$-values agree, and then to that output with strict inequality, producing a common nonempty block $K_m^{>}$ on which the next $a$-values exceed the next $b$-values. Put ${\xi }_m=\min K_m^{>}$. The two trace splices give $L(\delta ,b_m(j))<K_m^{=}<K_m^{>}$, independently of $j$, and both new minima have label $w_{\delta }=w$.

On the old trace, the first-disagreement bounds preserve every comparison. At the first point of $K_m^{=}$ the previous comparison is strict $>$ and the new comparison is equality, so [F2] creates no downward crossing. Comparisons remain equality through that block. At ${\xi }_m$, equality at its predecessor changes to strict $>$, so exactly ${\xi }_m$ is added to every coordinatewise oscillation set; the comparison stays strict through $K_m^{>}$, so no other new crossing appears. Label restriction in [F1] preserves all old marked labels and assigns $w$ to ${\xi }_m$.

Finite induction therefore produces sequences $a_m,b_m$ above $\delta$ and increasing ${\xi }_m$ with the seven invariants used in Moore's proof: proper common trace extension, one new oscillation, preservation below the first-disagreement bounds, a terminal strict comparison, old-label restriction, and label $w$ at every marked point.

Fix $n<\omega$. By [F4], choose ${\gamma }_0<\delta$ above every $L(\delta ,b_n(j))$ and every disagreement below $\delta$ between $e_{b_m(j)}$ and $e_{b_{m^{\mathrm{\prime }}}(j)}$ for $m,m^{\mathrm{\prime }}\le n$. Put ${\gamma }_1=\max {\bigcup }_{j<l}L(\delta ,b_n(j))$. For each $i<k$, the restriction $r_i=e_{a_n(i)}\upharpoonright ({\gamma }_1+1)$ belongs to $M$: the corresponding restriction of $e_{{\gamma }_1+1}$ belongs to $M$, and [F4] says that $r_i$ is a finite modification of it. Hence $S=\{a\in A:(\mathrm{\forall }i<k)e_{a(i)}\upharpoonright ({\gamma }_1+1)=r_i\}$ belongs to $M$. It contains $a_n\mathrm{\notin }M$, so it is uncountable; if it were countable, an enumeration in $M$ would put every member of $S$ in $M$.

By the limit law in [F5], choose $\eta <\delta$ such that $\eta <\xi <\delta$ implies ${\gamma }_0<\min L(\xi ,\delta )$. Since $S$ is an uncountable pairwise-disjoint family and $\eta$ is countable, some member of $S$ has all coordinates above $\eta$; this assertion has parameters in $M$, so elementarity gives such an $a\in S\cap M$. Thus $a<\delta$, ${\gamma }_0<L(a(i),\delta )$, and the definition of $S$ gives $L(\delta ,b_n(j))<\mathrm{\Delta }(e_{a(i)},e_{a_n(i)})$ for every $i,j$. Since every $b_m$ lies above $\delta$, one also has $a<b_m$ for all $m\le n$.

The inequalities in step 7.1 let [F5] splice every trace through $\delta$, and [F3] gives the corresponding labelled splice $\mu (a(i),b_m(j))=\mu (a(i),\delta )\cup \mu (\delta ,b_m(j))$. On $L(a(i),\delta )$ the functions $e_{b_m(j)}$ do not depend on $m$, by the choice of ${\gamma }_0$; on $L(\delta ,b_m(j))$, step 5.1 added exactly the marked oscillations and preserved their labels. The terminal comparison on the first piece is strict, so the splice boundary creates no further $\le$-to-$>$ oscillation. Hence clauses 2--4 hold, while step 7.1 gives clause 1. For $n=0$ the same reflection chooses $a$ and all unions over marked points are empty.

Since the recursively chosen sequence $⟨b_m:m<\omega ⟩$ is fixed before $n$ is specified, step 8.1 proves the required quantifier order. No coordinate assignment was introduced: the conclusion holds for all $i<k,j<l$ simultaneously.

Choose distinct primes $q_i>8$ for $i<k$. For every $a\in A$, the finitely many distinct Cantor points $z_{a(i)}$ supplied by F3 have pairwise-disjoint clopen neighborhoods, so some continuous $w_a:2^{\omega }\to \omega$ satisfies $w_a(z_{a(i)})=q_i$ for all $i<k$. There are only countably many continuous integer-valued maps on Cantor space. By F5, one value $w$ occurs for an uncountable subfamily; replace $A$ by that subfamily.

Put $Q={\prod }_{i<k}{q}_i$ and $N=6Q$. Apply [F1] with this $w$ and block length $N$. It gives $a\in A$, members $b_m\in B$, and marked points such that, relative to $b_0$, the evaluated label $q_i=w(z_{a(i)})$ occurs exactly $m$ additional times in the oscillation set for $(a(i),b_m(\pi (i)))$, while every other evaluated-label count is unchanged.

For each $i<k$, let $O_i=\mathrm{Osc}(a(i),b_0(\pi (i)))$ and $h_i=\mathrm{\mid }\{\xi \in O_i:\mu (a(i),b_0(\pi (i));a(i))(\xi )=q_i\}\mathrm{\mid }$. For $s\mathrm{\ne }0,q_i$ put $h_{i,s}=\mathrm{\mid }\{\xi \in O_i:\mu (a(i),b_0(\pi (i));a(i))(\xi )=s\}\mathrm{\mid }$, and set $r_i=({\sum }_{s\mathrm{\ne }0,q_i}(h_{i,s}<mrow><mi\; mathvariant="normal">m</mi><mi\; mathvariant="normal">o</mi><mi\; mathvariant="normal">d</mi></mrow>s))<mrow><mi\; mathvariant="normal">m</mi><mi\; mathvariant="normal">o</mi><mi\; mathvariant="normal">d</mi></mrow>6$. The sum has finite support by F2. The primes $q_i$ are pairwise coprime, so F4 gives a residue $x$ modulo $Q$ satisfying $x+h_i\equiv 6-r_i+2^{\chi (i)}(\mathrm{m}\mathrm{o}\mathrm{d}{q}_i)$ for every $i$. Choose its representative $0\le x<Q<N$ and put $b=b_x$. The right-hand side lies between $2$ and $8$, hence is already its least nonnegative residue modulo $q_i$.