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

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

Определение

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

${\begin{aligned}C_{\nu }^{0}(\alpha )={}&\Omega _{\nu },\\[6pt]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 \leq \omega \},\\[6pt]C_{\nu }(\alpha )={}&\bigcup _{n<\omega }C_{\nu }^{n}(\alpha ),\\\psi _{\nu }(\alpha )={}&\min\{\gamma \mid \gamma \not \in C_{\nu }(\alpha )\},\end{aligned}}$

где

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

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

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

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

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

Свойства

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

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

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

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

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

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

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

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

1. Если $\alpha =\psi _{\nu _{1}}(\beta _{1})+\psi _{\nu _{2}}(\beta _{2})+\cdots +\psi _{\nu _{k}}(\beta _{k})$, где $k\geq 2$, тогда $\operatorname {cof} (\alpha )=\operatorname {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)$, тогда $\operatorname {cof} (\alpha )=\omega$ и $\alpha [\eta ]=\psi _{\eta }(0)$,
3. Если $\alpha =\psi _{\nu +1}(0)$, тогда $\operatorname {cof} (\alpha )=\Omega _{\nu +1}$ и $\alpha [\eta ]=\Omega _{\nu +1}[\eta ]=\eta$,
4. Если $\alpha =\psi _{\nu }(\beta +1)$, тогда $\operatorname {cof} (\alpha )=\omega$ и $\alpha [\eta ]=\psi _{\nu }(\beta )\cdot \eta$ (отметим, что: $\psi _{\nu }(0)=\Omega _{\nu }$),
5. Если $\alpha =\psi _{\nu }(\beta )$ и $\operatorname {cof} (\beta )\in \{\omega \}\cup \{\Omega _{\mu +1}\mid \mu <\nu \}$, тогда $\operatorname {cof} (\alpha )=\operatorname {cof} (\beta )$ и $\alpha [\eta ]=\psi _{\nu }(\beta [\eta ])$,
6. Если $\alpha =\psi _{\nu }(\beta )$ и $\operatorname {cof} (\beta )\in \{\Omega _{\mu +1}\mid \mu \geq \nu \}$, тогда $\operatorname {cof} (\alpha )=\omega$ и $\alpha [\eta ]=\psi _{\nu }(\beta [\gamma [\eta ]])$, где $\left\{{\begin{array}{lcr}\gamma [0]=\Omega _{\mu }\\\gamma [\eta +1]=\psi _{\mu }(\beta [\gamma [\eta ]])\\\end{array}}\right.$.

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

Поскольку Бухгольц работает в cистеме Цермело — Френкеля, каждый ординал $\alpha$ равен множеству всех меньших ординалов, $\alpha =\{\beta \mid \beta <\alpha \}$. Условие $C_{\nu }^{0}(\alpha )=\Omega _{\nu }$ означает, что множество $C_{\nu }^{0}(\alpha )$ содержит все ординалы, меньшие чем $\Omega _{\nu }$ или другими словами $C_{\nu }^{0}(\alpha )=\{\beta \mid \beta <\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 \leq \omega \}$ означает, что множество $C_{\nu }^{n+1}(\alpha )$ содержит:

• все ординалы из предыдущего множества $C_{\nu }^{n}(\alpha )$,

• все ординалы, которые могут быть получены суммированием аддитивно главных ординалов из предыдущего множества $C_{\nu }^{n}(\alpha )$,

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

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

Тогда $\psi _{\nu }(\alpha )=\min\{\gamma \mid \gamma \not \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,\ldots ,\psi (1)=\omega ,\ldots ,\psi (2)=\omega ^{2},\ldots ,\psi (3)=\omega ^{3},\ldots \}$ и $\psi _{0}(\omega )=\omega ^{\omega }$.

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

Если $\alpha =\Omega +1$, тогда $C_{0}(\alpha )=\{0,1,\ldots ,\psi _{0}(\Omega )=\varepsilon _{0},\ldots ,\varepsilon _{0}+\varepsilon _{0},\ldots ,\psi _{1}(0)=\Omega ,\ldots \}$ и $\psi _{0}(\Omega +1)=\varepsilon _{0}\omega =\omega ^{\varepsilon _{0}+1}$.

$\psi _{0}(\Omega 2)=\varepsilon _{1}$ – второе число эпсилон,

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

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

$\psi _{0}(\Omega ^{\Omega })=\Gamma _{0}=\varphi (1,0,0)=\theta (\Omega ,0)$, где $\theta$ обозначает функцию Фефермана, а $\Gamma _{0}$ обозначает ординал Фефермана-Шютте

$\psi _{0}(\Omega ^{\Omega ^{2}})=\varphi (1,0,0,0)$ – ординал Аккермана,

$\psi _{0}(\Omega ^{\Omega ^{\omega }})$ – Малый ординал Веблена,

$\psi _{0}(\Omega ^{\Omega ^{\Omega }})$ – Большой ординал Веблена,

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

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

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

Если $\alpha =1$, тогда $C_{1}(\alpha )=\{0,\ldots ,\psi _{0}(0)=\omega ,\ldots ,\psi _{1}(0)=\Omega ,\ldots ,\Omega +\omega ,\ldots ,\Omega +\Omega ,\ldots \}$ и $\psi _{1}(1)=\Omega \omega =\omega ^{\Omega +1}$.

$\psi _{1}(2)=\Omega \omega ^{2}=\omega ^{\Omega +2},$

$\psi _{1}(\psi _{1}(0))=\psi _{1}(\Omega )=\Omega ^{2}=\omega ^{\Omega +\Omega },$

$\psi _{1}(\psi _{1}(\psi _{1}(0)))=\omega ^{\Omega +\omega ^{\Omega +\Omega }}=\omega ^{\Omega \cdot \Omega }=(\omega ^{\Omega })^{\Omega }=\Omega ^{\Omega },$

$\psi _{1}^{4}(0)=\Omega ^{\Omega ^{\Omega }},$

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

$\psi _{1}(\Omega _{2})=\psi _{1}^{\omega }(0)=\Omega \uparrow \uparrow \omega =\varepsilon _{\Omega +1}.$

Для случая $\psi (\psi _{2}(0))=\psi (\Omega _{2})$ множество $C_{0}(\Omega _{2})$ содержит функции $\psi _{0}$ со всеми аргументами, меньшими чем $\Omega _{2}$, то есть такими аргументами, как $0,\psi _{1}(0),\psi _{1}(\psi _{1}(0)),\psi _{1}^{3}(0),\ldots ,\psi _{1}^{\omega }(0)$

и тогда

$\psi _{0}(\Omega _{2})=\psi _{0}(\psi _{1}(\Omega _{2}))=\psi _{0}(\varepsilon _{\Omega +1}).$

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

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