В математике доказательство методом индукции — это способ выяснить, когда закономерность будет продолжаться до бесконечности. Если у нас есть последовательность таких утверждений:
1)-первое утверждение верно;
И
2)-если n-е утверждение верно, то утверждение n + 1 тоже верно;
то мы можем сделать вывод, что все эти утверждения верны.
Доказательство методом индукции аналогично падению костяшек домино. Если их поставить в ряд и n-я костяшка упадет, она толкнет костяшку n + 1, а значит, для того чтобы упали все костяшки, достаточно всего лишь опрокинуть первую костяшку.
Но вернемся к исходной задаче. Для того чтобы доказать, что машинальный рисунок может быть двухцветным, нам необходимо доказать, что:
1)-рисунок, состоящий из одного ряда, может быть двухцветным;
2)-если рисунок, состоящий из n рядов, может быть двухцветным, то и рисунок с количеством n + 1 рядов тоже будет двухцветным.
Доказать истинность первого утверждения очень просто: достаточно провести через всю страницу прямую линию и заштриховать область с одной стороны. А вот для того, чтобы доказать истинность второго утверждения, понадобится немного поразмышлять.
Начнем доказательство с рассмотрения n + 1 линий, как показано на схеме 1 ниже. (Очевидно, что для иллюстрации данного примера для числа n нужно выбрать какое-то значение, поэтому мы должны проследить за тем, чтобы наше доказательство было применимо к любому числу n.)
Если удалить одну линию, у нас получится рисунок с количеством линий n, показанный на схеме 2. Предположим, рисунок с количеством линий n можно сделать двухцветным, как на схеме 3. Теперь давайте восстановим линию, убранную на первом шаге (схема 4), и с одной ее стороны поменяем цвет на противоположный, другими словами — белые фрагменты сделаем заштрихованными, а заштрихованные — белыми. В результате каждый сектор над линией расположен рядом с сектором под линией, имеющим другой цвет. Следовательно, у нас пролучился двухцветный рисунок с количеством линий n + 1 (схема 5).
Доказательство теоремы о двухцветном рисунке методом индукции
Иными словами, мы продемонстрировали, что второе утверждение истинно. Процесс доказательства методом индукции завершен: все рисунки могут быть двухцветными. (Это доказательство распространяется только на рисунки, образованные посредством вычерчивания линий на квадратном листе. То же самое касается и любого фигурного рисунка с «завитушками», когда перо начинает и прекращает двигаться в одной и той же точке, но по мере перемещения может рисовать петли, спирали и пересечения любой сложности. Однако это утверждение требует более сложного доказательства.)
Труд Евклида «Начала» стал самым важным текстом в истории математики, и не только потому, что он раскрыл информацию о простых числах, треугольниках и т. д., но и благодаря тому, как именно это было сделано. Красота этого текста состоит в его строгости. Евклид весьма скрупулезен. Он ничего не упрощает, не дает никаких оценок и не делает заявлений, которые не может доказать. Если вы согласитесь с тем, что десять исходных предположений Евклида верны, то вы должны принять и истинность всех 465 теорем, сформулированных в книге. «Начала» — это образец применения аксиоматического метода, свидетельство силы дедуктивного мышления.
Говорят, что «Начала» Евклида переиздавались на протяжении большего периода и в большем количестве экземпляров, чем любая другая книга, за исключением Библии. Это очень уместное сравнение, поскольку более двух тысячелетий труд Евклида считался священным текстом, а аксиоматический метод принимался в качестве догмы. Однако в XVII веке появились первые признаки «нечестивости». Евклид полагался на аксиомы и определения, которые по самой своей сути не требовали доказательств и, разумеется, не содержали внутренних противоречий. Но, как мы видели в предыдущей главе, бесконечно малой величине, или величине, которая представляет собой одновременно и нечто, и ничто, свойственна именно такая внутренняя противоречивость. Ньютон и его современники использовали концепцию бесконечно малых величин, поскольку она позволила им доказать множество новых теорем, хотя им и приходилось закрывать глаза на противоречие с догматами Евклида, которые это за собой влекло.
Однако со временем математики поняли: для того чтобы исчисление было свободно от внутренних противоречий, оно должно опираться на более прочный фундамент. Было решено положить в основу исчисления не бесконечно малые величины, а нечто более надежное — концепцию предела. После упрощения исходных предположений и уточнения определений родился новый раздел математики — математический анализ. Сейчас этим термином обозначаются все области, связанные с исчислением, непрерывностью и бесконечными процессами. Одним из первых знаковых достижений математического анализа стала теорема о промежуточном значении, о которой шла речь в начале главы, гласящая, что непрерывная кривая покрывает все точки, расположенные между ее минимумом и максимумом.
Присущая XIX столетию склонность к научной строгости нашла свое отражение не только в математическом анализе, но и в других областях, в частности в евклидовой геометрии. Внимательно проанализировав «Начала», немецкий математик Мориц Паш сделал невероятное открытие: в рассуждениях Евклида есть прорехи, которые до сих пор никто не заметил, несмотря на то что «Начала» — наиболее изученный учебник по математике за всю историю. Евклид считал само собой разумеющимся, что, если три разные точки лежат на одной прямой, значит, одна из них находится между двумя другими. Однако если бы Евклид придерживался собственных стандартов, ему следовало бы сформулировать это утверждение в виде аксиомы. Евклид совершил неосмотрительную ошибку, позволив своим глазам воздействовать на дедуктивный процесс. В 1899 году Давид Гильберт предложил новую, усовершенствованную евклидову систему, содержащую 21 постулат.
Числа тоже были тщательно проанализированы по-новому. Числа — это ядро всей математики, по сути — всей науки. Но что такое число и почему 1 + 1 = 2?
В 1879 году немецкий математик Готлоб Фреге опубликовал свой труд Begriffsschrift («Исчисление понятий»), в котором представил тщательно проработанную, имеющую собственные обозначения систему исчисления, позволяющую определить истинность и ложность утверждений. Это было рождение математической логики — использования математических рассуждений для анализа других математических рассуждений.
Фреге хотел дать четкий ответ на вопрос «Что такое число?». Для решения этой задачи он позаимствовал у своего современника Георга Кантора концепцию множества. В математике часто бывает так, что на первый взгляд простое слово означает нечто сложное. Но только не в случае с множеством. Множество — это всего лишь совокупность объектов, обладающих одним и тем же свойством. Множеством может быть ящик яблок, пелотон (лидирующая группа) велосипедистов или звездная галактика.
Фреге разработал систему, в которой числа определяются как множества, аксиомы записываются с использованием его системы исчисления понятий, а истинность арифметических законов может быть доказана. Он планировал свести арифметику к системе не допускающих двойного толкования логических операций, в основу которой положены исходные предположения, лишенные внутренних противоречий, — например «отрицание отрицания утверждения А означает утверждение А» [6]. Работа с такими концепциями, как числа и сложение, не вызывает никаких трудностей, поэтому вы можете подумать, что задача Фреге была не особо сложной. Но на самом деле она потребовала огромных умственных усилий. В отличие от всех своих предшественников, использовавших числа и арифметические операции в качестве кирпичей для строительства здания математики, Фреге сделал подкоп непосредственно под ее фундамент.
Готлоб Фреге опубликовал свою теорию в книге The Basic Laws of Arithmetic («Основные законы арифметики»), первый том которой вышел в 1893 году. Однако, когда второй том уже находился в типографии, Фреге узнал весьма неприятную новость. Профессор философии Кембриджского университета Бертран Рассел прислал ему письмо, в котором указывал на одно противоречие. Поскольку задача сведения арифметики к логике состояла в создании системы, полностью лишенной противоречий, найти хотя бы одно несоответствие было равносильно катастрофе. Фреге быстро написал к книге дополнение: «Вряд ли ученый может столкнуться с чем-либо более нежелательным, чем разрушение основ в тот момент, когда работа уже завершена». С тех пор слово «нежелательный», которое использовал тогда Фреге, называют величайшим преуменьшением в истории математики.
Рассел открыл проклятие самореференции (самоотносимости).
Ниже приведены некоторые из моих любимых утверждений, ссылающихся на самих себя [7].
предложение должно начинаться с большой буквы.
В вопросе «быть или не быть» скомбинированы два предложения.
В этом предложении !!! преждевременно поставлен знак препинания
Однако самое древнее самоотносимое предложение приписывают критянину Эпимениду, который сказал: «Все критяне лжецы». Эпименид не только ссылается сам на себя, но и сам себе противоречит. Если он говорит правду, значит, он лжет, а если лжет, тогда говорит правду. Высказывание Эпименида (которое назвали «парадоксом лжеца») получило множество новых интерпретаций. Дайте ответ «да» или «нет» на такой вопрос: «Будет ли следующее слово, которое вы скажете, словом “нет”?»
Бертран Рассел понял, что парадокс самореференции нанесет серьезный удар по проекту Фреге и, возможно, даже погубит его. Преимущество использования множеств в качестве основы арифметики состоит в том, что эту концепцию легко понять: множество — это просто совокупность объектов. Однако Рассел изобрел такое множество:
Множество всех множеств, которые не содержат себя в качестве своего элемента.
Большинство множеств не содержат себя в качестве своего элемента. Множество туфель не является туфлей. Но некоторые множества все же являются исключениями. Например, множество концепций — это тоже концепция. А теперь посмотрим на множество Рассела. Содержит ли оно себя? Если предположить, что да, мы придем к выводу, что не содержит, а если предположить, что нет, то мы сделаем вывод, что содержит! Это множество имеет противоречие. Рассел провел аналогию с брадобреем одной деревни, на стене дома которого висела табличка: «Я брею всякого, кто сам не бреется». Кто же бреет брадобрея? Если он сам бреется, значит, он не побреет себя, а если он сам не бреется, значит, он себя побреет. Мы имеем бесконечный цикл рассуждений, противоречащих друг другу.
Парадокс Рассела демонстрирует, что множества в том виде, как их представлял себе Фреге, нельзя использовать в качестве прочной основы для арифметики. Самореференция со свойственной ей внутренней противоречивостью способна испортить всю систему. Однако, вместо того чтобы отбросить проект Фреге как ошибочный, Рассел стал его величайшим сторонником. Мечта о том, чтобы поставить математику на надежную логическую основу, была слишком заманчивой, чтобы от нее отказываться. На протяжении следующих десяти лет Рассел вместе с Альфредом Нортом Уайтхедом работал над усовершенствованием этой системы. Рассел и Уайтхед согласились с предположением Фреге о том, что множество может стать подходящей основой для чисел. Но, чтобы избавиться от парадоксов самореференции, они создали строгую иерархию множеств. На ее первом уровне находятся объекты, такие как книги или кошки. На втором — множества объектов первого уровня, такие как книги на моей полке или кошки на моей улице. На третьем — множества объектов второго уровня, такие как полки с книгами по математике или лондонские кошки, сгруппированные по улицам. Парадокс Рассела не может возникнуть, поскольку то или иное множество может быть только членом множества верхнего уровня, а значит, не может содержать само себя.
Рассел и Уайтхед ввели систему обозначений, определения и аксиомы, чрезвычайно строго и тщательно сформулированные. Стремление ученых к простоте и понятности разъяснений привело к написанию одного из самых сложных и неудобочитаемых текстов за всю историю математики. Только на 379-й странице авторы смогли доказать, что 1 + 1 = 2. Когда они предложили опубликовать книгу Principia Mathematica («Принципы математики»), издатель отказался это делать, поскольку не смог найти читателей, способных ее понять. Написание этой книги потребовало таких огромных умственных усилий, что Рассел больше никогда ничего не писал по математике или логике.
Польский специалист в области логики Альфред Тарский предложил иерархию языка (во многом напоминающую иерархию множеств Рассела), которая позволяет решить парадокс лжеца [8]. В соответствии с ней существует язык уровня 1 и метаязык уровня 2 для описания утверждений на языке уровня 1, а также метаязык уровня 3 для описания утверждений на языке уровня 2 и т. д. Истинность или ложность утверждений можно описывать только на метаязыке следующего уровня, поэтому утверждение не может приписывать истинность или ложность самому себе. Как объяснил однажды Рассел, если бы Эпименид заявил: «Я говорю неправду уровня n», это действительно была бы ложь, но ложь уровня n + 1.
Комедианты используют метаязык так же, как и логики [9]. Если шутка не удалась, всегда можно выйти из ситуации с юмором, отпустив шутку по поводу неудавшейся шутки.
Книга Principia Mathematica так и остается непрочитанной. Тем не менее предпринятая в ней попытка создать свободную от парадоксов аксиоматическую основу арифметики была с энтузиазмом подхвачена другими учеными. Аксиоматическая теория множеств считается величайшим интеллектуальным достижением начала XX столетия [10], приведшим к появлению замечательных работ в области математики, логики и философии. Стандартная система аксиом получила название ZFC (сокр. от имен математиков Эрнста Цермело (Ernst Zermelo) и Авраама Френкеля (Abraham Fraenkel)) с аксиомой выбора. Аксиома выбора гласит, что при наличии бесконечного количества множеств, каждое из которых содержит не менее одного элемента, можно создать новое множество, включающее по одному элементу из каждого множества. На первый взгляд эта аксиома кажется вполне справедливой, хотя на самом деле она крайне противоречива. Одна из самых горячих дискуссий в теории множеств касалась именно того, стоит ли включать эту аксиому в систему, потому что из-за этого начнут происходить весьма странные вещи.
Стефан Банах, польский математик, который доказал теорему о бутерброде с ветчиной в Шотландском кафе, а также Альфред Тарский, специалист в области логики, предложивший расселовскую иерархию языка, доказали, что если считать аксиому выбора истинной, то истинной будет и следующая теорема:
Шар можно разделить на конечное количество фрагментов, из которых можно собрать две идентичные копии исходного шара.
Эта теорема более известна как «парадокс Банаха — Тарского». Слово «парадокс» используется здесь потому, что на первый взгляд теорема противоречит законам физики, хотя в ее доказательстве нет логических противоречий. В физическом смысле собрать два шара из фрагментов одного невозможно, поскольку эти фрагменты представляют собой не цельную структуру, а совокупность бесконечного количества точек. Тем не менее теорема поражает воображение. Из нее следует, что любой шар можно разделить на части и составить из них любой другой объект, а значит, из горошины можно сделать солнце. (Несмотря на столь невероятные выводы, сейчас большинство математиков принимают аксиому выбора.)
Если суть шутки состоит в неожиданных выводах, то парадокс Банаха — Тарского — самая смешная теорема в математике.
В конце 1970-х, когда мне было около восьми лет, мы перешли на уроках математики от чисел к множествам. Я хорошо помню, как это происходило. Овал с несколькими точками олицетворял собой одно множество, а второй овал с несколькими точками — другое множество. Нам следовало соединить точки одного множества с точками другого, что показывало, в каком множестве больше точек. Я так и не понял, в чем смысл этих упражнений, и мне кажется, учителя тоже не понимали. Примерно через год на уроках перестали говорить о множествах, и я снова встретился с ними уже на втором курсе университета. Если вы учились в школе в 60-х, 70-х или 80-х годах XX века, вполне вероятно, что вас тоже кратко знакомили с теорией множеств. Присутствие этой дисциплины в учебной программе связано с именем Николя Бурбаки, самого плодовитого математика ХХ столетия.
В 1939 году Бурбаки опубликовал свою первую книгу из масштабной серии под названием Éléments de Mathématique («Начала математики»). «В прошлом считалось, что каждый раздел математики зависит от интуитивных знаний в этой области, на которых основаны концепции и истины, — писал он. — Однако в наши дни, как известно, можно, логически говоря, вывести практически всю человеческую математику из одного источника — теории множеств» [11]. Название этой серии содержало отсылку к Евклиду. Подобно тому как труд Евклида «Начала» формализовал математические знания древних греков в рамках системы аксиом, основанной на свойствах точек и линий, «Начала математики» Бурбаки формализовали современные математические знания в рамках аксиоматической системы, построенной на свойствах множеств. Выбор слова mathématique (в единственном числе, в отличие от английского mathematics) подчеркивал убежденность Бурбаки в единстве этой области знаний. Серия «Начала математики» состояла из десятков книг общим объемом около 7000 страниц, причем не только по теории множеств, но и по таким дисциплинам, как алгебра, математический анализ и топология. Кроме того, Бурбаки была свойственна одна отличительная особенность, которая делала его уникальным среди современников. Такого человека не существовало.