Эквивалентность множеств

Определение 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.

Эквивалентность множеств - student2.ru

Рис. 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.

Эквивалентность множеств - student2.ru

Рис. 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] эквивалентны.

Эквивалентность множеств - student2.ru

Рис.1.5

Таким же образом можно установить эквивалентность множеств точек двух интервалов. На рис.1.6 показано, что множества точек любого интервала (a, b) эквивалентно множеству точек всей прямой.

Эквивалентность множеств - student2.ru

Рис. 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.

Итак, все интервалы, отрезки и вся прямая эквивалентны между собой.

Счетные множества

Определение 1.3. Множество, эквивалентное множеству натуральных чисел N = {1, 2, 3, …, n,…}, называется счетным.

Можно сказать также, что множество счетно, если его элементы можно перенумеровать.

Пример 1.20.

Следующие множества являются счетными.:

1. A1 = {–1, –2, …, – n, …};

2. A2 = {2, 22, …, 2n,…};

3. A3 = {2, 4, …, 2n,…};

4. A4 = {…, – n, …, – 1, 0, 1, …, n,…};

Чтобы установить счетность некоторого множества, достаточно указать взаимно однозначное соответствие между элементами данного множества и множества натуральных чисел. Для примера 1.19 взаимно однозначное соответствие устанавливается по следующим правилам: для множества A1: –n « n; для множества A2: 2n « n; для множества A3: 2n « n; счетность множества A4 установлена в примере 1.19;

Установить счетность множеств можно также, используя следующие теоремы о счетных множествах (приводятся без доказательств).

Теорема 1. Всякое бесконечное подмножество счетного множества счетно.

Пример 1.21.

Множество A = {3, 6, …, 3n,…} счетно, т.к. A – бесконечное подмножество множества натуральных чисел, A Ì N.

Теорема 2. Объединение конечной или счетной совокупности счетных множеств счетно.

Пример 1.22.

Множество A = {0, 1, …, n,…} неотрицательных целых чисел счетно, множество B = {0, –1, …, –n,…} неположительных целых чисел тоже счетно, поэтому множество всех целых чисел С = АÈB = {…, –n, …– 2, –1, 0, 1, 2, …, n, …} тоже счетно.

Теорема 3. Множество всех рациональных чисел, т.е. чисел вида Эквивалентность множеств - student2.ru , где p и q целые числа, счетно.

Теорема 4. Если А = {a1, a2, …} и B = {b1, b2, …} – счетные множества, то множество всех пар С = {(ak, bn), k = 1, 2,…; n = 1, 2, …} счетно.

Пример 1.23.

Геометрический смысл пары (ak, bn) – точка на плоскости с рациональными координатами (ak, bn). Поэтому можно утверждать, что множество всех точек плоскости с рациональными координатами счетно.

Теорема 5. Множество всех многочленов P(x) = a0 + a1x + a2x2 + … + anxn любых степеней с рациональными коэффициентами a0, a1, a2, … an счетно.

Теорема 6. Множество всех корней многочленов любых степеней с рациональными коэффициентами счетно.

Наши рекомендации