Равночисленность множеств (равномощность).

Кардинальные числа.

Часто вместо выражения «равночисленность множеств» используются также выражения «эквивалентность множеств» или «имеют одинаковую мощность». 

Понятия, которые мы определим в этом параграфе, относятся к важнейшим и самым основным понятиям теории множеств.

Определение7.1.  X~_RY ≡ R 1–1  X = D_ℓ (R)  Y=D_p (R)

Выражение X~_RYсчитается: отношение R устанавливает равночисленность множеств Х и Y. Отношение:

 x R₁ y ≡ x =2y  x  N

устанавливает, таким образом, равночисленность множества всех натуральных чисел и множества всех положительных четных чисел; отношение  

xR₂y≡x=y² x N

устанавливает равночисленность множества всех натуральных чисел и множества всех квадратов натуральных чисел.

Множества Х и Y называются равномощными, если между ними можно установить взаимно-односвязные соответствия (Шиханович, стр.198), взаимно-односвязное соответствие означает:

a) элемент х Х, а y Y;

b) каждый элемент обоих множеств попал в одну и только одну пару     áx,yñ.

Например, если Х − множество всех юношей на танцплощадке, а Y – множество всех девушек на танцплощадке, то пары áx,yñ образуют танцующих друг с другом юношей и девушек.

Два конечных множества равномощны тогда и только тогда, когда они содержат одинаковое количество элементов.

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

1, 2, 3, … n – множество N.

↓ ↓ ↓   ↓

2, 4, 6, … 2n − множество четных чисел.

Множество натуральных чисел (N) содержит столько же элементов, сколько и его часть − множество четных чисел. Точно также устанавливается взаимнооднозначное соответствие между множеством N и множеством всех квадратов натуральных чисел: n → n²; и множество всех кубов натуральных чисел: n → n³ и т. д.

Вообще между множеством N и любой его бесконечной частью всегда можно установить взаимнооднозначное соответствие. Для этого достаточно перенумеровать по порядку числа из этой части.

Пусть К₁ и К₂ две концентрические окружности. Точке К₁ мы приводим в соответствие точку окружности К₂, если эти точки лежат на полупрямой, выходящей из общего центра О₁. Данное соответствие устанавливает равночисленность множества точек, лежащих на этих окружностях.

       К₁                          О₁                                                                                           О₁

          К₂                   

О₁                                      А₁   А₂       

                                                                                                              А                           В

                          В₁              В₂    

Примеры равночисленности точек:

«где больше точек, на отрезке равном 1 см или 1 м?». На этих отрезках точек поровну! То есть часть равна целому. Этим свойством могут обладать только бесконечные множества.        

Из теоремы 5.2, определения 7.1 (áx,yñ Ф(a,b)≡Ф(x,y)), и следствий 6.5 и 6.3 следует следствие 7.1.

Следствие 6.5. R  1-1 ≡ [áx,yñ, áx,zñ  áx,yñ, áx,zñ  E_a,b a R b];

Следствие 6.4. a) x  D_ℓ (R) ≡

b) x D_ℓ(R)≡

с)R функции   х D_ℓ(R) → R(x) D_p(R)

Следствие 7.1. Отношение R устанавливает равночисленность множеств X и Y тогда, и только тогда, когда множеству  (a R b) не принадлежат никакие две (различные) упорядоченные пары, первые или вторые элементы которых тождественны, причем первые элементы упорядоченных пар, принадлежащих множеству   (a R b), образуют множество X, а вторые элементы множество Y.

Определение7.2.

X~Y ≡  X~ _RY

Выражение X~Y читается: множества X и Y равночисленны. Таким образом, два множества равночисленны тогда, и только тогда, когда существует отношение, устанавливающее их равночисленность. Очевидно, что два конечных множества равночисленны тогда, и только тогда, когда число элементов одного из них равно числу элементов другого.

В рассуждениях этого параграфа будет удобно обозначать отношение тождества символом J. Таким образом, вместо x=y будем писать xJy. Такая символика достаточно часто применяется в логике. Заметим еще, что xJx есть логическая теорема.

Лемма7.1.

X = J (X) [X = R (X)]

Доказательство.

(1.1) y X

(1.2) y X yJy                 {1.1}

(1.3) xJy             {1.2}

(1.4) y J(x)                  {определение 6.4.(y R(x) ≡ xRy, x X), 1.3}

(2.1) y J(x)

(2.2) xJy                 {определение 6.4, 2.1}

(2.3) x₁ X                         {2.2}

(2.4) x₁Jy                            {2.2}

(2.5) y X                          {2.3, 2.4}

X = J (X)                            {определение 1.1, 1.1 → 1.4, 2.1 → 2.5}

Теорема 7.1.

a) X~X                                        (рефлективность)

     b) X~Y→Y~X                        (симметричность)

с) X~Y Y~Z→X~Z                   (транзитивность)

Эту теорему словесно можно сформулировать так: отношение равночисленности множеств рефлексивно, симметрично и транзитивно, а потому оно есть отношение эквивалентности.

Доказательство (a):

(1) J функции {определение 6.1 − (R фунц.≡ [xRy  xRz→y=z])}

(2) J^-1 функции {определение 6.5 − (xR^-1y ≡ yRx), D6.1}

(3) J 1-1        {определение 6.6 ­− (R 1-1 ≡ R₁R^-1 функции), 1, 2}

(4) J_x 1-1      {лемма 6.4 − (R 1-1 → R_x 1-1), 3}

(5) x D_ℓ(J)   {определение 6.2a − (x D_ℓ(R) ≡ xRy)}

(6) D_ℓ(J) =1    {определение 1.1 − (x=y= (x X ≡ x Y)), 5, A1.1 − (x 1)}

(7) xÌD_ℓ(J)    {теорема 1.1 − (xÌ1), 6}

(8) D_ℓ(J_x) = D_p (J_x) = x {лемма 6.5a, b, 7, 7.1 ­− (x = J(x))}

(9) X ~ X     {определение 7.1 − (X~_RY ≡ R 1-1  x=D_ℓ(R) Y=D_p(R)), 4, 8}

X ~ X         {определение 7.2 − (X ~ Y ≡ X ~ _RY), 9}       

Доказательство (b):

(1) X ~ Y                               {доп.}

(2) X ~ _R1Y                            {определение 7.2, 1}

(3) R₁  1-1                                 {определение 7.1, 2}

(4) X = D_ℓ (R₁)  Y = D_p (R₁)              {определение 7.1, 2}

(5) R₁^-1  1-1                              {лемма 6.2 − (R  1-1 → R^-1  1-1), 3}

(6) D_ℓ­ (R₁^-1) = Y  D_p(R₁^-1) = x  {лемма 6.1a, 6, 4}

(7) Y ~ _R^-1 X                                 {определение 7.1, 5, 6}       

Y ~ X                                     {определение 7.2, 7}

Доказательство (c):

(1) X ~ Y  Y ~ Z                {доп.}

(2) X ~ _R1Y  Y ~ _S1Z                {определение 7.2, 1}

(3) R₁, S₁  1-1                            {определение 7.1, 2}

(4) X = D_ℓ (R₁)  Y = D_p (R₁) = D_ℓ (S₁)  Z = D_p (S₁) {определение 7.1, 2}

(5) R₁; S₁  1-1                  {лемма 6.6 − (R, S  1-1 → R; S  1-1), 3}

(6) X = D_ℓ­ (R₁; S₁)  Z = D_p (R₁; S₁)  {лемма 6.7a, 6, 4}

(7) X ~ _{R1; S1} Z                               {определение 7.1, 5, 6}       

X ~ Z                                     {определение 7.2, 7}

Следующими двумя леммами будем пользоваться в одном из дальнейших параграфов.

Лемма 7.2.

X ~ _RY → Y = R (x)

Доказательство.

(1) X ~ _RY                {доп.}

(2) X = D_ℓ (R)          {определение 7.1, 1}

(3) Y = D_p (R)          {определение 7.1, 1}

(4) D_p (R_x) = R (x)             {лемма 6.5b − (x D_ℓ (R) → D_p (R_x) = R (x))};

(5) R_x = R                 {лемма 6.8 − (X = D_ℓ (R) → R_x = R), 2}

(6) D_p (R_x) = D_p (R)  {5}

Y = R (x)             {3, 6, 4}              

 Лемма 7.3. R 1-1  ÌX D_ℓ (R) → X ~ _Rx R (x)

Доказательство.

(1) R  1-1                       {доп.}

(2) X  D_ℓ (R)        {доп.}

(3) R_x  1-1             {лемма 6.4 − (R  1-1 → R_x  1-1), 1}

(4) D_ℓ (R_x) = X         {лемма 6.5a − (x D_ℓ (R) → D_ℓ (R_x) = X), 2};

(5) D_p (R_x) = R (x)             {лемма 6.5b − (x D_ℓ (R) → D_p(R_x) = R(x)), 2}

X ~ _Rx R (x) {определение 7.1 − (X~_RY ≡R  1-1  X=D_ℓ (R) Y=D_p (R)), 3, 4, 5}

Мы вводим новое исходное понятие ­− понятие мощности множества. Мощность множества X обозначается через . Создатель теории множеств Г. Кантор считал, что мы приходим к понятию мощности множества, отвлекаясь от того, какие предметы образуют данное множество и как эти предметы в нем упорядочены. Две черточки в обозначении мощности множества и должны, собственно, символизировать эту двойную абстракцию. К системе теории множеств мы присоединяем новую аксиому, в которую входит введенный исходный термин:

Аксиома 7.1.

Замечание 7.1. Будем считать, что мощность пустого множества есть число нуль, а мощность конечного множества − натуральное число, указывающее, сколько элементов насчитывает данное множество.

Таким образом, мощности двух множеств тождественны тогда, и только тогда, когда эти множества равночисленны.

(В математической терминологии утвердить название «мощность множества», хотя, возможно, лучше было бы пользоваться термином «численность множества»).

Заметим, что из аксиомы 7.1 и из рефлективности, симметричности и транзитивности тождества непосредственно следует теорема 7.1.

Определение 7.3   .

Выражение m КЧ читается: m есть кардинальное число. Таким образом, математический объект − кардинальное число тогда, и только тогда, когда он есть мощность некоторого множества. Из замечания 7.1 и определения 7.3 следует, что натуральные числа мы покажем, что существуют неравночисленные бесконечные множества. Таким образом, существуют различные кардинальные числа, которые не являются ни натуральными, ни нулем. Произвольные кардинальные числа мы будем обозначать малыми готическими буквами m, n, f. Из определения 7.3легко следует:

Теорема 7.2.

а)

b)

c)

Эта теорема имеет следующую словесную формулировку:

a. Мощность произвольного множества есть кардинальное число.

b. Для всякого множества существует точно одно кардинальное число, равное мощности этого множества.

c. Для всякого кардинального числа существует множество мощность которого равна данному кардинальному числу.

Лемма 7.4. Для любых множеств А и В существуют множества А₁ и В₁, такие, что А₁~A, В₁~В и А₁ В₁ = 0.  

Доказательство.     Множества А₁ и В₁ мы определяем следующим образом:

á1, añ  A₁ ≡ a  A

á2, bñ  B₁ ≡ b  B

Легко видеть, что А₁ и В₁ удовлетворяют условию леммы.

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

    Лемма 7.5.

a) A~B  A₁~B₁  A∙A₁=B∙B₁=0 → A + A₁ ~ B + B₁

b) A~B  A₁~B₁ → A x A₁ ~ B x B₁

Доказательство.     a. Допустим, что отношение R устанавливает равночисленность множеств А и В, а отношение R₁ − равночисленность А₁ и В₁. Нетрудно видеть, что отношение S, определяемое формулой:

xSy ≡ (xRy  xR₁y)^*

устанавливает равночисленность множеств А+А₁ и В+В₁.

 

________________________

* – Такое определенное отношение S называется суммой отношения R, R₁ и обычно обозначается через R+R₁. Произведение и дополнение отношений определяются следующим образом:

xR∙Sy ≡ xRy  xSy

xR’y ≡ ~(xRy).

Можно показать, что определяемые операции над отношениями удовлетворяют аксиомам алгебры Буля, приведенным в §3. Тем самым мы получаем еще одну интерпретацию этой алгебры.

Заметим, что условие: множества А и А₁, а также В и В₁ не пересекаются существенно, как можно видеть из следующего примера:

А={1, 2, 3},   A₁={1, 2, 3, 4}

B={1, 2, 3},             B₁={1, 4, 5, 6}

b. Самостоятельно. Леммами 7.4, 7.5будет показываться в следующем параграфе.

Заметим еще, что мощность множества всех натуральных чисел обозначается через  (читается: алеф-нуль − еврейский алфавит − ввел Г. Кантор), мощность множества всех действительных чисел − через f.

Таким образом, имеют место равенства:

Натуральные числа:

Действительные числа:  f

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

Множества, мощность которых есть число f, называют множествами континуума.

Множество А называют несчетным, если оно бесконечно и несчетно. Из теоремы Кантора (Шиханович, 199) следует, что сегмент  [0, 1]   несчетен.  Очевидно,  любое

множество либо не более чем счетно, либо несчетно.

Множество А называют не более чем счетным, если А конечно (в частности, пусто) или счетно.

Среди несчетных множеств важнейшее значение имеют континуальные множества. Множество А называют континуальным, если А и [0, 1] равномощны.

Множество действительных чисел (D) континуально. Каждое действительное число можно записать в виде бесконечной десятичной дроби вида а, α_1, α_{2, …,} α_n (0,50000…, 0,49999…, 0,575675…).

Из теоремы Кантора следует, что любое континуальное множество несчетно.

Определение 7.4.

Множество А есть запас последовательности

Теорема 7.3.

 

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

Доказательство. Пусть а_1, а_2, а_{3, …} бесконечная последовательность, не имеющая повторяющихся членов, запас которой – множество А. Приведем в соответствие каждому члену этой последовательности его индекс, т.е. члену а₁ – число 1_, члену а₂ – число 2 и т.п. Легко видеть, что данное соответствие устанавливает эквивалентность множеств А и N. Отсюда следует доказываемая теорема.

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