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

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

Определение

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

• Ω _ξ = ω _ξ , если ξ > 0, Ω ₀ = 1

Функции ψ _v (α) для α — ординала, v — ординала не выше ω, определяются индукцией по α следующим образом:

• ψ _v (α) — наименьший ординал, не входящий в C _v (α)

где C _v (α) — наименьшее множество, такое что

• C _v (α) содержит все ординалы, меньшие Ω _v
• C _v (α) замкнуто относительно порядкового сложения
• C _v (α) замкнуто относительно функций ψ _u (для u ≤ω), примененных к аргументам, меньшим α.

Пределом этой записи является ординал Такеути–Фефермана–Бухгольца .

Характеристики

Пусть — класс аддитивно главных ординалов. Бухгольц показал следующие свойства этих функций: ${\displaystyle P}$

• ${\displaystyle \psi _{\nu }(0)=\Omega _{\nu },}$ ^{[3] : 197}
• ${\displaystyle \psi _{\nu }(\alpha )\in P,}$ ^{[3] : 197}
• ${\displaystyle \psi _{\nu }(\alpha +1)=\min\{\gamma \in P:\psi _{\nu }(\alpha )<\gamma \}{\text{ if }}\alpha \in C_{\nu }(\alpha ),}$ ^{[3] : 199}
• ${\displaystyle \Omega _{\nu }\leq \psi _{\nu }(\alpha )<\Omega _{\nu +1}}$ ^{[3] : 197}
• ${\displaystyle \psi _{0}(\alpha )=\omega ^{\alpha }{\text{ if }}\alpha <\varepsilon _{0},}$ ^{[3] : 199}
• ${\displaystyle \psi _{\nu }(\alpha )=\omega ^{\Omega _{\nu }+\alpha }{\text{ if }}\alpha <\varepsilon _{\Omega _{\nu }+1}{\text{ and }}\nu \neq 0,}$ ^{[3] : 199}
• ${\displaystyle \theta (\varepsilon _{\Omega _{\nu }+1},0)=\psi (\varepsilon _{\Omega _{\nu }+1}){\text{ for }}0<\nu \leq \omega .}$ ^{[3] : 206}

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

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

Нормальная форма для 0 — 0. Если — ненулевое порядковое число , то нормальная форма для — где и и каждое также записывается в нормальной форме. ${\displaystyle \alpha }$ ${\displaystyle \alpha <\Omega _{\omega }}$ ${\displaystyle \alpha }$ ${\displaystyle \alpha =\psi _{\nu _{1}}(\beta _{1})+\psi _{\nu _{2}}(\beta _{2})+\cdots +\psi _{\nu _{k}}(\beta _{k})}$ ${\displaystyle \nu _{i}\in \mathbb {N} _{0},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 }$ ${\displaystyle \operatorname {cof} (\alpha )=1}$ ${\displaystyle \alpha [0]=\alpha -1}$ ${\displaystyle \alpha }$ ${\displaystyle \operatorname {cof} (\alpha )\in \{\omega \}\cup \{\Omega _{\mu +1}\mid \mu \geq 0\}}$

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

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 _{0}(0)=1}$ ${\displaystyle \operatorname {cof} (\alpha )=1}$ ${\displaystyle \alpha [0]=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.}$

Объяснение

Бухгольц работает в теории множеств Цермело–Френкеля, что означает, что каждый ординал равен множеству . Тогда условие означает, что множество включает в себя все ординалы, меньшие, чем другими словами . ${\displaystyle \alpha }$ ${\displaystyle \{\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 \}.}$

Таким образом, объединение всех множеств с ie обозначает множество всех ординалов, которые могут быть получены из ординалов с помощью функций + (сложение) и , где и . ${\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\}}$(так как функций нет и 0 + 0 = 0). ${\displaystyle \psi (\eta <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 ,\beta )=\psi _{0}(\Omega ^{\alpha }(1+\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 {\text{googol}},\ldots ,\psi _{0}(1)=\omega ,\ldots ,\psi _{0}(\Omega )=\varepsilon _{0},\ldots }$

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

Мы также можем написать:

${\displaystyle \theta (\Omega _{\nu },0)=\psi _{0}(\Omega _{\nu }^{\Omega }){\text{ (for }}1\leq \nu )<\omega }$

Порядковая нотация

Бухгольц ^[3] определил порядковую нотацию, связанную с функцией. Мы одновременно определяем множества и как формальные строки, состоящие из индексированных по , фигурных скобок и запятых следующим образом: ${\displaystyle {\mathsf {(OT,<)}}}$ ${\displaystyle \psi }$ ${\displaystyle T}$ ${\displaystyle PT}$ ${\displaystyle 0,D_{v}}$ ${\displaystyle v\in \omega +1}$

• ${\displaystyle 0\in T\land 0\in PT}$,
• ${\displaystyle \forall (v,a)\in (\omega +1)\times T(D_{v}a\in T\land D_{v}a\in PT)}$.
• ${\displaystyle \forall (a_{0},a_{1})\in PT^{2}((a_{0},a_{1})\in T)}$.
• ${\displaystyle \exists s(a_{0}=s)\land (a_{0},a_{1})\in T\times PT\rightarrow (s,a_{1})\in T}$.

Элемент из называется термином , а элемент из называется главным термином . По определению, является рекурсивным множеством и является рекурсивным подмножеством . Каждый термин является либо , главным термином или массивом главных терминов в фигурных скобках длины . Мы обозначаем через . По соглашению, каждый термин может быть однозначно выражен либо как или как непустой массив главных терминов в фигурных скобках. Поскольку пункты 3 и 4 в определении и применимы только к массивам длины , это соглашение не вызывает серьезной двусмысленности. ${\displaystyle T}$ ${\displaystyle PT}$ ${\displaystyle T}$ ${\displaystyle PT}$ ${\displaystyle T}$ ${\displaystyle 0}$ ${\displaystyle \geq 2}$ ${\displaystyle a\in PT}$ ${\displaystyle (a)}$ ${\displaystyle 0}$ ${\displaystyle T}$ ${\displaystyle PT}$ ${\displaystyle \geq 2}$

Затем мы определяем бинарное отношение следующим образом: ${\displaystyle a<b}$ ${\displaystyle T}$

• ${\displaystyle b=0\rightarrow a<b=\bot }$
• ${\displaystyle a=0\rightarrow (a<b\leftrightarrow b\neq 0)}$
• Если , то: ${\displaystyle a\neq 0\land b\neq 0}$
  • Если для некоторых , то истинно, если верно одно из следующих утверждений: ${\displaystyle a=D_{u}a'\land b=D_{v}b'}$ ${\displaystyle ((u,a'),(v,b'))\in ((\omega +1)\times T)^{2}}$ ${\displaystyle a<b}$
    • ${\displaystyle u<v}$
    • ${\displaystyle u=v\land a'<b'}$
  • Если для некоторых , то истинно, если верно одно из следующих утверждений: ${\displaystyle a=(a_{0},...,a_{n})\land b=(b_{0},...,b_{m})}$ ${\displaystyle (n,m)\in \mathbb {N} ^{2}\land 1\leq n+m}$ ${\displaystyle a<b}$
    • ${\displaystyle \forall i\in \mathbb {N} \land i\leq n(n<m\land a_{i}=b_{i})}$
    • ${\displaystyle \exists k\in \mathbb {N} \forall i\in \mathbb {N} \land i<k(k\leq min\{n,m\}\land a_{k}<b_{k}\land a_{i}=b_{1})}$

${\displaystyle <}$является рекурсивным строгим полным порядком на . Мы сокращаем как . Хотя сам по себе не является хорошо упорядоченным, его ограничение на рекурсивное подмножество , которое будет описано позже, образует хорошо упорядоченное. Чтобы определить , мы определяем подмножество для каждого следующим образом: ${\displaystyle T}$ ${\displaystyle (a<b)\lor (a=b)}$ ${\displaystyle a\leq b}$ ${\displaystyle \leq }$ ${\displaystyle OT\subset T}$ ${\displaystyle OT}$ ${\displaystyle G_{u}a\subset T}$ ${\displaystyle (u,a)\in (\omega +1)\times T}$

• ${\displaystyle a=0\rightarrow G_{u}a=\varnothing }$
• Предположим, что для некоторого , тогда: ${\displaystyle a=D_{v}a'}$ ${\displaystyle (v,a')\in (\omega +1)\times T}$
  • ${\displaystyle u\leq v\rightarrow G_{u}a=\{a'\}\cup G_{u}a'}$
  • ${\displaystyle u>v\rightarrow G_{u}a=\varnothing }$

• Если для некоторых, для некоторых . ${\displaystyle a=(a_{0},...,a_{k})}$ ${\displaystyle (a_{i})_{i=0}^{k}\in PT^{k+1}}$ ${\displaystyle k\in \mathbb {N} \backslash \{0\},G_{u}a=\bigcup _{i=0}^{k}G_{u}a_{i}}$

${\displaystyle b\in G_{u}a}$является рекурсивным отношением на . Наконец, мы определяем подмножество следующим образом: ${\displaystyle (u,a,b)\in (\omega +1)\times T^{2}}$ ${\displaystyle OT\subset T}$

• ${\displaystyle 0\in OT}$
• Для любого , эквивалентно и для любого , . ${\displaystyle (v,a)\in (\omega +1)\times T}$ ${\displaystyle D_{v}a\in OT}$ ${\displaystyle a\in OT}$ ${\displaystyle a'\in G_{v}a}$ ${\displaystyle a'<a}$
• Для любого эквивалентно и . ${\displaystyle (a_{i})_{i=0}^{k}\in PT^{k+1}}$ ${\displaystyle (a_{0},...,a_{k})\in OT}$ ${\displaystyle (a_{i})_{i=0}^{k}\in OT}$ ${\displaystyle a_{k}\leq ...\leq a_{0}}$

${\displaystyle OT}$является рекурсивным подмножеством , а элемент называется порядковым членом . Затем мы можем определить карту следующим образом: ${\displaystyle T}$ ${\displaystyle OT}$ ${\displaystyle o:OT\rightarrow C_{0}(\varepsilon _{\Omega _{\omega }+1})}$

• ${\displaystyle a=0\rightarrow o(a)=0}$
• Если для некоторых , то . ${\displaystyle a=D_{v}a'}$ ${\displaystyle (v,a')\in (\omega +1)\times OT}$ ${\displaystyle o(a)=\psi _{v}(o(a'))}$
• Если для некоторого с , то , где обозначает убывающую сумму ординалов, что по определению совпадает с обычным сложением . ${\displaystyle a=(a_{0},...,a_{k})}$ ${\displaystyle (a_{i})_{i=0}^{k}\in (OT\cap PT)^{k+1}}$ ${\displaystyle k\in \mathbb {N} \backslash \{0\}}$ ${\displaystyle o(a)=o(a_{0})\#...\#o(a_{k})}$ ${\displaystyle \#}$ ${\displaystyle OT}$

Бухгольц проверил следующие свойства : ${\displaystyle o}$

• Отображение является сохраняющим порядок биективным отображением относительно и . В частности, является рекурсивным строгим полным порядком на . ${\displaystyle o}$ ${\displaystyle <}$ ${\displaystyle \in }$ ${\displaystyle o}$ ${\displaystyle OT}$
• Для любого удовлетворяющего совпадает с порядковым типом, ограниченным счетным подмножеством . ${\displaystyle a\in OT}$ ${\displaystyle a<D_{1}0}$ ${\displaystyle o(a)}$ ${\displaystyle <}$ ${\displaystyle \{x\in OT\;|\;x<a\}}$
• Ординал Такеути -Фефермана-Бухгольца совпадает с ординальным типом, ограниченным рекурсивным подмножеством . ${\displaystyle <}$ ${\displaystyle \{x\in OT\;|\;x<D_{1}0\}}$
• Порядковый тип больше, чем порядковый тип Такеути-Фефермана-Бухгольца . ${\displaystyle (OT,<)}$
• Для любого обоснованность ограничения рекурсивным подмножеством в смысле несуществования примитивно рекурсивной бесконечной нисходящей последовательности не доказуема при . ${\displaystyle v\in \mathbb {N} \;\backslash \;\{0\}}$ ${\displaystyle <}$ ${\displaystyle \{x\in OT\;|\;x<D_{0}D_{v+1}0\}}$ ${\displaystyle {\mathsf {ID}}_{v}}$
• Обоснованность ограничения рекурсивным подмножеством в том же смысле, что и выше, не доказуема при . ${\displaystyle <}$ ${\displaystyle \{x\in OT\;|\;x<D_{0}D_{\omega }0\}}$ ${\displaystyle \Pi _{1}^{1}-CA_{0}}$

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

Нормальная форма для функции Бухгольца может быть определена путем вытягивания стандартной формы для порядковой нотации, связанной с ней посредством . А именно, набор предикатов для порядковых чисел в определяется следующим образом: ${\displaystyle o}$ ${\displaystyle NF}$ ${\displaystyle C_{0}(\varepsilon _{\Omega _{\omega }+1})}$

• Предикат порядкового числа, определяемый как «принадлежит» . ${\displaystyle \alpha =_{NF}0}$ ${\displaystyle \alpha \in C_{0}(\varepsilon _{\Omega _{\omega }+1})}$ ${\displaystyle \alpha =0}$ ${\displaystyle NF}$

• Предикат  на ординалах  определен  как  и  принадлежит . ${\displaystyle \alpha _{0}=_{NF}\psi _{k_{1}}(\alpha _{1})}$ ${\displaystyle \alpha _{0},\alpha _{1}\in C_{0}(\varepsilon _{\Omega _{\omega }+1})}$ ${\displaystyle k_{1}=\omega +1}$ ${\displaystyle \alpha _{0}=\psi _{k_{1}}(\alpha _{1})}$ ${\displaystyle \alpha _{1}=C_{k_{1}}(\alpha _{1})}$ ${\displaystyle NF}$
• Предикат на ординалах  с целым числом,  определяемым как , , и  принадлежит . Здесь  — это символ функции, а не фактическое сложение, и  обозначает класс главных аддитивных чисел. ${\displaystyle \alpha _{0}=_{NF}\alpha _{1}+...+\alpha _{n}}$ ${\displaystyle \alpha _{0},\alpha _{1},...,\alpha _{n}\in C_{0}(\varepsilon _{\Omega _{\omega }+1})}$ ${\displaystyle n>1}$ ${\displaystyle \alpha _{0}=\alpha _{1}+...+\alpha _{n}}$ ${\displaystyle \alpha _{1}\geq ...\geq \alpha _{n}}$ ${\displaystyle \alpha _{1},...,\alpha _{n}\in AP}$ ${\displaystyle NF}$ ${\displaystyle +}$ ${\displaystyle AP}$

Также полезно заменить третий случай следующим, полученным путем объединения второго условия:

• Предикат на ординалах  с целым числом  и определяется как , , и  принадлежит . ${\displaystyle \alpha _{0}=_{NF}\psi _{k_{1}}(\alpha _{1})+...+\psi _{k_{n}}(\alpha _{n})}$ ${\displaystyle \alpha _{0},\alpha _{1},...,\alpha _{n}\in C_{0}(\varepsilon _{\Omega _{\omega }+1})}$ ${\displaystyle n>1}$ ${\displaystyle k_{1},...,k_{n}\in \omega +1}$ ${\displaystyle \alpha _{0}=\psi _{k_{1}}(\alpha _{1})+...+\psi _{k_{n}}(\alpha _{n})}$ ${\displaystyle \psi _{k_{1}}(\alpha _{1})\geq ...\geq \psi _{k_{n}}(\alpha _{n})}$ ${\displaystyle \alpha _{1}\in C_{k_{1}}(\alpha _{1}),...,\alpha _{n}\in C_{k_{n}}(\alpha _{n})\in AP}$ ${\displaystyle NF}$

Отметим, что эти две формулировки не эквивалентны. Например,  является допустимой формулой, которая ложна относительно второй формулировки из-за , в то время как является допустимой формулой, которая истинна относительно первой формулировки из-за , , и . Таким образом, понятие нормальной формы сильно зависит от контекста. В обеих формулировках каждый ординал в  может быть однозначно выражен в нормальной форме для функции Бухгольца. ${\displaystyle \psi _{0}(\Omega )+1=_{NF}\psi _{0}(\zeta _{1})+\psi _{0}(0)}$ ${\displaystyle \zeta _{1}\neq C_{0}(\zeta _{1})}$ ${\displaystyle \psi _{0}(\Omega )+1=\psi _{0}(\zeta _{1})+\psi _{0}(0)}$ ${\displaystyle \psi _{0}(\zeta _{1}),\psi _{0}(0)\in AP}$ ${\displaystyle \psi _{0}(\zeta _{1})\geq \psi _{0}(0)}$ ${\displaystyle C_{0}(\varepsilon _{\Omega _{\omega }+1})}$

Ссылки

1. Джагер, Г (1984). «ρ-недоступные ординалы, схлопывающиеся функции и рекурсивная система обозначений». Archiv für Mathematische Logik und Grundlagenforschung . 24 (1): 49–62. дои : 10.1007/BF02007140. S2CID  38619369.
2. Бухгольц, В.; Шютте, К. (1983). «Ein Ordinalzahlensystem ftir die beweistheoretische Abgrenzung der H~-Separation und Bar-Induktion». Sitzungsberichte der Bayerischen Akademie der Wissenschaften, Math.-Naturw. Класс .
3. Бухгольц, В. (1986). «Новая система порядковых функций теории доказательств». Annals of Pure and Applied Logic . 32 : 195–207. doi : 10.1016/0168-0072(86)90052-7 .