순서형 접기함수

수학적 논리학 및 세트 이론에서 서수형 붕괴 함수(또는 투영 함수)는 특정 재귀적 대형 카운트 가능 서수를 정의하는 기술(또는 투영 함수)이며, 그 원리는 정의되는 서수보다 훨씬 큰 특정 서수, 아마도 큰 추기경(재귀적으로 대체될 수 있지만)에 이름을 부여하는 것이다.추가 기술 난이도의 비용으로 대형 서수들을 그리고 나서 그것들을 찾는 서수들을 위한 표기 체계로 "축소"한다. 이러한 이유로, 서수 붕괴 함수는 서수 이름을 붙이는 충동적인 방법으로 설명된다.

서수 붕괴 함수의 정의에 대한 세부 사항은 다양하며, 더 큰 서수가 정의되고 있기 때문에 더욱 복잡해지지만, 전형적인 생각은 표기 시스템이 "연료가 고갈되고" 특정 서수의 이름을 지정할 수 없을 때마다 훨씬 더 큰 서수를 "위에서" 가져와 그 중요한 지점에 이름을 붙이는 것이다. 바흐만-하워드 서수를 정의하는 서수형 붕괴 함수(즉, 바흐만-하워드 서수까지의 표기 체계를 정의함)에 대해 이 기능이 어떻게 작동하는지에 대한 예가 아래에 자세히 설명된다.

이후 큰 가산 ordinals고 표시된 주어진 붕괴에 의해 정의된 특정 공식적인 시스템의ordinal-theoretic 힘, 그 r의 빛에서 볼 수( 같은 분석의 typically[1][2]서브 시스템 언급된다 순서가 무너지고 기능의 사용과 정의는 서수적 분석의 이론에 얽혀 있기 때문에everse 수학), Kripke-Platek 집합 이론의 확장, 비숍 스타일의 건설 수학 시스템 또는 마틴 뢰프식 직관 유형 이론 시스템. (psi)(1)

순서형 접기 함수는 일반적으로 그리스 문자 $\psi {\displaystyle }$ ${\displaystyle \psi }($psi) 또는 $\theta {\displaystyle }$ ${\displaystyle \teta$}($$teta)의 일부 변동을 사용하여 표시된다.

바흐만-하워드 서수날까지 이어지는 예

아래에 제시된 서수 붕괴 기능의 선택은 부홀츠에^[3] 의해 도입된 시스템을 크게 모방하지만, 설명의 명확성을 위해 하나의 추기경을 붕괴시키는 것으로 한정된다. 이 사례와 Buchholz의 시스템 사이의 관계에 대한 자세한 내용은 다음과 같다.

정의

$\Omega {\displaystyle }$ ${\displaystyle \Oomega}$은(는) 첫 번째 계산할 수 없는 서수 ${\displaystyle {\Omega \mathrm{}}_{}}$ 1 ${\displaystyle \omega$ $_$${$$1},$또는$$ 실제로 구성될 모든 카운트 가능한 서수보다 클 것을 보장한 서수를 나타내도록 두십시오(예: Churchart-Kleeneal은 o에 적합함$$).$\Omega {\displaystyle {}_{}}$ ${\displaystyle {1\mathrm{}}_{}}$ ${\$}와 함께 작업할 것이다. 왜냐하면 정의에서 셀 수 있는 단어를 편리하게 사용할 수 있기 때문이다$$.)

함수$$$inal{\displaystyle }$ {\$displaystyle$ \$psi }($비감소 및 연속)을 정의하고, $임의{\displaystyle }$ 순서$α$ {\$displaystyle$ \alpha $}$을(를) $\alpha {\displaystyle }$${\displaystyle }$(${\displaystyle \alpha )}$ ${\$$displaystyle \psi$ $(\alpha$)에 재귀적으로$,$ 다음과 같이 정의한다$.$

$\psi {\displaystyle }$(${\displaystyle \beta }$) ${\displaystyle \psi (\beta )}$이(가) 모든 < ${\displaystyle \beta <\alpha }$에 대해 정의되었다고$$ 가정하고,$\psi {\displaystyle }$ ${\displaystyle (\alpha }$) ${\displaysty \psi (\alpha )}$을 정의하고자 한다$.$

C${\displaystyle }$(${\displaystyle \alpha }$) ${\displaystyle$ $C$$(\alpha )}$을(를) 다음 기능을 반복적으로 적용하여$$ $0{\displaystyle \mathrm{}}$ ${\displaystyle$ $0$$\},$ 1 ${\displaystyle$ 1$\},$ $\Omega {\displaystyle }$ ${\$$displaystyle$ ${\displaystyle {}_{}}$$omega$$}$부터 생성되는 서수 집합으로 $두십시오$.α{\displaystyle \psi \upharpoonright_{\alpha}}, 즉,ψ{\displaystyle \psi}의 ordinals 제한, α{\displaystyle \beta<>\alpha}.(형식적으로, 우리(C을 정의하는 α)0){0,1, ω, Ω}{\displaystyle C(\alpha)_{0}=\{0,1,\omega ,\Omega)}}과 귀납적으로 C(α)n+1=C(α)n.<>β ∪{β 1+β 2, β 1β 2, β 1β 2:β 1, β 2∈ C(n}∪{ψ(β):β ∈ C(α)n∧ β<>α}{\displaystyle C(\alpha)_{n+1}(\alpha)_{n}\cup \{\beta_{1}+\beta _{2},\beta _{1}\beta _{2},{\beta_{1}}^{\beta_{2}}:\beta _{1},\beta _{2}\in C(\alpha)_{n}\}\cup){\psi(\beta):\beta\in C(\alpha)_{.n$}\land \beta <\alpha \}$ 모든 $자연수{\displaystyle }$ n ${\displaystyle n}$에 $대해{\displaystyle }$ C(α)${\displaystyle }$${\$$displaystyle C(\$alpha )$_{n$$}$를 모든 $n$에 대해$$ $C{\displaystyle (\alpha {}_{}}$){\$displaystystyle C(\$$alpha$)_{n$}$의 조합으로$$ 한다.$$

그러면 $\psi {\displaystyle }$(${\displaystyle \alpha }$) ${\displaystyle \psi (\alpha )}$은(는) $C{\displaystyle }$ ${\displaystyle (\alpha }$) ${\displaystyle C(\alpha )}$에 속하지 않는 가장 작은 서수로 정의된다$.$

좀 더 간결하게(좀 더 모호하긴 하지만) 다음과 같은 방법으로:

${\displaystyle \psi }$(${\displaystyle \alpha }$) ${\displaystyle \psi (\alpha )}$은(는) $0{\displaystyle \mathrm{}}$ ${\displaystyle$ $0$$\},$ 1 ${\displaystyle$ 1$\},$ $\Omega {\displaystyle }$ ${\displaystyle$ $\$$omega},$ $합계$, $,$ 지수 및 $display$ {\displaystyle \$psi}$ 함수$$ 자체에서 표현할 수 없는 가장 작은 순서다. $\alpha {\displaystyle }$ ${\displaystyle \alpha }$보다 작은 서수.

여기에 ${\displaystyle \psi }$의 정의에 대한 동기를 직관적인$$ 용어로 설명하려는 시도가 있다: 통상적인 덧셈, 곱셈, 지수가 그리 멀리 서수를 지정하기에 충분하지 않기 때문에 n이 없는 첫 번째 것을 취함으로써 체계적으로 서수의 새 이름을 만들려고 한다.아직까지는, 그리고 이름이 떨어질 때마다, 임시방편으로 발명하거나 대각선 계획을 사용하기보다는, 우리가 건설하고 있는 것들보다 훨씬 더 멀리 서수로 그것들을 찾는다$([\displaystyle \Oomega$ $\},$ 즉, ]. 그래서 우리는 셀 수 없는 서수들에 이름을 붙인다. 그리고, 결국 이름 목록은 반드시 셀 수 있기 때문에, $\psi {\displaystyle }$.$[\displaystyle \cHB }$은(는) 그것들을 카운트 가능한 서수로 "조정"할$$ 것이다.

ψ의 값 계산

함수 $\psi {\displaystyle }${\$displaystyle \psi}$이(가) 특정 서수들에 대한 공식을 생성하는 방법을 명확히 하기 위해 이제 첫 번째 값을 계산한다.

술어 출발

먼저 $C{\displaystyle }$( ${\displaystyle 0}$) ${\displaystyle C(0)}$을(를) 고려하십시오$.$ It contains ordinals ${\displaystyle 0,1,2,3,\omega ,\omega +1,\omega +2,\omega 2,\omega 3,\omega ^{2},\omega ^{3},\omega ^{\omega },\omega ^{\omega ^{\omega }}}$ and so on. 또한 $\Omega {\displaystyle \mathrm{},}$ ${\displaystyle \mathrm{\Omega }}$+ ${\displaystyle 1}$,${\displaystyle \mathrm{\Omega }}$, ${\displaystyle \Omega }$, Ω,${\displaystyle }$Ω, ${\displaystyle {\mathrm{}}^{}}$,$$ 스타일 {\$displaystyle \Oomega,\Oomega +1,\Oomega \omega ^{\Oomega }}$과 같은 서수를 포함한다$.$ The first ordinal which it does not contain is ${\displaystyle \varepsilon _{0}}$ (which is the limit of ${\displaystyle \omega }$, ${\displaystyle \omega ^{\omega }}$, ${\displaystyle \omega ^{\omega ^{\omega }}}$ and so on — less than ${\displaystyle \Omega }$ by assumption). The upper bound of the ordinals it contains is ${\displaystyle \varepsilon _{\Omega +1}}$ (the limit of ${\displaystyle \Omega }$, ${\displaystyle \Omega ^{\Omega }}$, ${\displaystyle \Omega ^{\Omega ^{\Omega }}}$ and so on), but that is not so important. $이것$은 ${\displaystyle (}$ (${\displaystyle 0}$ )${\displaystyle }$= ${\displaystyle {0\mathrm{}}_{}}$ 0 ${\$을 나타낸다$.$

마찬가지로 $C{\displaystyle }$( ${\displaystyle 1}$) ${\displaystyle$ $C$$(1)}$에는 $0{\displaystyle \mathrm{}}$ ${\displaystyle$ $0$$\},$ 1 ${\$$displaystyle$ 1$\},$$$$\Omega {\displaystyle {}_{}}$ $\$$omega$$\},$ ${\displaystyle {\Omega \mathrm{}}_{}}$$$${\$0$\},$ 덧셈, 곱셈을 사용하여 구성할$$ 수 있는 서수가 있다$$. This contains all the ordinals up to ${\displaystyle \varepsilon _{1}}$ but not the latter, so ${\displaystyle \psi (1)=\varepsilon _{1}}$. In this manner, we prove that ${\displaystyle \psi (\alpha )=\varepsilon _{\alpha }}$ inductively on ${\displaystyle \alpha }$: the proof 그러나 < α ${\$까지만 작업할 수 있다 따라서 다음과 같은 결과를 얻을 수 있다.

${\displaystyle \psi (\alpha )=\varepsilon _{\alpha }=\phi _{1}(\alpha )}$ for all ${\displaystyle \alpha \leq \zeta _{0}}$, where ${\displaystyle \zeta _{0}=\phi _{2}(0)}$ is the smallest fixed point of ${\displaystyle \alpha \mapsto \varepsilo$$n _{\cHB$ $\}\}.$

(여기서 ${\displaystyle \pi }$ 함수는$$ ${\displaystyle {\varphi \mathrm{}}_{}}$ 1${\displaystyle {}_{}}$(${\displaystyle \alpha }$)${\displaystyle }$= ${\displaystyle {}_{}}$ ${\displaystyle {\alpha }_{}}$α {\$displaystyle \phi _{$1}(\$alpha )=\varepsilon$ _${\alpha }}}$부터 정의된 베블렌 함수다.$$

Now ${\displaystyle \psi (\zeta _{0})=\zeta _{0}}$ but ${\displaystyle \psi (\zeta _{0}+1)}$ is no larger, since ${\displaystyle \zeta _{0}}$ cannot be constructed using finite applications of ${\displaystyle \phi _{1}\colon \alpha \mapsto \varepsilon _{\$따라서$$$$$\alpha {\displaystyle \mathrm{\Omega }}$ ${\$$displaystyle C(\alpha$ )}에 대해 $설정$된 C(α$){\displaystyle$ C$(\$alpha $)}$에 속하지 않으며$,$ $\psi {\displaystyle }$ ${\displaystyle \$$leq$ \$Oba \$$psi$} 함수는 한동안$$ ${\displaystyle {0\mathrm{}}_{}}$ 0${\$에서 "stick" 상태로$$ 유지된다.

${\displaystyle \psi }$(${\displaystyle \alpha }$)${\displaystyle }$= $\zeta {\displaystyle {}_{}}$ ${\displaystyle {0\mathrm{}}_{}}$ ${\$ ${\displaystyle )=\backslash }$$zeta$${\displaystyle \mathrm{\Omega }}$ ${\$$displaystyle \zeta _{0}\leq \leq$\leq $\leq$ \leq \$lq$ \$Oomega}}$에 대한$$ ζ 0$.$

첫 번째 귀납 값

다시 $\psi {\displaystyle }$(${\displaystyle \mathrm{\Omega }}$)${\displaystyle }$= ${\displaystyle {}_{}}$ ${\displaystyle {0\mathrm{}}_{}}$ ${\$ However, when we come to computing ${\displaystyle \psi (\Omega +1)}$, something has changed: since ${\displaystyle \Omega }$ was ("artificially") added to all the ${\displaystyle C(\alpha )}$, we are permitted to take the value ${\displaystyle \psi (\Omega )=\zeta _{0}}$ in the process. So ${\displaystyle C(\Omega +1)}$ contains all ordinals which can be built from ${\displaystyle 0}$, ${\displaystyle 1}$, ${\displaystyle \omega }$, ${\displaystyle \Omega }$, the ${\displaystyle \phi _{1}\colon \alpha \mapsto \varepsilon _{\alpha }}$ function up to ${\displaystyle {\zeta }_{}}$ ${\$ ${$$0}}$ 그리고$$ 이번에도 ${\displaystyle {and\mathrm{}}_{}}$ 0 {\$displaystyle \zeta _{0}}$ 그 자체로$$ 덧셈, 곱셈, 지수를 사용한다. $C{\displaystyle (\mathrm{\Omega }}$+ ${\displaystyle 1}$)에 포함되지 않은 가장 작은 서수$(\$$Displaystyle$ C$)(\Oomega +$1)는$$${\displaystyle {\epsilon {}_{}}_{}}$ ${\displaystyle {{0\mathrm{}}_{}}_{}}$+ ${\displaystyle 1_{}}$ ${\$$displaystyle$ $\$$varepsilon$ $_$${\zeta _$${$$0}+$$1}:{$0$$}+$$$$1}(${\displaystyle {가장\mathrm{}}_{}}$ 작은 서수)이다$.$

We say that the definition ${\displaystyle \psi (\Omega )=\zeta _{0}}$ and the next values of the function ${\displaystyle \psi }$ such as ${\displaystyle \psi (\Omega +1)=\varepsilon _{\zeta _{0}+1}}$ are impredicative because they use ordinals (here, ${\displaystyle \Ome$$ga }$)는 정의되는 것보다 크다(여기서 ${\displaystyle {\zeta \mathrm{}}_{}}$ 0 ${\$

Feferman-Schütte 서수식까지의 ψ 값

The fact that ${\displaystyle \psi (\Omega +\alpha )=\varepsilon _{\zeta _{0}+\alpha }}$ remains true for all ${\displaystyle \alpha \leq \zeta _{1}=\phi _{2}(1)}$ (note, in particular, that ${\displaystyle \psi (\Omega +\zeta _{0})=\var$$엡실론 _{\zeta _{0}2}}$: 그러나 지금부터는 서수 ${\displaystyle {0\mathrm{}}_{}}$ 0${\$이(가) 구성되어 이것을$$ 넘어서는 것을 막을 수 있는 것은 아무것도 없다.) However, at ${\displaystyle \zeta _{1}=\phi _{2}(1)}$ (the first fixed point of ${\displaystyle \alpha \mapsto \varepsilon _{\alpha }}$ beyond ${\displaystyle \zeta _{0}}$), the construction stops again, because ${\displaystyle \zeta _{1}}$ cannot be constructed from smaller 서수 및$\zeta {\displaystyle {}_{}}$ ${\displaystyle {0\mathrm{}}_{}}$ {\$displaystyle$\zeta $_{0}.$ $\epsilon {\displaystyle }$ ${\displaystyle \var렙실론 }$ 함수를$$ 정밀하게 적용$$. 그래서 우리는 $\psi {\displaystyle }$(${\displaystyle \mathrm{\Omega }2}$) = ${\displaystyle {1\mathrm{}}_{}}$ 1 ${\$1}를 $가지고$ 있다$.$

The same reasoning shows that ${\displaystyle \psi (\Omega (1+\alpha ))=\phi _{2}(\alpha )}$ for all ${\displaystyle \alpha \leq \phi _{3}(0)}$, where ${\displaystyle \phi _{2}}$ enumerates the fixed points of ${\displaystyle \phi _{1}\colon \al$$pha \mapsto \varepsilon _{\alpha }}$ and ${\displaystyle \phi _{3}(0)}$ is the first fixed point of ${\displaystyle \phi _{2}}$. We then have ${\displaystyle \psi (\Omega ^{2})=\phi _{3}(0)}$.

Again, we can see that ${\displaystyle \psi (\Omega ^{\alpha })=\phi _{1+\alpha }(0)}$ for some time: this remains true until the first fixed point ${\displaystyle \Gamma _{0}}$ of ${\displaystyle \alpha \mapsto \phi _{\alpha }(0)}$, which is the Feferman–Schütte ordinal. 따라서 $\psi {\displaystyle }$(${\displaystyle {\mathrm{}}^{}}$ ${\displaystyle {\Omega \mathrm{}}^{}}$)${\displaystyle }$= ${\displaystyle {\gamma \mathrm{}}_{}}$ 0 ${\$는 페페르만-슈뷔테 서수형이다.

페페르만-슈튀트 서수문 너머

We have ${\displaystyle \psi (\Omega ^{\Omega }+\Omega ^{\alpha })=\phi _{\Gamma _{0}+\alpha }(0)}$ for all ${\displaystyle \alpha \leq \Gamma _{1}}$ where ${\displaystyle \Gamma _{1}}$ is the next fixed point of ${\displaystyle \alpha \ma$$psto \phi _{\alpha }(0)}$. So, if ${\displaystyle \alpha \mapsto \Gamma _{\alpha }}$ enumerates the fixed points in question (which can also be noted ${\displaystyle \phi (1,0,\alpha )}$ using the many-valued Veblen functions) we have ${\displaystyle \psi (\Omega ^{\Om$$ega }(1+\alpha ))=\Gamma _{\alpha }}$, until the first fixed point ${\displaystyle \phi (1,1,0)}$ of the ${\displaystyle \alpha \mapsto \Gamma _{\alpha }}$ itself, which will be ${\displaystyle \psi (\Omega ^{\Omega +1})}$ (and the first fixed point ${\displaystyl$$e$ ${\displaystyle \alpha }$ ↦${\displaystyle \mapsto }$ (${\displaystyle 1}$,${\displaystyle \mathrm{\alpha }}$, 0${\displaystyle }$)의$$ \phi (2,$0,0$)}$$$\pi$ ($1,\alpha ,0)}$ 함수는$$ $\psi {\displaystyle }$(Ω ${\displaystyle {\mathrm{}}^{}}$ \${\displaystyle {\mathrm{\Omega }}^{}}$ $2$${\displaystyle {}^{}}$) ${\displaysty \psi (\Oomega ^{\Oomega2})$가 된다.$$ 이러한 방식으로:

• ${\displaystyle \psi ({\mathrm{}}^{}}$ ${\displaystyle {\Omega {\mathrm{}}^{}}^{}}$ ${\displaystyle {{2\mathrm{}}^{}}^{}}$) ${\displaystyle \psi(\Oomega ^{\Oome ^{2}}:)$는 Ackermann 서수형(표기 notation,${\displaystyle \alpha ,}$ ${\displaystyle \beta }$,${\displaystyle \gamma }$) ${\displaystyle \phi(\alpha ,\beta ,\gamma )})$가 사전적으로 정의됨$$),
• ${\displaystyle \psi }$(${\displaystyle {\mathrm{}}^{}}$ ${\displaystyle {\Omega {\mathrm{}}^{}}^{}}$ ${\displaystyle {{\Omega }^{}}^{}}$) ${\displaystyle \psi(\Oomega ^{\Oomega ^{\dots }})$는 "작은" 베블렌 서수($displaysty{\displaystyle }$\ ( …${\displaystyle }$) ${\displaysty \phi (\ldots )})$는 사전적으로$$ 많은 변수를 사용한다.
• ${\displaystyle \psi ({\mathrm{}}^{}}$ ${\displaystyle {\Omega {\mathrm{}}^{}}^{}}$ ${\displaystyle {{\Omega \mathrm{}}^{}}^{}}$) ${\displaystyle \psi$${\displaystyle (\backslash }$$Oomega ^{\Oomega ^{\$$dots }})$는 "큰" 베블렌 서수형(trans-finally-but-predicative-multi $변수$를 $사전적$으로 사용함${\displaystyle )}$이다$.$
• the limit ${\displaystyle \psi (\varepsilon _{\Omega +1})}$ of ${\displaystyle \psi (\Omega )}$, ${\displaystyle \psi (\Omega ^{\Omega })}$, ${\displaystyle \psi (\Omega ^{\Omega ^{\Omega }})}$, etc., is the Bachmann–Howard ordinal: after this our function ${$$\displaystyle \property$}은(는) 일정하며$$, 우리가 준 정의로는 더 이상 나아갈 수 없다.

바흐만-하워드 서수까지의 서수 표기법

이제 우리는 바흐만-하워드 서수까지의 서수들에 대한 표기를 $\psi {\displaystyle }$ ${\displaystyle \psi}$ 함수가$$ 어떻게 정의하는지 보다 체계적으로 설명한다.

기본 표현에 대한 참고 사항

Recall that if ${\displaystyle \delta }$ is an ordinal which is a power of ${\displaystyle \omega }$ (for example ${\displaystyle \omega }$ itself, or ${\displaystyle \varepsilon _{0}}$, or ${\displaystyle \Omega }$), any ordinal ${\displaystyle \alpha }$ can be uniquely expressed in the form $$${\displaystyle \delta ^{\beta _{1}}\gamma _{1}+\ldots +\delta ^{\beta _{k}}\gamma _{k}}$, where ${\displaystyle k}$ is a natural number, ${\displaystyle \gamma _{1},\ldots ,\gamma _{k}}$ are non-zero ordinals less than ${\displaystyle \delta }$, and > 2>β k > $β$ ${\$는 순서형 숫자($\beta {\displaystyle {}_{}}$ ${\displaystyle k_{}}$= 0 ${\displaysty \property_{k}=0})$이다.$$ 이 "베이스 $\Delta {\displaystyle }$ ${\displaystyle \delta }$표현$$"은 캔터 정상 형태(사례 $\Delta {\displaystyle }$= ${\displaystyle \Omega }$ ${\displaystyle \delta =\omega$})$$의 명백한 일반화다. 물론, 꽤 잘은 방정식, 즉, α)δ α{\displaystyle \alpha =\delta ^{\alpha}}, 하지만 다른 경우에 나는{\displaystyle \beta_{나는}은 β}모든α{\displaystyle \alpha}이상이어야 한다 재미 없다고 하는;수도 있는 사건은 표현은 사소한(즉,α<>δ{\displa 수 있다.y$스타일{\displaystyle }$ ${\displaystyle \backslash }$$cHB <\$$displaystyle k\leq 1}$과($와{\displaystyle {}_{}}$) ${\displaystyle {\alpha \mathrm{}}_{}}$ 1 =$$ {\$displaystyle \property \{1}=\property$}

만약 α{\displaystyle \alpha}는ε Ω보다+1{\displaystyle \varepsilon_{\Omega+1}}셨습니다. 그러나 순서는 기지 Ω{\displaystyle \Omega}표현 계술 거야.Ω{\displaystyle \gamma_{나는}< < γ, 가지고 있다.\Omega}(정의에 의해)과 밑이 나는 <\alpha}(becauα{\displaystyle \beta_{나는}< β.< + ${\$ $\$$alpha <\varepsilon _{\$$Oomega$$+1$$})$ 가정: 따라서 이러한 지수를 염기 $\Omega$으로 다시 쓰고$$ 공정이 종료될 때까지 작업을 반복할 수 있다$($서수수의 감소 순서는 유한하다). 우리는 결과 표현이iterated 기지 Ωα{\displaystyle \alpha}의{\displaystyle \Omega}표현 및 다양한 계수를 적용 표현의 조각( 멱지수 등)관련된(고 Ω{\displaystyle<>< 있다;라고 부른다.\Omega})또는 짧게 줄여서,Ω{\displaystyle \Omega}-pieces. ${\displaystyle \alpha }$ ${\displaystyle \alpha$ $\}.$

ψ의 일부 속성

• 함수 $\psi {\displaystyle }$ ${\displaystyle \psi }$은(는) 감소하지 않고 연속적이다$$(이것은 그 정의에서 다소 명백하다).
• β<>만약 ψ(α))ψ(β){\displaystyle\psi(\alpha)=\psi(\beta)};α{\displaystyle \beta<>\alpha} 다음 반드시 C(α)=C(β){C(\alpha)=C(\beta)\displaystyle}. 실제로, 서수 β′β ≤과{\displaystyle \beta의}β′<>α{\displaystyle\beta \leq \beta '<, \alpha}b. 수 있에elong${\displaystyle C(\alpha )}$ (otherwise its image by ${\displaystyle \psi }$, which is ${\displaystyle \psi (\alpha )}$ would belong to ${\displaystyle C(\alpha )}$ — impossible); so ${\displaystyle C(\beta )}$ is closed by everything under which ${\displaystyle C(\alpha )}$ 폐점이라, 그래서 그들은 동등하다.
• $\psi {\displaystyle }$ =${\displaystyle \psi }$(${\displaystyle \alpha }$) {\$displaystyle \$$gamma =\$$psi$ $(\alpha )}$이$($가) 취한$$ 임의의$$ $값$은 $\$ {\$displaystyle$ \$varepsilon }$ -숫자$$(즉, $\beta {\displaystyle {}^{}}$ Ω ${\displaystyle {\beta }^{}}$ω의 고정점 {\$displaystyled \begeta$ \mpotegeta $$$\be \toome$ }). 실제로 그렇지 않다면 칸토어 정규형태로 작성함으로써 그것보다 적은 원소의 합계, 제품 및 지수를 사용하여 표현할 수 있었고, 따라서 $C{\displaystyle }$${\displaystyle (\alpha )}$ ${\displaystyle C(\alpha$) ${\displaystyle C(\alpha$$)\},$ 따라서 $모순$일 것이다$.$
• Limma:가정하라 δ{\delta\displaystyle}은ε{\displaystyle \varepsilon}-number과 α 서수가ψ(β)<>{\displaystyle \alpha}, 모든β<>에 δ{\displaystyle \psi(\beta)<, \delta};α{\displaystyle \beta<>\alpha}:그 당시의 Ω{\displaystyle \Omega}-pieces(위에 정의한)o.어떤 elemen의t of ${\displaystyle C(\alpha )}$ are less than ${\displaystyle \delta }$. Indeed, let ${\displaystyle C'}$ be the set of ordinals all of whose ${\displaystyle \Omega }$-pieces are less than ${\displaystyle \delta }$. Then ${\displaystyle C'}$ is closed under addition, multiplication 및 지수화($\Delta {\displaystyle }${\$displaystyle \cHB }$은(는) $\Delta {\displaystyle }${\$displaystyle \varepsilon }$ -number이므로$$ 더하기, 곱하기, 지수화 시 닫히는 것보다 적은 서수. 그리고 C′{\displaystyle C의}도 0{0\displaystyle}, 1{1\displaystyle},ω{\displaystyle \omega},Ω{\displaystyle \Omega}가 포함되어 있습니다. 그래서 Cβ<>를 위해 ψ(β){\displaystyle \psi(\beta)}, 가정에 의해 α{\displaystyle \beta<>\alpha}가 포함되어 있습니다.′⊇ C(α){\disp.을 낳$티엘 C'\supseteq C(\alpha )}$이$($가) 보여질 예정이었다.
• 이전의 보조정리인 $\psi {\displaystyle }$ ${\displaystyle (\alpha }$ ${\displaystyle \psi (\alpha )\leq \delta }$의 가설에서, $$Δ C${\displaystyle }$(${\displaystyle \alpha }$ )${\displaystyle \delta \not \in$ C$(\alpha )}$는 $$$\Delta {\displaystyle }$ C (.
• 【\$displaystyle$ $\$$varepsilon$ $}】$의 범위에 있는 일부 요소보다 숫자가$$ 작은 $【\displaystyle$ $\psi }$의 범위에 있는 $【\displaystyle$ $\psi$}($$$즉{\displaystyle }$, $【\displaystyle \varepsilon$} -number$$)】의 범위에 포함되지 않는다$$$$. 만약 δ{\delta\displaystyle}은ε{\displaystyle \varepsilon}-number ψ{\displaystyle \psi}의 범위보다 크지 않실제로,β{\beta\displaystyle}가ψ(β)<>δ{\displaystyle \psi(\beta)<, \delta}의 α{\displaystyle \alpha}최소한 상한:당시로 알려 주십시오. above we have ${\displaystyle \psi (\alpha )\leq \delta }$, but ${\displaystyle \psi (\alpha )<\delta }$ would contradict the fact that ${\displaystyle \alpha }$ is the least upper bound — so ${\displaystyle \psi (\alpha )=\delta }$.
• Whenever ${\displaystyle \psi (\alpha )=\delta }$, the set ${\displaystyle C(\alpha )}$ consists exactly of those ordinals ${\displaystyle \gamma }$ (less than ${\displaystyle \varepsilon _{\Omega +1}}$) all of whose ${\displaystyle \Omega }$-pieces are less than ${\displaysty$$le \delta }$. Indeed, we know that all ordinals less than ${\displaystyle \delta }$, hence all ordinals (less than ${\displaystyle \varepsilon _{\Omega +1}}$) whose ${\displaystyle \Omega }$-pieces are less than ${\displaystyle \delta }$, are in ${\displaystyle C(\alpha )}$. Conversely, if 우리는 모든 < >< > <Δ > <\$displaystyle \psi (\$$displaystyle \property \property$ \property $}$에 대해$$${\displaystyle \Delta }$ $<\displaystyle$=\$propers }$라고 가정한다.$$ 반면에 일부 β<>다면(α)ψ)ψ(β){\displaystyle\psi(\alpha)=\psi(\beta)};α{\displaystyle \beta<>\alpha}, 우리는 이미 우리가 가장 가능한 ψ(α))δ{\dis과 α{\displaystyle \alpha}를 대체할 수 있C(α)=C(β){C(\alpha)=C(\beta)\displaystyle} 말했다.놀$스타일 \cHB(\cHB )=\cHB$$}$

서수 표기법

위의 사실들을 이용하여 바흐만-하워드 서수보다 적은$$ 모든 $\gamma {\displaystyle }${\$displaystyle \gamma}$에 대한 (캐논어) 서수 표기법을 정의할 수 있다. 우리는 이것을 $\gamma {\displaystyle }$ ${\displaystyle \gamma }$에 유도하여 한다$.$

If ${\displaystyle \gamma }$ is less than ${\displaystyle \varepsilon _{0}}$, we use the iterated Cantor normal form of ${\displaystyle \gamma }$. Otherwise, there exists a largest ${\displaystyle \varepsilon }$-number ${\displaystyle \delta }$ less or equal to ${\displaystyle \gamma }$ (this iS때문에 ε{\displaystyle \varepsilon}-numbers의 집합이 닫히는):δ<>γ{\displaystyle \delta<>\gamma}그때 유도에 의해 우리는δ{\delta\displaystyle}에 대한 기호와 기본γ{\displaystyle \gamma}의 δ{\delta\displaystyle}표현 하나 γ{\displayst을 준다 규정해 왔습니다.yle \g$암마$ $\}$ 그래서 우리는 끝났다.

그것은 γ)δ{\displaystyle \gamma =\delta}은ε{\displaystyle \varepsilon}-number 그 사건에 대처하기:우리는, 이 경우에, 우리는 몇몇(아마 무수한)순서 α<>;ε Ω, \varepsilon_{δ)ψ(α){\displaystyle \delta =\psi(\alpha)}+1{\displaystyle \alpha를 쓸 수 있었다고 주장했다 남아 있다.\Omega$+1}$:$\alpha {\displaystyle }$ ${\displaystyle \alpha }$을(를) 가능한 최대 서수(inal$$ ${\displaystyle \psi$}이$$(가) 되도록 한다. $\alpha {\displaystyle }$ ${\displaystyle$ $\Aomega}$의 반복 베이스$$ $\Omega {\displaystyle \mathrm{}}$ ${\displaystyle$ $\alpha }$을(를) 사용한다$.$ 이 표현물의 모든 부분이 $\Delta {\displaystyle }$ ${\\displaystyle \delta }$보다 작다는 것을 보여 주기 위해 이미 표기법을 정의했다.$$ If this is not the case then, by the properties we have shown, ${\displaystyle C(\alpha )}$ does not contain ${\displaystyle \alpha }$; but then ${\displaystyle C(\alpha +1)=C(\alpha )}$ (they are closed under the same operations, since the value of ${\displaystyle \psi }$ at ${\dis$$playstyle \$$cHB$$}$을(를) 절대 취할 수 없으므로$$ $so{\displaystyle (\mathrm{\alpha }}$+ 1${\displaystyle }$)${\displaystyle }$=${\displaystyle \Delta }$ ${\displaystyle$\$\(\\ +1)=\\(\\ )=\\}}}$의 $최대성$과 모순된다$.$

참고: 실제로 우리는 바흐만-하워드 서수보다 낮은 서수뿐만 아니라, 특정 서수, 즉 $\Omega {\displaystyle \mathrm{}}$ ${\displaystyle \Oomega}$ -피스가$$ 바흐만-하워드 서수(viz.: 반복된 베이스 $\Omega {\displaystyle \mathrm{}}$ ${\displaystyle \Oomega}$에 기록하여 c를 사용한다.모든 작품에 대한 비논리적 표현). 이 표준 표기법은 $\psi {\displaystyle }$ ${\displaystyle \psi }$ 함수의$$ 인수에 사용된다(이것은 계산할 수 없는 것일 수 있음).

예

$\epsilon {\displaystyle {}_{}}$ ${\displaystyle {0\mathrm{}}_{}}$= ${\displaystyle \mathrm{\psi }}$( 0${\displaystyle }$) ${\displaystyle \varepsilon _{0}=\psi (0)}$보다 작은 서수의 경우 정의된 표준서수 표기법은 반복된 캔터 정규 형식(정의에 따라)과 일치한다$.$

For ordinals less than ${\displaystyle \varepsilon _{1}=\psi (1)}$, the notation coincides with iterated base ${\displaystyle \varepsilon _{0}}$ notation (the pieces being themselves written in iterated Cantor normal form): e.g., ${\displaystyle \omega ^{\omega ^{\varepsilon _{0}+\o$$mega }}}$ will be written ${\displaystyle {\varepsilon _{0}}^{\omega ^{\omega }}}$, or, more accurately, ${\displaystyle \psi (0)^{\omega ^{\omega }}}$. For ordinals less than ${\displaystyle \varepsilon _{2}=\psi (2)}$, we similarly write in iterated base ${\displaystyle {\epsilon }_1}$${\displaystyle \varepsilon _{1}}$ and then write the pieces in iterated base ${\displaystyle \varepsilon _{0}}$ (and write the pieces of that in iterated Cantor normal form): so ${\displaystyle \omega ^{\omega ^{\varepsilon _{1}+\varepsilon _{0}+1}}}$ is written ${$$\displaystyle {\varepsilon _{1}}^{\varepsilon _{0}\omega }}$, or, more accurately, ${\displaystyle \psi (1)^{\psi (0)\,\omega }}$. Thus, up to ${\displaystyle \zeta _{0}=\psi (\Omega )}$, we always use the largest possible ${\displaystyle \varepsilon }$-number base which gives a non-tri바이알 표현

이 외에도, 우리는 $\Omega {\displaystyle \mathrm{}}${\$displaystyle \Oomega}$을(를) 초과하는 서수들을 표현할 필요가 있을 수 있다$:$ 이것은 항상 반복된 $\Omega {\displaystyle \mathrm{}}$ ${\displaystyle \Oomega}$ - 베이스에서$$ 이루어지며, 조각들 자체는 비교표현을 할 수 있는 가장 큰 $base{\displaystyle }$ ${\displaystystyle \varepsilon$} -number$$ base를 사용하여 표현해야 한다.

$\psi {\displaystyle ({\mathrm{\epsilon }}_{}}$ ${\displaystyle {\Omega \mathrm{}}_{}}$+ 1${\displaystyle {}_{}}$) ${\displaystyle \psi(\varerpsilon _{\Oomega +1})$는 바흐만-하워드 서수(Bachmann-Howard 서수)와 동일하지만, 이것은 우리가 정의한 의미에서 "캐논 표기법"이 아니라는 점에 유의하십시오(카논어 표기법은 바흐만-하워드 서수보다 작은 서수식에 대해서만 정의된다).

규범성 조건

따라서 정의된 표기법에는 $\psi {\displaystyle }${\$displaystyle \psi$} 함수를$$ 중첩할 때마다 "inner" $\psi {\displaystyle }${\$displaystyle \psi$} 함수의$$ 인수가 항상 "Outer" 함수의 인수보다 작다는 속성이 있다(이는 $\Omega {\displaystyle \mathrm{}}$ ${\$$displaystyle \Alpha$$$$}$의 피스가$$ $\alpha {\displaystyle }$ ${\$picescs$.$ 여기서 $\alpha {\displaystyle }$ ${\displaystyle \alpha$}은$($는) 일부 $\epsilon {\displaystyle }$${\displaystyle (\alpha }$)${\displaystyle }$= ${\displaystyle \Delta }$ ${\displaystyle$\ \ $(\deplaystyle$ \$psi)=\display }$이$($가$)$ 일부$$$$ε ${\displaysty \$$delta$$\delta {\displaystyle }$}보다 모두 $\Delta {\displaystyle }$ ${\displaystystypt }$보다 작을(으)만큼 가장$$ 크다. For example, ${\displaystyle \psi (\psi (\Omega )+1)}$ does not occur as a notation: it is a well-defined expression (and it is equal to ${\displaystyle \psi (\Omega )=\zeta _{0}}$ since ${\displaystyle \psi }$ is constant between ${\displaystyle \zeta _{0}}$ and ${\disp$$laystyle$ \Oomega$})$ 그러나 그것은 우리가 개략적으로 설명한 귀납 알고리즘에 의해 생성된 표기법은 아니다.

표준성은 재귀적으로 확인할 수 있다: 표현은 표준적인 것으로서,$$${\displaystyle {\epsilon \mathrm{}}_{}}$ 0 ${\$보다 작은 서수의 반복된 칸토어 정규 형태 또는 일부 $\Delta {\displaystyle }$= ${\displaystyle \psi }$(${\displaystyle \alpha }$) ${\displaysty \$$delta }$의 반복된$$ 기본 형태인 경우에만 표준적이다.$\alpha {\displaystyle }$ ${\displaystyle \alpha$}이$($가) 자체로$$ 반복된 베이스$\Omega$으로 작성된$$ $델타$=\$psi(\alpha$ )$$\$displaystyle \Oomega}$은($이{\displaystyle \mathrm{}}$) 조각이 표준적이고 $\Delta {\displaystyle }$ ${\$$displaysty$ $\$$delta }$보다 작은 모든 것을 나타냄$$$).$ 모든 레벨의 사전 확인으로 순서를 확인한다$({\$discompicogicographicogicogicogicanical 검증한다.$}}$은(는) $\psi {\displaystyle }$ ${\displaystyle \psi }$에서 얻은 어떤$$표현보다 크며, 표준 값의 $경우{\displaystyle }$ values ${\displaystyle \psi}$은(는) 항상 덜 또는 심지어 덜 임의의 합계$$, 제품 및 지수(소수의 값)를 능가한다.

For example, ${\displaystyle \psi (\Omega ^{\omega +1}\,\psi (\Omega )+\psi (\Omega ^{\omega })^{\psi (\Omega ^{2})}42)^{\psi (1729)\,\omega }}$ is a canonical notation for an ordinal which is less than the Feferman–Schütte ordinal: it can be written using the Veblen functions as ${\displaystyle \phi _{1}(\phi _{\omega +1}(\phi _{2}(0))+\phi _{\omega }(0)^{\phi _{3}(0)}42)^{\phi _{1}(1729)\,\omega }}$.

Concerning the order, one might point out that ${\displaystyle \psi (\Omega ^{\Omega })}$ (the Feferman–Schütte ordinal) is much more than ${\displaystyle \psi (\Omega ^{\psi (\Omega )})=\phi _{\phi _{2}(0)}(0)}$ (because ${\displaystyle \Omega }$ is greater than ${\displaystyle }$${\displaystyle \psi }$ of anything), and ${\displaystyle \psi (\Omega ^{\psi (\Omega )})=\phi _{\phi _{2}(0)}(0)}$ is itself much more than ${\displaystyle \psi (\Omega )^{\psi (\Omega )}=\phi _{2}(0)^{\phi _{2}(0)}}$ (because ${\displaystyle }$${\displaystyle \Omega ^{\psi (\Omega )}}$ is greater than ${\displaystyle \Omega }$, so any sum-product-or-exponential expression involving ${\displaystyle \psi (\Omega )}$ and smaller value will remain less than ${\displaystyle \psi (\Omega ^{\Omega })}$). 실제로 $\psi {\displaystyle }$(${\displaystyle \mathrm{\Omega }{}^{}}$) ${\displaystyle {\psi }^{}}$ $){\$은(는) 이미${\displaystyle }already{\displaystyle }$ (${\displaystyle \mathrm{\Omega }}$+ ${\displaystyle 1}$ $){\displaysty \psi (\Oomega$+1$)$보다 작다$$$.$

순서형 표기 표준 순서

바흐만-하워드 서수(모두 계산 가능한 동일성) 아래에 서수의 표기법을 정의했다는 사실을 목격하기 위해, 우리는 그 중 하나에 수렴하는 표준 시퀀스를 정의할 수 있다(물론 그것이 한계 서수라면). 실제로 우리는 특정 비할 수 없는 서수들, 즉 카운트할 수 없는 공완성의 헤아릴 수 없는 서수들(우리가 그것들에 수렴하는 순서를 정의하기를 희망한다면...)에 대해서도 표준 서열을 정의할 것이다. 이 서수는 (즉$$, 모든$\Omega {\displaystyle \mathrm{}}$ {\$style$\Oomega$}$ - 피스가 바흐만-하워드 서수보다 작다.

마지막 규칙을 제외하고 다음 규칙은 다소 명백하다.

• First, get rid of the (iterated) base ${\displaystyle \delta }$ representations: to define a standard sequence converging to ${\displaystyle \alpha =\delta ^{\beta _{1}}\gamma _{1}+\cdots +\delta ^{\beta _{k}}\gamma _{k}}$, where ${\displaystyle \delta }$ is either ${\displaystyle \omega }$${\displaystyle \omega }$ 또는$$ $\psi {\displaystyle (\cdots )}$ ${\displaystyle \psi(\cdots )}($또는 $\Omega {\displaystyle \mathrm{}}$ ${\displaystyle \Oomega$ 그러나 아래 참조):
  • $k{\displaystyle }$ ${\displaystyle k}$이(가) 0이면 ${\displaystyle \mathrm{\alpha }}$= 0 ${\displaystyle \cHB$ =$0}$이며 수행할 작업이$$ 없음.
  • $\beta {\displaystyle {}_{}}$ ${\displaystyle k_{}}$ ${\$가 0이고 $\gamma {\displaystyle {}_{}}$ {\$displaystyle \property_{k}$가 후계자라면$$, $\alpha {\displaystyle }$ ${\displaystyle \property \$property }이(가)가 후계자이므로$$ 할 일이 없다.
  • $\gamma {\displaystyle {}_{}}$ ${\displaystyle k_{}}$ ${\$이(가) 제한적인 경우 $display$ k {\displaystyle $\property_{k}$로 수렴되는 표준 시퀀스를 취하고 해당$$ 시퀀스의 요소에 의한 표현으로 ${\displaystyle {replace}_{}}$ k ${\$을 대체한다.
  • if ${\displaystyle \gamma _{k}}$ is successor and ${\displaystyle \beta _{k}}$ is limit, rewrite the last term ${\displaystyle \delta ^{\beta _{k}}\gamma _{k}}$ as ${\displaystyle \delta ^{\beta _{k}}(\gamma _{k}-1)+\delta ^{\beta _{k}}}$ and 마지막 기간의 지수$$ $\beta {\displaystyle {}_{}}$ ${\displaystyle k_{}}$ ${\$를 수렴하는 기본 시퀀스의 요소로 대체한다.
  • if ${\displaystyle \gamma _{k}}$ is successor and ${\displaystyle \beta _{k}}$ is also, rewrite the last term ${\displaystyle \delta ^{\beta _{k}}\gamma _{k}}$ as ${\displaystyle \delta ^{\beta _{k}}(\gamma _{k}-1)+\delta ^{\beta _{k}-1}$$\cHB }$과(와) 이 표현식의 마지막$$ $\Delta {\displaystyle }$ ${\displaystyle$\ \}을$($를) 수렴하는 기본 시퀀스의 요소로 대체하십시오.
• $\Delta {\displaystyle }$ ${\$$displaystyle$ $\$$delta$ $}$이(가)$\Omega$인 경우,$$$\Delta$의 기본 시퀀스로 명백한$$ $0{\displaystyle \mathrm{},}$ 1, ${\displaystyle 2}$,${\displaystyle 3,}$ …$${\$displaystyle 0,1$,2$,3,\ldots$ $}$을(를$)$ 취하십시오$.$
• $\Delta {\displaystyle }$= ${\displaystyle \Delta }$(${\displaystyle 0}$) ${\displaystyle$ $\delta$ $=\psi (0$$)}$의 시퀀스$$$\Omega {\displaystyle }$ ,${\displaystyle {\Omega }^{}{}^{}}$ , Ω ${\displaystyle {\Omega {}^{}}^{}}$ ,$$Ω , … {\$displaystyle$ \$omega \$omega$^{\omega$},\$dots}$의 기본 시퀀스로 삼는다$$.
• If ${\displaystyle \delta =\psi (\alpha +1)}$ then take as fundamental sequence for ${\displaystyle \delta }$ the sequence ${\displaystyle \psi (\alpha ),\psi (\alpha )^{\psi (\alpha )},\psi (\alpha )^{\psi (\alpha )^{\psi (\alpha )}},\ldots }$
• If ${\displaystyle \delta =\psi (\alpha )}$ where ${\displaystyle \alpha }$ is a limit ordinal of countable cofinality, define the standard sequence for ${\displaystyle \delta }$ to be obtained by applying ${\displaystyle \psi }$ to the standard sequence for ${\displaystyle \alpha }$ (recall that $$${\displaystyle \psi }$ $[\displaystyle \psi }$이(가) 연속적이고 증가함, 여기에서).
• $\Delta {\displaystyle }$= ${\displaystyle \alpha }$(${\displaystyle \alpha }$ ${\displaystyle )}$ ${\displaystyle \delta =\psi (\alpha )}$ $\alpha {\displaystyle }$ ${\displaystyle \alpha }$이(가) 탑재된 경우(예: $\Omega {\displaystyle \mathrm{}}$ ${\displaystyle \Oomega }$ 그 자체$$)를 처리하는 것이 남아 있다. 이것은 명백히 시퀀스 이 경우에는{\displaystyle \alpha}α 받침 해 주는 정의하기;어떤 ρ를<>에, 우리는 무엇이라 정의할 수 있는 시퀀스 converging, 가산 cofinality고 ψ{\displaystyle \psi}ρ{\displaystyle \rho}사이에 끊임없이에 α{\displaystyle \rho<>\alpha}이치에 맞지 않습니다. 그리고 ${\displaystyle \alpha }$. This ${\displaystyle \rho }$ will be the first fixed point of a certain (continuous and non-decreasing) function ${\displaystyle \xi \mapsto h(\psi (\xi ))}$. To find it, apply the same rules (from the base ${\displaystyle \Omega }$ representation of ${\displaystyle$$\alpha }$) as to find the canonical sequence of ${\displaystyle \alpha }$, except that whenever a sequence converging to ${\displaystyle \Omega }$ is called for (something which cannot exist), replace the ${\displaystyle \Omega }$ in question, in the expression of ${\displaystyle \alpha =h(\Omega )}$, by a ${\displaystyle \psi (\xi )}$ (where ${\displaystyle \xi }$ is a variable) and perform a repeated iteration (starting from ${\displaystyle 0}$, say) of the function ${\displaystyle \xi \mapsto h(\psi (\xi ))}$: this gives a sequence ${\dis$$playstyle 0,h(\psi (0)),h(\psi (h(\psi (0)))),\ldots }$ tending to ${\displaystyle \rho }$, and the canonical sequence for ${\displaystyle \psi (\alpha )=\psi (\rho )}$ is ${\displaystyle \psi (0)}$, ${\displaystyle \psi (h(\psi (0)))}$, ${$$\displaystyle \property (h(\property (0)))}}...$ $\Delta {\displaystyle }$ ${\displaystyle \$$delta$$}$에 대한 기본 시퀀스의 n ${\$displaystyle $n}$ 요소$$($0{\displaystyle \mathrm{}}$ ${\$$displaystyle$ $0$에서 시작)를 $\Delta {\displaystyle }$[$]$로 표시하도록 하면, 재귀법을 사용하여 이 점을 보다 명확하게 설명할 수 있다$.$ 이 표기법을 사용하면 ${\displaystyle \mathrm{\Delta }}$[ 0 ${\displaystyle ]}$= ${\displaystyle \mathrm{\psi }}$( 0${\displaystyle }$) ${\displaystyle \delta [0]=\psi (0)}$을(를) 꽤$$ 쉽게 알 수 있다. 우리는 재귀로 나머지 시퀀스를 ${\displaystyle \mathrm{정의}}$할 수 있다: $\Delta {\displaystyle }$[ ${\displaystyle n]}$ = ${\displaystyle (}$ (${\displaystyle h}$(${\displaystyle \mathrm{\Delta }}$[ n -${\displaystyle }$1$]$ )$${\$displaystyle \delta$ [n$]=\psi$(h(\$delta$ [n-1$])\}).$ (아래 예시에서는 이것을 더 명확하게 해야 한다.)

마지막(가장 흥미로운) 사례에 대한 몇 가지 예를 들어보자.

• The canonical sequence for ${\displaystyle \psi (\Omega )}$ is: ${\displaystyle \psi (0)}$, ${\displaystyle \psi (\psi (0))}$, ${\displaystyle \psi (\psi (\psi (0)))}$... 이것은 실제로 $\rho {\displaystyle }$= ${\displaystyle \psi }$(${\displaystyle \mathrm{\Omega }}$)${\displaystyle }$= ${\displaystyle {\zeta \mathrm{}}_{}}$ 0 ${\$에 수렴되며, 그 후$$ $\psi {\displaystyle }$ ${\displaystyle \psi$}은 $\Omega {\displaystyle \mathrm{}}$ ${\displaystystyle \Obe}$까지 일정하다$.$
• The canonical sequence for ${\displaystyle \psi (\Omega 2)}$ is: ${\displaystyle \psi (0)}$, ${\displaystyle \psi (\Omega +\psi (0))}$, ${\displaystyle \psi (\Omega +\psi (\Omega +\psi (0))),\ldots }$ This indeed converges to the value of ${\displays$$tyle \psi$} $at$ = ${\displaystyle \mathrm{\Omega }}$+ ${\displaystyle \psi }$ ${\displaystyle (\mathrm{\Omega }}$ 2${\displaystyle }$)${\displaystyle }$= ${\displaystyle \mathrm{\Omega }}$+ ${\displaystyle {\zeta \mathrm{}}_{}}$ 1 ${\$(\$Oome2)=\Oomega +\$$zeta$$_{1}}$이후$$ $\psi {\displaystyle \mathrm{}}$ ${\$$displaystystyle$\iote $Optogue$}}이 ${\displaystyle 2}$ ${}$까지 일정하다$.$
• The canonical sequence for ${\displaystyle \psi (\Omega ^{2})}$ is: ${\displaystyle \psi (0),\psi (\Omega \psi (0)),\psi (\Omega \psi (\Omega \psi (0))),\ldots }$ This converges to the value of ${\displaystyle \psi }$ at ${\displaysty$$\rho =\Oomega \psi(\Oomega ^{2})}$.
• The canonical sequence for ${\displaystyle \psi (\Omega ^{2}3+\Omega )}$ is ${\displaystyle \psi (0),\psi (\Omega ^{2}3+\psi (0)),\psi (\Omega ^{2}3+\psi (\Omega ^{2}3+\psi (0))),\ldots }$ This converges to the value of ${\d$$isplaystyle \psi$} $at$ = ${\displaystyle {\mathrm{}}^{}}$ 2 ${\displaystyle {}^{}\mathrm{}}$+ ${\displaystyle \psi }$ ${\displaystyle ({\mathrm{}}^{}}$ ${\displaystyle {2\mathrm{}}^{}}$ ${\displaystyle {}^{}\mathrm{}}$+ ${\displaystyle \mathrm{\Omega }}$) ${\displaystyle \rho =\Oomega ^{2}3+\psi(\Oomega ^{2}3+\Oomega$ $)\}.$
• The canonical sequence for ${\displaystyle \psi (\Omega ^{\Omega })}$ is: ${\displaystyle \psi (0),\psi (\Omega ^{\psi (0)}),\psi (\Omega ^{\psi (\Omega ^{\psi (0)})}),\ldots }$ This converges to the value of ${\displaystyle \psi }$ at ${\displaystyle \rho ={\mathrm{\Omega }}^{}}$${\displaystyle {\psi }^{}}$(${\displaystyle {{\mathrm{}}^{}}^{}}$ ${\displaystyle {{\Omega \mathrm{}}^{}}^{}}$) ${\$ $\}\}\}\}\}\}.$
• The canonical sequence for ${\displaystyle \psi (\Omega ^{\Omega }3)}$ is: ${\displaystyle \psi (0),\psi (\Omega ^{\Omega }2+\Omega ^{\psi (0)}),\psi (\Omega ^{\Omega }2+\Omega ^{\psi (\Omega ^{\Omega }2+\Omega ^{\psi ($$0)})}),\ldots }$ This converges to the value of ${\displaystyle \psi }$ at ${\displaystyle \rho =\Omega ^{\Omega }2+\Omega ^{\psi (\Omega ^{\Omega }3)}}$.
• The canonical sequence for ${\displaystyle \psi (\Omega ^{\Omega +1})}$ is: ${\displaystyle \psi (0),\psi (\Omega ^{\Omega }\psi (0)),\psi (\Omega ^{\Omega }\psi (\Omega ^{\Omega }\psi (0))),\ldots }$ This converges to the value of ${\dis$$\rho {\displaystyle }$ =${\displaystyle {\mathrm{}}^{}}$ ${\displaystyle {}^{}{1}^{}}$ (${\displaystyle {\mathrm{}}^{}}$ ${\displaystyle {\Omega \mathrm{}}^{}}$+ 1${\displaystyle {}^{}}$)의 플레이 스타일$$$\psi$\$displaystyle \rho =\Oomega ^{\Oomega ^}\psi(\Oomega ^{\\Oomega +1})$.
• The canonical sequence for ${\displaystyle \psi (\Omega ^{\Omega ^{2}+\Omega 3})}$ is: ${\displaystyle \psi (0),\psi (\Omega ^{\Omega ^{2}+\Omega 2+\psi (0)}),\psi (\Omega ^{\Omega ^{2}+\Omega 2+\p$$si(\Oomega ^{\Oomega ^{2}+\Oomega 2+\psi (0)})),\ldots }$

다른 사례의 몇 가지 예는 다음과 같다.

• $\Omega {\displaystyle {}^{}}$ ${\displaystyle {2\mathrm{}}^{}}$ ${\$의 정식 순서는$$: $0{\displaystyle \mathrm{}}$ ${\displaystyle$ 0$},$ Ω {\$displaystyle \omega$},$$$\Omega {\displaystyle }$ ${\displaystyle 2}$ ${\displaystyle$ $\$$omega$ 2$},$${\displaystyle \mathrm{\Omega }}$ 3 ${\displaystystylease$ \$omega 3}...$
• The canonical sequence for ${\displaystyle \psi (\omega ^{\omega })}$ is: ${\displaystyle \psi (1)}$, ${\displaystyle \psi (\omega )}$, ${\displaystyle \psi (\omega ^{2})}$, ${\displaystyle \psi (\omega ^{3})}$...
• The canonical sequence for ${\displaystyle \psi (\Omega )^{\omega }}$ is: ${\displaystyle 1}$, ${\displaystyle \psi (\Omega )}$, ${\displaystyle \psi (\Omega )^{2}}$, ${\displaystyle \psi (\Omega )^{3}}$...
• The canonical sequence for ${\displaystyle \psi (\Omega +1)}$ is: ${\displaystyle \psi (\Omega )}$, ${\displaystyle \psi (\Omega )^{\psi (\Omega )}}$, ${\displaystyle \psi (\Omega )^{\psi (\Omega )^{\psi (\Omega )}}}$...
• The canonical sequence for ${\displaystyle \psi (\Omega +\omega )}$ is: ${\displaystyle \psi (\Omega )}$, ${\displaystyle \psi (\Omega +1)}$, ${\displaystyle \psi (\Omega +2)}$, ${\displaystyle \psi (\Omega +3)}$...
• The canonical sequence for ${\displaystyle \psi (\Omega \omega )}$ is: ${\displaystyle \psi (0)}$, ${\displaystyle \psi (\Omega )}$, ${\displaystyle \psi (\Omega 2)}$, ${\displaystyle \psi (\Omega 3)}$...
• The canonical sequence for ${\displaystyle \psi (\Omega ^{\omega })}$ is: ${\displaystyle \psi (1)}$, ${\displaystyle \psi (\Omega )}$, ${\displaystyle \psi (\Omega ^{2})}$, ${\displaystyle \psi (\Omega ^{3})}$...
• The canonical sequence for ${\displaystyle \psi (\Omega ^{\psi (0)})}$ is: ${\displaystyle \psi (\Omega ^{\omega })}$, ${\displaystyle \psi (\Omega ^{\omega ^{\omega }})}$, ${\displaystyle \psi (\Omega ^{\omega ^{\omega ^{\omega }}})}$... (this is $\psi {\displaystyle }$( ${\displaystyle 0}$) ${\displaystyle \psi (0)}$의 기본 시퀀스에서 파생됨.$$
• The canonical sequence for ${\displaystyle \psi (\Omega ^{\psi (\Omega )})}$ is: ${\displaystyle \psi (\Omega ^{\psi (0)})}$, ${\displaystyle \psi (\Omega ^{\psi (\psi (0))})}$, ${\displaystyle \psi (\Omega ^{\psi (\psi (\psi (0)$$))}}}...$ (이것은 위에서 주어진$$$\psi {\displaystyle }$($){\displaystyle \psi (\Oomega )}$에 대한 기본 시퀀스에서 도출된 것이다.

Even though the Bachmann–Howard ordinal ${\displaystyle \psi (\varepsilon _{\Omega +1})}$ itself has no canonical notation, it is also useful to define a canonical sequence for it: this is ${\displaystyle \psi (\Omega )}$, ${\displaystyle \psi (\Omega ^{\Omega })}$, ${\displaystyle \psi (\Omega ^{\Omega ^{\Omega }})}$...

A terminating process

Start with any ordinal less than or equal to the Bachmann–Howard ordinal, and repeat the following process so long as it is not zero:

• if the ordinal is a successor, subtract one (that is, replace it with its predecessor),
• if it is a limit, replace it by some element of the canonical sequence defined for it.

Then it is true that this process always terminates (as any decreasing sequence of ordinals is finite); however, like (but even more so than for) the hydra game:

1. it can take a very long time to terminate,
2. the proof of termination may be out of reach of certain weak systems of arithmetic.

To give some flavor of what the process feels like, here are some steps of it: starting from ${\displaystyle \psi (\Omega ^{\Omega ^{\omega }})}$ (the small Veblen ordinal), we might go down to ${\displaystyle \psi (\Omega ^{\Omega ^{3}})}$, from there down to ${\displaystyle \psi (\Omega ^{\Omega ^{2}\psi (0)})}$, then ${\displaystyle \psi (\Omega ^{\Omega ^{2}\omega ^{\omega }})}$ then ${\displaystyle \psi (\Omega ^{\Omega ^{2}\omega ^{3}})}$ then ${\displaystyle \psi (\Omega ^{\Omega ^{2}\omega ^{2}3})}$ then ${\displaystyle \psi (\Omega ^{\Omega ^{2}(\omega ^{2}2+\omega )})}$ then ${\displaystyle \psi (\Omega ^{\Omega ^{2}(\omega ^{2}2+1)})}$ then ${\displaystyle \psi (\Omega ^{\Omega ^{2}\omega ^{2}2+\Omega \psi (\Omega ^{\Omega ^{2}\omega ^{2}2+\Omega \psi (0)})})}$ then ${\displaystyle \psi (\Omega ^{\Omega ^{2}\omega ^{2}2+\Omega \psi (\Omega ^{\Omega ^{2}\omega ^{2}2+\Omega \omega ^{\omega ^{\omega }}})})}$ and so on. It appears as though the expressions are getting more and more complicated whereas, in fact, the ordinals always decrease.

Concerning the first statement, one could introduce, for any ordinal ${\displaystyle \alpha }$ less or equal to the Bachmann–Howard ordinal ${\displaystyle \psi (\varepsilon _{\Omega +1})}$, the integer function ${\displaystyle f_{\alpha }(n)}$ which counts the number of steps of the process before termination if one always selects the ${\displaystyle n}$'th element from the canonical sequence (this function satisfies the identity ${\displaystyle f_{\alpha }(n)=f_{\alpha [n]}(n)+1}$). Then ${\displaystyle f_{\alpha }}$ can be a very fast growing function: already ${\displaystyle f_{\omega ^{\omega }}(n)}$ is essentially ${\displaystyle n^{n}}$, the function ${\displaystyle f_{\psi (\Omega ^{\omega })}(n)}$ is comparable with the Ackermann function ${\displaystyle A(n,n)}$, and ${\displaystyle f_{\psi (\varepsilon _{\Omega +1})}(n)}$ is comparable with the Goodstein function. If we instead make a function that satisfies the identity ${\displaystyle g_{\alpha }(n)=g_{\alpha [n]}(n+1)+1}$, so the index of the function increases it is applied, then we create a much faster growing function: ${\displaystyle g_{\psi (0)}(n)}$ is already comparable to the Goodstein function, and ${\displaystyle g_{\psi (\Omega ^{\Omega ^{\omega }\omega })}(n)}$ is comparable to the TREE function.

Concerning the second statement, a precise version is given by ordinal analysis: for example, Kripke–Platek set theory can prove^[4] that the process terminates for any given ${\displaystyle \alpha }$ less than the Bachmann–Howard ordinal, but it cannot do this uniformly, i.e., it cannot prove the termination starting from the Bachmann–Howard ordinal. Some theories like Peano arithmetic are limited by much smaller ordinals (${\displaystyle \varepsilon _{0}}$ in the case of Peano arithmetic).

Variations on the example

Making the function less powerful

It is instructive (although not exactly useful) to make ${\displaystyle \psi }$ less powerful.

If we alter the definition of ${\displaystyle \psi }$ above to omit exponentiation from the repertoire from which ${\displaystyle C(\alpha )}$ is constructed, then we get ${\displaystyle \psi (0)=\omega ^{\omega }}$ (as this is the smallest ordinal which cannot be constructed from ${\displaystyle 0}$, ${\displaystyle 1}$ and ${\displaystyle \omega }$ using addition and multiplication only), then ${\displaystyle \psi (1)=\omega ^{\omega ^{2}}}$ and similarly ${\displaystyle \psi (\omega )=\omega ^{\omega ^{\omega }}}$, ${\displaystyle \psi (\psi (0))=\omega ^{\omega ^{\omega ^{\omega }}}}$ until we come to a fixed point which is then our ${\displaystyle \psi (\Omega )=\varepsilon _{0}}$. We then have ${\displaystyle \psi (\Omega +1)={\varepsilon _{0}}^{\omega }}$ and so on until ${\displaystyle \psi (\Omega 2)=\varepsilon _{1}}$. Since multiplication of ${\displaystyle \Omega }$'s is permitted, we can still form ${\displaystyle \psi (\Omega ^{2})=\phi _{2}(0)}$ and ${\displaystyle \psi (\Omega ^{3})=\phi _{3}(0)}$ and so on, but our construction ends there as there is no way to get at or beyond ${\displaystyle \Omega ^{\omega }}$: so the range of this weakened system of notation is ${\displaystyle \psi (\Omega ^{\omega })=\phi _{\omega }(0)}$ (the value of ${\displaystyle \psi (\Omega ^{\omega })}$ is the same in our weaker system as in our original system, except that now we cannot go beyond it). This does not even go as far as the Feferman–Schütte ordinal.

If we alter the definition of ${\displaystyle \psi }$ yet some more to allow only addition as a primitive for construction, we get ${\displaystyle \psi (0)=\omega ^{2}}$ and ${\displaystyle \psi (1)=\omega ^{3}}$ and so on until ${\displaystyle \psi (\psi (0))=\omega ^{\omega ^{2}}}$ and still ${\displaystyle \psi (\Omega )=\varepsilon _{0}}$. This time, ${\displaystyle \psi (\Omega +1)=\varepsilon _{0}\omega }$ and so on until ${\displaystyle \psi (\Omega 2)=\varepsilon _{1}}$ and similarly ${\displaystyle \psi (\Omega 3)=\varepsilon _{2}}$. But this time we can go no further: since we can only add ${\displaystyle \Omega }$'s, the range of our system is ${\displaystyle \psi (\Omega \omega )=\varepsilon _{\omega }=\phi _{1}(\omega )}$.

In both cases, we find that the limitation on the weakened ${\displaystyle \psi }$ function comes not so much from the operations allowed on the countable ordinals as on the uncountable ordinals we allow ourselves to denote.

Going beyond the Bachmann–Howard ordinal

We know that ${\displaystyle \psi (\varepsilon _{\Omega +1})}$ is the Bachmann–Howard ordinal. The reason why ${\displaystyle \psi (\varepsilon _{\Omega +1}+1)}$ is no larger, with our definitions, is that there is no notation for ${\displaystyle \varepsilon _{\Omega +1}}$ (it does not belong to ${\displaystyle C(\alpha )}$ for any ${\displaystyle \alpha }$, it is always the least upper bound of it). One could try to add the ${\displaystyle \varepsilon }$ function (or the Veblen functions of so-many-variables) to the allowed primitives beyond addition, multiplication and exponentiation, but that does not get us very far. To create more systematic notations for countable ordinals, we need more systematic notations for uncountable ordinals: we cannot use the ${\displaystyle \psi }$ function itself because it only yields countable ordinals (e.g., ${\displaystyle \psi (\Omega +1)}$ is, ${\displaystyle \varepsilon _{\phi _{2}(0)+1}}$, certainly not ${\displaystyle \varepsilon _{\Omega +1}}$), so the idea is to mimic its definition as follows:

Let ${\displaystyle \psi _{1}(\alpha )}$ be the smallest ordinal which cannot be expressed from all countable ordinals, ${\displaystyle \Omega }$ and ${\displaystyle \Omega _{2}}$ using sums, products, exponentials, and the ${\displaystyle \psi _{1}}$ function itself (to previously constructed ordinals less than ${\displaystyle \alpha }$).

Here, ${\displaystyle \Omega _{2}}$ is a new ordinal guaranteed to be greater than all the ordinals which will be constructed using ${\displaystyle \psi _{1}}$: again, letting ${\displaystyle \Omega =\omega _{1}}$ and ${\displaystyle \Omega _{2}=\omega _{2}}$ works.

For example, ${\displaystyle \psi _{1}(0)=\varepsilon _{\Omega +1}}$, and more generally ${\displaystyle \psi _{1}(\alpha )=\varepsilon _{\Omega +1+\alpha }}$ for all countable ordinals and even beyond (${\displaystyle \psi _{1}(\Omega )=\varepsilon _{\Omega 2}}$ and ${\displaystyle \psi _{1}(\psi _{1}(0))=\varepsilon _{\varepsilon _{\Omega +1}}}$): this holds up to the first fixed point ${\displaystyle \zeta _{\Omega +1}}$ beyond ${\displaystyle \Omega }$ of the ${\displaystyle \xi \mapsto \varepsilon _{\xi }}$ function, which is the limit of ${\displaystyle \psi _{1}(0)}$, ${\displaystyle \psi _{1}(\psi _{1}(0))}$ and so forth. Beyond this, we have ${\displaystyle \psi _{1}(\alpha )=\zeta _{\Omega +1}}$ and this remains true until ${\displaystyle \Omega _{2}}$: exactly as was the case for ${\displaystyle \psi (\Omega )}$, we have ${\displaystyle \psi _{1}(\Omega _{2})=\zeta _{\Omega +1}}$ and ${\displaystyle \psi _{1}(\Omega _{2}+1)=\varepsilon _{\zeta _{\Omega +1}+1}}$.

The ${\displaystyle \psi _{1}}$ function gives us a system of notations (assuming we can somehow write down all countable ordinals!) for the uncountable ordinals below ${\displaystyle \psi _{1}(\varepsilon _{\Omega _{2}+1})}$, which is the limit of ${\displaystyle \psi _{1}(\Omega _{2})}$, ${\displaystyle \psi _{1}({\Omega _{2}}^{\Omega _{2}})}$ and so forth.

Now we can reinject these notations in the original ${\displaystyle \psi }$ function, modified as follows:

${\displaystyle \psi (\alpha )}$ is the smallest ordinal which cannot be expressed from ${\displaystyle 0}$, ${\displaystyle 1}$, ${\displaystyle \omega }$, ${\displaystyle \Omega }$ and ${\displaystyle \Omega _{2}}$ using sums, products, exponentials, the ${\displaystyle \psi _{1}}$ function, and the ${\displaystyle \psi }$ function itself (to previously constructed ordinals less than ${\displaystyle \alpha }$).

This modified function ${\displaystyle \psi }$ coincides with the previous one up to (and including) ${\displaystyle \psi (\psi _{1}(0))}$ — which is the Bachmann–Howard ordinal. But now we can get beyond this, and ${\displaystyle \psi (\psi _{1}(0)+1)}$ is ${\displaystyle \varepsilon _{\psi (\psi _{1}(0))+1}}$ (the next ${\displaystyle \varepsilon }$-number after the Bachmann–Howard ordinal). We have made our system doubly impredicative: to create notations for countable ordinals we use notations for certain ordinals between ${\displaystyle \Omega }$ and ${\displaystyle \Omega _{2}}$ which are themselves defined using certain ordinals beyond ${\displaystyle \Omega _{2}}$.

A variation on this scheme, which makes little difference when using just two (or finitely many) collapsing functions, but becomes important for infinitely many of them, is to define

${\displaystyle \psi (\alpha )}$ is the smallest ordinal which cannot be expressed from ${\displaystyle 0}$, ${\displaystyle 1}$, ${\displaystyle \omega }$, ${\displaystyle \Omega }$ and ${\displaystyle \Omega _{2}}$ using sums, products, exponentials, and the ${\displaystyle \psi _{1}}$ and ${\displaystyle \psi }$ function (to previously constructed ordinals less than ${\displaystyle \alpha }$).

i.e., allow the use of ${\displaystyle \psi _{1}}$ only for arguments less than ${\displaystyle \alpha }$ itself. With this definition, we must write ${\displaystyle \psi (\Omega _{2})}$ instead of ${\displaystyle \psi (\psi _{1}(\Omega _{2}))}$ (although it is still also equal to ${\displaystyle \psi (\psi _{1}(\Omega _{2}))=\psi (\zeta _{\Omega +1})}$, of course, but it is now constant until ${\displaystyle \Omega _{2}}$). This change is inessential because, intuitively speaking, the ${\displaystyle \psi _{1}}$ function collapses the nameable ordinals beyond ${\displaystyle \Omega _{2}}$ below the latter so it matters little whether ${\displaystyle \psi }$ is invoked directly on the ordinals beyond ${\displaystyle \Omega _{2}}$ or on their image by ${\displaystyle \psi _{1}}$. But it makes it possible to define ${\displaystyle \psi }$ and ${\displaystyle \psi _{1}}$ by simultaneous (rather than "downward") induction, and this is important if we are to use infinitely many collapsing functions.

Indeed, there is no reason to stop at two levels: using ${\displaystyle \omega +1}$ new cardinals in this way, ${\displaystyle \Omega _{1},\Omega _{2},\ldots ,\Omega _{\omega }}$, we get a system essentially equivalent to that introduced by Buchholz,^[3] the inessential difference being that since Buchholz uses ${\displaystyle \omega +1}$ ordinals from the start, he does not need to allow multiplication or exponentiation; also, Buchholz does not introduce the numbers ${\displaystyle 1}$ or ${\displaystyle \omega }$ in the system as they will also be produced by the ${\displaystyle \psi }$ functions: this makes the entire scheme much more elegant and more concise to define, albeit more difficult to understand. This system is also sensibly equivalent to the earlier (and much more difficult to grasp) "ordinal diagrams" of Takeuti^[5] and ${\displaystyle \theta }$ functions of Feferman: their range is the same (${\displaystyle \psi _{0}(\varepsilon _{\Omega _{\omega }+1})}$, which could be called the Takeuti-Feferman–Buchholz ordinal, and which describes the strength of ${\displaystyle \Pi _{1}^{1}}$-comprehension plus bar induction).

A "normal" variant

Most definitions of ordinal collapsing functions found in the recent literature differ from the ones we have given in one technical but important way which makes them technically more convenient although intuitively less transparent. We now explain this.

The following definition (by induction on ${\displaystyle \alpha }$) is completely equivalent to that of the function ${\displaystyle \psi }$ above:

Let ${\displaystyle C(\alpha ,\beta )}$ be the set of ordinals generated starting from ${\displaystyle 0}$, ${\displaystyle 1}$, ${\displaystyle \omega }$, ${\displaystyle \Omega }$ and all ordinals less than ${\displaystyle \beta }$ by recursively applying the following functions: ordinal addition, multiplication and exponentiation, and the function ${\displaystyle \psi \upharpoonright _{\alpha }}$. Then ${\displaystyle \psi (\alpha )}$ is defined as the smallest ordinal ${\displaystyle \rho }$ such that ${\displaystyle C(\alpha ,\rho )\cap \Omega =\rho }$.

(This is equivalent, because if ${\displaystyle \sigma }$ is the smallest ordinal not in ${\displaystyle C(\alpha ,0)}$, which is how we originally defined ${\displaystyle \psi (\alpha )}$, then it is also the smallest ordinal not in ${\displaystyle C(\alpha ,0)=C(\alpha ,\sigma )}$, and furthermore the properties we described of ${\displaystyle \psi }$ imply that no ordinal between ${\displaystyle \sigma }$ inclusive and ${\displaystyle \Omega }$ exclusive belongs to ${\displaystyle C(\alpha ,\sigma )}$.)

We can now make a change to the definition which makes it subtly different:

Let ${\displaystyle {\tilde {C}}(\alpha ,\beta )}$ be the set of ordinals generated starting from ${\displaystyle 0}$, ${\displaystyle 1}$, ${\displaystyle \omega }$, ${\displaystyle \Omega }$ and all ordinals less than ${\displaystyle \beta }$ by recursively applying the following functions: ordinal addition, multiplication and exponentiation, and the function ${\displaystyle {\tilde {\psi }}\upharpoonright _{\alpha }}$. Then ${\displaystyle {\tilde {\psi }}(\alpha )}$ is defined as the smallest ordinal ${\displaystyle \rho }$ such that ${\displaystyle {\tilde {C}}(\alpha ,\rho )\cap \Omega =\rho }$ and ${\displaystyle \alpha \in {\tilde {C}}(\alpha ,\rho )}$.

The first values of ${\displaystyle {\tilde {\psi }}}$ coincide with those of ${\displaystyle \psi }$: namely, for all ${\displaystyle \alpha <\zeta _{0}}$ where ${\displaystyle \zeta _{0}=\varphi _{2}(0)}$, we have ${\displaystyle {\tilde {\psi }}(\alpha )=\psi (\alpha )}$ because the additional clause ${\displaystyle \alpha \in {\tilde {C}}(\alpha ,\rho )}$ is always satisfied. But at this point the functions start to differ: while the function ${\displaystyle \psi }$ gets "stuck" at ${\displaystyle \zeta _{0}}$ for all ${\displaystyle \zeta _{0}\leq \alpha \leq \Omega }$, the function ${\displaystyle {\tilde {\psi }}}$ satisfies ${\displaystyle {\tilde {\psi }}(\zeta _{0})=\varepsilon _{\zeta _{0}+1}}$ because the new condition ${\displaystyle \alpha \in {\tilde {C}}(\alpha ,\rho )}$ imposes ${\displaystyle {\tilde {\psi }}(\zeta _{0})>\zeta _{0}}$. On the other hand, we still have ${\displaystyle {\tilde {\psi }}(\Omega )=\zeta _{0}}$ (because ${\displaystyle \Omega \in C(\alpha ,\rho )}$ for all ${\displaystyle \rho }$ so the extra condition does not come in play). Note in particular that ${\displaystyle {\tilde {\psi }}}$, unlike ${\displaystyle \psi }$, is not monotonic, nor is it continuous.

Despite these changes, the ${\displaystyle {\tilde {\psi }}}$ function also defines a system of ordinal notations up to the Bachmann–Howard ordinal: the notations, and the conditions for canonicity, are slightly different (for example, ${\displaystyle \psi (\Omega +1+\alpha )={\tilde {\psi }}({\tilde {\psi }}(\Omega )+\alpha )}$ for all ${\displaystyle \alpha }$ less than the common value ${\displaystyle \psi (\Omega 2)={\tilde {\psi }}(\Omega +1)}$).

Other similar OCFs

Arai's ψ

Arai's ψ function is an ordinal collapsing function introduced by Toshiyasu Arai (husband of Noriko H. Arai) in his paper: A simplified ordinal analysis of first-order reflection. ${\displaystyle \psi _{\Omega }(\alpha )}$ is a collapsing function such that ${\displaystyle \psi _{\Omega }(\alpha )<\Omega }$, where ${\displaystyle \Omega }$ represents the first uncountable ordinal (it can be replaced by the Church–Kleene ordinal at the cost of extra technical difficulty). Throughout the course of this article, ${\displaystyle {\mathsf {KP\Pi _{N}}}}$ represents Kripke–Platek set theory for a ${\displaystyle {\mathsf {\Pi _{N}}}}$-reflecting universe, ${\displaystyle \mathbb {K} _{N}}$ is the smallest ${\displaystyle {\mathsf {\Pi _{N}}}}$-reflecting ordinal, ${\displaystyle N}$ is a natural number ${\displaystyle >2}$, and ${\displaystyle \Omega _{0}=0}$.

Suppose ${\displaystyle {\mathsf {KP\Pi _{N}\vdash \theta }}}$ for a ${\displaystyle {\mathsf {\Sigma _{1}}}}$ (${\displaystyle \Omega }$)-sentence ${\displaystyle {\mathsf {\theta }}}$. Then, there exists a finite ${\displaystyle n}$ such that for ${\displaystyle \alpha =\psi _{\Omega }(\Omega _{n}(\mathbb {K} _{N}+1))}$, ${\displaystyle L_{\alpha }\models \theta }$. It can also be proven that ${\displaystyle {\mathsf {KP\Pi _{N}}}}$ proves that each initial segment ${\displaystyle \{\alpha \in OT:\alpha <\psi _{\Omega }(\Omega _{n}(\mathbb {K} _{N}+1))\};n=1,2,\ldots }$ is well-founded, and therefore, the proof-theoretic ordinal of ${\displaystyle \psi _{\Omega }(\varepsilon _{\mathbb {K} _{N}+1})}$ is the proof-theoretic ordinal of ${\displaystyle {\mathsf {KP\Pi _{N}}}}$. Using this, ${\displaystyle \psi _{\Omega }(\varepsilon _{\mathbb {K} _{N}+1})=\min(\{\alpha \leq \Omega \mid \forall \theta \in \Sigma _{1}({\mathsf {KP\Pi _{N}}}\vdash \theta ^{L_{\Omega }}\rightarrow L_{\alpha }\models \theta )\})}$. One can then make the following conversions:

• ${\displaystyle \psi _{\Omega }(A)=\psi _{0}(\Omega )= {\mathsf {PA}} =\varphi (1,0)}$, where ${\displaystyle A}$ is the least admissible ordinal, ${\displaystyle {\mathsf {PA}}}$ is Peano arithmetic and ${\displaystyle \varphi }$ is the Veblen hierarchy.
• ${\displaystyle \psi _{\Omega }(\varepsilon _{A+1})=\psi _{0}(\varepsilon _{\Omega +1})= {\mathsf {KP}} ={\mathsf {BHO}}}$, where ${\displaystyle A}$ is the least admissible ordinal, ${\displaystyle {\mathsf {KP}}}$ is Kripke–Platek set theory and ${\displaystyle {\mathsf {BHO}}}$ is the Bachmann–Howard ordinal.
• ${\displaystyle \psi _{\Omega }(I)=\psi _{0}(\Omega _{\omega })= {\mathsf {\Pi _{1}^{1}-CA_{0}}} ={\mathsf {BO}}}$, where ${\displaystyle I}$ is the least recursively inaccessible ordinal and ${\displaystyle {\mathsf {BO}}}$ is Buchholz's ordinal.
• ${\displaystyle \psi _{\Omega }(\varepsilon _{I+1})=\psi _{0}(\varepsilon _{\Omega _{\omega }+1})= {\mathsf {KPI}} ={\mathsf {TFBO}}}$, where ${\displaystyle I}$ is the least recursively inaccessible ordinal, ${\displaystyle {\mathsf {KPI}}}$ is Kripke–Platek set theory with a recursively inaccessible universe and ${\displaystyle {\mathsf {TFBO}}}$ is the Takeuti–Feferman–Buchholz ordinal.

Bachmann's ψ

The first true OCF, Bachmann's ${\displaystyle \psi }$ was invented by Heinz Bachmann, somewhat cumbersome as it depends on fundamental sequences for all limit ordinals; and the original definition is complicated. Michael Rathjen has suggested a "recast" of the system, which goes like so:

• Let ${\displaystyle \Omega }$ represent an uncountable ordinal such as ${\displaystyle \omega _{1}}$;
• Then define ${\displaystyle C^{\Omega }(\alpha ,\beta )}$ as the closure of ${\displaystyle \beta \cup \{0,\Omega \}}$ under addition, ${\displaystyle (\xi \rightarrow \omega ^{\xi })}$ and ${\displaystyle (\xi \rightarrow \psi _{\Omega }(\xi ))}$ for ${\displaystyle \xi <\alpha }$.
• ${\displaystyle \psi _{\Omega }(\alpha )}$ is the smallest countable ordinal ρ such that ${\displaystyle C^{\Omega }(\alpha ,\rho )\cap =\rho }$

${\displaystyle \psi _{\Omega }(\varepsilon _{\Omega +1})}$ is the Bachmann–Howard ordinal, the proof-theoretic ordinal of Kripke–Platek set theory with the axiom of infinity (KP).

Buchholz's ψ

Buchholz's ${\displaystyle \psi }$ is a hierarchy of single-argument functions ${\displaystyle \psi _{\nu }:{\mathsf {On}}\rightarrow {\mathsf {On}}}$, with ${\displaystyle \psi _{\nu }(\alpha )}$ occasionally abbreviated as ${\displaystyle \psi _{\nu }\alpha }$. This function is likely the most well known out of all OCFs. The definition is so:

• Define ${\displaystyle \Omega _{0}=1}$ and ${\displaystyle \Omega _{\nu }=\aleph _{\nu }}$ for ${\displaystyle \nu >0}$.
• Let ${\displaystyle P(\alpha )}$ be the set of distinct terms in the Cantor normal form of ${\displaystyle \alpha }$ (with each term of the form ${\displaystyle \omega ^{\xi }}$ for ${\displaystyle \xi \in {\mathsf {On}}}$, see Cantor normal form theorem)
• ${\displaystyle C_{\nu }^{0}(\alpha )=\Omega _{\nu }}$
• ${\displaystyle C_{\nu }^{n+1}(\alpha )=C_{\nu }^{n}(\alpha )\cup \{\psi _{\nu }(\xi )\mid \xi \in \alpha \cap C_{\nu }^{n}(\alpha )\land \xi \in C_{u}(\xi )\land u\leq \omega \}}$
• ${\displaystyle C_{\nu }(\alpha )=\bigcup \limits _{n<\omega }C_{\nu }^{n}(\alpha )}$
• ${\displaystyle \psi _{\nu }(\alpha )=\min(\{\gamma \mid \gamma \notin C_{\nu }(\alpha )\})}$

The limit of this system is ${\displaystyle \psi _{0}(\varepsilon _{\Omega _{\omega }+1})}$, the Takeuti–Feferman–Buchholz ordinal.

Extended Buchholz's ψ

This OCF is a sophisticated extension of Buchholz's ${\displaystyle \psi }$ by mathematician Denis Maksudov. The limit of this system is much greater, equal to ${\displaystyle \psi _{0}(\Omega _{\Omega _{\Omega _{\cdots }}})}$ where ${\displaystyle \Omega _{\Omega _{\Omega _{...}}}}$ denotes the first omega fixed point, sometimes referred to as Extended Buchholz's ordinal. The function is defined as follows:

• Define ${\displaystyle \Omega _{0}=1}$ and ${\displaystyle \Omega _{\nu }=\aleph _{\nu }}$ for ${\displaystyle \nu >0}$.
• ${\displaystyle C_{\nu }^{0}(\alpha )=\{\beta \mid \beta <\Omega _{\nu }\}}$
• ${\displaystyle C_{\nu }^{n+1}(\alpha )=\{\beta +\gamma ,\psi _{\mu }(\eta )\mid \mu ,\beta ,\gamma ,\eta \in C_{\nu }^{n}(\alpha )\land \eta <\alpha \}}$
• ${\displaystyle C_{\nu }(\alpha )=\bigcup \limits _{n<\omega }C_{\nu }^{n}(\alpha )}$
• ${\displaystyle \psi _{\nu }(\alpha )=\min(\{\gamma \mid \gamma \notin C_{\nu }(\alpha )\})}$

Madore's ψ

This OCF was the same as the ψ function previously used throughout this article; it is a simpler, more efficient version of Buchholz's ψ function defined by David Madore. Its use in this article lead to widespread use of the function.

• ${\displaystyle C_{0}(\alpha )=\{0,1,\omega ,\Omega \}}$
• ${\displaystyle C_{n+1}(\alpha )=\{\gamma +\delta ,\gamma \delta ,\gamma ^{\delta },\psi (\eta )\mid \gamma ,\delta ,\eta \in C_{n}(\alpha );\eta <\alpha \}}$
• ${\displaystyle C(\alpha )=\bigcup \limits _{n<\omega }C_{n}(\alpha )}$
• ${\displaystyle \psi (\alpha )=\min(\{\beta \in \Omega \mid \beta \notin C(\alpha )\})}$

This function was used by Chris Bird, who also invented the next OCF.

Bird's θ

Chris Bird devised the following shorthand for the extended Veblen function ${\displaystyle \varphi }$:

• ${\displaystyle \theta (\Omega ^{n-1}a_{n-1}+\cdots +\Omega ^{2}a_{2}+\Omega a_{1}+a_{0},b)=\varphi (a_{n-1},\ldots ,a_{2},a_{1},a_{0},b)}$
• ${\displaystyle \theta (\alpha ,0)}$ is abbreviated ${\displaystyle \theta (\alpha )}$

This function is only defined for arguments less than ${\displaystyle \Omega ^{\omega }}$, and its outputs are limited by the small Veblen ordinal. ${\displaystyle \theta (1,2,\omega ,\Omega )}$

Jäger's ψ

Jäger's ψ is a hierarchy of single-argument ordinal functions ψ_κ indexed by uncountable regular cardinals κ smaller than the least weakly Mahlo cardinal M₀ introduced by German mathematician Gerhard Jäger in 1984. It was developed on the base of Buchholz's approach.

• If ${\displaystyle \kappa =I_{\alpha }(0)}$ for some α < κ, ${\displaystyle \kappa ^{-}=0}$.
• If ${\displaystyle \kappa =I_{\alpha }(\beta +1)}$ for some α, β < κ, ${\displaystyle \kappa ^{-}=I_{\alpha }(\beta )}$.
• ${\displaystyle C_{\kappa }^{0}(\alpha )=\{\kappa ^{-}\}\cup \kappa ^{-}}$
• For any finite n, ${\displaystyle C_{\kappa }^{n+1}(\alpha )\subset M_{0}}$ is the smallest set satisfying the following:
  • The sum of any finitely many ordinals in ${\displaystyle C_{\kappa }^{n}(\alpha )\subset M_{0}}$ belongs to ${\displaystyle C_{\kappa }^{n+1}(\alpha )\subset M_{0}}$.
  • For any ${\displaystyle \beta ,\gamma \in C_{\kappa }^{n}(\alpha )}$, ${\displaystyle \varphi _{\beta }(\gamma )\in C_{\kappa }^{n+1}(\alpha )}$.
  • For any ${\displaystyle \beta ,\gamma \in C_{\kappa }^{n}(\alpha )}$, ${\displaystyle I_{\beta }(\gamma )\in C_{\kappa }^{n+1}(\alpha )}$.
  • For any ordinal γ and uncountable regular cardinal ${\displaystyle \pi \in C_{\kappa }^{n}(\alpha )}$, ${\displaystyle \gamma <\pi <\kappa \Rightarrow \gamma \in C_{\kappa }^{n+1}(\alpha )}$.
  • For any ${\displaystyle \gamma \in \alpha \cap C_{\kappa }^{n}(\alpha )}$ and uncountable regular cardinal ${\displaystyle \pi \in C_{\kappa }^{n}(\alpha )}$, ${\displaystyle \gamma \in C_{\pi }(\gamma )\Rightarrow \psi _{\pi }(\gamma )\in C_{\kappa }^{n+1}(\alpha )}$.
• ${\displaystyle C_{\kappa }(\alpha )=\bigcup \limits _{n<\omega }C_{\kappa }^{n}(\alpha )}$
• ${\displaystyle \psi _{\kappa }(\alpha )=\min(\{\xi \in \kappa \mid \xi \notin C_{\kappa }(\alpha )\})}$

Simplified Jäger's ψ

This is a sophisticated simplification of Jäger's ψ created by Denis Maksudov. An ordinal is α-weakly inaccessible if it is uncountable, regular and it is a limit of γ-weakly inaccessible cardinals for γ < α. Let I(α, 0) be the first α-weakly inaccessible cardinal, I(α, β + 1) be the first α-weakly inaccessible cardinal after I(α, β) and I(α, β) = ${\displaystyle sup(\{I(\alpha ,\gamma )\mid \gamma <\beta \})}$ for limit β. Restrict ρ and π to uncountable regular ordinals of the form I(α, 0) or I(α, β + 1). Then,

• ${\displaystyle C_{0}(\alpha ,\beta )=\beta \cup \{0\}}$
• ${\displaystyle C_{n+1}(\alpha ,\beta )=\{\gamma +\delta \mid \gamma ,\delta \in C_{n}(\alpha ,\beta )\}\cup \{I(\gamma ,\delta )\mid \gamma ,\delta \in C_{n}(\alpha ,\beta )\}\cup \{\psi _{\pi }(\gamma )\mid \pi ,\gamma ,\in C_{n}(\alpha ,\beta )\land \gamma <\alpha \}}$
• ${\displaystyle C(\alpha ,\beta )=\bigcup \limits _{n<\omega }C_{n}(\alpha ,\beta )}$
• ${\displaystyle \psi _{\pi }(\alpha )=\min(\{\beta <\pi \mid C(\alpha ,\beta )\cap \pi \subseteq \beta \})}$

Rathjen's Ψ

Rathjen's Ψ function is based on the least weakly compact cardinal to create large countable ordinals. For a weakly compact cardinal K, the functions ${\displaystyle M^{\alpha }}$, ${\displaystyle C(\alpha ,\pi )}$, ${\displaystyle \Xi (\alpha )}$, and ${\displaystyle \Psi _{\pi }^{\xi }(\alpha )}$ are defined in mutual recursion in the following way:

• M⁰ = ${\displaystyle K\cap {\mathsf {Lim}}}$, where Lim denotes the class of limit ordinals.
• For α > 0, M^α is the set ${\displaystyle \{\pi <K\mid C(\alpha ,\pi )\cap K=\pi \land \forall \xi \in C(\alpha ,\pi )\cap \alpha ,M^{\xi }{\mathsf {}}}$ is stationary in ${\displaystyle \pi \land \alpha \in C(\alpha ,\pi )\}}$
• ${\displaystyle C(\alpha ,\beta )}$ is the closure of ${\displaystyle \beta \cup \{0,K\}}$ under addition, ${\displaystyle (\xi ,\eta )\rightarrow \varphi (\xi ,\eta )}$, ${\displaystyle \xi \rightarrow \Omega _{\xi }}$ given ξ < K, ${\displaystyle \xi \rightarrow \Xi (\xi )}$ given ξ < α, and ${\displaystyle (\xi ,\pi ,\delta )\rightarrow \Psi _{\pi }^{\xi }(\delta )}$ given ${\displaystyle \xi \leq \delta <\alpha }$.
• ${\displaystyle \Xi (\alpha )=\min(M^{\alpha }\cup \{K\})}$.
• For ${\displaystyle \xi \leq \alpha }$, ${\displaystyle \Psi _{\pi }^{\xi }(\alpha )=\min(\{\rho \in M^{\xi }\cap \pi :C(\alpha ,\rho )\cap \pi =\rho \land \pi \land \alpha \in C(\alpha ,\rho )\}\cup \{\pi \})}$.

Collapsing large cardinals

As noted in the introduction, the use and definition of ordinal collapsing functions is strongly connected with the theory of ordinal analysis, so the collapse of this or that large cardinal must be mentioned simultaneously with the theory for which it provides a proof-theoretic analysis.

• Gerhard Jäger and Wolfram Pohlers^[6] described the collapse of an inaccessible cardinal to describe the ordinal-theoretic strength of Kripke–Platek set theory augmented by the recursive inaccessibility of the class of ordinals (KPi), which is also proof-theoretically equivalent^[1] to ${\displaystyle \Delta _{2}^{1}}$-comprehension plus bar induction. Roughly speaking, this collapse can be obtained by adding the ${\displaystyle \alpha \mapsto \Omega _{\alpha }}$ function itself to the list of constructions to which the ${\displaystyle C(\cdot )}$ collapsing system applies.
• Michael Rathjen^[7] then described the collapse of a Mahlo cardinal to describe the ordinal-theoretic strength of Kripke–Platek set theory augmented by the recursive Mahloness of the class of ordinals (KPM).
• Rathjen^[8] later described the collapse of a weakly compact cardinal to describe the ordinal-theoretic strength of Kripke–Platek set theory augmented by certain reflection principles (concentrating on the case of ${\displaystyle \Pi _{3}}$-reflection). Very roughly speaking, this proceeds by introducing the first cardinal ${\displaystyle \Xi (\alpha )}$ which is ${\displaystyle \alpha }$-hyper-Mahlo and adding the ${\displaystyle \alpha \mapsto \Xi (\alpha )}$ function itself to the collapsing system.
• In a 2015 paper, Toshyasu Arai has created ordinal collapsing functions ${\displaystyle \psi _{\pi }^{\vec {\xi }}}$ for a vector of ordinals ${\displaystyle \xi }$, which collapse ${\displaystyle \Pi _{n}^{1}}$-indescribable cardinals for ${\displaystyle n>0}$. These are used to carry out ordinal analysis of Kripke–Platek set theory augmented by ${\displaystyle \Pi _{n+2}}$-reflection principles. ^[9]
• Rathjen has begun^[when?][10] the investigation of the collapse of yet larger cardinals, with the ultimate goal of achieving an ordinal analysis of ${\displaystyle \Pi _{2}^{1}}$-comprehension (which is proof-theoretically equivalent to the augmentation of Kripke–Platek by ${\displaystyle \Sigma _{1}}$-separation).

Notes

References

• Arai, Toshiyasu (September 2020). "A simplified ordinal analysis of first-order reflection". The Journal of Symbolic Logic. 85 (3): 1163–1185. arXiv:1907.07611. doi:10.1017/jsl.2020.23. S2CID 118940547.
• Takeuti, Gaisi (1967). "Consistency proofs of subsystems of classical analysis". Annals of Mathematics. 86 (2): 299–348. doi:10.2307/1970691. JSTOR 1970691.
• Jäger, Gerhard; Pohlers, Wolfram (1983). "Eine beweistheoretische Untersuchung von (${\displaystyle \Delta _{2}^{1}}$-CA)+(BI) und verwandter Systeme". Bayerische Akademie der Wissenschaften. Mathematisch-Naturwissenschaftliche Klasse Sitzungsberichte. 1982: 1–28.
• Buchholz, Wilfried (1986). "A New System of Proof-Theoretic Ordinal Functions". Annals of Pure and Applied Logic. 32: 195–207. doi:10.1016/0168-0072(86)90052-7.
• Rathjen, Michael (1991). "Proof-theoretic analysis of KPM". Archive for Mathematical Logic. 30 (5–6): 377–403. doi:10.1007/BF01621475. S2CID 9376863.
• Rathjen, Michael (1994). "Proof theory of reflection" (PDF). Annals of Pure and Applied Logic. 68 (2): 181–224. doi:10.1016/0168-0072(94)90074-4.
• Rathjen, Michael (1995). "Recent Advances in Ordinal Analysis: ${\displaystyle \Pi _{2}^{1}}$-CA and Related Systems". The Bulletin of Symbolic Logic. 1 (4): 468–485. doi:10.2307/421132. JSTOR 421132.
• Kahle, Reinhard (2002). "Mathematical proof theory in the light of ordinal analysis". Synthese. 133: 237–255. doi:10.1023/A:1020892011851. S2CID 45695465.
• Rathjen, Michael (2005). "An ordinal analysis of stability". Archive for Mathematical Logic. 44: 1–62. CiteSeerX 10.1.1.15.9786. doi:10.1007/s00153-004-0226-2. S2CID 2686302.
• Rathjen, Michael (August 2005). "Proof Theory: Part III, Kripke–Platek Set Theory" (PDF). Archived from the original (PDF) on 2007-06-12. Retrieved 2008-04-17.(slides of a talk given at Fischbachau)