10.4. Теоремы Тарского и Гёделя

Поскольку графики вычислимых функций арифме-тичны, очевидно, разрешимые и перечислимые множе­ства тоже будут арифметическими. Тем самым мы мо­жем оправдать название «арифметическая иерархия» для классов £„ и П„:

Теорема 68. При любом п любое множество из клас­са £„ или П„ арифметично (есть формула арифметики, выражающая принадлежность этому множеству).

<] После того, как мы доказали арифметичность вы­числимых функций, всё ясно — множества из классов £„ и П„ получаются навешиванием кванторов на разреши­мые множества, а разрешимое множество арифметич­но. >

Верно и обратное:

Теорема 69. Всякое арифметическое множество лежит в классе £„ или П„ для некоторого п (и, естественно, для всех больших п).

Теоремы Тарского и Гёдеяя

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

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

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

Теорема 70. Любое арифметическое множество т-сво-дится к множеству Т.

<] Это утверждение почти очевидно. Пусть А — про­извольное арифметическое множество. Пусть а(х) — формула с одной переменной, которая выражает принад­лежность множеству А. Это означает, что а(п) истинно при тех и только тех п, которые принадлежат А. То­гда вычислимая функция п н->- (номер формулы, которая является результатом подстановки константы п в а(х)) m-сводит А к Т. >

Теорема 71. Множество Т не арифметично.

<] После проведённой нами подготовки это утвержде­ние очевидно: если бы Т было арифметическим, то оно лежало бы в некотором конкретном классе £„. Посколь­ку всякое арифметическое множество сводится к Т, то по теореме 53 все арифметические множества лежали бы в этом классе. Но мы знаем, что множества из более вы­соких классов иерархии тоже арифметичны, но в £„ не лежат. >

Эта теорема называется теоремой Тарского. Её мож­но прочесть так: множество арифметических истин не арифметично. Или: понятие арифметической истины не­выразимо в арифметике.

Теорема 72. Множество Т арифметических истин нс-персчислимо.

<] В самом доле, любое псрсчислимос множество ариф-мстично. >

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

84. Покажите, что для любого N множество всех истинных замкнутых арифметических формул, содержащих не более N кванторов, арифметично.

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