Лекции и упражнения
жүктеу/скачать 1,95 Mb. Pdf көрінісі
|
Matan Lectures 2013
Глоссарий(кәсіпкерлік) СӨЖ, 6 тақырып, 1-сабақ. Оразәлі Шайра (1), Саттархан АЛТЫНХАН 4-апта, access -9week, Семинар 15 алгебра, Методичка по препаратам при первой помощи, Копия Новая презентация
ГЛАВА 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 . Противоречие. |