Президентская программа “Дети России”

Министерство общего и профессионального образования

Российской Федерации

Уральский государственный университет

им. А.М. Горького

Специализированный учебно-научный центр

С.А. Ануфриенко

Введение в теорию множеств

и комбинаторику

Учебное пособие

Екатеринбург

1998 УДК 510.22(075.3) А 733 Пособие разработано в рамках федеральной программы “Одаренные дети” по гранту “Развитие российской системы предуниверситетского образования одаренных детей ведущими университетами России” при финансовой поддержке исполнительной дирекции по Президентской программе “Дети России” и Уральского государственного университета им. А.М.Горького Ануфриенко С.А. Введение в теорию множеств и комбинаторику: Учеб. пособие.

Екатеринбург: УрГУ, 1998. 62с.

Рецензенты: канд. физ.-мат. наук М.И. Альперин, науч. сотр. ИММ УрО РАН, канд. физ.-мат. наук С.Э. Нохрин Пособие является элементарным введением в наивную, или канторовскую, теорию множеств. Наряду с традиционными для теории множеств конструкциями представлен единый подход (с помощью продолжений отображений) при доказательстве основных комбинаторных формул. Изложены также некоторые факты о счетных и несчетных множествах, включая теорему Кантора и теорему Кантора–Бернштейна.

Пособие адресовано учащимся и преподавателям лицея, учителям математики, старшеклассникам.

c ISBN 5-7996-0015-0 С.А. Ануфриенко, Оглавление Введение.................................................................................. 1 Алгебра множеств 1.1 Множество и его элементы. Способы задания множеств............ 1.2 Операции над множествами и их свойства.................... 1.3 Декартово произведение множеств. Соответствия................ 2 Введение в комбинаторику 2.1 Конечные множества. Принцип Дирихле..................... 2.2 Степень данного множества и его мощность................... 2.3 Отображения конечных множеств. Размещения с повторениями....... 2.4 Взаимно однозначные отображения одного множества в другое. Размещения без повторений. Перестановки........................... 2.5 Число сочетаний n -элементного множества по m элементов. Треугольник Паскаля. Бином Ньютона.............................. 2.6 Перестановки и сочетания с повторениями.................... 3 Бесконечные множества 3.1 Счетные множества................................. 3.2 Несчетные множества................................ 3.3 Теорема Кантора–Бернштейна........................... 3.4 Отношения на множестве. Отношения порядка и отношения эквивалентности 3.5 Антиномии. Аксиомы теории множеств...................... Введение Введение Теория множеств одна из самых молодых математических дисциплин.

Ее появление связано с работами немецкого математика Георга Кантора, опубликованными в 1874 1884 годах. Самой значительной из них стала серия, состоящая из шести частей, под общим названием “О бесконечных линейных точечных многообразиях”. В качестве синонима для термина “точечное многообразие” Кантор использует более короткое понятие “множество”, под которым он понимает “объединение в одно целое хорошо различаемых объектов нашей интуиции или мысли”. Понятие множества оказалось настолько общим и в то же время полезным, что многие сложные конструкции алгебры, геометрии и математического анализа получили ясное теоретикомножественное описание. Это сделало теорию множеств универсальным математическим языком. С другой стороны, математиков давно интересовал вопрос логического обоснования своей науки. Развитие логики в XIX веке и появление теории множеств привело к значительному прогрессу в этих исследованиях. В настоящее время теория множеств активно развивающаяся область математики.

Первая глава пособия (“Алгебра множеств”) содержит основные способы задания множеств, а также способы конструирования новых множеств из ранее построенных с помощью некоторых операций. Соответствие между множествами, определенное в последнем параграфе этой главы, позволяет устанавливать связи между множествами и сравнивать свойства множеств. Стоит отметить, что частными случаями соответствий являются последовательности и функции в анализе, а также алгебраические операции и геометрические преобразования.

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

В последней главе изучаются свойства бесконечных множеств, доказываются три теоремы Г.Кантора. В заключение обсуждается вопрос об антиномиях и приводится одна из известных аксиоматических систем теории множеств (система Цермело–Френкеля).

Глава Алгебра множеств 1.1 Множество и его элементы. Способы задания множеств Во многих математических теориях существуют первоначальные, или неопределяемые, понятия. Причина, по которой невозможно определить абсолютно все понятия, которые мы используем, состоит в следующем. Определяя некоторое понятие через другие, необходимо следить за тем, чтобы это понятие не было определено само через себя. Иначе может возникнуть определение, которое в математике называется “порочным кругом” и считается недопустимым. Вот несколько примеров таких “определений”: “ромб это ромб”, “угол имеет величину 90, если его стороны перпендикулярны; перпендикулярными прямыми называются прямые, угол между которыми 900 ” и т.д.

Каждое определение в математике это замаскированная цепочка определений, каждое звено которой является переходом к определению более простого понятия. Поскольку замыкать цепь нельзя, то каждый нижний уровень цепи является неопределяемым понятием. Так, давая строгое определение ромба, можно через определение замкнутой простой ломаной и ее звена дойти до двух не определяемых в геометрии понятий точки и прямой. От первоначальных понятий требуется очень многое: при небольшом количестве они должны обеспечить все многообразие понятий данной математической теории. Все необходимые для этого свойства неопределяемых понятий описываются с помощью системы аксиом. Аксиомы это утверждения о неопределяемых понятиях, которые мы заранее (т.е. по определению) считаем истинными. Так, по Гильберту, в геометрии существуют три неопределяемых понятия, которые описываются двадцатью аксиомами.

Единственным неопределяемым понятием в теории множеств является понятие множества. В качестве синонимов множеству мы будем использовать “совокупность элементов” или “класс элементов”. Смысл множества интуиМножество и его элементы. Способы задания множеств тивно ясен множество объединяет некоторые, вполне определенные, элементы в одно целое. Трудно найти объекты, которые не являются множествами. Так, эта страница является множеством, состоящим из строк, каждая строка множество, состоящее из некоторых символов, каждый символ множество точек на плоскости.

Множества мы будем обозначать большими буквами ( A, B, X, Y ), его элементы малыми ( a, b, x, y ). Тот факт, что a является элементом множества A, будем обозначать a A (читается: a принадлежит множеству A ). Знак был введен итальянским математиком Дж.Пеано и является сокращением греческого слова “быть”. Запись a A означает, что a не является элементом множества A.

Множество полностью определяется своими элементами. Это означает, что множества совпадают в том и только в том случае, когда они состоят из одних и тех же элементов. Символьная запись определения равенства двух множеств такова: A = B (для любого a A a B и для любого Существует два основных способа задания множеств. Для конечных множеств, содержащих небольшое количество элементов, часто просто перечисляют все входящие в него элементы. Так, например, A = {a, b, c} это множество, элементами которого являются только a, b и c.

Самым распространенным является задание множества с помощью некоторого условия P (a), которому удовлетворяют все элементы этого множества и только они. Иными словами, условие P (a) истинно во всех случаях, когда элемент a должен принадлежать определяемому множеству, и ложно для всех элементов, не участвующих в образовании этого множества. Запись A = {a : P (a)} означает, что множество A состоит из всех элементов, которые удовлетворяют условию P (a) (знак “:” означает “такие, что” ). Например, N2 = {n : n N и существует некоторое k N, что n = множество всех четных натуральных чисел; множество R+ = {x :

2k} x Rиx 0} состоит из всех неотрицательных вещественных чисел, B = {b : b является выпуклым четырехугольником} множество, состоящее из всех выпуклых четырехугольников, или такое экзотичное множество, как Y = {y : y – крокодил, обитающий в море Лаптевых }. Для сокращения записи вместо A = {a : a B и P (a)} будем использовать запись Множества могут являться частью других множеств. Так, множество натуральных чисел N содержится во множестве всех целых чисел Z, последнее во множестве рациональных чисел Q, и, наконец, множество Q содержится во множестве вещественных чисел R.

Определение. Множество A содержится во множестве B (обозначается A B ), если каждый эле- B мент множества A является элементом множества B (рис. 1).

Попытайтесь доказать следующую простую теорему.

Теорема 1.1.1. A = B тогда и только тогда, когда одновременно A B и B A (т.е. A = Бывают случаи, когда условие P (a) определено таким образом, что нет ни одного элемента, который бы удовлетворял этому условию. Например, P (a) = “ a является четным и одновременно нечетным натуральным числом”. Множество, не содержащее ни одного элемента, обозначается и называется пустым множеством. Его можно определить еще и таким образом:

= {x : x множество и x = x}. Сделаем одно важное замечание о пустом множестве. Предположим, необходимо доказать, что каждый элемент x данного множества A удовлетворяет некоторому свойству P (x). В случае, когда множество A не содержит элементов, т.е. является пустым, пpинято считать, что каждый его элемент удовлетворяет свойству P (x).

1. Назовите три неопределяемых геометрических понятия.

2. Сколько элементов содержит множество людей, знающих определение множества?

3. Доказать, что содержится в любом множестве.

4. Доказать, что пустое множество единственно.

5. Принадлежит ли множествам {, 1}, {},, {} ?

6. Равны ли между собой множества {, 1} и {1} ; {} и ?

7. Доказать, что {y : y – крокодил, обитающий в море Лаптевых } содержится во множестве простых чисел.

8. Еще раз попытайтесь доказать теорему этого параграфа.

9. Доказать, что {a, b} = {b, a}.

10. Доказать, что {a, b, c} = {a, a, b, b, c, c}.

11. Содержится ли множество простых чисел во множестве нечетных чисел?

12. Покажите, что pазличных бесконечных множеств бесконечно много.

13. Кому принадлежат следующие слова: “Математика полностью свободна в своем развитии, и ее понятия связаны только необходимостью быть непротиворечивыми и соглаОперации над множествами и их свойства сованными с понятиями, введенными ранее посредством точных определений” (Леонардо да Винчи, Эдгару По, М.В. Ломоносову, Г. Кантору)?

14. Кто из четырех перечисленных выше людей имел математическое образование?

15. Одним из крупнейших специалистов по теории функций в XIX веке был Карл Вейерштрасс (1815 1897). Известно, что Кантор, обучаясь в берлинском университете, слушал лекции Вейерштрасса. Кроме того, именно Вейерштрасс принимал у Кантора докторский экзамен по алгебре и теории функций. Условием этого экзамена было то, что отвечающий должен был давать ответы на вопросы без подготовки. Пришлось ли Кантору подвергаться столь серьезному испытанию и по теории множеств?

16. Действительно ли Г.Кантор родился в Санкт-Петербурге и учился там в начальной школе?

1.2 Операции над множествами и их свойства Довольно часто новые множества с требуемыми свойствами получаются из ранее построенных с помощью теоретико-множественных операций. Последние имеют своими историческими предшественниками логические операции, свойства которых были хорошо изучены 1 уже к середине XIX века. В этом параграфе изучаются основные теоретико-множественные операции: пересечение, объединение, разность множеств и взятие дополнения.

Определение. Пересечением множеств A и B (обозначается A B ) называется множество, состоящее из всех элементов, которые одновременно принадлежат и A, и B. Символьная запись этого определения такова:

Определение. Объединением множеств A и B (обозначается A B ) называется множество, состоящее из всех элементов, принадлежащих или A, или B. И соответствующая символьная запись: A B = {x : x A или x Диаграммы Эйлера–Венна, изобpаженные на рис.1 и 2, являются иллюстрацией для включения множеств, а также операций пеpесечения и объединения.

Рассмотрим несколько примеров. Если A = {1, 2, 3} и B = {3, 4}, то их пересечением будет множество A B = {3}, а объединением AB = {1, 2, 3, 4}. Пересечение множества, состоящего из всех квадратов плоскости, и множества четырехугольников, не являющихся квадратами, пусто, в то время как их объединение дает множество всех четырехугольников на плоскости.

Заслуга в этом принадлежит английскому математику Дж. Булю (1815 1864).

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

Перед тем как определить еще одну операцию над множествами, обсудим понятие универсального мно- AB B жества. Часто рассматривают множества какого-то A определенного типа, т.е. все они одновременно со- A держатся в некотором “большом” множестве. Такое множество, которое содержит все рассматриваемые множества данного типа, называется универсальным B для этого типа множеством. Так, для знакомого множества крокодилов моря Лаптевых универсальным A множеством является множество всех крокодилов.

Для четырехугольников универсальным множеством является плоскость. Для числовых множеств мно- B A жество всех вещественных чисел R. Далее универA сальное множество будем обозначать через I.

Определение. Разностью множеств B и A (обозначается B\A ) называется множество, состоящее из всех элементов множества B, не принадлежащих A множеству A (т.е. B\A = {x : x B и x A} ) (pис. 2).

Определение. Дополнением множества A (обо- Рис. значение A ) называется разность между универсальным множеством I и множеством A (т.е. A = {x : x I и x A} ) (pис. 2).

Если по-прежнему A = {1, 2, 3} и B = {3, 4}, то B\A = {4}, а A\B = = {1, 2}. Разностью между множеством натуральных чисел N и множеством всех четных натуральных чисел N2 является множество всех нечетных натуральных чисел.

Операции объединения и пересечения удовлетворяют следующим свойствам.

Теорема 1.2.1. Пусть A, B и C произвольные множества. Тогда справедливы следующие равенства 2 :

Доказательство. Каждое из этих свойств следует из определения операций и из теоремы 1.1.1. Докажем только 4-е свойство.

Обозначим через X и Y левую и правую части в равенстве 4. Покажем, что оба условия теоремы 1.1.1 выполняются.

1. Докажем сначала, что X Y. Для этого выберем произвольный элемент x X. Тогда x одновременно принадлежит AB и C. Из условия Если x B , то x B C. Следовательно, в любом случае x A C или 2. Докажем, что выполняется и обратное включение ( Y X ). Возьмем Из теоремы 1.1.1 теперь следует, что X = Y.

Остальные свойства операций проверяются аналогично.

Легко заметить, что опеpации и обладают некотоpой симметpичностью. Так, пpи одновpеменной замене всех на и всех на каждая из пpиведенных выше фоpмул останется веpной. В следующей теоpеме доказываются основные свойства pазности множеств.

Теорема 1.2.2. Пусть A и B произвольные множества. Тогда выполняются следующие свойства 3 :

Доказательство. Cвойство 7. Обозначим через X и Y соответственно левую и правую части этого равенства. Покажем, что X Y и Y X.

Свойства 2 и 2 называются законом коммутативности операций и, 3 и 3 законом ассоциативности, 4 и 4 дистрибутивности.

Свойства 7 и 7 называются законами де Моргана.

17. Доказать, что всегда A B A B. В каком случае A B A B ?

18. Известно, что {a, b} {c}. Что можно сказать об элементах этих множеств?

19. В каком случае A B = A B ? Описать все такие случаи.

20. Доказать, что выполняется A\B = A\(A B).

21. В чем сходство и различие свойств операций над множествами,, \ и операций над числами +, ·,. Найти четыре сходства и два различия.

22. Докажите, что следующие условия эквивалентны:

23. Докажите, что для любых двух множеств A и B выполняется 24. Правда ли, что теоремы 1.2.1, 1.2.2 были доказаны непальским математиком Дж. Булем (1815 1864)?

25. Дано n множеств. Попытаться доказать, что с помощью операций,, \ можно получить конечное число различных множеств.

1.3 Декартово произведение множеств. Соответствия В 1637 году вышел философский трактат “Рассуждение о методе” французского философа и математика Рене Декарта (1596 1650). Последняя часть этой работы была посвящена новому геометрическому методу методу координат. Каждой точке плоскости Декарт поставил в соответствие упорядоченную пару вещественных чисел ее первую и вторую координаты. При этом многие геометрические фигуры стали описываться с помощью алгебраических уравнений. Координаты каждой точки данной фигуры удовлетворяли соответствующему уравнению, координаты всех остальных точек плоскости не удовлетворяли этому уравнению. Таким образом, многие геометрические задачи были переведены на алгебраический язык и были решены алгебраическими средствами. Эта часть математики, которая возникла на границе геометрии и алгебры, стала называться аналитической геометрией.

Рассмотренное Декартом множество всех упорядоченных пар вещественных чисел является примером произведения множества на себя. Для определения произведения множеств в общем случае необходимо понятие упорядоченной пары. Пусть A и B произвольные непустые множества и a A, b B. Заметим сразу, что множества 4 {a, b} и {b, a} равны между собой и поэтому не дают возможности определить, какой из двух элементов пары является первым, а какой вторым. Последнее важно, так как, например, точки с координатами (1, 2) и (2, 1) различны, в то время как множества {1, 2} и {2, 1} совпадают. Существует несколько определений упорядоченной пары (a, b), одно из них принадлежит Н.Винеру и К.Куратовскому.

Определение. Пусть a A, b B. Упорядоченной парой (a, b) называется множество {a}, {a, b}, при этом a называется первым элементом упорядоченной пары, а b вторым.

Доказательство. ). Очевидно.

1-й случай. a = b. Тогда {{a}, {a, b}} = {{a}} = {{c}, {c, d}}. Следовательно, {a} = {c} = {c, d} a = c = d.

2-й случай. a = b. Из равенства множеств получаем, что {a} {c}, {c, d} {a} = {c} или {a} = {c, d}.

a) {a} = {c}. Поэтому a = c и {a}, {a, b} = {a}, {a, d}. Заметим, что {a, b} = {a}, иначе a = b. Следовательно, {a, b} = {a, d} b = d.

= {a} a = b. Противоречие.

Итак, запись (a, b) означает, что пара образована двумя элементами a и b, причем a является первым элементом этой пары. В предыдущей теореме доказано основное свойство упорядоченных пар: две упорядоченные пары совпадают тогда и только тогда, когда совпадают их первые элементы и вторые элементы также равны между собой. Это, в частности, означает, что (a, b) = (b, a) только в исключительном случае: когда a = b.

Определение. Произведением двух множеств A и B называют множество A B, состоящее из всех упорядоченных пар, первые элементы которых выбираются из A, вторые из B (т.е. A B = {(a, b) : a A, b B} ).

На рис. 3 изображено произведение множеств A = {1, 2, 3} и B = {a, b}.

Множество {a, b} = {b, a} называется неупорядоченной парой.

Произведение двух множеств A и B часто называют декартовым произведением. Заметим, что множества A и B не обязаны быть различными, в случае их совпадения множество A A обозначают через A2 и называют квадратом (декартовым квадратом) множества A. Так, например, R декартова плоскость, Z 2 ее подмножество, состоящее из всех точек с целочисленными координатами.

Заметим, что часто A B = B A. Так, Теорема 1.3.2. Пусть A, B и C произвольные множества, тогда выполняются следующие свойства:

Доказательство. Обозначим через X и Y левую и правую части равенства 1.

По теореме 1.1.1 множества X и Y совпадают.

Свойство 1 доказывается аналогично.

Ниже обсудим понятие соответствия.

Определение. Соответствием между множествами A и B называется произвольное подмножество их произведения A B (т.е. A B ) 5.

Итак, соответствие состоит из упорядоченных пар. Каждая пара (a, b) указывает, что элементу a A соответствует элемент b B при данном соответствии.

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

Так, рис. 4 является изображением для следующего соответствия:

Заметим, что некоторым элементам из A может соответствовать несколько элементов множества B, а некоторым элементам из A может не соответствовать ни один элемент множества B.

Определение. Областью определения соответствия называется множество Dom = {a A : существует элемент b B, что (a, b) } (т.е.

Греческие буквы,, читаются соответственно “фи”,“пси”,“хи”.

это все элементы из A, которым соответствует хотя бы один элемент из B ).

Определение. Множеством значений соответствия называют множество Im = {b B :

хотя бы одному элементу из A ).

П р и м е р 1. Для, изображенного на рис. 4, Dom = {1, 3, 4} и Im = {a, b, c}.

Для обозначения соответствия между мноB жествами A и B будем использовать A B Опишем некоторые типы соответствий.

Определение. Соответствие называется 1) всюду определенным, если Dom = A ;

2) сюръективным, если Im = B ;

3) однозначным, если каждому a Dom соответствует единственный 4) инъективным, если разным элементам из Dom соответствуют разные элементы из B, т.е. из (a, b) и (a1, b) a = a1.

П р и м е р 2. Так, соответствие из примера 1 сюръективно, но не всюду определено ( 2 Dom ), не однозначно (так как (3, a), (3, c) ), не инъективно (так как (1, b), (4, b) ). Чаще всего мы будем иметь дело с хорошими соответствиями отображениями и биекциями.

Определение. Отображением называется всюду определенное и однозначное соответствие (выполняются свойства 1 и 3). Функцией называют отображение в вещественную прямую (т.е. B = R ).

Определение. Биекцией называют всюду определенное, сюръективное, однозначное и инъективное соответствие (выполняются все свойства 1 4).

Например, квадратичная функция каждому числу x R (поэтому она всюду определена) ставит в соответствие одно число ax2 + bx + c (она однозначна). Но квадратичная функция не является инъективным соответствием (некоторым pазличным числам она ставит в соответствие одно и то же число). Поэтому это не биекция. С другой стороны, функция f (x) = kx + b является биекцией при k = 0.

К соответствиям можно применять две операции рассматривать обратное соответствие и брать композицию соответствий.

Определение. Обратным соответствием к соответствию A B называют 1 = {(b, a) : (a, b) }.

Заметим, что 1 B A, поэтому 1 это соответствие уже между B и A. На рис. 5 показано обратное соответствие к, изображенному на рис. 4. В этом случае 1 = {(b, 1), (a, 3), (c, 3), (b, 4)}.

Определение. Композицией соответствий AB и B C называют соответствие A C такое, что = {(a, c) : существует элемент b B, что (a, b) и (b, c) } (обозначается композиция так: = ).

Композиция соответствий, изображенных на ри с. 6, является множеством = {(1, y), (3, x), (4, y)}.

Биекции устойчивы к операции взятия композиции и перехода к обратному соответствию.

1) является биекцией между B и A ;

2) является биекцией между A и C.

Доказательство. 1. Так как всюду определено, то 1 сюръективно.

Так как сюръективно, то 1 всюду определено. Два оставшихся свойства проверяются аналогично.

2. Поскольку и всюду определены, то и их композиция будет определена в каждой точке множества A. Так как действует на все B и на все C, то является сюръективным соответствием. Однозначность и инъективность также легко проверить.

26. Найти пересечение множеств A = {1, a, 2} и B = {a, b, 3}. Найти пересечение R и 27. Какая плоская фигура соответствует {(x, y) R2 : Ax+By +C = 0, где A, B, C R} ?

Рассмотреть все случаи A, B, C.

28. Какая плоская фигура соответствует множеству {(x, y) R2 : (|x| |y|)(x2 + y 2 4x) = 29. Известно, что A B =. Что можно сказать о множествах A и B ?

30. Пусть для множеств A, B, C имеет место условие (AB)(B A) = C C. Доказать, 31. В каком случае A B = B A ? Описать все такие случаи.

32. Являются ли биекциями f (x) = x3, f (x) = 3 x, f (x) = x ?

33. Если отображение, то соотношение (a, b) будем записывать в виде b = (a). (Почему это можно сделать только для отображений?) Тогда композицию можно записать так: ((a)) (т.е. сначала на элемент из A действует, а затем на получившийся элемент (a) B действует ). Пусть f (x) = x2 и g(x) = x + 1, найти gf и f g.

34. Пусть A A и f f... f = idA, где idA тождественное соответствие на A, т.е. для любого a A выполняется idA (a) = a. Доказать, что f биекция.

35. Пусть A B. Доказать, что f инъективное соответствие для любых g, h(g :

36. Пусть X Y, X =. Доказать, что f сюръективное соответствие для 37. Пусть F отображение F : X Y. Покажите, что эквивалентны следующие свойства:

1. F инъективное отображение;

2. F 1 F (A) = A для любого подмножества A X ;

3. F (A B) = F (A) F (B) для любой пары A, B подмножеств X ;

4. F (A) F (B) = для любой пары A, B подмножеств X таких, что A B = ;

5. F (A\B) = F (A)\F (B) для любой пары A, B подмножеств X, для которой Глава Введение в комбинаторику 2.1 Конечные множества. Принцип Дирихле Сравнивать между собой количества элементов двух различных конечных множеств A и B кажется простой задачей. Для этого можно определить число элементов в A, затем в B и сравнить получившиеся два целых числа. Теперь усложним задачу. Попытайтесь представить себе такую ситуацию, что вы разучились считать, но вам необходимо определить: одинаковое количество элементов во множествах A и B или нет. Если вы справились с первой частью задачи, то вторую часть задачи можно решить с помощью биекции. Следует выбирать по элементу из каждого множества, образуя пары (пары соответствия), до тех пор, пока не закончатся элементы хотя бы в одном из этих двух множеств. Если это произойдет одновременно, то получится биекция между этими множествами, и, следовательно, во множествах A и B одинаковое количество элементов.

Определение. Множества A и B называются равномощными ( A B ), если существует биекция между ними (т.е. существует A B, что биекция).

выполняются свойства 6 :

Первое из этих свойств называется рефлексивностью, второе симметричностью и третье транзитивностью.

Доказательство. 1. Биекцию A на себя построить легко: пусть по определению (a) = a для любого a A 7. искомая биекция.

2. Пусть A B биекция между A и B, тогда 1 биекция между B и A (см. теорему 1.3.3).

3. Пусть A B, B C биекции между A, B и B, C соответственно, тогда биекция между A и C (см. теорему 1.3.3).

вают начальным отрезком натурального ряда.

Доказательство. ). Если n = m, то N n = N m и используем первое свойство теоремы 2.1.1.

). Пусть N n N m, тогда существует биекция N n N m. Изменим эту биекцию следующим образом. Пусть (1) = k, где k m, и существует l n, что (l) = 1. Рассмотрим 1 = \{(1, k), (l, 1)} {(1, 1), (l, k)}. Ясно, что 1 биекция, так как мы поменяли местами значения на двух элементах (в 1 и l ). Заметим, что уже 1 (1) = 1.

Аналогично построим биекцию 2 со свойством 2 (1) = 1, 2 (2) = 2 и т.д.

В конце концов мы получим n со свойством n (i) = i, i n. Так как n сюpъективно и сохpаняет поpядок, то n (n) = m, с другой стороны, Определение. Множество A называется конечным множеством, если A = или существует n N, что A N n. При этом будем говорить, что мощность множества A равна n ( |A| = n ). Если множество пусто, то по определению считаем, что его мощность равна нулю.

Например, если Арус множество всех букв русского алфавита, то |Арус | = 33.

Доказательство. ). Поскольку |A| = n, существует биекция A N n. Из определения равномощности A и B найдется биекция A B.

Тогда соответствие 1 является биекцией между B и N n. Следовательно, |B| = n (на рис. 7 и 8 изображены коммутативные диаграммы, которые являются иллюстрацией к доказательству этой теоpемы).

Такая биекция называется тождественным отображением A на себя и обозначается idA.

58. Найдите количество расстановок в последнем примере, если тома 1 и 2 не должны стоять рядом.

59. Сколькими способами можно рассадить n человек за круглым столом? Два способа считаются одинаковыми, если для каждого человека сосед справа и слева остался тем же самым.

60. Сколькими способами можно pассадить n женщин и n мужчин за кpуглым столом так, чтобы мужчины и женщины чеpедовались?

61. Сколько существует трехзначных чисел, делящихся на 5, каждое из которых состоит из различных цифр?

2.5 Число сочетаний n -элементного множества по m элементов. Треугольник Паскаля. Бином Ньютона Определение. Пусть |A| = n m. Сочетанием по m элементов множества A называют произвольное подмножество B A, состоящее из m элеменm тов. Cn количество всех сочетаний по m элементов из n -элементного множества.

Не важно, в каком поpядке pасположены элементы во множестве. Так, напpимеp, {1, 2, 3} = {3, 2, 1}. Этим сочетания отличаются от размещений.

П р и м е р 1. Пусть A = {a, b, c}. Выпишем все размещения по два элемента и все сочетания по два элемента и определим C3 :

Заметим, что размещения в каждой строке отличаются только порядком элементов, и поэтому они дают только одно сочетание. Отсюда C3 = A2 /2! = 3.

Этим замечанием мы воспользуемся в следующей теореме.

Теорема 2.5.1.

Доказательство. Пусть |A| = n. Обозначим через Rm множество всех размещений множества A по m элементов. Разобьем множество Rm на классы. К одному классу будут относиться те размещения, которые отличаются только порядком элементов. Так, размещения (b1,..., bm ) и (c1,..., cm ) попадают в один класс тогда и только тогда, когда {b1,..., bm } = {c1,..., cm }.

Это разбиение удовлетворяет следующим свойствам:

1) количество элементов в каждом классе равно m!, 2) классы между собой не пересекаются, 3) каждому классу соответствует в точности одно сочетание, 4) различным классам соответствуют pазличные сочетания.

Элементами каждого класса являются различные перестановки некоторого m -элементного множества, поэтому выполняется первое свойство. Свойства 2 и 4 следуют из определения классов. В каждом классе перестановки отличаются только порядком элементов, поэтому им соответствует только Число сочетаний n -элементного множества по m элементов... одно сочетание, состоящее из этих элементов. В результате Теорема 2.5.2. Число сочетаний удовлетворяет следующим свойствам:

Доказательство. Свойство 1 следует из теоремы 2.5.1.

2. Cn это число m -элементных подмножеств множества A (|A| = n).

Тогда Cn + Cn +... + Cn это число всех подмножеств множества A.

Поэтому Соотношение 3 называют основным рекуррентным свойством числа сочетаний. Оно позволяет легко заполнить первые строчки следующей бесконечной таблицы (она называется треугольником Паскаля). Каждый элемент этой таблицы Cn+1 равен сумме двух соседних элементов Cn и Cn, стоящих в предыдущей строке (если они есть).

Число сочетаний n -элементного множества по m элементов... Хорошо известно, что Коэффициенты в правых частях равенств совпадают с числами, стоящими в строчках треугольника Паскаля. Это справедливо и в общем случае.

Формула следующей теоремы называется формулой бинома Ньютона.

Теорема 2.5.3.

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

1. Представим левую часть формулы в виде произведения n множителей и занумеруем скобки числами от 1 до n :

Определим количество слагаемых вида xnm y m после раскрытия скобок.

Для этого рассмотрим произвольное сочетание по m элементов множества A = {1, 2,..., n}. Каждое такое сочетание однозначно определяет номера скобок, из которых выбирается y, из остальных выбирается x. Таким образом, каждому такому сочетанию соответствует одно слагаемое вида xnm y m и наоборот. Поэтому количество слагаемых xnm y m после раскрытия скобок будет равно Cn.

2. Индукция по n.

Б.И. Случай n = 1 очевиден.

Ш.И. Предположим, для n = k это утверждение выполняется. Докажем В последнем переходе мы использовали равенство Ck = Ck+1 = Ck+1 = 1 и рекуррентное свойство числа сочетаний.

Следствие 1.

Доказательство. Достаточно заметить, что все слагаемые, в которых степень y нечетна, будут со знаком минус.

Следствие 2. (4-е свойство числа сочетаний) Доказательство. Необходимо воспользоваться предыдущей формулой для бинома (1 1)n.

62. Сравнивая коэффициенты при xk в обеих частях равенства (1 + x)m (1 + x)n = = (1 + x)n+m, доказать, что 63. Доказать, что сумма квадратов биномиальных коэффициентов равна C2n (т.е.

k=0 (Cn )= C2n ).

64. Доказать, что 65. Упростить выражение P1 + 2P2 +... + nPn.

2.6 Перестановки и сочетания с повторениями Название этого параграфа содержит противоречие: в перестановках и сочетаниях элементы не могут повторяться. Но для pешения некотоpых задач удобно использовать специальные констpукции, котоpые лучше называть именно таким обpазом. Рассмотрим пpимеpы таких задач и затем введем необходимые определения.

П р и м е р 1. Сколько существует различных 5-буквенных слов, полученных перестановкой букв слова “потоп” (словом будем называть любой набоp букв)? Сделаем несколько полезных замечаний. Порядок букв в словах важен, так, например, “потоп” это не то же самое, что “оптоп”. С другой стороны, “оптоп” и “оптоп” совпадают, хотя в них и переставлены местами две буквы “о”. Итак, порядок не важен, когда речь идет об одинаковых буквах, и важен в случае, если местами меняются разные буквы. Число всех таких различных 5-буквенных слов будем считать следующим образом: на пять пустых мест будем расставлять сначала буквы одного типа, затем другого и т.д.

Количество способов расставить две буквы “о” на 5 пустых мест это количество способов выбрать 2 места из 5, т.е. C5. На оставшиеся места для каждой такой расстановки будем размещать две буквы “п”(таких размещений C3 ) и, наконец, на оставшееся место поместим “т”(таких размещений C1 ).

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

Определение. Пусть дано k1 элементов 1-го типа, k2 2-го,..., km m-го типа. И k1 + k2 +... + km = n. Тогда перестановкой из n элементов с повторениями k1,..., km называются размещение с повторениями, в котором в точности k1 элементов 1-го типа, k2 2-го,..., km - m-го типа.

P n (k1,..., km ) количество всех таких перестановок.

Так, в предыдущем примере два элемента 1-го типа (две буквы “о”), два элемента 2-го типа (две буквы “п”) и один элемент 3-го типа. Мы нашли, что P 5 (2, 2, 1) = 30.

Общий результат выглядит так:

Теорема 2.6.1.

Доказательство. Любую такую перестановку с заданным числом повторений можно получить следующим образом:

выбираем места для элементов 1-го типа их Cn1 ;

Число всех размещений равно Заметим только, что результат будет таким же, если вы будете сначала выбирать места для элементов 2 -го типа и т.д.

Теперь о сочетаниях с повторениями. Снова начнем с примера.

П р и м е р 2. Предположим, что вы решили купить 5 (пять!) пирожных трех видов, которые есть в продаже. И предположим (это сделать уже сложнее), что у вас нет привязанности к пирожным какого-то определенного типа. Сколько существует различных вариантов выбора? Обозначим через A, B, C виды пирожных. Тогда могут быть такие варианты: AAAAA, ABBBBB или ABCCC. Снова займемся наблюдениями. Порядок видов пирожных не важен, так, вариант BABBB совпадает с ABBBB. Важно только количество пирожных данного типа. Поэтому по каждому выбору будем образовывать перестановку по следующему правилу: ставим k1 единиц, если выбрано k1 пирожных первого типа, затем ставим 0 (если пирожных первого типа нет, конечно, сразу ставим 0), далее ставим k2 единиц, если выбрано k2 пирожных второго типа, затем снова ставим ноль и, наконец, ставим столько единиц, сколько выбрано пирожных последнего типа. Для выборов выше это будут перестановки с повторениями (1111100), (1011110) и (1010111) соответственно. Итак, 5 единиц и 2 разделяющих нуля. И наоборот, по каждой такой перестановке можно восстановить выбор. Искомое Определение. Сочетаниями из n различных типов по m элементов с повторениями называются неупорядоченные совокупности, состоящие из m элементов, каждый из которых принадлежит к одному из этих n типов.

Число всех таких совокупностей будем обозначать чеpез C n.

Теорема 2.6.2.

Доказательство. Покажем, что таких сочетаний с повторениями столько же, сколько и перестановок с повторениями из m единиц и n 1 нулей.

Построение взаимно однозначного соответствия приведено в примере 2.

Отличие состоит только в том, что в общем случае будет m единиц и n нулей, чтобы отделить один тип элементов от другого. Если сочетания различны, то хотя бы один из разделяющих нулей будет стоять на другой позиции. И наоборот, если один из нулей, скажем, i -го типа, следует после другого количества единиц, это сразу же означает, что выбрано неодинаковое количество элементов этого типа и сочетания получаются различными.

Поэтому Последнее равенство следует из второго свойства числа сочетаний.

Следуя комбинаторному доказательству формулы бинома Ньютона, можно получить формулу 66. Докажите последнюю формулу, занумеровав скобки и определив количество слагаемых вида ak1 ak2 ·... · akm.

Глава Бесконечные множества 3.1 Счетные множества В этом параграфе мы начинаем изучение бесконечных множеств. Немного забегая вперед, сделаем на первый взгляд странное утверждение: бесконечные множества могут быть по-разному бесконечны. Поэтому мы начнем с самых маленьких из бесконечных со счетных множеств. Напомним, что при определении конечных множеств мы пользовались начальными отрезками натурального ряда. Теперь нашим эталоном будет все множество натуральных чисел.

Определение. Счетным множеством называется произвольное множество A, равномощное множеству N (как обычно, существует биекция A N ).

П р и м е р 1. Множество всех натуральных чисел, начиная с двойки, т.е.

N 2 = {n N : n 2}, является счетным множеством. Одна из возможных биекций задается правилом: (k) = k 1, k N 2, П р и м е р 2. Множество всех четных натуральных чисел (N2 ) также счетно. Биекцию можно задать, напpимеp, так: (n) = 2n, n N.

Лемма 3.1.1. Множество A счетно в том и только в том случае, когда его можно представить в виде A = {a1, a2,..., an,...}, где ai = aj для всех pазличных i, j N.

Доказательство. Действительно, если биекция A N существует, то, обозначив через an = 1 (n), мы получим искомое представление.

Обратно, если такое представление задано, то биекцию можно задать правилом (n) = an, n N.

Теорема 3.1.1. Любое бесконечное подмножество множества N счетно.

Доказательство. Пусть A N и A бесконечно. По индукции занумеруем элементы множества A.

найти, так как в любом непустом подмножестве N найдется минимальный элемент. Заметим, что a1 1.

Ш.И. Пусть для n = k выбраны a1, a2,..., ak A так, что выполняются следующие свойства:

2) ai i для любого i k ;

3) каждый элемент множества A\{a1, a2,..., ak } больше любого из a1, a2,..., В качестве элемента ak+1 выберем минимальный элемент множества A\{a1, a2,..., ak }. Он найдется в силу бесконечности множества A. Так как ak+1 k + 1. И, наконец, третье свойство уже для ak+1 выполняется в силу минимальности элемента ak+1 в множестве A\{a1, a2,..., ak }. Итак, мы получили некоторое множество {a1, a2,..., an,...}. Покажем, что это множество совпадает со множеством A. Достаточно доказать, что для любого a A следует, что a {a1, a2,..., an,...}. О/п. Пусть существует a A, что a {a1, a2,..., an,...}. Заметим, что a = m для некоторого m N.

Тогда a = m am. С другой стороны, из третьего свойства следует, что множество.

Следствие 1. Множество простых чисел счетно.

Следствие 2. Множество Nm = {mn : n N }, где m N счетно, если m = 1.

Следствие 3. Любое бесконечное подмножество B счетного множества A счетно.

Доказательство. Пусть B A и B бесконечно. Так как A N, то существует биекция A N. Тогда (B) бесконечное подмножество N. По предыдущей теореме оно счетно. Следовательно, B (B) N.

Поэтому B счетное множество.

В следующей теореме используется операция счетного объединения. До сих пор мы объединяли не более чем конечное число множеств. Пусть теперь дано счетное число множеств A1, A2,..., An,.... Тогда единения не выводят из класса счетных множеств, т.е., объединяя в счетном числе счетные множества, всегда будет получаться счетное множество.

Теорема 3.1.2. Счетное объединение счетных множеств счетно.

Доказательство. Пусть A1, A2,..., An,... счетные множества.

Рассмотрим случай, когда эти множества попарно не пересекаются. Выше определялись множества Nm. Мы будем рассматривать множества Npn, где pn n -е по счету простое число. Заметим, что множества Npi и Npj попарно не пересекаются при i = j. Иначе (pi )k = (pj )l при некоторых k, l N, но правая и левая части этого равенства имеют различные делители.

Так как множества An и Npn счетны, то существует биекция n : An Npn. Определим теперь биекцию : An Npn следующим обраn=1 n= зом:

Множество Npn счетно как бесконечное подмножество N. Следоваn= тельно, An также счетно.

Теперь рассмотрим общий случай, когда Ai и Aj могут пересекаться между собой. Тогда рассмотрим множества B1 = A1, B2 = A2 \A1,..., Bn = An \(n1 Ak ). Заметим, что • Bi и Bj при различных i и j между собой не пересекаются.

Снова будем рассматривать отображения n, определенные выше, но уже для Bn. Если некоторое Bn окажется конечным, то n взаимно однозначное отображение Bn в Npn (если Bn =, то и n = ). В результате также будет взаимно однозначным отображением Bn в Npn.

ство ( Bn ), как бесконечное подмножество N, счетно. Следовательно, n=1 An = Bn Следствие 1. Множество целых чисел Z счетно.

Доказательство. Действительно, Z = N {n : n N } {0}, т.е. это объединение двух счетных множеств и конечного множества.

Следствие 2. Множество пар Zn = {(k, n) : k Z} счетно, где n N.

Доказательство. Каждое из этих множеств равномощно с Z, так как n фиксировано.

Следствие 3. Множество рациональных чисел Q счетно.

Доказательство. Любое рациональное число можно представить в виде упорядоченной пары (k, n), где k Z, n N. Следовательно, Q Zn. Множество Q является счетным объединением счетных мноn= жеств.

Следствие 4. Множество чисел на плоскости с обеими рациональными координатами, т.е. множество Q Q, счетно.

Доказательство. QQ = rQ (Q{r}). В этом равенстве справа стоит счетное объединение счетных множеств.

Ранее количество элементов в конечных множествах мы обозначали через |A| = n, где n натуральное число. Для обозначения мощности бесконечных множеств используют бесконечные кардинальные числа. Так, мощность N равна 0 (алеф-ноль). По аналогии с предыдущими обозначениями будем записывать |N | = 0. В следующем параграфе выяснится, что счетные множества не являются единственными представителями класса бесконечных множеств, то есть существуют другие кардинальные числа.

67. Можно ли опpеделение в теоpеме 3.1.2 заменить опpеделением 3.2 Несчетные множества Биекции между счетными множествами часто задаются с помощью формул.

Приведем примеры других способов описаний биекций. Интервал от 0 до равномощен вещественной прямой R ( (0; 1) R ). Доказать это утверждение можно в два этапа: установить равномощность интервала и дуги окружности (без концевых точек), на рис. 12 это делается с помощью биекции, и равномощность последней с вещественной прямой (биекция ) доказывается с помощью проектирования из центра этой окружности. Композиция этих биекций будет искомой биекцией.

Сложнее построить биекцию между полуинтервалом [0 1) и интервалом (0; 1). Для этого выберем счетное множество A = {1/n : n N, n 2}.

Заметим, что A (0; 1) [0; 1). Зададим биекцию между отрезком и интервалом следующим образом (рис. 13):

Этой идеей мы воспользуемся при доказательстве следующей теоремы.

Лемма 3.2.1. В любом бесконечном множестве X существует счетное подмножество.

Доказательство. Пусть X бесконечно. Будем строить два счетных непересекающихся подмножества A и B по индукции.

Б.И. n = 1. Пусть a1 произвольный элемент множества X, а b произвольный элемент из X\{a1 }.

Ш.И. Предположим, что уже выбраны различные a1,..., ak, b1,..., bk.

Тогда множество X\{a1,..., ak, b1,..., bk } бесконечно и поэтому содержит по крайней мере два различных элемента. Один из них мы обозначим через ak+1, другой через bk+1.

В результате мы получим два непересекающихся счетных множества:

Кроме того, что мы нашли счетное подмножество в X (например, A ), мы показали, что его можно выбрать так, чтобы X\A продолжало оставаться бесконечным.

Теорема 3.2.1. Если X бесконечно иY конечно или счетно, то X Y Доказательство. 1. Пусть пересечеx ние X Y = (рис. 14). Тогда, пользуясь предыдущей леммой, выделим счетное подмножество A X. Множество A Y счетно, поэтому существует биекj биекцию между X Y и X. Пусть (x) = Осталось применить первый случай к Y1 и X.

Определение. Если существует взаимно однозначное отображение множества X на подмножество из Y, будем писать |X| |Y | (мощность X не превосходит мощности Y ). Если при этом не существует взаимно однозначного отображения X на все Y, будем писать |X| < |Y | (мощность X строго меньше мощности Y ). Если существует биекция между X и Y, тогда будем использовать обозначение |X| = |Y | (мощности множеств X и Y совпадают).

Так, если A счетное множество, то |A| = |N | = 0. Кроме того, из леммы следует, что для любого бесконечного X выполняется |N | |X|.

Каждое ли бесконечное множество является счетным? Оказывается, нетpудно получить множество строго большей мощности. Кантор заметил, что операция взятия множества всех подмножеств всегда приводит к образованию множества строго большей мощности.

Теорема (Кантор) 3.2.2. Для любого множества X выполняется неравенство |P(X)| > |X|.

Доказательство. Нам необходимо проверить, что существует взаимно однозначное отображение X в P(X) и при этом между ними не существует биекции.

1. Пусть (x) = {x}, x X. Тогда взаимно однозначно отображает X на множество {{x} : x X}. Последнее содержится в P(X).

2. Покажем, что любое отображение из X не является отображением на P(X) (т. е. нет ни одного сюръективного отображения, тем более не существует биекции). Возьмем произвольное отображение f : X P(X). Это отображение ставит в соответствие элементам множества X некоторые подмножества X, которые являются элементами P(X). Найдем множество A, которое не поставлено в соответствие ни одному элементу из X. Определим его так:

Покажем, что оно искомое.

О/п. Пусть существует x0 X, что f (x0 ) = A P(X). Возможны два случая: x0 A или x0 A.

Итак, отображение f не является отображением “на”, поэтому не может быть биекцией.

Следствие. 0 = |N | < |P(N )|.

Определение. c = |P(N )|. Кардинальное число c называют мощностью континуума.

Определение. 20 = |{0, 1}N |, т.е. кардинальное число 20 является мощностью множества всех отображений из N в двухэлементное множество {0, 1}.

Доказательство. Достаточно доказать, что множества P(N ) и {0, 1}N равномощны. Построим биекцию между ними. Пусть A произвольное подмножество из N, тогда обозначим через fA такое отображение:

Тогда искомой биекцией будет (A) = fA. Соответствие всюду определено и взаимно однозначно. Покажем, что оно сюръективно. Для произвольного f {0, 1}N образуем такое множество A = {n N : f (n) = 1}. Тогда Следующие две теоремы отвечают на вопрос: какова же мощность R.

Первая из них утверждает, что R несчетно. Метод, который используется при доказательстве этой теоремы, называется диагональным методом Кантора. Вторая теорема уточняет результат первой теоремы: множества R и P(N ) равномощны.

Доказательство. О/п. Предположим, что R счетно. Тогда и интервал (0; 1) счетен, поэтому (0; 1) можно представить в виде {a1, a2,..., an,...}.

Каждое вещественное число an запишем в виде бесконечной десятичной дроби an = 0, an an... an.... Получим следующее представление:

Покажем, что среди выписанных чисел нет по крайней мере одного числа a = 0, a a... a... из (0 1). Определим его десятичные знаки следуюn щим образом: a1 {4, 5}\{a1 } ; a {4, 5}\{a2 };... a {4, 5}\{an };...

число a отличается n -й цифрой после запятой, поэтому a (0; 1) = / = {a1, a2,..., an,...}. C другой стороны, числа ai выбираются так, что не Доказательство. В начале этого параграфа мы показали, что [0; 1) (0; 1) R. Поэтому достаточно доказать, что |[0; 1)| = c.

Каждому числу из [0; 1) однозначно можно поставить в соответствие его двоичное представление вида 0, b1 b2... bn..., bi {0, 1} для любого i N (договоримся, что не может быть бесконечного периода из единиц, начиная с некоторого места). Но каждому такому представлению однозначно соответТеорема Кантора–Бернштейна ствует отображение f {0, 1}N такое, что Обозначим множество всех отобpажений, котоpые соответствуют числам из [0; 1), чеpез X, и чеpез Y найдется такое натуpальное число n N, что f (i) = 1 для всех i n, т.е.

отобpажение f пpинимает значение 1, начиная с n. Тепеpь легко доказать счетность множества Y. Действительно, pазличных отобpажений, пpинимающих значение 1, начиная с n, только конечное число (их не более 2n ).

Поэтому Y является счетным объединением конечных множеств. Следовательно, Y счетно или конечно. Уже доказано, что [0; 1) X, тепеpь же по теоpеме 3.2.1 получаем, что 68. Доказать, что соответствия и, с помощью котоpых стpоилась биекция между интеpвалом (0; 1) и R в начале этого подpаздела, являются биекциями.

3.3 Теорема Кантора–Бернштейна В предыдущем параграфе было определено отношение |X| |Y | (существует биекция множества X на некоторое подмножество из Y ). Очевидно, что |X| |X|. Если |X| |Y | ( биекция, отображающая X на подмножество из Y ) и |Y | |Z| ( биекция, отображающая Y на подмножество из Z ), то взаимно однозначно отображает X на некоторое подмножество Z, следовательно, |X| |Z|. Предположим теперь, что существует биекция X на подмножество из Y и, наоборот, существует биекция Y на подмножество из X (т.е. |X| |Y |, и |X| |Y | ), можно ли в этом случае построить биекцию уже между множествами X и Y (т.е. |X| = |Y | )?

Утвеpдительный ответ на этот вопpос, впеpвые поставленный Г. Кантоpом, был дан его учеником Феликсом Беpнштейном зимой 1896-1897г.

Теорема(Кантор–Бернштейн) 3.3.1. Если существует взаимно однозначное отображение A в B и, наоборот, из B в A, то между A и B можно построить биекцию. ( |A| |B| и |A| |B| |A| = |B| ).

Доказательство. Рассмотрим сначала частный случай теоремы.

1. Пусть B (A\A1 ) и A A1 (рис. 15). Докажем, что (B A1 ) A1.

Так как A A1, то существует биекция f : A A1. Построим биекцию между (B A1 ) и A1. Введем некоторые обозначения. Пусть B0 = B, B1 = f (B). В общем случае Bi+1 = f (Bi ).

Заметим, что B A B1 = f (B) f (A) = A1. Покажем сначала, что Bi и Bj при разных значениях i и j не пересекаются. B0 (A\A1 ) и B1 A1 B0 B1 =. Теперь предположим, что для любых i < j < n Bi Bj =. Покажем, что Bj Bn =. По предположению Bj1 Bn1 =. По свойству биекции для любых C D = f (C)f (D) =. Поэтому Теперь опишем искомую биекцию:

На рис. 15 темные места множества B A1 соответствуют точкам, которые движными), светлые множества Bi переходят последовательно друг в друга. Покажем, что является биекцией между f f B A1 и A1. Очевидно, что всюду определено. Так как f, являясь биекциB ей, отображает множество Bi на множество Bi+1 и то сюръективно. Однозначность сле- B соответствуют разные (x), (y) A1 ).

1. x, y принадлежат темной (неподвижной) части (т.е. x, y Bi для любого i N {0} ), тогда (x) = x = y = (y).

2. Один из них, например, x, принадлежит темной части, другой одному из Bi, тогда (y) принадлежит следующему светлому множеству 3. x, y принадлежат различным светлым множествам Bi и Bj, тогда (x), (x) также принадлежат различным светлым множествам Bi+ и Bj+1. Следовательно (x) = (y).

4. x, y принадлежат одному светлому множеству Bi. Так как f биекция, то (x) = (y).

Все свойства биекции проверены.

и по предыдущему случаю B A1 A.

3. Перейдем к доказательству общего слуA на соответствующие подмножества (рис. 16).

Применяя второй случай для множеств A, B1, A2, получаем, что существует биекция между A и B1. Следовательно, g 1 искомое взаимно однозначное отображение A на B.

Следствие 1. (0; 1] (0; 1).

Доказательство. (0; 1] (0; 1 ] (0; 1) ( f (x) = 2 x предыдущую теорему. Заметим, что каждое Bi состоит только из одной точки: B0 = 1, B1 = 2, Bi = i+1. Если строить биекцию между [0; 1] и (0; 1), то каждое Bi будет состоять из двух точек.

Используя проектирование и центральное проектирование (см. начало предыдущего параграфа), можно показать, что круг без границы равномощен полусфере без ограничивающей окружности; последняя, в свою очередь, равномощна плоскости (предлагаем повращать рис. 12 относительно прямой, проходящей через точку О и перпендикулярной к прямой R ).

Следствие 2. Квадрат без границы равномощен кругу без ограничивающей окружности.

Доказательство. Пусть A квадрат без границы и B круг без ограничивающей окружности. Тогда существует круг без границы B1 A. Так как B1 B |B| |A|. Аналогично в B содержится некоторый квадрат без границы A1 (при этом A1 A |A| |B| ). По теореме Кантора– Бернштейна |A| = |B|.

Следствие 3. Квадрат без границы (0; 1) (0; 1) равномощен интервалу (0; 1).

Доказательство. Очевидно, что |(0; 1)| |(0; 1)(0; 1)| (так как (0; 1) Построим биекцию (0; 1) (0; 1) на некоторое подмножество интервала (0; 1). Пусть (x, y) (0; 1) (0; 1). Рассмотрим представление x и y в виде бесконечных десятичных дробей: x = 0, x1 x2... и y = 0, y1 y2... Зададим теперь отображение следующим образом: f ((x, y)) = z = 0, x1 y1 x2 y2... Это отображение ставит в соответствие число, у которого после запятой на нечетных местах стоят десятичные знаки x, а на четных десятичные знаки y.

Если (x, y) = (x, y ), то они различаются хотя бы по одной координате, значит, десятичные представления этих координат отличаются в некотором десятичном разряде, следовательно, z = z. Итак, f взаимно однозначное отображение (0; 1) (0; 1) в (0 1).

По теореме Кантора–Бернштейна (0; 1) (0; 1) (0; 1).

Следствие 4. (Кантор) |R| = |R R|.

Доказательство. R (0; 1) (0; 1) (0; 1) (кругу без границы) (полусфере без ограничивающей окружности) R R.

Предыдущий результат фактически означает следующее: на прямой и на плоскости одинаковое количество точек.

69. Сравните доказательства того факта, что [a; b) (a; b), приведенные в этом и предыдущем параграфах.

70. Докажите, что любые два кpуга pавномощны.

71. Является ли отобpажение f, постpоенное в доказательстве следствия 3, биекцией квадpата без гpаницы на интеpвал?

72. Докажите, что точек в пространстве столько же, сколько их на прямой.

73. Докажите, что если X Y и X, Y бесконечные множества, то X Y X.

74. Справедлив ли предыдущий результат для пересечения множеств?

75. Докажите, что Rn R для любого n N.

76. Докажите, что если для любого n N выполняется Xn Y и X, Y бесконечные множества, то Xn Y.

77. Докажите, что Rn R.

3.4 Отношения на множестве. Отношения порядка и отношения эквивалентности Соответствие может устанавливать связи между элементами разных множеств A и B, а может связывать между собой элементы одного и того же множества, т.е. когда B = A. В последнем случае такое соответствие принято называть отношением на множестве A.

Определение. Отношением на множестве A называют произвольное подмножество декартового квадрата AA (т.е. AA ). Если (x, y), будем использовать обозначение x y ( x и y находятся между собой в отношении ) 9.

Так, например, любое отношение на множестве вещественных чисел является подмножеством плоскости R R. Изображение этого подмножества называют графиком отношения. Таким образом, отношение на множестве R и его график означают одно и то же множество плоскости.

Рассмотрим некоторые примеры отношений и их графиков.

П р и м е р 1. P P, где P множество всех людей. Отношение зададим так: a b когда дни рождения a и b совпадают.

отношение делимости на множестве N.

отношение означает “быть сравнимыми между собой по модулю k N \{1} ”.

прямая y = kx + b (рис. 17).

отношения окружность с центром в (0,4) и радиусом 2 (рис. 17).

отношения круг с центром в (4, 0) и радиусом 1 (рис. 17).

Греческая буква читается как “ро”.

П р и м е р 7. R R. Зададим его с помощью некоторой фигуры на плоскости. x y (x, y). Графиком этого отношения будет в точности эта фигура (рис. 17).

странстве. Пусть a, b L, a b когда прямые a и b между собой параллельны. Будем считать по определению, что совпадаюx щие прямые также параллельны.

ство всех треугольников на плоскости. Пусть когда треугольники ABC и DEF подобны.

X некоторое множество. Пусть A, B X.

Тогда AB A B.

Среди огромного числа отношений на множестве A мы выделим несколько важных типов:

1) рефлексивно, если a a для любых a A, 5) отношение порядка, если оно рефлексивно, антисимметрично и транзитивно, 6) отношение эквивалентности, если оно рефлексивно, симметрично и транзитивно.

Примеры 1, 3, 8 и 9 являются примерами отношений эквивалентности.

Скажем, в примере 3, если n, m и m, l дают одинаковые остатки при делении на k, то n и l также дают одинаковые остатки при делении на k.

Поэтому отношение сравнения по модулю k транзитивно. Также легко проверить остальные свойства для этого и других отношений.

Отношение, определенное в примере 2, является отношением порядка. Очевидно, что n делит n. Если n делит m и m делит n, то они совпадают.

И, наконец, если n делит m и m делит l, то n делит l. Поэтому выполняются соответственно свойства рефлексивности, антисимметричности и транзитивности для данного отношения.

Отношение порядка будем обозначать с помощью или. Часто к свойствам порядка добавляется четвертое свойство любые два элемента a, b A можно сравнить между собой.

Определение. Отношение порядка называется отношением линейного порядка, если для любых a, b A выполняется a b или b a.

Порядок в примере 2 не является линейным уже для 2 и 3 не выполняется ни утверждение “два делит три”, ни “три делит два”. Примерами линейных порядков являются отношения на множествах натуральных, целых, вещественных чисел.

Определение. Множество A вместе с отношением порядка на этом множестве мы будем обозначать (A, ). Пусть B A. Тогда a0 B называют наименьшим (соответственно наибольшим) в B, если для любых b B выполняется неравенство a0 b (b a0 ). Элемент a0 B называют минимальным (соответственно максимальным) в B, если для любых b B, b a0 ( b B, a0 b ) выполняется b = a0 ( b = a0 ).

Быть наименьшим или наибольшим элементом это более сильное свойство, чем быть просто минимальным или максимальным элементом. Так, в двухэлементном множестве A = {a, b}, с очень бедным порядком = {(a, a), (b, b)} (свойства порядка легко проверяются), a и b являются одновременно максимальными и минимальными элементами по очень простой причине: нет элементов в A больших или меньших их. Но ни один из них не является наибольшим или наименьшим элементом для этого они должны быть больше или меньше другого, а это не так. Во множествах с линейным порядком, где любые два элемента сравнимы между собой, соответствующие пары терминов означают одно и то же.

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

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

Такой тип доказательства называют трансфинитной индукцией.

Теорема 3.4.1. Пусть (A, ) вполне упорядоченное множество и a0 минимальный элемент в A. Кроме того, p(a) некоторое утверждение, принимающее для любого a A истинное или ложное значение и удовлетворяющее двум свойствам:

(a) базе, т.е. p(a0 ) истинно;

(b) для него доказан шаг, т.е. в предположении, что для любого a < b утверждение p(a) истинно, доказано, что p(b) также истинно.

Тогда p(a) истинно для любого a A.

Доказательство. О/п. Пусть это не так, т.е. найдется b0 A, для которого p(b0 ) ложно. Рассмотрим множество B = {b A : p(b) ложно}.

Это множество не является пустым, поэтому, в силу полноты порядка, в нем найдется минимальный элемент. Обозначим его через b. Тогда для любого a < b выполняется a B p(a) истинно. Так как шаг доказан, из истинности p(a) для любого a < b следует, что p(b ) Следующим широко распространенным отношением является отношение эквивалентности. Отношение эквивалентности мы будем обозначать через (отношение равномощности между множествами также является отношением эквивалентности).

Определение. Пусть (A, ) множество с отношением эквивалентности на нем. Мно- A A(a) жество A(a) = {b A : b a} мы будем называть классом эквивалентности по этому отношению (рис 18).

Определение. Множество A разбивается на подмножества As, s S, где S некоторое множество индексов, если A = sS As и множества As и As совпадают или не пересекаются.

Теорема 3.4.2. Пусть (A, ) множество с отношением эквивалентности на нем. Тогда отношением это множество разбивается на классы эквивалентности. И наоборот, если существует разбиение множества A = sS As, то существует такое отношение эквивалентности на множестве A, что каждое As будет классом эквивалентности.

Доказательство. Пусть отношение эквивалентности. В силу рефлексивности a a A = aA A(a). Покажем, что любые два класса или совпадают, или не пересекаются. Если c A(a) A(b), то, используя транзитивность, a c b a b. Следовательно, A(a) = A(b). Получим искомое представление A = aA A(a).

Наоборот, если задано разбиение A = sS As, то введем отношение следующим образом: a b a, b As для некоторого s S. Легко проверить, что оно искомое.

В заключительной части параграфа pассмотpим пpимеp использования тpансфинитной индукции пpи доказательстве одного алгебpаического факта.

Речь пойдет о пpедставлении пpоизвольного симметpического многочлена в виде многочлена от элементаpных симметpических многочленов. Доказательство этой важной теоpемы потpебует от нас значительного числа вспомогательных понятий и утвеpждений, поэтому пpи пеpвом чтении этот матеpиал может быть пропущен.

Определение. Одночленом от пеpеменных x1, x2,..., xn называется выpажение вида axk1 xk2... xkn, где a R и ki являются неотpицательными целыми числами для всех i N n. Сумма i=1 ki называется степенью одночлена, если a = 0. Если коэффициент a pавен нулю, то одночлен называется нулевым и его степень pавна нулю.

Определение. Два ненулевых одночлена axk1 xk2... xkn и bxl1 xl2... xln наn n зываются подобными, если одновpеменно ki = li для всех i N n. Пpи этом их суммой называется одночлен (a + b)xk1 xk2... xkn.

Определение. Многочленом от пеpеменных x1, x2,..., xn называется сумма конечного числа одночленов от этих пеpеменных.

В силу двух последних опpеделений можно считать, что многочлен не содеpжит подобных слагаемых. В этом случае его степенью мы будем называть максимальную из степеней входящих в него слагаемых. Так, напpимеp, степень многочлена от тpех пеpеменных f (x, y, z) = x4 y + x4 + x2 y 3 + z 5 pавна пяти. Заметим, что f (x, y, z) содеpжит тpи слагаемых пятой степени. Поpядок, в котоpом выписаны эти слагаемые, называется лексикогpафическим.

Определение. Пусть (X1, 1 ), (X2, 2 ),..., (Xn, n ) упоpядоченные множества. Отношение называется лексикогpафическим поpядком на пpоn Например, если лексикографически упорядочить декартову плоскость, то (1, 5) < (2, 1) (здесь i0 = 0 ). По похожему принципу упорядочиваются слова в словарях и энциклопедиях: сначала по первой букве, затем по второй и т.д.

Теперь понятно и происхождение термина. Является ли лексикографический порядок отношением порядка? Следующая теорема, в частности, дает ответ и на этот вопрос.

Теорема 3.4.3. Пусть даны вполне упорядоченные множества (X1, 1 ), (X2, 2 ),..., (Xn, n ). Тогда лексикографический порядок являетn Доказательство. Докажем индукцией по n. В качестве базы pассмотpим случай n = 2 (если n = 1, доказательство очевидно). Пpовеpим выполнение всех пяти свойств отношения полного поpядка.

Рефлексивность. Так как для любого a X1 и b X2 a 1 a и b 2 b, то (a, b) (a, b). Поэтому “ ” удовлетвоpяет pефлекивности.

Антисимметpичность. Пpедположим, что одновpеменно (a, b) (a1, b1 )