Арифметика кардинальных чисел.

Определим сложение, умножение и возведение в степень кардинальных чисел. Для обозначения каждой из этих операций мы будем пользоваться символами, которые обозначаются в арифметике «обычных» чисел, например, в арифметике натуральных чисел или в арифметике действительных чисел. Мы сохраним также терминологию этих арифметик, называя, например, результат сложения кардинальных чисел − суммой, а складываемые кардинальные числа − слагаемыми.

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

X∙Y = 0 →

Это сокращенная форма определения сложения кардинальных чисел. Точная форма такого определения следующая:

m+n = f ≡

Определения остальных операций мы приведем только в сокращенной форме.

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

Сформулируем вспомогательное определение:

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

Выражение читается:  функция R есть отображение множества Х в множество Y.

Из определения 8.3 следует:

А~A₁  B~B₁ → B^A~B₁^A1 (*)

Доказательство (*) аналогично лемме 7.5а.

Из определения 8.3 легко следует также:

Следствие 8.1.

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

Таким образом мощность множества Х, возведенная в степень, равную мощности множества Y в множество X.

Покажем, что определение 8.1− корректное определение. С этой целью нужно доказать, что для любых двух кардинальных чисел m и n существует только одно кардинальное число, равное их сумме.

По теореме 7.2ссуществует такие множества А и А₁, что  и . По лемме 7.4мы можем считать, что эти множества не пересекаются. Ссылаясь на теорему 7.2b, мы устанавливаем:

Существование кардинального числа f

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

Из леммы 7.5 легко следует, что А + А₁ ~ В + В₁. Отсюда и из аксиомы 7.1 следует, что f=f₁.

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

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

Пусть X = {x₁, x₂, …, x_m}, Y = {y₁, …, y_n}.

Предположим, что среди элементов x₁, x₂, …, x_m нет тождественных, а также, что среди y₁, …, y_n нет тождественных элементов.

Тогда .

Допустим далее, что каждый элемент множества Х отличен от каждого элемента множества Y. Очевидно, .

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

Покажем, что . Декартову произведению принадлежит X´Y принадлежит любая упорядоченная пара , где i = 1, 2, …, m; y = 1, 2, …, n. Очевидно, что таких пар . Таким образом, умножение натуральных чисел – частный случай умножения кардинальных чисел. Далее заметим, что всякое отображение множества Y в множество Х однозначно определит n-численную последовательность

(1) x₁, x₂, …, x_m,

члены которой – элементы множества Х. (Очевидно, что члены последовательности (1) с различными индексами могут быть тождественны.) Легко видеть, что таких последовательностей mⁿ. Таким образом, и возведение в степень натуральных чисел – частный случай возведения в степень кардинальных чисел.

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

Теорема 8.1. а. ,

                   b.

Эту теорему можно записать в таком виде:

а) m+n = n+m

b) m∙n = n∙m

Доказательство.     a. По лемме 7.4 мы можем считать, что множества X и Y не пересекаются. Тогда имеет место равенство (1):

(1)  X∙Y = Y∙X = 0

(2)                                    {определение 8.1, 1} 

(3)                          {определение 8.1, 1} 

(4)                     {теорема 2.2a}

(5)                              {4}

                                   {5,2,3}

b. По определение 8.2имеют место следующие равенства:

(1)

     

Определим отношение, которое потребуется дальше в доказательстве:

áz, tñ, R, áx, yñ ≡ x = t  y = z  x  X  y  Y.

Очевидно, что и  это отношение устанавливает равночисленность множеств. Отсюда из определения 8.2и аксиомы 7.1следует равенство:

 (2)

Из (1) и (2) следует:

Теорема 8.2.

Доказательство. По лемме 7.4мы можем считать, что равенство (1) имеет место:

(1) X∙Y = 0

(2)                                                      {определение 8.1, 1}

(3)             {определение 8.2, 2}       

(4)                                                {теорема 5.1b, 1}

(5)     {определения 8.1, 8.2, 4}

(6)                          {теорема 5.1a}

(7)                                {6}

                            {7, 3, 5}

Теорема 8.3.

Доказательство. Пусть Â₁={1, 2, …, n}. Отсюда Â₁=n.

Обозначим через X_i (i = 1, 2, …, n) декартово произведение одноэлементного множества {i} и множества Х.

Легко видеть, что имеют место следующие равенства:

                

Из этих формул, теоремы 5.1си определений 8.1 и 8.2следуют равенства:

Таким образом, теорема верна.

Теорема 8.4.

Доказательство. Пусть Â₁={1, 2, …, n}. Отсюда Â₁=n. Из определения 8.3следует, что множество Х^Â1 есть подмножество всех последовательностей х₁, х₂, …, х_n, члены которых – элементы множества Х, а по определению 5.1множество  – это множество всех упорядоченных n-ок <х₁,х₂,…,х_n>, причем х₁, х₂, …, х_n  Х. Очевидно, что отношение, сопоставляющее последовательности х₁, х₂, …, х_n и упорядоченную n-ку <х₁,х₂,…,х_n>, устанавливает равночисленность множеств Х^Â1 и

Отсюда и из определений 8.2 и 8.4следует теорема.

Теорема 8.5.

Доказательство, которое здесь приводится, содержит много сокращений.

Доказательство. По лемме 7.4можем считать, что:

(1) Y∙Z = 0.

Пусть R – произвольная функция, отображающая множество Y+Z в множество Х. Отсюда и из формулы (1), а также определений 6.7 и 8.3 следуют формулы:

R_Y  X^Y

R_Z  X^Z

Пусть отношение S сопоставляет функции R упорядоченную пару  <R_Y, R_Z>. Отношение S устанавливает равночисленность множеств X^Y+Z и X^Y∙X^Z. Отсюда уже легко следует теорема.

Следующую теорему приведем без доказательства:

R_Y  X^Y

Теорема 8.6.

Теоремы арифметики кардинальных чисел, которые приведены в этом параграфе, аналогичны теоремам арифметики натуральных чисел. Однако в дальнейших параграфах мы познакомимся с теоремами, не имеющими этого свойства. Заметим еще, что не было надо определений обратных операций: вычитания и деления.

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

Неравенства.

Лемма 9.1.

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

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

(2) Y~Y₁                                                 {доп.}

(3)                     {доп.}

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

(5) Y~_R1Y₁                                   {определение 7.2, 2}

(6) Y₁ = R₁ (Y)                   {лемма 7.2, 5}

(7)                         {4}

(8)                         {4}

(9)         {теорема 6.1, 7}

(10)              {9, 6}        

(11) Y = D_ℓ (R₁)                {определение 7.1, 5}

(12) Z₁ = D_ℓ (R₁)               {7, 11}

(13)     {лемма 7.3, 4, 12}

(14)              {лемма 7.2, 4, 13}

(15)         {теорема 7.1b, c, 1, 8, 14}

{10, 15}

Определим отношения слабого и сильного неравенства. Эти отношения будем обозначать символами, заимствованными из арифметики «обычных» чисел.

Определение 9.1

          «≤ » − слабое неравенство                   

Таким образом, необходимым и достаточным условием того, чтобы мощность множества Х была меньше или равно мощности множества Y, является равночисленность множества Х и некоторого подмножества Y. Заметим, что из леммы 9.1 следует: если , , , то и .

    Точная формула определения 9.1следующая:

Из определения 9.1и теоремы 7.1аследует:

Следствие 9.1.

                        «<» − слабое неравенство

Заметим еще, что замена под квантором выражения выражением  не позволила бы заменить знак ≤ знаком <, потому что, например, множество всех натуральных чисел, превосходящих некоторое определенное число, есть собственная часть можества всех натуральных чисел, но мощности этиъ множеств равны.

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

  «<» – сильное неравенство

Легко видеть, что оба определенных отношения являются обобщениями соответствующих отношений арифметики натуральных чисел.

Лемма 9.2.    

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

(1)                                                                               {доп.}

(2) X~Y                                                                                 {аксиома 7.1, 1}

(3)                                                       {теорема 1.4a}

(4)                                        {2, 3}

                                              {определение 9.1, 4}

Определение 9.2 и лемму 9.2можно записать также в следующей форме:

m < n ≡ m  n  m  n

m = n → m  n

На основании этих формул и теоремы исчисления предложений:

мы устанавливаем истинность.

Теорема 9.1.

m  n ≡ m = n  m < n

Следующая теорема называется теоремой Кантора-Бернштейна:

Теорема 9.2.

m  n  m = n  m < n

Мы не будем приводить трудного доказательства этой теоремы, а ограничимся лишь указанием, в чем состоит основная мысль этого доказательства.

Пусть =m и =n. Из условий теоремы следует существование подмножества Z множества X и подмножества U множества Y, а также отношений R и S, таких, что Х~_RU и Y~_SZ.

На основании этих допущений можно показать, что сущесвует взаимнооднозначное отношение T, левая область которого – х, а правая – y.

Теорема 9.3.

a) m < n → m  n

b) n < m → m  n

c) m = n → ~(m < n)

d) m = n → ~(n < m)

e) m < n → ~(n  m)

Доказательство. Формулы а и b следуют из определения 9.2. Из этих формул с помощью контрапозиции мы получаем формулы с и d.

Приводим доказательство формулы е:

(1) m < n                                                                          {доп.}

(2) n  m                                                                          {доп.}

(3) m  n                                             {определение 9.2, 1}

(4) m  n                                               {определение 9.2, 1}

(5) m = n                                           {теорема 9.2, 2, 4}

Противоречие.                                    {3, 5}

Теорема 9.4. m  n  n  m

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

=m и =n. Чтобы доказать теорему 9.4, следует показать, что всегда существует такое подмножество U множества Y и такое отношение R, что X~_RU, или существует такое подмножество Z множества Х и такое отношение S, что Y~_SZ. Однако для доказательства этого, недостаточно принятых до сих пор аксиом; возникает необходимость в принятии новой аксиомы − так называемой аксиомы выбора, формулировка которой будет дана в §14.

m  n  n  m → m = n

Из теорем 9.4 и 9.1следует, что для любых двух кардинальных чисел имеет место одно из следующих соотношений:

m < n     n < m     m = n

Из теоремы 9.3следует, что может иметь место не более одного из этих отношений. Этот факт мы сформулируем кратко: для кардинальных чисел имеет место принцип трихатолии.

Из того, что  = и f = , а также из следствия 9.1 и определения 9.2 следует:

Теорема 9.5. a)  f

b) Если n – натуральное число, то n < .

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

Лемма 9.5.

a) m < n →m∙f  n∙f

b) m < n →m^k  n^k

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

(1) m < n                          {доп.}

(2) ₁ = m ₁ = n ₁ = f       {теорема 7.2c}

(3) Z₁ Y₁  X₁ ~ Z₁                                   {определения 9.2, 9.1, 1, 2}

(4) ₁ = m                                   {аксиома 7.1, 3, 2}

(5)                   {теорема 5.1d, 3}

(6)                    {следствие 9.1, 5}

m∙f  n∙f                                {определение 8.2, 2, 4}

b. В аналогичном доказательстве формулы b используется следствие 8.1(Z Y→Z^X Y^X).

 

 

Степенное множество.

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

Множество 2^Y называется степенным множеством. Таким образом, элементами степенного множества 2^Y являются все подмножества множества Y.

Лемма 10.1.

Доказательство. Пусть М₁ – семейство всех одноэлементных множеств {m}, единственный элемент которых m принадлежит М, и только таких множеств. Тогда:

{m}  M₁ ≡ m  M.

Очевидно, что любое из множеств {m} есть подмножество множества М. Отсюда: М₁ 2^M (1);

Обозначим через R₁ отношение, сопоставляющее любому элементу m множества М одноэлементное множество {m}. Легко видеть, что это отношение устанавливает равночисленность М и М₁. Отсюда из формулы (1) и определения 9.1: () следует лемма.

Пусть R – произвольная функция, сопоставляющая индивидам множества индивидов.

Мы определим множество Z(R), зависящее от функции R:

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

R  функц. → [x  Z(R) ≡ x  D_ℓ(R)   x  R(x)].

Таким образом, элемент х левой области отношения принадлежит множеству Z(R) тогда, и только тогда, когда х не является элементом множества, которое ему сопоставляет функция R. Этим определением мы будем пользоваться в доказательствах дальнейших лемм.

Лемма 10.2.

R  функц. → Z(R)  D_p(R)

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

(1) R  функц.                 {доп.}

(2) Z(R)  D_p(R)               {доп. к. д.}

Из формулы (2) следует существование элемента х₁ левой области отношения R, которому сопоставляется множество Z(R). Таким образом, формулы (3), (4) имеют место.

(3) х₁  D_ℓ(R)

(4) Z(R) = R (x₁)

(5) x₁  Z(R) ≡ x₁  R(x₁) {определение 10.2, 1, 3}

(6) x₁  Z(R) ≡ x₁  Z(R) {5, 4}

Очевидно, что из формулы (6) следует противоречие.

Лемма 10.3.

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

(1)           {доп. к. д.}

(2)           {аксиома 7.1, определение 7.2, 1}

(3) R₁  функц.       {определение 7.1, 2}

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

(5) D_p(R₁) = 2^M                 {определение 7.1, 2}

(6) Z(R₁) D_ℓ(R₁)             {определение 10.2, 3}

(7) Z(R₁) M          {6, 4}

(8) Z(R₁) 2^M                    {определение 10.1, 7}

(9) Z(R₁)  D_p(R₁)   {8, 5}

(10) Z(R₁)  D_p(R₁) {лемма 10.2, 3}

  Противоречие.          {9, 10}

Теорема 10.1.

Таким образом, мощность произвольного множества меньше мощности множества всех его подмножеств.

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

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

Пусть М – произвольное множество, и пусть А  М. Функция φ_А^(m) называется характеристической функцией множества А тогда, и только тогда, когда эта функция для каждого m  M удовлетворяет условию:

φ_А^(m) = 1, если m  A

                      0, если m  A          

Теорема 10.2.

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

Из определения 8.3 () и определения 10.3следует, что любая характеристическая функция множества А М есть отображение множества М в множество {0,1} и обратно: любое отображение множества М в множество {0,1} есть характеристическая функция некоторого подмножества М. Приведем в соответствие каждому отображению множества М в множество {0,1}, то подмножество, характеристической функцией которого будет это отображение. Легко видеть, что данное соответствие устанавливает равночисленность множества {0,1}^M всех отображений множества М в множество {0,1} и множества 2^М всех подмножеств множества М. Таким образом, имеет место формула (1):

(1) {0, 1}^M ~ 2^M

(2)                             {аксиома 7.1, 1}

(3)       {определение 8.4}

                                    {2, 3}

Теорема 10.3.

                                                        {теорема 10.1, теорема 10.2}

Эту теорему можно записать в виде:

m < 2^m

Теорема 10.4.

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

Доказательство. Для доказательства этой теоремы достаточно заметить, что по теореме 10.3 каждый элемент последовательности: , , , … менее следующего за ним.