Доказательство. Если M сопряжено с a, то N \ M сопряжено с Øa. чтд

Свойство 2. Объединение и пересечение арифметических множеств суть арифметические множества.

Доказательство. Если M сопряжено с a, N сопряжено с b, то MÇN сопряжено с aÙb, MÈN сопряжено с aÚb. чтд

Свойство 3. Арифметическое множество выразимо множеством истин арифметики.

Доказательство. Пусть M сопряжено с a, определим F: N® bool следующим образом: F (x):= a(x). чтд

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

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

Принятая аксиома позволяет в несколько шагов закончить доказательство первой теоремы Гёделя о неполноте.

Шаг 1. Существует неперечислимое арифметическое множество.

Доказательство. Рассмотрим множество N, построенное в доказательстве следствия 5 п. 4.4'.6. Это множество перечислимо и имеет неперечислимое дополнение по следствию 6. Но само множество N арифметическое по аксиоме арифметичности и его дополнение арифметично по свойству 1. чтд

Шаг 2. Существует непечислимое множество, выразимое множеством истин арифметики.