Меню Главная Случайная статья Настройки Гидра Бухгольца Материал из https://ru.wikipedia.org Гидра Бухгольца — в математической логике и теории доказательств — однопользовательская математическая игра, основанная на последовательном отсечении «голов» у древовидной структуры, называемой гидрой. Игра является комбинаторным представлением сложного процесса редукции ординалов с использованием ординальных функций Бухгольца. Главное свойство игры заключается в том, что утверждение о её завершённости («любая игра с гидрой заканчивается») истинно, но недоказуемо в очень сильных формальных системах, таких как теория арифметики второго порядка ${\displaystyle {\mathsf {(\Pi _{1}^{1}-CA)+BI}}}$. Это делает её одним из важнейших примеров независимости в математической логике, превосходящим по силе классические примеры, такие как теорема Гудстейна (независимая от арифметики Пеано). Свойства игры и её связь с теорией доказательств были исследованы немецким математиком Вильфридом Бухгольцем в 1987 году[1]. Содержание 1 Описание игры 1.1 Ход игры 1.2 Цель игры 2 Теорема о гидре 3 Функция BH(n) 4 Связь с ординалами 5 См. также 6 Примечания 7 Литература 8 Ссылки Описание игры Игра ведётся на гидре — конечном корневом дереве ${\displaystyle A}$, обладающем следующими свойствами: Корень дерева имеет специальную метку ${\displaystyle +}$ и не считается обычной вершиной. Любая другая вершина (узел) имеет метку — ординал. В стандартных версиях игры эти ординалы ограничены некоторым большим счётным ординалом (например, ординалом Бахмана-Ховарда), но для иллюстрации часто рассматривают метки как натуральные числа или ${\displaystyle \omega }$. Все вершины, являющиеся непосредственными потомками корня, имеют метку ${\displaystyle 0}$. Терминальные вершины (листья) дерева, за исключением корня, называются головами гидры. Ход игры На каждом шаге ${\displaystyle n}$ (${\displaystyle n=1,2,3,\dots }$) игрок выбирает одну из голов гидры, обозначим её ${\displaystyle \sigma }$, и «отсекает» её (удаляет вместе с ведущим к ней ребром). После этого гидра ${\displaystyle A}$ преобразуется в новую гидру ${\displaystyle A'}$ по правилам, которые зависят от метки удалённой головы ${\displaystyle u}$ и структуры её предков. Пусть ${\displaystyle \tau }$ — родительская вершина для ${\displaystyle \sigma }$, а ${\displaystyle A^{-}}$ — дерево, оставшееся после удаления ${\displaystyle \sigma }$. Правило 1: Метка ${\displaystyle \sigma }$ равна 0 (${\displaystyle u=0}$) Гидра просто уменьшается: ${\displaystyle A'=A^{-}}$. Голова исчезает безвозвратно, новая структура не нарастает. Это единственный способ уменьшить количество вершин в гидре. Правило 2: Метка ${\displaystyle \sigma }$ — натуральное число ${\displaystyle u>0}$ Это правило самое сложное и отвечает за рост гидры. Находится первая вершина-предок ${\displaystyle \varepsilon }$ на пути от ${\displaystyle \sigma }$ к корню, метка которой ${\displaystyle v}$ строго меньше ${\displaystyle u}$ (${\displaystyle v<u}$). Если такой вершины нет, гидра не меняется (этот случай обычно исключается выбором стратегии). Поддерево ${\displaystyle A_{\tau }}$ с корнем в ${\displaystyle \tau }$ (родителе ${\displaystyle \sigma }$) копируется ${\displaystyle n}$ раз. В исходной гидре ${\displaystyle A^{-}}$ вершина ${\displaystyle \tau }$ удаляется вместе со всем своим поддеревом. Вместо ${\displaystyle \tau }$ к её родителю («дедушке» ${\displaystyle \sigma }$) прикрепляются ${\displaystyle n}$ копий поддерева ${\displaystyle A_{\tau }}$, в каждой из которых метка вершины, соответствующей ${\displaystyle \tau }$, заменяется на ${\displaystyle u-1}$. Правило 3: Метка ${\displaystyle \sigma }$ равна ${\displaystyle \omega }$ Метка самой вершины ${\displaystyle \sigma }$ заменяется на натуральное число ${\displaystyle n}$. Это правило «конкретизирует» предельную метку, используя номер текущего хода. Структура дерева при этом не меняется. Примечание: описанные правила являются популярной упрощённой версией. В оригинальной работе Бухгольца правила редукции более абстрактны и напрямую соответствуют коллапсу ординальных нотаций. Цель игры Цель игрока — «победить» гидру, то есть свести её к единственной вершине — корню ${\displaystyle (+)}$. Последовательность ходов называется стратегией. Если стратегия приводит к победе за конечное число шагов, она называется выигрышной. Теорема о гидре Несмотря на то, что правило 2 может приводить к взрывному росту гидры, игра всегда завершается за конечное число шагов, какую бы стратегию игрок ни выбрал. Теорема о гидре Бухгольца: Для любой гидры любая стратегия является выигрышной. Этот факт имеет глубокое значение для оснований математики. Завершаемость игры с гидрой Бухгольца является примером истинного утверждения, которое недоказуемо в сильной системе арифметики второго порядка ${\displaystyle {\mathsf {\Pi _{1}^{1}-CA+BI}}}$. Это означает, что для доказательства завершаемости требуются более мощные логические средства (например, трансфинитная индукция до достаточно большого ординала), чем те, что доступны в указанной системе. Функция BH(n) На основе игры с гидрой определяется быстрорастущая функция ${\displaystyle BH(x)}$. Для этого рассматривается специальный класс стартовых гидр и фиксированная стратегия. В качестве стартовой гидры ${\displaystyle R_{x}}$ берётся дерево, состоящее из корня ${\displaystyle +}$ с одним дочерним узлом с меткой ${\displaystyle 0}$, у которого, в свою очередь, есть один дочерний узел с меткой ${\displaystyle x}$. В качестве стратегии на каждом шаге выбирается самая правая голова гидры. Функция ${\displaystyle BH(x)}$ определяется как количество шагов, необходимое для победы над гидрой ${\displaystyle R_{x}}$ при использовании этой стратегии. Из теоремы о гидре следует, что функция ${\displaystyle BH(x)}$ всюду определена. Однако доказать её тотальность (т. е. то, что она определена для всех натуральных ${\displaystyle x}$) в системе ${\displaystyle {\mathsf {\Pi _{1}^{1}-CA+BI}}}$ невозможно. Скорость роста ${\displaystyle BH(x)}$ превосходит любые вычислимые функции, тотальность которых доказуема в этой системе. Связь с ординалами Доказательство завершаемости игры (в более сильной теории) основано на сопоставлении каждой гидре ${\displaystyle A}$ ординала ${\displaystyle o(A)}$ из некоторой системы ординальных нотаций. Ключевое свойство этого сопоставления в том, что каждый ход в игре строго уменьшает соответствующий ординал: ${\displaystyle o(A')<o(A)}$. Поскольку любое множество ординалов вполне упорядочено, любая строго убывающая последовательность ординалов конечна. Преобразование дерева в ординал выполняется рекурсивно с использованием ординальных функций Бухгольца ${\displaystyle \psi _{\alpha }(\beta )}$. Ординал, сопоставленный гидре, определяется по следующему принципу: Ординал гидры — это сумма ординалов поддеревьев, растущих из корня. Ординал поддерева, корень которого ${\displaystyle v}$ имеет метку ${\displaystyle u}$ и дочерние поддеревья ${\displaystyle T_{1},\dots ,T_{k}}$, вычисляется как ${\displaystyle o(T)=\psi _{u}(o(T_{1})+\dots +o(T_{k}))}$. Ординал листа (головы) — это ${\displaystyle \psi _{u}(0)}$. Примеры соответствия гидр и ординалов по стандартному отображению Гидра (структура) Ординал (вычисление) Значение ${\displaystyle +}$ ${\displaystyle 0}$ ${\displaystyle 0}$ ${\displaystyle +(0)}$ ${\displaystyle \psi _{0}(0)}$ ${\displaystyle 1}$ ${\displaystyle +(0)(0)}$ ${\displaystyle \psi _{0}(0)+\psi _{0}(0)}$ ${\displaystyle 2}$ ${\displaystyle +(0(0))}$ ${\displaystyle \psi _{0}(\psi _{0}(0))=\psi _{0}(1)}$ ${\displaystyle \omega }$ ${\displaystyle +(0(0(0)))}$ ${\displaystyle \psi _{0}(\psi _{0}(\psi _{0}(0)))=\psi _{0}(\omega )}$ ${\displaystyle \omega ^{\omega }}$ ${\displaystyle +(0(1))}$ ${\displaystyle \psi _{0}(\psi _{1}(0))}$ ${\displaystyle \omega ^{\varepsilon _{0}}}$ ${\displaystyle +(0(2))}$ ${\displaystyle \psi _{0}(\psi _{2}(0))}$ ${\displaystyle \omega ^{\zeta _{0}}}$ ${\displaystyle +(0(\omega ))}$ ${\displaystyle \psi _{0}(\psi _{\omega }(0))}$ Ординал Бухгольца ${\displaystyle \psi _{0}(\Omega _{\omega })}$ Примечание: таблица иллюстрирует, как древовидные структуры кодируют большие счётные ординалы. Значения в правой колонке (например, ${\displaystyle \varepsilon _{0},\zeta _{0}}$) являются стандартными обозначениями для некоторых важных ординалов. См. также Игра с гидрой (Кирби и Пэрис) — более простая версия игры, завершаемость которой недоказуема в арифметике Пеано. Теорема Гудстейна Быстрорастущая иерархия Теория доказательств Примечания Ошибка в сносках?: Неверный тег <ref>; для сносок buchholz не указан текст Литература Buchholz, Wilfried. An independence result for ${\displaystyle (\Pi _{1}^{1}{\text{-CA}})+{\text{BI}}}$ // Annals of Pure and Applied Logic. — 1987. — Т. 33, вып. 2. — С. 131–155. — doi:10.1016/0168-0072(87)90078-9. A direct independence proof of Buchholz's Hydra game on finite labeled trees // Archive for Mathematical Logic. — 1997. — Т. 37, вып. 2. — С. 67–89. — doi:10.1007/s001530050084. Ссылки Hydras (англ.) на сайте Agnijo's mathematical treasure chest.