Гильберт, Бернайс - Основания математики. Логические исчисления и формализация арифметики (947375), страница 103
Текст из файла (страница 103)
Вследствие предъявляемых нами к определению редукции требований, редукция формулы без )-символов должна будет совпадать с самой этой формулой. Элементарная формула, содержащая хотя бы одно вхождение «-символа, представляет собой либо формульную переменную с аргументами, либо предикатный символ с аргументами. В обоих случаях эта элементаряая формула может быть записана в виде З»()у Я(А,), )Г 3(гг), гь(5е)). Эта запись должна пониматься таким образом, 'Ф 17 что «Я(»ь), ) й)(р«), ..., ) й (т ) суть различные «-термы, внешние в этой элементарной формуле, т. е. не вложенные ни в какие другие )-термы. Такого рода внешний )-терм, входящий в элементарную формулу, не обязан быть непосредственным ь) Буква З) в виде исключения обозначает здесь пе формулу, а некоторую (петапатепатячесную) опграцню.
520 пОнятин «тОт, котОРын» и нгО устРАнимость [гл. Тш » «) УСТРАНИМОСТЬ ХАРАКТНРИСТИК («-СИМВОЛОВ) 524 аргументом формульной переменной или предикатного символа. Он может быть н аргументом какого-либо функционального анака. Далее, следует обратить внимание на то, что один и тот же )-терм может входить в элементарную формулу как в качестве внешнего терма, так и в качестве вложенного в какой-нибудь другой. Так, терм > Я(~>), который в рассматриваемой элементарной формуле встречается в качестве внешнего, может например, одновременно быть вложенным в > 3(~,); такое вхождение пе будет учитываться в нашей записи элементарной формулы.
О другой стороны, один и тот же >-терм в данной алементарной формуле может несколько раз встречаться В качестве внешнего герма; в этом случае он будет перечисляться в нашей записи только один раз. Так, )(>(с) может иметь вид с( с, и тогда )р(>„Я(х)) будет представлять собой элементарную формулу >„Я(х) (с„Я(х). Кроме того, следует подчеркнуть, что равными мы будем считать и такие >-термы, которые отличаются друг от друга обозначением связанных переменных; таким образом, в нашем списке >-тернов Я(г>), ..., ег И(г ) не должно~ ~быть двух таких, которые гг отличались бы друг от друга тольке обоаначением связанных переменных. Так, элементарная формула )„21(х) ( >„Я(у) должна записываться в виде Ф(.Я(х)).
а не в виде Ф(~.Я(х), >„Я(у)). Редукцией формулы (*) Ф ( г, Я И>), г, й) (~,), ..., „й (.,)) мы назовем формулу 1(Ь .. ° 'ФКе (Я (Я (М А д«Я (й (К,)) 'Р (а Ь,И. Правда, этим определением редукция формулы (») непосредственно еще не указывается, поскольку в ней в качестве составных частей фигурируют редукции формул Я(с,),, й(с,). Но ати формулы содержат меньше )-символов, чем исходная элементарная формула, и, в силу перестановочности логических операций с оператором редукции, редукции этих формул оказываются построенными иа редукций элементарных формул, которые содержат меньше >-символов, чем рассматриваемая нами исходная элементарная формула.
Таким образом, для нахождения редукций элементарных формул мы получаем некоторую рекурсивную процедуру, выполнение которой ааканчивается за число шагов, не превосходящее числа >-символов, содержащихся в этой элементарной формуле. Обрыв процесса происходит тогда, когда мы доходим до элементарных формул без >-символов, редукции которых, как мы знаем, совпадают с ними самими. В итоге мы получаем некоторое определение редукции формулы, удовлетворяющее обоим поставленным требованиям: 1) редукция любой формулы не содержит )-символов и 2) редукция формулы, не содержащей >-символов, совпадает с ней самой. Кроме того, в силу данного нами определения, оператор редукции перестановочен с логическими операциями.
А отсюда уже получается, что логическая структура редукции произвольной формулы совпадает со структурой самой этой формулы. Оператор редукции устроен, кроме того, таким образом, что всякая свободная переменная, являющаяся параметром какой-либо формулы, остается параметром и ее редукции. Из этих замечаний мы можем сделать следующие выводы: ни одна из собственных аксиом не претерпевает в результате редуцирования никаких изменений; редукция формулы, истинной в логике высказываний, также истинна в логике высказываний; редукция формулы одного из следующих видов: ЧхЯ (х)' — >-Я (а), Я (а)-эЗхЯ (х), а=Ь-э(Я (а) — в-Я (Ь)), Я (О) д«)ех (Я (х) — ~ Я (х')) -» Я (а) сама является формулой такого >ке вида. Что касается схемы закл>очения, схем (а) и (р) и правила подстановки вместо свободных индивидных переменных термов, не содержащих >-символов, то при каждом применении любого из этих правил замена участвующих в этом применении формул их редукциями сохраняет вид применяемой схемы; таким обрааом, из редукции посылки (соответственно из редукций посылок) редукция результирующей формулы выводится по той же самой схеме.
Кроме того, редукции двух формул, получающихся друг из друга переименованием связанных переменных, тоже путем переименования могут быть переведены друг в друга. Поэтому, в соответствии с нашим планом доказательства устранимости >-символов, остается только показать, что редукция формулы, полученной по схеме Лхуу (я (у) у = х) -». (>ух (я (х) -«- й) (х)) -». 5 (>„я (х))), выводима без использования >-символов. Ыы установим несколько больше, а именно — выводимость без использования >-символов редукций более сильных формул, получающихся по схеме Лхасу (Я (у) у = х) — » (Чх (Я (х) — » З (х)) З (> Я (х)), 522 апонятнк етот, котОРын2 и вго устРАннмость ~гл. чп2 т.е.
выводимость без использования 2-символов формул вида 1Ж, Я, 3) Зх'Фу (Ж (Я (у)) — у = х) -« (чх (Ж (Я (х)) -«Ж (Й (х))) Щ(3 (2, Я (х)))), из которых уже могут быть выведены редукции рассматриваемых нами формул. 4. Доказательство. Доказательство б, дет вестись индукцией по числу логических знаков в формуле 3(с) — с переменной с, не встречающейся ни в Я(х), ни в 3(х) (Аименная переменнаяз),— причем к логическим знакам мы причисляем здесь и 2-символы. Если рассматриваемое число равно нулю, то 3(с) является элементарной формулой без 2-символов; тогда, по определению редукции, Ж(3(~„9((х))) представляет собой формулу чх(Ж(Я(х)) — « 3(х)), а Ж(3(с)) совпадает с 3(с). Следовательно, (Ж, Я, 3) является формулой, истинной в логике высказываний.
Пусть теперь 3(с) — элементарная формула, в которую входит по меньшей мере один 2-символ. Рассмотрим сначала случай, когда переменная с не встречается ни в одном из входящих в 3(с) 2-тернов. Тогда в формуле 3(~„Я(х)) терм 2„Я(х) является внешним 2-терном. Кроме того, мы предположим, что.терм 2,Я (х) не входит в Й (с). Тогда формула 3 (22Я (х)) будет иметь вид 'ЗА(~ Я(х), 2„,51(х,), ..., ~„52(х1)), где дз (с, см ..., с~) — элементарная формула без 2-символов. Ее редукцией будет формула чхчх~ ...
~х~(Ж(Я (х)) & Ж(5,(х,)) &... &Ж(5~(х~))-« т (Х х!1 ° ° ° ! Х~)) ° Эта редукция может быть преобразована в формулу пх(Ж(Я(х))-«чх2 ... ух~(Ж(51(х1)) & ... & Ж (51(х~))— '41 (х,х„..., х~))); но эта последняя и есть в точности Чх(Ж(Я(х))- Ж(3(х))). Тем самым эквивалентность чх(Ж(Я(х))«Ж(3(х))) Ж(3(~„Я(х))) и тем более формула (Ж, Я, 3) оказываются выводимыми без использования 2-символов. В рассмотренных до сил пор случаях посылка формулы (Ж, Я, 3) в процессе вывода атой формулы не играла никакой роли; мы не пользовались и индуктивным предположением о том, з а] устРАнимость хАРАктнРистнк а-символов) 523 что для всякой формулы 32 с числом логических знаков, меньшим, чем у формулы Й, без использования 2-символов выводима формула (Ж, Я, 32). В дальнейших рассуждениях, напротив, и то, и другое найдет себе самое существенное применение.
В случае элементарной формулы Й (с) мы должны еще рассмотреть тот случай, когда один из входящих в Й (с) 2-термов совпадает (быть может, с точностью до обозначений связанных пере22енных) с термом 2„Я (х), а также случай, когда переменная с входит внутрь одного или нескольких 2-тернов из числа 2„5~ (х~) 2$ (~ = 1, ..., 2), что мы будем в этом случае отражать в записи 2„5; (хп с). Обе указанные возможности могут реализоваться и одновременно. Но случай, когда какой-либо из термов 2„5~ (хо с) совпадает с 2 Я (х), не входит в рассмотрение.
Действительно, переменная с используется в записи Й (с) только в качестве именной переменной; и эта именная переменная должна выбираться отличной от всех остальных, в частности от переменных, входящих В Я (х). Допустим сначала, что реализуется только первая из указанных возможностей. тогда, если 2;,5, (х,), ..., 2,~5~ (х~)— полный список различных (с точностью до обозначений связанных переменных) внешних 2-тернов формулы 3(с), то мы можем считать, что 5, (х,) совпадает с Я (х).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
