Дискретка

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

x 15. Теорема Г¼деля

Одним из наиболее знаменитых результатов математической логики является теорема Г¼деля о неполноте системы Z1.

Теорема 1. Если система Z1 непротиворечива, то существует та- кое суждение в теории Z1, что ни это суждение, ни его отрицание не могут быть доказаны в Z1.

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

Напомним, что все суждения являются словами в некотором конечном алфавите a0; a1; : : : ; an 1; будем при этом полагать, что a0

это правая скобка ")". Слову ai1 ai2 : : : air сопоставим натуральное число ir + ir 1n + + i2nr 2 + i1nr 1. Мы получим биективное со-

ответствие между положительными натуральными числами и теми словами, которые не начинаются с символа ")". Поскольку ни одно суждение не начинается с этого символа, все суждения получают некоторые номера, причем номер однозначно определяет суждение; этот номер называется г¼делевым номером суждения. Отметим, что не всем номерам отвечают именно суждения (многим из них отве- чают просто бессмысленные наборы букв), но для нас это не существенно.

Все доказательства в теории Z1 тоже могут быть пронумерованы (аналогично тому, как выше мы пронумеровали все примитивно рекурсивные функции). При этом в результате n-го доказательства

получается суждение, г¼делев номер которого обозначим через h(n).

Нетрудно провести нумерацию доказательств так, чтобы получившаяся функция h(n) была рекурсивна.

Пусть M рекурсивно перечислимое, но не рекурсивное множе-

ство из предыдущего пункта. Еще один факт, доказательство которого мы опускаем: утверждение n 2 M и его отрицание n 2= M мо-

гут быть выражены как суждения Bn, :Bn в системе Z1, причем г¼делевы номера этих суждений g(n), g0(n) являются рекурсивными

функциями от n.

Теорема 2. Существует n 2 N0, для которого ни суждение Bn, íè его отрицание не могут быть доказаны в Z1.

Доказательство. Предположим, что для всех n можно доказать ли-

бо суждение Bn, либо суждение Bn0 (оба суждения не могут быть одновременно доказуемы, так как тогда существовало бы доказательство тождественно ложного суждения Bn&:Bn, то есть система Z1

была бы противоречива). Это означает, что для любого n существует такое t, что либо g(n) = h(t), либо g0(n) = h(t). Поэтому уравнение

61

T (n; t) = jg(n) h(t)j jg0(n) h(t)j = 0 разрешимо для любого n; обозначим через w(n) = ( tT )(n) наименьшее решение этого уравнения. Функция w(n) рекурсивна; вместе с ней рекурсивна и функция

v(n) = sgn(jg0(n) h(w(n))j):

Лемма 1. Функция v(n) является характеристической функцией множества M.

Доказательство. Если n 2 M, то утверждение n 2= M не может быть доказано. Тогда jg0(n) h(t)j 6= 0 äëÿ âñåõ t 2 N0, è

v(n) = sgn(jg0(n) h(w(n))j) 6= 0;

но функция v(x) принимает только значения 0, 1, и потому v(n) = 1. Если n 2= M, то утверждение n 2 M не может быть доказано;

поэтому jg(n) h(t)j =6 0 для всех t 2 N0. В частности, не равно нулю число jg(n) h(w(n))j; но

jg(n) h(w(n))j jg0(n) h(w(n))j = T (n; w(n)) = 0;

поэтому jg0(n) h(w(n))j = 0, òî åñòü v(n) = sgn(jg0(n) h(w(n))j) = 0.

Таким образом, мы получили, что рекурсивная функция v(n) является характеристической функцией множества M, то есть множество M рекурсивно. Это противоречие доказывает, что предположение о том, что для всякого n существует доказательство одного из сужде- íèé Bn, :Bn, неверно.

62