Пси-функции Бухгольца являются иерархией ординальных коллапсирующих функций
, введенной немецким математиком Вилфридом Бухгольцем в 1986 году.[1] Эти функции являются упрощенной версией
-функций Фефермана[англ.], но тем не менее, имеют такую же силу. Позже этот подход был расширен немецкими математиками Г. Егером[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}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/c26e53d03e19229477f7c021345a0f64f1adcf3f)
где
– наименьший трансфинитный ординал ![{\displaystyle \Omega _{\nu }={\begin{cases}1{\text{, если }}\nu =0\\{\text{кардинальное число }}\aleph _{\nu }{\text{, если }}\nu >0\end{cases}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/cb8e980e7bce5c90ef719f6fd766046870e94e86)
– множество аддитивно главных чисел в форме
, таких что
и
и
, где
– класс всех ординалов.
Примечание: греческие буквы везде означают ординалы.
Пределом этой нотации является ординал Такеути-Фефермана-Бухгольца
.
Бухгольц показал следующие свойства этих функций:
в частности, ![{\displaystyle \psi _{0}(0)=1,}](https://wikimedia.org/api/rest_v1/media/math/render/svg/3e5e844f0a7de0a6152080c54b457ca478fc572d)
![{\displaystyle \psi _{\nu }(\alpha )\in P,}](https://wikimedia.org/api/rest_v1/media/math/render/svg/0e60cd39fec511973ddc7d03862d4a4c775fafac)
![{\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}},}](https://wikimedia.org/api/rest_v1/media/math/render/svg/069bbdf6132fcda9a0d96943b5ac5850d36f6d91)
![{\displaystyle \Omega _{\nu }\leq \psi _{\nu }(\alpha )<\Omega _{\nu +1}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/9e50940be2a45823690d5e1243cca9107ce2180a)
![{\displaystyle \psi _{0}(\alpha )=\omega ^{\alpha }{\text{ если }}\alpha <\varepsilon _{0},}](https://wikimedia.org/api/rest_v1/media/math/render/svg/eafbb26e04b3bf219d4f00ff578c183e6ab599ff)
![{\displaystyle \psi _{\nu }(\alpha )=\omega ^{\Omega _{\nu }+\alpha }{\text{ если }}\alpha <\varepsilon _{\Omega _{\nu }+1}{\text{ и }}\nu \neq 0,}](https://wikimedia.org/api/rest_v1/media/math/render/svg/f064d9fa57df1b4045a3735975d83a7bae9c1ad1)
![{\displaystyle \theta (\varepsilon _{\Omega _{\nu }+1},0)=\psi _{0}(\varepsilon _{\Omega _{\nu }+1}){\text{ для }}0<\nu \leq \omega .}](https://wikimedia.org/api/rest_v1/media/math/render/svg/3a7269011ab7ba72aaf34c7ee36cfcf4163c0fc9)
Фундаментальные последовательности и нормальная форма для функций Бухгольца
[править | править код] Нормальной формой для нуля является 0. Если
– ненулевой ординал, тогда нормальной формой для
является
, где
и
, где каждый ординал
также записан в нормальной форме.
Фундаментальная последовательность для предельного ординала
с кофинальностью
– это строго возрастающая трансфинитная последовательность
с длиной
и с пределом
, где
представляет собой
-й элемент этой последовательности, то есть
.
Для предельных ординалов
, записанных в нормальной форме, фундаментальные последовательности определяются следующим образом:
- Если
, где
, тогда
и
, - Если
, тогда
и
, - Если
, тогда
и
, - Если
, тогда
и
(отметим, что:
), - Если
и
, тогда
и
, - Если
и
, тогда
и
, где
.
Поскольку Бухгольц работает в cистеме Цермело — Френкеля, каждый ординал
равен множеству всех меньших ординалов,
. Условие
означает, что множество
содержит все ординалы, меньшие чем
или другими словами
.
Условие
означает, что множество
содержит:
- все ординалы из предыдущего множества
,
- все ординалы, которые могут быть получены суммированием аддитивно главных ординалов из предыдущего множества
,
- все ординалы, которые могут быть получены применением ординалов (меньших чем
) из предыдущего множества
, как аргументов функций
, где
.
Поэтому данное условие может быть переписано следующим образом:
![{\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 \}.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/d50bbe085fc4bff32c01cfe0cae14499944b3460)
Таким образом, объединение всех множеств
с
, то есть
, является множеством всех ординалов, которые могут быть образованы из ординалов
функциями + (сложение) и
, где
и
.
Тогда
является наименьшим ординалом, который не принадлежит этому множеству.
Примеры
Рассмотрим следующие примеры:
![{\displaystyle C_{0}^{0}(\alpha )=\{0\}=\{\beta \mid \beta <1\},}](https://wikimedia.org/api/rest_v1/media/math/render/svg/9b9e8bd7eb7ffabd70195e97740c81cd01046c53)
(поскольку нет значений функций
для
, а 0 + 0 = 0).
Тогда
.
содержит
и все возможные суммы натуральных чисел. Следовательно,
– первый трансфинитный ординал, который больше всех натуральных чисел по определению.
содержит
и все их возможные суммы. Следовательно,
.
Если
, тогда
и
.
Если
, тогда
и
– наименьшее число эпсилон, то есть первая неподвижная точка
.
Если
, тогда
и
.
– второе число эпсилон,
, то есть первая неподвижная точка
,
, где
обозначает функцию Веблена,
, где
обозначает функцию Фефермана[англ.], а
обозначает ординал Фефермана-Шютте[англ.]
– ординал Аккермана[англ.],
– Малый ординал Веблена[англ.],
– Большой ординал Веблена[англ.],
![{\displaystyle \psi _{0}(\Omega \uparrow \uparrow \omega )=\psi _{0}(\varepsilon _{\Omega +1})=\theta (\varepsilon _{\Omega +1},0).}](https://wikimedia.org/api/rest_v1/media/math/render/svg/789a887f55d6e549cb24ce60051c1ad6a6f446a0)
Теперь рассмотрим, как работает функция
:
, то есть содержит все счетные ординалы. Следовательно,
содержит все возможные суммы всех счетных ординалов и
является первым несчетным ординалом, который больше всех счетных ординалов по определению, то есть наименьшим ординалом с кардинальностью
.
Если
, тогда
и
.
![{\displaystyle \psi _{1}(2)=\Omega \omega ^{2}=\omega ^{\Omega +2},}](https://wikimedia.org/api/rest_v1/media/math/render/svg/08e9a3705bbb49a5996e58631020cbd06a560ede)
![{\displaystyle \psi _{1}(\psi _{1}(0))=\psi _{1}(\Omega )=\Omega ^{2}=\omega ^{\Omega +\Omega },}](https://wikimedia.org/api/rest_v1/media/math/render/svg/56f79b980e8dae8ca77159601351596550352edf)
![{\displaystyle \psi _{1}(\psi _{1}(\psi _{1}(0)))=\omega ^{\Omega +\omega ^{\Omega +\Omega }}=\omega ^{\Omega \cdot \Omega }=(\omega ^{\Omega })^{\Omega }=\Omega ^{\Omega },}](https://wikimedia.org/api/rest_v1/media/math/render/svg/02773e7e0a59c93dd22a7e984557e0895b262369)
![{\displaystyle \psi _{1}^{4}(0)=\Omega ^{\Omega ^{\Omega }},}](https://wikimedia.org/api/rest_v1/media/math/render/svg/9ac509356fb8288eefcb4a81f1b60bc52a62dab5)
, где
– натуральное число,
,
![{\displaystyle \psi _{1}(\Omega _{2})=\psi _{1}^{\omega }(0)=\Omega \uparrow \uparrow \omega =\varepsilon _{\Omega +1}.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/b7a0ea944192c60de02c0e16c7cc40db7ac24612)
Для случая
множество
содержит функции
со всеми аргументами, меньшими чем
, то есть такими аргументами, как
и тогда
![{\displaystyle \psi _{0}(\Omega _{2})=\psi _{0}(\psi _{1}(\Omega _{2}))=\psi _{0}(\varepsilon _{\Omega +1}).}](https://wikimedia.org/api/rest_v1/media/math/render/svg/1f52d3d420da962ecf27aee689e516a18d62f8af)
В общем случае:
![{\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).}](https://wikimedia.org/api/rest_v1/media/math/render/svg/0aa0c893b3c5c1c25dc0745df110a2f357696695)
- ↑ Buchholz, W. A New System of Proof-Theoretic Ordinal Functions (неопр.) // Annals of Pure and Applied Logic. — Т. 32. Архивировано 28 октября 2021 года.
- ↑ Jäger, G.
-inaccessible ordinals, collapsing functions, and a recursive notation system (англ.) // Archiv f. math. Logik und Grundlagenf. : journal. — 1984. — Vol. 24, no. 1. — P. 49—62. - ↑ Buchholz, W.; Schütte, K. Ein Ordinalzahlensystem ftir die beweistheoretische Abgrenzung der
-Separation und Bar-Induktion (нем.) // Sitzungsberichte der Bayerischen Akademie der Wissenschaften, Math.-Naturw. Klasse : magazin. — 1983.
![Перейти к шаблону «Большие числа»](//upload.wikimedia.org/wikipedia/commons/thumb/c/c9/Wikipedia_interwiki_section_gear_icon.svg/14px-Wikipedia_interwiki_section_gear_icon.svg.png) |
---|
Числа | |
---|
Функции | |
---|
Нотации | |
---|