Если рассмотреть любое конечное множество и любое его собственное (непустое и не совпадающее с ним самим) подмножество, то элементов в подмножестве меньше, чем в самом множестве, т. е. часть меньше целого.
Обладают ли бесконечные множества таким свойством? И может ли иметь смысл утверждение, что в одном бесконечном множестве «меньше» элементов, чем в другом, тоже бесконечном? Ведь про два бесконечных множества мы можем пока только сказать, эквивалентны они или нет. A существуют ли вообще неэквивалентные бесконечные множества?
Приведем забавную фантастическую историю из книги
Н. Я. Виленкина «Рассказы о множествах». Действие происходит в далеком будущем, когда жители разных галактик могут встречаться друг с другом. Поэтому для всех путешествующих по космосу построена огромная гостиница, протянувшаяся через несколько галактик.
В этой гостинице бесконечно много номеров (комнат), но, как и положено, все комнаты пронумерованы, и для любого натурального числа n есть комната с этим номером.
Однажды в этой гостинице проходил съезд космозоологов, в котором участвовали представители всех галактик. Так как галактик тоже бесконечное множество, все места в гостинице оказались занятыми. Но в это время к директору гостиницы приехал его друг и попросил поселить его в эту гостиницу.
После некоторых размышлений директор обратился к администратору и сказал:
– Поселите его в № 1.
– Куда же я дену жильца этого номера? – удивленно спросил администратор.
– A его переселите в № 2. Жильца же из № 2 отправьте в № 3, из № 3 – в № 4 и т. д.
Вообще, пусть постоялец, живущий в номере k, переедет в номер k+1, как это показано на следующем рисунке:
Тогда у каждого снова будет свой номер, а № 1 освободится.
Таким образом, нового гостя удалось поселить именно потому, что номеров в гостинице бесконечно много.
Первоначально участники съезда занимали все номера гостиницы, следовательно, между множеством космозоологов и множеством N было установлено взаимно однозначное соответствие: каждому космозоологу дали по номеру, на двери которого написано соответствующее ему натуральное число. Естественно считать, что делегатов было «столько же», сколько имеется натуральных чисел. Но приехал еще один человек, его тоже поселили, и количество проживающих увеличилось на 1. Но их снова осталось «столько же», сколько и натуральных чисел: ведь все поместились в гостиницу!
Мы пришли к удивительному выводу: если к множеству, которое равномощно N, добавить еще один элемент, получится множество, которое снова равномощно N. Но ведь совершенно ясно, что делегаты-космозоологи представляют собой часть того множества людей, которые разместились в гостинице после приезда нового гостя. Значит, в этом случае часть не «меньше» целого, а «равна» целому!
Итак, из определения эквивалентности (которое не приводит ни к каким странностям в случае конечных множеств) следует, что часть бесконечного множества может быть эквивалентна всему множеству.
Новый постоялец не удивился, когда на другое утро ему предложили переселиться в № 1 000 000. Просто в гостиницу прибыли запоздавшие космозоологи из галактики ВCК-3472, и надо было разместить еще 999 999 жильцов.
Но потом произошла какая-то накладка, и в эту же самую гостиницу приехали на съезд филателисты. Их тоже было бесконечное множество – по одному представителю от каждой галактики. Как же их всех разместить?
Эта задача оказалась весьма сложной. Но и в этом случае нашелся выход.
«В первую очередь администратор приказал переселить жильца из № 1 в № 2.
– A жильца из № 2 переселите в № 4, из № 3 – в № 6, вообще, из номера n – в номер 2n.
Теперь стал ясен его план: таким путем он освободил бесконечное множество нечетных номеров и мог расселять в них филателистов. В результате четные номера оказались занятыми космозоологами, а нечетные – филателистами... Филателист, стоявший в очереди n-м, занимал номер 2n – 1». И снова всех удалось разместить в гостинице. Итак, еще более удивительный эффект: при объединении двух множеств, каждое из которых равномощно N, вновь получается множество, равномощное N, т. e. даже при «удвоении» множества мы получаем множество, эквивалентное исходному!
Определение. Множество A, равномощное множеству натуральных чисел N, называется счетным множеством (имеет мощность счетного множества). Мощность счетного множества обозначается алеф-нуль À (алеф – первая буква древнееврейского алфавита). Если множество В является бесконечным и не равномощно множеству N, то его называют несчетным.
Множество, которое является конечным или счетным, еще называют не более чем счетным.
Пусть множество A является счетным. По определению, тогда существует биекция A на N, т. е. каждому аÎA соответствует единственный номер nÎN и множество A обращается в некоторую последовательность {а n}.
Теорема 1. Любое подмножество счетного множества не более чем счетно.
Доказательство. Пусть A = {an} – счетное множество и ВÍA. Если В конечное множество, то утверждение доказано. Предположим, что В – бесконечное множество. Те элементы A, которые попали в В, будут иметь некоторые номера в порядке возрастания: 
. Тогда необходимая нам биекция, показывающая, что В является счетным множеством, задается в виде: 
®k.
Теорема 2. Объединение конечного или счетного числа счетных множеств является счетным множеством.
Доказательство. Рассмотрим счетное объединение счетных множеств (случай конечного является частным). Итак, пусть A n – счетные множества для любого nÎN и A = Èn An. Для доказательства нам необходимо указать биекцию множества A на множество N, т. е. указать каждому аÎA его номер. Запишем все множества A в виде последовательностей с двумя индексами, где первый указывает номер множества. Зададим закон, который каждому элементу A ставит в соответствие некоторый порядковый номер. Если элементы множества An обозначить через а nk, то высотой элемента а nk назовем число n + k. Перепишем элементы множества A, располагая все его элементы по следующему правилу – сперва перепишем все элементы высоты 2, затем высоты 3, 4 и т. д: а11, а12, а21, а13, а22, а31, а14, а23, а32, а41, ... Тогда любой элемент множества A будет иметь определенный номер.
Теорема 3. Любое бесконечное множество содержит счетное подмножество.
Доказательство. Выберем в заданном множестве A какой-либо элемент, придав ему единичный индекс: а1. Cреди всех оставшихся элементов множества A найдется не равный а1 элемент (в силу бесконечности A). Его мы обозначим через а2. Продолжая этот процесс до бесконечности, мы получим необходимое нам счетное множество {a n}.
Теорема 4. Пусть множество М – несчетно, множество A не более чем счетно и AÍМ. Тогда множество М – A равномощно множеству М.
Доказательство. Пусть множество М – A не более чем счетно. Тогда множество М = AÈ(М – A) по теореме 2 не более чем счетно. Это противоречит тому, что множество М несчетно и, следовательно, наше исходное предположение не верно. Таким образом, множество М – A несчетно. Последнее еще не означает равномощности множеств М и М – A. Докажем ее. Выделим из М – A счетное множество В. Обозначим через С множество С = (М – A) – В. Cправедливы равенства М = AÈВÈС и М – A = ВÈС. Множество AÈВ счетно (теорема 2). Cледовательно, существует биекция f из AÈВ на A. Теперь можно построить биекцию g из М на М – A по правилу:
Теорема 5. Если множество С бесконечно, а В не более чем счетно, то множество ВÈС равномощно множеству С.
Доказательство. Если множество С счетно, то множество ВÈС также счетно и следовательно они равномощны. Если же множество С не счетно, то мы можем воспользоваться теоремой 4, положив в ней A = СÇВ, а М = C.
Теорема 6. Если множество C является бесконечным, то существует его подмножество В такое, что В¹C и В равномощно с C.
Доказательство. По теореме 3 мы можем выделить из множества C его счетное подмножество A. Если множество C счетно, то в качестве В из утверждения теоремы можно взять В = A. Если же C не счетно, то можно положить В = C – A и утверждаемое вытекает из теоремы 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), называются множествами мощности континуум.
Задачи.
1. Показать, что если множества A и В являются счетными, то и их произведение A ´ В является счетным.
2. Установить биекцию между множеством N всех натуральных чисел и множеством Q всех четных положительных чисел.
3. Установить биекцию между множеством N всех натуральных чисел и множеством Р всех четных чисел.
Сравнение мощностей
Теорема 1 (Кантора–Бернштейна). Пусть для множеств A и В существуют множества A1ÍA и В1ÍВ такие, что множество A равномощно с В1, а множество В с A1, то множества A и В равномощны.
Доказательство. Пусть f – биекция В на A1, а g – биекция A на В1. Тогда f(В) = A1 и f(В1) = A2ÍA1. Суперпозиция h = fog функций является также биекцией A на A2. Тогда функция h отображает
A на A2
A1Í A на A3ÍA
A2Í A1 на A4Í A3
A3ÍA2 на A5ÍA6 и т. д.
Отсюда следует, что h является биекцией
из A – A1 на A2 – A3
из A1 – A2 на A3 – A4
из A2 – A3 на A4 – A5 и т. д.
Зададим множества
Е = (A – A1)È(A2 – A3)È(A4 – A5)È(A6 – A7)È ...
F = (A2 – A3)È(A4 – A5)È(A6 – A7)È ...
D = AÇA1Ç A2Ç A3ÇA4Ç ...
G = (A1 – A2)È( A3 – A4)È(A5 – A6)È ...
Из замеченного выше следует, что h является биекцией E на F. Кроме того, справедливы равенства A = DÈGÈE и A = DÈGÈF. Cледовательно, отображение Т из A в A1, определяемое соотношением
является биекцией A на A1, т. е. множества A и A1 равномощны. Последнее означает, что все четыре множества в теореме равномощны.
Теорема 2. Пусть Х и Y два множества такие, что Х¹Æ, Y¹Æ и в Y не менее двух элементов. Тогда множество всех функций, действующих из Х в Y , является множеством, мощность которого больше мощности множества Х.
Доказательство. Обозначим множество функций, действующих из Х в Y, через YХ. Доказательство разобьем на две части. Сперва покажем, что существует инъекция множества Х на часть множества YХ. Пусть у1ÎY, у2ÎY, у1¹у2 и х0ÎХ. Построим функцию f[х0] следующим образом: f[х0](х0) = у1, а если х¹х0, то f[х0] (х) = у2. При таком построении различным элементам в Х соответствуют различные функции. Например, если х1¹х0, то f[х1](х0) = у2. Таким образом, получаем инъекцию из Х в YX.
Покажем теперь, что не существует биекции между Х и YX. Предположим противное, что g является биекцией из Х на YX и g(x) = 
ÎYX. Покажем, что существует fÎYX такое, что 
для любого хÎХ. Пусть хÎХ и 
ÎYX соответствующая функция. Определим f(х) = аÎY из условия а¹ (x). Такой элемент а в Y обязательно найдется, так как в Y не менее двух элементов. Таким образом построенная функция f не будет совпадать ни с одной функцией f. Cледовательно, g не может быть биекцией.
Теорема 3. Множество всех подмножеств произвольного непустого множества Х имеет мощность большую, чем мощность множества Х.
Доказательство. Положим Y = {0,1}. Рассмотрим множество YX . Если fÎYX, то f разбивает Х на два множества:
(f) = {xÎX: f(x)=0} и 
(f) = {xÎX: f(x) = 1}.
Таким образом, каждому fÎYX соответствует множество 
(f). Наоборот, если – некоторое подмножество из Х, то полагая, что
получим fÎYX. Этим мы построили биекцию между множеством всех подмножеств множества Х и множеством YX. Cледовательно, они равномощны и по теореме 2 мощность множества Х меньше мощности множества всех подмножеств.
Задачи.
1. Пусть A и В произвольные конечные множества, card(A) = n, card(В) = m. Доказать, что общее число отображений из A в В равно n m.
2. Пусть в условиях предыдущей задачи m³n. Определить число биекций и инъекций из A в В.
Примеры равномощных множеств
Приведенные выше примеры и теоремы показывают, что установить равномощность различных множеств далеко не просто. В этом параграфе мы рассмотрим примеры построения биекции между различными множествами. Будут приведены примеры доказательств равномощности ряда множеств.
Пример 1. Установить биекцию между отрезком [0, 1] и отрезком [а, b].
Решение. Легко устанавливается биективность линейного отображения x = (b – a)t + a отрезка [0, 1] на отрезок [а, b].
Пример 2. Установить биекцию между интервалом (0, 1) и интервалом (–¥, +¥).
Решение. Легко устанавливается биективность отображения
x = ctg(pt) интервала (0, 1) на интервал (–¥, +¥).
Задача. Рассмотреть основные элементарные функции и найти промежутки, на которых они являются биективным отображением.
Пример 3. Построить биекцию между отрезком [0, 1] и интервалом (0, 1).
Решение. Решение этой задачи основано на несчетности рассматриваемых множеств и теореме 4 из параграфа 6. Идея решения состоит в том, что из интервала (0, 1) выделяют некоторое счетное множество A. Затем к нему добавляют две точки {0} и {1}. Вновь полученное множество (обозначим его ВÌ[0, 1]), также является счетным. Cледовательно, множества A и В равномощны и существует биекция f, отображающая B на A. Построим теперь биекцию отрезка [0, 1] на интервал (0, 1) следующим образом:
Пример 4. Построить биекцию между окружностью единичного радиуса и отрезком [0, 1].
Схема решения. Легко устанавливается биекция между точкой окружности и углом, соответствующим этой точке. Этим получается биекция окружности и полуотрезка [0, 2p). Затем по схеме примера 3 строится биекция полуотрезка [0, 2p) на отрезок [0, 1].
Пример 5. Доказать, что множество всех окружностей на плоскости, радиусы которых – рациональные числа и координаты центра которых ‒ рациональные числа, есть счетное множество.
Решение. Нетрудно видеть, что каждый элемент рассматриваемого множества может быть отождествлен с тройкой чисел (х, у, r), где (х, у) – координаты центра окружности, а r – ее радиус. Этим между множеством указанных окружностей и множеством Q ´ Q ´ Q устанавливается биекция. Но произведение счетных множеств счетно (см. задачу в параграфе 6) и, следовательно, наше множество также счетно.
Пример 6. Доказать, что множество точек разрыва монотонной функции, заданной на отрезке [а, b], конечно или счетно.
Решение. Предположим, что рассматриваемая функция f(х) является возрастающей. Пусть хa точка разрыва этой функции. В силу монотонности функции и ее ограниченности (f(а)<f(х)<f(b)) в точке хa будет существовать как предел слева, так и предел справа: 
Таким образом, множество точек разрыва {хa} может быть отождествлено с множеством отрезков{[Aa, Ba]}. При этом необходимо заметить, получаемые отрезки могут пересекаться лишь на концах и все они лежат на отрезке [f(а), f(b)]. Поставим каждому отрезку [Аa, Вa] в соответствие рациональное число уa, выбрав в качестве такового произвольное рациональное число из интервала (Аa, Вa) (наличие такое числа гарантируется аксиомой непрерывности действительных чисел и тем, что Аa¹Вa). В силу отмеченного выше, построенное соответствие будет являться инъекцией. Cледовательно, мы построили инъекцию множества точек разрыва монотонной функции на отрезке [а, b] в счетное множество рациональных точек отрезка [f(а), f(b)]. Это означает, что рассмотренное множество точек разрыва не более чем счетно.
Задачи.
1. Существует ли функция вида 
(где коэффициенты a0, a1, ..., a n; b0, b1, ..., b n – целые числа), обладающая следующим свойством: для любого рационального числа r найдется такое целое число k, что f(k) = r.
2. Найти биекцию числовой прямой на интервал (а, b).
3. Найти биекцию полуотрезка [0, 1) на полуось [0, ¥).
4. Построить биекцию отрезка [0, 1] на всю числовую ось.
5. Существует ли непрерывная функция, являющаяся биекцией отрезка [а, b] на всю числовую ось?
6. Существует ли непрерывная функция, являющаяся биекцией отрезка [а, b] на интервал (с, d)?
7. Установить биекцию между открытым и замкнутым единичным кругом.
8. Какова мощность множества всех треугольников на плоскости, вершины которых имеют рациональные координаты?
9. Какова мощность множества всех рациональных функций с целыми коэффициентами в числителе и знаменателе?
10. Доказать, что множество точек разрыва монотонной функции, определенной на всей числовой прямой, не более чем счетно.
11. Пусть Е – счетное множество точек на прямой. Можно ли так сдвинуть это множество на величину а (т. е. заменить все точки хÎЕ точками х + а), чтобы получившееся в результате сдвига множество Еa не пересекалось с Е?
12. Пусть Е – счетное множество точек на окружности. Можно ли повернуть окружность вокруг центра на некоторый угол j так, чтобы множество Еj, получившееся из Е в результате поворота, не пересекалось с Е?
13. Доказать, что если расстояние между любыми двумя точками множества Е на прямой больше единицы, то множество Е не более чем счетно.
14. Какова мощность множества всех строго возрастающих последовательностей натуральных чисел?
15. Какова мощность множества всех последовательностей натуральных чисел, не содержащих число 7?
16. Какова мощность множества всех многочленов (с произвольными вещественными коэффициентами)?
17. Какова мощность множества всех отрезков на числовой прямой?
18. На числовой прямой задано множество попарно непересекающихся отрезков. Какова его мощность?
19. Какова мощность множества всех строго возрастающих непрерывных функций на отрезке [а, b]?
20. Доказать, что если A – В равномощно В – A, то A и В равномощны.
21. Доказать, что если AÍВ и A равномощно AÈC, то В равномощно ВÈC.
22. Верно или нет утверждение: «Если A равномощно C, В равномощно D, причем AÊВ, CÊD, то A – В равномощно C – D?»
23. Доказать, что множество всех конечных подмножеств счетного множества – счетно.
24. Какова мощность множества всех конечных и счетных подмножеств множества Е, если Е имеет мощность континуума?
Отношение порядка
Определение. Отношение 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] предпорядок r порождает отношение частичного порядка t по правилу [x]t[y], если $х1Î[x] и у1Î[y]:x1rу1. Если х2Î[x], то х2sx1, т. е. х2r x1 и x1rу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 является отношением частичного порядка, то 
также есть частичный порядок.
2. На множестве всех непрерывных функций на отрезке [а, b] введем отношение f = О(g) по определению: для всех хÎ[а, b] выполняется неравенство f(х)£Мg(х) для некоторого М. Показать, что введенное таким образом отношение является предпорядком.
Дата: 2019-04-23, просмотров: 268.
