Мифы об основаниях математики

Март 16, 2010 в 10:05 пп · Рубрика: Логика и математика ·Отмечено бесконечность, гёдель, заблуждения, кантор, логика, математика, математическая-логика, мифы, наука, парадокс, парадоксы, рассел

Из-за сложности вопроса и говнюков-популяризаторов вокруг оснований математики сложилось много мифов. Здесь я попробую рассмотреть три группы таких мифов: общего характера, о теории множеств и о теореме Гёделя о неполноте.

Но сначала некоторые термины, чтобы было понятно.

Термины для неспециалистов.

Теория – множество строк (они называются теоремами).

Арифметическая теория – теория, состоящая только из формул первого порядка с операциями +, *, предикатом =, константой 0. Пример формулы: (для любого x)(для любого y)(для любого z)(x*x*x+y*y*y=z*z*z -> (x=0 или y=0 или z=0)).

Истинная арифметическая формула – истинная в стандартной модели арифметики, т.е. в интерпретации, где предметное множество – {0,1,2,…,}, + действует как сложение, * – как умножение и т.д.

Корректная теория – в которой все теоремы истинны.

Перечислимая теория – для которой существует множество пар строк (A,B), такое, что:
1) A – теорема T <=> существует B, для которого (A,B) лежит в множестве;
2) существует алгоритм, который для каждой пары (A,B) проверяет, лежит ли она в множестве.
Здесь B можно назвать доказательством A, алгоритм из пункта 2 – проверяющий доказательства.

Для перечислимых теорий существует способ записи утверждения о их непротиворечивости в виде арифметической формулы. Он должен быть строго задан, можно его найти почти в любом учебнике по мат. логике (в каждом учебнике он свой, но суть от этого не меняется). Утверждение о непротиворечивости относится не к самой теории, а к алгоритму из пункта 2 (т.е. для одинаковых теорий с разными алгоритмами формулы могут получиться разными).

Функция выбора – функция, которая каждому непустому множеству из некоторого семейства ставит в соответствие его элемент.

Аксиома выбора – функция выбора существует для любого семейства множеств.

Термины для остальных.

C – строго недостижимый кардинал, если:
1) C несчётен;
2) A<C -> 2^A<C;
3) множество мощности C не представимо в виде меньшего C объединения множеств мощности < C.

Натуральная модель теории множеств – это такая интерпретация, в которой:
1) предметное множество состоит из корневых деревьев без бесконечных цепочек, обладающих следующим свойством: у каждой вершины все поддеревья, соответствующие её сыновьям, различны;
2) предметное множество является множеством всех таких деревьев мощности меньше C, где C – некоторый строго недостижимый кардинал;
3) (A принадлежит B)<=>(дерево A совпадает с деревом, соответствующим некоторому сыну корневой вершины дерева B).

Все натуральные модели являются моделями ZFC.

Высшие аксиомы бесконечности – утверждения о существовании больших кардиналов типа строго недостижимых (или ещё больше).

Все остальные термины – в яндекс.

ОБЩИЕ МИФЫ ОБ ОСНОВАНИЯХ МАТЕМАТИКИ

Миф номер 1. В математике все строго определяется и доказывается, за исключением некоторого набора базовых неопределяемых понятий и аксиом. Очень распространенный миф, что не мешает ему быть мифом. На самом деле, достаточно простым рассуждением можно показать, что нет универсального языка, на котором можно записать любое математическое утверждение.
Будем для простоты рассматривать функции, отображающие множество натуральных чисел в {0,1}. Пусть у нас есть некоторый универсальный язык для записи таких функций. На нём, очевидно, можно записать не все функции (функций континуум, а записей счётно), но пусть выполняется свойство: все функции, которые можно описать записать конечным текстом на естественном языке, можно записать и на этом языке. Пусть F(n)=(1-(значение функции, соответствующей тексту с номером n на аргументе n)). Эту функцию можно описать текстом на естественном языке (если наш язык мы смогли описать), тогда её можно описать и на нашем языке=>ей соответствует некоторый конечный текст=>номер m. Очевидно, что F(m) не равно значению функции с номером m на m=>противоречие. Нет языка, на котором можно выразить любую извращённую фантазию математика.

Кроме того, есть теорема Гёделя о неполноте, которая говорит, что множество всех истинных арифметических формул не является перечислимой теорией. Более того, есть теорема Гёделя о недоказуемости непротиворечивости, из которой вытекает, что какую бы мы не взяли (вменяемую) перечислимую теорию, в ней нельзя будет доказать ее непротиворечивость (простенькое утверждение о свойствах алгоритмов). Но, с другой стороны, если мы используем эту теорию, то мы верим в ее непротиворечивость, тем самым можем эту непротиворечивость добавить в качестве аксиомы, расширить теорию. Добавив эту аксиому, мы с ее помощью не сможем доказать непротиворечивость исходной системы с этой аксиомой, эту непротиворечивость тоже можно добавить в качестве аксиомы и т.д. У этого процесса нет конца, и всегда остается простор для творчества и фантазии. Короче говоря, математика – это творческое занятие.

Миф номер 2. Математика – это всего навсего формальный вывод теорем из некоторого набора аксиом, который выбирается произвольно. Главное, чтобы аксиоматика была непротиворечивой.. В корне неверное представление. На самом деле, аксиомы выбираются не абы как, а для того, чтобы описать свойства некоторого мира, о котором мы имеем представление. Само представление неформализуемо, но можно формализовать некоторые свойства, из которых можно выводить другие свойства. Проблема всегда остается как с выразимостью свойств, так и с доказуемостью. Заметим, что математики, вообще говоря, довольно редко записывают свои теоремы на формальных языках, и уж тем более редко выписывают формальные доказательства. Обычно они пользуются естественным языком, при этом стараясь изъясняться так, чтобы их правильно понимали. Одна из основных задач математика – это объяснить, для чего нужны его результаты и какое они отношение имеют к реальному миру. Это объяснение не может быть формальным. Естественный язык апеллирует к неформальным, интуитивным человеческим представлениям, которые являются либо обобщением (опять же неформальная операция) его опыта, либо развитием представлений, имеющихся с рождения. Тем самым естественный язык позволяет сокращать длину формулировок и (особенно) доказательств.

Миф номер 3. Существует и непротиворечиво – синонимы. Это не так. См. предыдущий миф.

Миф номер 4. ZFC (аксиоматика теории множеств Цермело-Френкеля) является формализацией возможностей человеческого мышления. Иными словами, всё, что может доказать человек, можно доказать в ZFC, и наоборот. Опять же, стоит повториться, что на языке теории множеств первого порядка, который использует ZFC, как и на любом другом языке, даже записать можно не все математические утверждения, на которые человеку может захотеться найти ответы (см. рассуждение из мифа 1). Более того, этот язык ещё и не имеет никакой естественной семантики (соответствия формула->истинность/ложность). Семантика языка, как известно, зависит от выбора интерпретации. Естественной интерпретацией в данном случае является натуральная модель теории множеств, но их, как известно, много. Из Теоремы Гёделя о недоказуемости непротиворечивости вытекает, что формальную непротиворечивость нельзя доказать в ZFC (хотя сформулировать можно). Но человеческое мышление до этой непротиворечивости как-то додумалось. Есть и более сильные средства, доступные человеческому мышлению, но выходящие за рамки ZFC. Например, те, формализациями которых являются высшие аксиомы бесконечности.

Миф номер 5. Абстракции бесконечности не имеют никакого отношения к реальности, и не несут никакой пользы для прикладных задач. Как известно, абстракции бесконечности имеют пользу для арифметики. Например, в теории множеств ZFC можно доказать много арифметических утверждений, которые нельзя доказать в арифметике Пеано. И ZFC здесь не предел. Высшие аксиомы бесконечности позволяют доказывать утверждения арифметики, которые нельзя доказать в ZFC. Аксиома существования строго недостижимого кардинала, например, позволяет доказать непротиворечивость ZFC – арифметическое утверждение . Прикладные задачи часто требуют разрешения задач арифметики. Например, известная проблема “P?=NP”, решение которой имело бы огромную пользу для науки и техники, является открытой проблемой, которую можно записать в языке арифметики, и которая обладает всеми не очень приятными особенностями арифметических предложений. Какие средства могут потребоваться для её разрешения, на данный момент не известно. Не исключено, что и ZFC будет недостаточно. Отметим ещё одну особенность абстракций бесконечности: они сильно упрощают жизнь. Например, если бы люди (понимая, что абсолютная точность никому не нужна) всё мерили рациональными числами и приближали скорости движения тел конечными разностями, инженерные расчеты были бы очень громоздкими. В этом смысле бесконечные абстракции действительного числа, производной, интеграла и т.п. очень помогают, сокращая выкладки на несколько порядков.

Миф номер 6. Вся математика, имеющая прикладную значимость, была разработана ещё в 19 веке. Это не так. Почти во всех прикладных областях возникают математические задачи, не сводящиеся к использованию уже готовых методов. Например, большинство известных вычислительных методов работают гораздо медленнее, чем хотелось бы, и границы возможностей их улучшения пока не видно.

МИФЫ О ТЕОРИИ МНОЖЕСТВ

Миф номер 1. Множество и свойство (предикат) – это одно и тоже. Очень распространенный миф. Однако такое представление о действительности приводит к противоречию. Самой известной демонстрацией этого противоречия является парадокс Рассела. Рассмотрим свойство, которому удовлетворяют те и только те множества, которые не являются элементами самих себя. Этому свойству должно соответствовать некоторое множество A всех множеств, удовлетворяющих этому свойству. Теперь попытаемся ответить на вопрос: является ли A элементом себя? При этом как истинный так и ложный ответ будет противоречить определению A.

Миф номер 2. Понятие множества имеет однозначный смысл. Это не так. Сначала попытаемся ответить на вопрос: что может быть элементом множества? Хочется сразу сказать – ВСЁ! Но такой подход приводит к противоречиям (парадокс Рассела, например). Поэтому нужно договориться, что именно. Могут ли элементами быть числа? А зайцы, кролики? А комбинации зайцев или кроликов? А мысли, чувства, вымышленные сущности? А другие множества? И т.п. Следующий вопрос: может ли множество быть элементом себя? Если да, то равны ли, например, два множества A={A} и B={B}? Обычно на эти вопросы отвечают так:
- элементами множеств могут быть только множества;
- множество не может быть элементом себя;
- более того, любое множество должно быть сконструировано из атомов (в данном случае множество атомов пусто), т.е. не существует бесконечной последовательности множеств, где каждое множество является элементом предыдущего.
Естественной вселенной множеств, в которой множества удовлетворяют этим свойствам, является натуральная модель теории множеств. Но таких моделей можно придумать много, ибо недостижимый кардинал не единственен (хотя в ZFC нельзя доказать существование даже одной), и среди них нет такой, которая была бы чем-то лучше других. Основная проблема тут вот в чем: какую бы мы не взяли вселенную, совокупность всех множеств этой вселенной будет вне этой вселенной, хотя по всем признакам эта совокупность ничем не хуже других множеств. Добавив это множество во вселенную и замкнув получившуюся совокупность относительно элементарных теоретико-множественных операций, мы получим новую вселенную, у которой будет аналогичный недостаток и т.д.

Миф номер 3. Язык теории множеств первого порядка является универсальным языком, в котором можно записать любое осмысленное математическое утверждение. Некоторые воспринимают это как аналог тезиса Чёрча-Тьюринга для выразимости. Но на самом деле, нужно повториться, что никакого универсального языка не существует, потому что см. рассуждение в общем мифе 1. Кроме того, истинность в теории множеств зависит от выбора универсума (натуральной модели теории множеств). Например, утверждение о существовании строго недостижимого кардинала ложно во вселенной, соответствующей минимальному строго недостижимому кардиналу, но истинно во вселенной, соответствующей следующему за минимальным.

Миф номер 4. Каждому утверждению теории множеств естественным образом соответствует истинность или ложность. Это не так. См. предыдущий миф.

Миф номер 5. Понятие истинности в теории множеств абсурдно. Это не так. Если мы задали интерпретацию (например, выбрали конкретную натуральную модель теории множеств), то истинность приобретает смысл. Например, мы можем договориться использовать натуральную модель теории множеств, соответствующую минимальному строго недостижимому кардиналу.

Миф номер 6. Парадоксы Кантора/Рассела – это одно из свойств “дурной” бесконечности. Это не так. Какие-либо конкретные свойства мощностей здесь вообще не причём. Это легко пояснить примером. Пусть у нас универсум – это все множества с конечным транзитивным замыканием (транзитивное замыкание – это множество всех элементов множества, элементов элементов и т.д.), т.е. как бы натуральная модель теории множеств, в которой все деревья конечные. Тогда в этом универсуме “множество всех множеств” будет бесконечным (счётным), поэтому будет лежать вне вселенной. На самом деле, парадоксы лишь показывают, что множества относятся не к физической реальности, а являются вымышленными сущностями, которые на то и вымышленные, что их можно придумывать, причём процесс придумывания не сводится к выбору из уже готового набора. Если мы уже придумали какую-то вселенную множеств, то мы можем работать с ней как с физической реальностью.

Миф номер 7. Встречающееся обоснование неконструктивности аксиомы выбора. Рассмотрим множество A всех действительных чисел, которые записываемы конечным математическим текстом (т.е. для которых записываемо свойство, отличающее это число от остальных). Тогда если бы существовало конструктивное правило выбора, то, применив его к множеству R\A (которое, очевидно, не пусто), мы получили бы число, представимое конечным математическим текстом, но не лежащее в A. На самом деле это объяснение скорее показывает отсутствие “универсального языка” для записи даже действительных чисел: утверждения о выразимости “конечным текстом” не получится записать конечным текстом. А нужное число из R\A можно получить, используя диагональ Кантора, аналогично тому, как делается в доказательстве несчётности R, без всякой аксиомы выбора. См. рассуждение из общего мифа 1 и теорему Тарского о невыразимости истины (яндекс).

Миф номер 8. Не существует явного способа, позволяющего выбирать элемент из каждого непустого множества. Распространённый миф: казалось бы, если уж независимость аксиомы выбора от других аксиом ZFC доказана, то отсутствие явной формулы для выбора элемента из множества наверно ещё проще доказать (формула – более простой объект, чем доказательство). Но на самом деле всё в точности наоборот. Например, если выполнена Гёделевская гипотеза конструктивности “V=L” (независимая с ZFC), то все множества можно (конструктивно) упорядочить по “логической сложности” (сложность – ординал), тогда явное правило выбора будет выглядеть так: выбирай множество с минимальной сложностью. Это означает, что утверждения о явной выразимости “правила выбора”, как правило, независимы с ZFC (“утверждениЯ”, потому что понятие выразимости можно определить по-разному).
Замечание: здесь мы считаем, что элементами множеств могут быть только множества (как это обычно делается в теории множеств).

Миф номер 9. Бывают множества, а бывают классы. Например, совокупность всех множеств – это класс, но не множество. На самом деле, понятие класса такое же расплывчатое, как и само понятие множества (см. миф 2). Например, то, что в одной модели было классом-немножеством, в другой вполне может быть множеством. Класс – это абстракция теории Неймана-Бернайса-Гёделя (NBG), нужное для того, чтобы удобно было работать с такими понятиями, как класс эквивалентности, кардинал, ординал и т.д. Например, утверждение “для любого простого p существует ровно одна группа мощности p (с точностью до изоморфизма)” в теории с классами запишется естественным образом (через понятие класса эквивалентности групп относительно изоморфизма), а в теориях без классов, типа ZFC, придётся выкручиваться: “для любого простого p существует группа мощности p, и любые две такие группы изоморфны“.

Миф номер 10. В ZFC выводимы те и только те утверждения (из тех, что выразимы в ее языке), которые истинны вне зависимости от выбора вселенной множеств. Если под вселенной подразумевать модель ZFC, то да. Но у ZFC бывают модели, не имеющие ничего общего со вселенными множеств (например, счетные модели). Гораздо правильнее было бы считать вселенной натуральную модель теории множеств. Тогда это утверждение будет неверно. Например, континуум-гипотеза либо истинна, либо ложна во всех таких вселенных одновременно, но в ZFC её нельзя ни доказать, ни опровергнуть. Тоже самое относится к утверждениям арифметики (точнее, их переводам).

Миф номер 11. Множества делятся на те, существование которых можно доказать в ZFC, и на те, для которых это сделать нельзя. Это не так. ZFC – это формальная теория, оперирующая с символами и формулами, в ней нельзя доказать существование каких-либо множеств. Множество – это человеческое представление. На основе своих представлений человек может составить формулу теории множеств, которая, по его мнению, будет выражать существование некоторого множества.

Миф номер 12. Континуум-гипотезу (отсутствие промежуточной мощности между счетной и континуумом) нельзя ни доказать, ни опровергнуть. Гёдель и Коэн доказали, что это невозможно сделать в ZFC и некоторых её расширениях. Но из этого нельзя делать вывод, что это вообще сделать нельзя! Правильно было бы сказать так: истинность континуум-гипотезы – это открытая проблема.

Миф номер 13. Независимость континуум-гипотезы и ZFC доказана в самой ZFC. Это не так. Из теоремы Гёделя о недоказуемости непротиворечивости следует, что средствами ZFC вообще нельзя доказать недоказуемость чего-либо в ZFC (если она непротиворечива). Гёдель и Коэн сделали своё дело, используя дополнительно утверждение о непротиворечивости ZFC.

Миф номер 14. Высшие аксиомы бесконечности не дают возможности доказать или опровергнуть континуум-гипотезу. Гёдель, Коэн и другие доказали это для достаточно большого класса высших аксиом бесконечности. Но понятие высшей аксиомы бесконечности неформализуемо, поэтому нельзя это утверждать для любой такой аксиомы.

Миф номер 15. Говорить об истинности континуум-гипотезы бессмысленно. Этот миф встречается в работах некоторых матлогиков, но он абсолютно беспочвенен. Из доказанной неразрешимости утверждения для большого класса формальных систем нельзя делать вывод о его бессмысленности, это никчёмный пессимизм. См. миф 5.

МИФЫ О ТЕОРЕМЕ ГЁДЕЛЯ О НЕПОЛНОТЕ

Миф номер 1. Любая непротиворечивая теория не полна. Это неверно. Например, теория первого порядка, порождаемая одной аксиомой “(для любого x)P(x)”, непротиворечива и полна.

Миф номер 2. Любая непротиворечивая теория, содержащая арифметику Пеано, не полна. Это тоже неверно. В качестве контрпримера можно взять множество всех истинных формул в стандартной модели арифметики. Важным условием теоремы Гёделя является перечислимость теории (т.е. возможность алгоритмической проверки доказательств). Теорема Гёделя – это утверждение об алгоритмах и только о них!

Миф номер 3. Утверждение о непротиворечивости теории нельзя записать в языке самой теории. Это не так. В языке арифметики можно записывать утверждения о любых алгоритмах, поэтому можно естественным образом записать утверждение о непротиворечивости для любой теории (точнее, для порождающего её алгоритма). Ограничения есть только для различных утверждений об истинности (см. теорема Тарского о невыразимости истины в яндексе), но никак не для утверждений о формальной выводимости.

Миф номер 4. Теорема Гёделя о неполноте верна только для теорий, построенных на основе логики первого порядка (исчисления предикатов). Это неверно. Теорема Гёделя верна для любой перечислимой корректной теории языка арифметики. Это означает, что должно быть понятие доказательства и возможность это доказательство алгоритмически проверять. Структура доказательства и средства, которые оно использует, не играют никакой роли.

Миф номер 5. Теорема Гёделя о неполноте является ограничением аксиоматического подхода. Это неправда. Теория может быть построена на основе любого подхода. Главное, чтобы была возможность алгоритмически проверять доказательства. Наличие каких-либо аксиом вовсе не обязательно. Правильно было бы сказать так: теорема Гёделя о неполноте является ограничением алгоритмического подхода.

Миф номер 6. Теорема Гёделя о недоказуемости непротиворечивости верна только для теорий, построенных на основе логики первого порядка (исчисления предикатов). Это не так. Единственное ограничение: множество всех выводимых в теории арифметических предложений должно быть замкнуто относительно правил вывода исчисления предикатов (ну и само собой алгоритмическая проверяемость доказательств, содержание арифметики Пеано, корректность). Замкнутость – вполне разумное ограничение. Её отсутствие означает искусственную ограниченность теории. Если мы такую теорию замкнём, то мы ничего не потеряем, теория только расширится, и некорректной от этого не станет (как и не потеряет других перечисленных свойств). Опять же, средства, которые используются в доказательствах, не играют никакой роли.

См. также:
Теорема Гёделя о недоказуемости непротиворечивости
Высшие аксиомы бесконечности
Логические парадоксы и биология
Вымышленные сущности

Постоянная ссылка