Следствие 11. Множество значений бесконечной последовательности с попарно различными членами бесконечно.

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

Теорема 12. Множество, служащее в качестве подмножества множество значений бесконечной последовательности с попарно различными членами, бесконечно.

Множество, удовлетворяющее условиям теоремы 12, называется бесконечным в смысле Дедекинда.

Множество, бесконечное в смысле Дедекинда, бесконечно – аналог теоремы 12.

Обратная теорема также верна, но для её доказательства требуется аксиома выбора.

°Теорема 13. Бесконечное множество бесконечно в смысле Дедекинда.

Д о к а з а т е л ь с т в о. Пусть - бесконечное множество и

 - функция выбора для семейства - .

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

Определим теперь по индукции последовательность  и :

,                              

Легко показать по индукции, что любое множество  конечно и  для . Отсюда следует, что  и, значит,  и  для каждого . В последовательности  все члены попарно различны.

В самом деле, если , то , но , т.к. полагая , получаем  и . Поэтому .

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

Теорема Д. Кёнига.

Пусть  - множества,  и . Конечная последовательность  (бесконечная последовательность ) называется ветвью длины  (бесконечной ветвью), если  и  для каждого  (для каждого ).

Элемент  (не обязательно принадлежащий ) называется начальной вершиной ветви.

Если - ветвь длины  (бесконечная ветвь) и  ( ), то  - ветвь длины .

Теорема 1 (Д. Кёниг, 1927г.). Пусть все множества уровня функции  конечны. Если  и для каждого  существует ветвь длины  с начальной вершиной , то существует по крайней мере одна бесконечная ветвь с начальной вершиной .

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

Лемма 1. Если , то .

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

Теперь пусть - функция выбора для семейства непустых множеств вида , . Дополним область определения функции , полагая . Тогда  ставит соответствие каждому множеству вида  элемент множества . Определим по индукции последовательность :

,

.

Покажем, что для каждого

                (1)

Действительно, для  имеем , значит,  и, согласно лемме 1, . Следовательно, по определению функции выбора . Если утверждение (1) верно для какого-то , то по лемме 1:  и, значит, . Таким образом, утверждение (1) доказано. Из него следует, что , т.е. - бесконечная ветвь с начальной вершиной .

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

Можно доказать, что полностью устроить аксиому выбора из доказательства теоремы Кёнига невозможно, т.е. что эта теорема не следует из системы аксиом

Пример. Пусть - замкнутый интервал , и пусть  для , .

Пусть - такое семейство открытых интервалов, что . Говорят, что  покрывает интервал .

Теорема 2. Существует такое число , что  покрывает все интервалы  для .

Д о к а з а т е л ь с т в о. Пусть - семейство всех интервалов , а - семейство тех интервалов , , которые не покрываются .

Пусть  - тот интервал , который содержит . Тогда определена функция, принадлежащая , причем множества её уровня конечны. Для доказательства теоремы достаточно показать, что существует такое число , что ни одна из ветвей с начальной вершиной  не имеет длины .

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

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

Графы. Теорема Рамсея.

Множество , состоящее из неупорядоченных пар различных элементов, называется графом. Множество  называется полем графа, его элементы – вершинами графа.

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

Эта геометрическая интерпретация представляет собой линию, отрезки которой (рёбра) не имеют общих точке, за исключением вершин.

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

Если - граф над полем , то разность  также является графом, называемым дополнением графа .

Граф  называется подграфом графа , если . Изучение графов равносильно изучению симметричных антирефлексивных отношений, т.е. отношений, для которых 1) , 2) .

В самом деле, каждому графу  можно поставить в соответствие такое отношение, полагая . И обратно, каждое симметричное антирефлексивное отношение определяет граф , причем .

Теорема (Рамсей, 1923г). Если - граф над бесконечным полем, то или , или  содержит полный подграф над бесконечным полем.

Д о к а з а т е л ь с т в о. Пусть - функция выбора для . Положим

,

.

Тогда множество  состоит из вершин, связанных ребром с  в графе , а - из вершин, связанных ребром с  в графе .

Определим по индукции 4 последовательности:

,          ,

,               .

А именно:

, , .

1)

2) , , .

Рассмотрим 2 случая:

 для всех .

Можно доказать по индукции, что для всех

(1) ,

(2) множество  бесконечно,

(3) ,

(4) .

Если , то из (3) следует, что , а т.к.  (по (1) и (4)), то .

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

2-й случай. Существует такое , что . Обозначим наименьшее такое число через . Т.к.  для , то .

Множество  или равно  (если ), или имеет вид . В обоих случаях оно бесконечно: в 1-м случае – по условию, во 2-м случае – поскольку .

Определим по индукции последовательность  подмножеств множества  и последовательность  элементов множества :

,                            ,

Множества  образуют убывающую последовательность:  для . Докажем по индукции, что каждое множество  бесконечно.

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

Итак, каждое множество  бесконечно. Отсюда следует, что  для всех . Если , то , а потому . Беря в качестве  множество всех значений последовательности , получаем , и, таким образом, теорема доказана, т.к. множество  бесконечно.

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

Замечание 1. Наглядно теорему Рамсея можно сформулировать следующим образом: если каждое из ребер полного графа , где - бесконечное множество, выкрасить в один их 2-х цветов, то будет содержать такое бесконечное множество , что все ребра графа  будут выкрашены в один и тот же цвет.

Замечание 2. Теорема Рамсея имеет свой аналог (ниже принадлежащий Рамсею) для конечных множеств:

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

Другими словами, если - граф над -элементным полем, то или , или  содержит полный подграф над -элементным полем.