§ 4. Вопросы систематики

1. Понятия t-тождественной формулы и формулы, тождественной в конечном; дедуктивная замкнутость совокупности t-тождественных формул; непротиворечивость исчисления предикатов; вопросы полноты.

Обилие представленных здесь формул не требует для своего запоминания никаких особых усилий со

стороны памяти, поскольку эти формулы выражают всего лишь ту мысль, что с обобщенными конъюнкциями и дизъюнкциями, которые изображаются кванторами всеобщности и существования, можно обращаться в точности так же, как и с обычными конъюнкциями и дизъюнкциями.

Эту мысль можно сделать особенно отчетливой, если отнести формулы (1) — (20) к индивидной области, состоящей только из двух индивидов (мы обозначим их символами 1 и 2).

Будем вместо и т. д. писать

а вместо

Тогда формулы (1) — (20) перейдут, как легко убедиться, в тож дественные формулы исчисления высказываний, в которых будут играть роль независимых формульных переменных. Например, формула (2) перейдет в формулу

которая соответствует правилу замены для отрицания; формула (5) перейдет в

которая является одной из формул закона дистрибутивности; формула (7) перейдет в

формула (11) в

а формула (14) в

Этот факт не должен нас удивлять. Ведь формулируя нашу систему основных правил, мы выбрали формулы и схемы для кванторов всеобщности и существования как раз таким образом, чтобы они получались из формул и правил для конъюнкции и дизъюнкции путем перехода от конечного числа членов к некоторому продолжению на произвольную, конечную или бесконечную, индивидную область. Поэтому, если мы применим формулы исчисления предикатов к индивидной области с заданным конечным число индивидов, то эффект произведенного предельного перехода ликвидируется и мы снова вернемся к формулам исчисления высказываний.

Это рассуждение, вместе с его итогом, мы хотели бы сформулировать более точно. С этой целью мы введем понятие 1-тождественной формулы для конечного, отличного от нуля числа

Формулу исчисления предикатов мы будем называть -тож-дественной, если она, будучи естественным образом проинтерпретирована в индивидной области, состоящей из объектов, при любой подстановке вместо входящих в нее свободных индивидных переменных (если таковые имеются) переходит в тождественную формулу исчисления высказываний.

Эта интерпретация предикатных формул осуществляется следующим образом. Рассмотрим -элементную индивидную область, элементы которой обозначены цифрами

Выражение будем понимать как конъюнкцию

а — как дизъюнкцию

Результирующая формула должна быть тождественной в том смысле, что всевозможные элементарные формулы, встречающиеся в ней, такие, например, как

должны рассматриваться как независимые формульные переменные. При подстановке вместо свободных индивидных переменных в качестве их допустимых значений должны рассматриваться только индивиды

в случае, если формула содержит только связанные индивидные переменные, никакой подстановки производить не требуется. Рассмотрим в качестве примера формулу

Она является 1-тождественной, но не 2-тождественной. Действительно, если рассмотреть эту формулу в одноэлементной индивидной области, то получится формула

которая является тождественно истинной, в то время как в двухэлементной индивидной области получаются две формулы:

и

которые обе не являются тождественно истинными. Точно таким же образом мы убеждаемся, что формула

является 1-тождественной и 2-тождественной, но не 3-тождественной, и что формула

является 1-, 2- и 3-тождественной, но не -тождественной.

Следуя закону построения этих формул, можно для всякого числа I указать такую формулу, которая будет 1-тождественной для всякого числа I от 1 до включительно, но -тождественной не будет.

Таким образом, мы видим, что для каждого числа имеются такие формулы, которые являются -тождественными, но не -тождественными. Но с другой стороны, мы легко можем убедиться, что всякая -тождественная формула является и -тождественной. Действительно, формула которая получается при интерпретации некоторой формулы в индивидной области

может быть построена на основе формулы получающейся при интерпретации в индивидной облаети

следующим образом: мы всюду вместо аргумента ! проставляем 1, а затем повторяющиеся конъюнктивные и дизъюнктивные члены сокращаем до одного. Если является -тождественной формулой, то будет тождественно принимать значение «истина», когда все входящие в нее элементарные формулы мы будем рассматривать как независимые формульные переменные. Замена аргумента аргументом 1 (например, замена посредством посредством и т. д.) равнозначна ряду подстановок вместо формульных переменных. В результате этих подстановок из тождественой формулы снова получится некоторая тождественная формула; вычеркивание повторяющихся членов также представляет собой допустимое преобразование. Поэтому формула тоже является тождественно истинной, а значит, является -тождественной формулой.

Таким образом, -тождественные формулы представляют собой собственную часть совокупности -тождествеппых формул.

Если какая-либо формула является -тождественной для любого числа то мы будем говорить, что она является тождественной в конечном.

Следует обратить внимание на то, что понятие формулы, тождественной в конечном, не дает нам в руки никакого критерия, с помощью которого мы могли бы для произвольной заданной формулы исчисления предикатов выяснить, является она тождественной в конечном или же нет.

Имеют место следующие утверждения:

Теорема 1. Всякая формула исчисления предикатов, выводимая в соответствии с нашими основными правилами, является тождественной в конечном.

Теорема 2. Совокупность -тождественных формул является дедуктивно замкнутой в том смысле, что при добавлении к исходным формулам исчисления предикатов новых -тождественных формул снова оказываются выводимыми только 1-тождествен-ные формулы.

Доказательство этих утверждений получается из рассмотрения системы наших основных правил путем установления следующих фактов:

а) Тождественные формулы исчисления высказываний, а также формулы (а) и т. е. все исходные формулы исчисления предикатов — являются тождественными в конечном.

б) Путем подстановки, в которой не участвуют предикатные и индивидные символы, из -тождественной формулы получается снова -тождественная.

в) Применение схем (а) и к -тождественным формулам снова дает формулы с тем же самым свойством.

г) Если обе формулы являются -тождествен-ными, то также является -тождественной.

Следует обратить внимание на то, что утверждения б), в) и г), поскольку они верны для произвольного числа останутся верными и в том случае, если мы в них вместо -тождественности будем говорить о тождественности в конечном.

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

другой. Это верно даже в следующей усиленной форме: пусть фиксированное конечное число; добавляя к исходным формулам произвольные -тождественные формулы, мы не сможем добиться того, чтобы выводимыми оказались две формулы Действительно, иначе одновременно оказались бы тождественными. Но отрицание любой -тождественной формулы в случае -элементной индивидной области тождественно принимает значение «ложь» и, следовательно, не может быть -тождественным.

Другое следствие касается тех формул исчисления предикатов, которые не содержат связанных переменных, т. е. формул, построенных с помощью связок исчисления высказываний из формульных переменных без аргументов или со свободными индивидными переменными в качестве аргументов.

Различные (т. е. различные по внешнему виду) элементарные формулы, из которых построена формула такого рода, мы будем называть компонентами этой формулы.

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

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

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

Формулы рассмотренного типа, обладающие указанным свойством, мы также будем называть тождественно истинными формулами.

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

каждая выводимая формула тождественна в конечном, но что каждая тождественная в конечном формула является также и выводимой.

Однако это справедливо лишь в отношении некоторой части исчисления предикатов, именно в отношении тех формул, у которых все элементарные подформулы имеют не более одного аргумента. Для этой части исчисления, которую мы будем называть «одноместным» исчислением предикатов, мы действительно докажем, что каждая тождественная в конечном формула является и выводимой.

Однако для всего исчисления предикатов в целом такая теорема места не имеет. Это обнаруживается при рассмотрении формул, выражающих определенные условия конечности, накладываемые на индивидную область. К одной из формул такого рода нас приводят уже обсуждавшиеся в гл. I формулы

Относительно этих формул мы установили, что в конечной индивидной области их невозможно одновременно выполнить посредством подстановки какого-либо конкретного двуместного предиката вместо переменной Этот результат свидетельствует о том, что следующая формула

которая представляет собой конъюнкцию трех указанных формул, будучи рассмотрена в конечной индивидной области, при любой подстановке какого-либо конкретного предиката вместо переменной принимает значение «ложь», или, другими словами, что ее отрицание является формулой, тождественной в конечном.

Если бы всякая тождественная в конечном формула была выводимой, то, в частности, выводимой была бы и формула

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

трех формул, входящих в систему

также ранее упоминавшуюся в гл. Формула также не может быть выполнена ни в какой конечной индивидной области путем подстановки какого-нибудь предиката вместо переменной ; другими словами, формула является тождественной в конечном. И все-таки в дальнейшем мы покажем, что выводимой эта формула не является.

Еще один пример формулы, обладающей рассмотренным свойством, дает следующая формула

относительно нее тоже можно показать, что она не может быть выполнена ни в какой конечной индивидной области подстановкой вместо переменной А какого-либо предиката, так что ее отрицание является тождественным в конечном. С другой стороны, формула не выводима в исчислении предикатов, а именно — ее невыводимость может быть установлена на основе невыводимости формулы Действительно, формула как мы покажем позже, может быть выведена из формулы и тем самым из невыводимости следует невыводимость

Однако мы можем здесь сделать и более сильное утверждение: как показал М. Вайсберг, можно задать бесконечную последовательность формул исчисления предикатов таких, что все они тождественны в конечном, однако ни одна из них не выводима из остальных средствами исчисления предикатов.

Результаты, показывающие необратимость теоремы 4, играют особенно важную роль в связи с вопросом о полноте исчисления предикатов.

Для одноместного исчисления предикатов вопрос о его полноте решается в утвердительном смысле теоремой о том, что всякая

формула, тождественная в конечном, одновременно является и выводимой.

Эта теорема, которую мы в дальнейшем еще должны будем доказать, представляет собой аналог теоремы о полноте дедуктивного исчисления высказываний, согласно которой всякая тождественная формула исчисления высказываний выводима из системы формул

Правда, мы здесь не имеем аналога теоремы о том, что при добавлении какой-либо невыводимой формулы к числу исходных выводимой становится уже любая формула. В самом деле, если мы к исходным формулам одноместного исчисления предикатов добавим, например, какую-либо 1-тождественную формулу, то в результате опять окажутся выводимыми только 1-тождественные — и, значит, не произвольные — формулы.