Гильберт, Аккерман - Основы теоретической логики (947372), страница 26
Текст из файла (страница 26)
Мажнп, далее, ограничиться даже такими формулами, в которых встречаетсл талька один едмнственный двумсстный переменный предикат и, кроме того, приставка из!еет форму '. (Ех,)... (Ех„) (у,) (у,) (Ег) (и,)... (и„). При решении проблеиы выполнимости можно, далее, ограничи!ься формулами, приставки которых имеют форму '. (х,) (х„) (х„) (Еу,) .., (Еу„). Наконец, прн решении проблемы выполнимости достаточно рассв!огреть формулы, приставки которых ииеют форму '. (ЕХ) (у) (Ек) (и,)... (и,) . Интересующихся доказательством этих предложений отошлем к цитированным оригинальным работам'.
' 1.4лелае(т. !... ОЬег Мбансшшиеп 1пч йе!апчав!ЬЬ1. Мв(Ь. Ап. ВО. 75 (!9!5). в Ка!тас, С, гцгасыаьгцпа бев ЕпшсаешцпюргоЫепчв вц( аеп Рвп чоп Рогпче!и гпз1 е!пег е!пкваеп ь!пагеп Ропы!опзцлг!аь!еп. Сошр. Ывю. ВО. 4 (!93б). Владе(, К., лщпч ЕпмсЬе!бцп зргоЫет Оез (ощзсЬеп Рцп!с!!опеп!шжаи. МЬ. Мвю. РЬувж.
и. 49 (1933). "Аме"тать и'., Вс!1гвье кцт епсвсьеицсавргоыеш оег шаше иксьеп ! а!ь. мк(ь. Апп. Во. 1!г (шзб!. ' Дкаьпеашке прелложепцп редукции находам о работах: Рерм, 3„Ве!!свае вцг йеоцсиопв1ьшг!е оез !омшьсп еп(всье(- оцплзргоыетв, Ассе ы1. звеаед Во б (!рзб); зло.ап, то., юп1бе йебцсиопеп дез еп!шьс!ацнавргоысшв. лчь. ч!б.льва.Оз!о,!. Ыв1.-пве.
К!лвзе, !93б. йг. б. узе е нгн«ззнее «змеи«нные Гтр:Взече резрииинзгти расскажем теперь о важнейших частных случаях, в которых удалось решить проблему разрепшз!ости. Эти частные случаи образуют некоторую параллель с вышеупомянутыми предложениями редуцируемости. Предло!кению, что для каждой формулы исчвсления нредикатов можно указать равнозначную в отношении выполнимости, в которой встречанпся только одноместные и двумсстные предикатные переменные, соответствует предложение, что проблема решена для вблатни фврмул, которые содержат только одноместные арвдикитные переменныг.
Точно так же предложениям, которые по отношению к проблеме разрешимости прелнринимаюг редукцию формул к таковым с определепныии приставками, соответствует тот факт, что для определенных классов приставок удалось также достигнуть решения проблемы разрешимости, Принципиальную возможность решения в области одноместных предикатов установил впервые Лбвенгейм'.
Более простые доказательства были предложены Сколемом' и Беманом'. Указанньгедоказательства по своему значению выход!и за пределы области узкого исчисления предикатов, так как они решают проблему разрешимости, поскольку встречаются только одноместные предикаты, и для исчисления предикатов второй ступени, которое подлежнг рассмотрению в четвертой главе, где мы н возвратимся к этапу. В следующих рассуждениях нам удоопее иметь дело с проблемой общезначзп!33сти, Мы можем убедиться в разрешимости формул узкого исчисления з йбюзнвеггн, Г...
ВЬег МЬЗ33еь3ге31ен !т Не3е13чае1ао3 маш, Аи. Ва, тб(39151. * Згз!ет, та., 31неегзчсЬннбеп ОЬег те А«3ете бее К!еззениежбм нна Оьег ргебищецон- чнб ЗиттененергеЫете, ме3еье вечные к3«геен чон Аиеыиен ье1гепеп. ч3б. звпггег 3. м«1..не1. К3«зее, ЮЗО, Кг. З. ' Веиненв, и., Вецгабе чнг А3зеЬге аег вещи чоб еипз Втмдеы озер Ы . Мет. Аи Ва. Зб 33992).
Особенна ясное нзнанзеине нечншиинн одноместных нре. лен«ген мы находим з «инге. Нзюе з — Н г зу, Огиитеиеп бег Мещетегш ! (ер. неебенме ! б, егр 391 — 39б). предикатов, которые содержат только одноместные переменные предикаты, следующим элементарным пу- тем. Пусть дана некоторая форлгула из указанной области. Пусть 33-число различных преднкатных знаков А, В,..., К, встречающихся в рассматриваемой фор- муле. Мы утверждаем: если формула общезначима вв вгвх случаях, иог3)а область индивидуумов состоит са- мое большее из 2з предметов, то вна вообще вбщезна- чима. Для доказательстве мы допустим, что рассматри- ваемая фориула для некоторой системы индивидуумов, большей, чем 2", при замене переменных предикагов А, В, „К определеш1ымн предикатаегн А„В„...,К„ выражает ложное высказывание.
В таком случае мы выведен из этого высказывания другое ложное вы- сказывание, которое также получается путем специа- лизации рассматриваемой формулы и относится самое большее к системе 2' индивидуумов. Ь(ь3 подразделим предметы, к которым относится данное ложное высказывание (с предика!вин А„В„..., ..., К,), на классы, причисляя два предмета а, Ь к одному и тому же классу, если нысказывания А,(а), В,(а), ..., К,(а) равнозначны соответственно с А,(Ь), В, (Ь)...., К,(Ь), т, е.
А,(а) равнозначно с А,(Ь), В,(а) раонозначнос В,(Ь), К,(а) равнозначно с К„(Ь). В результате мы получим самое большее 2' классов. В самом деле, для предмета а выражение А,(а) может бить только истинным или ложным; то же самое и для В,(а) и т. д. В целом существует, следовазсльно, только 2" возлгажяоетЕй для Распределении !за узлов оживление превовотвв Поввлема разрешимости 1бУ истинности нли ложности среди высказываний А,(а), В,(а),..., К,(а), и если для двух предметов это распределение сов- падает, то они прина;де>хат к одному классу.
Пусть и„ и„ ...,и„ различные классы, которые мы таким сбразол~ получаем, причем, как указано, и чй'. Возьмем теперь совокупность классов а„ «„... ..., и, в начес~во новой системы предметов. По отно- шению к этим предметам определим д предикатов А„В„..., К, следующим образом: А, выполняется длч класса а„(р †. 1,..., и) тогда и только согда, когда А, выполняешься для предметов, принадлежа- щих первоначально к а,.
Соответственно определяются В„..., К,, Если затем в пронзвольнолг высказывании, обра- зованном с помощью логических знаков из предикатов Л„В„,..., К„заменим А, на А„В„на В„..., К, на К„возьмем в качестве значений переменных. вместо первоначальных предметовклассы и„ае..и, и заменим каждый определенный пре„мет, встречаю- щийся в данном случае в высказь,ванин, классом, к которому он принадлежит, то высказывание пере- ходит в раннозначное с нвм. Истинность этого утверждения нспосрегственно очевидна, если соответствующее высказывание не содер- жит знаков общности и существования. Для общего до- казательства представим себе высказывание записан- ным в нормальной форлге и от истинности нашего утверждения для т стоящих впереди кванторов за- ключим к истинности его длч т~-1 кванторов. Из этого предлонсения, в частности, следует, что то ложное высказывание, которое, согласно нашему предполом<ению, возникает из данной формулы после замены переменных предикатов Л, В, ..., К преди- катами А„В„,..., К„, юсова переходит в ложное вы- сказывание, если мы заменим прсдикаты А„В„:.,К.
на А„В„..., К, и возьмем в качестве значений пе- ременных классы а„а„..., а„. Позтому достаточно решить вопроса всегда-штинности только для случая, когди илсеется самее боль. шее 2' предметов, т. е. число их конечно. В етом же случае, как мы видели, проблема разрешимости решает. ся конечным приемом. Если мы теперь снова рассмотрим формулы, в которых .встречаются произвольные переиенные предикагы, то можем лет<о указать разрешающий прием для общезначимости формул, у которых приставка состоит только из знассов общности или только из знаков существования, или у ссоторых все знаки общности предшвствуют всем знакам существования. Прежде всего рассмотрим формулу первого рода, т.
е. формулу вида (х,) (х,)...(х )й((х„хе,..., хч), у которой сй(х„х„..., и„,) больше не содержит зна. кон общности или существования. Эта сбормула нюг- да и только тогда общезначима, когда она общезначима в области, содержащей т индивидуумов. В самом деле, если бы в некоторой области с чи- слом индивидуумов, превосходящим т, формула не была общезначимой, то в этой облав~и существовали бы элементы а„а„..., а„и специальные предикаты такие, что выражение т( (а„а„..., а„) прегставляло бы собсй ланскую формулу.
Однако в этом случае, как неп средственно ви,но, не было бы общезначнмосзи в области (а„а,,..., а ). Формула (Ех,)...(Ех„,) оХ(х„..., х ), у которой приставки состоит иванько из знаков существования, обшезначима, если и.чеется общезначимость в области толысо с одним индивидтумом. Действительно, если вышеупомянутая формула не общезначима, то, во всякои случае, не общезначима Прсдзсмо Гозрсши ив!щи Узкое и гиглсние лредйзомев 158 н формула (Ех)сй(х, х, ..., х), которая ведь представляет собой более сильное утвер- ждение. Таким образом, существует в некоторой обла- сти элемент а и специальные предикаты такие, что 9((О, ..., О) превращается в ложную формулу.
Мы не имели бы в таком случае общезначиз!ости и в этой об- ласти с одним нашим элементом а. Так же врос!о можно показат!н что формулы (х,)... (х„) (Еу,)... (Еу„] 6(х„..., х„н ую ..., ул), у которых все знаки общности идут раньше знаков существования, общсзнзчнмы, если имеется общезначи- масть в области с и индивидуумами. Именно, мы обра- зуем дизьюнкпию всех возмо)кных формул 5 (х„, .,, хл„х,, ..., х, ), которые получаются из 9((х„..., хно у„..., у„) прн какой-нибудь замене уы ..., у„переменными из ряда х„..., хм. Обозначим эту дизыонкцию через ю(х„..., х ). Очевидно,для области нз !и индивидуу- мов из общезначимости (х,)... (хм)(Еу,)... (Еу.)9((хн ..,, х, у„..., у„) следует общезначимость для (х,)...
(хм) ю (хо ., ., х ), а значит, и общезначимость (х,) ... (х„) З (х„ , хм) вообще Но так как (х,) ... (хм) ю(х„..., х ) пред- ставляет собой более сильное высказывание, чем (х,)... (хм) (Еу,)... (Еул) 9)! (х„., х, у„.,у„), то наше утверждение доказано'. ' Последние нз упомянутых частных случаев проблемы резрегнниостн были окончательно решены а работе Веглоуг Р. нпа зглдл)ожс! М. Ешп Во!оспе!Оипсзргошеш Оег шз!Ье~пзгЬЬ всиеп Ьощк, Мзщ. Апп. ВО.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
