Walk on countable ordinals: the characteristics

In this post, we shall present a few aspects of the method of walk on ordinals (focusing on countable ordinals), record its characteristics, and verify some of their properties. All definitions and results in this post are due to Todorcevic.

Let $⟨C_{\alpha }\mid \alpha <{\omega }_1⟩$ be a sequence such that $C_{\alpha +1}=\{\alpha \}$ for all $\alpha <{\omega }_1$, and for all limit $\alpha <{\omega }_1$: $C_{\alpha }$ is a cofinal subset of $\alpha$ of order-type $\omega$. Given $\alpha <\beta <{\omega }_1$, define

• $Tr(\alpha ,\beta )\in {}^{\omega }{\omega }_1$, by recursively letting for all $n<\omega$:

$$Tr(\alpha ,\beta )(n):=\{\begin{array}{ll}\beta ,& n=0\\ min(C_{Tr(\alpha ,\beta )(n-1)}\setminus \alpha ),& n>0\mathrm{\&}Tr(\alpha ,\beta )(n-1)>\alpha \\ \alpha ,& \text{otherwise}\end{array}$$

• ${\rho }_2(\alpha ,\beta ):=min\{n<\omega \mid Tr(\alpha ,\beta )(n)=\alpha \}$;
• ${\rho }_{1\beta }\in {}^{\beta }\omega$, by ${\rho }_{1\beta }(\alpha ):=max{\rho }_0(\alpha ,\beta )$, where:
• ${\rho }_0(\alpha ,\beta ):=⟨otp(C_{Tr(\alpha ,\beta )(j)}\cap \alpha )\mid j<{\rho }_2(\alpha ,\beta )⟩$;
• $L(\alpha ,\beta ):=\{\underset{i\le j}{max}sup(C_{Tr(\alpha ,\beta )(i)}\cap \alpha )\mid j<{\rho }_2(\alpha ,\beta )\}$;
• $tr(\alpha ,\beta ):=Tr(\alpha ,\beta )\upharpoonright {\rho }_2(\alpha ,\beta )$.

Remark: We consider $tr(\alpha ,\alpha ),{\rho }_0(\alpha ,\alpha )$ and $L(\alpha ,\alpha )$ as the empty set.

Notation: Write $\mathrm{\Omega }:=\{\alpha <{\omega }_1\mid cf(\alpha )=\omega \}$. Also, by $A=B\oplus C$, we mean that:

• $A=B\cup C$;
• $B\ne \mathrm{\varnothing }$, $C\ne \mathrm{\varnothing }$;
• $(\bigcup B)\in (\bigcap C)$.

Proposition 1. If $\delta \in \mathrm{\Omega }$ and $\delta <\beta <{\omega }_1$, then $max(L(\delta ,\beta ))<\delta$.
Proof. If $\delta \ge max(L(\delta ,\beta ))$, then by definition, there exists $i<{\rho }_2(\delta ,\beta )$ such that $sup(C_{Tr(\delta ,\beta )(i)}\cap \delta )=\delta$.  In particular, there exists an ordinal $\alpha$ with  $\delta <\alpha <\beta$ such that $sup(C_{\alpha }\cap \delta )=\delta$. It follows that $cf(\delta )\le otp(C_{\alpha }\cap \delta )<otp(C_{\alpha })\le \omega$, contradicting the fact that $\delta \in \mathrm{\Omega }$. $\mathrm{<img\; draggable="false"\; role="img"\; class="emoji"\; alt="◻"\; src="https://s.w.org/images/core/emoji/15.1.0/svg/25fb.svg">}$

Proposition 2. For every $\alpha <\beta <\gamma <{\omega }_1$: if $\alpha >max(L(\beta ,\gamma ))$, then $$tr(\alpha ,\gamma )=tr(\beta ,\gamma ){}^{⌢}tr(\alpha ,\beta ).$$Proof. It suffices to prove that under the same hypotheses, $Tr(\beta ,\gamma )=Tr(\alpha ,\gamma )\upharpoonright {\rho }_2(\beta ,\gamma )$, and $Tr(\alpha ,\gamma )({\rho }_2(\beta ,\gamma ))=\beta$.
Clearly, $Tr(\alpha ,\gamma )(0)=\gamma =Tr(\beta ,\gamma )(0)$. Next, if $i<{\rho }_2(\beta ,\gamma )$ and $Tr(\alpha ,\gamma )(i)=Tr(\beta ,\gamma )(i)$, then by $$\beta >\alpha >max(L(\beta ,\gamma ))\ge sup(C_{Tr(\beta ,\gamma )(i)}\cap \beta ),$$ we get that $$min(C_{tr(\alpha ,\gamma )(i)}\setminus \alpha )=min(C_{tr(\beta ,\gamma )(i)}\setminus \alpha )=min(C_{tr(\beta ,\gamma )(i)}\setminus \beta ),$$ and hence $Tr(\alpha ,\gamma )(i+1)=Tr(\beta ,\gamma )(i+1)$. $\mathrm{<img\; draggable="false"\; role="img"\; class="emoji"\; alt="◻"\; src="https://s.w.org/images/core/emoji/15.1.0/svg/25fb.svg">}$

Proposition 3. For every $\alpha <\beta <\gamma <{\omega }_1$: if   $min(L(\alpha ,\beta ))>max(L(\beta ,\gamma ))$, then $$L(\alpha ,\gamma )=L(\beta ,\gamma )\oplus L(\alpha ,\beta ).$$Proof. By $\alpha \ge min(L(\alpha ,\beta ))>max(L(\beta ,\gamma ))$, we get from the previous porposition that $tr(\alpha ,\gamma )=tr(\beta ,\gamma ){}^{⌢}tr(\alpha ,\beta )$, and hence $$L(\alpha ,\gamma )=L(\beta ,\gamma )\oplus U,$$ for $U:=L(\alpha ,\beta )\setminus (max(L(\beta ,\gamma ))+1)$. Recalling that $min(L(\alpha ,\beta ))>max(L(\beta ,\gamma ))$, we conclude that $L(\alpha ,\gamma )=L(\beta ,\gamma )\oplus L(\alpha ,\beta )$. $\mathrm{<img\; draggable="false"\; role="img"\; class="emoji"\; alt="◻"\; src="https://s.w.org/images/core/emoji/15.1.0/svg/25fb.svg">}$

Proposition 4. For every $\alpha <{\omega }_1$ and $n<\omega$: the set $\{\xi <\alpha \mid {\rho }_{1\alpha }(\xi )\le n\}$ is finite.
Proof. Suppose not. Let $\alpha <{\omega }_1$ be the least for which there exists $n<\omega$ and a set $\mathrm{\Gamma }\in [\alpha {]}^{\omega }$ with ${\rho }_{1\alpha }(\gamma )\le n$ for all $\gamma \in \mathrm{\Gamma }$. In particular, $otp(C_{\alpha }\cap \gamma )\le n$ for all $\gamma \in \mathrm{\Gamma }$.
Define $o:\mathrm{\Gamma }\to n+1$ by stipulating that $o(\gamma ):=otp(C_{\alpha }\cap \gamma )$. Then there exists ${\mathrm{\Gamma }}^{\prime }\in [\mathrm{\Gamma }{]}^{\omega }$ on which $o$ is constant. In particular, $min(C_{\alpha }\setminus {\gamma }_1)=min(C_{\alpha }\setminus {\gamma }_2)$ for all ${\gamma }_1,{\gamma }_2\in {\mathrm{\Gamma }}^{\prime }$. Put ${\alpha }^{\prime }:=min(C_{\alpha }\setminus min({\mathrm{\Gamma }}^{\prime }))$. Then ${\mathrm{\Gamma }}^{\prime }\in [{\alpha }^{\prime }{]}^{\omega }$, and so by ${\alpha }^{\prime }<\alpha$ and minimality of the latter, we may find some ${\gamma }^{\prime }\in {\mathrm{\Gamma }}^{\prime }$ such that ${\rho }_{1{\alpha }^{\prime }}({\gamma }^{\prime })>n$.
By $min(C_{\alpha }\setminus {\gamma }^{\prime })={\alpha }^{\prime }$, we have  $tr({\gamma }^{\prime },\alpha )=⟨\alpha ⟩{}^{⌢}tr({\gamma }^{\prime },{\alpha }^{\prime })$, and hence $${\rho }_{1\alpha }({\gamma }^{\prime })=max\{otp(C_{\alpha }\cap {\gamma }^{\prime }),{\rho }_{1{\alpha }^{\ast }}({\gamma }^{\prime })\}>n.$$ This is a contradiction. $\mathrm{<img\; draggable="false"\; role="img"\; class="emoji"\; alt="◻"\; src="https://s.w.org/images/core/emoji/15.1.0/svg/25fb.svg">}$

Proposition 5.  For every $\alpha <\beta <{\omega }_1$, the set $\{\xi <\alpha \mid {\rho }_{1\alpha }(\xi )\ne {\rho }_{1\beta }(\xi )\}$ is finite.
Proof. Suppose not. Let $\beta <{\omega }_1$ be the least for which there exists $\alpha <\beta$ and a subset $\mathrm{\Gamma }\subseteq \alpha$ of order-type $\omega$ with ${\rho }_{1\alpha }(\xi )\ne {\rho }_{1\beta }(\xi )$ for all $\xi \in \mathrm{\Gamma }$. Put $\gamma :=sup(\mathrm{\Gamma })$, ${\gamma }^{-}:=sup(C_{\beta }\cap \gamma )$, and  ${\gamma }^{+}:=min(C_{\beta }\setminus \gamma )$.
By $cf(\gamma )=\omega \ge otp(C_{\beta })$, we infer that ${\gamma }^{-}<\gamma \le \alpha \le {\gamma }^{+}<\beta$.
Put $n:=otp(C_{\beta }\cap \gamma )$, and ${\mathrm{\Gamma }}^{\prime }:=\{\xi \in \mathrm{\Gamma }\setminus {\gamma }^{-}\mid {\rho }_{1\beta }(\xi )>n\}$. By the previous proposition, we know that $otp({\mathrm{\Gamma }}^{\prime })=\omega$. It then follows from ${\gamma }^{+}<\beta$ and minimality of the latter, that there exists $\xi \in {\mathrm{\Gamma }}^{\prime }$ such that ${\rho }_{1\alpha }(\xi )={\rho }_{1{\gamma }^{+}}(\xi )$.
By ${\gamma }^{-}\le \xi <\gamma \le {\gamma }^{+}$, we know that $min(C_{\beta }\setminus \xi )=min(C_{\beta }\setminus \gamma )$ and $otp(C_{\beta }\cap \xi )=otp(C_{\beta }\cap \gamma )=n$. That is, $min(C_{\beta }\setminus \xi )={\gamma }^{+}$, and ${\rho }_{1{\gamma }^{+}}(\xi )>otp(C_{\beta }\cap \xi )$. So $tr(\xi ,\beta )=⟨\beta ⟩{}^{⌢}tr(\xi ,{\gamma }^{+})$, and hence $${\rho }_{1\beta }(\xi )=max\{otp(C_{\beta }\cap \xi ),{\rho }_{1{\gamma }^{+}}(\xi )\}={\rho }_{1{\gamma }^{+}}(\xi )={\rho }_{1\alpha }(\xi ).$$ This is a contradiction. $\mathrm{<img\; draggable="false"\; role="img"\; class="emoji"\; alt="◻"\; src="https://s.w.org/images/core/emoji/15.1.0/svg/25fb.svg">}$

Proposition 6.  For every $\alpha <\beta <{\omega }_1$, the set $\{\xi <\alpha \mid {\rho }_0(\xi ,\alpha )={\rho }_0(\xi ,\beta )\}$ is closed.
Proof. Let $\delta$ be a limit point of this set. Then, by Proposition 1, $max(L(\delta ,\beta ))<\delta$ and $max(L(\delta ,\alpha ))<\delta$. Consequently, we may find $\xi$ in this set such that $max(L(\delta ,\alpha )\cup L(\delta ,\beta ))<\xi$. It then follows from proposition 2 that:

• $tr(\xi ,\alpha )=tr(\delta ,\alpha ){}^{⌢}tr(\xi ,\delta )$;
• $tr(\xi ,\beta )=tr(\delta ,\beta ){}^{⌢}tr(\xi ,\delta )$.

Write $n:=\text{dom}(tr(\xi ,\delta ))$. Then $tr(\delta ,\alpha )$ is equal to $tr(\xi ,\alpha )\upharpoonright (\text{dom}(tr(\xi ,\alpha ))-n)$, and hence ${\rho }_0(\delta ,\alpha )$ is equal to ${\rho }_0(\xi ,\alpha )\upharpoonright (\text{dom}(tr(\xi ,\alpha ))-n)$. Likewise, ${\rho }_0(\delta ,\beta )$ is equal to ${\rho }_0(\xi ,\beta )\upharpoonright (\text{dom}(tr(\xi ,\beta ))-n)$. Recalling that ${\rho }_0(\xi ,\alpha )={\rho }_0(\xi ,\beta )$, we conclude that indeed ${\rho }_0(\delta ,\alpha )={\rho }_0(\delta ,\beta )$. $\mathrm{<img\; draggable="false"\; role="img"\; class="emoji"\; alt="◻"\; src="https://s.w.org/images/core/emoji/15.1.0/svg/25fb.svg">}$