Мощность или кардинальное число множества

 

Говорят, что множество А равномощно множеству В и пишут А ~ В, если существует биекция множества А на множество В. Так как обратное к биекции отображение и композиция двух биекций суть также биекции, то отношение равномощности А ~ В является отношением эквивалентности. Мощностью или кардинальным числом m(A) данного множества А называется совокупность всех тех множеств В, на которые множество А можно биективно отобразить:

 

m(A) = {B, $ биекция j: A ® B}

 

Так как обратное к биекции отображение само является биекцией, то

 

m(A) = {B, $ биекция j: B ® A}

 

Поэтому

m(A) = {B, B ~ A}= {B, A ~ B}

 

Для любых множеств А₁ и А₂ их классы m(A₁) и m(A₂) либо не пересекаются, либо совпадают.

 

Целые неотрицательные числа можно понимать как кардинальные числа некоторых множеств – эталонов, например:

 

0 = m(Æ), 2 = m( множество рук человека ),

5 = m(множество пальцев на руке человека) и так далее.

 

Введём ещё обозначения:

 

a = m(N), где N - множество всех натуральных чисел,

b = m(R), где R - множество всех вещественных чисел.

 

 

Пусть m₁ и m₂ - два кардинальных числа. Будем говорить, что m₁ предшествует m₂ (или m₁ не больше m₂ ) и писать m₁ £ m₂, если

 

"A Î m₁ и "BÎ m₂ существует инъекция j из А в В,

 

Заметим, что если A, A₁ Î m₁ и B, B₁ Î m₂, и существует инъекция j из А в В, то существует и инъекция f из А₁ в В₁. Поэтому достаточно проверить существование инъекции j для выбранных представителей А и B классов m₁ и m₂. Если m(A) £ m(B), то будем говорить, что мощность А не больше мощности В. Заметим, что если А Ì В, то m(A) £ m(B). Можно показать, что отношение m₁ £ m₂ является отношением частичного и даже линейного порядка на множестве кардинальных чисел. Действительно, аксиома транзитивности выполняется за счёт того, что композиция двух инъекций есть также инъекция. Аксиома рефлексивности также выполняется, так как тождественное отображение из А в А: j(x) = x " xÎ A является биекцией, а следовательно и инъекцией из А в А. Далее, можно показать, что каковы бы ни были множества А и В, всегда существует инъекция из А в В или инъекция из В в А, т. е. выполняется аксиома 4) линейного порядка. Содержание же аксиомы антисимметричности заключено в следующей теореме:

Теорема Бернштейна. Если существует инъекция из А в В и существует инъекция из В в А, то существует и биекция между А и В.

Доказательство теоремы проведём на модели, по картинке, с “раскраской” всех элементов множеств А и В на три цвета.

Задача 4. Проведите общее (абстрактное) доказательство теоремы Бернштейна

(см., например, Дж. Л. Келли “Общая топология”, стр. 48-49).

 

Задача 5. Покажите, что множество бесконечно (содержит бесконечно много

элементов) тогда и только тогда, когда оно равномощно некоторой

своей части, отличной от самого множества).

 

Будем говорить, что мощность множества А строго меньше мощности множества В и писать m₁ < m₂, если m₁ £ m₂ , но m₁ ¹ m₂ , т. е. если существует инъекция из А в В, но не существует инъекции из В в А.

 

Множества, равномощные множеству натуральных чисел, т. е. принадлежащие классу a = m(N), будем называть счётными множествами.

 

 

Теорема. Множество Z целых чисел и множество Q рациональных чисел являются счётными, а множество R вещественных чисел не является счётным.

 

Всякое бесконечное множество А содержит счётное подмножество, следовательно оно «не менее, чем счётно», т. е. a £ m(A) или m(A) ³ a.

 

Введём обозначение A° для множества всех частей или всех подмножеств данного множества А: A° = {B, B Ì A}

Теорема Кантора. Мощность множества всех подмножеств любого бесконечного множества А строго больше мощности самого множества А. Другими словами:

 

Если А – бесконечно, то m(A°) > m(A)

Cхема доказательства:

 

1) так как j(x) = {x} – инъекция из множества А во множество всех его частей A°, то m(A°) ³ m(A),

2) покажем, что не существует биекции между множеством А и множеством A° всех его частей. Доказательство проведём от противного. Пусть такая биекция f существует. Построим множество A’ = { x Î A таких, что x Ï f(x) } и простроим далее элемент x’ = f^-1(A’). Этот элемент x’ либо принадлежит множеству A’, либо не принадлежит ему. Но и то и другое невозможно (приводит к противоречию).

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

 

Тогда на множестве кардинальных чисел можно ввести следующие операции: если A₁ ¹ Æ, A₂ ¹ Æ, m(A₁) ³ a или m(A₁) ³ a, m(A₁) = m₁, m(A₂) = m₂, то положим про определению

 

m₁ + m₂ = m(A₁ È A₂), m₁ × m₂ = m(A₁ ´ A₂),

 

Можно показать, что введённые таким образом операции удовлетворяют свойствам m₂ + m₁ = m₁ + m₂, m₂ · m₁ = m₁ · m₂ , (m₂ + m₁) · m₃ = m₁ · m₃ + m₂ · m₃ , m^k+l = m^k + m^l и так далее. Но если хотя бы одно из множеств А₁ или А₂ бесконечно, то всегда имеет место:

 

m₁ + m₂ = m₁ × m₂ = max {m₁, m₂}

 

Заметим, что с учётом выше приведённых обозначений теорему Кантора можно переписать в виде: " m ³ a: 2^m > m.

Заметим также, что b = m(R) = m(0,1) = m{N®{0,1}} = 2^a

 

Ряд кардинальных чисел есть, таким образом, бесконечное линейно упорядоченное множество:

0, 1, 2, 3, …, a, b = 2^a , g = 2^b , d = 2^g , …

 

+ примеры вычисления мощности множества