Эквивалентность множеств
Определение 1.2. Если каждому элементу множества A сопоставлен единственный элемент множества B и при этом всякий элемент множества B оказывается сопоставленным одному и только одному элементу множества A, то говорят, что между множествами A и B существует взаимно однозначное соответствие. Множества A и B в этом случае называют эквивалентными или равномощными.
Эквивалентность множеств обозначается следующим образом: A ~ B.
Эквивалентность множеств обладает следующим свойством транзитивности.
Если A ~ B и B ~ C, то A ~ C.
Докажем это свойство. Так как A ~ B, то для всякого элемента a Î А существует единственный элемент b Î B. Но так как B ~ C, то для всякого элемента b Î B существует единственный элемент c Î C. Сопоставим этот элемент элементу a Î А. Значит, для всякого элемента a Î А существует единственный элемент c Î C и для всякого элемента c Î C существует единственный элемент a Î А. Следовательно, A ~ C.
Очевидно, что два конечных множества эквивалентны тогда и только тогда, когда количество элементов в них одинаково. Например, множества А = {4, 5, 6} и В = {x, y, z} эквивалентны, A ~ B. Взаимно однозначное соответствие может быть установлено между элементами 4 и x, 5 и y, 6 и z.
Мощностью конечного множества А (обозначается çАç) называется число элементов этого множества. Например, мощность множества А = {1, 2} равна çАç= 2.
Пример 1.17.
Ранее (разд. 1.1) мы рассматривали множество всех подмножеств данного множества А, которое называется множеством-степенью и обозначается P(A). Множество P(A) состоит из 2n элементов. Таким образом, çP(A) ç = 2n.
Рассмотрим задачу определения мощности объединения n конечных множеств.
Пусть n = 2 и A и B – два пересекающихся множества. Докажем с помощью диаграммы Эйлера – Венна следующее соотношение:
çАÈB ç= çА ç+ çB ç– çАÇB ç. (1.1)
Из рис. 1.3 видим, что
çАÈB ç= n1+n2+n3;
çА ç= n1+n2;
çB ç= n2+n3;
çАÇB ç= n2.
Рис. 1.3
Очевидно, что n1+n2+n3 = (n1+n2) +(n2+n3) – n2, что и доказывает формулу ().
Формула (1.1) справедлива и для случая, если множества A и B не пересекаются. В этом случае
çАÈB ç= çА ç+ çB ç.
Пусть n = 3 и A, B и С – три пересекающихся множества. В этом случае справедливо следующее соотношение:
çАÈBÈ Сç= çА ç+ çB ç+ çC ç– çАÇB ç– çАÇC ç– çBÇC ç+ çАÇB ÇC ç. (1.2)
Из рис. 1.4 видим, что
çАÈBÈ Сç= n1+n2+n3+n4+n5+n6+n7;
çА ç= n1+n2+n4+n5;
çB ç= n2+n3+n5+n6;
çСç=n4+n5+n6+n7;
çАÇB ç= n2+n5;
çАÇC ç= n4+n5;
çBÇC ç= n5+n6;
çАÇB ÇC ç= n5.
Рис. 1.4
Очевидно, что
n1+n2+n3+n4+n5+n6+n7 =(n1+n2+n4+n5) + (n2+n3+n5+n6) +(n4+n5+n6+n7) – (n2+n5) – (n4+n5) – (n5+n6) + n5,
что и доказывает формулу (1.2).
Формула (1.2) справедлива и для случая, если множества A, B и С попарно не пересекаются. В этом случае
çАÈBÈ Сç= çА ç+ çB ç+ çC ç.
В общем случае мощность объединения n множеств определяется по формуле:
çА1È А2 È…ÈАnç= çА1ç+çА2ç+…+ çАnç– (çА1Ç А2ç+ çА1Ç А3ç+ … +çАn–1ÇАnç)+ çАÇB ÇC ç+ (çА1Ç А2 Ç А3ç + … +çАn–2ÇАn–1ÇАnç) – … + (–1)n – 1 çА1ÇА2 …ÇАnç. (1.3)
Эта формула выводится индукцией по n, [3].
Если множества Аi попарно не пересекаются, т.е. Аi ÇАj = Æ, i ¹ j,то получим частный случай формулы (1.3):
çА1È А2 È…ÈАnç= çА1ç+çА2ç+…+ çАnç.
В общем случае справедливо неравенство
çА1È А2 È…ÈАnç£ çА1ç+çА2ç+…+ çАnç.
Понятие эквивалентности годится и для бесконечных множеств. Пусть, например, A = {1, 2, 3, …, n,…}, B = {– 1, –2, …, –n, …}. Тогда A ~ B. Взаимно однозначное соответствие устанавливается по правилу: элементу nÎ A соответствует элемент – nÎ B, т.е. n « – n.
Пример 1.18.
A = {1, 2, 3, …, n,…}, B = {2, 4 …, 2n, …}. Тогда A ~ B. Взаимно однозначное соответствие устанавливается по правилу: n « 2 n.
Пример 1.19.
A = {1, 2, 3, …, n,…} – множество натуральных чисел, B = {…, –n, …– 2, –1, 0, 1, 2, …, n, …} – множество всех целых чисел.
Перепишем множество B следующим образом:
B = {0, –1, 1, – 2, 2, …, –n, n, …}, так, что 0 будет на первом месте, –1 на втором, 1 на третьем, –2 на четвертом и т.д. Нетрудно заметить, что отрицательные числа будут стоять на местах с четными номерами, а 0 и положительные числа – на местах с нечетными номерами. Поэтому взаимно однозначное соответствие между множествами A и B устанавливается по правилу: для всякого n ³ 0 элементу a = 2n +1 из множества A (т.е. нечетному элементу) соответствует элемент b = n из множества B; элементу a = 2n из множества A (т.е. четному элементу) соответствует элемент b = –n из множества B. Таким образом, реализуется взаимно однозначное соответствие между множествами A и B: 1 « 0, 2 « –1, 3 « 1, 4 « –2 и т.д.
Примеры 1.18 и 1.19 показывают, что множество может быть эквивалентно своему подмножеству. Так, в примере 1.18 BÌ A, а в примере 1.19 A Ì B. И в том, и в другом случае A ~ B.
Установить эквивалентность множеств, т.е. установить взаимно однозначное соответствие между их элементами можно различными путями. На рис. 1.5 показано, что множества точек двух отрезков [a, b] и [c, d] эквивалентны.
Рис.1.5
Таким же образом можно установить эквивалентность множеств точек двух интервалов. На рис.1.6 показано, что множества точек любого интервала (a, b) эквивалентно множеству точек всей прямой.
Рис. 1.6
Для установления эквивалентности двух множеств можно применять следующую теорему.
Теорема Бернштейна. Если множество A эквивалентно части множества B, а множество B эквивалентно части множества A, то множества A и B эквивалентны.
Применим теорему Бернштейна для доказательства того, что множество точек любого отрезка эквивалентно множеству точек любого интервала.
Пусть A = [a, b] – произвольный отрезок, а B = (c, d) – произвольный интервал.
Пусть A1 = [a1, b1] – любой внутренний интервал отрезка [a, b], A1Ì A. Тогда A1 ~ B.
Пусть B1 = (c1, d1) – любой внутренний отрезок интервала (c, d), B1Ì B. Тогда B1 ~ A.
Таким образом, выполняются условия теоремы Бернштейна. Поэтому A ~ B.
Итак, все интервалы, отрезки и вся прямая эквивалентны между собой.