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

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

Определение

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

[math]\displaystyle{ \begin{align} 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 \lt \omega} C_\nu^n (\alpha), \\ \psi_\nu(\alpha) = {} & \min\{\gamma \mid \gamma \not\in C_\nu(\alpha)\}, \end{align} }[/math]

где

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

[math]\displaystyle{ \Omega_\nu = \begin{cases} 1\text{, если } \nu=0 \\ \text{кардинальное число }\aleph_\nu\text{, если } \nu\gt 0 \end{cases} }[/math]

[math]\displaystyle{ P(\gamma)=\{\gamma_1,\ldots,\gamma_k\} }[/math] – множество аддитивно главных чисел в форме [math]\displaystyle{ \omega^\xi }[/math], таких что [math]\displaystyle{ \gamma=\gamma_1+\cdots+\gamma_k }[/math] и [math]\displaystyle{ \gamma_1\geq\cdots\geq\gamma_k }[/math] и [math]\displaystyle{ \gamma_1,\ldots,\gamma_k \in P=\{\omega^\xi| \xi \in \operatorname{On} \}=\{\alpha\in \operatorname{On} | 0\lt \alpha \wedge \forall \xi, \eta \lt \alpha (\xi+\eta \lt \alpha)\} }[/math], где [math]\displaystyle{ On }[/math] – класс всех ординалов.

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

Пределом этой нотации является ординал Такеути-Фефермана-Бухгольца [math]\displaystyle{ \psi_0(\varepsilon_{\Omega_{\omega}+1}) }[/math].

Свойства

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

[math]\displaystyle{ \psi_\nu(0)=\Omega_\nu, }[/math] в частности, [math]\displaystyle{ \psi_0(0)=1, }[/math]
[math]\displaystyle{ \psi_\nu(\alpha)\in P, }[/math]
[math]\displaystyle{ \psi_\nu(\alpha+1) = \begin{cases}\min\{\gamma\in P: \psi_\nu(\alpha)\lt \gamma\} \text{ если }\alpha\in C_\nu(\alpha)\\ \psi_\nu(\alpha)\text{ если }\alpha\notin C_\nu(\alpha)\end{cases}, }[/math]
[math]\displaystyle{ \Omega_\nu\le\psi_\nu(\alpha)\lt \Omega_{\nu+1} }[/math]
[math]\displaystyle{ \psi_0(\alpha)=\omega^\alpha \text{ если }\alpha\lt \varepsilon_0, }[/math]
[math]\displaystyle{ \psi_\nu(\alpha)=\omega^{\Omega_\nu+\alpha} \text{ если } \alpha\lt \varepsilon_{\Omega_\nu+1} \text{ и } \nu\neq 0, }[/math]
[math]\displaystyle{ \theta(\varepsilon_{\Omega_\nu+1},0)=\psi_0(\varepsilon_{\Omega_\nu+1}) \text{ для } 0\lt \nu\le\omega. }[/math]

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

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

Нормальной формой для нуля является 0. Если [math]\displaystyle{ \alpha }[/math] – ненулевой ординал, тогда нормальной формой для [math]\displaystyle{ \alpha }[/math] является [math]\displaystyle{ \alpha=\psi_{\nu_1}(\beta_1)+\psi_{\nu_2}(\beta_2)+\cdots+\psi_{\nu_k}(\beta_k) }[/math], где [math]\displaystyle{ \nu_i\le\omega, k\in\mathbb N_{\gt 0}, \beta_i\in C_{\nu_i}(\beta_i) }[/math] и [math]\displaystyle{ \psi_{\nu_1}(\beta_1)\geq\psi_{\nu_2}(\beta_2)\geq\cdots\geq\psi_{\nu_k}(\beta_k) }[/math], где каждый ординал [math]\displaystyle{ \beta_i }[/math] также записан в нормальной форме.

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

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

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

Если [math]\displaystyle{ \alpha=\psi_{\nu_1}(\beta_1)+\psi_{\nu_2}(\beta_2)+\cdots+\psi_{\nu_k}(\beta_k) }[/math], где [math]\displaystyle{ k\geq2 }[/math], тогда [math]\displaystyle{ \operatorname{cof}(\alpha)=\operatorname{cof}(\psi_{\nu_k}(\beta_k)) }[/math] и [math]\displaystyle{ \alpha[\eta]=\psi_{\nu_1}(\beta_1)+\cdots+\psi_{\nu_{k-1}}(\beta_{k-1})+(\psi_{\nu_k}(\beta_k)[\eta]) }[/math],
Если [math]\displaystyle{ \alpha=\psi_{\omega}(0) }[/math], тогда [math]\displaystyle{ \operatorname{cof}(\alpha)=\omega }[/math] и [math]\displaystyle{ \alpha[\eta]=\psi_{\eta}(0) }[/math],
Если [math]\displaystyle{ \alpha=\psi_{\nu+1}(0) }[/math], тогда [math]\displaystyle{ \operatorname{cof}(\alpha)=\Omega_{\nu+1} }[/math] и [math]\displaystyle{ \alpha[\eta]=\Omega_{\nu+1}[\eta]=\eta }[/math],
Если [math]\displaystyle{ \alpha=\psi_{\nu}(\beta+1) }[/math], тогда [math]\displaystyle{ \operatorname{cof}(\alpha)=\omega }[/math] и [math]\displaystyle{ \alpha[\eta]=\psi_{\nu}(\beta)\cdot \eta }[/math] (отметим, что: [math]\displaystyle{ \psi_\nu(0)=\Omega_\nu }[/math]),
Если [math]\displaystyle{ \alpha=\psi_{\nu}(\beta) }[/math] и [math]\displaystyle{ \operatorname{cof}(\beta)\in\{\omega\}\cup\{\Omega_{\mu+1}\mid\mu\lt \nu\} }[/math], тогда [math]\displaystyle{ \operatorname{cof}(\alpha)=\operatorname{cof}(\beta) }[/math] и [math]\displaystyle{ \alpha[\eta]=\psi_{\nu}(\beta[\eta]) }[/math],
Если [math]\displaystyle{ \alpha=\psi_{\nu}(\beta) }[/math] и [math]\displaystyle{ \operatorname{cof}(\beta)\in\{\Omega_{\mu+1}\mid\mu\geq\nu\} }[/math], тогда [math]\displaystyle{ \operatorname{cof}(\alpha)=\omega }[/math] и [math]\displaystyle{ \alpha[\eta]=\psi_\nu(\beta[\gamma[\eta]]) }[/math], где [math]\displaystyle{ \left\{\begin{array}{lcr} \gamma[0]=\Omega_\mu \\ \gamma[\eta+1]=\psi_\mu(\beta[\gamma[\eta]])\\ \end{array}\right. }[/math].

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

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

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

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

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

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

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

[math]\displaystyle{ C_\nu^{n+1}(\alpha) = \{\beta+\gamma,\psi_\mu(\eta)\mid\beta, \gamma,\eta\in C_\nu^n(\alpha)\wedge\eta\lt \alpha \wedge \mu \leq \omega\}. }[/math]

Таким образом, объединение всех множеств [math]\displaystyle{ C_\nu^n (\alpha) }[/math] с [math]\displaystyle{ n\lt \omega }[/math], то есть [math]\displaystyle{ C_\nu(\alpha) = \bigcup_{n \lt \omega} C_\nu^n (\alpha) }[/math], является множеством всех ординалов, которые могут быть образованы из ординалов [math]\displaystyle{ \lt \aleph_\nu }[/math] функциями + (сложение) и [math]\displaystyle{ \psi_{\mu}(\eta) }[/math], где [math]\displaystyle{ \mu\le\omega }[/math] и [math]\displaystyle{ \eta\lt \alpha }[/math].

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

Примеры

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

[math]\displaystyle{ C_0^0(\alpha)=\{0\} =\{\beta\mid\beta\lt 1\}, }[/math]

[math]\displaystyle{ C_0(0)=\{0\} }[/math] (поскольку нет значений функций [math]\displaystyle{ \psi_\nu }[/math] для [math]\displaystyle{ \eta\lt 0 }[/math], а 0 + 0 = 0).

Тогда [math]\displaystyle{ \psi_0(0)=1 }[/math].

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

[math]\displaystyle{ C_0(2) }[/math] содержит [math]\displaystyle{ \psi_0(0)=1, \psi_0(1)=\omega }[/math] и все их возможные суммы. Следовательно, [math]\displaystyle{ \psi_0(2)=\omega^2 }[/math].

Если [math]\displaystyle{ \alpha=\omega }[/math], тогда [math]\displaystyle{ C_0(\alpha)=\{0,\psi(0)=1,\ldots,\psi(1)=\omega,\ldots,\psi(2)=\omega^2,\ldots,\psi(3)=\omega^3, \ldots\} }[/math] и [math]\displaystyle{ \psi_0(\omega)=\omega^\omega }[/math].

Если [math]\displaystyle{ \alpha=\Omega }[/math], тогда [math]\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\} }[/math] и [math]\displaystyle{ \psi_0(\Omega)=\varepsilon_0 }[/math] – наименьшее число эпсилон, то есть первая неподвижная точка [math]\displaystyle{ \alpha=\omega^\alpha }[/math].

Если [math]\displaystyle{ \alpha=\Omega+1 }[/math], тогда [math]\displaystyle{ C_0(\alpha)=\{0,1,\ldots,\psi_0(\Omega)=\varepsilon_0,\ldots,\varepsilon_0+\varepsilon_0,\ldots,\psi_1(0)=\Omega,\ldots\} }[/math] и [math]\displaystyle{ \psi_0(\Omega+1)=\varepsilon_0\omega=\omega^{\varepsilon_0+1} }[/math].

[math]\displaystyle{ \psi_0(\Omega2)=\varepsilon_1 }[/math] – второе число эпсилон,

[math]\displaystyle{ \psi_0(\Omega^2) = \varepsilon_{\varepsilon_\cdots}=\zeta_0 }[/math], то есть первая неподвижная точка [math]\displaystyle{ \alpha=\varepsilon_\alpha }[/math],

[math]\displaystyle{ \varphi(\alpha,1+\beta)=\psi_0(\Omega^\alpha\beta) }[/math], где [math]\displaystyle{ \varphi }[/math] обозначает функцию Веблена,

[math]\displaystyle{ \psi_0(\Omega^\Omega)=\Gamma_0=\varphi(1,0,0)=\theta(\Omega,0) }[/math], где [math]\displaystyle{ \theta }[/math] обозначает функцию Фефермана^[en], а [math]\displaystyle{ \Gamma_0 }[/math] обозначает ординал Фефермана-Шютте^[en]

[math]\displaystyle{ \psi_0(\Omega^{\Omega^2})=\varphi(1,0,0,0) }[/math] – ординал Аккермана^[en],

[math]\displaystyle{ \psi_0(\Omega^{\Omega^\omega}) }[/math] – Малый ординал Веблена^[en],

[math]\displaystyle{ \psi_0(\Omega^{\Omega^\Omega}) }[/math] – Большой ординал Веблена^[en],

[math]\displaystyle{ \psi_0(\Omega\uparrow\uparrow\omega) =\psi_0(\varepsilon_{\Omega+1}) = \theta(\varepsilon_{\Omega+1},0). }[/math]

Теперь рассмотрим, как работает функция [math]\displaystyle{ \psi_1 }[/math]:

[math]\displaystyle{ C_1^0(0)=\{\beta\mid\beta\lt \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\} }[/math], то есть содержит все счетные ординалы. Следовательно, [math]\displaystyle{ C_1(0) }[/math] содержит все возможные суммы всех счетных ординалов и [math]\displaystyle{ \psi_1(0)=\Omega_1 }[/math] является первым несчетным ординалом, который больше всех счетных ординалов по определению, то есть наименьшим ординалом с кардинальностью [math]\displaystyle{ \aleph_1 }[/math].

Если [math]\displaystyle{ \alpha=1 }[/math], тогда [math]\displaystyle{ C_1(\alpha)=\{0,\ldots,\psi_0(0) = \omega, \ldots, \psi_1(0) = \Omega,\ldots,\Omega+\omega,\ldots,\Omega+\Omega,\ldots\} }[/math] и [math]\displaystyle{ \psi_1(1)=\Omega\omega=\omega^{\Omega+1} }[/math].

[math]\displaystyle{ \psi_1(2)=\Omega\omega^2=\omega^{\Omega+2}, }[/math]

[math]\displaystyle{ \psi_1(\psi_1(0))=\psi_1(\Omega)=\Omega^2=\omega^{\Omega+\Omega}, }[/math]

[math]\displaystyle{ \psi_1(\psi_1(\psi_1(0))) =\omega^{\Omega+\omega^{\Omega+\Omega}} = \omega^{\Omega\cdot\Omega} = (\omega^{\Omega})^\Omega=\Omega^\Omega, }[/math]

[math]\displaystyle{ \psi_1^4(0)=\Omega^{\Omega^\Omega}, }[/math]

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

[math]\displaystyle{ \psi_1(\Omega_2) = \psi_1^\omega(0) = \Omega \uparrow\uparrow \omega = \varepsilon_{\Omega+1}. }[/math]

Для случая [math]\displaystyle{ \psi(\psi_2(0))=\psi(\Omega_2) }[/math] множество [math]\displaystyle{ C_0(\Omega_2) }[/math] содержит функции [math]\displaystyle{ \psi_0 }[/math] со всеми аргументами, меньшими чем [math]\displaystyle{ \Omega_2 }[/math], то есть такими аргументами, как [math]\displaystyle{ 0, \psi_1(0), \psi_1(\psi_1(0)), \psi_1^3(0),\ldots, \psi_1^\omega(0) }[/math]

и тогда

[math]\displaystyle{ \psi_0(\Omega_2) = \psi_0(\psi_1(\Omega_2)) = \psi_0(\varepsilon_{\Omega+1}). }[/math]

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

[math]\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). }[/math]

Примечания

↑ Buchholz, W. A New System of Proof-Theoretic Ordinal Functions (неопр.) // Annals of Pure and Applied Logic. — Т. 32.
↑ Jäger, G. [math]\displaystyle{ \rho }[/math]-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 [math]\displaystyle{ \Pi_2^1 }[/math]-Separation und Bar-Induktion (нем.) // Sitzungsberichte der Bayerischen Akademie der Wissenschaften, Math.-Naturw. Klasse : magazin. — 1983.

Ссылки

[1] Buchholz, W. A New System of Proof-Theoretic Ordinal Functions (неопр.) // Annals of Pure and Applied Logic. — Т. 32.

[2] Jäger, G. [math]\displaystyle{ \rho }[/math]-inaccessible ordinals, collapsing functions, and a recursive notation system (англ.) // Archiv f. math. Logik und Grundlagenf. : journal. — 1984. — Vol. 24, no. 1. — P. 49—62.

[3] Buchholz, W.; Schütte, K. Ein Ordinalzahlensystem ftir die beweistheoretische Abgrenzung der [math]\displaystyle{ \Pi_2^1 }[/math]-Separation und Bar-Induktion (нем.) // Sitzungsberichte der Bayerischen Akademie der Wissenschaften, Math.-Naturw. Klasse : magazin. — 1983.

[1]

[2]

[3]

Большие числа
Числа	Гугол Число Шеннона Гуголплекс Число Скьюза Число Мозера Число Грэма TREE(3) Число Райо
Функции	Функция Аккермана Функция Веблена Пси-функции Бухгольца Тетрация Пентация Гипероператор Быстрорастущая иерархия Медленнорастущая иерархия Иерархия Харди
Нотации	Обозначения Штейнгауза — Мозера Стрелочные обозначения Кнута Стрелочные обозначения Конвея Массивная нотация Бауэрса