Мнение Витгенштейна о математической индукции и алгоритмической разрешимости

Учитывая то, что нельзя навешивать кванторы над бесконечной математической областью определения, возникает вопрос: Что, если уж на то пошло, любое теоретико-числовое доказательство посредством математической индукции на самом деле доказывает?

Обычно, доказательство методом математической индукции строится следующим хрестоматийным образом:

База индукции: φ(1)

Шаг индукции:  n(φ(n) →φ(n + 1))

Утверждение:  nφ(n)

Если, однако, «  nφ(n)» - это не значащее (подлинное) математическое предложение, из чего же мы должны составить это доказательство?

Исходный ответ Витгенштейна на этот вопрос, несомненно, загадочен. «Индукция – это выражение арифметической общности», но «индукция сама по себе не предложение» (PR §129).

Мы не говорим, что когда выполняется f(1) и когда f(c + 1) следует из f(c), то, следовательно, предложение f(x) истинно для всего натурального ряда; но: «предложение f(x) выполняется для всех натуральных чисел» означает, что «оно выполняется для x = 1, и f(c + 1) следует из f(c)». (PG 406)

В доказательстве методом математической индукции, мы в действительности не доказываем «предложение» [например,  nφ(n)], которое традиционно толкуется как утверждение доказательства (PG 406, 374; PR §164), хотя скорее это псевдо-предложение или «формулировка» находится в качестве «заместителя» для «бесконечной возможности» (т.е., «индукции»), которую мы хотим «увидеть» при помощи доказательства (WVC 135). «Я хочу сказать», заключает Витгенштейн, что «однажды получив индукцию, на этом все и кончается» (PG 407). Поэтому, по мнению Витгенштейна, особое доказательство методом математической индукции нужно понимать следующим образом:

База индукции: φ(1)

Шаг индукции: φ(n) →φ(n + 1)

Заместитель утверждения: φ(m)

Здесь в «утверждении» индуктивного доказательства [т.е., «то, что нужно доказать» (PR §164)] используется ‘m’ вместо ‘n’ для обозначения того, что ‘m’ есть любое конкретное число, в то время как ‘n’ – это любое произвольное число. Для Витгенштейна, заместитель утверждения “φ (m)” – это не математическое предложение, которое «утверждает о своей общности» (PR §168), это элиминируемое (устранимое) псевдо-предложение, которое выступает заместителем для доказанных базы и индуктивного шага. Хотя индуктивное доказательство не может доказать «бесконечную возможность применения» (PR §163), оно позволяет нам «осознать», что прямое доказательство любого конкретного предложения может быть построено в конструктивной манере. Например, если мы доказали “φ(1)” и “φ(n) →φ(n + 1)”, то нам не нужно повторять модус поненс (modus ponens) m – 1 раз для доказательства конкретного предложения “φ(m)” (PR §164). Прямое доказательство, скажем, “φ(714)” (т.е., без 713 итераций модус поненс) «не может иметь еще лучшего доказательства, чем, скажем, мое установление вывода, поскольку это и есть само предложение» (PR §165).

Вторым очень важным моментом для Витгенштейновской радикальной конструктивной позиции по поводу математической индукции является его отказ от неразрешимых математических предложений.

Во время дискуссий о доказуемости математических предложений часто высказывается мнение, что есть существенные математические предложения, чьи истинность или ложность должны оставаться неразрешимыми. То, чего не понимают говорящие это люди, так это то, что такие предложения, если мы можем использовать их и хотим называть их «предложениями», это совсем не то же самое, что мы называем «предложениями» в других случаях; потому что доказательство меняет грамматику предложения (PG 367).

В этой цитате, Витгенштейн ссылается на Брауэра, который в 1907 и 1908 заявляет, во-первых, что «вопрос соблюдения principium tertii exclusi эквивалентен вопросу существуют ли неразрешимые математические проблемы», во-вторых, что «нет даже частицы (?shred) доказательства того убеждения, … что не существует неразрешимых математических проблем», и, в-третьих, что существует значащие предложения/«вопросы», такие как «Существует ли в десятичном разложении числа π бесконечно много пар равных цифр?», к которым закон исключенного третьего неприменим, потому что «нужно рассматривать неопределенным то, решаемы ли проблемы подобно [данной]» (Brouwer, 1908 [1975, 109-110]). «Тем более не является определенным то, что любая математическая проблема может быть решена, либо доказана ее нерешаемость», говорит Брауэр в (1907 [1975, 79]), «хотя ГИЛЬБЕРТ в “Mathematische Probleme” верит, что каждый математик глубоко в этом убежден».

Витгенштейн из тех же начальных данных делает противоположный вывод. Если, по словам Брауэра, мы не уверены, все ли или некоторые «математические проблемы» решаемы, то мы знаем, что у нас нет на данный момент применимой процедуры разрешимости, что означает, что заявленные математические предложения неразрешимы, здесь и сейчас. «То, что «математические вопросы» имеют общего с подлинными вопросами», пишет Витгенштейн в (PR §151), «так это то, что на них можно ответить». Это значит, что если мы не знаем как разрешить выражение, то мы также не знаем как его сделать ни доказанным (истинным), ни опровергнутым (ложным), что значит, что закон исключенного третьего «неприменим», и, поэтому, что наше выражение – не математическое предложение.

Как Витгенштейновский финитизм, так и его критерий алгоритмической разрешимости проливают свет на его очень спорные замечания о мнимых значимых гипотезах, таких как ПТФ и ГГ. ГГ – это не математическое предложение, потому что мы не знаем как разрешить ее, и если кто-то подобно G. H. Hardy говорит, что он «верит» в истинность ГГ (PG 381; LFM 123; PI §578), мы должны сказать, что у него/нее только «имеются догадки о возможностях расширения существующей системы» (LFM 139) – что человек может верить, что выражение «корректно» только в том случае, если он знает как доказать это. ГГ может быть быть доказана только в смысле, в котором она может «соответствовать доказательству методом математической индукции», что значит, что недоказанный индуктивный шаг (т.е., “G(n) →G(n + 1)”) и выражение « nG(n)» не являются математическими предложениями, т.к. у нас нет алгоритмического способа поиска индукции (PG 367). «Общее предложение» бессмысленно еще до индуктивного доказательства «потому что вопрос имел бы смысл только тогда, когда общий метод разрешения был бы известен до открытия конкретного доказательства» (PG 402). Недоказанные «индукции» или индуктивные шаги - не значащие предложения, потому что закон исключенного третьего не выполняется в том смысле, что мы не знаем процедуру разрешимости, с помощью которой мы можем доказать или опровергнуть выражение (PG 400; WVC 82).

Кажется, что такая позиция, однако, лишает нас какой-либо причины искать «разрешимость» такого незначащего «выражения», как ГГ. Витгенштейн в переходный период только говорит, что «математик... руководствуется... определенными аналогиями с существовавшей ранее системой» и что нет ничего «неправильного или незаконного в том, что кто-то занимается последней теоремой Ферма» (WVC 144).

Если, например, у меня есть метод поиска целых чисел, удовлетворяющих уравнению x^2 + y^2 = z^2, то формула x^n + y^n = z^n может простимулировать меня. Я могу позволить формуле побудить меня к действию. Т.о. я скажу, что здесь имеется стимул (побудитель) – но не вопрос. Математические проблемы всегда являются такими стимулами. (WVC 144, Jan. 1, 1931)

Более точно, математик может позволить бессмысленной гипотезе, такой как ПТФ, простимулировать его/ее, если он/она желает знать, может ли исчисление быть расширено без изменения его аксиом или правил (LFM 139).

То, что здесь происходит [в попытке разрешить ГГ], - это несистематическая попытка конструирования исчисления. Если попытка успешная, то у меня снова будет исчисление, правда уже отличное от того, которое я использовал до сих пор. (WVC 174-75; Sept. 21, 1931)

Если, например, нам удастся доказать ГГ методом математической индукции (т.е., мы докажем “G(1)” и “G(n) →G(n + 1)”), то мы получим доказательство индуктивного шага, но поскольку индуктивный шаг не был предварительно алгоритмически разрешим [(PR §§148, 155, 157), (PG 380)], то при конструировании доказательства мы построили новое исчисление, новую вычислительную машину (WVC 106), в которой мы теперь знаем как использовать это новую «машино-часть» (RFM VI, §13) (т.е., несистематически доказанный индуктивный шаг). До доказательства индуктивный шаг не является осмысленным математическим предложением (в конкретном исчислении), тогда как после доказательства шаг индукции уже является математическим предложением с новым, определенным смыслом, и в новом, только что созданном исчислении. Это разграничение выражений без математического смысла и доказанных либо опровергнутых предложений, каждое из которых имеет определенный смысл в некотором исчислении, есть точка зрения Витгенштейна, которую он произносил несметное число раз с 1929 по 1944.

Неизвестно, является ли это в конечном счете оправданным – а это абсолютно ключевой вопрос для философии математики Витгенштейна – этот сильно не-интуитивный аспект мнения Витгенштейна об алгоритмической разрешимости, доказательстве и смысле математических предложений есть часть его отказа от предопределенности в математике. Даже в том случае, если мы алгоритически разрешим математическое предложение, связи, которые возникли в результате, не существуют до алгоритмической разрешимости, что означает, что даже если у нас есть «математический вопрос», разрешенный нашей процедурой разрешимости, выражение имеет определенный смысл только как предложение, которое разрешено. Как в средний, так в поздний период Витгенштейн считал, что «новое доказательство дает предложению место для новой системы» (RFM VI, §13), оно «помещает его в целую систему исчислений», хотя оно «не приводит, полностью не описывает целую систему вычислений, которые стоят за предложением и придают ему смысл» (RFM VI, §11).

Необычная позиция Витгенштейна здесь – вариант структурализма, который частично происходит из его непринятия математической семантики. Мы ошибочно думаем, например, что ГГ имеет полностью определенный смысл, потому что, следуя «обманчивым путем, где тип выражения языка, состоящего из слов, дает смысл математических предложений» (PG 375), мы воспроизводим в памяти ложные картины и ошибочные, ссылочные концепции математических предложений, и тем самым ГГ у нас получается о математической реальности, и т.о. имеет определенный смысл, такой как «где-то еще во Вселенной существуют разумные существа» (т.е., предложение, которое определенно является истинным или ложным, независимо от того, знали ли мы когда-нибудь его истинностное значение). Витгенштейн покончил с этой традицией, во всех ее формах, подчеркивая, что в математике, в отличие от области контингенциальных (или эмпирических) предложений, «если мне нужно знать, что говорит такое предложение, как последняя теорема Ферма», я должен знать ее критерий истины. В отличие от критерия истины для эмпирических предложений, который может быть известен до того, как предложение разрешено, мы не можем знать критерий истины для нерезрешенного математического предложения, хотя мы «знакомы с критерием истины для похожих предложений» (RFM VI, §13).