Доказательство. Рассмотрим построенное перечислимое неразрешимое множество N. Его дополнение N\N неперечислимо, в противном случае N было бы разрешимо по лемме 3. чтд

Таким образом, построено перечислимое множество с неперечислимым дополнением.

К данному моменту накоплен достаточный запас фактов, чтобы показать применимость и полезность наивной теории алгоритмов в форме доказательства первой теоремы Гёделя о неполноте.

4.4 ¢ .7. Истинность и доказуемость

В первой теореме Гёделя о неполноте (п. 4.4.9) речь идет об «истинности» и «доказуемости». Чтобы доказывать какие-либо утверждения относительно этих понятий, необходимо придать им математический смысл.

Понятие доказательства является едва ли не самым главным в математике, но формально определить его даже труднее, чем понятия множества и алгоритма. Прекрасное определение: доказательство — это рассуждение, убеждающее нас настолько, что с его помощью мы готовы убеждать других. Однако это определение принадлежит скорее психологии, нежели математике. Ничуть не проще для математического определения и понятие истины. Попытки раскрыть это понятие во всей полноте уводят нас в философию, языкознание, теологию и в другие очень интересные и поучительные области мысли, которые, однако, далеки от изучаемого предмета: дискретной математики для программистов.

Выход состоит в том, чтобы зафиксировать неопределяемые понятия в виде несложно устроенных конструктивных объектов и далее манипулировать этими объектами средствами наивной теории множеств и наивной теории алгоритмов. То, что получится, можно назвать наивной теорией доказательства.

В данном случае множество истинных утверждений, или множество истин, рассматривается просто как некоторое множество слов T в нашем универсальном алфавите U. Далее, множество доказательств также рассматривается просто как некоторое разрешимое множество слов D в нашем универсальном алфавите U. Элементы множества D называются доказательствами. Других ограничений на множества T и D пока не накладывается. Наряду с разрешимым множеством D постулируется наличие вычислимой функции D: D ® U ^*, называемой функцией извлечения доказанного. Если p = D (d), где d Î D, то p называется теоремой. Таким образом, P = D (D) — множество теорем. Пара < D, D > называется дедуктикой.

Пример. Формальные теории, рассматриваемые в предыдущих разделах, являются дедуктиками. Множество D в них строится как последовательности слов, получаемых из «аксиом» по «правилам вывода» (проверка корректности вывода — это и есть разрешающий алгоритм), а функция извлечения доказанного очень проста и, очевидно, вычислима: последнее слово в доказательстве является теоремой.

Нас интересует, как соотносятся теоремы и истины в зависимости от того, какими свойствами обладают множества T и D.

Примеры. Рассмотрим некоторые примеры формулировок свойств интересующих нас множеств на естественном языке.

1. Существуют недоказуемые истины. Это утверждение тривиально и неинтересно. Достаточно положить D:=Æ, и при любом T все истины окажутся недоказуемыми.

2. Не существует дедуктики, в которой все истины доказуемы. А это утверждение просто неверно. Достаточно положить D:= Т, D (t):= t и при любом T все истины окажутся легко доказуемыми.

Дедуктика < D, D > называется непротиворечивой относительно множества истин T, если D (D) Í T (т. е. P Í T). Дедуктика < D, D > называется полной относительно множества истин T, если T Í D (D) (т. е. T Í P). Непротиворечивая и одновременно полная дедуктика называется адекватной множеству истин T, в такой дедуктике множество теорем совпадает с множеством истин, T = P.

Замечание. Разрешимое множество доказательств D является подмножеством множества всех слов, которое перечислимо. Значит, по лемме 2 множество D перечислимо. Далее, множество теорем P является образом перечислимого множества при применении вычислимой функции. Значит, по лемме 4 множество P также перечислимо.

Пример. Адекватные дедуктики для интересных множеств истин существуют: построение таблиц истинности является адекватной дедуктикой для тавтологий в исчислении высказываний (п. 4.3.8).

Вопрос состоит в том, при каких условиях, налагаемых на множество истин T, может не найтись адекватной дедуктики?

Теорема. Если множество истин T перечислимо, то существует дедуктика < D, D >, адекватная T.

Доказательство. Если T =Æ, то достаточно положить D:=Æ. Пусть T ¹Æ и T: N® T перечисляющий алгоритм в форме вычислимой функции, вычисляющей истину по её номеру. Тогда положим D:= N и D:= T. чтд

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

Следствие. Если множество истин T неперечислимо, то не существует дедуктики < D, D >, адекватной T.