Логические парадоксы и человеческое сознание (продолжение)
Продолжение предыдущего поста.
Математик Стивен Клини назвал тип определений, проиллюстрированный картинкой в предыдущем посте, непредикативными. Бертран Рассел, понимая, что непредикативные определения легко приводят к парадоксам, сформулировал принцип порочного круга и предложил от таких определений отказаться. Однако, оказалось, что математика, достигшая к концу XIX века впечатляющей мощи, вовсю использует непредикативные определения. Порушить классический математический анализ ради идеала высокой строгости математики оказались не готовы. И под знамена Рассела в большинстве своем не пошли.
Ну хорошо. Я еще готов понять позицию, когда не хочется трогать уже созданные и прекрасно работающие на благо человека дифференциальное и интегральное исчисления. Но если уж математики взялись подводить фундамент, в виде математической логики и теории множеств, под математику в целом, то, по моему разумению, хотя бы в базовых построениях этих основополагающих разделов математики стоило избегать непредикативных определений и связанных с ними автореференций. Нет, не устояли!
Приведу примеры.
Если у нас есть множество М, обозначим через Р(М) множество всех его подмножеств. Георг Кантор доказал, что для любого множества М множество Р(М) более «мощное», чем М. Говоря более строго, нельзя установить взаимно-однозначное соответствие между элементами М и Р(М) , последних принципиально больше.
Это теорема Кантора - один из краеугольных камней теории множеств и математики в целом. Ее значение исключительно велико.
Но давайте посмотрим на метод доказательства этой теоремы. Его суть в следующем: допустим, что требуемое взаимно-однозначное соответствие существует: f: M -> P(M) . Далее в M строится некое специальное подмножество Y (подробности опускаю), а поскольку соответствие f взаимно-однозначное, то в М должен найтись элемент m0, соответствующий множеству Y: f(m0)=Y. Далее показывается, что возникает парадокс: если допустить, что m0 принадлежит Y, то получается, что он не принадлежит Y, а если допустить, что m0 не принадлежит Y, то получается, что он принадлежит Y. Полученное противоречие, говорит нам учебник, доказывает, что исходное предположение о существовании взаимно-однозначного соответствия неверно, что и доказывает теорему.
Я изложил только схему доказательства, его детали для моего изложения не нужны.
Ведь ясно, что происходит: в процессе доказательства задается некое множество Y, с его помощью определяется элемент m0, который потом соотносится с Y - это же в чистом виде непредикативное определение! И в итоге получается парадокс - какой сюрприз! Так может, парадокс возник не потому, что предположение о существовании взаимно-однозначного соответствия было неверно, а просто потому, что в ходе доказательства был использован прием, который приводит к парадоксам? Прием, который Рассел предлагал запретить как некорректный?
Следующий пример, тоже теорема, доказанная Кантором.
Он доказал, что множество всех бесконечных последовательностей, составленных из нулей и единиц (то есть последовательностей вида 1 1 0 0 0 1 0 1 0 1 1 1 0 …), мощнее множества натуральных чисел, или, проще говоря, их нельзя занумеровать (нельзя построить взаимно-однозначное соответствие между натуральными числами и такими последовательностями).
Это, опять же, фундаментальнейший результат математики. Из него, в частности, следует, что действительных чисел больше, чем натуральных, и много еще чего. Метод, использованный при доказательстве («диагональ Кантора»), впоследствии применялся при доказательстве многих теорем.
Суть доказательства такова:
Допустим, что все такие последовательности можно каким-то образом занумеровать:
Построим новую последовательность (методом диагонали Кантора): первый элемент этой последовательности должен отличаться от первого элемента первой последовательности в нашей нумерации, второй элемент - от второго элемента второй последовательности, третий элемент - от третьего элемента третьей последовательности и т. д. То есть в нашем примере новая последовательность будет выглядеть так:
0 0 1 1 0 1 1 … и так далее
Эта новая последовательность тоже должна иметь какой-то номер (мы же все последовательности занумеровали), допустим, k. Тогда по самому способу построения, эта последовательность должна отличаться от последовательности номер k в k-том элементе, то есть она должна отличаться от самой себя в k-том элементе.
Полученное противоречие, говорит Кантор, доказывает, что исходное предположение о возможности пронумеровать такие последовательности неверно. Значит, таких нумераций не существует, и множество этих последовательностей несчетно.
Проанализируем доказательство: мы вначале берем исходное множество всех двоичных (0 - 1) бесконечных последовательностей, затем при помощи этого множества строим новый элемент (диагональ Кантора), и далее пытаемся соотнести этот новый элемент с исходным множеством. Опять непредикативное определение!
То есть, и это доказательство тоже смахивает на жульничество. Кантор использует сомнительный прием.
Сомнительность метода диагонали Кантора хорошо иллюстрирует парадокс Ришара (1905). Неформально изложу его суть.
Мы будем рассматривать функции на множестве натуральных чисел, такие что их можно определить при помощи какого-либо выражения русского языка. Например: функция, которая каждому числу ставит в соответствие его удвоение (то есть, 1->2, 2->4, 3->6, 4->8, и т.д.). Все такие выражения можно «пересчитать», точнее говоря, поскольку их бесконечно много, можно задать их пересчет. Скажем, сначала пересчитаем все такие определения функций, в которых не более 50 букв, пробелов и знаков препинания - их конечное число. Потом пересчитаем определения функций, содержащие ровно 51 символ, потом - содержащие ровно 52 символа и т.д. Таким образом, мы описали процедуру, которая каждому выражению - определению функции позволяет присвоить некоторый номер. Занумеруем эти функции: f1, f2, f3 … Определим новую функцию g следующим образом: для каждого числа k значение новой функции отличается на единицу от значения функции с номером : g(k)=fk(k)+1.
Эту новую функцию также можно определить при помощи фразы русского языка (см. точное изложение парадокса в книге С.Клини «Введение в метаматематику», §11, там эта фраза приведена). Тогда эта функция должна иметь какой-то номер n, то есть g - это fn. Но по определению функции g получается, что она должна отличаться сама от себя на единицу при аргументе n: fn(n)=g(n)=fn(n)+1.
Мы видим, что приведенное рассуждение - это по сути диагональ Кантора. То есть, Ришар продемонстрировал, что использование диагонали Кантора приводит к парадоксам. Тем не менее, в современной математике диагональ Кантора считается корректным методом доказательства.
Проиллюстрирую эту ситуацию с помощью аналогии.
Допустим, у меня есть весы, на них написано, что взвешивать можно грузы не тяжелее 10 килограмм. Продавец в магазине не поленился мне продемонстрировать на образце с витрины, что если на весы бухнуть груз в 30 килограмм, то что-то там внутри с хрустом ломается, и весы выходят из строя.
Я принес весы домой и поставил на них тяжелый предмет. Стрелка весов немного зашкалила. Я прислушиваюсь: вроде ничего не хрустнуло. Ну, стрелка зашкалила, похоже, что предмет весит 12 килограмм.
Правильный ли мой вывод? Да с чего бы?. Может, там стоит ограничитель, который не сломался, но просто не дает стрелке отклоняться дальше, а предмет весит на самом деле 15 килограмм. А может, еще что-то - эти весы не предназначены для взвешивания тяжелых предметов, никто не даст гарантий, что в этом случае они покажут правильный вес, а то и не сломаются вообще.
То есть получается, что математики позволяют себе использовать сомнительные приемы, а результат оценивают на глазок: ну, вроде, все логично, вроде парадоксов не получилось - вот и ладненько.
Ну раз так, то я приведу одно логически безупречное доказательство.
Все слышали про Великую теорему Ферма? Пьер Ферма сформулировал ее в 1637 году, формулировка выглядела очень просто. Доказать ее смогли 350 лет спустя, с применением весьма продвинутых методов современной математики. Несколько лет потратили на устранение обнаруженных ошибок в доказательстве, в итоге оно представляет из себя 130-страничный текст.
Чудаки. Столетия потратили, тонны бумаги извели… Читаем внутри рамки:
Если первое утверждение истинно, значит, оба утверждения должны быть ложны, в том числе и первое. Противоречие. Значит, первое утверждение ложно. А раз так, то в противовес этому ложному утверждению, хотя бы одно из утверждений в рамке должно быть истинно. Но первое утверждение, как мы показали - ложно. Значит, истинно второе утверждение.
Великая теорема Ферма доказана.
МОРАЛЬ: автореференции совсем не обязаны приводить к парадоксам. Зато они дают замечательный способ доказывать все, что угодно.
Переходим к финалу-апофеозу математической части моей статьи.
В 1931 году выдающийся немецкий математик Курт Гедель опубликовал «теорему о неполноте». Эта теорема подействовала на математический мир как удар обухом по голове. Если выражаться не совсем строго, Гедель доказал следующее:
Если математическая теория непротиворечива, то ее непротиворечивость доказать нельзя.
(Сразу оговорюсь, что речь тут идет только о минимально сложных теориях, таких, что они содержат в себе натуральные числа и возможность производить с ними арифметические действия. Математика как раз и является примером такой теории.)
Из теоремы Геделя получается, что в непротиворечивость математики можно только верить. Ну, с оговоркой типа «весь человеческий опыт подтверждает, что» и т. д. Потому что, если математика и в самом деле непротиворечива, то доказать это - увы…
Эта знаменитая (так называемая «вторая») теорема Геделя является следствием его «первой теоремы» или теоремы о неполноте:
Если математическая теория непротиворечива, то в ней можно построить математическое утверждение, такое, что невозможно доказать ни его самого, ни его отрицания.
Как же доказывает Гедель эту теорему? Сначала он определяет способ нумерации всех формул и утверждений математической теории. Каждая формула получает свой уникальный номер, который называется геделевым. Далее Гедель строит некую формулу W, содержащую переменную x, затем он вместо x подставляет геделев номер формулы W. В результате такой подстановки он получает математическое утверждение, которое нельзя доказать в рамках данной математической теории.
Что же мы видим? Поскольку геделев номер формулы по сути означает эту самую формулу (для каждой формулы ее геделев номер уникален), то, подставляя внутрь формулы ее саму, мы получаем автореференцию. Причем, с содержательной точки зрения, формула W составлена Геделем так, что после указанной подстановки она превращается в утверждение, отрицающее само себя (вспоминаем парадокс лжеца). Если говорить более конкретно, то формула «содержательно выражает свою собственную невыводимость» (цитата из §5 главы 3 учебника Э. Мендельсона «Введение в математическую логику») И далее Гедель показывает, что если теория непротиворечива, то с ее помощью нельзя вывести утверждение, отрицающее свою собственную выводимость. Да ну? Вот это да!
Итак, Первая теорема Геделя утверждает, что если математическая теория непротиворечива, то в ней нельзя вывести, грубо говоря, парадокс лжеца (повторюсь, формула W говорит «Меня вывести нельзя!»). Иными словами, из непротиворечивости теории вытекает невозможность вывода формулы, отрицающей собственную выводимость. Но наша формула именно это и утверждает («Меня вывести нельзя!»). Получается, что, исходя из непротиворечивости теории, мы вывели эту формулу. А по Первой теореме Геделя ее вывести невозможно. Получается, что если бы могли доказать непротиворечивость математической теории, то на основе этого доказанного факта мы смогли бы доказать как формулу W, так и ее недоказуемость!
Вот это вот повторяющееся прокручивание парадокса лжеца, которое мы наблюдали в предыдущем абзаце, есть не что иное как содержательная интерпретация доказательства Второй теоремы Геделя (само доказательство очень формально, длинно и мозгодробительно).
То есть, даже теорема, утверждающая невозможность доказать непротиворечивость математики, доказывается с помощью сомнительного трюка.
Окончание следует.
Математик Стивен Клини назвал тип определений, проиллюстрированный картинкой в предыдущем посте, непредикативными. Бертран Рассел, понимая, что непредикативные определения легко приводят к парадоксам, сформулировал принцип порочного круга и предложил от таких определений отказаться. Однако, оказалось, что математика, достигшая к концу XIX века впечатляющей мощи, вовсю использует непредикативные определения. Порушить классический математический анализ ради идеала высокой строгости математики оказались не готовы. И под знамена Рассела в большинстве своем не пошли.
Ну хорошо. Я еще готов понять позицию, когда не хочется трогать уже созданные и прекрасно работающие на благо человека дифференциальное и интегральное исчисления. Но если уж математики взялись подводить фундамент, в виде математической логики и теории множеств, под математику в целом, то, по моему разумению, хотя бы в базовых построениях этих основополагающих разделов математики стоило избегать непредикативных определений и связанных с ними автореференций. Нет, не устояли!
Приведу примеры.
Если у нас есть множество М, обозначим через Р(М) множество всех его подмножеств. Георг Кантор доказал, что для любого множества М множество Р(М) более «мощное», чем М. Говоря более строго, нельзя установить взаимно-однозначное соответствие между элементами М и Р(М) , последних принципиально больше.
Это теорема Кантора - один из краеугольных камней теории множеств и математики в целом. Ее значение исключительно велико.
Но давайте посмотрим на метод доказательства этой теоремы. Его суть в следующем: допустим, что требуемое взаимно-однозначное соответствие существует: f: M -> P(M) . Далее в M строится некое специальное подмножество Y (подробности опускаю), а поскольку соответствие f взаимно-однозначное, то в М должен найтись элемент m0, соответствующий множеству Y: f(m0)=Y. Далее показывается, что возникает парадокс: если допустить, что m0 принадлежит Y, то получается, что он не принадлежит Y, а если допустить, что m0 не принадлежит Y, то получается, что он принадлежит Y. Полученное противоречие, говорит нам учебник, доказывает, что исходное предположение о существовании взаимно-однозначного соответствия неверно, что и доказывает теорему.
Я изложил только схему доказательства, его детали для моего изложения не нужны.
Ведь ясно, что происходит: в процессе доказательства задается некое множество Y, с его помощью определяется элемент m0, который потом соотносится с Y - это же в чистом виде непредикативное определение! И в итоге получается парадокс - какой сюрприз! Так может, парадокс возник не потому, что предположение о существовании взаимно-однозначного соответствия было неверно, а просто потому, что в ходе доказательства был использован прием, который приводит к парадоксам? Прием, который Рассел предлагал запретить как некорректный?
Следующий пример, тоже теорема, доказанная Кантором.
Он доказал, что множество всех бесконечных последовательностей, составленных из нулей и единиц (то есть последовательностей вида 1 1 0 0 0 1 0 1 0 1 1 1 0 …), мощнее множества натуральных чисел, или, проще говоря, их нельзя занумеровать (нельзя построить взаимно-однозначное соответствие между натуральными числами и такими последовательностями).
Это, опять же, фундаментальнейший результат математики. Из него, в частности, следует, что действительных чисел больше, чем натуральных, и много еще чего. Метод, использованный при доказательстве («диагональ Кантора»), впоследствии применялся при доказательстве многих теорем.
Суть доказательства такова:
Допустим, что все такие последовательности можно каким-то образом занумеровать:
Построим новую последовательность (методом диагонали Кантора): первый элемент этой последовательности должен отличаться от первого элемента первой последовательности в нашей нумерации, второй элемент - от второго элемента второй последовательности, третий элемент - от третьего элемента третьей последовательности и т. д. То есть в нашем примере новая последовательность будет выглядеть так:
0 0 1 1 0 1 1 … и так далее
Эта новая последовательность тоже должна иметь какой-то номер (мы же все последовательности занумеровали), допустим, k. Тогда по самому способу построения, эта последовательность должна отличаться от последовательности номер k в k-том элементе, то есть она должна отличаться от самой себя в k-том элементе.
Полученное противоречие, говорит Кантор, доказывает, что исходное предположение о возможности пронумеровать такие последовательности неверно. Значит, таких нумераций не существует, и множество этих последовательностей несчетно.
Проанализируем доказательство: мы вначале берем исходное множество всех двоичных (0 - 1) бесконечных последовательностей, затем при помощи этого множества строим новый элемент (диагональ Кантора), и далее пытаемся соотнести этот новый элемент с исходным множеством. Опять непредикативное определение!
То есть, и это доказательство тоже смахивает на жульничество. Кантор использует сомнительный прием.
Сомнительность метода диагонали Кантора хорошо иллюстрирует парадокс Ришара (1905). Неформально изложу его суть.
Мы будем рассматривать функции на множестве натуральных чисел, такие что их можно определить при помощи какого-либо выражения русского языка. Например: функция, которая каждому числу ставит в соответствие его удвоение (то есть, 1->2, 2->4, 3->6, 4->8, и т.д.). Все такие выражения можно «пересчитать», точнее говоря, поскольку их бесконечно много, можно задать их пересчет. Скажем, сначала пересчитаем все такие определения функций, в которых не более 50 букв, пробелов и знаков препинания - их конечное число. Потом пересчитаем определения функций, содержащие ровно 51 символ, потом - содержащие ровно 52 символа и т.д. Таким образом, мы описали процедуру, которая каждому выражению - определению функции позволяет присвоить некоторый номер. Занумеруем эти функции: f1, f2, f3 … Определим новую функцию g следующим образом: для каждого числа k значение новой функции отличается на единицу от значения функции с номером : g(k)=fk(k)+1.
Эту новую функцию также можно определить при помощи фразы русского языка (см. точное изложение парадокса в книге С.Клини «Введение в метаматематику», §11, там эта фраза приведена). Тогда эта функция должна иметь какой-то номер n, то есть g - это fn. Но по определению функции g получается, что она должна отличаться сама от себя на единицу при аргументе n: fn(n)=g(n)=fn(n)+1.
Мы видим, что приведенное рассуждение - это по сути диагональ Кантора. То есть, Ришар продемонстрировал, что использование диагонали Кантора приводит к парадоксам. Тем не менее, в современной математике диагональ Кантора считается корректным методом доказательства.
Проиллюстрирую эту ситуацию с помощью аналогии.
Допустим, у меня есть весы, на них написано, что взвешивать можно грузы не тяжелее 10 килограмм. Продавец в магазине не поленился мне продемонстрировать на образце с витрины, что если на весы бухнуть груз в 30 килограмм, то что-то там внутри с хрустом ломается, и весы выходят из строя.
Я принес весы домой и поставил на них тяжелый предмет. Стрелка весов немного зашкалила. Я прислушиваюсь: вроде ничего не хрустнуло. Ну, стрелка зашкалила, похоже, что предмет весит 12 килограмм.
Правильный ли мой вывод? Да с чего бы?. Может, там стоит ограничитель, который не сломался, но просто не дает стрелке отклоняться дальше, а предмет весит на самом деле 15 килограмм. А может, еще что-то - эти весы не предназначены для взвешивания тяжелых предметов, никто не даст гарантий, что в этом случае они покажут правильный вес, а то и не сломаются вообще.
То есть получается, что математики позволяют себе использовать сомнительные приемы, а результат оценивают на глазок: ну, вроде, все логично, вроде парадоксов не получилось - вот и ладненько.
Ну раз так, то я приведу одно логически безупречное доказательство.
Все слышали про Великую теорему Ферма? Пьер Ферма сформулировал ее в 1637 году, формулировка выглядела очень просто. Доказать ее смогли 350 лет спустя, с применением весьма продвинутых методов современной математики. Несколько лет потратили на устранение обнаруженных ошибок в доказательстве, в итоге оно представляет из себя 130-страничный текст.
Чудаки. Столетия потратили, тонны бумаги извели… Читаем внутри рамки:
Если первое утверждение истинно, значит, оба утверждения должны быть ложны, в том числе и первое. Противоречие. Значит, первое утверждение ложно. А раз так, то в противовес этому ложному утверждению, хотя бы одно из утверждений в рамке должно быть истинно. Но первое утверждение, как мы показали - ложно. Значит, истинно второе утверждение.
Великая теорема Ферма доказана.
МОРАЛЬ: автореференции совсем не обязаны приводить к парадоксам. Зато они дают замечательный способ доказывать все, что угодно.
Переходим к финалу-апофеозу математической части моей статьи.
В 1931 году выдающийся немецкий математик Курт Гедель опубликовал «теорему о неполноте». Эта теорема подействовала на математический мир как удар обухом по голове. Если выражаться не совсем строго, Гедель доказал следующее:
Если математическая теория непротиворечива, то ее непротиворечивость доказать нельзя.
(Сразу оговорюсь, что речь тут идет только о минимально сложных теориях, таких, что они содержат в себе натуральные числа и возможность производить с ними арифметические действия. Математика как раз и является примером такой теории.)
Из теоремы Геделя получается, что в непротиворечивость математики можно только верить. Ну, с оговоркой типа «весь человеческий опыт подтверждает, что» и т. д. Потому что, если математика и в самом деле непротиворечива, то доказать это - увы…
Эта знаменитая (так называемая «вторая») теорема Геделя является следствием его «первой теоремы» или теоремы о неполноте:
Если математическая теория непротиворечива, то в ней можно построить математическое утверждение, такое, что невозможно доказать ни его самого, ни его отрицания.
Как же доказывает Гедель эту теорему? Сначала он определяет способ нумерации всех формул и утверждений математической теории. Каждая формула получает свой уникальный номер, который называется геделевым. Далее Гедель строит некую формулу W, содержащую переменную x, затем он вместо x подставляет геделев номер формулы W. В результате такой подстановки он получает математическое утверждение, которое нельзя доказать в рамках данной математической теории.
Что же мы видим? Поскольку геделев номер формулы по сути означает эту самую формулу (для каждой формулы ее геделев номер уникален), то, подставляя внутрь формулы ее саму, мы получаем автореференцию. Причем, с содержательной точки зрения, формула W составлена Геделем так, что после указанной подстановки она превращается в утверждение, отрицающее само себя (вспоминаем парадокс лжеца). Если говорить более конкретно, то формула «содержательно выражает свою собственную невыводимость» (цитата из §5 главы 3 учебника Э. Мендельсона «Введение в математическую логику») И далее Гедель показывает, что если теория непротиворечива, то с ее помощью нельзя вывести утверждение, отрицающее свою собственную выводимость. Да ну? Вот это да!
Итак, Первая теорема Геделя утверждает, что если математическая теория непротиворечива, то в ней нельзя вывести, грубо говоря, парадокс лжеца (повторюсь, формула W говорит «Меня вывести нельзя!»). Иными словами, из непротиворечивости теории вытекает невозможность вывода формулы, отрицающей собственную выводимость. Но наша формула именно это и утверждает («Меня вывести нельзя!»). Получается, что, исходя из непротиворечивости теории, мы вывели эту формулу. А по Первой теореме Геделя ее вывести невозможно. Получается, что если бы могли доказать непротиворечивость математической теории, то на основе этого доказанного факта мы смогли бы доказать как формулу W, так и ее недоказуемость!
Вот это вот повторяющееся прокручивание парадокса лжеца, которое мы наблюдали в предыдущем абзаце, есть не что иное как содержательная интерпретация доказательства Второй теоремы Геделя (само доказательство очень формально, длинно и мозгодробительно).
То есть, даже теорема, утверждающая невозможность доказать непротиворечивость математики, доказывается с помощью сомнительного трюка.
Окончание следует.