Иерархия арифметической сложности формул, определяющих множества

Введение

Иерархия классов сложности для формул, определяющих множества

В математической логике арифметическая иерархия, или иерархия Клейне–Мостовского (названа в честь математиков Стивена Коула Клейне и Анджея Мостовского) классифицирует определенные множества на основе сложности формул, которые их определяют. Любое множество, которому присвоена классификация, называется арифметическим. Арифметическая иерархия была независимо изобретена Клейне (1943) и Мостовским (1946). Арифметическая иерархия играет важную роль в теории вычислимости, эффективной дескриптивной теории множеств и изучении формальных теорий, таких как арифметика Пеано. Алгоритм Тарского–Куратовского предоставляет простой способ получить верхнюю границу для классификаций, присвоенных формуле и определяемому ею множеству. Гиперарифметическая и аналитическая иерархии расширяют арифметическую иерархию для классификации дополнительных формул и множеств.

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

Следующие значения можно придать обозначениям арифметической иерархии формул. Индекс в символах Σ и Π указывает на количество чередований блоков универсальных и экзистенциальных кванторов первого порядка, используемых в формуле. При этом, внешний блок экзистенциальный в формулах Σ и универсальный в формулах Π. Верхний индекс в символах Σ₀, Π₀ и Σₙ указывает на тип объектов, над которыми производится квантификация. Объектами типа 0 являются натуральные числа, а объекты типа n+1 – это функции, отображающие множество объектов типа n в натуральные числа. Квантификация над объектами более высокого типа, например, над функциями от натуральных чисел к натуральным числам, описывается верхним индексом, большим 0, как и в аналитической иерархии. Верхний индекс 0 указывает на кванторы над числами, верхний индекс 1 – на квантификацию над функциями от чисел к числам (объектами типа 1), верхний индекс 2 – на квантификацию над функциями, принимающими объект типа 1 и возвращающими число, и так далее.

Примеры

Множества чисел – это множества, определяемые формулой вида, где присутствуют только ограниченные кванторы. Это именно рекурсивно перечислимые множества. Множество натуральных чисел, являющихся индексами машин Тьюринга, вычисляющих тотальные функции, интуитивно понятно, если и только если для каждого "существует такое , что машина Тьюринга с индексом останавливается на входе после шагов". Полное доказательство показало бы, что свойство, заключенное в кавычки в предыдущем предложении, определимо на языке арифметики Пеано формулой . Каждое подмножество пространства Байра или пространства Кантора является открытым множеством в обычной топологии пространства. Более того, для любого такого множества существует вычислимое перечисление чисел Гёделя основных открытых множеств, объединение которых является исходным множеством. По этой причине такие множества иногда называют эффективно открытыми. Аналогично, каждое множество замкнуто, и такие множества иногда называют эффективно замкнутыми. Каждое арифметическое подмножество пространства Кантора или пространства Байра является множеством Бореля. Светлая иерархия Бореля расширяет арифметическую иерархию, включая дополнительные множества Бореля. Например, каждое подмножество пространства Кантора или Байра является множеством, то есть множеством, равным пересечению счетного числа открытых множеств. Более того, каждое из этих открытых множеств вычислимо, и список чисел Гёделя этих открытых множеств имеет вычислимое перечисление. Если есть формула с переменной свободного множества и переменными свободного числа, то множество является пересечением множеств вида, где принимает значения в множестве натуральных чисел. Формулы можно проверить, последовательно перебирая все случаи, что возможно, поскольку все их кванторы ограничены. Время, необходимое для этого, полиномиально относительно их аргументов (например, полиномиально относительно для ); таким образом, соответствующие задачи принятия решений включены в класс E (поскольку число битов экспоненциально относительно их количества). Это больше не верно при альтернативных определениях , допускающих использование примитивных рекурсивных функций, поскольку теперь кванторы могут быть ограничены любой примитивной рекурсивной функцией аргументов. Формулы в рамках альтернативного определения, допускающего использование примитивных рекурсивных функций с ограниченными кванторами, соответствуют множествам натуральных чисел вида для примитивной рекурсивной функции . Это связано с тем, что добавление ограниченного квантора ничего не дает к определению: для примитивной рекурсивной функции , то же самое, что и , а то же самое, что и ; с помощью рекурсии по значениям каждое из этих выражений может быть определено одной примитивной рекурсивной функцией.

The sets of numbers are those definable by a formula of the form where has only bounded quantifiers. These are exactly the recursively enumerable sets. The set of natural numbers that are indices for Turing machines that compute total functions is Intuitively, an index falls into this set if and only if for every "there is an such that the Turing machine with index halts on input after steps". A complete proof would show that the property displayed in quotes in the previous sentence is definable in the language of Peano arithmetic by a formula. Every subset of Baire space or Cantor space is an open set in the usual topology on the space. Moreover, for any such set there is a computable enumeration of Gödel numbers of basic open sets whose union is the original set. For this reason, sets are sometimes called effectively open. Similarly, every set is closed and the sets are sometimes called effectively closed. Every arithmetical subset of Cantor space or Baire space is a Borel set. The lightface Borel hierarchy extends the arithmetical hierarchy to include additional Borel sets. For example, every subset of Cantor or Baire space is a set, that is, a set that equals the intersection of countably many open sets. Moreover, each of these open sets is and the list of Gödel numbers of these open sets has a computable enumeration. If is a formula with a free set variable and free number variables then the set is the intersection of the sets of the form as ranges over the set of natural numbers. The formulas can be checked by going over all cases one by one, which is possible because all their quantifiers are bounded. The time for this is polynomial in their arguments (e. g. polynomial in for ); thus their corresponding decision problems are included in E (as is exponential in its number of bits). This no longer holds under alternative definitions of that allow the use of primitive recursive functions, as now the quantifiers may be bound by any primitive recursive function of the arguments. The formulas under an alternative definition, that allows the use of primitive recursive functions with bounded quantifiers, correspond to sets of natural numbers of the form for a primitive recursive function This is because allowing bounded quantifier adds nothing to the definition: for a primitive recursive , is the same as , and is the same as ; with course of values recursion each of these can be defined by a single primitive recursive function.

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

Множество X натуральных чисел определяется формулой φ на языке арифметики Пеано (язык первого порядка с символами "0" для нуля, "S" для функции следования, "+" для сложения, "×" для умножения и "=" для равенства), если элементы X – это именно те числа, которые удовлетворяют φ. То есть, для всех натуральных чисел n, где – это число в языке арифметики, соответствующее множеству A. Множество определимо в арифметике первого порядка, если оно определено некоторой формулой на языке арифметики Пеано. Каждому множеству X натуральных чисел, определимому в арифметике первого порядка, присваиваются классификации вида , , и , где – натуральное число, следующим образом. Если X определимо -формулой, то X присваивается классификация . Если X определимо -формулой, то X присваивается классификация . Если X является одновременно и , то присваивается дополнительная классификация . Следует отметить, что редко имеет смысл говорить о -формулах; первый квантор формулы либо экзистенциальный, либо универсальный. Таким образом, множество не обязательно определяется -формулой в смысле формулы, которая является одновременно и ; скорее, существуют как -формулы, так и -формулы, определяющие множество. Например, множество нечетных натуральных чисел можно определить либо , либо . Параллельное определение используется для определения арифметической иерархии на конечных декартовых степенях множества натуральных чисел. Вместо формул с одной свободной переменной используются формулы с k свободными переменными первого порядка для определения арифметической иерархии на множествах k-кортежей натуральных чисел. Они фактически связаны посредством использования функции спаривания.

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

Так же, как мы можем определить, что значит для множества X быть рекурсивным относительно другого множества Y, позволяя вычислениям, определяющим X, использовать Y как оракул, мы можем распространить это понятие на всю арифметическую иерархию и определить, что значит для X быть Σn или Πn в Y, обозначаемых соответственно Σn(Y) и Πn(Y). Для этого зафиксируем множество натуральных чисел Y и добавим предикат принадлежности к Y в язык арифметики Пеано. Мы говорим, что X находится в Σn(Y), если он определен формулой Σn в этом расширенном языке. Другими словами, X является Σn в Y, если он определяется формулой Σn, которой разрешено задавать вопросы о принадлежности к Y. Альтернативно, множества Σn(Y) можно рассматривать как те множества, которые могут быть построены, начиная с множеств, рекурсивных в Y, и поочередно беря объединения и пересечения этих множеств до n раз. Например, пусть Y будет множеством натуральных чисел. Пусть X будет множеством чисел, делящихся на элемент из Y. Тогда X определяется формулой, поэтому X находится в Σn(Y) (на самом деле, он также находится в Πn(Y), поскольку мы могли бы ограничить оба квантора n).

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

Пространство Кантора, обозначаемое , представляет собой множество всех бесконечных последовательностей из 0 и 1; пространство Байра, обозначаемое или , представляет собой множество всех бесконечных последовательностей натуральных чисел. Следует отметить, что элементы пространства Кантора могут быть отождествлены с множествами натуральных чисел, а элементы пространства Байра – с функциями из натуральных чисел в натуральные числа. Обычная аксиоматизация арифметики второго порядка использует язык, основанный на множествах, в котором квантификаторы по множествам могут естественным образом рассматриваться как квантификация по пространству Кантора. Подмножеству пространства Кантора присваивается классификация , если оно определимо формулой. Множеству присваивается классификация , если оно определимо формулой. Если множество одновременно и , то ему присваивается дополнительная классификация . Например, пусть будет множеством всех бесконечных двоичных строк, которые не состоят только из нулей (или, эквивалентно, множеством всех непустых множеств натуральных чисел). Как мы видим, это определяется формулой и, следовательно, является -множеством. Следует отметить, что хотя элементы пространства Кантора (рассматриваемые как множества натуральных чисел) и подмножества пространства Кантора классифицируются в арифметических иерархиях, это не одна и та же иерархия. Фактически, связь между этими двумя иерархиями интересна и нетривиальна. Например, элементы пространства Кантора не являются (в общем случае) такими же, как элементы пространства Кантора, поэтому является подмножеством пространства Кантора. Однако многие интересные результаты связывают эти две иерархии. Существует два способа классификации подмножества пространства Байра в арифметической иерархии. Подмножество пространства Байра имеет соответствующее подмножество пространства Кантора посредством отображения, которое переводит каждую функцию из в характеристическую функцию её графа. Подмножеству пространства Байра присваивается классификация , , или тогда и только тогда, когда соответствующее подмножество пространства Кантора имеет ту же классификацию. Эквивалентное определение арифметической иерархии на пространстве Байра дается путем определения арифметической иерархии формул с использованием функциональной версии арифметики второго порядка; затем арифметическая иерархия на подмножествах пространства Кантора может быть определена на основе иерархии на пространстве Байра. Это альтернативное определение дает точно такие же классификации, как и первое определение. Параллельное определение используется для определения арифметической иерархии на конечных декартовых степенях пространства Байра или пространства Кантора, используя формулы с несколькими свободными переменными. Арифметическую иерархию можно определить на любом эффективном польском пространстве; определение особенно просто для пространства Кантора и пространства Байра, поскольку они соответствуют языку обычной арифметики второго порядка. Следует отметить, что мы также можем определить арифметическую иерархию подмножеств пространств Кантора и Байра относительно некоторого множества натуральных чисел. Фактически, полужирный шрифт – это просто объединение для всех множеств натуральных чисел Y. Следует отметить, что полужирная иерархия – это просто стандартная иерархия множеств Бореля.

The Cantor space, denoted , is the set of all infinite sequences of 0s and 1s; the Baire space, denoted or , is the set of all infinite sequences of natural numbers. Note that elements of the Cantor space can be identified with sets of natural numbers and elements of the Baire space with functions from natural numbers to natural numbers. The ordinary axiomatization of second order arithmetic uses a set based language in which the set quantifiers can naturally be viewed as quantifying over Cantor space. A subset of Cantor space is assigned the classification if it is definable by a formula. The set is assigned the classification if it is definable by a formula. If the set is both and then it is given the additional classification For example, let be the set of all infinite binary strings that aren't all 0 (or equivalently the set of all non empty sets of natural numbers). As we see that is defined by a formula and hence is a set. Note that while both the elements of the Cantor space (regarded as sets of natural numbers) and subsets of the Cantor space are classified in arithmetic hierarchies, these are not the same hierarchy. In fact the relationship between the two hierarchies is interesting and non trivial. For instance the elements of the Cantor space are not (in general) the same as the elements of the Cantor space so that is a subset of the Cantor space. However, many interesting results relate the two hierarchies. There are two ways that a subset of Baire space can be classified in the arithmetical hierarchy. A subset of Baire space has a corresponding subset of Cantor space under the map that takes each function from to to the characteristic function of its graph. A subset of Baire space is given the classification , , or if and only if the corresponding subset of Cantor space has the same classification. An equivalent definition of the arithmetical hierarchy on Baire space is given by defining the arithmetical hierarchy of formulas using a functional version of second order arithmetic; then the arithmetical hierarchy on subsets of Cantor space can be defined from the hierarchy on Baire space. This alternate definition gives exactly the same classifications as the first definition. A parallel definition is used to define the arithmetical hierarchy on finite Cartesian powers of Baire space or Cantor space, using formulas with several free variables. The arithmetical hierarchy can be defined on any effective Polish space; the definition is particularly simple for Cantor space and Baire space because they fit with the language of ordinary second order arithmetic. Note that we can also define the arithmetic hierarchy of subsets of the Cantor and Baire spaces relative to some set of natural numbers. In fact boldface is just the union of for all sets of natural numbers Y. Note that the boldface hierarchy is just the standard hierarchy of Borel sets.

Свойства

Следующие свойства выполняются для арифметической иерархии множеств натуральных чисел и арифметической иерархии подмножеств пространства Кантора или пространства Байра. Коллекции Σⁿ и Πⁿ замкнуты относительно конечных объединений и конечных пересечений своих элементов. Множество является Σⁿ, если и только если его дополнение является Πⁿ. Множество является Δⁿ, если и только если оно является одновременно Σⁿ и Πⁿ, в этом случае его дополнение также будет Δⁿ. Включения Σⁿ ⊆ Πⁿ⁺¹ и Πⁿ ⊆ Σⁿ⁺¹ выполняются для всех n. Таким образом, иерархия не схлопывается. Это прямое следствие теоремы Поста. Включения Σⁿ ⊆ Σⁿ⁺¹ и Πⁿ ⊆ Πⁿ⁺¹ и Δⁿ ⊆ Σⁿ⁺¹ выполняются для всех n. Например, для универсальной машины Тьюринга T множество пар (n, m), таких что T останавливается на n, но не останавливается на m, принадлежит Σ¹ (поскольку оно вычислимо с оракулом для задачи остановки), но не принадлежит Π¹. Это включение строго по определению, данному в этой статье, но совпадение с Σ¹ возможно при одном из вариантов определения, приведенных выше.

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

Если S – вычислимое по Тьюрингу множество, то и S, и его дополнение рекурсивно перечислимы (если T – машина Тьюринга, выдающая 1 для входных данных из S и 0 в противном случае, мы можем построить машину Тьюринга, останавливающуюся только на первых, и другую, останавливающуюся только на вторых). По теореме Поста, и S, и его дополнение находятся в . Это означает, что S находится как в , так и в , и, следовательно, оно находится в . Аналогично, для любого множества S из , как S, так и его дополнение находятся в и, следовательно, (по теореме Поста) рекурсивно перечислимы с помощью некоторых машин Тьюринга T1 и T2 соответственно. Для каждого числа n ровно одна из этих машин останавливается. Поэтому мы можем построить машину Тьюринга T, которая поочередно запускает T1 и T2, останавливаясь и возвращая 1, когда первая останавливается, или останавливаясь и возвращая 0, когда останавливается вторая. Таким образом, T останавливается для каждого n и возвращает, принадлежит ли n множеству S; следовательно, S вычислимо.

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

Тьюринговычислимые множества натуральных чисел – это именно множества на уровне арифметической иерархии. Рекурсивно перечислимые множества – это именно множества на уровне. Ни одна машина с оракулом не способна решить свою собственную проблему остановки (применяется вариация доказательства Тьюринга). Проблема остановки для оракула, на самом деле, находится в. Теорема Поста устанавливает тесную связь между арифметической иерархией множеств натуральных чисел и степенями Тьюринга. В частности, она устанавливает следующие факты для всех n ≥ 1: множество (n-й скачок Тьюринга пустого множества) является многими к одному полным в. Множество является многими к одному полным в. Множество является Тьюринговым полным в. Полиномиальная иерархия – это «версия с ограниченными выполнимыми ресурсами» арифметической иерархии, в которой на участвующие числа накладываются полиномиальные ограничения по длине (или, эквивалентно, на участвующие машины Тьюринга накладываются полиномиальные ограничения по времени). Она дает более детальную классификацию некоторых множеств натуральных чисел, находящихся на уровне арифметической иерархии.