Гильберт, Бернайс - Основания математики. Теория доказательств (947376), страница 51
Текст из файла (страница 51)
б) Теорема Левенгейма и теорема Геделя о полноте. Теоретико-модельная сколемовская нормальная форма может быть, в частности, использована — и в этих целях ею пользовался, в частности, сам Сколем з) †д того, чтобы достаточно простым способом доказать теорему о том, что всякал выполни»щи формула выполнима также и в сбласпш нитуриленых чисел. Ввиду того, что каждая формула исчисления предикатов модельно равна некоторой сколемовской нормальной форме, эту теорему, которая, как уже упоминалось ранее, была найдена и впервые доказана Левенгеймом'), достаточно доказать только для этих нормальных форм.
Кроме того, согласно сделанным ранее замечаниям, при этом можно ограничиться рассмотрением только таких формул, которые не содержат ни формульных переменных без аргументов, ни свободных индивидных переменных. Можно также считать, ') В ермииологии Генриха Шольпа две формулы, иаходяшиееи в атом отиошеиии, иазываютси авива ииыми по выполнимости.
з) Б)г о! ет ТЬ. Еоя!»сЬ)гошшпа1ог!»сье 1)п!егзпсьппаеп 9Ьег гве Ег16цЬагаец ооег Вегее!»Ьаг)ге!! гпврпетабзсЬег а!хе пеЬМ е!пеш ТЬеогеш 0Ьег гн<Ь!е Мепяеп. — гг!г).-зе!»Ь» Ягг. Кг!зцап!а, 1 Ма!.-!Чв1. К1., 1920, № 4. з) Еогвепь е ! т Е. ОЬ»г Мая1)сЬЬе!1еп !го йе1а!!»)га1)гп1.— Ма!Ь. Апп,. 1915, 76. 237 а-СИМВОЛ И ЛОГИЧЕСКИИ ФОРМАЛИЗМ и'Л. П1 примеиВние к пРОБлеме РАЗРешимости что в кванторной приставке всегда имеется по крайней мере один квантор всеобщности и один квантор существования. Действительно, для предваренной формулы исчисления предикатов, не содержащей либо кванторов всеобщности, либо кванторов существования, справедливость этого утверждения немедленно вытекает из того, что модель любой такой формулы, если она возможна вообще, может быть построена и в конечной индивидной области').
Итак, рассмотрим формулу 5 вида ~31...~3дрз...--(3,21(31, ..., 3„3„..., р,), где Г„..., 3„31, ..., р — полный список входящих в нее индивидных переменных (! и б отличны от нуля). Будем считать, что в 5 нет формульных переменных без аргументов. Пусть эта формула выполнима в какой-либо индивидной области У. Требуется показать, что тогда она выполнима и в области натуральных чисел. По предположению, для формулы 5 существует система выполняющих ее логических функций, аргументы которых принимают значения в области з'. Пусть З(3„..., ра) обозначает выРажение, котоРое полУчаетсЯ из 6(3„..., Ра) в РезУльтате замены формульных переменных сопоставленными им выполняющими логическими функциями.
Тогда формула 1Уе! ° И3сЗР1 ° ° ° Жаш (а ° ° ° 3, Р 9а) будет истинной в области л. Поэтому на основании принципа выбора существуют такие математические функции !!1, ..., т от 1 аргументов, пробегающих область л', что формула ~13 "~3,~(31, ", 3„у.(гз, ", 3,), ", ха(гз, ", ре)) истинна в этой области. Таким образом, если а„..., а„— какие- либо символы или выражения, обозначающие элементы области (, то формула е(а„..., а, )11(«1, ..., «,),, уа(аз, ..., а,)) является истинной.
А теперь выделим в области У какой-либо элемент и возьмем в качестве обозначения для него символ а. Затем устроим перечисление всех термов, построенных из символов а, т„ ..., уа, устанавливая порядок этих термов в первую очередь по их ') См. рассуждения, проведенные в т. 1 ва с. 239 — 243. Этя рассуждения без труда могут быть переложены с языка теории доказательств ва язык теории моделей. кр атн ости относительно символов )(1, ..., Х,, т. е. по числу входящих в данный терм функциональных знаков, считаемых с учетом учетом их кратности, а при одинаковой кратности в лексико- графически. В этом перечислении каждому числу и однозначно (и даже взаимно однозначно) соответствует некоторый построенный из символов сз, )(„..., ха терм, имеющий и в качестве номера.
По смыслу указанных символов этот терм изображает некоторый элемент области з'. Поэтому, сопоставив числу и значение того построенного из символов а, т„..., !(а терма, который в нашем перечислении слепни имеет номер п, мы получим некоторую функцию $(п) от натурального аргумента со значениями из области Пусть ! — какое-либо из чисел 1, ..., 6. Каковы бы ни были числа и„..., и„, значение выражения )!,($(л!), ..., $(п,)), являю- щееся элементом о ом области з', тоже изображается выражением, построенным из символов а, )(1, ..., та.
Номер этого выражения в его зависимости от чисел пы ..., и, и индекс а ! Мы обозначим через ф,(пы ..., и). Тогда функции фз(П„..., Пс), ..., фа(пз, ..., Л,) будут арифметическими, и значение $(зр,(лз, ..., л,)) при = 1 ... 6 всегда будет совпадать со значением )!!($(п,), ..., $(п,)1. А теперь мы сопоставим каждой входящей в выражение ) логической функции 3!(а„..., а„) с аргументами, пробегающими область а', соответствующую ей логическую функ- ЦИЮ 4) ($ (Лз), ..., с(ПР)) С НатУРаЛЬНЫМИ аРГУМЕНтаМИ П„..., П„ Обозначим через Ве (31, ..., ра) выражение, получающееся из езультате замены входящих в него символов логических функци , ф й, заданных в области У, символами сопостав- ленных им логических функций с натуральными аргументами. Тогда с учетом произведенного сопоставления и с учетом равен- ства значений выражений х,(5(лз), ..., $(п,)) и $(ф,(па, ..., и„)) значение выражения Ее(л„..., п„ф!(лт, ..., п,),, фа(п„..., л,)) при произвольных числах и„ ..., „ уд р и б дет равно значению выражения В 5(л ), ..., $(п,), т ($(л ), ..., $(п„)),..., х ($ !лз), ..., $(л,))), е-СИМВОЛ И ЛОГИЧЕСКИИ ФОРМАЛИЗМ ПРИМЕНЕНИЕ К ПРОБЛЕМЕ РАЗРЕШИМОСТИ 1гл гп т.
е. значению «истина». Таким образом, формула Уйг "Чй,.6*(гг..., Гг, ф (й " Иг) "'гф.(Г " ~г)), а потому и формула ~Гг...)УйД»г...лр«З»(.ь ..,, ~„Р„..., 9«) истинна в области натуральных чисел, и, значит, о и ла выполнима в области натуральных чисел. силу доказанной таким образом теорем Д" понятие выполнимости формул исчисл ы е'венгейма об ее ения предикатов может быть пт в заменено в математическом отношении в ыполнимости в области натуральных чисел. есьма удобным понятием проблемы аз еш Одно еще более серьезное и о е у р щ ние теоретико-множественной про лемы разрешимости получается из веделевской те р ут рждает, что всякая неопровержимая Форм й теоремы о лол- является вьтолнимой.
я формцла В доказательстве этой теоремы опять рассмотрен е ф и м формул вида р ять можно ограничиться (3) ай!...~й,--)!)г...~))зй)(й„..., йс, рь ..., !)з) г ° 1'з, где г„ ..., е,, 9, ... 9— в ь ,,з — полный список входящих в нее ндиых переменных.
Действительно, Гз ее ииди- мула исчисления предикатов, а 31 — тео и , если — какая-ниб ь вляется ~~рмулой указанного частного вида, а во-вторых, в отношении опровержимости формулы 91 и 6 в Следовательно, если фо м ла н и равносильны. и формула . С д гой сто о формула 5 неопровержима, то неопровержима пима и сч. Поэтом, если м ру р ны, если Я выполнима, то вып л- ыполсч. П у, и мы сможем из неопровержимости Я заключить о ее выполнимости, то то же с относительно св. то же самое будет верно и йй1». — Мопасз)г. д!а1)ь р)г, З )Г х)аше без )ой!за)геп гпп)с1)опеп)га1- ') бо де! К. В!е го!1«1апб)й)ге!! бег Ах! ше В уз., 7, «2. »тай работе Гедель показал также, что в некоторой усиленн й фо же, что теорема а полноте верна н ность формул, з й а рме — а именно, ч , что всякая счетная последователь- получил зто уситени, нз которо нельзя вывести п оги р аоречип, выполнима.
Гедель последовательно й-. бо . ение, показав, что если выполнима любая конечная поднима и са а сть како -либо счетной п бо оследовательности формул, га выпал»Той усиленн й Р м зта последовательность. О дно очень прозрачное доказательство да Л. Генкнным в его работе: Непй|п 1.. о теоремы о полноте на 1949 14 р 159 — 166 3 к ательство было у рошеиа Г. Хыы~- — атем ато дока» те ь й, Е1пе Вегаегйппй гп НепЫпз Вене!з 96 1 е1 ез РгйдП'д'еп"а!йщз ""ег 81п)е — Л 8УЩЬ'Ис )-09!с н другне даназателс" — тех пор с помошью сгва теоремы о полноте.
различных методов были па«учены Далее, можно снова считать, что рассматриваемая нами формула (3) содержит по крайней мере один квантор всеобщности и по крайней мере один квантор существования. Для обоснования этого утверждения нам не нужны рассуждения, с помощью которых мы ранее разобрзлн случаи 9=0 и соответственно Т=О. Просто мы можем воспользоваться тем обстоятельством, что любая формула !!(Г ...)УГ„.гВ(Г„..., й,) переводима в формулу Ууг...)уй,=)!)(6(Г„..., ~г)бг(А(1)) ~/ 1А(п))), а формула ЛР~ рае (рь ' ' 1)з) переводима в формулу ЧЛ,Т...З!)«((А®1~-)А(й))8 В(рг, ..., рз)) и что указанные преобразования не меняют выполнимости рассматриваемых формул. Итак, пусть 5 — неопровержимая формула вида (3), где г и 6 отличны от нуля, а хг, ..., х„пь ..., Рз суть все входящие в эту формулу индивидные переменные.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
