Следствие 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. Теорема Рамсея имеет свой аналог (ниже принадлежащий Рамсею) для конечных множеств:
Для любого натурального числа найдётся такое натуральное число , что если множество имеет менее элементов, то для каждого графа существует такое подмножество , содержащее элементов, что или .
Другими словами, если - граф над -элементным полем, то или , или содержит полный подграф над -элементным полем.
Дата добавления: 2018-04-04; просмотров: 404; Мы поможем в написании вашей работы! |
Мы поможем в написании ваших работ!