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

НЕВОЗМОЖНЫЕ ФИГУРЫ, ПРОДОЛЖАЮЩИЕСЯ ДО БЕСКОНЕЧНОСТИ

Сэр Роджер Пенроуз разработал в сотрудничестве со своим отцом, Лайонелом Пенроузом, несколько невозможных геометрических фигур и послал их голландскому художнику М. К. Эшеру (одному из героев книги «Гёдель, Эшер, Бах»), а тот использовал их в своих гравюрах. К числу наиболее знаменитых из этих фигур относятся две следующие{34}:

Треугольник Пенроуза

Лестница Пенроуза – нескончаемое путешествие

Только представьте себе, как вы поднимаетесь по этой лестнице – все поднимаетесь и поднимаетесь и все же все время возвращаетесь в одну и ту же точку. Эшер добавил череду вечно поднимающихся и вечно спускающихся монахов: все они оказываются в том же месте, с которого начали движение.

Ну что же, мы познакомились с несколькими интересными концепциями, но теперь нам пора вернуться к теории Кантора и узнать, что бесконечность бесконечна.

Бесконечность бесконечна

Существует ли множество чисел, мощность которого больше мощности множества вещественных чисел? Есть ли вообще «наибольшее» значение мощности?

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

Булеаны

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

ОПРЕДЕЛЕНИЕ БУЛЕАНА

Пусть дано множество А. Множество, состоящее из всех подмножеств А, называется булеаном А и обозначается Р(А).

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

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

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

МИНИ-ТЕОРЕМА

Если #A = n, то #P(A) = 2ⁿ (где # – количество элементов).

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

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

.

Ч. т. д.

ТЕОРЕМА КАНТОРА

Мощность любого множества А строго меньше, чем мощность P(A).

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

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

Две головоломки для математиков

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