Русская Википедия:Пси-функции Бухгольца

Содержание

Текст

Текст

Текст

Текст

Текст

Текст

Текст

Текст

Текст

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

Определение

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

<math>

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

где

<math>\omega</math> – наименьший трансфинитный ординал

<math>

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

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

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

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

Свойства

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

• <math>\psi_\nu(0)=\Omega_\nu, </math> в частности, <math>\psi_0(0)=1,</math>
• <math>\psi_\nu(\alpha)\in P, </math>
• <math>\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},</math>
• <math>\Omega_\nu\le\psi_\nu(\alpha)<\Omega_{\nu+1} </math>
• <math>\psi_0(\alpha)=\omega^\alpha \text{ если }\alpha<\varepsilon_0,</math>
• <math>\psi_\nu(\alpha)=\omega^{\Omega_\nu+\alpha} \text{ если } \alpha<\varepsilon_{\Omega_\nu+1} \text{ и } \nu\neq 0,</math>
• <math>\theta(\varepsilon_{\Omega_\nu+1},0)=\psi_0(\varepsilon_{\Omega_\nu+1}) \text{ для } 0<\nu\le\omega.</math>

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

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

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

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

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

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

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

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

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

Условие <math>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>C_\nu^{n+1}(\alpha)</math> содержит:

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

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

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

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

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

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

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

Примеры

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

<math>C_0^0(\alpha)=\{0\} =\{\beta\mid\beta<1\},</math>

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

Тогда <math>\psi_0(0)=1</math>.

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

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

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

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

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

<math>\psi_0(\Omega2)=\varepsilon_1</math> – второе число эпсилон,

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

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

<math>\psi_0(\Omega^\Omega)=\Gamma_0=\varphi(1,0,0)=\theta(\Omega,0)</math>, где <math>\theta</math> обозначает Шаблон:Iw, а <math>\Gamma_0</math> обозначает Шаблон:Iw

<math>\psi_0(\Omega^{\Omega^2})=\varphi(1,0,0,0)</math> – Шаблон:Iw,

<math>\psi_0(\Omega^{\Omega^\omega})</math> – Шаблон:Iw,

<math>\psi_0(\Omega^{\Omega^\Omega})</math> – Шаблон:Iw,

<math> \psi_0(\Omega\uparrow\uparrow\omega) =\psi_0(\varepsilon_{\Omega+1}) = \theta(\varepsilon_{\Omega+1},0).</math>

Теперь рассмотрим, как работает функция <math>\psi_1</math>:

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

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

<math>\psi_1(2)=\Omega\omega^2=\omega^{\Omega+2},</math>

<math>\psi_1(\psi_1(0))=\psi_1(\Omega)=\Omega^2=\omega^{\Omega+\Omega},</math>

<math>\psi_1(\psi_1(\psi_1(0))) =\omega^{\Omega+\omega^{\Omega+\Omega}} = \omega^{\Omega\cdot\Omega} = (\omega^{\Omega})^\Omega=\Omega^\Omega,</math>

<math>\psi_1^4(0)=\Omega^{\Omega^\Omega},</math>

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

<math> \psi_1(\Omega_2) = \psi_1^\omega(0) = \Omega \uparrow\uparrow \omega = \varepsilon_{\Omega+1}.</math>

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

и тогда

<math> \psi_0(\Omega_2) = \psi_0(\psi_1(\Omega_2)) = \psi_0(\varepsilon_{\Omega+1}).</math>

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

<math>\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>