Иерархия Харди

В теории вычислимости , теории сложности вычислений и теории доказательств иерархия Харди , названная в честь Г.Х. Харди , представляет собой иерархию множеств числовых функций, порожденных из порядкового индексного семейства функций h _α : N → N (где N — множество натуральные числа , {0, 1, ...}), называемые функциями Харди . Это связано с быстрорастущей иерархией и медленнорастущей иерархией .

Иерархия Харди была представлена ​​Стэнли С. Вайнером в 1972 году. но идея его определения взята из статьи Харди 1904 года: в котором Харди демонстрирует набор реалов с мощностью $\aleph _{1}$.

Определение

Пусть µ — такой большой счетный ординал , что фундаментальная последовательность соответствует каждому предельному ординалу, меньшему µ, . Тогда функции Харди h _α : N → N для α < µ определяются следующим образом:

• $H_{0}(n)=n,$
• $H_{\alpha +1}(n)=H_{\alpha }(n+1),$
• $H_{\alpha }(n)=H_{\alpha [n]}(n)$ если α — предельный ординал.

Здесь α[ n ] обозначает n ^й элемент фундаментальной последовательности, присвоенный предельному ординалу α . Стандартизированный выбор фундаментальной последовательности для всех α ≤ ε ₀ описан в статье о быстрорастущей иерархии .

Иерархия Харди $\{{\mathcal {H}}_{\alpha }\}_{\alpha <\mu }$ представляет собой семейство числовых функций. Для каждого ординала α множество ${\mathcal {H}}_{\alpha }$ определяется как наименьший класс функций, содержащий H _α , ноль, функции-преемники и проекции, и замкнутый при ограниченной примитивной рекурсии и ограниченной замене. (аналогично иерархии Гжегорчика ).

Кайседо (2007) определяет модифицированную иерархию функций Харди. $H_{\alpha }$ используя стандартные фундаментальные последовательности, но с α[ n +1] (вместо α[ n ]) в третьей строке приведенного выше определения.

Отношение к быстрорастущей иерархии

Иерархия Вейнера функций f _α и иерархия Харди функций H _α связаны соотношением f _α = H _{ω ^а} для всех α < ε ₀ . Таким образом, для любого α < ε ₀ чем H _α растет гораздо медленнее, f _α . Однако иерархия Харди «догоняет» иерархию Вейнера при α = ε ₀ , так что f _{ε 0} и H _{ε 0} имеют одинаковую скорость роста в том смысле, что f _{ε 0} ( n -1) ≤ H _{ε 0} ( n ) ≤ f _{ε 0} ( n +1) для всех n ≥ 1. ( Gallier 1991 )

Ссылки

• Харди, GH (1904), «Теорема о бесконечных кардинальных числах», Ежеквартальный журнал математики , 35 : 87–94.
• Галье, Жан Х. (1991), «Что такого особенного в теореме Краскала и ординале Γ ₀ ? Обзор некоторых результатов теории доказательств» (PDF) , Ann. Чистое приложение. Logic , 53 (3): 199–260, doi : 10.1016/0168-0072(91)90022-E , MR   1129778 . (В частности, раздел 12, стр. 59–64, «Взгляд на иерархии быстро и медленно растущих функций».)
• Кайседо, А. (2007), «Функция Гудштейна» (PDF) , Revista Colombiana de Matemáticas , 41 (2): 381–391 .