Гильберт, Бернайс - Основания математики. Теория доказательств (947376), страница 71
Текст из файла (страница 71)
Затем, согласно допущениям а) и в), функцию эту можно изобразить некоторым термом 6(Й, 2), обладающим тем свойством, что если 2 является номером некоторого выражения Я из Р, 2 — некоторой цифрой, а ~п — номером выражения, получающегося из й в результате повсеместной замены переменной а цифрой 2, то в Р выводимо равенство 6(2, 2) ° ж. Кроме того, терм 6(Г», 2) может быть выбран таким образом, чтобы в нем не встречалось никаких связанных переменных, входящих в формулу Ю2(а), так что выражение Ю2(6(а, а)) и его отрицание 2 И (6 (а, а)) будут формулами. Номер формулы ~% (6 (а, п)) мы обозначим буквой «. Если 2 — цифра, являющаяся номером выражения й, то значение 6(2, 2) представляет собой номер того выражения, которое получается из Я в результате повсеместной замены переменной а цифрой Е Поэтому значение терма 6(«, «) представляет собой номер формулы 1%(6(««)) Лусть а — этот номер, тогда вследствие упоминавшегося выше свойства терма 6(й, 2) в Р будет выводимо равенство 6 («, «) я.
Отсюда (по предположению а)2 получаются импликации Ю2 (ч) Ю2 (6 (««)) и И (6 (««))» И (ч) С другой стороны, [согласно допущению г)], так как й является номером формулы 2%(6(«, «)), не содержащей свобоДных переменных, то в' г" выводимы импликации Ю2 (а) -э ) % (6 («, «)) и 1 И (6 («, «)) -+ И (я). Теперь мы легко получаем противоречие. Действительно, импликации Ю2(6(«, «))-~-Ю2(й) н Ю2(ч)-~- 1Ю2(6(«, «)), взятые друг с другом, дают формулу %(6(«, «)) 1Ю2(6(«, «)). из которой затем получается формула ) Ю2(6(««)) С другой стороны, эта формула, взятая вместе с импликациями 2%(6(«, «))-эЮ2(ц) и %(й)-».Ю2(6(«, «)), дает нам формулу И (6 ( .
«)). Тем самым мы получили формализацию антиномии лжеца. При этом высказыванию, утверждающему свою собственную ложность, соответствует формула 2 И (6 («, «)). Действительно, для любого числа п, являющегося номером какой- либо формулы Я без свободных переменных„ формула Ю2(п) изображает утверждение об истинности Я, и потому ~Ю2(п) изображает утверждение о том, что Я ложно. Так как 6(«, «(=ч„а я является номером формулы ) Ю2(6 («, «)), то формула 2 ш2(6(«, «)) изображает утверждение о том, что )Ю2(6(«, «)) ложно.
То обстоятельство, что эту антиномию можно изложить совершенно формально, отчетливо показывает, что она не имеет никакого отношения к вопросу о реальной истине как гносеологической проблеме. Более того, в данной ситуации от понятия истинности данного высказывания для получения противоречия нам потребовалось лишь то, что было формализовано в предположении г) и что в обиходном языке может быть сформулировано примерно следующим 'образом: «Любое предложение вида „высказывание Я истинно" само является высказыванием; из этого высказывания следует высказывание Я, и обратно: это предложение следует из высказывания Я». Но перечисляя явным образом предположения, сделанные относительно рассматриваемого дедуктивного формализма, и формализуя эту антиномию, мы добиваемся в первую очередь не парадокса. У нас получается некоторый общий факт, относящийся к дедуктивным формализмам вообще.
Именно, обнаруженное противоречие показывает, что для любого непротиворечивого формализма Р, удовлетворяющего условиям а) — г), если имеется взаимно однозначная нумерация его выражений, обладающая указанными в допущении б) свойствами, то невозможна такая формализация в рамках самого «' числового преднката еч является номером некоторой формулы из формализма г, изображающей истинное утверждение», которая удовлетворяла бы условию г). 337 336 ВЫХОД ЗА РАМКИ ТЕОРИИ ДОКАЗАТЕЛЬСТВ 1гл т 5 н ГРАНИЦЫ ИЗОБРАЗИМОСТИ И ВЫВОДИМОСТИ Как уже упоминалось, сделанные нами предголожения в некоторых отношениях могут быть ослаблены. В этой связи заметим, в частности, следующее: 1.
Не обязательно требовать, чтобы в формализме Р имелись свободные переменные. В самом деле, в нашем выводе противоречия свободная переменная а фигурирует лишь постольку, поскольку, с одной стороны, в определении рекурсивной функции, представленной термом 6(й, 1), используется ссылка иа замену переменной а некоторой цифрой и, с другой стороны, цифоа р определяется как номер выражения ЭЛ(6(а, а)).
Но для этого вовсе не требуется, чтобы переменная а принадлежала формализму Р, а нужно лишь, чтобы она была включена в нашу нумерацию. Аналогичным образом в формулировке наших предположений свободные переменные могут быть использованы для указания мест аргументов также без того, чтобы включать их в сам формализм Р.
2. Не обязательно требовать, чтобы в формализме Р содержались цифры. Вместо цифр в Р могут фигурировать какие-нибудь более сложные термы (быть может, содержащие и переменные), относительно которых нужно только предположить, что имеется некоторое отображение, устанавливающее взаимно однозначное соответствие между этими термами и цифрами; эти термы можно будет также использовать вместо цифр в качестве номеров выражений из Р в нашей нумерации. 3. Нет необходимости требовать, чтобы каждая рекурсивная функция была изобразима в формализме Р. Достаточно потребовать, чтобы в Р была и р едет а в и ма в некотором смысле одна такая функция при условии, что формализм Р по меньшей мере содержит кваптор всеобщности вместе с соответствующим образом обобщенным понятием ф о р м у л ы, а также связанные с квантором всеобщности способы умозаключения, формализованные каким-то образом.
Характер требуемой при этом представимости проще всего выяснить на примере разобранного нами случая, проанализировав роль, которую при выводе данного противоречия начинает играть предположение об изобразимости в Р рекурсивных функций. Фактически это предположение использовалось в выводе только один раз, а именно когда мы изображали одну рекурсивную функцию с помощью терма 6(л, 1).
Рассматриваемая при этом функция — мы обозначим ее БЬ(л, 1) †сопоставля номеру 1 какого-либо выражения К и цифре 1 номер БЬ (1, 1) выражения, получающегося из Й в результате замены переменной а цифрой 1. Для формализации рассматриваемой антиномии вместо того, чтобы изображать функцию БЬ(й, 1) термом 6(/г, 1), нам достаточно изобразить трехместиый предикат ЗЬ(й, 1)=т такой формулой О (Й, 1, 1и) из Р, не содержащей отличных от й, 1 и и свободных переменных, чтобы для произвольных цифр 1, 1 и ш, удовлетворяющи х равенству ЗЬ(1, 1)=В1, в Р была выводима формула Я(1, 1, п1) и чтобы, кроме того, в Р выводилась формула (1) тухану'уиди(Я(х, у, и)ЬЯ(х, у, О) — «и=п).
Действительно, пусть р — номер формулы АХ((О(а, а, Х)-«) 1О1(Х)), а Ч вЂ” цифра, являющаяся значением БЬ(р, р). Тогда 4 является номером формулы 'т'х(4О(р, р, х) — «) Ю1(х)). Т как эта формула не содержит свободных переменных, то, ак к м лы согласно предположению г), в Р выводимы форму (2) и(ч)-«чх(Я(р, р, х)-«)%(х)) (3) Вх (Я (р, Р, х) - ~ 3)1 (х)) «У1 (4). Далее, так как справедливо равенство БЬ(р, р)=4, то в Р выводима формула (4) Я (р, р, ч). Нз формул (2) и (4) можно полУчить формулу 3)1(1))-+. ) В)1(4) а из нее — формулу ') 3)1 (я) Эта формула, взятая вместе с формулами (4) и (1), на основании общей аксиомы равенства дает формулу Чх(Я(р, р, х)-«) 3)1(х)), которая в сочетании с (3) дает формулу 3~(ч) так что мы снова получаем противоречие.
3 мечанне. В этом рассуждении мы пользовались предположением, что формализм Р удовлетворяет условию в). Однак амеч о совершенно аналогичным образом можно рассуждать и в том случае, когда формализм Р не содержит свободных переменных. В этом случае выражение Я(й, 1, и) не будет принадлежать фор- выход зд рдмки тиоиин докдздтильств гглницы изоииязнмости и выводимости 329 й и !гл. ч мализму Р, а будет играть роль именной формы. Зато для произвольных '1, 1 и !и выражение Я(1, 1, !и), а также выражение (1) будут формулами из Р. Переменная а будет учтена в нумерации выражений, входящих в Р, так что метаматематическнй смысл функции зЬ(й, 1) сохранится и выражение Чх(Я(а, а, х)-~ 1У1(х)) получит некоторый номер, хотя оно и не будет принадлежать формализму Р.
Это рассуждение равным образом может быть распространено и на случай такого формализма Р, в котором роль цифр играют какие-нибудь другие, более сложным образом устроенные термы. На основе всех наших замечаний относительно возможности ослабления предположений а) — г) мы могли бы сформулировать какую-нибудь модифицированную версию этих предположений. Однако такая версия, по-видимому, была бы довольно громоздкой и снова содержала бы ненужные ограничения на формализм Р. Окончательная общность в этом напранленин едва ли может быть достигнута. Но эти замечания о возможности ослабления наших предположений показывают, что обстоятельство, которое было отмечено в связи о формализацией антиномии лжеца и для которого достаточно предположений а), б) и в), имеет место и в формализмах гораздо более общей структуры.
Это обстоятельство состоит в том, что в формализмах указанного типа при условии нх непротиворечивости понятие истинности данного высказывания не может быть изображено 'способом, соответствующим основным формальным свойствам этого понятия, Тот факт, что такая невозможность имеет место во всех арифметически достаточно выразительных формализмах, а также в достаточно формально описанных дедуктивных формализмах, удовлетворяющих определенным, весьма общим условиям, был обнаружен Альфредом Тарским в его работе «Рег Я!аЬгЬе!1зЬедг)11 !п йеп 1огша!)з!ег1еп ЗргасЬеп» и высказан в виде теоремы'), причем Тарский подчеркнул, что' аналогичная ситуация имеет место и по отношению к другим семантическим понятиям, отличным от понятия истинности данного высказывания.
И действительно, при условиях, аналогичных указанным выше, формально- дедуктивное изображение различных понятий, относящихся к связи между обозначением и обозначаемым, также оказывается невозможным. ') Укзззниое сочинение Тарского сначало появилось на польском языке в Тгзчзцх йе 1з зос. йез зс!евсея ... йе Увгяэч1е в Варшаве в 1933 г. после анонса: Рег ъЧзйгйецзьеямп !и йеп зргвсйеп йег йейийнчеп Р1з»1р!!вен — Айад. й, %1зэеозсьь дУ!ео, Аизе!Кег, !932, 69. Немецкий перевод этого сочинения оцубликовзн, с послесловием, в 3!цо!з рш1озорнйсв, 1935, 1, Замечательным фактом этого рода является невозможность изобразить понятие <значения выражения, определяющего некоторое число», которая также может быть установлена при весьма общих предположениях относительно рассматриваемого дедуктивного формализма.
Мы даже могли бы извлечь ее непосредственно из нашего предыдущего результата, касающегося формализации понятия истинного высказывания, если бы наложили на рассматриваемые формализмы некоторое дополнительное условие. При этом мы, как и прежде, ограничимся рассмотрением таких дедуктивных формализмов, которые удовлетворяют предположениям а), б) и в). Добавляемое к этим предположениям дополнительное условие заключается в том, что мы требуем, чтобы для каждой формулы Я формализма Р, не содержащей свободных переменных„можно было указать такой терм Ь(Я) без свободных переменных, что формула Я переводима в равенство ()(Я) =О, причем это сопоставление формуле Я терма () (Я) должно производиться таким образом, чтобы номер терма 1) (Я) был рекурсивной функцией номера формулы Я. Это дополнительное предположение, которое мы обозначим посредством в,), выполняется всякий раз, когда формализм Р содержит кванторы, ь-символ и относящиеся к ннм правила и формулы (илн схемы формул).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
