Доказательство. Действительно, множество теорем P любой дедуктики перечислимо, а потому не может совпадать с неперечислимым множеством истин T. чтд

Итак, ответ на основной вопрос получен — если множество истин можно задать алгоритмом, то адекватная дедуктика может быть построена и всё в порядке: всё истинное доказуемо и всё доказуемое истинно. Если же множество истин невозможно задать алгоритмически, то и нет надежды на построение адекватной дедуктики (системы доказательств). Но, может быть, всё не так плохо и неалгоритмические множества истин нам просто не понадобятся на практике? Увы, ответ отрицательный — неалгоритмические множества истин нам совершенно необходимы.

4.4 ¢ .8. Множество истин арифметики

Сначала установим важный факт, относящийся к числовым множествам.

Говорят, что множество натуральных чисел N ÍN выразимо с помощью множества истин T, если существует такая вычислимая функция F: N® U ^*, что n Î N тогда и только тогда, когда F (n)Î T.

Теорема. Множество истин T выражает хотя бы одно неперечислимое множество натуральных чисел N тогда и только тогда, когда не существует дедуктики < D, D > адекватной T.

Доказательство.

[Þ] Пусть множество N неперечислимо и выразимо множеством истин T с помощью вычислимой функции F: N® U ^*. Имеем N = F ^–1 (Im F Ç T). Но множество значений Im F вычислимой функции натурального ряда перечислимо по лемме 4. Значит множество T неперечислимо, иначе множество Im F Ç T было бы перечислимо и множество N было бы перечислимо по лемме 5. Для неперечислимого множества истин адекватной дедуктики не существует.

[Ü] Пусть для множества истин T адекватной дедуктики не существует. Тогда множество Т неперечислимо. Но множество U ^* перечислимо, пусть оно перечисляется вычислимой функцией F: N® U ^*. Имеем T = F (F ^–1(T)). Положим N:= F ^–1(T). Заключаем по лемме 5, что множество N неперечислимо и выразимо множеством истин T. чтд

Данный факт сводит несуществование адекватной дедуктики к выразимости неперечислимых числовых множеств. Но, может быть, ещё не всё потеряно и такие множества истин нам просто не нужны, и про них можно забыть? К сожалению, это не так. Неприятные случаи совсем рядом. Рассмотрим в качестве примера множество истин арифметики.

Арифметика — понятие натуральных чисел, операции сложения, умножения, отношения между натуральными числами — это такой элемент общей культуры (не только раздел математики), без которого существование современного человечества трудно себе представить. Как и ранее, обсуждение вопросов о том, является ли арифметика откровением, данным Богом, или же это итог развития науки, является ли способность к счёту врожденной или благоприобретённой, уведут нас далеко от рассматриваемого предмета: дискретная математика для программистов.

Зафиксируем язык арифметики, определённый в п.4.4.7. В этом языке используются: цифры для записи натуральных чисел, буквы для записи переменных, операции сложения + и умножения ×, отношение =, логические связки Ø, ® и кванторы ", $.

Далее из этих символов в языке арифметики допускается строить следующие конструкции.

1. Термы. Все числа и переменные суть термы. Выражения вида (t + u) и (t × u), где t и u суть термы, также суть термы. Все переменные в терме являются его параметрами. Терм без параметров называется константой.

2. Атомы. Выражения вида (t = u), где t и u суть термы, называются атомами, или элементарными формулами. Параметрами атомов являются объединение параметров термов.

3. Формулы. Если A и B суть формулы, а x — переменная, то Ø А, А ® B, $ x A, " x A тоже формулы. Кванторы исключают свои переменные из числа параметров подкванторной формулы.

Далее формулам без параметров (суждениям) сопоставляются истинностные значения T и F по правилам п. 4.4.2. Все суждения арифметики, имеющие истинностное значение T, образуют множество истин арифметики T.

Охарактеризуем класс арифметических множеств. Рассмотрим класс формул языка арифметики не более чем с одним параметром. Будем обозначать такие формулы a(x). Тогда для любого конкретного x ÎN формула a(x) — суждение, и имеет истинностное значение. Множество М:= { x ÎN | a(x) = T} называется сопряженным с формулой a(x). Арифметические множества обладают рядом полезных свойств.

Свойство 1. Дополнение к арифметическому множеству есть арифметическое множество.