5
$\begingroup$

Reading Chapter V, pages (73-97) in Proof Theory (Springer, 1977), by Kurt Schütte, I have encountered a peculiar problem which puzzles me.

On page 96, a map $\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}$, thus proving Theorem 14.17 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,((0,0),0))$. But this is not a principal term, i.e. $\alpha\not\in\rm{OT}$ because it represents $\varepsilon_{0}$, and the unique ordinal term which represents this ordinal is $\beta=((0,0),0)\in\rm{OT}$. But $\rm{Nr}(\beta) = 5$. Then again, what element of $\rm{OT}$ maps to $31$?

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

$\endgroup$

1 Answer 1

4
$\begingroup$

Fortunately, there appears to be no flaw in Schütte's construction. Only in my understanding of it.

Ordinal terms are defined on page 86. The term $\alpha=(0,((0,0),0))$ does NOT represent $\varepsilon_{0}$. After a more careful look at the definitions on page 86 and the definition of $\psi$ on page 84 I see now that $\alpha$ represents

$$\psi0(\psi(\psi00)0) = \psi0\varepsilon_{0} = \phi0\varepsilon_{0}^{'} = \omega^{\varepsilon_{0}^{'}} = \omega^{\varepsilon_{0}+1} = \varepsilon_{0}\cdot\omega,$$

where $\alpha'$ denotes the successor of $\alpha$, and $\varepsilon_{0} = \psi(\psi00)0$, which is the ordinal represented by the term $((0,0),0)$.

Therefore, $\alpha$ is indeed a principal term, properly answering my question "what maps to 31?" The map $\rm{Nr}$ is indeed a bijection.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.