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

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

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

${\displaystyle {\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}}}$

где

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

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

${\displaystyle P(\gamma )=\{\gamma _{1},\ldots ,\gamma _{k}\}}$ – множество аддитивно главных чисел в форме ${\displaystyle \omega ^{\xi }}$, таких что ${\displaystyle \gamma =\gamma _{1}+\cdots +\gamma _{k}}$ и ${\displaystyle \gamma _{1}\geq \cdots \geq \gamma _{k}}$ и ${\displaystyle \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 )\}}$, где ${\displaystyle On}$ – класс всех ординалов.

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

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

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

• ${\displaystyle \psi _{\nu }(0)=\Omega _{\nu },}$ в частности, ${\displaystyle \psi _{0}(0)=1,}$
• ${\displaystyle \psi _{\nu }(\alpha )\in P,}$
• ${\displaystyle \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}},}$
• ${\displaystyle \Omega _{\nu }\leq \psi _{\nu }(\alpha )<\Omega _{\nu +1}}$
• ${\displaystyle \psi _{0}(\alpha )=\omega ^{\alpha }{\text{ если }}\alpha <\varepsilon _{0},}$
• ${\displaystyle \psi _{\nu }(\alpha )=\omega ^{\Omega _{\nu }+\alpha }{\text{ если }}\alpha <\varepsilon _{\Omega _{\nu }+1}{\text{ и }}\nu \neq 0,}$
• ${\displaystyle \theta (\varepsilon _{\Omega _{\nu }+1},0)=\psi _{0}(\varepsilon _{\Omega _{\nu }+1}){\text{ для }}0<\nu \leq \omega .}$

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

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

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

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

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

Условие ${\displaystyle 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 \}}$ означает, что множество ${\displaystyle C_{\nu }^{n+1}(\alpha )}$ содержит:

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

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

${\displaystyle 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 \}.}$

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

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

Примеры

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

${\displaystyle 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 \}}$, то есть содержит все счетные ординалы. Следовательно, ${\displaystyle C_{1}(0)}$ содержит все возможные суммы всех счетных ординалов и ${\displaystyle \psi _{1}(0)=\Omega _{1}}$ является первым несчетным ординалом, который больше всех счетных ординалов по определению, то есть наименьшим ординалом с кардинальностью ${\displaystyle \aleph _{1}}$.

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

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

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

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

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

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

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

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

и тогда

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

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

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