Jump to content

Гиперарифметическая теория

В теории вычислимости теория гиперарифметики является обобщением вычислимости по Тьюрингу . Он имеет тесные связи с определимостью в арифметике второго порядка и со слабыми системами теории множеств, такими как теория множеств Крипке-Платека . Это важный инструмент эффективной дескриптивной теории множеств . [1]

В центре внимания теории гиперарифметики находятся множества натуральных чисел, известные как гиперарифметические множества . Есть три эквивалентных способа определения этого класса множеств; изучение взаимосвязей между этими различными определениями является одной из причин изучения гиперарифметической теории.

и Гиперарифметические определимость множества

Первое определение гиперарифметических множеств использует аналитическую иерархию . Набор натуральных чисел классифицируется на уровне этой иерархии, если ее можно определить формулой арифметики второго порядка с использованием только кванторов экзистенциального множества и без каких-либо других кванторов множеств. Набор классифицируется на уровне аналитической иерархии, если она может быть определена формулой арифметики второго порядка только с кванторами универсального множества и без каких-либо других кванторов множеств. Набор если это оба и . Гиперарифметические множества — это в точности наборы.

итерированные прыжки Тьюринга: гиперарифметическая Гиперарифметические множества и иерархия

Определение гиперарифметических множеств как не зависит напрямую от результатов вычислимости. Второе, эквивалентное определение показывает, что гиперарифметические множества могут быть определены с помощью бесконечно повторяющихся прыжков Тьюринга . Это второе определение также показывает, что гиперарифметические множества можно классифицировать в иерархию, расширяющую арифметическую иерархию ; гиперарифметические множества — это именно те множества, которым присвоен ранг в этой иерархии.

Каждый уровень гиперарифметической иерархии индексируется счетным порядковым числом (ординалом), но не все счетные порядковые номера соответствуют уровню иерархии. Порядковые номера, используемые в иерархии, имеют порядковую нотацию , которая представляет собой конкретное и эффективное описание порядкового номера.

Порядковая запись — это эффективное описание счетного порядкового номера натуральным числом. Для определения гиперарифметической иерархии необходима система порядковых обозначений. Фундаментальное свойство, которым должна обладать порядковая запись, заключается в том, что она эффективно описывает порядковый номер в терминах меньших порядковых чисел. Типично следующее индуктивное определение; он использует функцию сопряжения .

  • Число 0 является обозначением порядкового номера 0.
  • Если n — обозначение ординала λ , то — обозначение λ + 1;
  • Предположим, что δ предельный ординал . Обозначением δ является число вида , где e — индекс полной вычислимой функции что для каждого n такой , — обозначение порядкового номера λ n меньше δ , а δ — это sup множества .

Это также можно определить, используя эффективные соединения на всех уровнях вместо только обозначений предельных порядковых номеров. [2]

Существует только счетное число порядковых обозначений, поскольку каждое обозначение представляет собой натуральное число; таким образом, существует счетный ординал, который является верхним числом всех ординалов, имеющих обозначение. Этот порядковый номер известен как порядковый номер Чёрча-Клин и обозначается . Обратите внимание, что этот порядковый номер по-прежнему счетен, а символ является лишь аналогией с первым неисчисляемым порядковым номером: . Множество всех натуральных чисел, являющихся порядковыми обозначениями, обозначается и позвонил Клини .

Порядковые обозначения используются для определения итерированных прыжков Тьюринга. Наборы натуральных чисел, используемые для определения иерархии: для каждого . иногда также обозначается , [3] или для обозначения для . [2] Предположим, что δ имеет обозначение e . Эти множества были впервые определены Дэвисом (1950) и Мостовски (1951). [2] Набор определяется с помощью e следующим образом.

  • Если δ = 0, то пустое множество.
  • Если δ = λ + 1, то это прыжок Тьюринга . Наборы и являются и , соответственно.
  • Если δ — предельный ординал, пусть — последовательность ординалов меньше δ, заданная обозначением e . Набор дается по правилу . Это эффективное соединение множеств .

Несмотря на то, что строительство зависит от наличия фиксированного обозначения для δ , а каждый бесконечный ординал имеет множество обозначений, теорема Клиффорда Спектора показывает, что Тьюринга степень зависит только от δ , а не от конкретных используемых обозначений, и, следовательно, хорошо определена с точностью до степени Тьюринга. [2]

Гиперарифметическая иерархия определяется этими повторяющимися прыжками Тьюринга. Множество X натуральных чисел классифицируется на уровне δ гиперарифметической иерархии, поскольку , если X сводится по Тьюрингу к . Всегда будет наименьшее такое δ , если оно вообще существует; именно это наименьшее δ измеряет уровень невычислимости X .

Гиперарифметические множества и конструктивность [ править ]

Позволять обозначают -й уровень конструктивной иерархии , и пусть быть отображением члена О Клини до порядкового номера, который он представляет. Подмножество является гиперарифметическим тогда и только тогда, когда оно является членом . Подмножество определяется с помощью формула тогда и только тогда, когда ее изображение под является -определяемый на , где взято из Леви . иерархии формул [4]

множества и рекурсия в Гиперарифметические типах высших

Третья характеристика гиперарифметических множеств, предложенная Клини, использует более высокого типа вычислимые функционалы . Функционал типа 2 определяется следующими правилами:

если существует i такое, что f ( i ) > 0,
если не существует i такого, что f ( i ) > 0.

Используя точное определение вычислимости относительно функционала типа 2, Клини показала, что набор натуральных чисел является гиперарифметическим тогда и только тогда, когда он вычислим относительно .

Пример: набор истинностей арифметики [ править ]

Каждое арифметическое множество является гиперарифметическим, но существует множество других гиперарифметических множеств. Одним из примеров гиперарифметического и неарифметического набора является набор T чисел Гёделя формул арифметики Пеано , которые верны для стандартных натуральных чисел. . Множество T тьюринг- эквивалентно множеству , и поэтому не занимает высокого места в гиперарифметической иерархии, хотя его нельзя арифметически определить с помощью теоремы неопределимости Тарского .

результаты Фундаментальные

Фундаментальные результаты теории гиперарифметики показывают, что три приведенных выше определения определяют один и тот же набор множеств натуральных чисел. Эти эквивалентности принадлежат Клини.

Результаты о полноте также имеют фундаментальное значение для теории. Набор натуральных чисел – это завершено, если оно находится на уровне аналитической иерархии и каждого множество натуральных чисел сводится к нему многими-единицами . Определение полное подмножество пространства Бэра ( ) аналогично. Несколько множеств, связанных с теорией гиперарифметики: полный:

  • Клини , набор натуральных чисел, которые являются обозначениями порядковых чисел
  • Множество натуральных чисел e таких, что вычислимая функция вычисляет характеристическую функцию хорошего порядка натуральных чисел. Это индексы рекурсивных ординалов .
  • Множество элементов пространства Бэра , которые являются характеристическими функциями хорошего упорядочения натуральных чисел (с использованием эффективного изоморфизма .

Результаты, известные как оценки следуют из этих результатов о полноте. Для любого множество S порядковых обозначений, существует такой, что каждый элемент S является обозначением порядкового номера меньше . Для любого подмножества T пространства Бэра, состоящего только из характеристических функций хорошего порядка, существует такой, что каждый порядковый номер, представленный в T, меньше, чем .

и Релятивизированная гиперстепени гиперарифметичность

Определение может быть релятивизировано к набору X натуральных чисел: в определении порядковой записи предложение о предельных ординалах изменено так, что вычислимое перечисление последовательности порядковых обозначений позволяет использовать X в качестве оракула. Множество чисел, являющихся порядковыми обозначениями относительно X , обозначается . Верхняя грань ординалов, представленных в обозначается ; это счетный ординал не меньше .

Определение также может быть релятивизировано к произвольному множеству натуральных чисел. Единственное изменение в определении состоит в том, что определяется как X, а не как пустое множество, так что является прыжком Тьюринга X и так далее. Вместо завершения на иерархия относительно X проходит через все порядковые номера меньше .

Релятивизированная гиперарифметическая иерархия используется для определения гиперарифметической сводимости . Учитывая множества X и Y , мы говорим тогда и только тогда, когда существует такой, что X сводится по Тьюрингу к . Если и тогда обозначение используется для обозначения того, X и Y что гиперарифметически эквивалентны . Это более грубое отношение эквивалентности, чем эквивалентность Тьюринга ; например, каждый набор натуральных чисел гиперарифметически эквивалентен своему скачку Тьюринга , но не эквивалентен Тьюрингу своему скачку Тьюринга. Классы эквивалентности гиперарифметической эквивалентности известны как гиперстепени .

Функция, которая переводит множество X в известен как гиперпрыжок по аналогии со скачком Тьюринга. Установлены многие свойства гиперпрыжка и гиперстепеней. В частности, известно, что проблема Поста для гиперстепеней имеет положительный ответ: для каждого множества X натуральных чисел существует множество Y натуральных чисел такое, что .

Обобщения [ править ]

Гиперарифметическая теория обобщается теорией α -рекурсии , которая изучает определимые подмножества допустимых ординалов . Гиперарифметическая теория — это частный случай, когда α равно .

Связь с другими иерархиями [ править ]

Светлое лицо Жирный шрифт
С 0
0
= П 0
0
= Д 0
0
(иногда то же, что ∆ 0
1
)
С 0
0
= П 0
0
= Д 0
0
(если определено)
Д 0
1
= рекурсивный
Д 0
1
= закрыто открыто
С 0
1
= рекурсивно перечисляемый
П 0
1
= корекурсивно перечисляемый
С 0
1
= G = открыто
П 0
1
= F = закрыто
Д 0
2
Д 0
2
С 0
2
П 0
2
С 0
2
= Ф п
П 0
2
= г δ
Д 0
3
Д 0
3
С 0
3
П 0
3
С 0
3
= г дс
П 0
3
= Ф сд
С 0
= Р 0
= D 0
= S 1
0
= П 1
0
= Д 1
0
= арифметический
С 0
= Р 0
= D 0
= S 1
0
= П 1
0
= Д 1
0
= жирный арифметический шрифт
Д 0
а
( рекурсивный )
Д 0
а
( счетное )
С 0
а
П 0
а
С 0
а
П 0
а
С 0
ой СК
1
= П 0
ой СК
1
= Д 0
ой СК
1
= Д 1
1
= гиперарифметический
С 0
ω 1
= Р 0
ω 1
= Д 0
ω 1
= Д 1
1
= Б = Борель
С 1
1
= аналитика светлого лица
П 1
1
= коаналитик светлой поверхности
С 1
1
= А = аналитический
П 1
1
= СА = коаналитический
Д 1
2
Д 1
2
С 1
2
П 1
2
С 1
2
= PCA
П 1
2
= КПКА
Д 1
3
Д 1
3
С 1
3
П 1
3
С 1
3
= ПКПККА
П 1
3
= CPCPCA
С 1
= Р 1
= D 1
= S 2
0
= П 2
0
= Д 2
0
= аналитический
С 1
= Р 1
= D 1
= S 2
0
= П 2
0
= Д 2
0
= P = проективный


Ссылки [ править ]

  • Х. Роджерс -младший, 1967. Теория рекурсивных функций и эффективная вычислимость , второе издание, 1987, MIT Press. ISBN   0-262-68052-1 (мягкая обложка), ISBN   0-07-053522-1
  • Г. Сакс , 1990. Теория высшей рекурсии , Springer-Verlag. ISBN   3-540-19305-7
  • С. Симпсон , 1999. Подсистемы арифметики второго порядка , Springer-Verlag.
  • Си Джей Эш, Дж. Ф. Найт , 2000. Вычислимые структуры и гиперарифметическая иерархия , Elsevier. ISBN   0-444-50072-3

Цитаты [ править ]

  1. ^ Теория вычислимости гиперарифметических множеств
  2. ^ Jump up to: Перейти обратно: а б с д С.Г. Симпсон, Иерархия, основанная на операторе перехода , стр. 268–269. Симпозиум Клини (Северная Голландия, 1980 г.)
  3. ^ CJ Эш, Дж. Найт, Вычислимые структуры и гиперарифметическая иерархия (Исследования в области логики и основы математики, 2000), гл. 5
  4. ^ Д. Натингга, Теорема вложения для группы автоморфизмов степеней α-перечисления (стр. 27), докторская диссертация, Университет Лидса, 2019.

Внешние ссылки [ править ]

Arc.Ask3.Ru: конец переведенного документа.
Arc.Ask3.Ru
Номер скриншота №: 958e8e41c84ff105a9f864587dbf888d__1712059200
URL1:https://arc.ask3.ru/arc/aa/95/8d/958e8e41c84ff105a9f864587dbf888d.html
Заголовок, (Title) документа по адресу, URL1:
Hyperarithmetical theory - Wikipedia
Данный printscreen веб страницы (снимок веб страницы, скриншот веб страницы), визуально-программная копия документа расположенного по адресу URL1 и сохраненная в файл, имеет: квалифицированную, усовершенствованную (подтверждены: метки времени, валидность сертификата), открепленную ЭЦП (приложена к данному файлу), что может быть использовано для подтверждения содержания и факта существования документа в этот момент времени. Права на данный скриншот принадлежат администрации Ask3.ru, использование в качестве доказательства только с письменного разрешения правообладателя скриншота. Администрация Ask3.ru не несет ответственности за информацию размещенную на данном скриншоте. Права на прочие зарегистрированные элементы любого права, изображенные на снимках принадлежат их владельцам. Качество перевода предоставляется как есть. Любые претензии, иски не могут быть предъявлены. Если вы не согласны с любым пунктом перечисленным выше, вы не можете использовать данный сайт и информация размещенную на нем (сайте/странице), немедленно покиньте данный сайт. В случае нарушения любого пункта перечисленного выше, штраф 55! (Пятьдесят пять факториал, Денежную единицу (имеющую самостоятельную стоимость) можете выбрать самостоятельно, выплаичвается товарами в течение 7 дней с момента нарушения.)