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 $\langle C_\alpha\mid\alpha<\omega_1\rangle$ 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{cases}
\beta,&n=0\\
\min(C_{Tr(\alpha,\beta)(n-1)}\setminus\alpha),&n>0\ \&\ Tr(\alpha,\beta)(n-1)>\alpha\\
\alpha,&\text{otherwise}
\end{cases}
$$

  • $\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):=\langle otp(C_{Tr(\alpha,\beta)(j)}\cap\alpha)\mid j<\rho_2(\alpha,\beta)\rangle$;
  • $L(\alpha,\beta):=\{ \max_{i\le j}\sup(C_{Tr(\alpha,\beta)(i)}\cap\alpha) \mid j<\rho_2(\alpha,\beta)\}$;
  • $tr(\alpha,\beta):=Tr(\alpha,\beta)\restriction\rho_2(\alpha,\beta)$.

Remark: We consider $tr(\alpha,\alpha), \rho_0(\alpha,\alpha)$ and $L(\alpha,\alpha)$ as the empty set.

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

  • $A=B\cup C$;
  • $B\not=\emptyset$, $C\not=\emptyset$;
  • $(\bigcup B)\in(\bigcap C)$.

Proposition 1. If $\delta\in\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\Omega$. $\square$

Proposition 2. For every $\alpha<\beta<\gamma<\omega_1$: if $\alpha>\max(L(\beta,\gamma))$, then $$tr(\alpha,\gamma)=tr(\beta,\gamma){}^\frown tr(\alpha,\beta).$$Proof. It suffices to prove that under the same hypotheses, $Tr(\beta,\gamma)=Tr(\alpha,\gamma)\restriction\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)$. $\square$

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

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 $\Gamma\in[\alpha]^\omega$ with $\rho_{1\alpha}(\gamma)\le n$ for all $\gamma\in\Gamma$. In particular, $otp(C_\alpha\cap\gamma)\le n$ for all $\gamma\in\Gamma$.
Define $o:\Gamma\rightarrow n+1$ by stipulating that $o(\gamma):=otp(C_\alpha\cap\gamma)$. Then there exists $\Gamma’\in[\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\Gamma’$. Put $\alpha’:=\min(C_\alpha\setminus\min(\Gamma’))$. Then $\Gamma’\in[\alpha’]^\omega$, and so by $\alpha'<\alpha$ and minimality of the latter, we may find some $\gamma’\in\Gamma’$ such that $\rho_{1\alpha’}(\gamma’)>n$.
By $\min(C_\alpha\setminus\gamma’)=\alpha’$, we have  $tr(\gamma’,\alpha)=\langle\alpha\rangle{}^\frown tr(\gamma’,\alpha’)$, and hence $$\rho_{1\alpha}(\gamma’)=\max\{otp(C_\alpha\cap\gamma’),\rho_{1\alpha^*}(\gamma’)\}>n.$$ This is a contradiction. $\square$

Proposition 5.  For every $\alpha<\beta<\omega_1$, the set $\{\xi<\alpha\mid \rho_{1\alpha}(\xi)\neq\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 $\Gamma\subseteq \alpha$ of order-type $\omega$ with $\rho_{1\alpha}(\xi)\neq\rho_{1\beta}(\xi)$ for all $\xi\in\Gamma$. Put $\gamma:=\sup(\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 $\Gamma’:=\{\xi\in\Gamma\setminus\gamma^{-}\mid \rho_{1\beta}(\xi)>n\}$. By the previous proposition, we know that $ otp(\Gamma’)=\omega$. It then follows from $\gamma^{+}<\beta$ and minimality of the latter, that there exists $\xi\in\Gamma’$ 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)=\langle\beta\rangle{}^\frown 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. $\square$

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){}^\frown tr(\xi,\delta)$;
  • $tr(\xi,\beta)=tr(\delta,\beta){}^\frown tr(\xi,\delta)$.

Write $n:=\text{dom}(tr(\xi,\delta))$. Then $tr(\delta,\alpha)$ is equal to $tr(\xi,\alpha)\restriction(\text{dom}(tr(\xi,\alpha))-n)$, and hence $\rho_0(\delta,\alpha)$ is equal to $\rho_0(\xi,\alpha)\restriction(\text{dom}(tr(\xi,\alpha))-n)$. Likewise, $\rho_0(\delta,\beta)$ is equal to $\rho_0(\xi,\beta)\restriction(\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)$. $\square$

This entry was posted in Blog, Expository and tagged . Bookmark the permalink.

2 Responses to Walk on countable ordinals: the characteristics

  1. Tanmay Inamdar says:

    Hi Assaf, I found a couple of typos:

    1) In the second last line of the proof of Proposition 4, the $theta$ should be an $n$.

    2) In the second line of the proof of Proposition 6, the last $alpha$ should be a $delta$.

Leave a Reply

Your email address will not be published. Required fields are marked *