Путеводитель для влюбленных в математику

Вначале математики относились к ней довольно беззаботно. Говорили просто: есть такая штука – множество и есть свойство «быть элементом множества», которое обозначают символом, а раз так, то можно двигаться дальше[90]. Но все это рано или поздно приводит к затруднениям.

Первое множество, приходящее нам в голову, – пустое множество. Там нет никаких элементов, и мы обозначаем его символом ∅. Мощность пустого множества равна нулю, и утверждение x ∈ ∅ ложно для любого x (потому что внутри ∅ ничего нет).

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

Форма записи {x | свойства x} определяет множество всех объектов, обладающих указанными свойствами.

А дальше возникает уйма сложностей.

В начале XX века философ и математик Бертран Рассел[91] размышлял о множестве A = {x | x – такое множество, что x ∉ x}.

Это множество всех множеств, чьими элементами не являются они сами. Например, пустое множество удовлетворяет условию: ∅ ∉ ∅, потому что пустое множество не содержит элементов. Таким образом, ∅ ∈ A.

Дальше Рассел задал роковой вопрос: входит ли множество A во множество A?

• Если ответ «да», то A∈A. Но тогда не выполняется условие попадания во множество A: оно не должно быть элементом самого себя.

• Если ответ «нет», то A∉A. Тогда выполняется условие попадания во множество A, и оно является элементом самого себя.

Если A∈A, то A∉A. Если A∉A, то A∈A. Но не может же такого быть, что A и входит, и не входит в A! Что-то пошло не так[92].

Одно из решений этого противоречия заключается в том, что множества A просто не существует. Нет его, и все тут.

После работ Рассела подход к теории множеств претерпел существенные изменения. Четкие, ясные, применимые на практике правила закрепили, как формировать множества и какие операции с ними можно совершать[93]. Определение множества и ∈ входит в свод правил непрямым образом. Мы не объясняем, что́ это; мы просто описываем, как оно себя проявляет. Мы говорим, что есть такие вещи, как множества, у них есть определенные свойства, а еще есть правила, по которым мы с ними работаем. Эти правила не позволили парадоксу Рассела вздыбить свою безобразную голову, и противоречий больше не возникало.

Но вернемся к вопросу: сколько всего действительных чисел? Мы знаем, что мощность множества положительных целых чисел равна И мы знаем, что Следует ли из этого, что Иными словами, существуют ли множества, чья мощность больше, чем ℤ⁺, но меньше, чем ℝ?[94] Кантор верил, что но не мог найти доказательство; свое предположение он назвал континуум-гипотезой. Многие ученые заинтересовались этим вопросом. В 1900-е годы немецкий математик Давид Гильберт составил перечень важнейших математических проблем наступающего XX века. Доказательство (или опровержение) континуум-гипотезы вошло в его перечень первым номером.

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

Ну и ну! Математику ценят за то, что на все вопросы (обычно) находится точный ответ. «Может быть и так, и этак» разрушает определенность. Как с этим жить?

Работы Курта Гёделя (1940-х годов) и Пола Коэна (1960-х) показали, что общепринятые правила аксиоматической теории множеств неполны и потому не позволяют ответить на поставленный вопрос. Точнее говоря, эти математики продемонстрировали: нельзя ни доказать, ни опровергнуть то, что существуют множества, чья мощность больше, чем ℤ⁺, но меньше, чем ℝ. Другими словами, можно принять или допущение или допущение Дальше мы получим две разные математические системы. Обе корректны, просто непохожи друг на друга.

Глава 9Числа Фибоначчи[95]

Квадраты и домино

Начнем с укладки квадратов и домино. Вообразим длинную горизонтальную рамку размерами 1 × 10. Мы хотим полностью заполнить ее квадратами 1 × 1 и костяшками домино 1 × 2, не оставив ни единой щели. Вот картинка:

Вопрос: сколькими способами это можно сделать?

Для удобства обозначим число вариантов F₁₀. Перебирать их все и потом пересчитывать – тяжелый труд, чреватый ошибками. Гораздо лучше упростить задачу.

Не будем с места в карьер искать F₁₀, начнем с F₁. Это проще простого! Нам нужно заполнить рамку 1 × 1 квадратами 1 × 1 и костяшками домино 1 × 2. Домино не поместится, остается единственное решение: взять один квадрат. Другими словами, F₁ = 1.

Теперь разберемся с F₂. Размер рамки 1 × 2. Можно заполнить ее двумя квадратами или одной костяшкой домино. Таким образом, есть два варианта, и F₂ = 2.

Дальше: сколькими способами можно заполнить рамку 1 × 3? Первый вариант: три квадрата. Два других варианта: одна костяшка домино (две не влезут) и квадрат слева или справа. Итак, F₃ = 3.

Еще один шаг: возьмем рамку 1 × 4. На рисунке показаны все варианты заполнения: