Восемь этюдов о бесконечности. Математическое приключение - страница 73

Тот факт, что множества, имеющего наибольшую мощность, не существует, доказал сам Кантор. Собственно говоря, в этом случае доказательство Кантора было конструктивным, потому что он показал, что для любого данного множества всегда можно найти множество еще большей мощности и как это сделать. Такие множества называются показательными множествами, или булеанами.

Прежде чем мы перейдем к самой теореме, познакомимся с одной новой концепцией.

Предположим, например, что A = {17, 42, 0}. Тогда булеан Р(А) будет построен следующим образом: P(A) = {{}, {17}, {42}, {0}, {17, 42}, {17, 0}, {42, 0}, {17, 42, 0}}.

Символ «{}» обозначает пустое множество, которое считается подмножеством любого множества А. Возможно, вы помните, что ранее в этой книге мы использовали для обозначения пустого множества символ ∅. Оба эти символа – {} и ∅ – обозначают одно и то же. Отметим, что множество А также считается подмножеством самого себя. Если подсчитать количество подмножеств, окажется, что в самом множестве А содержится три элемента, а в булеане А – восемь элементов.

Я уверен, что вам тут же пришло в голову равенство 2³ = 8. Случайна ли эта связь? Нет, не случайна.

Доказательство того, что булеан множества, содержащего n элементов, содержит 2^>n подмножеств, получено при поддержке Уильяма Шекспира и состоит в следующем: каждый элемент исходного множества должен решить, «быть или не быть» элементом каждого конкретного подмножества. Следовательно, поскольку у каждого элемента есть две возможности относительно каждого отдельного подмножества, суммарное число возможностей для n элементов равно 2^>n.

Чтобы пояснить эту концепцию на конкретном примере, предположим, что мы набираем подмножество из элементов множества A = {17, 42, 0}. 17 и 0 «решают» стать элементами этого подмножества, а 42 отказывается. В сочетании эти решения дают подмножество {17, 0}. Решения каждого из элементов множества однозначно определяет состав каждого конкретного подмножества; следовательно, количество подмножеств равно количеству уникальных решений, то есть 2 × 2 × 2 × … × 2 = 2^>n.

Ч. т. д.

Попросту говоря, теорема Кантора означает, что «количество» элементов множества А, то есть #A, должно быть строго меньше, чем «количество» подмножеств в соответствующем булеане, P(A). Другими словами, булеан любого множества должен иметь бо́льшую мощность, чем само это множество.

Теперь возьмем бесконечное множество, например счетное множество с мощностью ℵ_>0 или континуальное множество с мощностью ℵ. Мощность их булеанов обозначается соответственно

1. Докажите теорему Кантора (подсказка: парадокс Рассела).

2. Поскольку мощность множества натуральных чисел равна ℵ_>0, мощность множества его подмножеств должна быть

Докажите, что

Другими словами, докажите, что мощность всех подмножеств множества натуральных чисел равна мощности континуума.

В 1897 г. итальянский математик Чезаре Бурали-Форти представил парадокс, который впоследствии стал называться его именем. Его можно описать следующим образом.

Рассмотрим множество всех множеств, то есть включающее в себя множество всех живущих ныне людей, множество всех людей, которые жили в прошлом, множество всех песен, которые можно сочинить, множество всех женщин, которых никогда не показывали на Fashion Channel[60], множество всех женщин, которых зовут Гризельда, множество всех цветов, множество всех идей, о которых никто никогда не сможет подумать, множество всех сражений, в которых я не участвовал, множество всех вещественных чисел, множество всех кинофильмов, которые не поставил Тарковский, множество всех кинофильмов, которые можно или можно было посмотреть на сайте YouTube, множество всех функций, множество всех философов, которые никогда не страдали от депрессии, множество всех молекул, которые находятся в данный момент в подвале моего дома… Теперь прибавим к нему все подмножества всех множеств. Короче говоря, пусть в этом множестве множеств содержится все, о чем только можно помыслить.