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

Определение 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) состоит из 2 ⁿ элементов. Таким образом, ç P (A) ç = 2 ⁿ.

Рассмотрим задачу определения мощности объединения n конечных множеств.

Пусть n = 2 и A и B – два пересекающихся множества. Докажем с помощью диаграммы Эйлера – Венна следующее соотношение:

ç А È B ç= ç А ç+ ç B ç– ç А Ç B ç. (1.1)

Из рис. 1.3 видим, что

ç А È B ç= n ₁+ n ₂+ n ₃;

ç А ç= n ₁+ n ₂;

ç B ç= n ₂+ n ₃;

ç А Ç B ç= n ₂.

Рис. 1.3

Очевидно, что n ₁+ n ₂+ n ₃ = (n ₁+ n ₂) +(n ₂+ n ₃) – n ₂, что и доказывает формулу ().

Формула (1.1) справедлива и для случая, если множества A и B не пересекаются. В этом случае

ç А È B ç= ç А ç+ ç B ç.

Пусть n = 3 и A, B и С – три пересекающихся множества. В этом случае справедливо следующее соотношение:

ç А È B È С ç= ç А ç+ ç B ç+ ç C ç– ç А Ç B ç– ç А Ç C ç– ç B Ç C ç+ ç А Ç B Ç C ç. (1.2)

Из рис. 1.4 видим, что

ç А È B È С ç= n ₁+ n ₂+ n ₃+ n ₄+ n ₅+ n ₆+ n ₇;

ç А ç= n ₁+ n ₂+ n ₄+ n ₅;

ç B ç= n ₂+ n ₃+ n ₅+ n ₆;

ç С ç= n ₄+ n ₅+ n ₆+ n ₇;

ç А Ç B ç= n ₂+ n ₅;

ç А Ç C ç= n ₄+ n ₅;

ç B Ç C ç= n ₅+ n ₆;

ç А Ç B Ç C ç= n ₅.

Рис. 1.4

Очевидно, что

n ₁+ n ₂+ n ₃+ n ₄+ n ₅+ n ₆+ n ₇ =(n ₁+ n ₂+ n ₄+ n ₅) + (n ₂+ n ₃+ n ₅+ n ₆) +(n ₄+ n ₅+ n ₆+ n ₇) – (n ₂+ n ₅) – (n ₄+ n ₅) – (n ₅+ n ₆) + n ₅,

что и доказывает формулу (1.2).

Формула (1.2) справедлива и для случая, если множества A, B и С попарно не пересекаются. В этом случае

ç А È B È С ç= ç А ç+ ç B ç+ ç C ç.

В общем случае мощность объединения n множеств определяется по формуле:

ç А ₁È А ₂ È…È А_n ç= ç А ₁ç+ç А ₂ç+…+ ç А_n ç– (ç А ₁Ç А ₂ç+ ç А ₁Ç А ₃ç+ … +ç А_{n –1}Ç А_n ç)+ ç А Ç B Ç C ç+ (ç А ₁Ç А ₂ Ç А ₃ç + … +ç А_{n –2}Ç А_{n –1}Ç А_n ç) – … + (–1) ^{n – 1} ç А ₁Ç А ₂ …Ç А_n ç. (1.3)

Эта формула выводится индукцией по n, [3].

Если множества А_i попарно не пересекаются, т.е. А_i Ç А_j = Æ, i ¹ j,то получим частный случай формулы (1.3):

ç А ₁È А ₂ È…È А_n ç= ç А ₁ç+ç А ₂ç+…+ ç А_n ç.

В общем случае справедливо неравенство

ç А ₁È А ₂ È…È А_n ç£ ç А ₁ç+ç А ₂ç+…+ ç А_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 …, 2 n, …}. Тогда 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 = 2 n +1 из множества A (т.е. нечетному элементу) соответствует элемент b = n из множества B; элементу a = 2 n из множества 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) – произвольный интервал.

Пусть A ₁ = [ a ₁, b ₁] – любой внутренний интервал отрезка [ a, b ], A ₁Ì A. Тогда A ₁ ~ B.

Пусть B ₁ = (c ₁, d ₁) – любой внутренний отрезок интервала (c, d), B ₁Ì B. Тогда B ₁ ~ A.

Таким образом, выполняются условия теоремы Бернштейна. Поэтому A ~ B.

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

Дата добавления: 2014-11-06