Лекции и упражнения
жүктеу/скачать 1,95 Mb. Pdf көрінісі
|
Matan Lectures 2013
ГЛАВА 5. МОЩНОСТЬ МНОЖЕСТВА проще попросить школьников сесть на стулья. Если остались свободные стулья, значит стульев больше чем школьников, если кому-то не хва- тило стула, значит школьников больше. А если не останется ни свобод- ных стульев, ни школьников, которым не досталось стула, то, значит, школьников и стульев поровну. Определение 49. Множества A и B называются равномощными, если существует взаимно однозначное соответствие (т.е. биекция) между их эле- ментами. При этом каждому элементу a ? A ставится в соответствие один элемент b = f ( a ) ? B и каждому b ? B соответствует ровно один элемент a ? A , такой, что f ( a ) = b . Напомним, что инъекцией называется отображение f , которое переводит разные элементы в разные, т.е. если x 1 6 = x 2 , то f ( x 1 ) 6 = f ( x 2 ) . Например, отображение f 1 ( x ) = x 3 является инъекцией, а f 2 ( x ) = x 2 нет. Сюръекци- ей называется отображение X ? Y , которое ѕнакрываетї все множество Y , т.е. ? y ? Y ? x ? x : f ( x ) = Y 2 . Например, отображение f 1 ( x ) = x 3 является сюръекцией, а f 2 ( x ) = x 2 нет. Биекцией (взаимно однозначным отображе- нием) называется отображение которое является одновременно инъекцией и сюръекцией. Обозначается мощность множества | A | , если множество конечное, то | A | = n число элементов множества. Для мощности бесконечных мно- жеств некоторые обозначения будут приведены позднее. Будем говорить, что мощность множества A не превосходит мощности B и обозначать | A | ? | B | (или | B | ? | A | ), если существует инъекция из A в B . Если | A | ? | B | и множества не являются равномощными, то будем говорить что A множество меньшей мощности, чем B и обозначать | A | < | B | (или | B | > | A | ). Пример 16. Рассмотрим множество [0 , 1] и множество [0 , 1) . Казалось бы, во втором на одну точку меньше, но, оказывается, эти множества равномощны. Построим следующую функцию: f ( x ) = ( x, если x 6 = 1 , 1 2 , 1 4 , . . . , 1 2 k , . . . 1 2 k +1 , если x = 1 2 k . Она переводит 1 ? 1 2 , 1 2 ? 1 4 , и т. д. Таким образом, каждому элементу [0 , 1] ставится в соответствие элемент [0 , 1) и наоборот. Определение 50. Множество, равномощное множеству натуральных чи- сел называется счетным. Его мощность обозначается символом ? 0 (чита- ется алефноль). Хорошим примером, иллюстрирующим свойства счетных множеств, яв- ляется так называемый отель Гильберта. Предположим, что где-то далеко, 2 Это определение, вообще говоря, зависит от Y . Так, например, f ( x ) = ? x не является сюръекцией если рассматривать его как отображение R ? R , но является таковой как отображение [0 , + ? ) ? [0 , + ? ) . 5.1. СЧЕТНЫЕ МНОЖЕСТВА. 67 на краю Галактики расположен отель, в котором бесконечное число номе- ров (одноместных), все они пронумерованы: 1,2,3, . . . , 2014, . . . Допустим, что все номера заняты постояльцами. Прибывает еще один постоялец. Мож- но ли его поселить в отеле? Оказывается можно! Переселим постояльца из первого номера во второй, из второго в третий, . . . из 2014-го в 2015-й, и т. д. Тогда первый номер освободится, в него можно будет поселить нового постояльца. Пусть на следующий день прибыло 100 постояльцев. Найдется ли место для них? Конечно! Переселяем 1 ? 101 , 2 ? 102 , . . . 2013 ? 2113 . В итоге первые 100 номеров свободны туда и селим новых постояльцев. Но на следующий день прибывает уже бесконечное число постояльцев! Ку- да их поселить? Переселяем 1 ? 2 , 2 ? 4 , . . . 2013 ? 4026 ,. . . В результате становятся свободны все комнаты с нечетными номерами, а их бесконечное число. Там и разместятся вновь прибывшие. Допустим теперь, что постоялец комнаты ќ2014 решил покинуть отель. Чтобы номер не простаивал переселим 2015 ? 2014 , 2016 ? 2015 , . . . и опять все номера заняты! Допустим, что захотели уехать все постояльцы, занимающие комнаты с простыми номерами 2, 3, 5, 7, 11, . . . Как вы, наверное, знаете, простых чисел бесконечно много 3 . Переселим оставшихся постояльцев следующим образом: 4 ? 2 , 6 ? 3 , 8 ? 4 , 9 ? 5 , 10 ? 6 , . . . и т.д. Более формально, пусть p ( x ) количество простых чисел, не превосходящих x . Тогда пересе- ляем x ? x ? p ( x ) . В результате все номера снова заняты. Лемма 1. Подмножество счетного множества является конечным или счетным. Доказательство. Пусть B ? A , если оно конечно, то лемма доказана; предположим, что оно бесконечно. Занумеруем элементы множества A = { a 1 , a 2 , . . . , a n , . . . } сле- дующим образом: пусть f (1) наименьший номер k 1 , такой, что a k 1 ? B . Далее, f (2) наименьший номер k 2 6 = k 1 , такой, что a k 2 ? B . И так далее, f ( n ) наименьший номер k n 6 = k 1 , . . . , k n ? 1 , такой, что a k 2 ? B . Отобра- жение f : N 7? B является биекцией, т.к. любой элемент b ? B является элементом A с каким-то номером € k , следовательно, будет рассмотрен на некотором шаге. Следствие 2. Пусть существует инъекция f : A 7? N , тогда A ко- нечное или счетное. Действительно, рассмотрим подмножество Y ? N , заданное следующим образом: Y = { y = f ( a ) : a ? A } . Тогда по лемме 1 множество Y конечно или счетно, причем f : A ? Y биекция, т.е. | A | = | Y | . Лемма 2. Объединение конечного и счетного множеств является счет- ным. 3 А если не знаете, то вот доказательство Евклида: Предположим, что простых чисел конечное количество: p 1 , . . . , p n . Тогда рассмотрим число N = p 1 · p 2 · . . . · p n + 1 . У него должен быть простой делитель (или оно само простое), не совпадающий ни с одним из p 1 , . . . , p n . Противоречие. |