Добавил:
Upload Опубликованный материал нарушает ваши авторские права? Сообщите нам.
Вуз: Предмет: Файл:

Математическая логика

.pdf
Скачиваний:
16
Добавлен:
08.02.2015
Размер:
518.77 Кб
Скачать

21

19.Теоремы, недоказуемые в аксиоматической арифметике

В1977 г. было найдено истинное утверждение „арифметического\ характера, недоказуемое в рамках аксиоматической арифметики.

19.1. Усиленная теорема Рамсея. Одним из важных результатов в комбинаторике является теорема Рамсея.

Теорема Рамсея. Пусть заданы натуральные числа n; k и m. Тогда существует такое натуральное число N, что если мы припишем каждомуn-элементномуподмножеству множества S= f1; : : : ; Ng один из k цветов, то найдется подмножество Y ½ S, jY j> m, такое что всеn-элементныеподмножества множества Y имеют один и тот же цвет.

Замечание. N(2; 2; 3) = 6. Действительно, рассмотрим следующие2-элементныеподмножества множестваS =f1; 2; 3; 4; 5; 6g:f1; 2g; f1; 3g; f1; 4g; f1; 5g; f1; 6g. Среди них есть три одного (например, первого) цвета. Пусть это будут подмножестваf1; 2g,f1; 3g иf1; 4g. Если подмножествоf2; 3g имеет первый цвет, то

Y= f1; 2; 3g. Если подмножествоf2; 4g имеет первый цвет, тоY =f1; 2; 4g. Если подмножествоf3; 4g имеет первый цвет, тоY =f1; 3; 4g. Если же подмножестваf2; 3g,f2; 4g иf3; 4g имеют второй цвет, то

Y= f2; 3; 4g.

Вслучае n = 2,k = 2 иm = 3 теорема Рамсея имеет наглядную интерпретацию: чему должно

быть равно число N, чтобы при любой раскраске ребер полного графаKN в два цвета в нем нашелся одноцветный треугольник?

Теорему Рамсея можно усилить, дополнительно потребовав, чтобы число элементов множества Y было бы не меньше наименьшего элемента изY .

Теорема (Paris, Harrington [1977]) Усиленная форма теоремы Рамсея недоказуема в аксиоматической арифметике.

Замечание. Усиленная форма теоремы Рамсея может быть доказана в рамках теории множеств.

19.2. Теорема Гудстейна. Второй пример справедливого, но недоказуемого в арифметике утверждения связан со следующей конструкцией.

Строгой n-ичной(двоичной, троичной и т.д.) записью числа мы назовем такую его запись в соответствующей системе счисления, в которой числа> n не встречаются в показателях степеней. Другими словами, если среди показателей степеней есть числа большие числаn, то каждый такой показатель мы представим в строгой записи. Например,

35 = 222+1 + 2 + 1 (строгая двоичная запись); 100 = 33+1 + 2¢ 3 + 1 (строгая троичная запись):

Последовательность Гудстейна G(m) строится так:

²положим G(m)0 =m и найдем представление числаm в строгой двоичной записи;

²следующий шаг в строгой двоичной записи числа G(m)0 заменяем все двойки на тройки, из полученного числа вычитаем единицу это числоG(m)1 и находим представление числаG(m)1

встрогой троичной записи;

²следующий шаг в строгой троичной записи числа G(m)1 заменяем все тройки на четверки, из полученного числа вычитаем единицу это числоG(m)2 и находим представление числаG(m)2

встрогой четвертичной записи и т.д.

Пример. Последовательность G(3) выглядит очень просто:

G(3)0 = 3 = 2 + 1) 3 + 1) 3 =G(3)1 ) 4¡ 1 = 3 =G(3)2 )

) 3¡ 1 = 2 =G(3)3 ) 2¡ 1 = 1 =G(3)4 ) 1¡ 1 = 0 =G(3)5:

Мы видим, что на пятом шаге последовательность G(3) обнуляется. ПоследовательностьG(4) выглядит гораздо интереснее:

4 = G(4)0 = 22 ) 33 ¡ 1 = 26 =G(4)1 = 2¢ 32 + 2¢ 3 + 2) 2¢ 42 + 2¢ 4 + 2¡ 1 = 41 =G(4)2 )

) 2¢ 52 + 2¢ 5 = 60 =G(4)3 ) 2¢ 62 + 2¢ 6¡ 1 = 2¢ 62 + 6 + 5 = 83 =G(4)4 ) : : :

Вычисления показывают, что эта последовательность растет пока не достигнет числа 3

¢

2402653210

¡

1 (на

3 ¢ 2402653209шаге), после чего начинается долгое убывание до нуля.

 

 

Теорема Гудстейна (Goodstein [1944]). Любая последовательность Гудстейна становится нулевой после конечного числа шагов.

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

22

Неоднократно предпринимались попытки доказать теорему Гудстейна арифметическим методами. Наконец, была доказана следующая теорема.

Теорема (Kirby, Paris [1982]) Теорема Гудстейна недокаазуема в аксиоматической арифметике. Замечание.Это очень трудный результат.

Замечание. Последовательность Гудстейна быстро растет. Например,

G(19)0 = 19 = 222 + 2 + 1;

G(19)1 = 333 + 3 = 7 625 597 464 990;G(19)2 = 444 + 3¼ 1:3¢ 10154:

Можно определить функцию G : N ! N

G(n) = длина ненулевой части последовательности ГудстейнаG(n). Эта функция растет очень быстро.

19.3. Теорема Робертсона-Сеймура.Третий пример недоказуемого утверждения связан стеоремой Робертсона-Сеймура о графах. Сначала дадим определение.

Определение. ГрафH называетсяминором графаG, еслиH может быть получен при стягивании ребер некоторого подграфа графаG.

Первая теорема Робертсона-Сеймура(Robertson, Seymour [2004]).Пусть fGig бесконечная последовательность конечных графов. Тогда найдутся числа k и l, k < l, что граф Gk является минором графа Gl.

Вторая теорема Робертсона-Сеймура(Robertson, Seymour [2004]).Рассмотрим множество F

конечных графов, которое обладает следующим свойством: если граф G принадлежит F , то любой минор G также принадлежит F . Тогда существует конечное семейство графов O такое, что G 2 F в том и только том случае, когда ни один граф из O не является минором графа G.

Замечание. ЕслиF множество планарных графов, тоO =fK5; K3;3g. Это теоремаПонтрягина-Куратов-ского. Следует отметить, что теоремаПонтрягина-Куратовскогоне является следствием теоремы Роберт-сона-Сеймура,в которой лишьутверждается существование множестваO, но ничего не говорится о том, что оно из себя представляет.

Доказательство теоремы Робертсона-Сеймурарезультат многолетней работы. Сначала был доказан следующий конечный вариант теоремы.

Конечная теорема Робертсона-Сеймура. Для любого n существует m такое, что если G1; : : : ; Gm

конечная последовательность графов и jV (Gi)j+ jE(Gi)j6 n+ i для всех i,1 6 i6 m, то граф Gk является минором графа Gl для некоторых k и l, k < l.

Теорема Фридмана-Робертсона-Сеймура(Friedman-Robertson-Seymour[1987]).Конечная теорема Робертсона-Сеймура недоказуема в аксиоматической арифметике.

Литература

(1)Гэри М., Джонсон Д., Вычислительные машины и труднорешаемые задачи. М. Мир, 1982.

(2)Катленд Н., Вычислимость. Введение в теорию рекурсивных функций. М. Мир, 1983.

(3)Китаев А., Шень А., Вялый М., Классические и квантовые вычисления. М. МЦМНО, 1999.