XIX Белоусов А.И., Ткачев СБ. Дискретная математика (1081422), страница 15
Текст из файла (страница 15)
94 1. МНОЖЕСТВА И ОТНОШЕНИЯ Теорема 1.14. Пусть М вЂ” бесконечное множество, а И— его не более чем счетное подмножество. Если множество М ~ Ф бесконечно, то оно равномощно множеству М. ~ По теореме 1.10 в множестве М ~ Ф, поскольку оно бесконечно, можно выбрать счетное подмножество №. Ясно, что Ф ПИ> = Е1. Множество ФОФ> является счетным как объединение двух счетных множеств или объединение счетного и конечного множеств. Поэтому существует биекция у: ФО № ~ №. Поскольку (М~(>»'0№)) 0(ФО№) = М, М~ (ФО№) О№ = = М ~ Ж, то требуемую биекцню М на М ~ Ф строим так: на подмножестве М ~ (Ж О №), общем для М ~ Ф и М, эта биекция совпадает с тождественным отображением; на подмножестве Ф 0 № эта биекция есть биекция У. 1ь Следствие 1.1.
Если М вЂ” бесконечное множество, а Ф— не более чем счетное множество, то М МОИ. Существуют бесконечные множества, не являющиеся счетными. Это вытекает из следующих рассуждений. Рассмотрим множество всех последовательностей нулей и единиц, т.е.
последовательностей вида (>21, а2,..., а„,...), где а; Е (О> Ц для каждого 1) 1. Обозначим множество таких „двоичных" последовательностей через 10> Ц~. Теорема 1.15 (пзеорема Хангпора). Множество (О, Ц~ не есть счетное множество.
м Пусть множество (О, Ц~ счетное. Тогда существует биекция у: >ч' -+ (О, Ц~. Выпишем все последовательности >р(п): >Р(1) 1>.>11> >212» а1в> ° ")> Д(2) =1а21>а22»'''паз 1> >Р(п) = 1а»1> а»2» "° а»»> " ) > 1.9. М~ицжкть мяоиества 95 Построим последовательность |3 = ~Д,..., Д„...): положим Д =1, если ам=О, и Д =О, если он =1. Ясно, что эта последовательность не совпадает ни с одной из последовательностей у(п), а это противоречит допущению, что любая последовательность иэ (О, Ц~ есть у(й) для некоторого й.
Итак, М не равномощно (О, Ц~. В то же время (О, Ц~ содержит подмножество последовательностей, в каждой иэ которых только один член отличен от нуля. Это подмножество равномощно множеству всех одно- элементных подмножеств Я и, следовательно, самому М. Следовательно, множество (О, Ц бесконечно, но не равномощно счетному множеству и потому не является счетным. ° Теорема 1.16. Множество 2Н всех подмножеств множества натуральных чисел и множество 10, Ц~ равномощны. Определим отображение <р множества 2" на множество 10, Ц~ следующим образом: если Х С М, то у(Х); = 1 при 1 Е Х и у(Х), = 0 при ~ ф Х.
Тем самым подмножеству Х ставится в соответствие последовательность <р(Х), 1-й член которой равен единице тогда и только тогда, когда число 1 есть элемент множества Х. Докажем, что ср — биекция 2" на 10, Ц~. Покажем, что отображение у — инъекция. Пусть Х и У— различные подмножества Я. Тогда найдется число 1 Е Х 1 У или число у е У 1 Х. В первом случае в последовательности ~р(Х) 1-й член будет равен единице, а в последовательности фУ) — нулю.
Таким образом, у(Х) ~ <р(У). Во втором случае у(У)у = 1, у(Х)у — — 0 и опять у(Х) ф ~р(У). Следовательно, отображение у — инъекция. Покажем, что у — сюръекция. Возьмем произвольную последовательность а Е 10, Ц~. Образуем множество Ха = = (1: а; = Ц. Ясно, что у(Х,„) = а. Таким образом, для любой последовательности а Е 10, Ц~ существует подмножество Хв Е 2, такое, что у(Х,„) = а. Следовательно, у — сюръек- Н ция.
96 1. МНОЖЕСТВА И ОТНОШЕНИЯ Таким образом, мы показали, что у — биекция, а множества 2" и [О, 1)~ равномощны. ° Мощность множества 2и обозначают с и называют мои4- ностпью континуума, а любое множество, эквивалентное множеству 2", называют мнозтсестпаом мотиностпи нонтпинуума или нонтпинуалъным множестпаом.
Теорема 1.17. Множество действительных чисел отрезка [О, 1] равномощно множеству всех последовательностей нулей и единиц (О, 1)~. м Каждое действительное число из отрезка [О, Ц представим в виде бесконечной дроби в двоичной системе счисления. Число 1 представим в виде периодической дроби, содержащей бесконечное число единиц — О, 1(1).
Конечные рациональные дроби представим как бесконечные, дополнив справа бесконечным числом нулей. Таким образом, каждое число из [О, 1] представлено в виде последовательности нулей и единиц. Кроме этого, выбросим счетное множество всех периодических дробей вида О,аостт...стьО(1), поскольку каждая такая дробь представляет то же самое число, что и дробь О,стест1 ... аь1(0), где сн Е 10, Ц для всякого т =1,й. Легко видеть, что полученное таким образом множество двоичных дробей равномощно множеству С0,1) .в Следствие 1.2. [О, 1] 2".
~ Выше была доказана равномощность множеств (О, 1) и 2н. Тогда имеем [О, 1] 10, 1) ° 2н. ~ь Теорема 1.18. Следующие множества равномощны: 1) множество действительных чисел отрезка [О, 1]; 2) множество действительных чисел интервала (О, 1); 3) множество действительных чисел отрезка [а, Ь]; 4) множество действительных чисел интервала (а, (т); б) множество действительных чисел (числовая ось) Й; 97 1.9. Моящость миожестэо 6) множество всех подмножеств множества натуральных чисел 2". ~ Покажем равномощность множеств (О, 1] и (О, 1).
Иэ множества действительных чисел отрезка (О, 1] выделим двухэлементное подмножество (О, 1). Разностью этих множеств будет множество действительных чисел интервала (О, 1), и, согласно теореме 1.14, [О, 1] ° (О, 1). Отображение у = (Ь вЂ” а)х+ а задает биекцию множества (О, Ц на множество (а,6].
Следовательно, эти множества равномощны. Заметим, что аналогично доказывается равномощность (О, 1) и (а, Ь). Покажем, что (О, 1) й. Биекцию можно установить, на- 1 1 пример, с помощью функции у = — агс16х+ —. т 2 Поскольку равномощность (О, 1] и 2и ранее доказана, имеем (О, 1] ° (О, 1) ° (а, 6] ° (а, Ь) ° й ° 2и. Замечание 1.7. Заметим, что если в условиях теоремы 1.14 множество М несчетно, а Ж вЂ” его счетное подмножество, то множество М 1Ж бесконечно, ибо иначе получилось бы, что множество М = (М 1И) 0 М счетно как объединение конечного и счетного множеств.
Таким образом, можно утверждать, что для любого несчетного множества М и его не более чем счетного подмножества Ф имеет место равенство )М'1 Ф] = ]М]. До сих пор речь шла о равенстве мощностей. Однако мощности разных множеств можно в определенном смысле сравнивать, говоря о большей или меньшей мощности. Считают, что мощность множества А не превышает мощность множества В (]А] ~( ]В]), если А равномощно некоторому подмножеству множества В.
Можно показать, что иэ соотношений )А! < ]В] и ]В] < ]А] следует, что ]А] = ]В]. Мощность множества А считается строго меньшей мощности множества В (]А] < )В]), если множества А и В неравно- 98 1. МНОЖЕСТВА И ОТНОШЕНИЯ мощны и существует собственное подмножество С множества В, равномощное множеству А, т.е. (А ф В) и (ВС С В)(А ° С). Можно доказать, что из )А~ ~ ()В~ и ~В) < ~С~ следует )А] < < ~С~. Таким образом, на множестве всех мощностей (т.е. на множестве всех классов эквивалентности по отношению ° ) установлено отношение порядки Из определения сразу следует, что мощность любого конечного множества строго меньше мощности Ио, а нз доказательства теоремы 1.15 вытекает, что Ко < с. Кроме того, согласно теореме 1.9, мощность счетного множества Йо является нвименьшет1 на множестве всех бесконечных мощностей (т.е.
мощностей бесконечных множеств). Можно сказать, что всякое бесконечное множество не менее чем счетно. Вез доказательства приведем две важные теоремы. Теорема 1.19 (тпеоремп Кантора — Бернштпейна). Для любых двух множеств А и В имеет место в точности одно из следующих трех условий: либо ~А~ < ~В~, либо )В~ < ~А~, либо ~В~ = )А!. Таким образом, любые два множества сравнимы по мощности. Другими словами, „шкала мощностей" яинет1но упорядочена. Теорема 1.20. Для любого множества А верно неравенство ~2А~ ) )А~.
В силу теоремы 1.20 нет наибояьшет1 мощности, так как для любого множества А существует множество большей мощности — его булеан. Заметим, что для счетного множества А теорема 1.20 сводится к теореме Кантора 1.15. Теорема 1.21 (тпеорема о неадратпе). Для любого бесконечного множества М его декартпов квадрат М х М равно- мощен самому множеству М. ~ Доказательство проведем для частных случаев счетного и континуального множеств. 99 1.9. Мощность миожества Сначала обратимся к счетному множеству.
Для доказательства утверждения достаточно показать, что М х М М, т.е. задать на М х М некоторую нумерацию. Рассмотрим множество А; = ((1, у): ) Е М) упорядоченных пар. Это множество счетно по построению. Легко видеть, что справедливо равенство МхМ=ЦА;, откуда, согласно теореме 1.12, вытекает счетность д~сартова квадрата М х М множества М как счетного объединения счетных множеств. Перейдем к континузльному множеству. Докажем, что множество всех упорядоченных пар двоичных последовательностей эквивалентно множеству всех таких последовательностей, т.е. 2" х 2" 2". Паре последовательностей (а, ф) поставим в соответствие последовательность ае,,де, ам )9~, ..., а„, 4„...
Это соответствие будет взаимно однозначным, т.е. установлена биекция между 2и х 2~ и 2~. ~ Получается, что — как зто ни удивительно — в квадрате „столько же" точек, сколько и в каждой его стороне. Можно обобщить это утверждение для произвольной конечной декартовоб с~печени множества М. Следствие 1.3. Множество рациональных чисел Я счетно. С Каждому рациональному числу, представленному несократимой дробью †, однозначно соответствует упорядоченная пара (а, Ь), и, напротив, любая упорядоченная пара (а, Ь) взаимно простых целых чисел а и Ь однозначно определяет несократиа мую дробь — и, значит, рациональное число. Следовательно, множество Я эквимлентно некоторому бесконечному подмножеству множества Е х Е. Поскольку множество Е х Е счетно, из теоремы 1.11 вытекает, что любое его бесконечное подмножество счетно.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
