[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, не оставив ни единой щели. Вот картинка:
Вопрос: сколькими способами это можно сделать?
Для удобства обозначим число вариантов F10. Перебирать их все и потом пересчитывать – тяжелый труд, чреватый ошибками. Гораздо лучше упростить задачу.
Не будем с места в карьер искать F10, начнем с F1. Это проще простого! Нам нужно заполнить рамку 1 × 1 квадратами 1 × 1 и костяшками домино 1 × 2. Домино не поместится, остается единственное решение: взять один квадрат. Другими словами, F1 = 1.
Теперь разберемся с F2. Размер рамки 1 × 2. Можно заполнить ее двумя квадратами или одной костяшкой домино. Таким образом, есть два варианта, и F2 = 2.
Дальше: сколькими способами можно заполнить рамку 1 × 3? Первый вариант: три квадрата. Два других варианта: одна костяшка домино (две не влезут) и квадрат слева или справа. Итак, F3 = 3.
Еще один шаг: возьмем рамку 1 × 4. На рисунке показаны все варианты заполнения:
Мы нашли пять возможностей, но где гарантия, что мы ничего не упустили? Есть способ проверить себя.
В левом конце рамки может быть или квадрат, или костяшка домино. В верхнем ряду на рисунке – варианты, когда слева квадрат, в нижнем ряду – когда слева домино.
Допустим, слева квадрат. Оставшуюся часть нужно заполнить квадратами и домино. Другими словами, нужно заполнить рамку 1 × 3. Это дает 3 варианта, так как F3 = 3.
Если слева домино, размер оставшейся части 1 × 2, и заполнить ее можно двумя вариантами, так как F2 = 2.
Таким образом, у нас есть 3 + 2 = 5 вариантов, и мы удостоверились, что F4 = 5.
Теперь ваша очередь. Подумайте пару минут и найдите все варианты заполнения для рамки 1 × 5. Их немного. Решение – в конце главы. Можете отвлечься и подумать.
Вернемся к нашим квадратам. Хочется верить, что вы нашли 8 вариантов, так как есть 5 способов укладки, где слева квадрат, и еще 3 способа, где слева домино. Таким образом, F5 = 8.
Подытожим. Мы обозначили FN количество способов заполнения рамки 1 × n квадратами и костяшками домино. Нам необходимо найти F10. Вот что мы уже знаем:
Двигаемся дальше. Чему равно F6? Можно нарисовать все варианты, но это скучно. Лучше разобьем вопрос на две части. Сколькими способами можно заполнить рамку 1 × 6, если слева (a) квадрат и (b) костяшка домино? Хорошая новость: мы уже знаем ответ!
В первом случае нам остается пять квадратов, а мы знаем, что F5 = 8. Во втором случае нужно заполнить четыре квадрата; нам известно, что F4 = 5. Таким образом, F5 + F4 = 13.
Чему равно F7? Исходя из тех же соображений, F7 = F6 + F5 = 13 + 8 = 21. А как насчет F8? Очевидно, F8 = F7 + F6 = 21 + 13 = 34. И так далее. Мы обнаружили следующую взаимосвязь:
Fn = Fn– 1 + Fn –2.
Еще несколько шагов – и мы найдем искомое число F10. Правильный ответ – в конце главы.
Числа Фибоначчи – это последовательность:
1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, …
Она выстраивается по таким правилам:
– первые два числа 1 и 1;
– каждое следующее число получаем сложением двух предыдущих.
Будем обозначать n-ный элемент последовательности Fn, начиная с нуля:
F0 = 1, F1 = 1, F2 = 2, F3= 3, F4= 5, …
Очередной элемент мы вычисляем по формуле:
Fn = Fn– 1 + Fn –2.
Как мы видим, задача об укладке квадратов и домино привела нас к последовательности чисел Фибоначчи[96].
Попробуем сложить первые несколько чисел Фибоначчи. Что мы можем сказать о сумме F0 + F1 + … + Fn для любого n? Давайте проделаем кое-какие вычисления и посмотрим, что получится.
Обратите внимание на результаты сложения внизу. Видите ли вы закономерность? Повремените немного, прежде чем двигаться дальше: будет лучше, если вы найдете ответ самостоятельно, а не прочтете уже готовое решение.
Хочется верить, вы увидели, что результаты суммирования, если к ним приплюсовать по единице, тоже выстраиваются в последовательность чисел Фибоначчи. Например, сложение чисел от F0 до F5 дает:
F0 + F1 + F2 + F3 + F4 + F5 = 1 + 1 + 2 + 3 + 5 + 8 = 20 = F7 – 1.
Сложение чисел от F0 до F6 дает 33, что на единицу меньше F8 = 34. Мы можем записать формулу для неотрицательных целых чисел