Теория множеств(пособие ЕНФ)(Водопьянов)

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

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

В этой гостинице бесконечно много номеров (комнат), но, как и положено, все комнаты пронумерованы, и для любого натурального числа n есть комната с этим номером.

Однажды в этой гостинице проходил съезд космозоологов, в котором участвовали представители всех галактик. Так как галактик тоже бесконечное множество, все места в гостинице оказались занятыми. Но в это время к директору гостиницы приехал его друг и попросил поселить его в эту гостиницу.

"После некоторых размышлений директор обратился к администратору и сказал:

–Поселите его в № 1.

–Куда же я дену жильца этого номера? – удивлённо спросил администра-

тор.

–А его переселите в № 2. Жильца же из № 2 отправьте в № 3, из № 3 – в

№4 и т. д."

Вообще, пусть постоялец, живущий в номере k, переедет в номер k+1, как это показано на следующем рисунке:

Тогда у каждого снова будет свой номер, а № 1 освободится.

Таким образом, нового гостя удалось поселить – именно потому, что номеров в гостинице бесконечно много.

Первоначально участники съезда занимали все номера гостиницы, следовательно, между множеством космозоологов и множеством N было установле-

но взаимно однозначное соответствие: каждому космозоологу дали по номеру, на двери которого написано соответствующее ему натуральное число. Естественно считать, что делегатов было "столько же", сколько имеется натуральных чисел. Но приехал ещё один человек, его тоже поселили, и количество проживающих увеличилось на 1. Но их снова осталось "столько же", сколько и натуральных чисел: ведь все поместились в гостиницу!

Мы пришли к удивительному выводу: если к множеству, которое равномощно N, добавить ещё один элемент, получится множество, которое снова

23

равномощно N. Но ведь совершенно ясно, что делегаты-космозоологи пред-

ставляют собой часть того множества людей, которые разместились в гостинице после приезда нового гостя. Значит, в этом случае часть не "меньше" целого, а "равна" целому!

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

Новый постоялец не удивился, когда на другое утро ему предложили переселиться в № 1000000. Просто в гостиницу прибыли запоздавшие космозоологи из галактики ВСК-3472, и надо было разместить ещё 999999 жильцов.

Но потом произошла какая-то накладка, и в эту же самую гостиницу приехали на съезд филателисты. Их тоже было бесконечное множество – по одному представителю от каждой галактики. Как же их всех разместить?

Эта задача оказалась весьма сложной. Но и в этом случае нашёлся выход. "В первую очередь администратор приказал переселить жильца из № 1 в

№ 2.

–А жильца из № 2 переселите в № 4, из № 3 – в № 6, вообще, из номера n

–в номер 2n.

Теперь стал ясен его план: таким путём он освободил бесконечное множество нечётных номеров и мог расселять в них филателистов. В результате чётные номера оказались занятыми космозоологами, а нечётные – филателистами... Филателист, стоявший в очереди n-м, занимал номер 2n-1". И снова всех удалось разместить в гостинице. Итак, ещё более удивительный эффект: при объединении двух множеств, каждое из которых равномощно N, вновь по-

лучается множество, равномощное N, т. e. даже при "удвоении" множества мы

получаем множество, эквивалентное исходному!

Определение. Множество А, равномощное множеству натуральных чисел N, называется счетным множеством (имеет мощность счетного множества).

Если множество В является бесконечным и не равномощно множеству N, то

его называют несчетным.

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

Пусть множество А является счетным. По определению, тогда существует биекция А на N, т.е. каждому а А соответствует единственный номер n N и

множество А обращается в некоторую последовательность {аn}.

Теорема 1. Любое подмножество счетного множества не более чем счет-

но.

Доказательство. Пусть А = {an} - счетное множество и В А. Если В конечное множество, то утверждение доказано. Предположим, что В бесконечное множество. Те элементы А, которые попали в В будут иметь некоторые номера

24

в порядке возрастания: ank . Тогда необходимая нам биекция, показывающая, что В является счетным множеством, задается в виде: an k k.

Теорема 2. Объединение конечного или счетного числа счетных множеств является счетным множеством.

Доказательство. Рассмотрим счетное объединение счетных множеств (случай конечного является частным). Итак, пусть Аn - счетные множества для любого n N и А = n Аn. Для доказательства нам необходимо указать биекцию

множества А на множество N, т.е. указать каждому а А его номер. Запишем

все множества А в виде последовательностей с двумя индексами, где первый указывает номер множества. Зададим закон, который каждому элементу А ставит в соответствие некоторый порядковый номер. Если элементы множества Аn обозначить через аnk, то высотой элемента аnk назовем число n + k. Перепишем элементы множества А, располагая все его элементы по следующему правилу - сперва перепишем все элементы высоты 2, затем высоты 3, 4 и т.д: а11, а12, а21,

а13, а22, а31, а14, а23, а32, а41, ... Тогда любой элемент множества А будет иметь определенный номер.

Теорема 3. Любое бесконечное множество содержит счетное подмноже-

ство.

Доказательство. Выберем в заданном множестве А какой-либо элемент, придав ему единичный индекс: а1. Среди всех оставшихся элементов множества А найдется не равный а1 элемент (в силу бесконечности А). Его мы обозначим через а2. Продолжая этот процесс до бесконечности мы получим необходимое нам счетное множество {an} .

Теорема 4. Пусть множество М - несчетно, множество А не более чем счетно и А М. Тогда множество М – А равномощно множеству М.

Доказательство. Пусть множество М – А не более чем счетно. Тогда множество М = А (М – А) по теореме 2 не более чем счетно. Это противоречит тому, что множество М несчетно и, следовательно, наше исходное предположение не верно. Таким образом, множество М – А несчетно. Последнее еще не означает равномощности множеств М и М – А. Докажем ее. Выделим из М – А счетное множество В. Обозначим через С множество С = (М – А) – В. Справедливы равенства М = А В С и М – А = В С. Множество А В счетно (теорема 2). Следовательно, существует биекция f из А В на А. Теперь можно построить биекцию g из М на М – А по правилу:

f(b), если b A B,
g(b) =	b, если b C.

Теорема 5. Если множество С бесконечно, а В не более чем счетно, то множество В С равномощно множеству С.

25

Доказательство. Если множество С счетно, то множество В С также счетно и следовательно они равномощны. Если же множество С не счетно, то мы можем воспользоваться теоремой 4, положив в ней А = С В, а М = С.

Теорема 6. Если множество С является бесконечным, то существует его подмножество В такое, что В С и В равномощно с С.

Доказательство. По теореме 3 мы можем выделить из множества С его счетное подмножество А. Если множество С счетно, то в качестве В из утверждения теоремы можно взять В=А. Если же С не счетно, то можно положить В=С-А и утверждаемое вытекает из теоремы 4.

Теорема 7. Множество рациональных чисел Q является счетным.

Доказательство. Обозначим через Р множество всех пар натуральных чисел (p, q), таких что p и q не имеют общих целых делителей, кроме единицы. Для пары натуральных чисел (p, q) введем ее высоту m = p + q. Обозначим Рn множество пар натуральных чисел высоты n. Нетрудно проверить, что каждое множество Рn является конечным и содержит не более, чем n-1 член. Так как Р =n Рn, то множество Р счетно в силу теоремы 2.

Рассмотрим теперь множество Q+ положительных рациональных чисел. Каждое положительное рациональное число представим в виде не сократимой дроби p/q. Тогда между этим числом и парами из Р существует биекция p/q (p,q), которая показывает равномощность множеств Q +и Р, т.е. счетность мно-

жества Q+. Ясно, что множества Q+ и Q - равномощны. Тогда Q = Q

+ Q - является счетным множеством как объединение двух счетных мно-

жеств.

Теорема 8. Множество точек интервала (0,1) является несчетным.

Доказательство (диагональный метод Кантора). Доказательство прове-

дем от противного, предположив, что множество точек интервала (0,1) является счетным. Тогда все точки можно записать в виде последовательности:

0,а11а12а12а14 ...

0,а21а22а23а24 ...

0,а31а32а33а34 ...

0,а41а42а43а44 ...

..........................

Покажем, что на самом деле здесь записаны не все числа из интервала (0,1). Построим число 0,а1а2а3а4 ... по правилу аk аkk . Это всегда можно сделать. Но тогда построенное нами число входит в интервал (0,1) и не совпадает ни с одним из записанных чисел. Мы получили противоречие с тем, что нами были выписаны все числа из интервала (0,1) и этим доказали теорему.

Множества, равномощные множеству точек интервала (0, 1), называются множествами мощности континуум.

Задачи.

26

1. Показать, что если множества А и В являются счетными, то и их произведение А В является счетным.

2. Установить биекцию между множеством N всех натуральных чисел и множеством Q всех четных положительных чисел.

3. Установить биекцию между множеством N всех натуральных чисел и множеством Р всех четных чисел.

§ 7. Сравнение мощностей

Теорема 1 (Кантора-Бернштейна). Пусть для множеств А и В существуют множества А1 А и В1 В такие, что множество А равномощно с В1, а множество В с А1, то множества А и В равномощны.

Доказательство. Пусть f - биекция В на А1, а g - биекция А на В1. Тогда f(В)=А1 и f(В1)=А2 А1. Суперпозиция h=fog функций является также биекцией А на А2. Тогда функция h отображает

А на А2 А1 А на А3 А

А2 А1 на А4 А3 А3 А2 на А5 А6 и т.д.

Отсюда следует, что h является биекцией

из А – А1 на А2 – А3 из А1 – А2 на А3 – А4

из А2 – А3 на А4 – А5 и т.д.

Зададим множества

Е = (А – А1) (А2 – А3) (А4 – А5) (А6 – А7) ...

F = (А2 – А3) (А4 – А5) (А6 – А7) ...

D = А А1 А2 А3 А4 ...

G = (А1 – А2) (А3 – А4) (А5 – А6) ...

Из замеченного выше следует, что h является биекцией E на F. Кроме того, справедливы равенства А = D G E и А = D G F. Следовательно отображение Т из А в А1, определяемое соотношением

a, если a D G,

T(a) =

h(a), если а E,

является биекцией А на А1, т.е. множества А и А1 равномощны. Последнее означает, что все четыре множества в теореме равномощны.

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

27

Доказательство. Обозначим множество функций, действующих из Х в У через УХ. Доказательство разобьем на две части. Сперва покажем, что существует инъекция множества Х на часть множества УХ. Пусть у1 У, у2 У, у1 у2 и х0 Х. Построим функцию f[х0] следующим образом: f[х0](х0) = у1, а если х х0, то f[х0] (х) = у2. При таком построении различным элементам в Х соответствуют различные функции. Например, если х1 х0, то f[х1](х0) = у2. Таким образом, получаем инъекцию из Х в УX.

Покажем теперь, что не существует биекции между Х и УX. Предположим противное, что g является биекцией из Х на УX и g(x) = fx УХ. Покажем, что существует f УХ такое, что f fх для любого х Х. Пусть х Х и fх УХ соответствующая функция. Определим f(х) = а У из условия а fх(x). Такой элемент а в У обязательно найдется, т.к. в У не менее двух элементов. Таким образом построенная функция f не будет совпадать ни с одной функцией f . Следовательно g не может быть биекцией.

Теорема 3. Множество всех подмножеств произвольного непустого множества Х имеет мощность большую, чем мощность множества Х.

Доказательство. Положим У={0,1}. Рассмотрим множество УХ. Если f УХ, то f разбивает Х на два множества: Х0(f) = {x X: f(x)=0} и Х1(f) = {x X: f(x) = 1}. Таким образом, каждому f УX соответствует множество Х1(f). Наоборот, если Х1 - некоторое подмножество из Х, то полагая

1,	если	х Х1,
f(x) =		х Х Х1 ,
0,	если

получим f УХ. Этим мы построили биекцию между множеством всех подмножеств множества Х и множеством УХ. Следовательно они равномощны и по теореме 2 мощность множества Х меньше мощности множества всех подмножеств.

Задачи.

1.Пусть А и В произвольные конечные множества, card(А)=n, card(В)=m. Доказать, что общее число отображений из А в В равно nm.

2.Пусть в условиях предыдущей задачи m n. Определить число биекций

иинъекций из А в В.

§ 8. Примеры равномощных множеств

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

Пример 1. Установить биекцию между отрезком [0, 1] и отрезком [а, в].

28

Решение. Легко устанавливается биективность линейного отображения x = (в – a)t + a отрезка [0, 1] на отрезок [а, в].

Пример 2. Установить биекцию между интервалом (0, 1) и интервалом (–

, + ).

Решение. Легко устанавливается биективность отображения x= ctg( t) интервала (0, 1) на интервал (– , + ).

Задача. Рассмотреть основные элементарные функции и найти промежутки, на которых они являются биективным отображением.

Пример 3. Построить биекцию между отрезком [0, 1] и интервалом (0, 1). Решение. Решение этой задачи основано на несчетности рассматриваемых множеств и теореме 4 из параграфа 6. Идея решения состоит в том, что из

интервала (0, 1) выделяют некоторое счетное множество А. Затем к нему добавляют две точки {0} и {1}. Вновь полученное множество (обозначим его В [0, 1]), также является счетным. Следовательно, множества А и В равномощны и существует биекция f, отображающая B на A. Построим теперь биекцию отрезка [0, 1] на интервал (0, 1) следующим образом:

f(x), если		х В,
g(x) =	х, если х В.

Пример 4. Построить биекцию между окружностью единичного радиуса и отрезком [0, 1].

Схема решения. Легко устанавливается биекция между точкой окружности и углом, соответствующим этой точке. Этим получается биекция окружности и полуотрезка [0, 2 ). Затем по схеме примера 3 строится биекция полуотрезка [0, 2 ) на отрезок [0, 1].

Пример 5. Доказать, что множество всех окружностей на плоскости, радиусы которых рациональные числа и координаты центра которых - рациональные числа, есть счетное множество.

Решение. Нетрудно видеть, что каждый элемент рассматриваемого множества может быть отождествлен с тройкой чисел (х, у, r), где (х, у) - координаты центра окружности, а r - ее радиус. Этим между множеством указанных окружностей и множеством Q Q Q устанавливается биекция. Но произведе-

ние счетных множеств счетно (см. задачу в 6 параграфе) и, следовательно, наше множество также счетно.

Пример 6. Доказать, что множество точек разрыва монотонной функции, заданной на отрезке [а, в], конечно или счетно.

Решение. Предположим, что рассматриваемая функция f(х) является возрастающей. Пусть х точка разрыва этой функции. В силу монотонности функции и ее ограниченности ( f(а) < f(х) < f(в) ) в точке х будет существовать как

предел слева, так и предел справа: lim	f (x) A	B	lim f (x) Таким образом,
x x			x x

множество точек разрыва { х } может быть отождествлено с множеством от-

29

резков{[A , B ]}. При этом необходимо заметить, получаемые отрезки могут пересекаться лишь на концах и все они лежат на отрезке [f(а), f(в)]. Поставим каждому отрезку [А , В ] в соответствие рациональное число у , выбрав в качестве такового произвольное рациональное число из интервала (А , В ) (наличие такое числа гарантируется аксиомой непрерывности действительных чисел и тем, что А В ). В силу отмеченного выше, построенное соответствие будет являться инъекцией. Следовательно, мы построили инъекцию множества точек разрыва монотонной функции на отрезке [а, в] в счетное множество рациональных точек отрезка [f(а), f(в)]. Это означает, что рассмотренное множество точек разрыва не более чем счетно.

Задачи.

1. Существует ли функция вида	a0	a1 x+ ...+ a n xn
	f(x) = b0	(где коэф-
		b1 x+ ...+ bn xn

фициенты a0, a1, ..., an; b0, b1, ..., bn - целые числа), обладающая следующим свойством: для любого рационального числа r найдется такое целое число k, что f(k)=r.

2.Найти биекцию числовой прямой на интервал (а, в).

3.Найти биекцию полуотрезка [0, 1) на полуось [0, ).

4.Построить биекцию отрезка [0, 1] на всю числовую ось.

5.Существует ли непрерывная функция, являющаяся биекцией отрезка [а, в] на всю числовую ось?

6.Существует ли непрерывная функция, являющаяся биекцией отрезка [а, в] на интервал (с, d)?

7.Установить биекцию между открытым и замкнутым единичным кру-

гом.

8.Какова мощность множества всех треугольников на плоскости, вершины которых имеют рациональные координаты?

9.Какова мощность множества всех рациональных функций с целыми коэффициентами в числителе и знаменателе?

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

11.Пусть Е - счетное множество точек на прямой. Можно ли так сдвинуть

это множество на величину а (т.е. заменить все точки х Е точками х + а), чтобы получившееся в результате сдвига множество Еa не пересекалось с Е?

12.Пусть Е – счетное множество точек на окружности. Можно ли повернуть окружность вокруг центра на некоторый угол так, чтобы множество Е , получившееся из Е в результате поворота, не пересекалось с Е?

13.Доказать, что если расстояние между любыми двумя точками множества Е на прямой больше единицы, то множество Е не более чем счетно.

14.Какова мощность множества всех строго возрастающих последовательностей натуральных чисел?

30

15.Какова мощность множества всех последовательностей натуральных чисел, не содержащих число 7?

16.Какова мощность множества всех многочленов (с произвольными вещественными коэффициентами)?

17.Какова мощность множества всех отрезков на числовой прямой?

18.На числовой прямой задано множество попарно непересекающихся отрезков. Какова его мощность?

19.Какова мощность множества всех строго возрастающих непрерывных функций на отрезке [а, в]?

20.Доказать, что если А – В равномощно В – А, то А и В равномощны.

21.Доказать, что если А В и А равномощно А С, то В равномощно

В С.

22.Верно или нет утверждение: “Если А равномощно С, В равномощно

D, причем А В, С D, то А – В равномощно С – D”?

23.Доказать, что множество всех конечных подмножеств счетного множества – счетно.

24.Какова мощность множества всех конечных и счетных подмножеств множества Е, если Е имеет мощность континуума?

§ 9. Отношение порядка

Определение. Отношение r в множестве Х, удовлетворяющее условиям:

1)хrх для х Х (рефлексивность);

2)из хrу и уrх следует, что х=у (антисимметрия);

3)из хrу и уrz следует, что хrz (транзитивность).

называется частичным порядком на Х.

Пример. 1) Обычное отношение (или ) на множестве всех чисел;

2)х является целым кратным у, где х и у из N;

3)отношение включения для множеств на множестве всех подмножеств. Определение. Отношение r на Х, удовлетворяющее условиям:

1)хrх для х Х;

2)из хrу и уrz следует хrz.

называется предпорядком.

Пример. На некотором множестве людей отношением предпорядка яв-

ляются: а) рост одного человека больше или равен росту другого; б) вес одного человека больше или равен весу другого.

Если на множестве Х задано отношение предпорядка r, то полагая, что хsу, если хrу и уrх, получим отношение эквивалентности s на Х (проверить самостоятельно). Эквивалентность s разбивает Х на классы эквивалентности [x]. Обозначим через [X] - множество всех классов эквивалентности в Х. На [X]

31

предпорядок r порождает отношение частичного порядка t по правилу [x]t[y],

если х1 [x] и у1 [y]: x1rу1. Если х2 [x], то х2sх1, т.е. х2rх1 и х1rу1, следовательно, х2rу1. Последнее означает, что [x]t[y] тогда и только тогда, когда для х [x]

и у [y] выполняется хrу. Проверьте самостоятельно, что t является отношением частичного порядка на [X].

Определение. Отношение r в Х называется строгим порядком, если это отношение обладает свойствами

1)отношение хrх не верно ни для одного х Х (иррефлексивность);

2)из хrу и уrz следует хrz.

Если на множестве Х задан частичный порядок r, то он порождает на Х отношение строгого порядка t по правилу: хtу тогда и только тогда, когда хrу и х у. Верно и обратное: отношение строгого порядка порождает отношение частичного порядка (каким образом?).

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

Множество Х, на котором введено отношение частичного порядка r, называется линейно упорядоченным (или цепью), если для х,у Х выполнено одно из отношений: либо хrу, либо уrх.

Пусть Х - множество с частичным порядком r, а М Х. Тогда у Х называется левой гранью множества М, если уrх для х М. Если же z Х и хrz для

х М, то z называют правой гранью множества М.

Определение. у Х называется точной левой гранью множества М Х,

если

1)уrх для х М;

2)zrу для z Х: zrх.

Определение. у Х называется точной правой гранью множества

М Х, если:

1)хrу для х М;

2)уrz для z Х: zrх.

Определение. у М называется правым экстремальным (левым) эле-

ментом множества М Х, если: хrу (соответственно, уrх) для х М.

Задачи.

1.Показать, что если r является отношением частичного порядка, то r-1 также есть частичный порядок.

2.На множестве всех непрерывных функций на отрезке [а, в] введем от-

ношение f=О(g)по определению: для всех х [а, в] выполняется неравенство f(х) Мg(х) для некоторого М. Показать, что таким образом введеное отношение является предпорядком.

32