Арифметическая иерархия - Arithmetical hierarchy

Иллюстрация того, как взаимодействуют уровни иерархии и где в ней находятся некоторые основные категории.

В математической логике , в арифметической иерархии , арифметической иерархии или иерархии Клини-Мостовской (после того, как математика Клини и Анджей Мостовский ) классифицирует определенные наборы , основанные на сложностях формул , которые определяют их. Любой набор, получивший классификацию, называется арифметическим .

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

Алгоритм Тарского Kuratowski обеспечивает легкий способ получить верхнюю границу на классификации , присвоенной формулу и множества его определяет.

Гиперарифметическая иерархия и аналитическая иерархия расширить арифметическую иерархию для классификации дополнительных формул и множеств.

Арифметическая иерархия формул

Арифметическая иерархия классифицирует формулы на языке арифметики первого порядка . Обозначены классификации и для натуральных чисел n (включая 0). Греческие буквы здесь - это световые символы, что означает, что формулы не содержат заданных параметров. ${\ displaystyle \ Sigma _ {n} ^ {0}}$${\ Displaystyle \ Пи _ {п} ^ {0}}$

Если формула логически эквивалентна формуле только с ограниченными кванторами, то ей присваиваются классификации и . ${\ displaystyle \ phi}$${\ displaystyle \ phi}$${\ displaystyle \ Sigma _ {0} ^ {0}}$${\ displaystyle \ Pi _ {0} ^ {0}}$

Классификации и определяются индуктивно для каждого натурального числа n с использованием следующих правил: ${\ displaystyle \ Sigma _ {n} ^ {0}}$${\ Displaystyle \ Пи _ {п} ^ {0}}$

• Если логически эквивалентна формуле вида , где есть , то присваивается классификация .${\ displaystyle \ phi}$${\ Displaystyle \ существует м_ {1} \ существует м_ {2} \ cdots \ существует м_ {к} \ psi}$${\ displaystyle \ psi}$${\ Displaystyle \ Пи _ {п} ^ {0}}$${\ displaystyle \ phi}$${\ Displaystyle \ Sigma _ {п + 1} ^ {0}}$
• Если логически эквивалентна формуле вида , где есть , то присваивается классификация .${\ displaystyle \ phi}$${\ Displaystyle \ forall m_ {1} \ forall m_ {2} \ cdots \ forall m_ {k} \ psi}$${\ displaystyle \ psi}$${\ displaystyle \ Sigma _ {n} ^ {0}}$${\ displaystyle \ phi}$${\ Displaystyle \ Пи _ {п + 1} ^ {0}}$

Формула эквивалентна формуле , которая начинается с некоторыми кванторами существования и заместители раз между сериями экзистенциальных и универсальных кванторов ; в то время как формула эквивалентна формуле, которая начинается с некоторых универсальных кванторов и чередуется аналогичным образом. ${\ displaystyle \ Sigma _ {n} ^ {0}}$${\ displaystyle n-1}$${\ Displaystyle \ Пи _ {п} ^ {0}}$

Поскольку каждая формула первого порядка имеет предваренную нормальную форму , каждой формуле назначается по крайней мере одна классификация. Поскольку избыточные кванторы могут быть добавлены к любой формуле, как только формуле будет присвоена классификация, или ей будут назначены классификации и для каждого r> n . Таким образом, единственной релевантной классификацией, присваиваемой формуле, является класс с наименьшим n ; все остальные классификации могут быть определены из него. ${\ displaystyle \ Sigma _ {n} ^ {0}}$${\ Displaystyle \ Пи _ {п} ^ {0}}$${\ displaystyle \ Sigma _ {r} ^ {0}}$${\ displaystyle \ Pi _ {r} ^ {0}}$

Арифметическая иерархия множеств натуральных чисел

Множество натуральных чисел X определяется формулой φ в языке арифметики Пеано (язык первого порядка с символами «0» для нуля, «S» для функции-преемника, «+» для сложения, «×» для умножения , и "=" для равенства), если элементы X - это в точности числа, удовлетворяющие φ. То есть, для всех натуральных чисел п ,

${\ displaystyle n \ in X \ Leftrightarrow \ mathbb {N} \ models \ varphi ({\ underline {n}}),}$

где - число на языке арифметики, соответствующее . Множество определимо в арифметике первого порядка, если оно определяется некоторой формулой на языке арифметики Пеано. ${\ displaystyle {\ underline {n}}}$${\ displaystyle n}$

Каждый набор Х натуральных чисел , что определимо в арифметиках первого порядка присваиваются классификация формы , и , где это натуральное число, следующим образом . Если X определяется формулой, то X присваивается классификация . Если X определяется формулой, то X присваивается классификация . Если X равно и то и другое, то ему назначается дополнительная классификация . ${\ displaystyle \ Sigma _ {n} ^ {0}}$${\ Displaystyle \ Пи _ {п} ^ {0}}$${\ displaystyle \ Delta _ {n} ^ {0}}$${\ displaystyle n}$${\ displaystyle \ Sigma _ {n} ^ {0}}$${\ displaystyle \ Sigma _ {n} ^ {0}}$${\ Displaystyle \ Пи _ {п} ^ {0}}$${\ Displaystyle \ Пи _ {п} ^ {0}}$${\ displaystyle \ Sigma _ {n} ^ {0}}$${\ Displaystyle \ Пи _ {п} ^ {0}}$${\ displaystyle X}$${\ displaystyle \ Delta _ {n} ^ {0}}$

Обратите внимание, что редко имеет смысл говорить о формулах; первый квантор формулы либо экзистенциальный, либо универсальный. Итак, набор не определяется формулой; скорее, есть и те и другие формулы, которые определяют набор. Например, набор нечетных натуральных чисел определяется либо, либо . ${\ displaystyle \ Delta _ {n} ^ {0}}$${\ displaystyle \ Delta _ {n} ^ {0}}$${\ displaystyle \ Delta _ {n} ^ {0}}$${\ displaystyle \ Sigma _ {n} ^ {0}}$${\ Displaystyle \ Пи _ {п} ^ {0}}$${\ displaystyle n}$${\ Displaystyle \ forall к (п \ neq 2 \ раз к)}$${\ Displaystyle \ существует к (п = 2 \ раз к + 1)}$

Параллельное определение используется для определения арифметической иерархии конечных декартовых степеней множества натуральных чисел. Вместо формул с одной свободной переменной используются формулы с k свободными числовыми переменными для определения арифметической иерархии на наборах k - наборов натуральных чисел. На самом деле они связаны с помощью функции сопряжения .

Релятивизированные арифметические иерархии

Подобно тому , как мы можем определить , что это значит для множества X быть рекурсивными относительно другого множество Y , позволяя вычисление , определяющее X проконсультироваться Y в качестве оракула , мы можем распространить это понятие на всю арифметическую иерархию и определить , что значит для X в быть , или в Y , обозначаемые соответственно и . Для этого зафиксируйте набор целых чисел Y и добавьте предикат членства в Y в язык арифметики Пеано. Затем мы говорим, что X находится внутри, если он определен формулой на этом расширенном языке. Другими словами, X есть , если она определяется формулой разрешено задавать вопросы о членстве в Y . В качестве альтернативы можно рассматривать наборы как те наборы, которые могут быть построены, начиная с наборов, рекурсивных по Y, и поочередно принимая объединения и пересечения этих наборов до n раз. ${\ displaystyle \ Sigma _ {n} ^ {0}}$${\ displaystyle \ Delta _ {n} ^ {0}}$${\ Displaystyle \ Пи _ {п} ^ {0}}$${\ displaystyle \ Sigma _ {n} ^ {0, Y}}$ ${\ displaystyle \ Delta _ {n} ^ {0, Y}}$${\ displaystyle \ Pi _ {n} ^ {0, Y}}$${\ displaystyle \ Sigma _ {n} ^ {0, Y}}$${\ displaystyle \ Sigma _ {n} ^ {0}}$${\ displaystyle \ Sigma _ {n} ^ {0, Y}}$${\ displaystyle \ Sigma _ {n} ^ {0}}$${\ displaystyle \ Sigma _ {n} ^ {0, Y}}$

Например, пусть Y будет набором целых чисел. Пусть X будет набором чисел, делящихся на элемент Y. Тогда X определяется формулой, так что X находится в (на самом деле он также входит, поскольку мы могли бы связать оба квантора с помощью n). ${\ Displaystyle \ фи (п) = \ существует м \ существует т (Y (м) \ земля м \ раз т = п)}$${\ displaystyle \ Sigma _ {1} ^ {0, Y}}$${\ displaystyle \ Delta _ {0} ^ {0, Y}}$

Арифметическая сводимость и степени

Арифметическая сводимость - это промежуточное понятие между сводимостью по Тьюрингу и гиперарифметической сводимостью .

Набор является арифметическим (также арифметическим и арифметически определимым ), если он определяется некоторой формулой на языке арифметики Пеано. Эквивалентно X является арифметическим, если X равно или для некоторого целого числа n . Множество Х является арифметической в множестве Y , обозначаются , если Х определят , как некоторая формула на языке арифметики Пеано продлена предикатом на членство в Y . Эквивалентно, X является арифметическим по Y, если X находится в или для некоторого целого числа n . Синоним является: X является арифметический сводим к Y . ${\ displaystyle \ Sigma _ {n} ^ {0}}$${\ Displaystyle \ Пи _ {п} ^ {0}}$ ${\ Displaystyle X \ leq _ {A} Y}$${\ displaystyle \ Sigma _ {n} ^ {0, Y}}$${\ displaystyle \ Pi _ {n} ^ {0, Y}}$${\ Displaystyle X \ leq _ {A} Y}$

Отношение рефлексивно и транзитивно, поэтому отношение определяется правилом ${\ Displaystyle X \ leq _ {A} Y}$${\ Displaystyle \ Equiv _ {A}}$

${\ Displaystyle X \ Equiv _ {A} Y \ Leftrightarrow X \ leq _ {A} Y \ land Y \ leq _ {A} X}$

является отношением эквивалентности. Классы эквивалентности этого отношения называются арифметическими степенями ; они частично заказаны под . ${\ displaystyle \ leq _ {A}}$

Арифметическая иерархия подмножеств пространства Кантора и Бэра

Канторовым пространство , обозначается , есть множество всех бесконечных последовательностей 0 и 1; бэровский , обозначаются или , есть множество всех бесконечных последовательностей натуральных чисел. Обратите внимание, что элементы пространства Кантора можно отождествить с наборами целых чисел, а элементы пространства Бэра - с функциями от целых до целых чисел. ${\ displaystyle 2 ^ {\ omega}}$${\ displaystyle \ omega ^ {\ omega}}$${\ Displaystyle {\ mathcal {N}}}$

Обычная аксиоматизация арифметики второго порядка использует язык, основанный на множествах, в котором кванторы множеств естественным образом могут рассматриваться как количественные в пространстве Кантора. Подмножеству пространства Кантора присваивается классификация, если оно определяется формулой. Набору присваивается классификация, если она определяется формулой. Если набор как и тогда дается дополнительная классификация . Например, пусть будет набор всех бесконечных двоичных строк, которые не все 0 (или, что эквивалентно, набор всех непустых наборов целых чисел). Как мы видим, это определяется формулой и, следовательно, является набором. ${\ displaystyle \ Sigma _ {n} ^ {0}}$${\ displaystyle \ Sigma _ {n} ^ {0}}$${\ Displaystyle \ Пи _ {п} ^ {0}}$${\ Displaystyle \ Пи _ {п} ^ {0}}$${\ displaystyle \ Sigma _ {n} ^ {0}}$${\ Displaystyle \ Пи _ {п} ^ {0}}$${\ displaystyle \ Delta _ {n} ^ {0}}$${\ Displaystyle О \ подмножество 2 ^ {\ omega}}$${\ displaystyle O = \ {X \ in 2 ^ {\ omega} | \ существует n (X (n) = 1) \}}$${\ displaystyle O}$${\ displaystyle \ Sigma _ {1} ^ {0}}$${\ displaystyle \ Sigma _ {1} ^ {0}}$

Обратите внимание, что хотя элементы пространства Кантора (рассматриваемые как наборы целых чисел) и подмножества пространства Кантора классифицируются в арифметических иерархиях, это не одна и та же иерархия. На самом деле отношения между двумя иерархиями интересны и нетривиальны. Например, элементы пространства Кантора (в общем случае) не такие же, как элементы пространства Кантора, так что это подмножество пространства Кантора. Однако есть много интересных результатов, касающихся двух иерархий. ${\ Displaystyle \ Пи _ {п} ^ {0}}$${\ displaystyle X}$${\ displaystyle \ {X \}}$${\ Displaystyle \ Пи _ {п} ^ {0}}$

Существует два способа классификации подмножества пространства Бэра в арифметической иерархии.

• Подмножество пространства Бэра имеет соответствующее подмножество Cantor пространства при отображении , который принимает каждую функцию из , чтобы к характеристической функции ее графа. Подмножеству пространства Бэра дается классификация , или тогда и только тогда, когда соответствующее подмножество пространства Кантора имеет ту же классификацию.${\ displaystyle \ omega}$${\ displaystyle \ omega}$${\ Displaystyle \ Sigma _ {п} ^ {1}}$${\ Displaystyle \ Пи _ {п} ^ {1}}$${\ displaystyle \ Delta _ {n} ^ {1}}$
• Эквивалентное определение аналитической иерархии в пространстве Бэра дается путем определения аналитической иерархии формул с использованием функциональной версии арифметики второго порядка; тогда аналитическая иерархия на подмножествах пространства Кантора может быть определена из иерархии на пространстве Бэра. Это альтернативное определение дает точно такие же классификации, как и первое определение.

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

Обратите внимание, что мы также можем определить арифметическую иерархию подмножеств пространств Кантора и Бэра относительно некоторого набора целых чисел. На самом деле полужирный только объединение всех множеств целых чисел Y . Обратите внимание, что иерархия, выделенная жирным шрифтом, - это просто стандартная иерархия борелевских множеств . ${\ Displaystyle \ mathbf {\ Sigma} _ {п} ^ {0}}$${\ displaystyle \ Sigma _ {n} ^ {0, Y}}$

Расширения и вариации

Можно определить арифметическую иерархию формул, используя язык, расширенный функциональным символом для каждой примитивной рекурсивной функции . Этот вариант немного меняет классификацию , поскольку использование примитивных рекурсивных функций в арифметике Пеано первого порядка требует, как правило, неограниченного экзистенциального квантора, и, таким образом, некоторые множества, которые входят в это определение, входят в определение, данное в начале этого статья. и, таким образом, все более высокие классы в иерархии остаются неизменными. ${\ displaystyle \ Sigma _ {0} ^ {0} = \ Pi _ {0} ^ {0} = \ Delta _ {0} ^ {0}}$${\ displaystyle \ Sigma _ {0} ^ {0}}$${\ displaystyle \ Sigma _ {1} ^ {0}}$${\ displaystyle \ Sigma _ {1} ^ {0}}$

Более семантическая вариация иерархии может быть определена для всех конечных отношений натуральных чисел; используется следующее определение. Каждое вычислимое отношение определяется как . Классификации и определяются индуктивно по следующим правилам. ${\ displaystyle \ Sigma _ {0} ^ {0} = \ Pi _ {0} ^ {0} = \ Delta _ {0} ^ {0}}$${\ displaystyle \ Sigma _ {n} ^ {0}}$${\ Displaystyle \ Пи _ {п} ^ {0}}$

• Если отношение , то отношение определяется как${\ Displaystyle R (п_ {1}, \ ldots, n_ {l}, m_ {1}, \ ldots, m_ {k}) \,}$${\ displaystyle \ Sigma _ {n} ^ {0}}$${\ displaystyle S (n_ {1}, \ ldots, n_ {l}) = \ forall m_ {1} \ cdots \ forall m_ {k} R (n_ {1}, \ ldots, n_ {l}, m_ { 1}, \ ldots, m_ {k})}$${\ Displaystyle \ Пи _ {п + 1} ^ {0}}$
• Если отношение , то отношение определяется как${\ Displaystyle R (п_ {1}, \ ldots, n_ {l}, m_ {1}, \ ldots, m_ {k}) \,}$${\ Displaystyle \ Пи _ {п} ^ {0}}$${\ Displaystyle S (п_ {1}, \ ldots, n_ {l}) = \ существует m_ {1} \ cdots \ exists m_ {k} R (n_ {1}, \ ldots, n_ {l}, m_ { 1}, \ ldots, m_ {k})}$${\ Displaystyle \ Sigma _ {п + 1} ^ {0}}$

Этот вариант немного меняет классификацию некоторых наборов. В частности, как класс множеств (определяемых отношениями в классе) идентичен тому, как последний был определен ранее. Его можно расширить, чтобы охватить финитарные отношения в натуральных числах, пространстве Бэра и пространстве Кантора. ${\ displaystyle \ Sigma _ {0} ^ {0} = \ Pi _ {0} ^ {0} = \ Delta _ {0} ^ {0}}$${\ displaystyle \ Delta _ {1} ^ {0}}$

Значение обозначений

Обозначению арифметической иерархии формул можно придать следующие значения.

Нижний индекс в символах и указывает количество чередований блоков кванторов универсальных и экзистенциальных чисел, которые используются в формуле. Более того, самый внешний блок экзистенциальный в формулах и универсальный в формулах. ${\ displaystyle n}$${\ displaystyle \ Sigma _ {n} ^ {0}}$${\ Displaystyle \ Пи _ {п} ^ {0}}$${\ displaystyle \ Sigma _ {n} ^ {0}}$${\ Displaystyle \ Пи _ {п} ^ {0}}$

Верхний индекс в символах , и указывает на тип объектов, по которым проводится количественная оценка. Объекты типа 0 - это натуральные числа, а объекты типа - это функции, которые сопоставляют набор объектов типа с натуральными числами. Количественная оценка объектов более высокого типа, таких как функции от натуральных чисел до натуральных чисел, описывается надстрочным индексом больше 0, как в аналитической иерархии . Верхний индекс 0 указывает кванторы над числами, верхний индекс 1 будет указывать количественную оценку функций от чисел к числам (объекты типа 1), верхний индекс 2 будет соответствовать количественной оценке функций, которые принимают объект типа 1 и возвращают число, и так далее. ${\ displaystyle 0}$${\ displaystyle \ Sigma _ {n} ^ {0}}$${\ Displaystyle \ Пи _ {п} ^ {0}}$${\ displaystyle \ Delta _ {n} ^ {0}}$${\ displaystyle i + 1}$${\ displaystyle i}$

Примеры

• Эти наборы чисел являются те , определяемой формулой вида , где имеют только ограниченные кванторы. Это в точности рекурсивно перечислимые множества .${\ displaystyle \ Sigma _ {1} ^ {0}}$${\ Displaystyle \ существует n_ {1} \ cdots \ exists n_ {k} \ psi (n_ {1}, \ ldots, n_ {k}, m)}$${\ displaystyle \ psi}$
• Набор натуральных чисел, которые являются индексами машин Тьюринга, вычисляющих общие функции, равен . Интуитивно, индекс попадает в этот набор тогда и только тогда, когда для каждого «существует такое, что машина Тьюринга с индексом останавливается при вводе после шагов». Полное доказательство показало бы, что свойство, показанное в кавычках в предыдущем предложении, может быть определено в язык арифметики Пеано формулой.${\ displaystyle \ Pi _ {2} ^ {0}}$${\ displaystyle e}$${\ displaystyle m}$${\ displaystyle s}$${\ displaystyle e}$${\ displaystyle m}$${\ displaystyle s}$${\ displaystyle \ Sigma _ {1} ^ {0}}$
• Каждое подмножество пространства Бэра или пространства Кантора является открытым множеством в обычной топологии на пространстве. Более того, для любого такого множества существует вычислимая нумерация гёделевских чисел основных открытых множеств, объединение которых является исходным множеством. По этой причине наборы иногда называют фактически открытыми . Точно так же каждое множество замкнуто, и множества иногда называют эффективно замкнутыми .${\ displaystyle \ Sigma _ {1} ^ {0}}$${\ displaystyle \ Sigma _ {1} ^ {0}}$${\ displaystyle \ Pi _ {1} ^ {0}}$${\ displaystyle \ Pi _ {1} ^ {0}}$
• Каждое арифметическое подмножество пространства Кантора или пространства Бэра является борелевским множеством . Иерархия Lightface Borel расширяет арифметическую иерархию за счет включения дополнительных наборов Borel. Например, каждое подмножество пространства Кантора или Бэра является набором (то есть набором, который равен пересечению счетного числа открытых множеств). Более того, каждое из этих открытых множеств есть, и список гёделевских чисел этих открытых множеств имеет вычислимое перечисление. Если это формула со свободным набором переменной X и свободными числовыми переменными, то набор является пересечением множеств формы, поскольку n пробегает множество натуральных чисел.${\ displaystyle \ Pi _ {2} ^ {0}}$${\ displaystyle G _ {\ delta}}$${\ displaystyle \ Sigma _ {1} ^ {0}}$${\ Displaystyle \ фи (Х, п, м)}$${\ displaystyle \ Sigma _ {0} ^ {0}}$${\ displaystyle n, m}$${\ displaystyle \ Pi _ {2} ^ {0}}$${\ displaystyle \ {X \ mid \ forall n \ существует m \ phi (X, n, m) \}}$${\ displaystyle \ Sigma _ {1} ^ {0}}$${\ Displaystyle \ {Икс \ середина \ существует м \ фи (Х, п, м) \}}$
• Эти формулы могут быть проверены при переходе всех случаях один за другим, что возможно , так как все их кванторы ограничены. Время для этого полиномиально по их аргументам (например, полиномиально от n для ); таким образом, соответствующие им проблемы решения включены в E (поскольку n экспоненциально по количеству битов). Это больше не выполняется при альтернативных определениях , которые позволяют использовать примитивные рекурсивные функции, поскольку теперь кванторы могут быть связаны любой примитивно рекурсивной функцией аргументов.${\ displaystyle \ Sigma _ {0} ^ {0} = \ Pi _ {0} ^ {0} = \ Delta _ {0} ^ {0}}$${\ Displaystyle \ varphi (п)}$${\ displaystyle \ Sigma _ {0} ^ {0} = \ Pi _ {0} ^ {0} = \ Delta _ {0} ^ {0}}$
• В формулах под альтернативным определением, что позволяет использовать примитивные рекурсивные функции с ограниченными кванторами, соответствуют наборам целых чисел вида для примитивной рекурсивной функции F . Это происходит потому , что позволяет ограниченный квантор не добавляет ничего к определению: для примитивно рекурсивной F , такое же , как и то же ; с рекурсией курса значений каждый из них может быть определен одной простой функцией рекурсии.${\ displaystyle \ Sigma _ {0} ^ {0} = \ Pi _ {0} ^ {0} = \ Delta _ {0} ^ {0}}$${\ Displaystyle \ {п: е (п) = 0 \}}$${\ displaystyle \ forall k <n: f (k) = 0}$${\ Displaystyle f (0) + f (1) + ... f (n) = 0}$${\ Displaystyle \ существует к <n: f (k) = 0}$${\ Displaystyle f (0) * f (1) * ... f (n) = 0}$

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

Следующие свойства имеют место для арифметической иерархии множеств натуральных чисел и арифметической иерархии подмножеств пространства Кантора или Бэра.

• Наборы и замкнуты относительно конечных объединений и конечных пересечений соответствующих им элементов.${\ Displaystyle \ Пи _ {п} ^ {0}}$${\ displaystyle \ Sigma _ {n} ^ {0}}$
• Набор есть тогда и только тогда, когда его дополнение есть . Набор есть тогда и только тогда, когда набор одновременно и , и в этом случае его дополнение также будет .${\ displaystyle \ Sigma _ {n} ^ {0}}$${\ Displaystyle \ Пи _ {п} ^ {0}}$${\ displaystyle \ Delta _ {n} ^ {0}}$${\ displaystyle \ Sigma _ {n} ^ {0}}$${\ Displaystyle \ Пи _ {п} ^ {0}}$${\ displaystyle \ Delta _ {n} ^ {0}}$
• Включения и держи для всех . Таким образом иерархия не рушится. Это прямое следствие теоремы Поста .${\ Displaystyle \ Пи _ {п} ^ {0} \ subsetneq \ Пи _ {п + 1} ^ {0}}$${\ displaystyle \ Sigma _ {n} ^ {0} \ subsetneq \ Sigma _ {n + 1} ^ {0}}$${\ displaystyle n}$
• Включения , и удержания для .${\ displaystyle \ Delta _ {n} ^ {0} \ subsetneq \ Pi _ {n} ^ {0}}$${\ displaystyle \ Delta _ {n} ^ {0} \ subsetneq \ Sigma _ {n} ^ {0}}$${\ displaystyle \ Sigma _ {n} ^ {0} \ cup \ Pi _ {n} ^ {0} \ subsetneq \ Delta _ {n + 1} ^ {0}}$${\ Displaystyle п \ geq 1}$

• Например, для универсальной машины Тьюринга T, множество пар (п, т) , такие , что Т останавливается на п , но не от т, в (будучи вычислимо с оракулом к проблемам остановки) , но не в ,.${\ displaystyle \ Delta _ {2} ^ {0}}$${\ displaystyle \ Sigma _ {1} ^ {0} \ cup \ Pi _ {1} ^ {0}}$
• ${\ Displaystyle \ Sigma _ {0} ^ {0} = \ Pi _ {0} ^ {0} = \ Delta _ {0} ^ {0} = \ Sigma _ {0} ^ {0} \ cup \ Pi _ {0} ^ {0} \ subset \ Delta _ {1} ^ {0}}$. Включение строгое по определению, данному в этой статье, но тождество с выполняется при одном из вариантов определения, данного выше .${\ displaystyle \ Delta _ {1} ^ {0}}$

Отношение к машинам Тьюринга

Вычислимые множества

Если S - вычислимое множество по Тьюрингу , то и S, и его дополнение рекурсивно перечислимы (если T - машина Тьюринга, дающая 1 для входных данных в S и 0, в противном случае мы можем построить машину Тьюринга, останавливающуюся только на первом, а другую останавливающуюся только на последнем).

По теореме Поста и S, и его дополнение находятся в . Это означает, что S находится как внутри, так и внутри , а значит, и внутри . ${\ displaystyle \ Sigma _ {1} ^ {0}}$${\ displaystyle \ Sigma _ {1} ^ {0}}$${\ displaystyle \ Pi _ {1} ^ {0}}$${\ displaystyle \ Delta _ {1} ^ {0}}$

Аналогично, для каждого множества S in как S, так и его дополнение входят в и, следовательно, (по теореме Поста ) рекурсивно перечисляются некоторыми машинами Тьюринга T ₁ и T ₂ соответственно. Для каждого числа n ровно одна из этих остановок. Поэтому мы можем построить машину Тьюринга T, которая чередуется между T ₁ и T ₂ , останавливаясь и возвращая 1, когда первая останавливается, или останавливается и возвращает 0, когда последняя останавливается. Таким образом, T останавливается на каждом n и возвращает, находится ли он в S, поэтому S вычислим. ${\ displaystyle \ Delta _ {1} ^ {0}}$${\ displaystyle \ Sigma _ {1} ^ {0}}$

Резюме основных результатов

Вычислимые по Тьюрингу наборы натуральных чисел - это в точности наборы на уровне арифметической иерархии. Рекурсивно перечислимые множества - это в точности множества на уровне . ${\ displaystyle \ Delta _ {1} ^ {0}}$${\ displaystyle \ Sigma _ {1} ^ {0}}$

Ни одна машина-оракул не способна решить свою собственную проблему остановки (применима разновидность доказательства Тьюринга). На самом деле проблема остановки для оракула заключается в этом . ${\ displaystyle \ Delta _ {n} ^ {0, Y}}$${\ Displaystyle \ Sigma _ {п + 1} ^ {0, Y}}$

Теорема Поста устанавливает тесную связь между арифметической иерархией множеств натуральных чисел и степенями Тьюринга . В частности, он устанавливает следующие факты для всех n ≥ 1:

• Множество ( n- й прыжок Тьюринга пустого множества) завершено в несколько единиц .${\ Displaystyle \ emptyset ^ {(п)}}$${\ displaystyle \ Sigma _ {n} ^ {0}}$
• Набор много-один комплектный .${\ Displaystyle \ mathbb {N} \ setminus \ emptyset ^ {(п)}}$${\ Displaystyle \ Пи _ {п} ^ {0}}$
• Набор является полным по Тьюрингу .${\ Displaystyle \ emptyset ^ {(п-1)}}$${\ displaystyle \ Delta _ {n} ^ {0}}$

Полином иерархия является «выполним ресурсами ограничены» версией арифметической иерархии , в которой длина граница полиномиальной размещена на номерах участвующих (или, что эквивалентно, полиномиальные оценки времени помещается на тьюринговых машинах , участвующих). Он дает более тонкую классификацию некоторых наборов натуральных чисел, находящихся на уровне арифметической иерархии. ${\ displaystyle \ Delta _ {1} ^ {0}}$

Отношение к другим иерархиям

Смотрите также

• Иерархия Леви
• Иерархия (математика)
• Логика интерпретируемости
• Полиномиальная иерархия

использованная литература