Гильберт, Бернайс - Основания математики. Логические исчисления и формализация арифметики (947375), страница 87
Текст из файла (страница 87)
Допустим, что к данному формализму мы добавляем функцию одного или нескольких аргументов путем введения специального фуккциоиального знака ) (а,..., Й) вместе с относящимися к нему формулами, поаволяющими проводить формализованное вычисление значений этой функции для цифр, являющихся значениями аргументов. Мы будем говорить, что функция [ (а, ..., Й) п р е де т а в и м а 1) в рассматриваемом нами формалиаме, если авен- ство р е- 435 ПРВдставимость РвкуРсивных Функций 1гл. Уп РВКУРСИВНЫВ ОПРВДВЛВНИЯ 434 в рассматриваемом формализме оказывается выводимой формула Я(а, ...,1, 1), если 1 совпадает со значением 1(а,..., 2), и формула ~Я(а, ...,$,1) в противном случае.
При этом представляющая формула Я(а,....,я,() моясет быть выбрана таким образом, чтобы кроме а,..., )с, в ней не встречалось никаких свободных переменных. В самом деле, в представляющей формуле, содержащей другие свободные переменные, эти переменные без нарушения указанных свойств формулы можно устранить посредством соответствующих подстановок. Мы будем теперь говорить, что присоединение данной функции является существенным расширением нашего формализма, если эта функция в рассматриваемом формализме на предсвсивилса. 2.
Доказательство того, что сумма и разность не представимы в формализме системы (В); рекурсивные равенства для сложения как аксиомы; система (В). Мы сейчас покажем, что уже присоединение к формализму системы (В) функции а + Ь, равно как и присоединение функции а — ' Ь, ведет к существенному расширению этого формализма. Рассмотрим произвольную формулу из формализма системы (В) с единственной переменной а; эта формула средствами системы (В) переводима в ее редукцию, а зта последняя может быть переведена в такую диэъюнктивную нормальную форму, в которой не встречается отрицаний, так что каждый ее дизъюнктивный член представляет собой конъюнкцию равенств и неравенств. Равенства отдельно можно не рассматривать, так как любое равенство а=Ь переводимо в конъюнкцию неравенств а(Ь' & Ь(а'.
Для неравенства, не содержащего никаких переменных, кроме а, имеются следующие возможности: Либо оно является пумерическим; тогда оно истинно или ложно. Либо оно имеет вид а(1) ( а(1); тогда оно переводимо в нумерическое неравенство 011) < 011). Либо оно имеет вид а(1) ( 0(1); тогда, если 1~~1, оно переводимо в ложное неравенство 0 ( О„. если ясе г ( 1, оно переводимо в некоторое неравенство а ( 012); неравенство такого рода мы будем называть в е р х н е и о ц е н кой для а. Либо оно имеет внд 01" ( а(1); тогда, если г (1, оно переводимо в истинное неравенство 0<0', если же $)~1, то оно переводимо в некоторое неравенство 0(с) (а; неравенство такого рода мы будем называть н и ж н е й о ц е нкой для а.
В с те н оответствии с этим для формулы в целом получается ла ьлибо в рнатива, заключающаяся в том, что эта формула переводи о ма бо в истинную, либо в ложную нумерическую формулу, либо же в такую днзъюпктивную нормальную форму, у которой кажды" и й д зъюнктивныи член представляет собой конъюнкцию верхних и нижних оценок для а. Рассмотрим последний из перечисленных случаев. Здесь мыслимы следующие две воэможности. Либо верхних оценок для а нет по крайней мере в одном из дизъюнктнвных членов; тогда и и ой подстановке цифры, большей чем определенная цифра 012), при эта формула переходит в некоторую истинную формулу. Либо ясв верхняя оценка для а встречается в каждом диаъюнктивномчлене; тогда при любой подстановке какой-либо цифры, большей чем определенная цифра 012), эта формула переходит в некоторую ложТаким образом, во всех случаях паша формула обладает тем свойством, что либо она становится истинной для всех достаточно болыпих подставляемых вместо а цифр, либо же для всех достаточно больших цифр она становится ложной.
28 ° пгедстАВимость РекуРсиВных Функции РЕКУРСИВНЫЕ ОПРЕДЕЛЕНИЯ [гл, уп Теперь для исходной формулы получается, что либо она сама выводима для всех достаточно больших значений а, либо для всех достаточно больших значений а выводимо ее отрицание. При этом указанное свойство присуще любой формуле, принадлежащей формализму системы (В) и содержащей а в качестве единственной свободной переменной. Теперь на основе этого факта легко показать, что фуикции а + Ь и а — ' Ь не представимы в формализме системы (В).
В самом деле, допустим, что равенство а+Ь=с представимо некоторой формулой Я (а, Ь, с) формализма системы (В). Тогда эту формулу — как мы уже заметили — можно выбрать таким образом, чтобы она не содержала никаких свободных переменных, кроме а, Ь и с, а также чтобы в ней не встречалась связанная переменная х, так как в случае надобности эту перемеиную всегда можно переименовать в какую-нибудь другую. Тогда формула ЭхЯ (х, х, а) принадлежит формализму системы (В) и содержит единственную свободную перемеиную а.
Поэтому, согласно доказанной нами теореме, либо для всех достаточно', больших цифр Ь, т. е. начиная с некоторой цифры 0(1), средствами системы (В) выводима формула лхЯ(х, х, Ь) либо для всех достаточно больших Ь выводимо отрицание этой формулы, а значит, и формула 7х~ 1Я(х,х, Ь). Таким образом, если мы выберем цифру 1 достаточно большой, то для цифры Ь, являющейся значением 1 + 1, средствами системы (В) будут выводимы либо обе формулы ЗхЯ(х, х, Ь), ЗхЯ(х, х, Ь'), либо обе формулы Чх 1 Я (х х, Ь), ~Ух", 1 Я (х, х, Ь').
В первом случае, вследствие выводимости формулы ЧхЯ(х, х, Ь'), потеореме о частичной редукциит)мынашлибы цифру 1, такую что средствами системы (В) была бы выводима формула Я(1 1 Ь'» во втором случае вследствие выводимости формулы ухЧЯ(х,х, Ь), была бы выводимой формула -1 Я ($, 1, Ь). Но ни формула Я (1 1 3') ни формула 1Я(1,$, Ь) не могут быть выведены средствами системы (В). Действительно, так как Ь является значением 1 + 1, то ввиду того, что формула Я (а, Ь, с) представляет равенство а+Ь=с, формула Я(1, 1, Ь) Я(" 1 Ь) выводкмости Я(1,1, Ь) системы (В) была бы выводима некоторая формула отрицанием, между тем как мы ранее показали, чте непротиворечива.
и в случае средствами вместе с ее система (В) ') См. с. ЗОН должна быть выводимой средствами системы (В). Из того же самоге свойства формулы Я (а, Ь, с) следует, что и формула 1Я(1,1, Ь') выводима, так как при 1~($ Ь' больше значеиия 1 + 1, а в случае 1.> $ оно меньше этого значения и, значит, в любом случае отлично от значения 1+1. Таким образом, и в случае выводи- мости НРедстьвимость РекуРсиВных Функций РЕКУРСИВНЫЕ ОПРЕДЕЛЕНИЯ азз [гл. Рн Тот факт, что равенство а — '6=с также не представимо в формализме системы (В) пикакой формулой (В(а, Ь, с), получается совершенно аналогичным образом, если рассмотреть формулу Зх )В (а, х, х). Для того чтобы убедиться в этом, нам не нунсио снова повторять проведенное рассуждение, а достаточно лишь заметить, что справедливость равенства согласно определению значения Ь вЂ” ' с, равносильна справедливости равенства Р+6 = Ь.
Тем самым действительно показано, что ни одна иа функций а + Ь и а — ' Ь не представима в формализме системы (В). Отсюда, в частности, получается, что система (С), относительно которой мы показали, что ее средствами могут быть выведены все формулы системы (В), являетсн более богатой, чем система (В), т. е. формализм системы (С) является существенным рас1пирепнем формализма системы (В). Системе (С), в которой в качестве аксиом фигурируют рекурсивные равенства для а — ' д, мы сопоставим следующую, основанную на рекурсивных равенствах для а + Ь систему аксиом: а = Ь -э (А (а) — ~ А (Ь)), а ~0, а'=Ь'-1-а=Ь, а+О=а, а+Ь' = (а+Ь)', А (0) Ас у х (А (х) -+ А (х')) -ь. А (а) .
В этой системе кроме аксиомы равенства ()з) (аксиома ()1) окааывается излишней ввиду наличия аксиомы а + О = а) имеются обе пеановские аксиомы (Р,) н (Рз), которые в системе (С) были заменены рекурсивными равенствами для 6 (и) и формулой 0' Ф О, а также рекурсивные равенства для а + Ь и аксиома индукции. К этому мы добавим явное определение выражения а с Ь, которое вводится здесь формулой а(Ь Лх(х~Обса+х= Ь).
Основываясь на этом определении, мы мохсем вывести фор- мулы ас а', а(Ь-ьа'=Ь~/а'(Ь, 1(а(а), а ( Ь й Ь ( с -ь. а С с, причем 1) первая из них выводится непосредственно с помощью формулы (Р,), вторая — с помощью (выводимых при помощи аксиомы индукции) формул а~Π— 1-Зх(х' =а), а'+Ь=а+Ь', третья — с помощью формулы а+ Ь = а — ь Ь = О, выводимой из формул О+ а = а, а'+ Ь = а+Ь' и (Р,) индукцией по а, а четвертая — с помощью формул а + (Ь + с) = (а + Ь) + с Ь чь 0 -ь а + Ь ~ О, последняя из которых может быть получена из формул а ~ 0 -+.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
