Пятница, 20.07.2018, 13:54
Ш  К  О  Л  А     П  И  Ф  А  Г  О  Р  А
      Предмет математики настолько серьезен, что нужно
не упускать случая, сделать его немного занимательным".
                                                                           Блез Паскаль
Главная | Регистрация | Вход Приветствую Вас Гость | RSS
ПАМЯТКИ ПО МАТЕМАТИКЕ   ВЕЛИКИЕ МАТЕМАТИКИ   ТЕОРИЯ ЧИСЕЛ   МАТЕМАТИЧЕСКАЯ ЛОГИКА
УРОКИ МАТЕМАТИКИ В ШКОЛЕ
МАТЕМАТИЧЕСКАЯ КЛАДОВАЯ
В МИРЕ ЗАДАЧ
ЕГЭ ПО МАТЕМАТИКЕ
МАТЕМАТИКА В НАЧАЛЬНОЙ ШКОЛЕ
ВАРИ, КОТЕЛОК!
УДИВИТЕЛЬНАЯ МАТЕМАТИКА
ВЫСШАЯ МАТЕМАТИКА
В МИРЕ ИНТЕРЕСНОГО
Категории раздела
ПРОСТЫЕ ЧИСЛА. ДОЛГАЯ ДОРОГА К БЕСКОНЕЧНОСТИ [37]
КОГДА ПРЯМЫЕ ИСКРИВЛЯЮТСЯ. НЕЕВКЛИДОВЫ ГЕОМЕТРИИ [23]
МУЗЫКА СФЕР. АСТРОНОМИЯ И МАТЕМАТИКА [57]
МАГИЯ ЧИСЕЛ. МАТЕМАТИЧЕСКАЯ МЫСЛЬ ОТ ПИФАГОРА ДО НАШИХ ДНЕЙ [27]
ИНВЕРСИЯ [20]
ИСТИНА В ПРЕДЕЛЕ. АНАЛИЗ БЕСКОНЕЧНО МАЛЫХ [47]
БЕСКОНЕЧНОСТЬ В МАТЕМАТИКЕ [43]
МАТЕМАТИЧЕСКАЯ ЛОГИКА И ЕЕ ПАРАДОКСЫ [6]
ИЗМЕРЕНИЕ МИРА. КАЛЕНДАРИ, МЕРЫ ДЛИНЫ И МАТЕМАТИКА [33]
АБСОЛЮТНАЯ ТОЧНОСТЬ И ДРУГИЕ ИЛЛЮЗИИ. СЕКРЕТЫ СТАТИСТИКИ [31]
КОДИРОВАНИЕ И КРИПТОГРАФИЯ [47]
МАТЕМАТИКА В ЭКОНОМИКЕ [39]
ИСКУССТВЕННЫЙ ИНТЕЛЛЕКТ И МАТЕМАТИКА [35]
ЧЕТВЕРТОЕ ИЗМЕРЕНИЕ. ЯВЛЯЕТСЯ ЛИ НАШ МИР ТЕНЬЮ ДРУГОЙ ВСЕЛЕННОЙ? [9]
ТВОРЧЕСТВО В МАТЕМАТИКЕ [44]
ЗАГАДКА ФЕРМА. ТРЕХВЕКОВОЙ ВЫЗОВ МАТЕМАТИКЕ [30]
ТАЙНАЯ ЖИЗНЬ ЧИСЕЛ. ЛЮБОПЫТНЫЕ РАЗДЕЛЫ МАТЕМАТИКИ [95]
АЛГОРИТМЫ И ВЫЧИСЛЕНИЯ [17]
КАРТОГРАФИЯ И МАТЕМАТИКА [38]
ПОЭЗИЯ ЧИСЕЛ. ПРЕКРАСНОЕ И МАТЕМАТИКА [23]
ТЕОРИЯ ГРАФОВ [33]
НАУКА О ПЕРСПЕКТИВЕ [29]
ЧИСЛА - ОСНОВА ГАРМОНИИ. МУЗЫКА И МАТЕМАТИКА [15]
Статистика

Онлайн всего: 2
Гостей: 2
Пользователей: 0
Форма входа

Главная » Файлы » МИР МАТЕМАТИКИ » МАТЕМАТИЧЕСКАЯ ЛОГИКА И ЕЕ ПАРАДОКСЫ

Парадоксы
18.11.2015, 19:27

Парадокс есть сама страсть мыслителя.

Сёрен Кьеркегор


Хотя родители юного Бертрана Рассела в своем завещании указали, что их младший сын должен воспитываться на тех принципах, во имя которых они сражались во времена викторианской Англии, бабушка со стороны отца не допустила, чтобы этот мальчик с умными глазами стал атеистом. Ребенка передали воспитательницам, которые в классическом духе обучали Бертрана религии и иностранным языкам, благодаря чему юный аристократ в совершенстве овладел французским, немецким и итальянским и несколькими годами позже смог с легкостью путешествовать по всему миру. Однако в те далекие дни юности Бертран думал лишь о замысловатых греческих символах, которые так подходили для того, чтобы выразить его печальные мысли о самом себе и о выпавшей ему доле.

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

Он не сделал этот последний шаг не потому, что ему не хватило духа, а потому, что когда Бертрану было 11 лет, его брат Фрэнк открыл ему врата рая, который стал для него настоящим спасением и о котором еще столько предстояло узнать. Знакомство юного Рассела с райским садом «Начал» Евклида, к которым он обращался всякий раз, когда враждебный мир делался невыносимым, было подобно первой любви. Однако счастье Бертрана было неполным — хотя, по рассказам, греческий мудрец доказал все, каждый, кто открывал страницы этой книги, должен был принять на веру следующее утверждение: «Точка есть то, что не имеет частей».



Бертран Рассел в 1893 году в возрасте 21 года, удостоенный степени бакалавра математики кембриджского Тринити-колледжа.


А если бы она имела части? «От всякой точки до всякой точки можно провести прямую». А если нельзя? Бертран неохотно прислушался к совету брата, говорившего, что если не принять аксиомы на веру, обучение продолжить нельзя.

Прошло время, и спустя 12 лет после приезда в Олд-Саутгейт Бертран снова оказался в тупике — как в те моменты, когда он думал о самоубийстве. За эти 12 лет успело произойти многое: он получил степень по математике и философии в Кембриджском университете, где тайное общество лучших студентов, называвшее себя «Апостолами», наконец подарило ему тысячи часов бесед, которые он надеялся найти во время учебы. Он успел совершить путешествие, опубликовать первые книги о немецкой социал-демократии и основах геометрии и сочетаться браком с Элис Пирсолл — дочерью американских квакеров. Основным занятием Рассела оставалась математика, а его целью было свести аксиомы геометрии к законам логики, чтобы никакое утверждение больше не требовалось принимать на веру.

Попытавшись вывести из логики всю математику, Бертран столкнулся с противоречием, которым на первый взгляд казалась одна из задачек вида «Может ли мужчина жениться на сестре своей вдовы?». Чтобы увидеть, в чем заключается подвох, достаточно проанализировать значение каждого понятия. Однако разрешение противоречия, которое волновало Рассела, требовало гораздо больших усилий: два лета подряд он день за днем глядел на чистый лист бумаги, утро сменялось полуднем, наступал вечер, а лист по-прежнему был чистым, и в конце концов он пришел к мысли о том, что не существует множества всех множеств, которые не содержат сами себя.


Теория множеств

Чтобы понять, в чем заключается парадокс, который положил конец счастливой и спокойной жизни Бертрана Рассела, сначала в нескольких словах опишем основы теории множеств. В предыдущей главе мы хотели показать, что основы аксиоматического метода можно встретить уже в «Началах», однако для Евклида аксиомы были очевидными истинами, а не исходными утверждениями, выбранными из соображений удобства. Со временем языка Евклида оказалось недостаточно для изложения новых математических идей. Доказать сложные теоремы XIX века исключительно с помощью слов и фигур было так же сложно, как сегодня перевести на один из мертвых языков инструкцию для iPhone.

Постепенно математическая нотация становилась все более символической: была введена форма, пригодная не только для записи рядов, производных и интегралов, — благодаря работам английского математика Джорджа Буля (1815–1864) стало возможным записывать в виде уравнений логические высказывания. Геометрия изучает фигуры в пространстве, арифметика — числа, математический анализ — средства, необходимые для формализации физических законов, алгебра — уравнения. Можно ли найти язык, общий для всех этих дисциплин, который сделал бы очевидным их единство?

* * *

БУЛЕВА АЛГЕБРА

Джордж Буль был первым, кто провел аналогию между логическими связками «и» и «или» и операциями умножения и сложения в алгебре. Он также ввел обозначения 0 («ложь») и 1 («истина») для двух значений логических переменных. Перед тем как рассмотреть пример, напомним, что при умножении чисел результат равняется нулю только тогда, когда одно из этих чисел равно нулю.

Допустим, что мы хотим перевести на язык алгебры высказывание «Все люди смертны».

Буль предложил обозначить через р значение истинности высказывания «быть человеком», за q — значение высказывания «быть смертным». Этот хитроумный прием позволяет свести содержание фразы к уравнению р·(1q) = 0.

Так, если некто является человеком, то р принимает значение истинности 1 («истина»).

Уравнение гласит, что произведение чисел р и (1 — q) равно нулю. Так как р отлично от нуля, то 1 — q должно равняться нулю. Однако это означает, что равно 1 («истина»), то есть что человек смертен.



Джордж Буль, один из прародителей вычислительной алгебры.

* * *

Размышляя о проблеме, которая изначально не имела ничего общего с этим скорее философским, нежели математическим вопросом, Георг Кантор в период с 1878 по 1884 год считал, что нашел ответ в теории множеств. На интуитивном уровне множество определяется как совокупность объектов: мы говорим о множестве животных, множестве парков Парижа или множестве читателей этой книги.

Едва начав работу, Кантор осознал, что в его новой теории рассматривались одновременно два объекта совершенно разной природы: конечные и бесконечные множества. По сути задача о нахождении числа элементов множества (математики называют его кардинальным числом, или мощностью множества) имеет разные решения в зависимости от того, конечное или бесконечное множество мы рассматриваем. Представим очень простую ситуацию: допустим, мы хотим узнать, имеют ли два конечных множества одно и то же кардинальное число, например равно ли число букв в слове «нахальство» числу цветов радуги. Очевидный метод заключается в том, чтобы подсчитать элементы каждого множества и сравнить результаты: так как в слове Н-А-Х-А-Л-Ь-С-Т-В-О десять букв, а в радуге семь цветов (красный, оранжевый, желтый, зеленый, голубой, синий, фиолетовый), то эти два множества содержат разное число элементов. Но что произойдет, если мы применим этот же метод к двум бесконечным множествам? В этом случае необходимо либо считать, что все бесконечные множества обладают одинаковым кардинальным числом и поставить на этом точку, либо использовать какой-то другой метод.

Вернемся к конечным множествам и посмотрим, что произойдет, если мы будем не рассматривать две совокупности по отдельности, а станем по очереди извлекать из них по одному элементу: начнем с буквы Н и красного цвета и т. д., пока не дойдем до буквы С, которой соответствует фиолетовый цвет. В этот момент одно из двух множеств уже «закончилось», а в другом осталось еще три элемента — буквы Т, В и О, следовательно, кардинальное число этого множества больше. Операция, которую мы попытались проделать, в математике называется установлением биекции между двумя множествами и означает присвоение каждому элементу множества X элемента другого множества Y «один к одному» так, что выполняются следующие условия.

1. Не существует двух элементов X таких, которым соответствует один и тот же элемент Y.

2. Каждому элементу Y соответствует какой-либо элемент множества X.

Таким образом, используя введенную нами терминологию, можно сказать, что кардинальные числа двух множеств равны, если между ними можно установить биекцию. Нетрудно показать, что установить биекцию между двумя конечными множествами с разным числом элементов нельзя, так как либо несколько элементов X будут поставлены в соответствие одному и тому же элементу Y, либо какой-то элемент останется без пары.



Три примера отображения конечных множеств, лишь одно из которых (см. рис. 3) является биекцией, так как на рис. 1 двум элементам первого множества сопоставлен один элемент второго, а на рис. 2 один из элементов исходного множества остался без пары.


Преимущество этого подхода в том, что его можно применить к бесконечным множествам. Таким образом, будем говорить, что кардинальные числа двух множеств равны, если между множествами можно установить биекцию. Первое следствие этого, возможно, удивит читателя: существует столько же четных чисел, сколько четных и нечетных, вместе взятых. Как такое возможно? Для доказательства этого весьма неочевидного утверждения достаточно определить биекцию между натуральными и четными числами. Сопоставим 0 и 0, 1 и 2, 2 и 4, а произвольному п сопоставим число, в два раза большее него. При таком отображении различным числам всегда будут соответствовать разные числа, и любое четное число будет сопоставлено с числом, в два раза меньшим его. Так как оба свойства биекции выполняются, это означает, что существует столько же четных чисел, сколько и натуральных!

Переформулируем этот результат: «В отеле с бесконечным количеством комнат всегда найдется место для новых постояльцев, даже если все номера заняты». В самом деле, в гостиницах с конечным количеством номеров, где нет свободных мест, вам в лучшем случае подскажут, где находится ближайший отель. Но в гостиницах с бесконечным количеством номеров этого не происходит: так как в них столько же комнат, сколько комнат с четными номерами, можно использовать составленную нами биекцию и переселить постояльца из первого номера во второй, из второго — в четвертый и т. д., таким образом все комнаты с нечетными номерами окажутся свободными. И мы можем найти комнату для бесконечного числа путешественников. Возможно, владельцам отелей стоит взять это на заметку.

Существование подобных гостиниц, которые невозможно заполнить, — это не просто любопытный факт, связанный с четными числами, а основное свойство бесконечных множеств, как заметил Рихард Дедекинд в своей статье «Что такое числа и для чего они служат», опубликованной в 1888 году. Множество является бесконечным, если можно определить биекцию между ним и его частью. Очевидно, что с конечными множествами подобное невозможно, так как часть конечного множества не может быть поставлена в соответствие целому (как мы говорили выше, между двумя конечными множествами, число элементов которых равно m и n соответственно, можно установить биекцию только при m = n). Тем не менее натуральных чисел бесконечно много, так как часть этого множества, строго включенная в него, то есть множество четных чисел, имеет то же кардинальное число, что и все множество в целом. Следовательно, новое определение соответствует рассуждениям, основанным на аксиомах Пеано, с помощью которых мы в предыдущей главе доказали, что натуральных чисел бесконечно много. Однако множество натуральных чисел — это наименьшее бесконечное множество из всех, что можно представить.

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

Счетность множества означает, что между множеством X и множеством натуральных чисел можно установить биекцию. Так, каждому натуральному n можно поставить в соответствие элемент этого множества, который мы обозначим через хn, так, что если n и m различны, то хn и хm также различны. С другой стороны, все элементы можно записать в виде хn для некоторого n. Когда дети идут на экскурсию с классом, учитель иногда присваивает им номера, чтобы никто не потерялся.

Перед тем как сесть в автобус, каждый ученик громко выкрикивает свой номер: пе-е-ервый! второ-о-ой! тре-е-етий! Каждый ученик имеет свой номер, и ни один из номеров не повторяется. Элементы счетных множеств также имеют свои порядковые номера: «пе-е-ервый!» — это x1 «второ-о-ой!» — х2. Счетные множества — это множества, элементы которых можно выстроить в ряд. Мы показали, что множество четных чисел является счетным, так как их можно упорядочить: 0, 2, 4, 6, 8, 10… Это же справедливо и для положительных и отрицательных чисел, так как можно, начав с нуля, называть их поочередно: 0, 1, —1, 2, —2.

Элементы любого ли множества можно выстроить в ряд? Если это так, то все множества будут счетными, и мы придем к тому же, с чего начали, когда использовали примитивный метод подсчета элементов множества. Однако пусть читатель не беспокоится: одним из величайших достижений Георга Кантора стало открытие множеств, которые не являются счетными. Пусть дано множество, образованное бесконечными последовательностями нулей и единиц, то есть объектами вида 0100100010… или 1100101001… Покажем, что если мы будем считать это множество счетным, то придем к противоречию. В самом деле, если бы это множество было счетным, мы могли бы записать все его элементы в виде списка следующим образом:



Напомним, что аn, Ьn и сn принимают только значения 0 и 1. Составим элемент, который будет принадлежать к множеству бесконечных последовательностей нулей и единиц и при этом не будет упомянут в нашем списке. Для этого рассмотрим элементы, расположенные по диагонали и обведенные рамкой. Рассмотрим a0: если этот элемент равен 0, начнем нашу последовательность с 1, и наоборот. Так мы определим первый член нашей последовательности. Перейдем к b1 если этот элемент равен 0, то вторым членом нашей последовательности будет 1. Если же, напротив, этот элемент равен 1, то вторым членом последовательности будет 0. В общем случае для определения n-го члена нашей последовательности мы будем рассматривать соответствующий элемент на диагонали и записывать противоположное ему значение. Таким образом, мы получим последовательность, все члены которой будут иметь значение 0 или 1, следовательно, эта последовательность будет принадлежать к рассматриваемому множеству. Например, если наш список будет начинаться так:



то первыми членами составленной нами последовательности будут 1, 0, 0.

Так как этот метод составления последовательности нулей и единиц заключается в изменении значений элементов, расположенных по диагонали, он называется диагональным методом. Здесь мы хотим показать, что последовательность, полученная диагональным методом, является элементом рассматриваемого множества, однако не фигурирует в гипотетическом списке всех элементов этого множества. И действительно, наша последовательность не может быть первой последовательностью из списка, так как их первые члены отличаются. Она не может быть и второй последовательностью, так как мы изменили ее второй член, она не может быть ни третьей, ни четвертой: каждая последовательность из списка будет отличаться от составленной нами как минимум одним элементом — этот элемент будет располагаться на диагонали. Мы предположили, что множество последовательностей нулей и единиц счетное, то есть все его элементы можно представить в виде списка, и получили противоречие. Это доказывает, что наше множество не является счетным!

Мы посвятили несколько страниц объяснению основных понятий теории множеств не только для того, чтобы даже сформулировать парадокс Рассела. Доказательство того, что множество последовательностей нулей и единиц не является счетным, читатель может счесть не более чем виртуозным упражнением, однако оно позволит нам показать в главе 5, что существуют задачи, с которыми не могут справиться даже компьютеры, и установить пределы «сну разума», о котором говорится в названии этой книги. Мы также надеемся, что смогли продемонстрировать читателю, сколько тайн встречается тем, кто путешествует по миру бесконечных множеств.

* * *

ПРЕПОДАВАНИЕ ТЕОРИИ МНОЖЕСТВ В ШКОЛЕ

В 70-е годы группа последователей французской математической группы Бурбаки, которые, однако, в большинстве своем не были математиками, захотели ввести теорию множеств в курс начальных школ Европы. В этой учебной программе натуральные числа объяснялись как кардинальные числа конечных множеств. 0 определялся как кардинальное число пустого множества, а сложение 2 и 3 объяснялось как объединение множества из 2 элементов с другим множеством из 3 элементов, при этом не важно, что результат будет обозначаться 5, важно, что 2 + 3 = 3 + 2, так как не имеет значения, в каком порядке мы будем объединять элементы множеств. Как рассказывал Пьер Картье, в то время бывший секретарем группы Бурбаки, в результате этой политики в сфере образования дети возвращались из школы домой и плакали: «Мама, я не хочу быть множеством».



Диаграммы Венна — наиболее типичный способ представления множеств.

* * *

Парадокс Рассела

Бертран Рассел познакомился с теорией множеств в 1896 году. Ему было довольно трудно принять ее: автор книги, из которой Рассел узнал о существовании этой теории, входил в число тех, кто считал, что теория Кантора была недостаточно строгой, и уподоблял ее теологии, а Рассел в этот период стремился к максимальной научной строгости. Однако позднее он понял, что многие обвинения в адрес Кантора были необоснованными, и включил идеи этого немецкого математика в последнее издание «Начал математики», вышедшее в мае 1903 года. Знакомясь с новой литературой, чтобы дополнить последнее издание книги, Рассел открыл для себя труд Готлоба Фреге, который предвосхитил многие из его открытий, опередив Рассела на 20 лет.

Понять, что Фреге и Рассел вели речь об одном и том же, было не всегда просто: сложный символический язык Фреге, подобный нотной партитуре современной музыки, не имел ничего общего с простой и понятной нотацией, которую Рассел перенял у Пеано.

Подробно изучив «Исчисление понятий» (Begriffsschrift) — книгу, в которой Фреге впервые изложил результаты своих исследований, — Рассел начал задумываться о множестве всех множеств, которые не принадлежат сами себе. Множество всех котов определенно не является котом, однако множество всего, что только можно себе представить, также можно представить. О таких множествах мы говорим, что они принадлежат сами себе.



Гэтлоб Фреге — создатель математической логики.



Страница «Исчисления понятий» Гэтлоба Фреге.


Конечно, это определение несколько расплывчато, поэтому давайте одним махом разберемся со всеми множествами такого типа. Обозначим через R (по первой букве фамилии Рассела) множество всех множеств, которые не содержат сами себя в качестве своего элемента: к R будет принадлежать множество котов, столов и все совокупности предметов, не содержащие сами себя. И все будет в порядке, пока мы не пересекаем границу, отделяющую R от остальных множеств.



Различие между множеством всех котов, которое не является котом (рис. 1), и множеством всего, что только можно себе представить, которое также можно себе представить (рис. 2).

(Источник: Умберто Эко, Vertige de la liste, Париж, издательство Flammarion, 2009, стр. 396).


Парадокс возникает, когда мы задаемся вопросом, по какую сторону этой воображаемой границы находится само R: любой ответ на этот вопрос приведет к противоречию. Предположим, что множество принадлежит само себе. Тогда обладает свойством, которое мы хотели устранить, следовательно, оно не может принадлежать к множеству всех множеств, которые не принадлежат самим себе. Но что это за множество? Это вновь множество R! Следовательно, если R принадлежит само себе, то не принадлежит само себе. Пока что все в порядке: может случиться, что R не принадлежит само себе и, исходя из этой гипотезы, мы не придем к противоречию. Посмотрим, что произойдет, если мы будем считать, что R не принадлежит само себе. В этом случае R будет обладать свойством, которое определяет множество всех множеств, не принадлежащих самим себе, следовательно, R будет принадлежать этому множеству. Иными словами, если R не принадлежит само себе, то R принадлежит само себе. Оба этих вывода нарушают основной принцип, восходящий к трудам философа Парменида, который в своей дидактической поэме «О природе» показал, что нет промежуточных путей между бытием и небытием.

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

Чтобы объяснить свой парадокс простыми словами, Рассел описал город, где по закону брадобрей должен брить только тех, кто не бреет себя сам. Мы заменили свойство «принадлежать самому себе» на «бриться самому», и теперь в роли множества R будет выступать брадобрей. В этой версии парадокса возникает вопрос: кто бреет брадобрея? Если он бреет себя сам, то принадлежит к числу тех, кого по закону ему брить нельзя. Если же он не бреет себя сам, то по закону он должен брить себя сам. Что бы они ни делал, он окажется в тюрьме, где, возможно, некий логик попытается убедить его, что провести несколько лет в тюрьме всегда лучше, чем столкнуться с противоречием, которое ставит под сомнение правильность всей математики двух тысячелетий.

В другой версии парадокса брадобрей заменен на библиотекаря, которому нужно навести порядок в библиотеке — такой большой, что для нее требуется каталог, содержащий все каталоги. Кто-то предложил, что было бы неплохо отделить каталоги, которые содержат ссылки на самих себя, от каталогов, которые не содержат таких ссылок. Это предложение понравилось библиотекарю, и он принялся за работу.

В течение многих лет он работал днями и ночами, и вот, когда он осмотрел одну за другой все полки, ему осталось решить, куда следует поместить объемистый каталог, в составление которого он вложил столько сил. Если этот каталог содержит ссылку на самого себя, его нельзя включить в каталог всех каталогов, которые не содержат ссылку на себя. Если, напротив, этот каталог не содержит ссылки на себя самого, его нужно включить в каталог всех каталогов, которые не содержат ссылку на себя. Если он принадлежит к такому каталогу, то не принадлежит ему, и наоборот. Лишь в этот момент библиотекарь понял, что все его труды оказались напрасными: предложенный критерий не позволит составить полную классификацию.

Столкнувшись с этим парадоксом, Рассел написал письмо Фреге, который в то время вносил правки в доказательства второго тома своего главного труда — «Основные законы арифметики». В него Фреге включил аксиому, благодаря которой стало возможным сформировать множество всех объектов, обладающих свойством Р, однако Рассел открыл, что если эту аксиому применить к самому свойству Р = «принадлежать самому себе», то это приведет к противоречию: множество R всех множеств, которые не принадлежат сами себе, нарушает закон исключенного третьего. Обескураженный этим открытием, Фреге, с присущей ему скрупулезностью, добавил к книге предисловие, в котором признался: «С автором не может произойти ничего более печального, чем, закончив свой труд, увидеть, как рушится одна из основ выстроенного им здания». Затем он предложил видоизменить эту аксиому, однако ее новый вариант не согласовывался с остальной системой аксиом, поэтому решения парадокса Рассела пришлось ждать несколько лет.

В период с 1906 по 1908 год Рассел нашел простое решение парадокса, на основе которого сформулировал теорию типов. До этого он занимался решением онтологической задачи, предметом которой были описания вида «наибольшее натуральное число» или «нынешний король Франции», которые, будучи грамматически корректными, не описывают никакой конкретный объект. В случае с «множеством всех множеств, которые не содержат себя в качестве своего элемента» дело обстоит еще хуже: это множество не просто не существует, но даже его описание не является корректным. Оно равносильно высказыванию «Франция в период правления нынешнего короля» или «наибольшее натуральное число».

* * *

РАССЕЛ О ФРЕГЕ

В письме к историку математической логики Жану ван Хейенорту от 23 ноября 1962 года Рассел так отзывался о Фреге:

«Когда я думаю о благородстве и честности, то понимаю, что не знаком ни с кем, кто мог бы сравниться с Фреге в стремлении к поиску истины. Фреге заканчивал труд всей своей жизни, большая часть его трудов была проигнорирована, а предпочтение было отдано людям бесконечно менее компетентным, чем он. Второй том уже был готов к публикации, и когда Фреге понял, что его фундаментальная гипотеза была ошибочной, он отреагировал на это с интеллектуальным удовольствием, подавив всякое разочарование. Это было чем-то почти сверхчеловеческим и являло собой признак того, на что способны люди, которые посвятили себя творчеству и знанию, а не отчаянной погоне за властью и славой».

* * *

В простейшем варианте теории Рассела каждому математическому объекту можно присвоить число в зависимости от его сложности: элементы имеют тип 0, множества элементов — тип 1, множества множеств элементов — тип 2 и т. д. Например, если рассмотреть натуральные числа, то число 8 будет иметь тип 0, множество Р всех четных чисел и множество I всех нечетных чисел — тип 1, а множество {Р, I} будет иметь уже тип 2, так как его элементы будут иметь тип 1. После того как всем объектам присвоены типы, устанавливается нерушимое правило: для объекта типа n можно задать отношение принадлежности только к объекту типа n + 1. Выражение «число 8 четное» является корректным, так как 8 имеет тип О, Р — тип 1. Тем не менее нет смысла задаваться вопросом, является ли само множество Р четных чисел четным числом или нет, так как в этом случае речь идет об отношении принадлежности, связывающем объекты одного типа. Именно о таком отношении шла речь в описании множества всех множеств, которые не принадлежат самим себе. На языке логики говорить «принадлежать самому себе» с концептуальной точки зрения некорректно, и здесь парадокс исчезает: для данного свойства Р можно рассмотреть множество объектов, которые обладают этим свойством, однако для этого Р как минимум должно быть корректно определено.



Эрнст Цермело, создатель первой аксиоматики теории множеств.


Одновременно с публикацией в журнале American Journal of Mathematics статьи Рассела «Математическая логика, основанная на теории типов» Эрнст Цермело (1871–1953) предложил новое решение этого парадокса, менее концептуальное, чем выдвинутое Расселом, но намного более практичное с точки зрения «рабочих от математики». Сегодня нам известно, что одна из величайших трудностей при создании любой теории — это определить предмет ее изучения. Повсюду говорят о теории информации, но что такое информация? Некоторые определяют биологию как науку о жизни, но что такое жизнь? Этими же вопросами задался Цермело при рассмотрении теории множеств. Согласно интуитивному определению Кантора, множества были не более чем совокупностями объектов, обладающих определенным свойством, однако такое определение допускало создание множества всех множеств, которые не принадлежат сами себе. Без четкого определения множества нельзя было двигаться дальше. Цермело заменил примитивное определение множества списком аксиом, в число которых включил аксиому, не позволявшую определить множество из парадокса Рассела. Начиная с этого момента множества стали определяться как объекты, удовлетворяющие списку аксиом.


Парадокс лжеца

Мы начали эту главу с анализа парадокса Рассела, однако пусть читатель не думает, что логические парадоксы являются исключительно творениями современности. Само слово «парадокс» — «неожиданный, странный» — имеет греческие корни.

В широком смысле парадокс — это абсурдное заключение, к которому ведут рассуждения, кажущиеся правильными и начинающиеся с корректных гипотез. Когда Рассел стал рассматривать множество всех множеств, которые не принадлежат сами себе, он опирался на литературную и философскую традицию. Вплоть до конца XIX века казалось невозможным, что парадоксы пересекут границу естественных наук и вторгнутся в царство чистого разума. Философы прибегали к парадоксам, чтобы подчеркнуть, что чувства обманчивы, а поэты использовали парадоксы как единственный способ донести до читателя истину о любви. Математики же страшились парадоксов, словно ящика Пандоры, открыв крышку которого, можно разрушить все в один миг. Поэтому открытие противоречий в теории множеств в то самое время, когда ученые постепенно начали признавать труд Кантора универсальной основой математики, вызвало кризис, пошатнувший самые основы науки. И на преодоление этого кризиса потребовалось несколько лет.

Один из древнейших парадоксов — это парадокс об Ахиллесе и черепахе, с помощью которого философ-досократик Зенон Элейский, ученик Парменида, хотел доказать, что движения не существует, и нанести удар по защитникам атомистической концепции пространства и времени. Зенон объяснял: фора, которую Ахиллес дает черепахе, чтобы забег проходил в равных условиях, непреодолима — когда атлет добежит до того места, где черепаха находилась вначале, она проползет чуть дальше. Когда Ахиллес преодолеет расстояние, пройденное черепахой, он вновь не сможет поравняться с ней — она успеет проползти немного вперед. Ахиллеса всегда будет отделять от черепахи некоторое расстояние, сколь бы малым оно ни было.

В другой формулировке этого парадокса утверждается, что стрела никогда не достигнет цели, так как когда она пролетит половину требуемого расстояния, ей нужно будет преодолеть вторую половину, когда она пролетит половину этой половины — останется четвертая часть, затем восьмая и так далее до бесконечности. Однако в реальной жизни Ахиллес всегда обгоняет черепаху, а стрела долетает до цели.

Возможно, наиболее интересными среди классических парадоксов являются антиномии — утверждения, истинные и ложные одновременно. Среди них выделяется парадокс лжеца, обычно приписываемый Эпимениду Критскому, хотя возможно, что этот философ, о котором говорили, будто он проспал 57 лет в пещере, зачарованной Зевсом, не осознавал, что формулирует парадокс. В одном из стихов Эпименид говорит о «критянах, вечно лживых», которые не верили в бессмертие Зевса. Однако сам Эпименид также был критянином, поэтому его утверждение относилось к нему самому и было равносильно высказыванию «Я всегда лгу».

Допустим, что Эпименид лжет, тогда его высказывание не может быть верным, следовательно, он говорит правду. Если же, напротив, Эпименид говорит правду, то его высказывание должно быть истинным, следовательно, он лжет. По легенде, поэт Филит Косский умер от изнеможения, пытаясь разрешить этот парадокс.

В действительности фраза «я всегда лгу» не парадокс в строгом смысле этого слова, так как ее отрицанием является не высказывание «я всегда говорю правду», как мы предположили выше, а высказывание «я лгу не всегда» или «иногда я говорю правду». Тем не менее, вложив в уста Эпименида слова «эта фраза ложна», мы получим настоящий парадокс. В самом деле, предположим, что эта фраза истинна — в этом случае она должна выполняться, то есть быть ложной. Но если эта фраза ложна, то она должна быть истинной, так как она относится к себе самой. Если она истинна, то она ложна, если она ложна, то истинна. Это нарушает закон исключенного третьего, согласно которому любая фраза является истинной или ложной, и принцип непротиворечивости, который гласит, что обе эти ситуации не могут происходить одновременно.

* * *

ОСТРОВ РЫЦАРЕЙ И ОРУЖЕНОСЦЕВ

Некий логик попал на остров, все жители которого делились на две группы: рыцари всегда говорили правду, а оруженосцы всегда лгали. Повстречав троих жителей А, В и С, логик спросил А, к рыцарям или оруженосцам он принадлежит, но получил столь путаный ответ, что был вынужден обратиться к в и спросить его: «Что сказал А?». В ответил: «А сказал, что он оруженосец». Однако в этот самый момент в разговор вмешался С, который предупредил логика: «Не верь В, он лжет!»

На основе этих двух утверждений логик может определить, кем же являются B и С. В самом деле, согласно В, житель А сказал «Я оруженосец», что можно считать одной из версий парадокса лжеца: «Я всегда лгу». Следовательно, существует единственный непротиворечивый выход из этой ситуации: когда В говорил об А, он солгал, следовательно, В — оруженосец. Таким образом, когда С предупреждал логика, он говорил правду, из чего следует, что С — рыцарь. Чтобы узнать, кем на самом деле является А, нам потребуется задать дополнительные вопросы.

* * *

В разные эпохи парадокс лжеца трактовался по-разному. Сервантес, например, упоминает его в главе LI второй части «Дон Кихота» — «О том, как Санчо Панса губернаторствовал далее, а равно и о других поистине славных происшествиях» в качестве примера того, сколь трудные решения приходилось принимать Санчо Пансе на острове Баратария. До этого, в главе XVIII, дон Кихот объясняет, что к наукам, которые должен знать странствующий рыцарь, принадлежит математика, «ибо необходимость в математике может возникнуть в любую минуту». Именно это про

исходит с Санчо Пансой, когда ему сообщают о деле хозяина поместья, разделенного рекой, который обязывал всякого, кто хотел переправиться через нее, сначала сообщить, куда он направляется. Если путник говорил правду, ему разрешалось переправиться через реку, но если он лгал, его ждала казнь. После вступления закона в силу судьи беспрепятственно пропускали почти всех, пока в один прекрасный день перед ними не предстал человек, который заявил, что направляется на виселицу, чтобы быть повешенным. Посовещавшись, судьи вынесли вердикт: «Если позволить этому человеку беспрепятственно следовать дальше, то это будет значить, что он нарушил клятву и согласно закону повинен смерти; если же мы его повесим, то ведь он клялся, что пришел только затем, чтобы его вздернули на эту виселицу, следственно, клятва его, выходит, не ложна, и на основании того же самого закона надлежит пропустить его».



В шедевре Мигеля Сервантеса Дон Кихот предлагает разрешить парадокс своему оруженосцу.


В контексте нашего обсуждения этот пример не слишком полезен, так как, увидев, что причин повесить путника столько же, сколько и отпустить его на свободу, Санчо Панса посоветовал отпустить его, поскольку «делать добро всегда правильнее, нежели зло». Здесь интересным будет добавить, что два самых известных парадокса в истории — парадокс Ахиллеса и черепахи и парадокс лжеца — в действительности очень отличаются. С одной стороны, рассуждения Зенона, доказывающие невозможность победы Ахиллеса над черепахой, основаны на ошибочном представлении о бесконечности. Предположив, что изначально фора черепахи равняется одному метру, Зенон указывал, что Ахиллес должен преодолеть расстояние

(1/2) + (1/4) + (1/8) + (1/16) + (1/32) и т. д.

чтобы догнать черепаху. При этом сначала ему нужно преодолеть его половину (1/2), затем — половину половины, то есть одну четверть (1/4), затем — половину половины половины, то есть одну восьмую (1/8) и т. д. Так как число слагаемых бесконечно велико, то расстояние, которое должен преодолеть Ахиллес, обязательно равняется бесконечности, таким образом Ахиллесу не хватит всей жизни, чтобы преодолеть его и догнать черепаху. Ошибка Зенона состояла в том, что сумма бесконечного числового ряда необязательно равна бесконечности, при условии что члены ряда убывают с достаточной быстротой. Николай Орезмский (1323–1382) привел красивое геометрическое решение этого парадокса, в котором показал, что сумма ряда Зенона равна не бесконечности, а в точности единице — именно такую фору Ахиллес дал черепахе. Следовательно, парадокс Зенона есть не более чем ошибочное представление о бесконечных рядах.



Схема, с помощью которой Николай Орезмский в XIV веке показал, что сумма ряда из парадокса об Ахиллесе и черепахе не равна бесконечности.


С парадоксом лжеца дело обстоит иначе. «Эта фраза ложна» — об этом высказывании нельзя сказать, истинно оно или ложно, так как любой ответ неизменно ведет к противоположному. Как заметил греческий логик Хрисипп из Сол, те, кто сформулировал парадокс лжеца, «совершенно отклонились от изначального значения слов — они произвели лишь звуки, ничего не выразив». Первой естественной реакцией будет объяснить противоречие тем, что высказывание ссылается на само себя, однако этого недостаточно — высказывания «эта фраза истинна» или «эта фраза относится к книге «Сон разума. Математическая логика и ее парадоксы» также ссылаются сами на себя, однако не вызывают никаких затруднений.

Другим, несколько хитроумным решением, будет поставить вопрос: не принадлежит ли понятие истинности, подобно понятию множества, к числу тех, которые просто использовать, но трудно определить. Этой точки зрения придерживался Альфред Тарский (1902–1983), который в 1933 году опубликовал статью объемом свыше двухсот страниц на польском языке, где впервые формально определил истину. Несмотря на значительный объем статьи, Тарский не предложил придать понятию «истинность» новое значение, а вместо этого всего лишь описал на языке математики аристотелево определение истины как соответствие между тем, что говорится о реальности, и самой реальностью. Подобно тому как высказывание «снег белый» истинно тогда и только тогда, когда снег в самом деле белый, высказывание Р является истинным в некоторой теории тогда и только тогда, когда при интерпретации Р в рамках структуры, которую описывает эта теория, Р является истинным. В какой структуре следует интерпретировать фразу вида «эта фраза ложна»?

Как вы увидите в главе 4, ответить на этот вопрос удалось лишь Курту Геделю.

В конечном итоге парадокс Рассела, парадокс Ахиллеса и черепахи и парадокс лжеца были решены, однако попутно родилось множество других вопросов.

В 1905 году преподаватель института Дижона Жюль Ришар открыл парадокс, связанный с диагональным методом Кантора. Годом позже юный библиотекарь Бодлианской библиотеки Оксфордского университета (необязательно тот, который проводил дни и ночи, составляя каталог всех каталогов, не содержащих ссылки на самих себя) упростил парадокс Ришара, представив, что произойдет, если для описания любого натурального числа можно использовать только пятнадцать слов. Так как число выражений, состоящих из пятнадцати слов, является конечным, то с их помощью мы можем описать лишь конечное множество чисел. Среди всех чисел, которые мы не сможем описать пятнадцатью словами, одно будет наименьшим. Обозначим его через n. Однако в этом случае n будет «наименьшим числом, которое нельзя описать менее чем пятнадцатью словами» — это описание содержит всего девять слов!

Как мы можем быть уверены, что парадоксы не будут и дальше распространяться, подобно вирусам? Источниками противоречий служили бесконечность, самоотносимость и не вполне точно определенные понятия. Однако не все высказывания, которые ссылаются сами на себя, порождают парадоксы, полностью исключить бесконечность из математики нельзя, и у нас нет инструмента, который безошибочно укажет на недостаточно четко определенные понятия. В следующей главе мы расскажем о стратегии, с помощью которой наиболее выдающийся математик своего поколения, Давид Гильберт, хотел полностью избавиться от парадоксов.

Категория: МАТЕМАТИЧЕСКАЯ ЛОГИКА И ЕЕ ПАРАДОКСЫ | Добавил: admin | Теги: Мир Математики, все о математике, занимательная математика, популярная математика, дидактический материал по математик, сайт по математике
Просмотров: 906 | Загрузок: 0 | Рейтинг: 0.0/0
УЧИТЕЛЮ ИНФОРМАТИКИ
КОНСПЕКТЫ УРОКОВ
ВНЕКЛАССНЫЕ МЕРОПРИЯТИЯ ПО ИНФОРМАТИКЕ
ПОСОБИЯ И МЕТОДИЧКИ ДЛЯ УЧИТЕЛЯ ИНФОРМАТИКИ
ИЗ ОПЫТА РАБОТЫ УЧИТЕЛЯ ИНФОРМАТИКИ
ЗАДАНИЯ ШКОЛЬНОЙ ОЛИМПИАДЫ ПО ИНФОРМАТИКЕ


ИНФОРМАТИКА В ШКОЛЕ
ИНФОРМАТИКА В НАЧАЛЬНЫХ КЛАССАХ
ИНФОРМАТИКА В 3 КЛАССЕ
ИНФОРМАТИКА В 4 КЛАССЕ
КОНТРОЛЬНЫЕ РАБОТЫ ПО ИНФОРМАТИКЕ. 3 КЛАСС
КОНТРОЛЬНЫЕ РАБОТЫ ПО ИНФОРМАТИКЕ. 4 КЛАСС
ПРОГРАММИРОВАНИЕ ДЛЯ ДЕТЕЙ
СКАЗКА "ПРИКЛЮЧЕНИЯ ЭЛЕКТРОШИ"
ИГРОВЫЕ ТЕХНОЛОГИИ НА УРОКАХ ИНФОРМАТИКИ
ВИКТОРИНЫ ПО ИНФОРМАТИКЕ
КОМПЬЮТЕРНЫЕ ЧАСТУШКИ
ОБРАТНАЯ СВЯЗЬ
Поиск

Copyright MyCorp © 2018
Яндекс.Метрика Рейтинг@Mail.ru