Конструктивизм в логике и математике (витгенштейн против гёделя: некоторые современные прочтения)
К.А. Родин
Аннотация
Рассматриваются некоторые современные интерпретации заметок Л. Витгенштейна о Гёделе (о первой теореме о неполноте) в контексте решающего для Витгенштейна в философии математики различия между алгоритмическим и конструктивным (метаматематическим) типом доказательства. В рамках недавнего прочтения Т. Ламперта демонстрируется возможность соотнести соответствующие заметки Витгенштейна непосредственно с доказательством первой теоремы о неполноте.
Ключевые слова: Витгенштейн, первая теорема о неполноте, алгоритмическое доказательство, конструктивное доказательство, теория моделей, семантика.
In recent years, Wittgenstein's remarks on Gцdel have produced many disputes and publications. The discussion overcame the framework of historical and philosophical research, and directly touches upon series of problems adjacent to the proof of the first incompleteness theorem. After the publication in 1956 of Remarks on the Foundations of Mathematics, Kraisel and Bernays attributed a total misunderstanding of Gцdel to Wittgenstein. There were also apologetic readings. To date, almost all friendly or hostile interpretations consider Wittgenstein's remarks irrespective of the mathematical (purely syntactic) proof of the first incompleteness theorem (Wittgenstein's notes must allegedly be understood in the context of the semantic and philosophical implications of the theorem). Among such interpretations it is important to point out the historical and philosophical studies of Floyd (proofs of unprovability are considered here in the context of Wittgenstein's general position regarding the proof of the impossibility of certain geometric constructions). Or there are attempts to see Wittgenstein as the pioneer of paraconsistent logic. Undoubtedly, the semantic and general philosophical consequences of the theorem are of great importance today, and can be better understood in the context of Wittgenstein's remarks. In the article, the author considers the friendly reading of Wittgenstein by Putnam and Floyd (also considering Bays' criticism) (Parts I and II of the article) and the ground-breaking reading by Lampert (Part III). Lampert is notable for the following: he was the first to propose an apologetic reading of Wittgenstein under the condition of correlating the remarks directly with the proof of the first incompleteness theorem (Wittgenstein's approach to algorithmic and metamathematical (constructive) kinds of proof is also considered). In the final part, the author briefly dwells on the difference between two selected interpretations of Wittgenstein's remarks and on the general context of Wittgenstein's attitude toward Gцdel.
Keywords: Wittgenstein; first incompleteness theorem; algorithmic proof; constructive proof; model theory; semantics.
В последние годы вокруг заметок Л. Витгенштейна о Гёделе ведутся многочисленные споры. Дискуссия вышла за рамки историко-философского исследования и непосредственно затрагивает целый ряд проблем - смежных с доказательством первой теоремы о неполноте. После публикации в 1956 г. «Заметок по основаниям математики» (ЗОМ) [1] (Гёделю посвящены фрагменты RFM App. III и RFM Part 5, § 18-22) Крайзель и Бернайс приписали Витгенштейну тотальное непонимание Гёделя [2, 3]. Были и апологетические прочтения (см. работу Гудстейна [4]). На сегодняшний день почти все дружественные или враждебные интерпретации рассматривают заметки Витгенштейна безотносительно к математическому (чисто синтаксическому) доказательству первой теоремы о неполноте (заметки Витгенштейна якобы следует понимать в контексте семантических и философских следствий теоремы). Среди таких интерпретаций можно выделить историко-философские изыскания Флойд (доказательство недоказуемости рассматривается в контексте общей позиции Витгенштейна относительно доказательства невозможности определенных геометрических построений) [5]. Встречаются и попытки записать Витгенштейна в пионеры паранепротиворечивой логики (см.: [6-8]). Несомненно, семантические и общефилософские следствия теоремы имеют сегодня огромное значение (см.: [9]) и в контексте заметок Витгенштейна могут быть лучше поняты. В статье мы рассматриваем дружественное прочтение Витгенштейна Патнэмом и Флойд [10] (с учетом критических замечаний Т. Бейса [11]) (этому посвящены I и II части статьи) и новаторское прочтение Т. Ламперта [12] (III часть). Ламперт примечателен тем, что он первым предложил апологетическое прочтение Витгенштейна при условии соотнесения заметок непосредственно с доказательством первой теоремы о неполноте (здесь учитывается и подход Витгенштейна к алгоритмическому и метаматематическому (конструктивному) доказательству). В заключительной части мы коротко останавливаемся на различии двух избранных прочтений Витгенштейна и на общем контексте прохладного отношения Витгенштейна к Гёделю.
I. Дружественная интерпретация Х. Патнема и Д. Флойд основана на достаточно экстравагантном понимании небольшого отрывка из восьмого параграфа III приложения ЗОМ. Там Витгенштейн утверждает: если допустить (или пусть такой результат фактически получен) доказуемость -р (Р - Гёде- лево предложение G: --іЗуРгооР(у, [G] )), тогда придется отказаться от прочтения P через предложение русского языка «P недоказуемо». Х. Патнем и Д. Флойд понимают идею Витгенштейна так:
пусть доказательство --P фактически найдено,
предположим непротиворечивость системы PM, тогда согласно первой теореме Гёделя о неполноте система PM оказывается ю-противоречивой. Следовательно, для системы PM не существует такой модели, где бы расширение для предиката, который мы прочитываем как «х - натуральное число», было бы изоморфно натуральным числам.
И действительно, запишем гёделево предложение G через: -- (NaturalNo. (x). Proof (x, t)) (где значением t оказывается гёделев номер всего предложения G). Выражение может быть прочитано: «не существует такого х (х - натуральное число), которое оказывается гёделевым номером доказательства предложения с гёделевым номером t. Proof (n, m) есть, соответственно, сокращение для предиката, который задает алгоритмически вычислимое отношение между двумя натуральными числами n и m (при этом обязательно n есть гёделев номер доказательства, последней строкой в котором записано предложение с гёделевым номером m). И тогда приходим к двум положениям:
NaturalNo. (x) нельзя интерпретировать как «х - натуральное число». Во всех допустимых интерпретациях PM будут встречаться элементы - не натуральные числа (если х может не быть натуральным числом, х может не быть и гёделевым номером доказательства).
(Бесконечные) расширения для предикатов в системе PM (Proof (x, t)) неизбежно содержат в качестве элементов нечто помимо подмножества натуральных чисел.
И поэтому прочтение (интерпретация) P через «P недоказуемо в системе PM» невозможно.
Интерпретацию Патнема и Флойд подверг серьезной критике Т. Бейс. Сначала он кратко воспроизводит аргумент Гёделя.
Гёдель определяет формулы (Proof (x, y) и Subst (x, y, z)) - они обладают следующим свойством:
Нумерическая выразимость: пусть m кодирует предложение ф и n - натуральное число. Тогда:
Если n кодирует доказательство ф, тогда (Бейс использует систему Пе- ано РА. Но это никак не влияет на его аргументацию: аналогичные рассуждения могут быть приведены и для системы PM) РА I- Proof (п, ш).
Если п не кодирует доказательство ф, тогда РА I- -i Proof (її, m).
Аналогично пусть ф(и0) - формула с одной свободной переменной и
пусть р кодирует ф, а п и ш - натуральные числа. Тогда получаем:
1. Если ш кодирует ф(п ), тогда РА I- Subst (p, n, m).
2. Если m не кодирует ср(п ), тогда PA I--i Subst (р, fi, m).
С использованием данных формул Гёдель и определил предложение, которое Л. Витгенштейн называет P (и которое мы обозначаем через G). Сначала конструируется следующая формула:
фСо0) = 3 у [Subst (Do, Do, у) & -Іэ z Proof (z, y)].
Пусть e0 кодирует V|/(d0).
G = v|/(кB) = a y [Subst (%, к0, y) & -13 Z Proof (z, y)].
При допущении обоснованности (soundness) PA - при допущении N = PA (логический символ 1= означает «семантически влечет») - нумериче- ская выразимость вышеопределенных формул Proof (x, y) и Subst (x, y, z) приводит к другому свойству:
Арифметическая выразимость: для любых двух чисел п и m N 1= Proof (fi, m) если и только если m кодирует предложение ф, а п кодирует доказательство предложения ф. Аналогично: для любых трех чисел n, m и г N = Subst (fi, m, г) если и только если п кодирует формулу ф(ио), а г кодирует предложение ф(ш).
G = v|/(кE) прочитывается следующим образом: {элемент еЕ кодирует ф(и0)} подставим в ф(и0) вместо и0 и получим, что, согласно определению Subst (x, у, z) и определением самой функции v|/(u0) при замене еЕ на у (теперь у кодирует v|/(кE)) одновременно не существует значения z, которое кодировало бы закодированное через y предложение. Арифметическая выразимость позволяет говорить, что G «принадлежит» теории чисел (а использованная кодировка или нумерация изоморфна подмножеству натуральных чисел). Приходим к прочтению:
--13 z Proof (z, у) говорит: предложение с гёделевым номером у недоказуемо.
Subst (к0,к0, у) говорит: у - гёделев номер предложения G.
Поэтому и можно интерпретировать G через «G недоказуемо».
Нетрудно объяснить и семантическое прочтение первой теоремы о неполноте «G истинно и недоказуемо» (мы продолжаем следовать за статьей Т. Бейса). С учетом арифметической выразимости N 1= G, если и только если существует n, что N 1= Subst (к0, кE, fi) и N 1= --13 zProof (z, fi), если и только если существует п, который кодирует G, и N 1= --|Э z Proof (z, fi), если и только если не существует m, который кодирует доказательство G, если и только если PA Ц G.
Подобная эквивалентность диктует выбор: N = G и PA Ц G или N ф G и PA h G. Вторая альтернатива противоречит обоснованности (soundness) PA (N ф G и, следовательно, N ф PA). Поэтому мы вынуждены предпочесть первую. Поэтому «G истинно и недоказуемо».
Вернемся к интерпретации Патнема и Флойд (ПиФ). Предположим непротиворечивость РА и одновременно предположим РА І- -і G. Это влечет N ф РА. (N 1= РА и N 1= -і GиNl^Gи РА I- G и PA противоречива). Отсюда следует, что только нестандартные (неизоморфные натуральным числам) модели теории чисел удовлетворяют системе PA. И поэтому PA ю-противоречива (хотя требование ю-противоречивости и более сильное в сравнении с утверждением о существовании для PA только нестандартных моделей). Действительно, ю-противоречивость подразумевает существование некоторой определенной формулы ф(х), такой что для любого п РА I--і cp(Sо) и одновременно РА І- З X ф(х). Для PA I 1 G для любого n PA I 1 Proof
(й, TGI) и одновременно РА h 3 X Proof (x, TGI).
Теперь аргумент ПиФ можно продолжить. Рассмотрим специфическую модель РА - М. Поскольку РА h -i G, справедливо М 1= эх Proof (х, [ГGl )~). А значит, существует элемент m Є М, такой что М 1= Proof (in, fGl ). Однако согласно нумерической выразимости М 1= -i Proof (n, TG1) для любого натурального числа n. Отсюда соответствующий элемент m не является обычным натуральным числом (m один из «нестандартных» элементов М). Но тогда непонятно, в каком смысле m все еще кодирует доказательство G (и вообще кодирует что угодно). И поэтому нет оснований полагать, что (при интерпретации в рамках модели М) формула Proof (x, y) отображает понятие «у кодирует предложение - х кодирует доказательство данного предложения».
Интерпретация G через «G недоказуемо» на интуитивном уровне предполагает интерпретацию G на множестве натуральных чисел. «+» понимается как сложение. Э:т определяется на множестве натуральных чисел и т.д. Но если предположить, что доказано --G, такая интерпретация становится несовместимой с PA (PA в данном случае имеет только нестандартные модели). Аналогично интерпретация G через «G недоказуемо» обязана интерпретации Proof (x, y) в рамках свойства арифметической выразимости. Но интерпретация Proof (х, у) через нестандартные модели несовместима с арифметической выразимостью. Таким образом, при допущении PA I 1 G необходимо отка
заться от исходной интерпретации G и одновременно от исходного понимания Proof (x, y). Однако в подобном заключении нет ничего необычного: синтаксическое доказательство Гёделя и показывает (посредством нумерической выразимости), что при ю-непротиворечивости системы PA: PA Ц G (что с учетом арифметической выразимости соответствует первому из двух возможных обозначенных выше вариантов). Здесь вообще (поскольку доказательство чисто синтаксическое) возможно не принимать никакую интерпретацию.
Интерпретация ПиФ Витгенштейна на деле оказывается малоинтересной и бесперспективной (даже если согласиться с возможным прозрением Л. Витгенштейна в теории моделей). Представленный Т. Бейс теоретико-модельный аргумент вместе с экспликацией интерпретации ПиФ неизбежно ставит перед выбором: следует либо модифицировать интуитивную стандартную интерпретацию и, стало быть, перестать рассматривать N в качестве подходящей модели для нашего формального языка PA (в таком случае придется отказаться от интерпретации G через «G недоказуемо»), либо считать неудовлетворительной аксиоматизацию арифметики в формальной системе PA и сохранить при этом «релевантность» стандартной интерпретации. Патнем и Флойд автоматически предпочли первый вариант. Но при РА I- G сообщество математиков предпочло бы второй вариант и занялось бы поиском более подходящей для аксиоматизации арифметики системы (или принялось бы за модификацию существующей). По справедливому замечанию Бейса, математики предпочли бы пересмотр PA и исключение приведших к подобному доказательству принципов аксиоматизации (хотя подобное и может привести к отказу от стандартной интерпретации G). В любом случае никто не станет принимать нестандартные модели с целью сохранить ю-непротиворечивость PA. И если доказательство --G будет фактически найдено, предпочтительным станет не отказ от стандартной интерпретации G и признание существования только нестандартных моделей для PA. Наоборот, стандартная модель скорее будет сохранена путем поиска более подходящей аксиоматизации для натуральных чисел.
Допустим - несмотря на соображения Т. Бейс - релевантность интерпретации ПиФ. Интерпретация имеет смысл только благодаря известной асимметрии в доказательстве Гёделя «между» G и --G. Гёдель доказал недоказуемость G при условии непротиворечивости системы PM и недоказуемость --G при условии ю-непротиворечивости PM (более сильное допущение). Поэтому стало возможным при условии непротиворечивости PM предположить доказуемость --G и прийти к ю-противоречивости. Однако в 1936 г. Дж. Баркли Россер продемонстрировал необязательность подобной асимметрии в доказательстве неполноты системы PM. Так называемая уловка Россера демонстрирует: если доказуемо R (предложение Россера отличается от G), тогда за меньшее число шагов доказуемо и --R. Таким образом, интерпретация ПиФ (и позиция Витгенштейна - совпадай она с данной интерпретацией) перестают иметь какое бы то ни было существенное значение. Предположение PM І- -і G остается возможным, однако не имеет никаких последствий для общего результата ввиду своей экстравагантности и фактической невероятности.
Патнем и Флойд рассматривают только первую часть «аргумента» Витгенштейна: если допустить (или пусть такой результат фактически получен) доказуемость --G, тогда придется отказаться от прочтения G через «G недоказуемо». Однако Витгенштейн (так кажется при первом прочтении) сразу же распространяет подобное соображение и на доказуемость G: «If you assume that the proposition is provable in Russell's system, that means it is true in the Russell sense, and the interpretation «P is not provable» again has to be given up». Если под «the proposition» Витгенштейн продолжает подразумевать G, тогда интерпретация ПиФ оказывается несостоятельной (потому что нельзя предположить по аналогии непротиворечивость PM и одновременно PM h G). Поэтому есть основания не только отвергнуть интерпретацию ПиФ изнутри (что сделал Бейс), но и продемонстрировать безынтересность вообще и нере- левантность подобной интерпретации относительно текста Витгенштейна «извне».
Теперь обратимся к интерпретации Т. Ламперта. Ламперт в 2017 г. первым предложил подойти к заметкам Витгенштейна о Гёделе как если бы заметки имели отношение к математическому доказательству 1-й теоремы о неполноте непосредственно. Предложенные ранее дружественные или враждебные прочтения Витгенштейна, напротив, почти всегда заранее исключали такой подход и опирались на семантический (не оригинальный) вариант теоремы. Так, при воспроизведении интерпретации ПиФ мы должны были обращаться к семантическому свойству арифметической выразимости и использовать понятие обоснованности системы PA (все аксиомы PA истинны в стандартной интерпретации N: N |= PA). На деле никакое понятие истины в доказательстве 1-й теоремы о неполноте не фигурирует. Доказательство не требует полной формальной интерпретации символов избранного языка и не привлекает понятие истины. Однако доказательство Гёделя нуждается в корреляции между натуральными числами и формальными выражениями (между натуральными числами и терминами избранного формального языка). В противном случае невозможно было бы доказать свойство нумерической выразимости. витгенштейн конструктивный доказательство математика