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

Так, рис. 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 )