Previous  Next  Contents

 

СВЕЖДАНЕ НА ВЪПРОСИ ЗА ТЪЖДЕСТВЕНА ВЯРНОСТ, ИЗПЪЛНИМОСТ И СЛЕДВАНЕ
В ПРЕДИКАТНОТО СМЯТАНЕ С РАВЕНСТВО КЪМ ВЪПРОСИ В ОБЩОТО ПРЕДИКАТНО СМЯТАНЕ

    Ще предполагаме, че е налице двуместен предикатен символ eq. Ще наричаме представително множество от аксиоми на равенството такова множество от аксиоми на равенството, което съдържа поне по една формула от всеки от първите три вида, изброени в дефиницията за аксиома на равенството, и за всяко положително цяло число n съдържа поне една формула от четвъртия от изброените видове при всеки избор на функционалния символ w и поне една формула от петия от изброените видове при всеки избор на предикатния символ p. Ще предполагаме, че е фиксирано някое представително множество от аксиоми на равенството, и ще го означаваме с E (в частност би могло E да се състои от всички аксиоми на равенството). Ясно е, че за да бъдат верни в дадена структура аксиомите на равенството, необходимо и достатъчно е в тази структура да бъдат верни формулите от множеството E.

    Теорема 1. Нека j е произволна формула. За да бъде j тъждествено вярна в предикатното смятане с равенство, необходимо и достатъчно е j да следва от множеството E в общото предикатно смятане.

    Доказателство. Знаем, че ако пред една формула поставим квантори за общност относно нейните свободни променливи, получената формула е затворена и е вярна точно в онези структури, в които дадената формула е тъждествено вярна. Поради това можем без ограничение на общността да считаме, че формулата j е затворена. При такова положение задачата ни се свежда към това да докажем, че j е вярна във всяка нормална структура точно тогава, когато j следва от множеството E в общото предикатно смятане. В едната посока доказателството е очевидно - ако j следва от множеството E в общото предикатно смятане, то j е вярна във всяка нормална структура, защото формулите от E са верни във всяка такава структура. За да извършим доказателството в обратната посока, да предположим сега, че j е вярна във всяка нормална структура, и да разгледаме произволна структура S, с която са верни формулите от E. В структурата S ще бъдат верни аксиомите на равенството и поради това теорема 3 от въпроса за конгруентности и факторизация позволява да се построи нормална структура, в която са верни същите затворени формули както в S. Формулата j ще бъде вярна в така построената структура, следователно j ще бъде вярна и в S. С това е показано, че j следва от множеството E в общото предикатно смятане.

    Теорема 2. Нека M е произволно множество от формули. За да бъде M изпълнимо в предикатното смятане с равенство, необходимо и достатъчно е обединението MИE да бъде изпълнимо в общото предикатно смятане.

    Доказателство. Ако множеството M е изпълнимо в предикатното смятане с равенство, то съществува нормална конфигурация, в която са верни формулите от M, а във всяка такава конфигурация очевидно са верни и всички формули от множеството MИE. С това необходимостта е доказана. За да докажем достатъчността, нека предположим, че обединението MИE е изпълнимо в общото предикатно смятане. Нека s е такава субституция, за каквато става дума в допълнителната лема за равноизпълнимост, и нека Mў е множеството от формулите, получени от формулите от M чрез прилагането на s (разбира се Mў съвпада с M в случая, когато формулите от M са затворени, като в този случай разглеждането на s е всъщност излишно и доказателството се опростява). Споменатата лема, приложена към множеството MИE в качеството на M, позволява да се твърди, че множеството от затворени формули MўИE също е изпълнимо в общото предикатно смятане. Нека S е структура, която е модел на MўИE. Понеже в S са верни аксиомите на равенството, теорема 3 от въпроса за конгруентности и факторизация позволява да се построи нормална структура S., която е модел на Mў. Като използваме забележката към допълнителната лема за равноизпълнимост, можем да твърдим, че при подходящ избор на оценката v в S. на променливите нормалната конфигурация (S.,v) ще удовлетворява множеството M. Следователно множеството M е изпълнимо в предикатното смятаме с равенство.

    Следствие. Нека M е дадено множество от формули. Една формула следва от M в предикатното смятане с равенство точно тогава, когато тя следва от обединението MИE в общото предикатно смятане.

    Доказателство. Ако дадената формула е j, използваме, че j следва от M в предикатното смятане с равенство точно тогава, когато множеството MИ{Шj} е неизпълнимо в предикатното смятане с равенство.

 

Последно изменение: 26.07.1999 г.

 Previous  Next  Contents