§ 3. Мощность множества

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

Для бесконечных множеств этот способ не годится - мы не сможем закончить подсчет всех натуральных чисел. С целыми, рациональными и тем более вещественными числами еще сложнее. Для конечных множеств есть еще один способ. Будем устанавливать взаимно однозначное соответствие между данными множествами. Собственно говоря, речь идет о взаимно однозначных функциях множества на множество. Эти функции имеют название: биекция. Например, нужно решить вопрос: кого в данной академической группе больше: студентов или студенток? По первому способу можно эти количества подсчитать отдельно, а затем сравнить. По второму способу построим студентов в одну колонну, рядом студенток в другую колонну, чтобы в каждом ряду был один студент и одна студентка. Тогда будет понятно, кого больше. Студенты: 000000 000 Студентки: оооооооооооооо

В данном случае ясно видно, что студенток в группе больше. Такой способ годится и для бесконечных множеств, если удается установить биекцию f: A« B всего множества A на все множество B , то следует признать, что в смысле «количества элементов» данные множества равноценны или эквивалентны. Второй термин примем как официальный.

Определение

Множества A и B называются эквивалентными или равномощными между собой, если существует биекция f: A « B. Запись: A~B.

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

1. Рефлексивность.

A ~ A для всех множеств A.

Действительно, f = idA - есть биекция A на A .

2. Симметричность. A ~ B ^ B ~ A.

Действительно, если f: A « B - биекция, то f- биекция B на A.

3. Транзитивность.

A ~ BLB ~ C ^ A ~ C.

Действительно, при f: A « B, g: B « C, fog есть биекция A на C.

Отсюда сразу же следует простейший вывод, что эквивалентность множеств есть отношение эквивалентности и разбивает все «множество множеств» на классы эквивалентных между собой множеств.

Доказательство A ~ B должно состоять в доказательстве существования биекции f: A«B, например, путем ее конструктивного построения.

Пример

Доказать, что [0;1]~^[0;2].

Vxe [0;1], положим y = f (x) = 2x. Эта функция отображает

весь [0;1] на весь [0;2] и взаимно однозначна: f (a) = f (b), т. е.

2а = 2р^а = р, т. е. получили [0;1]~[0;2].

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

Запись: A или cardA . Итак, A = B & A~B.

Ясно, что понятие мощности есть обобщение понятия количества элементов в конечном множестве. (Можно и формально определить кардинальное число как элемент фактор - множества M / E, где M - множество всех множеств;

E - отношение равномощности множеств, но начинающему это не прибавит ясности понимания).

Ограничившись интуитивным представлением, согласимся на то, что кардинальные числа или мощности - это элементы некоторого множества символов, причем эквивалентным множествам соответствует один символ, неэквивалентным - разные.

Неизбежен вывод, что натуральные числа следует рассматривать как мощности конечных множеств: если

A = {a₁, a₂,..., a_n} , то A = n. Сразу же примем, по определению,

что 0 = 0. Это хорошо согласуется с «наглядностью». Итак, среди кардинальных чисел (мощностей) имеется и число 0, и все натуральные числа. Понятно, что этим дело не ограничивается: множество N бесконечно и у него свое кардинальное число, явно бесконечное. К кардинальным бесконечным числам мы скоро вернемся, а теперь установим простые свойства равномощности, которые часто бывают необходимы.

Пусть { A_i }_ie/, { Bj }_iei - дизъюнктные семейства множеств,

(т. е. i ф j ^ A п A_t = 0ЛД п B_t =0). Обозначим A = u A,

iel

B = u B_t. Если i e I ^ A = B_t, то можно ожидать, что A = B.

iel

Это действительно так.

Теорема 1 (принцип склеивания)

Если { A }_ieI, { B }_jeI - дизъюнктные семейства множеств,

A = B_t для всех i е I, то u A = u B_t

.

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

Если f : Д « B_i - биекция, то, очевидно, f₀ = u f есть

ieI

биекция A на B . Теорема доказана.

При сравнении мощностей иногда приходится «зажимать» множество между двумя эквивалентными. В какой-то мере это аналог теоремы о пределе промежуточной последовательности.

Теорема 2 (о промежуточной мощности)

Если Д с Дс A, A₂ ~A, то A~A. Доказательство

Пусть f : A « Д - биекция. Обозначим f ( A ) = А . Тогда A ~Д. А с А. Пусть f ( F₂) = Д . Продолжим этот процесс. Обозначим A = A₀ , имеем:

A з A з А з A, з Д з A3 з...

(*)

Д \ Д ~А \ Д Аг \ А ~А \ Аз

( А \ Д) п (А \ Аг ) = 0 ( д\ Аг ) п ( а \ Аз )=0

(А, \ Аз) п (д\ А ) = 0

Обозначим B = п Ai.

i=0

С одной стороны,

А = ( А \ Д) u (Д\ Аг) u (Д\ A3) u (АЛ A) u (А\ \ Аз) u... u B

.

С другой стороны,

4 = ( 4 \ 4) и (4г \ A) и (4\ A) и (д\ 4) и... и B.

Используя соотношения (*), (**), попарную непересе­каемость множеств и принцип склеивания, получаем: A~A₁ . Теорема доказана.

В некоторых случаях построить биекцию f : A « B сложно или технически неудобно. Оказывается, можно строить биекции A « B, 4 « B, где 4 е A, Ц е B и, тем не менее, получать A~B.

Теорема 3 (Г. Кантор, 1845 - 1918, Ф. Бернштейн, 1878 - 1956, Э. Шредер, 1841 - 1902)

Если 4 е A, Ц е B, 4 ~B, Д ~A, то A~B. Доказательство

Пусть f : B « A₁ - биекция. Обозначим A ={ a e 4: a = f (t\), b\e B_l} , т. е. 4 = f ( Д). Тогда A з A₁ з A₂ . Получаем: B₁~A, B₁~A₂ . В силу теоремы 2 о промежуточной мощности A~A₁ .

Итак, A~A a 4 ~B. Значит, A~B. Теорема доказана.

Следует обратить внимание на важный аспект.

Может быть, A е B, но A = B. Достаточно взять уже

рассмотренный пример A = [ 0;1], B = [ 0;2 ]. Два совпадающих

для конечных множеств аспекта - включение и эквивалентность - у бесконечных множеств уже различны.

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