Пси-функции Бухгольца

Пси-функции Бухгольца являются иерархией ординальных коллапсирующих функций ${\psi }_{\nu }(\alpha )$, введенной немецким математиком Вилфридом Бухгольцем в 1986 году. Эти функции являются упрощенной версией $\theta$-Шаблон:Iw, но тем не менее, имеют такую же силу. Позже этот подход был расширен немецкими математиками Г. Егером и К. Шютте.

Определение

Бухгольц определил свои функции следующим образом:

$\begin{array}{cc}{C}_{\nu }^0(\alpha )=& {\mathrm{\Omega }}_{\nu },\\ C_{\nu }^{n+1}(\alpha )=& C_{\nu }^n(\alpha )\cup \{\gamma \mid P(\gamma )\subseteq C_{\nu }^n(\alpha )\}\\ & \cup \{{\psi }_{\mu }(\xi )\mid \xi \in \alpha \cap C_{\nu }^n(\alpha )\wedge \xi \in C_{\mu }(\xi )\wedge \mu \le \omega \},\\ C_{\nu }(\alpha )=& \bigcup _{n<\omega }{C}_{\nu }^n(\alpha ),\\ {\psi }_{\nu }(\alpha )=& \min \{\gamma \mid \gamma \in ̸C_{\nu }(\alpha )\},\end{array}$

где

$\omega$ – наименьший трансфинитный ординал

${\mathrm{\Omega }}_{\nu }=\{\begin{array}{c}1\text{, если }\nu =0\\ \text{кардинальное число }{\mathrm{\aleph }}_{\nu }\text{, если }\nu >0\end{array}$

$P(\gamma )=\{{\gamma }_1,\dots ,{\gamma }_k\}$ – множество аддитивно главных чисел в форме ${\omega }^{\xi }$, таких что $\gamma ={\gamma }_1+\cdots +{\gamma }_k$ и ${\gamma }_1\ge \cdots \ge {\gamma }_k$ и ${\gamma }_1,\dots ,{\gamma }_k\in P=\{{\omega }^{\xi }|\xi \in \mathrm{On}\}=\{\alpha \in \mathrm{On}|0<\alpha \wedge \mathrm{\forall }\xi ,\eta <\alpha (\xi +\eta <\alpha )\}$, где $On$ – класс всех ординалов.

Примечание: греческие буквы везде означают ординалы.

Пределом этой нотации является ординал Такеути-Фефермана-Бухгольца ${\psi }_0({\epsilon }_{{\mathrm{\Omega }}_{\omega }+1})$.

Свойства

Бухгольц показал следующие свойства этих функций:

• ${\psi }_{\nu }(0)={\mathrm{\Omega }}_{\nu },$ в частности, ${\psi }_0(0)=1,$
• ${\psi }_{\nu }(\alpha )\in P,$
• ${\psi }_{\nu }(\alpha +1)=\{\begin{array}{c}\min \{\gamma \in P:{\psi }_{\nu }(\alpha )<\gamma \}\text{ если }\alpha \in C_{\nu }(\alpha )\\ {\psi }_{\nu }(\alpha )\text{ если }\alpha \notin C_{\nu }(\alpha )\end{array},$
• ${\mathrm{\Omega }}_{\nu }\le {\psi }_{\nu }(\alpha )<{\mathrm{\Omega }}_{\nu +1}$
• ${\psi }_0(\alpha )={\omega }^{\alpha }\text{ если }\alpha <{\epsilon }_0,$
• ${\psi }_{\nu }(\alpha )={\omega }^{{\mathrm{\Omega }}_{\nu }+\alpha }\text{ если }\alpha <{\epsilon }_{{\mathrm{\Omega }}_{\nu }+1}\text{ и }\nu \ne 0,$
• $\theta ({\epsilon }_{{\mathrm{\Omega }}_{\nu }+1},0)={\psi }_0({\epsilon }_{{\mathrm{\Omega }}_{\nu }+1})\text{ для }0<\nu \le \omega .$

Фундаментальные последовательности и нормальная форма для функций Бухгольца

Нормальная форма

Нормальной формой для нуля является 0. Если $\alpha$ – ненулевой ординал, тогда нормальной формой для $\alpha$ является $\alpha ={\psi }_{{\nu }_1}({\beta }_1)+{\psi }_{{\nu }_2}({\beta }_2)+\cdots +{\psi }_{{\nu }_k}({\beta }_k)$, где ${\nu }_i\le \omega ,k\in {\mathbb{N}}_{>0},{\beta }_i\in C_{{\nu }_i}({\beta }_i)$ и ${\psi }_{{\nu }_1}({\beta }_1)\ge {\psi }_{{\nu }_2}({\beta }_2)\ge \cdots \ge {\psi }_{{\nu }_k}({\beta }_k)$, где каждый ординал ${\beta }_i$ также записан в нормальной форме.

Фундаментальные последовательности

Фундаментальная последовательность для предельного ординала $\alpha$ с кофинальностью $\mathrm{cof}(\alpha )=\beta$ – это строго возрастающая трансфинитная последовательность $(\alpha [\eta ]{)}_{\eta <\beta }$ с длиной $\beta$ и с пределом $\alpha$, где $\alpha [\eta ]$ представляет собой $\eta$-й элемент этой последовательности, то есть $\alpha =\sup \{\alpha [\eta ]|\eta <\mathrm{cof}(\alpha )\}$.

Для предельных ординалов $\alpha$, записанных в нормальной форме, фундаментальные последовательности определяются следующим образом:

1. Если $\alpha ={\psi }_{{\nu }_1}({\beta }_1)+{\psi }_{{\nu }_2}({\beta }_2)+\cdots +{\psi }_{{\nu }_k}({\beta }_k)$, где $k\ge 2$, тогда $\mathrm{cof}(\alpha )=\mathrm{cof}({\psi }_{{\nu }_k}({\beta }_k))$ и $\alpha [\eta ]={\psi }_{{\nu }_1}({\beta }_1)+\cdots +{\psi }_{{\nu }_{k-1}}({\beta }_{k-1})+({\psi }_{{\nu }_k}({\beta }_k)[\eta ])$,
2. Если $\alpha ={\psi }_{\omega }(0)$, тогда $\mathrm{cof}(\alpha )=\omega$ и $\alpha [\eta ]={\psi }_{\eta }(0)$,
3. Если $\alpha ={\psi }_{\nu +1}(0)$, тогда $\mathrm{cof}(\alpha )={\mathrm{\Omega }}_{\nu +1}$ и $\alpha [\eta ]={\mathrm{\Omega }}_{\nu +1}[\eta ]=\eta$,
4. Если $\alpha ={\psi }_{\nu }(\beta +1)$, тогда $\mathrm{cof}(\alpha )=\omega$ и $\alpha [\eta ]={\psi }_{\nu }(\beta )\cdot \eta$ (отметим, что: ${\psi }_{\nu }(0)={\mathrm{\Omega }}_{\nu }$),
5. Если $\alpha ={\psi }_{\nu }(\beta )$ и $\mathrm{cof}(\beta )\in \{\omega \}\cup \{{\mathrm{\Omega }}_{\mu +1}\mid \mu <\nu \}$, тогда $\mathrm{cof}(\alpha )=\mathrm{cof}(\beta )$ и $\alpha [\eta ]={\psi }_{\nu }(\beta [\eta ])$,
6. Если $\alpha ={\psi }_{\nu }(\beta )$ и $\mathrm{cof}(\beta )\in \{{\mathrm{\Omega }}_{\mu +1}\mid \mu \ge \nu \}$, тогда $\mathrm{cof}(\alpha )=\omega$ и $\alpha [\eta ]={\psi }_{\nu }(\beta [\gamma [\eta ]])$, где $\{\begin{array}{c}\gamma [0]={\mathrm{\Omega }}_{\mu }\\ \gamma [\eta +1]={\psi }_{\mu }(\beta [\gamma [\eta ]])\end{array}$.

Объяснение принципов нотации

Поскольку Бухгольц работает в cистеме Цермело — Френкеля, каждый ординал $\alpha$ равен множеству всех меньших ординалов, $\alpha =\{\beta \mid \beta <\alpha \}$. Условие $C_{\nu }^0(\alpha )={\mathrm{\Omega }}_{\nu }$ означает, что множество $C_{\nu }^0(\alpha )$ содержит все ординалы, меньшие чем ${\mathrm{\Omega }}_{\nu }$ или другими словами $C_{\nu }^0(\alpha )=\{\beta \mid \beta <{\mathrm{\Omega }}_{\nu }\}$.

Условие $C_{\nu }^{n+1}(\alpha )=C_{\nu }^n(\alpha )\cup \{\gamma \mid P(\gamma )\subseteq C_{\nu }^n(\alpha )\}\cup \{{\psi }_{\mu }(\xi )\mid \xi \in \alpha \cap C_{\nu }^n(\alpha )\wedge \mu \le \omega \}$ означает, что множество $C_{\nu }^{n+1}(\alpha )$ содержит:

• все ординалы из предыдущего множества $C_{\nu }^n(\alpha )$,
• все ординалы, которые могут быть получены суммированием аддитивно главных ординалов из предыдущего множества $C_{\nu }^n(\alpha )$,
• все ординалы, которые могут быть получены применением ординалов (меньших чем $\alpha$) из предыдущего множества $C_{\nu }^n(\alpha )$, как аргументов функций ${\psi }_{\mu }$, где $\mu \le \omega$.

Поэтому данное условие может быть переписано следующим образом:

$C_{\nu }^{n+1}(\alpha )=\{\beta +\gamma ,{\psi }_{\mu }(\eta )\mid \beta ,\gamma ,\eta \in C_{\nu }^n(\alpha )\wedge \eta <\alpha \wedge \mu \le \omega \}.$

Таким образом, объединение всех множеств $C_{\nu }^n(\alpha )$ с $n<\omega$, то есть $C_{\nu }(\alpha )=\bigcup _{n<\omega }{C}_{\nu }^n(\alpha )$, является множеством всех ординалов, которые могут быть образованы из ординалов $<{\mathrm{\aleph }}_{\nu }$ функциями + (сложение) и ${\psi }_{\mu }(\eta )$, где $\mu \le \omega$ и $\eta <\alpha$.

Тогда ${\psi }_{\nu }(\alpha )=\min \{\gamma \mid \gamma \in ̸C_{\nu }(\alpha )\}$ является наименьшим ординалом, который не принадлежит этому множеству.

Примеры

Рассмотрим следующие примеры:

$C_0^0(\alpha )=\{0\}=\{\beta \mid \beta <1\},$

$C_0(0)=\{0\}$ (поскольку нет значений функций ${\psi }_{\nu }$ для $\eta <0$, а 0 + 0 = 0).

Тогда ${\psi }_0(0)=1$.

$C_0(1)$ содержит ${\psi }_0(0)=1$ и все возможные суммы натуральных чисел. Следовательно, ${\psi }_0(1)=\omega$ – первый трансфинитный ординал, который больше всех натуральных чисел по определению.

$C_0(2)$ содержит ${\psi }_0(0)=1,{\psi }_0(1)=\omega$ и все их возможные суммы. Следовательно, ${\psi }_0(2)={\omega }^2$.

Если $\alpha =\omega$, тогда $C_0(\alpha )=\{0,\psi (0)=1,\dots ,\psi (1)=\omega ,\dots ,\psi (2)={\omega }^2,\dots ,\psi (3)={\omega }^3,\dots \}$ и ${\psi }_0(\omega )={\omega }^{\omega }$.

Если $\alpha =\mathrm{\Omega }$, тогда $C_0(\alpha )=\{0,\psi (0)=1,\dots ,\psi (1)=\omega ,\dots ,\psi (\omega )={\omega }^{\omega },\dots ,\psi ({\omega }^{\omega })={\omega }^{{\omega }^{\omega }},\dots \}$ и ${\psi }_0(\mathrm{\Omega })={\epsilon }_0$ – наименьшее число эпсилон, то есть первая неподвижная точка $\alpha ={\omega }^{\alpha }$.

Если $\alpha =\mathrm{\Omega }+1$, тогда $C_0(\alpha )=\{0,1,\dots ,{\psi }_0(\mathrm{\Omega })={\epsilon }_0,\dots ,{\epsilon }_0+{\epsilon }_0,\dots ,{\psi }_1(0)=\mathrm{\Omega },\dots \}$ и ${\psi }_0(\mathrm{\Omega }+1)={\epsilon }_0\omega ={\omega }^{{\epsilon }_0+1}$.

${\psi }_0(\mathrm{\Omega }2)={\epsilon }_1$ – второе число эпсилон,

${\psi }_0({\mathrm{\Omega }}^2)={\epsilon }_{{\epsilon }_{\cdots }}={\zeta }_0$, то есть первая неподвижная точка $\alpha ={\epsilon }_{\alpha }$,

$\phi (\alpha ,1+\beta )={\psi }_0({\mathrm{\Omega }}^{\alpha }\beta )$, где $\phi$ обозначает функцию Веблена,

${\psi }_0({\mathrm{\Omega }}^{\mathrm{\Omega }})={\mathrm{\Gamma }}_0=\phi (1,0,0)=\theta (\mathrm{\Omega },0)$, где $\theta$ обозначает Шаблон:Iw, а ${\mathrm{\Gamma }}_0$ обозначает Шаблон:Iw

${\psi }_0({\mathrm{\Omega }}^{{\mathrm{\Omega }}^2})=\phi (1,0,0,0)$ – Шаблон:Iw,

${\psi }_0({\mathrm{\Omega }}^{{\mathrm{\Omega }}^{\omega }})$ – Шаблон:Iw,

${\psi }_0({\mathrm{\Omega }}^{{\mathrm{\Omega }}^{\mathrm{\Omega }}})$ – Шаблон:Iw,

${\psi }_0(\mathrm{\Omega }\uparrow \uparrow \omega )={\psi }_0({\epsilon }_{\mathrm{\Omega }+1})=\theta ({\epsilon }_{\mathrm{\Omega }+1},0).$

Теперь рассмотрим, как работает функция ${\psi }_1$:

$C_1^0(0)=\{\beta \mid \beta <{\mathrm{\Omega }}_1\}=\{0,\psi (0)=1,2,\dots ,10^{100},\dots ,{\psi }_0(1)=\omega ,\dots ,{\psi }_0(\mathrm{\Omega })={\epsilon }_0,\dots ,{\psi }_0({\mathrm{\Omega }}^{\mathrm{\Omega }})={\mathrm{\Gamma }}_0,\dots ,\psi ({\mathrm{\Omega }}^{{\mathrm{\Omega }}^{\mathrm{\Omega }}+{\mathrm{\Omega }}^2}),\dots \}$, то есть содержит все счетные ординалы. Следовательно, $C_1(0)$ содержит все возможные суммы всех счетных ординалов и ${\psi }_1(0)={\mathrm{\Omega }}_1$ является первым несчетным ординалом, который больше всех счетных ординалов по определению, то есть наименьшим ординалом с кардинальностью ${\mathrm{\aleph }}_1$.

Если $\alpha =1$, тогда $C_1(\alpha )=\{0,\dots ,{\psi }_0(0)=\omega ,\dots ,{\psi }_1(0)=\mathrm{\Omega },\dots ,\mathrm{\Omega }+\omega ,\dots ,\mathrm{\Omega }+\mathrm{\Omega },\dots \}$ и ${\psi }_1(1)=\mathrm{\Omega }\omega ={\omega }^{\mathrm{\Omega }+1}$.

${\psi }_1(2)=\mathrm{\Omega }{\omega }^2={\omega }^{\mathrm{\Omega }+2},$

${\psi }_1({\psi }_1(0))={\psi }_1(\mathrm{\Omega })={\mathrm{\Omega }}^2={\omega }^{\mathrm{\Omega }+\mathrm{\Omega }},$

${\psi }_1({\psi }_1({\psi }_1(0)))={\omega }^{\mathrm{\Omega }+{\omega }^{\mathrm{\Omega }+\mathrm{\Omega }}}={\omega }^{\mathrm{\Omega }\cdot \mathrm{\Omega }}=({\omega }^{\mathrm{\Omega }}{)}^{\mathrm{\Omega }}={\mathrm{\Omega }}^{\mathrm{\Omega }},$

${\psi }_1^4(0)={\mathrm{\Omega }}^{{\mathrm{\Omega }}^{\mathrm{\Omega }}},$

${\psi }_1^{k+1}(0)=\mathrm{\Omega }\uparrow \uparrow k$, где $k$ – натуральное число, $k\ge 2$,

${\psi }_1({\mathrm{\Omega }}_2)={\psi }_1^{\omega }(0)=\mathrm{\Omega }\uparrow \uparrow \omega ={\epsilon }_{\mathrm{\Omega }+1}.$

Для случая $\psi ({\psi }_2(0))=\psi ({\mathrm{\Omega }}_2)$ множество $C_0({\mathrm{\Omega }}_2)$ содержит функции ${\psi }_0$ со всеми аргументами, меньшими чем ${\mathrm{\Omega }}_2$, то есть такими аргументами, как $0,{\psi }_1(0),{\psi }_1({\psi }_1(0)),{\psi }_1^3(0),\dots ,{\psi }_1^{\omega }(0)$

и тогда

${\psi }_0({\mathrm{\Omega }}_2)={\psi }_0({\psi }_1({\mathrm{\Omega }}_2))={\psi }_0({\epsilon }_{\mathrm{\Omega }+1}).$

В общем случае:

${\psi }_0({\mathrm{\Omega }}_{\nu +1})={\psi }_0({\psi }_{\nu }({\mathrm{\Omega }}_{\nu +1}))={\psi }_0({\epsilon }_{{\mathrm{\Omega }}_{\nu }+1})=\theta ({\epsilon }_{{\mathrm{\Omega }}_{\nu }+1},0).$