П р и л о ж е н и е I

ИЗ ТЕОРИИ МОДЕЛЕЙ

Ряд устойчивых платонистских заблуждений связан с другими важными результатами математической логики, которые в основном тексте книги не рассматривались: теорема Геделя о полноте, теорема Левенгейма-Сколема, теорема о категоричности аксиом Пеано. Эти результаты и их методологические последствия (или отсутствие таковых) кратко обсуждаются в данном приложении.

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

Имея в своем распоряжении произвольные множества, теория моделей исследует формальные теории, используя интерпретации. Пусть L - некоторый язык формальной теории (другой термин - язык первого порядка, см. раздел 1.5), имеющий константы c₁, ..., c_k, функциональные символы f₁, ..., f_m, предикатные символы p₁, ..., p_n. Интерпретацией I языка L принято называть набор следующих объектов:

а) область интерпретации - некоторое непустое множество D_I (оно станет областью изменения переменных языка L),

б) отображение int_I , сопоставляющее:

- каждой константе c_i некоторый элемент множества D_I : int_I(c_i ) = c_i in D_I; это естественно - ведь константы "призваны" обозначать конкретные объекты в области интерпретации,

- каждому функциональному символу f_i некоторую функцию из D_I в D_I , т.е. int_I(f₁) = f_i, где f_i: D_I x...x D_I -> D_I (естественно, количество аргументов int_I(f_i) совпадает с количеством аргументов f_i),

- каждому предикатному символу p_i некоторое отношение на D_I, т.е. int_I(p_i) = p_i <=D_I x...x D_I (естественно, количество аргументов int_I(p_i) совпадает с количеством аргументов p_i).

В качестве примера рассмотрим так называемую стандартную интерпретацию S элементарной арифметики EA:

а) область интерпретации D_S ={0, 1, 2, ... }, т.е. D_S = w в терминах ZF,

б) отображение int_S сопоставляет: константе 0 - число 0 (пустое множество), константе 1 - число 1 (множество {0}), функциональному символу "+" - функцию x+y (сложение натуральных чисел), функциональному символу "*" - функцию x*y (умножение натуральных чисел), предикатному символу "=" - отношение x=y (равенство натуральных чисел).

При заданной интерпретации I (некоторого языка L) определяется понятие истинности формул языка L. Определение начинается с интерпретации термов в виде функций из D_I в D_I. Каждый терм языка является либо константой, либо переменной, либо комбинацией, использующей функциональные символы. В первых двух случаях интерпретацией терма становится либо постоянная функция c(x) = c_i , либо тождественная функция e(x) = x, а в последнем случае, если t=f(t₁, ..., t_n), то int_I(t) - функция, получаемая путем подстановки функций int_I(t₁), ..., int_I(t_n) в функцию int_I(f). Например, интерпретацией терма (x+y)*(x+y) является функция (x+y)² .

Далее естественным образом определяется истинность элементарных формул (при заданных значениях свободных переменных из области D_I): истинность формулы p_i(t₁, ..., t_n) устанавливается путем "вычисления" значений термов t₁, ..., t_n и подстановкой этих значений в отношение int_I(p_i). Замечание о свободных переменных здесь существенно - ведь истинность, например, формулы x=1 зависит от конкретного значения x.

Наконец, можно "определить" понятие истинности для произвольных формул языка L при данной интерпретации I (также, естественно, при заданных значениях свободных переменных формулы):

- вопрос об истинности формул ~A, A&B, AVB, A->B тривиальным образом сводится к вопросу об истинности формул A, B,

- формула (Ax)A(x) истинна, если формула A(x) истинна при любом значении переменной x из области D_I,

- формула (Ex)A(x) истинна, если формула A(x) истинна при хотя бы одном значении переменной x из области D_I.

Необходимо сознавать, что в случае бесконечной области D_I понятие истинности в такой интерпретации оказывается неконструктивным: например, проверка истинности формулы (Ax)A(x) требует проверки истинности A(x) для бесконечного числа конкретных значений x (ср. рассуждение в разделе 3.1 об истинности формул элементарной арифметики). Еще более неконструктивно понятие истинности формул вида (AxEy)B(x,y), (AxEyAz)C(x,y,z) и т.д.

Формула языка L называется тождественно истинной при данной интерпретации I, если она истинна при любых (взятых из D_I) значениях своих свободных переменных.

Ряд формул тождественно истинны при любых интерпретациях, например

A->A, (A->B)->((B->C)->(A->C)), (Ax)(C->D(x))->(C->(Ax)D(x)),

где формула C не содержит переменной x. Такие формулы, тождественно истинные при любой интерпретации (т.е. благодаря своей форме), принято называть логически общезначимыми. Следует отметить двойную неконструктивность этого понятия - на уже неконструктивное понятие истинности здесь накладывается квантор "для всех интерпретаций".

Легко проверить, что логические аксиомы и правила вывода, сформулированные в разделе 1.5, позволяют доказывать только логически общезначимые формулы. Но можно поставить обратный вопрос - всякую ли логически общезначимую формулу можно доказать с помощью этих аксиом? Получить ответ не так просто, он был дан в 1929 г. К.Геделем:

ТЕОРЕМА ГЕДЕЛЯ О ПОЛНОТЕ. В любом языке первого порядка формула является логически общезначимой, если и только если ее можно доказать с помощью логических аксиом и правил вывода из раздела 1.5.

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

Пусть T - формальная теория. Интерпретация I (языка T) называется моделью теории T, если при этой интерпретации тождественно истинны все аксиомы (и все теоремы) теории. Такое понятие модели несколько необычно: в нормальной ситуации сама теория служит моделью явления природы, технического устройства и т.п., а здесь - наоборот! Это, однако, общепринятый жаргон математической логики.

ТЕОРЕМА О СУЩЕСТВОВАНИИ МОДЕЛИ. Если формальная теория непротиворечива, то существует конечная или счетная модель этой теории.

Конечная или счетная модель - интерпретация с конечной или счетной областью D_I. Смысл теоремы можно при желании объяснять так: если в теории нет противоречий, то ее "содержание" непусто - она описывает какую-то "математическую реальность".

Элегантное доказательство теоремы о существовании модели, принадлежащее Л.Генкину и Г.Хазенъегеру, см. в книге Э.Мендельсона [1976].

Если теорема о существовании модели доказана, то теорема Геделя о полноте оказывается простым ее следствием. В самом деле, то, что все формулы некоторого языка первого порядка L, выводимые с помощью логических аксиом и правил вывода, являются логически общезначимыми, можно легко проверить, рассуждая по индукции. Теперь допустим, что какую-либо логически общезначимую формулу F из языка L нельзя доказать с помощью логических аксиом и правил вывода. Это значит, что теория T (на языке L), единственной собственной аксиомой которой является формула ~F, будет непротиворечивой (будь она противоречивой - это означало бы доказуемость "от противного" формулы F чисто логическими средствами). Таким образом, существует модель теории T, т.е. интерпретация, в которой тождественно истинны все аксиомы T, в том числе формула ~F. Однако в этой интерпретации должна быть тождественно истинной и (логически общезначимая) формула F! Формулы F и ~F не могут быть истинными в одной и той же модели, т.е. наше предположение неверно и формулу F можно доказать с помощью логических аксиом и правил вывода, что и требовалось.

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

Примечание 1. Полная конструктивность здесь, к сожалению, недостижима. Как показал в 1936 г. А.Черч, если рассматривать, например, язык EA, то не существует алгоритма, который распознает, является ли данная формула языка логически общезначимой (теорема Черча о неразрешимости исчислений предикатов, см. Э.Мендельсон [1976]).

Примечание 2. Теорема о существовании модели сначала была доказана в более слабой форме: если формальная теория имеет какую-либо модель, то она имеет и конечную или счетную модель (теорема Левенгейма-Сколема, доказанная Л.Левенгеймом в 1915 г. и Т.Сколемом в 1920 г.).

С теоремой Левенгейма-Сколема связан парадокс Сколема. Если предположить, что теория ZFC имеет какую-либо модель, то согласно этой теореме она имеет и модель, состоящую из счетного числа элементов (модель ZFC не может быть конечной из-за аксиомы бесконечности, которая должна выполняться в модели). Но ведь в теории ZFC можно доказать существование несчетных множеств, как же она может иметь счетную модель?

Платонистски настроенные мыслители делают отсюда вывод, что теория ZFC не является "полноценной" формализацией теории множеств. Более того, они считают, что "подлинную" теорию множеств вообще невозможно представить в виде формальной теории (ведь для любой такой теории - в случае ее непротиворечивости - найдется счетная модель).

На самом деле парадокс Сколема имеет очень простое объяснение, не оставляющее места для каких-либо спекуляций. Пусть I - интерпретация теории ZFC со счетной областью D_I. В ZFC можно доказать, что, например, множество всех дейст- вительных чисел R несчетно, т.е.

_1-1

~(Ef) f: R -> N, (1)

где N - множество всех натуральных чисел, f - однооднозначная функция. Разумеется, если взять интерпретации N и R: int_I(N)=n in D_I, int_I (R)=r in D_I, то n, r <= D_I и множества n, r оба оказываются счетными, т.е.

_1-1

(Ef) f: r-->n.

Однако интерпретацией теоремы (1) является утверждение

_1-1

~(Ef in D_I) f: r-->n,

поэтому противоречие здесь не возникает: однооднозначные функции типа f: r-->n существуют, но ни одна из них не содержится в модели! "Наблюдателю со стороны" все множества модели кажутся счетными, однако "наблюдатель", находящийся "внутри модели", некоторые функции "не видит", поэтому некоторые счетные множества ему представляются несчетными.

С аксиомами Дж.Пеано (см. начало раздела 3.1) связан еще один платонистский предрассудок. Для этих аксиом можно доказать теорему о категоричности, которая утверждает, что "всякие две модели, в которых выполняются аксиомы Пеано, изоморфны". Понятие модели арифметики Пеано легко формулируется в теории ZF: это тройка (v,o,s), где v - множество (его элементы считаются "натуральными числами" модели), o - элемент v ("нуль"), s - функция типа v->v (s(x) играет роль функции x+1). Будем говорить, что в модели (v,o,s) выполняются аксиомы Пеано, если

P1: ~(s(x)=o) для всех x in v,

P2: s(x)=s(y) -> x=y для всех x, y in v,

P3: если u<=v, то

o in u & (Ay)(y in u -> s(y) in u) -> u=v.

Естественной моделью арифметики Пеано оказывается множество w всех натуральных чисел по Дж. фон Нейману (см. раздел 2.3), где нулем является пустое множество 0, а роль s(x) играет xU{x}. Эту модель принято называть стандартной моделью. Наконец, будем говорить, что модель (v,o,s) изоморфна стандартной модели, если существует отображение f: w->v такое, что

а) f(0)=o,

б) n in w -> f(n+1)=s(f(n)) (если x соответствует n, т.е. x=f(n), то s(x) соответствует n+1, т.е. s(x)=f(n+1)),

в) область значений rng(f)=v,

г) f - однооднозначная функция. Теперь мы можем сформулировать упомянутую теорему.

ТЕОРЕМА О КАТЕГОРИЧНОСТИ. Всякая модель аксиом Пеано изоморфна стандартной модели.

Д о к а з а т е л ь с т в о. Итак, пусть в модели (v, o, s) выполняются аксиомы Пеано. Определим по индукции следующее отображение f типа w->v:

f(0)=o, f(1)=s(o), f(2)=s(s(o)),..., f(k+1)=s(f(k)),...

Покажем, что f является изоморфизмом:

а) f(0)=o по определению,

б) f(k+1)=s(f(k)) по определению,

в) область значений rng(f) содержится в v, ибо o in rng(f), и если y in rng(f), то y=f(k) для некоторого k, и поэтому s(y)=s(f(k))=f(k+1) in rng(f). Так как в модели (v,o,s) выполняется аксиома P3, то отсюда вытекает, что rng(f)=v,

г) покажем, что f(m)=f(n) -> m=n, т.е. что функция f однооднозначна. Итак, пусть f(m)=f(n). Возможны три случая:

г1) m=n=0 (все ясно),

г2) m=0, n>0. Тогда f(m)=o, однако f(n)=s(f(n-1))<>o из-за аксиомы P1, которая выполняется в модели (v,o,s),

г3) m, n>0. Тогда f(m)=s(f(m-1))=f(n)=s(f(n-1)), и по аксиоме P2 получается, что f(m-1)=f(n-1). Продолжая в таком духе, приходим либо к случаю г1), либо к г2).

Теорема доказана.

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

Из теоремы Геделя о неполноте (см. раздел 5.3) вытекает, что система аксиом EA (или любая другая система аксиом на языке EA) этим свойством категоричности обладать не может. В самом деле, формула Геделя для теории EA имеет вид ~(Ex)C(x), причем если теория EA непротиворечива, то для каждого конкретного натурального числа n: EA |- ~C(n), однако в EA невозможно доказать ~(Ex)C(x). Это означает, что непротиворечивой является теория EA' = EA+{(Ex)C(x)}. В моделях теории EA' для каждого "стандартного" натурального числа n выполняется ~C(n) (как теорема EA, т.е. и EA'), однако в этих моделях существует объект q, для которого выполняется C(q). Такие объекты принято называть "нестандартными" натуральными числами, а модели, в которых они существуют, - нестандартными моделями арифметики.

И формулировку, и доказательство теоремы о категоричности можно осуществить в теории ZF, т.е. ничего "сверхъестественного" в этой теореме быть не может. Ну, а причиной психологического заблуждения, связанного с ней, является закон исключенного третьего (одна из аксиом ZF: AV~A для любой формулы A, поэтому каждая формула в данной модели либо истинна, либо ложна).

П р и л о ж е н и е 2

ВОКРУГ ТЕОРЕМЫ РАМСЕЯ

Отношение многих "практикующих" математиков, занятых решением конкретных математических проблем (или даже прикладных вопросов), к теоремам о неполноте можно выразить следующими словами: "Из теорем Геделя не вытекает неразрешимость проблемы, которой я сейчас занимаюсь, поэтому оставьте меня в покое!" Некоторый "методологический базис" под такое отношение подводит Р.Парих [1971]:

"Таким образом, операция возведения в степень является не только средством для обозначения "больших чисел", но и средством введения "нематематических" вопросов в теорию чисел.

Почему мы говорим "нематематических"? Рассмотрим формулу Геделя A, которая утверждает: "Я недоказуема". Эта формула выражает свойства N (системы натуральных чисел. - К.П.), поскольку ее можно написать с помощью кванторов и логических связок (т.е. на языке EA. - К.П.). Однако чтобы увидеть, что A истинна, но недоказуема, мы используем не свойства N, а свойства интуитивного понятия "доказуемость". Таким образом, разговоры о том, что A является утверждением о числах, похожи на аргументы вроде: поведение человека является проблемой физики, поскольку человеческие существа являются физическими телами. Даже если такое предположение верно, оно оказывается очень теоретическим и малополезным."

Это глубокие соображения и, по-видимому, из них следуют далеко идущие выводы о природе формализации, однако они не могут служить оправданием пренебрежительного отношения "практикующих" математиков к теоремам о неполноте.

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

Первым серьезным шагом в этом направлении является обнаруженная в 1977 г. недоказуемость в теории EA так называемой усиленной конечной теоремы Рамсея (если преположить, что EA непротиворечива), которую нетрудно доказать в теории множеств (см. дальше). Это первый пример содержательно интересного утверждения о свойствах системы натуральных чисел, для доказательства которого недостаточно "ограниченного" понятия об этих числах, представленного в теории EA.

Бесконечная теорема Рамсея

Теорема, доказанная Ф.Рамсеем (1903-1930), относится к области комбинаторной математики.

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

Рассмотрим следующую проблему. Пусть M - конечное или счетное множество элементов, которые будем называть "игроками". Если e - натуральное число, то подмножества M, содержащие ровно e элементов, будем называть "e-командами". Пусть задано некоторое разбиение e-команд из M на r непересекающихся классов (например, по "классу игры"). Ф.Рамсей заметил, что если множество M взять достаточно большим, то при любом разбиении e-команд из M на r классов найдется достаточно большое подмножество H<=M, такое, что все e-команды из H попадают в один класс разбиения. Такое подмножество H принято называть однородным для данного разбиения.

Особенно наглядной проблема становится при e=2. Тогда элементы множества M можно представлять вершинами полного графа, а 2-команды - ребрами графа, окрашивая их в r цветов, в зависимости от класса разбиения, куда каждая команда попадает. Однородным множеством в этом случае является полный подграф, состоящий из ребер одного цвета. Согласно теореме Рамсея в достаточно большом "цветном" полном графе найдется и достаточно большой одноцветный полный подграф.

Правда, сам Ф.Рамсей доказал свою теорему для бесконечных множеств.

БЕСКОНЕЧНАЯ ТЕОРЕМА РАМСЕЯ. Пусть e,r>0 - натуральные числа. Если M - счетное множество, то для любого разбиения e-команд из M на r классов найдется бесконечное подмножество H<=M, все e-команды которого попадают в один класс разбиения.

Д о к а з а т е л ь с т в о (проводится в теории ZFC, см. Р.Грэхем [1984]). Воспользуемся индукцией по e.

1) При e=1 утверждение теоремы очевидно (если M - бесконечное множество, а число классов разбиения конечно, то в один из классов попадает бесконечное число элементов M, это и есть требуемое однородное подмножество H).

2) Идею дальнейшего доказательства проще всего объяснить для e=2. В этом случае (см. выше) ситуацию представляет "цветной" полный граф. Требуется доказать, что в бесконечном полном графе M, ребра которого раскрашены в r цветов, найдется бесконечный полный подграф с ребрами одного цвета.

Определим следующую последовательность вершин графа, цветов и подграфов. Сначала выбираем произвольную вершину a₀ in M. Из нее исходит бесконечное число ребер к остальным вершинам графа. Среди них найдется бесконечно много ребер одного цвета, обозначим этот цвет через c₀, а (бесконечное) множество конечных вершин этих ребер - через M₁ . Таким образом, M₁ <= M₀ = M, и вершина a₀ с вершинами из M₁ связана только ребрами цвета c₀. Затем выбираем произвольную вершину a₁ in M₁. Из нее в сторону остальных вершин M₁ исходит бесконечное число ребер, среди них - бесконечное число ребер одного цвета, который обозначим через c₁. Соответствующее (бесконечное) множество конечных вершин этих ребер обозначим через M₂ . Таким образом, M₂ <= M₁ <= M₀ , и вершина a₁ с вершинами из M₂ связана только ребрами цвета c₁ . Затем выбираем произвольную вершину a₂ in M , и т.д.

В результате этого процесса получаем три бесконечные последовательности:

- вершин: a₀, a₁, ..., a_n,...,

- цветов: c_0, c₁, ..., c_n, ...,

- бесконечных подграфов: M = M₀ >= M₁ >= ... >= M_m >= ... Здесь всегда a_i in M_i -M_i+1, и из a_i в сторону вершин из M_i+1 ведут только ребра цвета c_i.

Один из r цветов встречается в последовательности бесконечное число раз, обозначим его через c:

c = c_i0 = c_i1 = c_i2 =...

Множество соответствующих вершин обозначим через H:

H = {a_i0, a_i1, a_i2, ... }.

Оно бесконечно, и все его вершины связывают ребра цвета c, т.е. мы получили требуемый бесконечный "одноцветный" подграф.

Этим завершается доказательство бесконечной теоремы Рамсея для случая e=2.

3) Докажем теперь общий случай шага индукции: переход от e-1 к e. Мы сможем полностью повторить рассуждения п.2, если будет доказана следующая

ЛЕММА. Пусть даны счетное множество M и разбиение P e-команд из M на r классов. Если бесконечная теорема Рамсея верна для e-1, то для всякого бесконечного подмножества M' <= M и всякого элемента a' in M' найдется бесконечное подмножество H' <= M'-{a'}, такое, что все e-команды, состоящие из a' и элементов H', попадают в один класс разбиения P.

Докажем эту лемму. Исходя из разбиения P построим следующее разбиение P' (e-1)-команд из M' -{a'} на r классов:

{x₁, ..., x_e-1} in P_i' <-> {a', x₁, ..., x_e-1} in P_i.

Через P_i, P_i' здесь обозначены i-е классы обоих разбиений, все x_j in M'-{a'}. Применим бесконечную теорему Рамсея к (e-1)-командам из M'-{a'}, получив бесконечное подмножество H' <= M'-{a'}, такое, что все (e-1)-команды из H' попадают в один класс разбиения P'. Переходя от P' к исходному разбиению P (т.е. добавляя элемент a' к каждой (e-1)-команде из H'), получаем утверждение леммы.

Имея такую лемму, мы можем повторить рассуждение п.2. Лемма нужна для получения бесконечного множества M_i+1 <= M_i -{a_i}, такого, что все e-команды из M_i+1 U{a_i}, содержащие a_i , попадают в один класс разбиения P (этот класс можно обозначить через a ). i

Тем самым индукцией по e бесконечная теорема Рамсея дока- зана полностью.

Формулировка и доказательство бесконечной теоремы Рамсея относятся, разумеется, к теории множеств. Эта теорема оказывается, таким образом, теоремой теории ZFC. Нет никакой возможности даже сформулировать ее средствами теории EA, которые не позволяют обсуждать произвольные бесконечные множества.

Конечная теорема Рамсея

В теории EA можно, однако, сформулировать и доказать аналог бесконечной теоремы Рамсея для конечных множеств:

КОНЕЧНАЯ ТЕОРЕМА РАМСЕЯ. Существует вычислимая функция R(e, r, k), такая, что при любых e, r, k > 0 для любого конечного множества M: если |M| >= R(e, r, k), то для любого разбиения P e-команд из M на r классов найдется подмножество H <= M такое, что |H| >= k и все e-команды из H попадают в один класс разбиения P.

И здесь наиболее наглядной оказывается ситуация при e=2: существует функция R(r,k) такая, что любой полный граф, имеющий R(r,k) вершин и рeбра, раскрашенные в r цветов, содержат полный подграф из k вершин, все ребра которого раскрашены в один цвет.

Д о к а з а т е л ь с т в о (см. Р.Грэхем [1984], его можно формализовать в теории EA).

1) При r=1 утверждение теоремы очевидно: можно взять R(1, k) = k.

2) Рассмотрим теперь случай r=2, когда все e-команды из M разбиваются на два класса. Оказывается, легче доказать следующее обобщение теоремы: существует вычислимая функция R'(e, 2, k₁, k₂), такая, что при |M|>=R'(e ,2, k₁, k₂) для дюбого разбиения e-команд из M на два класса найдется либо подмножество H₁ такое, что |H₁| = k₁ и все e-команды из H₁ попадают в первый класс разбиения, либо подмножество H₂ такое, что |H₂| = k₂ и все e-команды из H₂ попадают во второй класс разбиения.

Доказываем по индукции, переходя от случая e-1 и случаев (e, k₁-1, k₂), (e, k₁, k₂-1) к случаю (e, k₁, k₂).

Б а з и с и н д у к ц и и. При e=1 можно взять

R'(1, 2, k₁, k₂ ) = k₁ + k₂

(в этом случае сами элементы M разбиваются на два класса). Далее, рассматривая случай произвольного e и наименьшего k₁, имеем: при k₁=e можно взять R'(e ,2, e, k₂) = k₂ (k₂>=e), поскольку если существует хотя бы одна e-команда первого класса, то она одна и составляет требуемое H₁, а если все e-команды из M попадают во второй класс, то можно взять H₂=M. Аналогично при k₂=e можно взять R'(e, 2, k₁, e) = k₁ (k₁>=e).

Ш а г и н д у к ц и и. Пусть k₁, k₂ > e. Покажем, что можно взять:

R'(e, 2, k₁, k₂) = 1+R'(e-1, 2, R'(e, 2, k₁-1, k₂), R'(e, 2, k₁, k₂-1)).

В самом деле, если |M|>=R'(e, 2, k₁, k₂), то выбираем один элемент a in M и рассматриваем все e-команды из M, содержащие a: {a, x₁, ..., x_e-1}. Каждая из них относится к первому или второму классу разбиения P. Определим для (e-1)-команд из M-{a} следу- ющее разбиение P' на два класса (i=1, 2):

{x₁, ..., x_e-1} in P' <-> {a, x₁, ..., x_e-1} in P .

Поскольку |M-{a}|>=R'(e-1, 2, T₁, T₂), где T₁ = R'(e, 2, k₁-1, k₂) и T₂ = R'(e, 2, k₁, k₂-1), то, по теореме Рамсея для случая e-1, найдется подмножество M'<=M-{a} такое, что либо |M'|=T₁ и все (e-1)-команды из M' попадают в первый класс, либо |M'|=T₂ и все (e-1)-команды из M' попадают во второй класс. В первом случае

(Ax₁, ..., x_e-1 in M') {a, x₁, ..., x_e-1} in P₁

(P₁ - первый класс разбиения P). Но так как |M'| = T₁ = R'(e, 2, k₁-1, k₂), то по предположению индукции (случай (e, k₁-1, k₂)) найдется подмножество H<=M' такое, что либо |H|=k₁-1 и все e-команды из H попадают в первый класс разбиения P (тогда HU{a} будет искомым подмножеством для случая (e, k₁, k₂)), либо |H|=k₂ и все e-команды из H попадают во второй класс разбиения P (тогда это же H подходит и для случая (e, k₁, k₂)).

Второй случай разбирается аналогично.

Для случая r=2 конечная теорема Рамсея доказана.

3). Перейдем теперь к случаю произвольного r>=2 и проведем индукцию по r.

Б а з и с и н д у к ц и и. При r=2 возьмем

R(e, 2, k) = R'(e, 2, k, k).

Ш а г и н д у к ц и и. Покажем, что можно взять

R(e, r, k) = R(e, 2, R(e,r-1,k)).

В самом деле, пусть |M|>=R(e, r, k) и задано некоторое разбиение P e-команд из M на r классов. Чтобы привести ситуацию к случаю двух классов, зафиксируем один из классов разбиения P (будем называть его первым классом), а остальные объединим (будем называть это вторым классом). Тогда согласно доказанному в случае r=2 найдется подмножество M'<=M такое, что |M'|=R(e, r-1, k) и либо а) все e-команды из M' попадают в первый класс, либо б) все e-команды из M' попадают во второй класс.

В случае а), поскольку R(e, r-1, k)>=k, мы сразу получаем H<=M' такое, что |H|=k и все e-команды H попадают в один класс разбиения P. В случае б) получаем разбиение e-команд из M' на r-1 класс разбиения P. Поскольку |M'|= R(e, r-1, k), то согласно предположению индукции (случай r-1) найдется подмножество H<=M' такое, что |H|=k и все e-команды из H попадают в один класс разбиения P.

Конечная теорема Рамсея доказана полностью.

Хотя в конечной теореме Рамсея идет речь не о натуральных числах, а о произвольных конечных множествах, эту теорему можно сформулировать в теории EA. Достаточно принять какое-либо кодирование конечных множеств натуральными числами, например с помощью бета-функции Геделя (см. раздел 3.3): кодом множества {a₁, ..., a_n} будем считать пару чисел a, b такую, что

beta(a, b, 0)=n, beta(a, b, 1)=a₁, ..., beta(a,b,n)=a_n.

Таким образом, конечную теорему Рамсея можно не только сформулировать, но и доказать в теории EA (в этом нет ничего удивительного: ведь все рассуждения в приведенном выше доказательстве элементарны).

Усиленная конечная теорема Рамсея

Мы имеем, таким образом, две теоремы Рамсея:

а) "бесконечную", которую нельзя ни сформулировать, ни (тем более) доказать в элементарной арифметике (теории EA); для этого нужна теория множеств (теория ZFC),

б) "конечную", которую можно сформулировать и доказать в элементарной арифметике.

В 1977 г. Л.Харрингтон, опираясь на новый метод, изобретенный Л.Кэрби и Дж.Парисом, обнаружил промежуточный вариант - усиленную конечную теорему Рамсея (УКТР), которую можно сформулировать, но нельзя доказать в элементарной арифметике (т.е. в теории EA, разумеется, если она непротиворечива). Это первый случай, когда удалось показать, что для доказательства некоторого содержательно интересного утверждения о свойствах натуральных чисел нужны средства, выходящие за рамки теории EA.

Чтобы подойти к формулировке усиленной конечной теоремы Рамсея, мы должны рассматривать в конечной теореме Рамсея не произвольные множества M, а множества, которые берутся из определенного счетного "универсума" с отношением порядка, например из множества всех натуральных чисел. Тогда появится возможность сравнивать конечные множества не только по количеству элементов, но и по другим признакам. Например, можно рассматривать "разреженные" множества H = {a₁, a₂, ... , a_n}, выделямые условием

2^a1 <= a₁, 2 ^a2 <= a ₂, ..., 2 ^an <= a_n,

или, наоборот, "плотные" множества:

a₁ < a₂ < ... < a_n & a₁ <= n

(или min(H)<=|H|). (Заметим, что в данном случае множество H может быть "плотным" и "разреженным" одновременно.)

В формулировке УКТР может использоваться широкий класс свойств "плотности". Как мы увидим из доказательства, в качестве свойства плотности в УКТР можно взять любое свойство gamma конечных множеств натуральных чисел, удовлетворяющее двум условиям:

а) если H₁ <= H₂ и gamma(H₁), то gamma(H₂ ),

б) если H₂ - бесконечное множество натуральных чисел, то найдется конечное подмножество H₁ <= H₂ , такое, что gamma(H₁).

Подобное свойство естественно называть плотностью (по отношению к системе всех натуральных чисел).

Свойство min(H)<=|H| является простейшим из свойств, удовлетворяющих этим условиям:

- если H₁ <= H₂ и min(H₁)<=|H₁|, то min(H₂ )<=|H₂|,

- если H₂ - бесконечное множество и H₁ - множество наименьших min(H₂) элементов H₂ , то min(H₁) <= |H₁|.

Это пример разрешимого свойства "плотности" (по заданному конечному множеству H можно "вычислить", плотное оно или нет).

УСИЛЕННАЯ КОНЕЧНАЯ ТЕОРЕМА РАМСЕЯ. Для каждого разрешимого свойства плотности gamma существует вычислимая функция R_gamma(e, r, k), такая, что при любых e, r, k>0 для любого конечного множества M: если |M|>=R_gamma(e, r, k), то для любого разбиения P e-команд из M на r классов найдется gamma-плотное подмножество H<=M, такое, что |H|>=k и все e-команды из H попадают в один класс разбиения P.

Эта теорема отличается от обычной конечной теоремы Рамсея по существу "только" одним словом - дополнительно требуется, чтобы множество H было плотным.

Д о к а з а т е л ь с т в о (проводится в теории ZFC, см. Дж.Парис, Л.Харрингтон [1977]). Очевидно, можно ограничиться рассмотрением в роли M множеств вида {0,1,...,n}, поэтому мы будем считать, что M={0,1,...,M-1} (как в разделе 2.3). Для данных e, r рассматриваются все M>=e.

Для M=e возможна только одна e-команда {0,1,...,e-1} и r ее разбиений на r классов.

Рассмотрим теперь конкретную пару (M,P), где P - разбиение e-команд из M на r классов. Если перейти от M к M+1, т.е.

M+1 = {0, 1, ..., M-1, M} = MU{M},

то из разбиения P можно получить только конечное число различных разбиений e-команд из M+1 на r классов, которые на M согласуются с P. Разбиение P' согласуется с P - это означает, что для любой e-команды {x₁,..., x_e} из M и любого i (1<=i<=r): 1 e

{x₁, ..., x_e} in P_i' <-> {x₁, ..., x_e} in P_i.

Разбиение P' отличается от P, таким образом, только тем как оно разбивает те e-команды, которые содержат число M.

Если начиная с M=e, повторно применять эту процедуру, то в результате мы получим бесконечное дерево с конечными ветвлениями:

|-------(e, P₀')------ ...

|

|-------(e, P₀'')------ ...

|

|------- ...

|

|-------(e, P₀⁽ⁱ⁾)------ ... --------(M, P)-------|-------(M+1, P^(j)) -----------

|

|------- ...

|

|-------(e, P₀^(r))------ ...

Здесь через P₀⁽ⁱ⁾ обозначены все разбиения e-команд из e на r классов, а через P^(j) - всевозможные разбиения e-команд из M+1 на r классов, согласованные с разбиением P. Легко проверить, что вершины этого дерева охватывают все возможные пары (M, P) (при фиксированных e, r), одновременно упорядочивая их определенным образом.

Будем называть вершину (M, P) "хорошей", если существует подмножество H<=M, обладающее свойством gamma, такое что |H|>=k и все e-команды из H попадают в один класс разбиения P. Легко проверить, что если (M, P) - "хорошая" вершина, то все (M+1, P^(j)) - также "хорошие".

Из-за конечности ветвлений в вершинах каждый уровень дерева содержит только конечное число вершин, поэтому УКТР будет доказана, если мы сумеем показать, что "нехороших" вершин существует только конечное число.

В самом деле, в таком случае мы могли бы предложить следующий алгоритм вычисления значения функции R_gamma(e, r, k). Будем проходить все уровни дерева подряд, проверяя каждую вершину (M, P), "хорошая" она или нет (путем полного перебора всех 2^M подмножеств M). Если на каком-то уровне все вершины оказались "хорошими", то номер M этого уровня можно взять в качестве значения R_gamma(e, r, k). Нужна только гарантия, что такой уровень всегда найдется.

Итак, предположим от противного, что в нашем дереве бесконечно много "нехороших" вершин. Если (M+1, P^(j)) - "нехорошая" вершина, то (M, P) - также "нехорошая", поэтому в дереве найдется бесконечная ветвь, состоящая только из "нехороших" вершин.

Упражнение 1. Докажите строго, что это действительно так (это лемма Кенига: если дерево с конечными ветвлениями содержит бесконечно много вершин, то в нем имеется бесконечная ветвь).

Бесконечная ветвь, состоящая из согласованных разбиений (M, P_M), задает одно определенное разбиение P' всех e-команд, состоящих из натуральных чисел, на r классов: класс e-команды {i₁, i₂, ..., i_e} определяет разбиение P_M , где

M = max{i₁, i₂, ..., i_e},

а последующие разбиения P_M+1, P_M+2, ... не могут это определение изменить, поскольку они согласованы с P_M.

Применив теперь к разбиению P' (всех e-команд из натуральных чисел) бесконечную теорему Рамсея, получим бесконечное множество H', все e-команды которого попадают в один класс разбиения P'. "Плотность" свойства gamma позволяет получить конечное подмножество H<=H', такое, что |H|>=k и gamma(H) (сначала находим просто конечное подмножество, обладающее свойством gamma, затем, если это необходимо, пополняем его до k элементов из H'). Если взять M=max(H), то все e-команды из H окажутся и в одном классе разбиения P_M. Это противоречит тому, что вершина (M, P_M) - "нехорошая".

Усиленная конечная теорема Рамсея доказана полностью.

УКТР недоказуема в элементарной арифметике

Легко показать, что для разрешимого свойства gamma (как min(H)<=|H|) УКТР можно сформулировать в теории EA. В 1977 г. Л.Харрингтон, опираясь на новый метод, изобретенный Л.Кэрби и Дж.Парисом, показал, что для свойства плотности min(H)<=|H| эту теорему нельзя доказать в теории EA (разумеется, если она непротиворечива, см. Дж.Парис, Л.Харрингтон [1977]). Это первый случай, когда удалось строго доказать, что для доказательства некоторого содержательно интересного утверждения о свойствах натуральных чисел нужны средства, выходящие за рамки теории EA (мы только что доказали УКТР, используя бесконечную теорему Рамсея, т.е. в теории ZFC). Можно утверждать поэтому, что древние греки, имеющие в своем распоряжении только то изолированное понятие натурального числа, которое формализовано в EA, не могли бы доказать УКТР. Такая возможность появилась только после изобретения теории множеств в XIX в.: введение Г.Кантором понятия произвольного бесконечного множества прибавило, таким образом, новые черты понятию натурального числа.

Если обратиться еще раз к приведенному выше доказательству УКТР, то можно заметить, что сама процедура вычисления функции R_gamma(e, r, k), разумеется, в средствах теории множеств не нуждается. Эти средства понадобились, чтобы доказать сходимость алгоритма: для доказательства, что в дереве разбиений существует уровень, состоящий только из "хороших" вершин (номер первого такого уровня и становится значением R_gamma(e,r,k)).

Однако для проверки истинности предиката R_gamma(e, r, k) = q средства теории множеств не нужны: проверить, состоит ли q-й уровень в дереве разбиений только из "хороших" вершин (а (q-1)-й - содержит "нехорошую"), можно без каких-либо дополнительных предположений. Поэтому, следуя методу раздела 3.3, мы можем получить формулу F_gamma(e, r, k, q), выражающую в теории EA предикат R_gamma(e, r, k) = q. Формула

(AeArAk)(Eq)F_gamma(e, r, k, q),

с одной стороны, утверждает, что R_gamma является всюду определенной функцией, а с другой стороны, она равносильна УКТР. Таким образом, если теория EA непротиворечива, то в ней невозможно доказать всюду определенность функции R_gamma (а в теории ZFC это уже можно сделать).

Еще один удивительный факт связан с чрезвычайной скоростью роста функции R_gamma. Уже функция R(e, r, k) из конечной теоремы Рамсея растет очень быстро (проверьте), однако R_gamma превосходит в этом смысле всякое воображение. Можно показать, что если в теории EA доказуема всюду определенность функции f(x), т.е.

EA|- (Ax)(Ey)F(x,y),

где F(x,y) - формула, представляющая в EA функцию f, то

ZFC |- (Ex₀)(Ax>x₀)(f(x)< R_gamma(x, x, x+1)).

Таким образом, функция R_gamma(x, x, x+1) растет быстрее любой функции, вычислимость которой можно доказать в элементарной арифметике! (См. Дж.Парис, Л.Харрингтон [1977]. )