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

у д этого вопроса мм вще верне»<ся прп двдук т оеввп логики предка«то» (см. гл. )У, с. 143 — (44). ермпп введен Готлобом <р еге. Т р~~, ракту редпкат как Фуп<щпю* мм р пап»пай с графиком этого првдпката.— пть его и о ег»пе 3 ГИЛЬб<РТ, П. Б<РНЛЙ< [гл, « ПРОБЛЕМА РАЗРЕШИМОСТИ ПРОБЛЕМА НЕПРОТИВОРЕЧИВОСТИ з" связываемые кванторами всеобщности или ущ с ествования пере- менные могут принимать лишь и значении, так что к Р ванто всеобщ- ности оказывается равнозначным некотор й о" и-членной конъюнк- ции, , а квантор существования — и-членной днзъюнкции.

омлы: Рассмотрим в качестве примера две следующие ф Р У '»хР (х, х) — » УхЭуР (х, у), )/хзу(Р(х, у) йР(у, х)-»х=у) (первая из них фигурировала в качестве примера общезначимой, а вторая — выполнимой формулы). Мы отнесем их к двухэлемент- ной индивидпой области. ами 1 и 2. Тогда Эти индивиды мы можем обозначить цифрами 1 и . огда в рассматриваемом нами примере 1 = 1, тельно, число различных систем предикатов будет равно 2'» = 2' = 16. Вместо»«хР (х, х) мы можем подставить Р(1, 1)б«Р(2, 2), а вместо ЧхлуР (х, у)— (Р (1, 1) ~/ Р (1, 2)) д«(Р (2, 1) ~/ Р (2, 2)). Тогда первая из рассматриваемых нами формул переплет в Р (1, 1) 8«Р (2, 2) — э.

(Р (1, 1) ~/ Р (1, 2)) д«(Р (2, 1) ~/ Р (2,2)). Эта импликация является истинной для тех предикатов Р, для которых Р (1, 1) д« Р (2, 2) является ложным, а также и для тех Р, для которых (Р (1, 1) ~/ Р (1, 2)) д«(Р (2, 1) ~/ Р (2, 2)) является истинным. . Теперь можно проверить, что для каждого нз 16 пробегов значений, получающихся приписыванием одного из значении «истина» ити «лоя ь» каждой из четырех возможных « пар значений переменных (1, 1), (1, 2), (2, 1), (2, 2), одно кэ этих двух „ ух условий выполняется, так что всякии раз все высказывание в цел .

в целом будет принимать значение «истина». ( Расом и име е проверка облегчается тем обстоятельством, сматриваемом примере пр остаточно асля становления истинности высказывания достаточно р что для у сматрнвать лишь значения Р (1, 1) и (, ).) чимость первои из н из наших формул с помощью рассмотренного нами способа может быть установлена путем прямои проверк . Вторая из упомянутых формул в случае двухэлементной индивидной области равнозначна конъюнкции (Р(1, 1) д«Р(1, 1)-+.1=1) д«(Р(2, 2)АР(2, 2)-»2 = 2) Ь (Р(1, 2) д«Р(2, 1)-+.1 = 2)8«(Р(2, 1) ЬР(1, 2)-+-2 = 1) ° Так как высказывания 1 = 1 и 2 = 2 являются истинными, то два первых конъюнктивных члена являются истинными всегда; оба последних члена истинны тогда и только тогда, когда Р (1, 2) А Р (2, 1) ложно.

Таким образом, чтобы выполнить интересующую нас формулу, мы должны взять такой предикат Р, у которого хотя бы одной нз пар (1, 2) или (2, 1) сопоставлено значение «ложью При всяком таком определении Р паше высказывание будет истинным. Следо- вательно, рассматриваемая формула действительно выполнима в двухэлементной иядивидной области. Эти примеры должны проиллюстрировать яам тот чисто комби- наторный характер, который проблема разрешимости носит в слу- чае заданного конечного числа индивидов.

Из комбинаторного характера этой проблемы, в частности, вытекает, что в случае конечного числа индивидов общезначимость формулы Я равно- сильна невыполнимости формулы ~5, а выполнимость формулы 1~~ равносильна тому, что формула $ яе является общезначи- мой. Действительно, 5 представляет собой истинное высказывание при тех наборах предикатов, при которых 1$ является ложным высказыванием и наоборот.

3. Метод построения модели. Теперь вернемся к нашему вопро- су о непротиворечивости камой-либо системы аксиом '). Как з рассмотренном выше примере, будем представлять себе эту систему записанной в символическом виде посредством одной- единствеяной формулы, Тогда вопрос о выполнимости этой формулы для заданной конечной индивидной области может быть решен при помощи г«еребора — по крайней мере в принципе Предположим теперь что нам удалось установить выполнимость этой формулы в какой- ннбудь конечной области индивидов; тогда мы тем самым получаем п доказательство непротиворечивости этой системы аксиом, при- чем доказательство, сопровождаемое иоеи»роением модели, с ука- занием конечной индивидной области вместе с набором пробегов значений предикатов, выполняющих эту формулу. Эта область в сочетании с предикатами образует модель, на которой можно "онкретным образом убедиться в выполнимости рассматриваемой аксиомы, )~..24 з» ПРОБЛЕМА РАЗРЕШИМОСТИ $2) (гл.

г ПРОБЛЕМА НЕПРОТИВОРЕЧИВОСТИ Рассмотрим пример такого построения применительно к аксиоматике геометрии. Будем исходить иэ первоначально зафиксированной системы аксиом. Аксиому 1 4), которая утверждает существование трех точек, не лежащих па одной прямой, мы заменим более слабой аксиомой 1 4') Эх Э у (х ~ у) (существуют две различные точки). Далее, мы опустим аксиому плоского порядка 11 5), но зато включим в число аксиом два предложения '), которые могут быть доказаны с помощью П 5): во-первых, расширим П 4) до П 4') ))сх))су(хчьу-РлгХч«(г, х, у)б«ЗгХсч(х, у, г)) и, во-вторых, добавим 11 5') ««х»«у«чг(х ~ у «Ус хта гса«с у чь г Х«ч(хв у, г) )/ Хсч(у, г, х) с/ Хсч(г«х, у)).

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

Прежде всего, предикат Сг мы определим так, чтобы он был истинным для любой тройки значений х, у, г. Тогда, как легко видеть, выполнятся все аксиомы группы 1, а также 11 1) и 111. Для того чтобы оказались выполненными аксиомы 11 2), 3), 4) и 5), на предикат Хсч необходимо, а также идостаточно, наложить следующие три условия: 1. Для тройки х, у, г с двумя совпадающими элементами Хсч всегда принимает значение «ложые 2.

Рассмотрим какой-либо набор из трех различных индивидов, входящих в число наших пяти. Требуется, чтобы среди шести различных упорядочений этого набора на двух упорядочениях с общим первым элементом Хсч принимал значение «истина», а на остальных четырех — «ложь». 3. Каждая пара различных индивидов является как началом, так и концом у одной из тех троек, для которых Хч принимает значение «нстина». ') Оба этв предложения з предыдущих и»данаях гнльбэртовых «Оснований геометрия» фигурировали в числе аксиом.

Однако оказалось, что онв могут быть доказаны с помощью аксиомы плоского порядка.(СМ. 7-э издание, с. 5 — 6 (с. 59 русского перевода).) ') Б ужэ упоминавшемся исследовании А ву«1«ш о( эх(онсв 1ог Зеош«1»у.— Тгавв. А«пег. МагЬ. Бес., 1904, 5, р. 350. Первому требованию можно удовлетворить путем прямого задания значений Хсч на соответствующих тройках индивидов.

Двум остальным требованиям можно удовлетворить следующим образом. Обозначим рассматриваемые пять элементов цифрами 1, 2, 3, 4, 5. Количество нндивидных троек, состоящих из трех различных элементов, для которых мы еще должны будем доопределить предикат Хсч, равно 5 4 3 = 60.

Каждый набор, состоящий из трех элементов, дает пам шесть таких троек; для двух из них предикат Хсч должен быть истинным, для остальных — ложным. Таким образом, из шестидесяти троек мы должны укааать двадцать, для которых Хсч долхсен оказаться истинным. Это будут те тройки, которые получаются иэ следующих четьсрех: (1 2 5), (1 5 2), (1 3 4), (1 4 3) в результате применения к ним циклической подстановки (1 2 3 4 5). Легко убедиться, что этим подбором мы удовлетворили всем сформулированным выше требованиям.

Построенная таким образом модель доказывает непротиворечивость рассмотренной нами системы аксиом '). Продемонстрированный на этом примере метод построения модели находит весьма многочисленные применения в новейших аксиоматических исследованиях. Прежде всего он используется для проведения различных доказательств независимости. Утверждение о независимости какого-либо предложения Я от системы аксиом Я равносильно утверждению о непротиворечивости системы аксиом ц4 )~р которую мы получим, добавив к Я в качестве новой аксиомы отрицание предложения Я. Если эта система аксиом выполнима в конечной индивидной области, то доказательство ее непротивоРечивости может быть проведено уже упоминавшимся методом построения модели э). Тем самым во многих исследованиях принципиального характера рассматриваемый метод оказывается хорошим дополнением к методу логического вывода, поскольку путем построения вывода мы можем устанавливать доказуемость разного Рода предложений при принятии тех или иных аксиом, а путем « ~* « — * «У нива в 5-элэ ~« „;,«„,„,, « в ээ состав 5-элементной ивдвзядной области, немедленно следует, что входящие состав вксвоыы и«Могут полностью определять линейный порядок.