Гильберт, Бернайс - Основания математики. Логические исчисления и формализация арифметики (947375), страница 34

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 34)

Точно таким же образом мы убеждаемся, что формула ЧхА(х) ~/)/х(~А(х) ~/ В(х)) ~/ Чх'( 1А(х) ~/ 1В(х)) является 1-тождественной и 2-тождественной, но не 3-тождествен- ной, и что формула ЧхА (х) ~/ 7х ( 3А (х) ~/ В(х)) ~/ Чх ( 1А (х) ~/ 1В(х) ~/ С (х)) ~/ Чх ( 1А (х) ~/ '1В (х) ~/ |С (х)) является 1-, 2- и З-тождественной, но не 4-тождественной. Следуя закону построения этих формул, можно для всякого числа 1 указать такую формулу, которая будет 1-тождественной для всякого числа 1 от 1 до 1 включительно, но (1 + 1)-тождественной не будет. Таким образом, мы видим, что для каждого числа 1 имеются такие формулы, которые являются 1-тождественными, но не (1+ 1)-тождественными. Но с другой стороны, мы легко можем убедиться, что всякая (1 + 1)-тождественная формула является и 1-тождественной. Действительно, формула Я', которая получается при интерпретации некоторой формулы Я в индивидной области 1,2, ...,1, может быть построена на основе формулы Я", получающейся при интерпретации Я в индивидной области 1,2,...,1+1, следующим образом: мы всюду вместо аргумента 1 + 1 проставляем 1, а затем повторяющиеся конъюнктивные и дизъюнктивные члены сокращаем до одного.

Если Я является (1 + 1)-тождественной формулой, то Я" будет тождественно принимать значение «истиная, когда все входящие в нее элементарные формулы мы будем рассматривать как независимые формульные переменные. Замена аргумента 1 + 1 аргументом 1 (например, замена А (1 + 1) посредством А (1), В (2, 1+ 1) посредством В (2, 1) и т. д.) равнозначна ряду подстановок вместо формульных переменных.

В реаультате этих подстановок из тождественой формулы Я снова получится некоторая тождественная формула; вычеркивание повторяющихся членов также представляет собой допустимое преобразование. Поэтому формула Я' тоже является тождественно истинной, а значит, Я является 1-тождественной формулой. 1гл. гч ВОпРОсы систнмАтики исчислипии пркдикАтОВ Таким образом, (1 + 1)-тождественные формулы представляют собой собственную часть совокупности г-тождественных формул.

Если какая-либо формула является 1-тождественной для любого числа г, то мы будем говорить, что она является тождественной в конечном. Следует обратить внимание на то, что понятие формулы, тождественной в конечном, не дает нам в руки никакого критерия, с помощью которого мы могли бы для произвольной заданной формулы исчисления преднкатов выяснить, является она тождественной в конечном или же нет. Имеют место следующие утверждения: Т е о р е м а г. Всякая формула исчисления предикатов, выводим я е соответствии с нашими основными правилами, является тождественной в конечном.

Т е о р е м а 2. Совокупность ~-тождественн х формул является дедуктивно замкнутой в том смысле, что при добавлении к исходным формулам исчисления предикатое новых г-тождественных формул снова оказываются выводимыми только г-тождественные формулы г). Доказательство этих утверждений получается из рассмотрения системы наших основных правил путем установления следующих фактов: а) Тождественные формулы исчисления высказываний, а также формулы (а) и (Ь) — т. е. все исходные формулы исчисления предикатов — являются тождественными в конечном.

б) Путем подстановки, в которой не участвуют предикатные и индивидные символы, из г-тождественной формулы получается снова 1-тождественная. в) Применение схем (а) и (р) к г-тождественным формулам снова дает формулы с тем же самым свойством. г) Если обе формулы б и (Б-ь Я: являются г-тождественными, то Й также является г-тождественной. Следует обратить внимание на то, что утверждения б), в) и г), поскольку они верны для произвольного числа 1, останутся верными и в том луч в том случае если мы в них вместо 1-тоягдественности будем говорить о тождественности в конечном.

В качестве специального следствия из теорем 1 и 2 вытекает, что с помощь с помощью наших основных правил невозмолсно вывести никакие две формулы Я и) Я, из которых одна является отрицанием ') Эта теорема к»давно получила существенное дополнение. Вайсбсрв 'йг а 1 и Ь е г я М. 1)пгегвпсЬппуеп йЬег г)еп гоп)сг)спея)са1йй) Иг спй11спе пд)ч)да«пьесе)сйе.— Ма1Ь. Апп., 1933, 108, № 2) показал, что пук лобаввек х дкым формулам исчисления предккатов любой 1-тождеств«якой, ио не (1+ 1)-тожксствекной формулы выволкмыык оказываются уж 1-тождествеккыс формулы.

другой. Зто верно даже в следующей усиленной форме: пусть г— фиксированное конечное число; добавляя к исходным формулам произвольные 1-тождественные формулы, мы нв сможем добиться того, чтобы выводимыми оказались две формулы Я и ~ Я. Действительно, иначе Я и ) Я одновременно оказались бы 1- тождественными. Но отрицание любой $-тождественной формулы в случае 2-элементной индивидной области тождественно принимает значение «ложь» и, следовательно, не может быть г-тождественным. Другое следствие касается тех формул исчисления предикатов, которые не содержат связанных переменных, т. е. формул, построенных с помощью связок исчисления высказываний из формульных переменных без аргументов или со свободными иидивидными переменными в качестве аргументов. Различные (т. е.

различные по внешнему виду) элементарные формулы, из которых построена формула такого рода, мы будем называть к о м и о н е н т а м и этой формулы. Если формула этого типа выводима в исчислении предикатов, то она должна быть г-тонсдественной для любого числа г. Возьмем в качестве г число различных входящих в Я индивидных переменных и заменим в какой-либо последовательности эти индивидные переменные цифрами 1, 2, ..., г, а затем возникшие в результате этой замены различные элементарные формулы заменим различными формульными переменными.

Тогда в результате этих действий формула Я перейдет в тогкдественную формулу. Но этот процесс сводится к тому, что каждая из компонент формулы Я замещается некоторой формульной переменной (без аргументов). Значит, при этой замене Я должна перейти в тождественную формулу. С другой стороны, это условие является и достаточным для выводимости Я; в самом деле, оно выраягает тот факт, что Я получается в результате подстановки в тождественную формулу исчисления высказываний. Таким образом, мы установили, что формула исчисления предикатов, не содержащая кванторов, выводима в исчислении предикатов тогда и только тогда, когда она может быть получена подстановкой из какой-либо тождественной формулы, а это в свою очередь имеет место тогда и только тогда, когда эта формула при аамене ве компонент различными формульными переменными без аргументов переходит в тождественнуто формулу.

Формулы рассмотренного типа, обладающие указанным свойством, мы также будем называть тождественно истинными формулами. Из теоремы 2 мы можем, кроме того, заключить, что совокупность всех формул, тождественных в конечном, является дедуктивно аамкнутой. Можно было бы думать, что эта совокупность совпадает с совокупностью выводимых формул, т. е. что не только 11 д. Гяльверт, П.

веря«а« 1гл. гч ВопРОсы систематики 163 исчисление ИРедикатов 162 " ая выводимая формула тождественна в конечном, но что каждая фо м ла является также каждая тождественная в конечном формула я и выводимой. то ой части Однако это справедливо лишь в отношении некоторой исчисления преднкатов, именно в отно тн шенин тех формул, у кото- рых се в элементарные подформулы имеют не более одного аргуменмы б ем называть та. Для этой части исчисления, которую мы уд «одноместным» исчислением предикатое, д " мы ействительно дока- жем, что каждая тождественная в конечном формула является ы и выводимои ).

тео ема сего исчисления предикатов в целом такая теор Однако для вс г места пе имеет. Это обнаружинается при рассмотрении формул, чности, накладываемые выражающих определенные условия коне на инднвидную область. К одной из формул такого рода нас приво- дят уже обсуждавшиеся в гл. 1 формулы ') ч<х ~Л(х, х), )ух <уу 7г (Л (х, у) д< Л (у, г) — ь Л (х, г)), <4<х Зу Л (х, у) Относительно О этих формул мы устанонили, что в конечной индивидпос е ством ной области их невозмох<но одновременно выполнить поср д местного предиката подстановки какого-либо конкретного двум вместо переменнои " Л.

Этот реаультат свидетельствует о том, что следующая формула Я: <з<х ) Л(х, х)б< <эх'чу<ее(Л(х, у)счЛ(у, г)-ьЛ(х, г))<й <эх лу Л (х, у), е ставляет собой конъюнкцию трех укаэанных формул, которая представля б сти, и и любой б чи ассмотрена в конечной индивидной обла , р удучи ра иката вместо перемени одстановке какого-либо конкретного пред то ее нои Л принимает значение «ложь», или, другими словами, ч )Я является формулой, тождественной в конечном.

отрицание Я явл фо м ла была выво- Е бы всякая тождественная в конечном формул ели ы димой то, в частности, выводимой была бы и ф р у Я. Однако в дальнейшем мы покажем, что фор у 5 ф м ла 1 не может быть выведена с помощью наших основных правил. В зто уд мб ет состоять результат тат одного из наших первых доказательств непротиворечивости з). В точности так же, как с формулои )у, дел обстоит и с формулой ф " 76, где 6 представлнет собой конъюнкцию <) Сы. с.

243 л далее. з) См. с. 38. ') См. с. 262 и далее. трех формул, входящих в систему ЗхЬ<у ~Я(у,х), ))<х <ч у «и <е о (Я (х, и) «6 Л (у, и) с .с (о Ь<х ЛуЯ(х, у), также ранее упомннаншуюся в гл. 1. Формула 6 также не может быть выполнена нн в какой конечной нндивндной области путем подстановки какого-нибудь преднката вместо переменной Я; другими словами, формула )6 является тождественной в конечном. И все-таки в дальнейшем мы покажем, что выводимой зта формула 16 не является ').

Еще один пример формулы, обладающей рассмотренным свойством, дает следующая формула 10 з): <)<х 1А (х, х) <л <эх Зу )«г (А (х, у) <л (А (г, х) -ь А (г, у))); относительно нее тоже можно показать, что она не может быть выполнена пн н какой конечной ннднвндной области подстановкой вместо переменной А какого-лнбо преднката, так что ее отрицание )ф является тождественным в конечном. С другой стороны, формула )ф не выводима в исчислении предикатов, а именно — ее невыводимость может быть установлена на основе невыводимости формулы 7Я. Дейстнительно, формула )~~, как мы покажем позже з), может быть вынедена из формулы )ф, и тем самым иа невыводимости 3)) следует неныводимость 1ф.

Характеристики

Список файлов книги