Skip to main content
1 of 7
Victor
  • 2.1k
  • 15
  • 24

Understanding a notation system for the ordinals $<\Gamma_{0}$ and an explicit mapping onto $\mathbb{N}$ in Kurt Schütte's *Proof Theory*

Reading Chapter V, pages (73-97) in Proof Theory (Springer, 1977), by Kurt Schütte, I have encountered a peculiar problem which, not being an expert in either proof theory or ordinal analysis puzzles me.

On page 96, an explicit bijection $\rm{Nr}:\overline{\rm{OT}}\rightarrow \mathbb{N}$ is defined using the Cantor pairing function $\pi(m,n)=\frac{1}{2}(m+n)(m+n+1)+m$, where $\rm{OT}$ is the set of ordinal terms defined on page 86 and $\overline{\rm{OT}} = \rm{OT}\cup\{\Gamma_{0}\}$. Namely (p.97),

  1. $\rm{Nr}(0) := 1$, $\rm{Nr}(\Gamma_{0})=0$.
  2. $\rm{Nr}(\alpha) = \displaystyle\prod_{i=1}^{n}P_{\pi\left(\rm{Nr}(\alpha_{i})-1,\rm{Nr}(\beta_{i})-1\right)}$, for $\alpha = (\alpha_{1},\beta_{1})\ldots(\alpha_{n},\beta_{n})\in\rm{OT}$ (where $P_{0}=2$ and for $k\ge 1$, $P_{k}$ is the $k$-th odd prime number.

On the same page he provides a definition of the inverse $\tau$ of $\rm{Nr}$ and proves that $\rm{Nr}$ is a bijection.

All very nice. However, what maps to $31=P_{10}$? Well, $10=\pi(0,4)$, and a simple calculation shows that it should be the term $\alpha = (0,(1,0))$. But this is not an ordinal term, i.e. $\alpha\not\in\rm{OT}$. Of course, the terms $(1,0)$ and $\alpha$ represent the same ordinal, namely $\varepsilon_{0}$. But $(1,0)$ is the unique term in $\rm{OT}$ representing $\varepsilon_{0}$, and thus $\rm{Nr}((1,0)) = 5$.

What am I not understanding of Schütte's argument?

Victor
  • 2.1k
  • 15
  • 24