Мощность или кардинальное число множества
Говорят, что множество А равномощно множеству В и пишут А ~ В, если существует биекция множества А на множество В . Так как обратное к биекции отображение и композиция двух биекций суть также биекции, то отношение равномощности А ~ В является отношением эквивалентности. Мощностью или кардинальным числом m(A) данного множества А называется совокупность всех тех множеств В , на которые множество А можно биективно отобразить:
m(A) = {B, $ биекция j : A ® B}
Так как обратное к биекции отображение само является биекцией, то
m(A) = {B, $ биекция j : B ® A}
Поэтому
m(A) = {B, B ~ A}= {B, A ~ B}
Для любых множеств А1 и А2 их классы m(A1) и m(A2) либо не пересекаются, либо совпадают.
Целые неотрицательные числа можно понимать как кардинальные числа некоторых множеств – эталонов, например:
0 = m(Æ), 2 = m(множество рук человека),
5 = m(множество пальцев на руке человека) и так далее.
Введём ещё обозначения:
a = m(N) , где N - множество всех натуральных чисел,
b = m(R) , где R - множество всех вещественных чисел.
Пусть m1 и m2 - два кардинальных числа. Будем говорить, что m1 предшествует m2 (или m1 не больше m2 ) и писать m1 £ m2 , если
"A Î m1 и "BÎ m2 существует инъекция j из А в В ,
Заметим, что если A, A1 Î m1 и B, B1 Î m2 , и существует инъекция j из А в В , то существует и инъекция f из А1 в В1 . Поэтому достаточно проверить существование инъекции j для выбранных представителей А и B классов m1 и m2 . Если m(A) £ m(B) , то будем говорить, что мощность А не больше мощности В . Заметим, что если А Ì В , то m(A) £ m(B) . Можно показать, что отношение m1 £ m2 является отношением частичного и даже линейного порядка на множестве кардинальных чисел. Действительно, аксиома транзитивности выполняется за счёт того, что композиция двух инъекций есть также инъекция. Аксиома рефлексивности также выполняется, так как тождественное отображение из А в А : j(x) = x " xÎ A является биекцией, а следовательно и инъекцией из А в А . Далее, можно показать, что каковы бы ни были множества А и В , всегда существует инъекция из А в В или инъекция из В в А , т. е. выполняется аксиома 4) линейного порядка. Содержание же аксиомы антисимметричности заключено в следующей теореме :
Теорема Бернштейна. Если существует инъекция из А в В и существует инъекция из В в А , то существует и биекция между А и В .
Доказательство теоремы проведём на модели, по картинке, с “раскраской” всех элементов множеств А и В на три цвета.
Задача 4. Проведите общее (абстрактное) доказательство теоремы Бернштейна
(см., например, Дж. Л. Келли “Общая топология”, стр. 48-49).
Задача 5. Покажите, что множество бесконечно (содержит бесконечно много
элементов) тогда и только тогда, когда оно равномощно некоторой
своей части, отличной от самого множества).
Будем говорить, что мощность множества А строго меньше мощности множества В и писать m1 < m2 , если m1 £ m2 , но m1 ¹ m2 , т. е. если существует инъекция из А в В , но не существует инъекции из В в А .
Множества, равномощные множеству натуральных чисел, т. е. принадлежащие классу 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° множества А .
Тогда на множестве кардинальных чисел можно ввести следующие операции: если A1 ¹ Æ , A2 ¹ Æ , m(A1) ³ a или m(A1) ³ a , m(A1) = m1 , m(A2) = m2 , то положим про определению
m1 + m2 = m(A1 È A2) , m1 × m2 = m(A1 ´ A2) , 
Можно показать, что введённые таким образом операции удовлетворяют свойствам m2 + m1 = m1 + m2 , m2 · m1 = m1 · m2 , (m2 + m1) · m3 = m1 · m3 + m2 · m3 , mk+l = mk + ml и так далее. Но если хотя бы одно из множеств А1 или А2 бесконечно, то всегда имеет место:
m1 + m2 = m1 × m2 = max{m1 , m2}
Заметим, что с учётом выше приведённых обозначений теорему Кантора можно переписать в виде: " m ³ a : 2m > m .
Заметим также, что b = m(R) = m(0,1) = m{N®{0,1}} = 2a
Ряд кардинальных чисел есть, таким образом, бесконечное линейно упорядоченное множество:
0 , 1 , 2 , 3 , … , a , b = 2a , g = 2b , d = 2g , …
+ примеры вычисления мощности множества