Бухгольц гидра

В математике , особенно в математической логике , теории графов и теории чисел , игра «Гидра Бухгольца» — это разновидность игры «Гидра» , которая представляет собой однопользовательскую игру, основанную на идее отрубания частей от математического дерева . Игру «Гидра» можно использовать для генерации быстро растущей функции , $BH(n)$ , которая в конечном итоге доминирует над всеми рекурсивными функциями , которые доказуемо тотальны в " ${\textrm {ID}}_{\nu }$ ", и прекращение всех игр гидры не является доказуемо полным в ${\textrm {(}}\Pi _{1}^{1}{\textrm {-CA)+BI}}$ . ^[1]

Правила

Игра ведется на гидре — конечном с корнями . связном дереве $A$ , со следующими свойствами:

Корень $A$ имеет специальную этикетку, обычно обозначаемую $+$ .
Любой другой узел $A$ есть этикетка $\nu \leq \omega$ .
Все узлы непосредственно над корнем $A$ иметь ярлык $0$ .

Если игрок решит удалить верхний узел $\sigma$ из $A$ , тогда гидра выберет произвольный $n\in \mathbb {N}$ , где $n$ текущий номер хода, а затем трансформируется в новую гидру $A(\sigma ,n)$ следующее. Позволять $\tau$ представлять родителя $\sigma$ , и пусть $A^{-}$ представляют собой часть гидры, которая остается после $\sigma$ был удален. Определение $A(\sigma ,n)$ зависит от этикетки $\sigma$ :

Если этикетка $\sigma$ равно 0 и $\tau$ является корнем $A$ , затем $A(\sigma ,n)$ = $A^{-}$ .
Если этикетка $\sigma$ равно 0, но $\tau$ не является корнем $A$ , $n$ копии $\tau$ и все его дети созданы, и края между ними и $\tau$ родительский элемент добавлен. Это новое дерево $A(\sigma ,n)$ .
Если этикетка $\sigma$ является $u$ для некоторых $u\in \mathbb {N}$ , позволять $\varepsilon$ быть первым узлом ниже $\sigma$ у которого есть этикетка $v<u$ . Определять $B$ как поддерево, полученное начиная с $A_{\varepsilon }$ и замена этикетки $\varepsilon$ с $u-1$ и $\sigma$ с 0. $A(\sigma ,n)$ затем получается, взяв $A$ и замена $\sigma$ с $B$ . В этом случае значение $n$ не имеет значения.
Если этикетка $\sigma$ является $\omega$ , $A(\sigma ,n)$ получается заменой метки $\sigma$ с $n+1$ .

Если $\sigma$ это самый правый глава $A$ , $A(n)$ написано. Серия ходов называется стратегией. Стратегия называется выигрышной, если после конечного числа ходов гидра возвращается к своему корню. Это всегда прекращается, хотя гидра может значительно вырасти выше. ^[1]

Теорема Гидры

Статья Бухгольца 1987 года показала, что каноническое соответствие между гидрой и бесконечным обоснованным деревом (или соответствующим термином в системе обозначений $T$ связан с функцией Бухгольца, которая не обязательно принадлежит порядковой системе обозначений $OT\subset T$ ), сохраняет фундаментальные последовательности выбора крайних правых листьев и $(n)$ операцию на бесконечном обоснованном дереве или $[n]$ операции на соответствующем сроке в $T$ . ^[1]

Теорема о гидре для гидры Бухгольца, утверждающая, что для любой гидры не существует проигрышных стратегий, недоказуема в ${\mathsf {\Pi _{1}^{1}-CA+BI}}$ . ^[2]

ЧД(н)

Предположим, что дерево состоит всего из одной ветви с $x$ узлы, помеченные $+,0,\omega ,...,\omega$ . Назовите такое дерево $R^{n}$ . Это невозможно доказать в ${\mathsf {\Pi _{1}^{1}-CA+BI}}$ это для всех $x$ , существует $k$ такой, что $R_{x}(1)(2)(3)...(k)$ это выигрышная стратегия. (Последнее выражение означает взятие дерева $R_{x}$ , затем преобразуя его с помощью $n=1$ , затем $n=2$ , затем $n=3$ и т. д. до $n=k$ .) ^[2]

Определять $BH(x)$ как самый маленький $k$ такой, что $R_{x}(1)(2)(3)...(k)$ как определено выше, является выигрышной стратегией. По теореме о гидре эта функция корректно определена, но ее полнота не может быть доказана в ${\mathsf {\Pi _{1}^{1}-CA+BI}}$ . Гидры растут очень быстро, потому что для убийства требуется количество ходов. $R_{x}(1)(2)$ больше, чем число Грэма или даже количество ходов, необходимое для убийства гидры Кирби-Пэрис; и $R_{x}(1)(2)(3)(4)(5)(6)$ имеет целую гидру Кирби-Пэрис в качестве своей ветви. Точнее, считается, что темпы его роста сопоставимы с $f_{\psi _{0}(\varepsilon _{\Omega _{\omega }+1})}(x)$ относительно неуказанной системы фундаментальных последовательностей без доказательства. Здесь, $\psi _{0}$ обозначает функцию Бухгольца, а $\psi _{0}(\varepsilon _{\Omega _{\omega }+1})$ – это ординал Такеути-Фефермана-Бухгольца, который измеряет силу ${\mathsf {\Pi _{1}^{1}-CA+BI}}$ .

Первые два значения функции BH практически вырождены: $BH(1)=0$ и $BH(2)=1$ . Аналогично слабой древовидной функции, $BH(3)$ очень велик, но меньше. ^{[ нужна ссылка ]}

Гидра Бухгольца в конечном итоге превосходит TREE(n) и SCG(n) , ^{[ нужна ссылка ]} тем не менее, он, вероятно, слабее, чем загрузчик, а также цифры из игр с конечным обещанием.

Анализ

можно установить взаимно однозначное соответствие Между некоторыми гидрами и ординалами . Чтобы преобразовать дерево или поддерево в порядковый номер:

Индуктивно преобразовать всех непосредственных дочерних элементов узла в порядковые номера.
Сложите эти дочерние ординалы. Если детей не было, это будет 0.
Если метка узла не +, примените $\psi _{\alpha }$ , где $\alpha$ — метка узла, а $\psi$ есть функция Бухгольца.

Полученное порядковое выражение полезно только в том случае, если оно находится в нормальной форме. Некоторые примеры:

Конверсия
Гидра	Порядковый номер
$+$	$0$
$+(0)$	$\psi _{0}(0)=1$
$+(0)(0)$	$2$
$+(0(0))$	$\psi _{0}(1)=\omega$
$+(0(0))(0)$	$\omega +1$
$+(0(0))(0(0))$	$\omega \cdot 2$
$+(0(0)(0))$	$\omega ^{2}$
$+(0(0(0)))$	$\omega ^{\omega }$
$+(0(1))$	$\varepsilon _{0}$
$+(0(1)(1))$	$\varepsilon _{1}$
$+(0(1(0)))$	$\varepsilon _{\omega }$
$+(0(1(1)))$	$\zeta _{0}$
$+(0(1(1(1))))$	$\Gamma _{0}$
$+(0(1(1(1(0)))))$	ТАК
$+(0(1(1(1(1)))))$	ЛВО
$+(0(2))$	ОТ
$+(0(\omega ))$	БО

Ссылки

^ Jump up to: ^а ^б ^с Бухгольц, Вильфрид (1987), "Результат независимости для $(\Pi _{1}^{1}{\text{-CA}})+{\text{BI}}$ », Анналы чистой и прикладной логики , 33 (2): 131–155, doi : 10.1016/0168-0072(87)90078-9 , MR 0874022
^ Jump up to: ^а ^б Хамано, Масахиро; Окада, Мицухиро (1997), «Прямое доказательство независимости игры Бухгольца «Гидра» на конечных помеченных деревьях», Archive for Mathematical Logic , 37 (2): 67–89, doi : 10.1007/s001530050084 , MR 1620664

Дальнейшее чтение

Хамано, Масахиро; Окада, Мицухиро (1997), «Взаимосвязь между редукцией доказательства Генцена, игрой гидры Кирби-Пэрис и игрой гидры Бухгольца», Mathematical Logic Quarterly , 43 (1): 103–120, doi : 10.1002/malq.19970430113 , MR 1429324
Гордеев, Лев (декабрь 2001 г.), «Обзор «Прямого доказательства независимости игры Бухгольца Гидры на конечных помеченных деревьях », Бюллетень символической логики , 7 (4): 534–535, doi : 10.2307/2687805 , ISSN 1079- 8986 , JSTOR 2687805
Кирби, Лори; Пэрис, Джефф (1982), «Доступные результаты независимости для арифметики Пеано» (PDF) , Bull. Лондонская математика. Соц. , 14 (4): 285–293, doi : 10.1112/blms/14.4.285 , получено 3 сентября 2021 г.
Кетонен, Юсси; Соловей, Роберт (1981), «Быстро растущие функции Рамсея» , Annals of Mathematics , 113 (2): 267–314, doi : 10.2307/2006985 , ISSN 0003-486X , JSTOR 2006985 , получено 03 сентября 2021 г.
Такеути, Гаиси (2013), Теория доказательств (2-е издание (переиздание)), Ньюберипорт: Dover Publications, ISBN 978-0-486-32067-0 , OCLC 1162507470

Внешние ссылки

«Гидрас» , математический сундук с сокровищами Аньихо , извлечен 4 сентября 2021 г.

В эту статью включен текст , доступный по лицензии CC BY-SA 3.0 .

[buchholz-1] Jump up to: ^а ^б ^с Бухгольц, Вильфрид (1987), "Результат независимости для $(\Pi _{1}^{1}{\text{-CA}})+{\text{BI}}$ », Анналы чистой и прикладной логики , 33 (2): 131–155, doi : 10.1016/0168-0072(87)90078-9 , MR 0874022

[hamano-okada-2] Jump up to: ^а ^б Хамано, Масахиро; Окада, Мицухиро (1997), «Прямое доказательство независимости игры Бухгольца «Гидра» на конечных помеченных деревьях», Archive for Mathematical Logic , 37 (2): 67–89, doi : 10.1007/s001530050084 , MR 1620664

[1]

[2]