Cтраница 1
Результаты Геделя ( верные не только по отношению к арифметике, но и ко всякой системе, содержащей арифметику натуральных чисел как свою часть - такова, напр. Черч, пользуясь методами, аналогичными геделевым, доказал неразрешимость проблемы разрешения как для теорий, содержащих арифметику натуральных чисел, так и для исчисления предикатов), имели важнейшее филос. [1]
Результаты Геделя применимы к любой дедуктивной системе, достаточно богатой для того, чтобы содержать арифметику. Даже в обычной арифметике существуют утверждения, которые истинны, но недоказуемы. [2]
Можно было бы подумать, что результат Геделя вскрывает лишь недостаточную полноту выбранной нами системы аксиом формальной арифметики и что при разумном пополнении этой системы аксиом новыми аксиомами неполнота арифметики ( при сохранении ее непротиворечивости) уже не будет иметь места. В действительности дело обстоит далеко не так просто. Как показывает подробный анализ, проведенный Геделем, при любом непротиворечивом расширении системы аксиом формальная арифметика продолжает оставаться неполной и в ней по-прежнему будут существовать неразрешимые замкнутые формулы. Более того, всякая формальная система, удовлетворяющая некоторым довольно общим условиям ( наличие достаточно богатого набора формул и объектов), в случае ее непротиворечивости будет обязательно неполной. [3]
Свою первую, написанную еще в студенческие годы, работу по математической логике А. И. Мальцев [1 ] посвятил доказательству двух теорем, обобщавших результаты Геделя и Сколема. Вторая его привлекала именно потому, что непосредственно допускала алгебраическое истолкование: он из нее сделал заключение, что всякое бесконечное алгебраическое тело имеет расширения. Теорема, о которой идет речь, гласит, что если выполнима всякая конечная часть некоторой бесконечной системы предложений, допускающих выражение средствами узкого исчисления предикатов, то выполнимой является и вся система. А имеет место и для всей области-могут быть получены из этого предложения как непосредственные следствия. Для доказательства их достаточно убедиться в том, что утверждение о справедливости свойства А для какой-нибудь области может быть записано в виде системы предложений, содержащих - кроме знаков для индивидуальных предикатов и индивидуальных предметов и знака равенства - логические связки и, или, если... Такой общий подход к локальным теоремам не только позволил А. И. Мальцеву получить сразу ряд теорем, доказанных ранее весьма частными приемами ( в том числе; например, теорему Шура о том, что всякая периодическая группа матриц над полем характеристики нуль содержит абелев нормальный делитель конечного индекса), но и непосредственно усмотреть, что некоторые из них имеют место и в более широких условиях. Так, в доказательстве по методу А. И. Мальцева теоремы Черникова: если всякая подгруппа локально-конечной группы g имеет силовское множество, то силовскую систему имеет и сама группа g - локальная конечность нигде не используется. Для доказанного первоначально Бэром только для счетных групп предложения о расширении структурного изоморфизма Л. Е. Садовским было указано впоследствии доказательство, годное и для несчетных групп. По методу А. И. Мальцева предложение Бэра доказывается сразу, буквально в несколько строк, в самых общих предположениях. [4]
Метаматематические результаты, изложенные до сих пор в этой книге, были получены методами, которые более или менее подсказывались интерпретацией системы. Результаты Геделя получаются с помощью метаматематических рассуждений, глубже проникающих в структуру формальной системы как системы объектов. [5]
В этой работе было показано, что некоторые математические проблемы не могут быть решены алгоритмами из определенного класса. Общность результата Геделя связана с вопросом о том, совпадает ли использованный им класс алгоритмов с классом всех алгоритмов в интуитивном понимании этого термина. [6]
Оба доказательства имеют много общего и, естественно, основные положения из результатов Геделя могут быть непосредственно получены путем использования процедуры Тьюринга. Давайте посмотрим, как это происходит, и как при этом можно несколько иным образом взглянуть на то, что осталось за кулисами теоремы Геделя. [7]
Допущение более широких ( но корректных с точки зрения брауэровского интуициониз ма) средств пришло позднее, особенно под влиянием результатов Геделя о неполноте. Генценовское доказательство непротиворечивости арифметики [10] показало, как можно примирить ограничения, налагаемые теоремой Геделя, с требованием фи-нитности: привлеченный Генценом принцип ( бескванторная индукция до е0), выходящий за рамки формальной арифметики первого порядка, формулируется в языке финитных предложений. [8]
Этот замечательный результат, который был открыт Куртом Геделем в 1931 году, наводит на мысль о том, что натуральные числа, возможно, не являются единственным классом объектов, для которых доказуемые формулы из М верифицируемы, и что, возможно, существует класс объектов, который включает все натуральные числа и, кроме них, другие объекты, для которых доказуемые формулы М верифицируемы. То, что такой класс на самом деле существует, было действу тельно установлено через три года после результата Ге-деля Торальфом Сколемом, создателем рекурсивной арифметики, который показал ( независимо от методов и результатов Геделя), что не только системы вроде М и М, но всякая формализация арифметики не может полностью характеризовать понятие числа и допускает в качестве значений числовых переменных класс объектов такой, что все натуральные числа являются лишь его начальным сегментом. [9]
Легко и просто за какие-нибудь три пассажа Смаллиан показывает, что на острове существует по крайней мере один непризнанный рыцарь и по крайней мере один неотъявленный лжец. Если рассматривать рыцарей как истинные утверждения, признанных рыцарей как доказуемые истинные утверждения, лжецов как ложные утверждения и отъявленных лжецов как доказуемые ложные утверждения, то результаты, к которым приходит в ходе своих рассуждений Смаллиан, соответствуют результатам Геделя. [10]
Он неоднократно описывался ( см., например: Шенфлис [ 1, с. В свете результатов Геделя [1] и Коэна [1] эта неудача становится объяснимой. [11]
Нельсоном [ 1947, части II - IV ] ( и Клини [1945]) получены уточнения результатов, изложенных нами здесь на основе интерпретации. Так как все они опираются на непротиворечивость арифметического формализма, то вполне элементарного рассмотрения ожидать нельзя. В частности, в силу этих результатов и результатов Геделя [1932 - 33] ( см. следствие 2 из теоремы 60), метаматематически доказано, что как S, так и Sc просто непротиворечивы, если просто непротиворечива S. Нельсон в качестве своей 5 выбирает л не нашу интуиционистскую формальную систему, а систему, которая, если отвлечься от несущественного различия в постулатах равенства, получается из нашей путем присоединения некоторых дополнительных функциональных символов с их определяющими уравнениями. Эти уравнения подходят под наши схемы ( I) - ( V) § 43 1) или под очень похожие схемы, если не считать того, что допускается также некоторая схема возвратной рекурсии. [12]
Все это ставит определенные границы возможностям А. Однако и в этих границах он сыграл и продолжает играть важную роль в основаниях математики. Что касается такого основного вопроса оснований математики, как проблема непротиворечивости, то после результатов Геделя стало ясно, что для его решения, по-видимому, не обойтись без других, отличных от финитистских, средств и идей. Здесь оказались возможными разные подходы, не для всех математиков в равной степени приемлемые или убедительные, в частности в виду существования различных точек зрения на допустимость тех или иных логич. Из результатов о непротиворечивости формальных систем следует прежде всего указать на доказательство непротиворечивости формализованной арифметики ( см. [8]), к-рое опирается на бесконечную индукцию до нек-рого счетного трансфинита. [13]