10.6. Арифметическая иерархия и число перемен кванторов

Мы установили, что класс арифметических множеств есть объединение всех классов £„ и П„. Посмотрим по­дробнее, как связан номер класса с числом перемен кван­торов в арифметической формуле.

Чтобы сделать это, надо уточнить, какие формулы мы считаем бескванторными. Если представлять сложе­ние и умножение предикатными символами, то бескван­торные формулы будут логическими комбинациями фор­мул Х{ + Xj = Xk и Х{ х Xj = Xk] при этом уже для записиформулы а + Ь + с = ё нам понадобится квантор: она за­писывается как Зы((а -\- Ь = и) А (и -\- с = а1)). Мы же, как это обычно делается, будем считать сложение и умно­жение функциональными символами и тем самым разре­шим использовать произвольные многочлены с целыми коэффициентами в бескванторных формулах. При этом бескванторными формулами будут логические комбина­ции выражений вида Р = <5, где Р и <5 — произвольные многочлены с целыми коэффициентами. Тогда верна та­кая теорема:

Теорема 73. Множество А С N принадлежит клас­су £„ (п ^ 1) тогда и только тогда, когда принадлеж­ность ему выражается формулой в предварённой нор­мальной форме, начинающейся с квантора существова­ния и содержащей п групп одноимённых кванторов.

(Переходя к дополнению, видим, что множество при­надлежит классу П„ тогда и только тогда, когда при­надлежность ему выражается в предварённой нормаль­ной форме с п группами одноимённых кванторов, начи­нающейся с квантора всеобщности.)

<] Мы докажем эту теорему лишь отчасти. Во-пер­вых, если множество задаётся формулой в предварённой нормальной форме с п группами кванторов, то оно при­надлежит классу £„ (или П„ — в зависимости от того, какой квантор первый) — напомним, что к подряд иду­щих одноимённых кванторов можно заменить на один с помощью вычислимой биекции между      и N.

Более сложно доказать обратное утверждение. Основ­ную трудность представляет случай п = 1. В 1970 году Ю. В. Матияссвич, решая 10-ю проблему Гильберта, по­казал, что всякое псрсчислимос множество есть множест­во неотрицательных значений многочлена от нескольких переменных с целыми коэффициентами при натуральных значениях переменных. А это свойство, очевидно, запи­сывается в виде формулы с кванторной приставкой из кванторов существования. Тем самым случай п = 1 был разобран.

Если считать результат Матияссвича известным, то доказательство заканчивается, поскольку каждый следу­ющии класс получается из предыдущего навешиванием очередного квантора.

Посмотрим, однако, что можно извлечь из приведён­ного нами доказательства арифметичности вычислимых функций. Пусть дано произвольное псрсчислимос мно­жество. Его можно представить как область определе­ния вычислимой функции, все значения которой равны нулю, и применить описанную нами процедуру. Тогда по­лучится формула, начинающаяся с кванторов существо­вания (существуют числа, кодирующие последовательно­сти значений каждой переменной в смысле /3-кодирова­ния по Гёдслю). Затем идёт квантор всеобщности (по номеру шага работы программы: на каждом шаге пе­реход должен соответствовать программе). Затем идёт формула, которая была бы бескванторной, если бы не со­держала в себе остатков от деления одного выражения на другое. Но их можно устранить, добавив ещё кванторы всеобщности: утверждение типа

У г [... остаток от деления Р на <5 ... ],

где Р и <5 — некоторые выражения, содержащие пере­менные (из определения /3-кодирования) можно заменить по определению остатка на

Уг'У«Уг> [(Р = и0 + г«) Л (г« < 0)} => [.. ,г«...].

Следовательно, мы можем представить любое псрсчисли­мос множество в виде 3 .. .ЗУ .. .У-формулы. Тем самым любое множество из класса £„ можно представить фор­мулой в предварённой нормальной форме с п + 1 груп­пами кванторов, начинающейся с кванторов существова­ния, а любое множество из класса П„ можно представить формулой с п + 1 группами кванторов, начинающейся с квантора всеобщности. >