Раздел 4. Субдисциплины философии математики

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

Тезис о том, что теория множеств наиболее подходит для использования в качестве основы математики, ни в коем случае не является спорным. За последние десятилетия теория категорий выступила в качестве конкурента на эту роль. Теория категорий - это математическая теория, которая была разработана в середине двадцатого века. В отличие от теории множеств, в теории категорий математические объекты определяются только с точностью до изоморфизма. Это означает, что проблема идентификации Бенацеррафа не может быть поднята для теоретических понятий категории и «объектов». В то же время (приблизительно) все, что можно сделать в теории множеств, можно сделать в теории категорий (но не всегда естественным образом) и наоборот (опять же не всегда естественным образом). Это означает, что для структурной точки зрения теория категорий является привлекательным кандидатом для обеспечения основ математики [4, с. 87].

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

Некоторые из исследователей, которые пытаются решить гипотезу континуума, думают, что это правда; другие думают, что это ложно. Но есть также множество теоретиков и философов математики, которые считают, что гипотеза континуума не просто неразрешима в ZFC, но абсолютно неразрешима, то есть она не доказуема (в неформальном смысле этого слова) и не опровергаема (в неформальном смысле слово), потому что это не правда и не ложь. Например, если математическая вселенная является множественной теоретической мультивселенной, то существуют в равной степени модели, которые делают гипотезу континуума истинной, и в равной степени хорошие модели, делающие ее ложной, и больше говорить нечего [9, с. 135-136].

4.2. Категоричность. Во второй половине девятнадцатого века Дедекинд доказал, что основные аксиомы арифметики, вплоть до изоморфизма, имеют ровно одну модель, и то же самое справедливо для основных аксиом реального анализа. Если теория, вплоть до изоморфизма, имеет ровно одну модель, то она называется категориальной. Таким образом, по модулю изоморфизмы, арифметика и анализ имеют точно одну предполагаемую модель. Спустя полвека Цермело доказал, что принципы теории множеств являются «почти» категоричными или квазикатегоричными: для любых двух моделей принципов теории множеств M1 и M2 либо M1 изоморфна M2, либо M1 изоморфна сильно недоступный ранг M2, или M2 изоморфен сильно недоступному рангу M1 [4, с. 40]. В последние годы предпринимались попытки разработать аргументы о том, что заключение Цермело может быть усилено до полного утверждения категоричности [11, с. 30], но мы не будем обсуждать эти аргументы здесь.

В то же время в теореме Левенгейма-Сколема говорится, что каждая формальная теория первого порядка, имеющая хотя бы одну модель с бесконечной областью, должна иметь модели с областями всех бесконечных мощностей. Поскольку принципы арифметики, анализа и теории множеств должны обладать хотя бы одной бесконечной моделью, теорема Лёвенхайма-Сколема, кажется, применима к ним. Разве это не противоречит теорем Дедекинда о категоричности?

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

4.3. Расчет и доказательство. До недавнего времени предмету вычислений не уделялось много внимания в философии математики. Это может быть отчасти связано с тем, что в аксиоматизации теории чисел в гильбертовом стиле вычисления сводятся к доказательству в арифметике Пеано. Но эта ситуация изменилась в последние годы. Кажется, что наряду с возросшей важностью вычислений в математической практике философские размышления о понятии вычислений будут занимать более видное место в философии математики в последующие годы.

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

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

Крейзель давно указал, что даже если тезис не может быть формально доказан, все же возможно получить внутреннее доказательство для него из строгого, но неформального анализа интуитивных представлений [8, с. 35]. Крейзель называет эти упражнения неформальной строгостью. Подробная стипендия Sieg показала, что оригинальная статья представляет собой прекрасный пример именно такого рода анализа интуитивной концепции алгоритмической вычислимости [11, с. 41].

В настоящее время наиболее активными объектами исследований в области основ и философии вычислений являются следующие. Во-первых, энергия была вложена в разработку теорий алгоритмического вычисления на структурах, отличных от натуральных чисел. В частности, были предприняты попытки получить аналоги тезиса Черча для алгоритмических вычислений на различных структурах. В этом контексте в последние десятилетия был достигнут существенный прогресс в разработке теории эффективных вычислений для действительных чисел. Во-вторых, были предприняты попытки объяснить понятия вычислимости, отличные от алгоритмической вычислимости, людьми. Здесь особый интерес представляет область квантовых вычислений.