Московское математическое общество, Московский центр непрерывного математического образования, Малый мехмат МГУ

Серия "Библиотека «Математическое просвещение»"

И. В. Ященко Парадоксы теории множеств


4. Равномощность множеств

Рассмотрим два множества A и B.

Отображение f из A в B (обозначается f: A ® B) – это правило, которое каждому элементу множества A ставит в соответствие элемент множества B, причем ровно один. (При этом не запрещается двум элементам множества A ставить в соответствие один и тот же элемент множества B, рис. 1, а .)

а ) б )
Рис. 1

Отображение f называется взаимно однозначным , если каждый элемент множества B поставлен в соответствие ровно одному элементу множества A (рис. 1, б ).

Множества A и B называются равномощными , если существует взаимно однозначное отображение f: A ® B. Понимать это можно так: множества равномощны, если в них одинаковое количество элементов.

Например, множества {0,1,2} и {лошадь,корова,телевизор} равномощны, а множества {0,1,2} и {лошадь,корова} неравномощны*7. А равномощны ли множества Ж и {Ж}? Неравномощны: в множестве Ж нет ни одного элемента, а в множестве {Ж} есть один элемент – пустое множество (множество {Ж} – это коробка, в которой лежит пустое множество, а пустое множество – это коробка, в которой ничего не лежит).

*7 Телевизор был по делу...

Таблица 1
A P(A)
Ж {Ж}
{1} {Ж, {1}}
{1,2} {Ж, {1}, {2}, {1,2}}
Таблица 2
j
1 2 3 4 5 6 7 8
i 1 + + + - - - + -
2 + + - + - + - -
3 + - + + + - - -

Множества N (множество всех натуральных чисел) и N \ {1} (множество всех натуральных чисел без единицы) равномощны: легко видеть, что отображение f: N ® N \ {1}, f: n ® n + 1, является взаимно однозначным. Множества N и Z (множество всех целых чисел) также равномощны (достаточно рассмотреть отображение, которое переводит четные натуральные числа в целые неотрицательные, а нечетные – в отрицательные).

Обозначим через P(A) множество всех подмножеств множества A. Примеры P(A) для некоторых множеств A приведены в табл. 1. (Eстественно, подмножествами множества A являются и пустое множество, и само множество A.)

Подмножества множества A = {1,2,3} не будем выписывать в строчку (так недолго запутаться), а перечислим при помощи таблицы: если элемент i входит в подмножество с номером j, то на пересечении i-й строки и j-го столбца ставится плюс, если не входит – минус (табл. 2). Например, первый столбец, в котором стоит три плюса, соответствует подмножеству {1,2,3}.

Если составить такую же таблицу для множества из n элементов, каждое подмножество будет определяться столбцом из n символов (по числу элементов), и каждый символ можно выбрать двумя способами – либо " + ", либо " - ". Поэтому всего получится 2n различных столбцов. Итак, если в множестве A содержится n элементов, то в множестве P(A) содержится 2n элементов – существенно больше, чем в множестве A.

Но если подмножества конечного множества мы можем просто сосчитать, то как же быть с бесконечными? Например, подмножеств множества натуральных чисел бесконечно много, и самих натуральных чисел бесконечно много. Оказывается, что в множестве P(N) "бесконечно больше" элементов, чем в множестве N.

Теорема. Каково бы ни было множество A, множество его подмножеств P(A) неравномощно самому множеству A.

Это один из важнейших фактов теории множеств.

а ) б )
Рис. 2

Доказательство. Доказывать будем методом от противного*8. Предположим, что A равномощно P(A), т. е. существует взаимно однозначное отображение
f: A ® P(A),
которое каждому элементу a множества A ставит в соответствие f(a) – подмножество множества A.

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

Вспоминая рефлексивные прилагательные, которые сами обладают тем свойством, которое определяют, мы назовем элемент a хорошим, если a О f(a) (рис. 2, а ), и плохим, если a П f(a) (рис. 2, б ). Пусть П М A – множество всех плохих элементов (возможно, пустое). Поскольку отображение f взаимно однозначно, существует элемент x О A, такой что f(x) = П. Вопрос: элемент x – хороший или плохой? Предположим, элемент x – хороший. Но тогда x О f(x), а f(x) = П – множество плохих элементов, и значит, элемент x – плохой. Противоречие. Если же элемент x – плохой, то x П f(x) = П, а раз x не принадлежит множеству плохих элементов, то x – хороший. Снова противоречие. Получается, что элемент x, с одной стороны, должен принадлежать П, а с другой стороны, не должен.

Но сейчас, в отличие от парадокса с прилагательным "нерефлексивный", у нас есть лазейка. Мы получили противоречие, предположив, что A равномощно P(A). Значит, наше предположение неверно, т. е. A и P(A) неравномощны. Теорема доказана.

На головную страницу