КОНГРУЕНТНОСТИ. ФАКТОРИЗАЦИЯ

    Лесно се вижда, че ако в условието 5 на горната дефиниция заменим знака "=" със знака "Ј", ще получим дефиниция, еквивалентна на нея.

    Теорема 1. Нека е налице символ eq в P₂ и S=(C,I) е произволна структура. Нека R е множеството на онези двойки (c,d) от C², за които I(eq)(c,d)=1. За да бъдат аксиомите на равенството верни в S, необходимо и достатъчно е R да бъде конгруентност в S.

    Доказателство. Удобно е да си послужим с варианта на дефиницията за конгруентност, който е с неравенство в условието 5. Ако в изискванията от този вариант на дефиницията вземем пред вид конкретния начин, по който е определена релацията R в случая, получаваме съвкупност от изисквания, за която лесно се проверява, че е удовлетворена точно тогава, когато в S са верни аксиомите на равенството и формулите, споменати в забележката след изброяването на въпросните аксиоми (при проверката може да се използва обстоятелството, че една затворена универсална формула е вярна в дадена структура точно тогава, когато безкванторната част на въпросната формула е тъждествено вярна в дадената структура). Като вземем пред вид казаното в същата забележка, виждаме, че получената съвкупност от изисквания е удовлетворена точно тогава, когато в S са верни аксиомите на равенството.

    Ако S=(C,I) е структура, а R е конгруентност в S, то ще дефинираме една нова структура, която ще наричаме фактор-структура на S относно R и ще означаваме с S/R. Ще направим това по следния начин. От условията 1, 2 и 3 в дефиницията за конгруентност е ясно, че R е релация на еквивалентност в C, следователно можем да образуваме фактор-множеството C/R на C относно R (елементите на C/R - това са класовете на еквивалентност в C, породени от R, т.е. множествата [c]_R={d|cRd}, отговарящи на елементите c на C). Полагаме S/R=(C/R,Iў), където Iў е интерпретиращото съответствие, дефинирано така: Iў(w)=[I(w)]_R при wОW₀ и Iў(p)=I(p) при pОP₀, а при n>0 и произволни c₁, ..., c_n от C имаме Iў(w)([c₁]_R,...,[c_n]_R)=[I(w)(c₁,...,c_n)]_R при wОW_n, Iў(p)([c₁]_R,...,[c_n]_R)=I(p)(c₁,...,c_n) при pОP_n. Този начин на определяне на Iў(w)([c₁]_R,...,[c_n]_R) и Iў(p)([c₁]_R,...,[c_n]_R) е коректен благодарение съответно на условията 4 и 5 от дефиницията за конгруентност и на обстоятелството, че за произволни c и d от C равенството [c]_R=[d]_R е равносилно със съотношението cRd. Ще покажем, че в известен смисъл структурите S и S/R са неразличими посредством дадения език на предикатното смятане. За тази цел да означим с B множеството на всички наредени двойки от вида (c,[c]_R), където cОC. Начинът, по който дефинирахме интерпретиращото съответствие Iў, позволява да се твърди, че B е бисимулация между S и S/R, като тази бисимулация очевидно е тотална (дефинициите за бисимулация и за тотална бисимулация бяха дадени във въпроса за безкванторни формули). Сега ще докажем следното важно допълнение към доказаната по-рано бисимулационна лема.

    Лема за тоталните бисимулации. Ако B е тотална бисимулация между две конфигурации (S,v) и (Sў,vў), то за всяка формула j е в сила равенството j^S,v=j^Sў,vў. Ако B е тотална бисимулация между две структури S и Sў, то за всяка затворена формула j е в сила равенството j^S=j^Sў.

    Доказателство. Ако B е тотална бисимулация между две структури S и Sў, то за всяка оценка v в S на променливите може да се намери такава оценка vў в Sў на променливите, че B да бъде тотална бисимулация и между конфигурациите (S,v) и (Sў,vў) (разбира се вярно е и симетричното на това твърдение - за намиране на v по дадено vў). Поради тази причина второто твърдение на лемата представлява следствие от първото и е достатъчно да докажем първото. Доказателството му се извършва чрез индукция, съобразена с дефиницията на понятието формула, като двете структури S и Sў могат да се считат фиксирани, но оценките v и vў трябва да могат да варират. Понеже атомарните формули са безкванторни формули, верността на твърдението за тях ни е известна от по-рано. Индуктивните стъпки, отговарящи на образуването на отрицание, на конюнкция и на дизюнкция, се извършват по същия прост начин както по-рано при доказателстовото на бисимулационната лема. Остава да разгледаме случаите на генерализация и на екзистенциализация на формула, имаща доказваното свойство. Нека j е такава формула, а x е променлива. Трябва да докажем, че и формулите "xj и $xj имат това свойство. Ще направим това за първата от тях, а за втората разсъжденията са аналогични. За целта при предположение, че B е тотална бисимулация между две конфигурации (S,v) и (Sў,vў), ще докажем равенството "xj^S,v="xj^Sў,vў. Последното равенство е равносилно с твърдението, че ако формулата "xj е вярна в някоя от конфигурациите (S,v) и (Sў,vў), то тази формула е вярна и в другата от тези конфигурации. Нека например "xj е вярна в конфигурацията (S,v). За да докажем верността на "xj в конфигурацията (Sў,vў), ще предположим, че е даден произволен елемент cў на носителя на Sў, и ще покажем, че формулата j е вярна в конфигурацията (Sў,wў), където wў е x,cў-модификацията на vў. Нека c е такъв елемент на носителя на S, че да бъде изпълнено условието cBcў (такова c съществува благодарение на тоталността на B). Да означим с w x,c-модификацията на v. Лесно се проверява, че B ще бъде тотална бисимулация и между конфигурациите (S,w) и (Sў,wў) и следователно, по индуктивното предположение, ще бъде в сила равенството j^S,w=j^Sў,wў. От друга страна, поради верността на формулата "xj в конфигурацията (S,v) формулата j е вярна в конфигурацията(S,w), следователно тя е вярна и в конфигурацията (Sў,wў).

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

    Теорема 2. Нека S е структура, а R е конгруентност в S. Тогава множеството на затворените формули, които са верни в S, съвпада с множеството на затворените формули, които са верни във фактор-структурата S/R.

    От теореми 1 и 2 може да се извлече следното заключение, което ще използваме няколко пъти по-нататък.

    Теорема 3. Нека е налице символ eq в P₂ и S е структура, в която са верни аксиомите на равенството. Тогава съществува такава конгруентност R в S, че фактор-структурата S/R е нормална структура и в нея са верни същите затворени формули както в структурата S.

    Доказателство. Нека S=(C,I) и нека R е множеството на онези двойки (c,d) от C², за които I(eq)(c,d)=1. Според теорема 1 R е конгруентност в S. Следователно можем да образуваме фактор-структурата S/R, имаща носител C/R. Нека Iў е нейното интерпретиращо съответствие. Тогава за произволни c и d от C имаме равенството Iў(eq)([c]_R,[d]_R)=I(eq)(c,d). Следователно Iў(eq)([c]_R,[d]_R)=1 точно тогава, когато е изпълнено условието cRd, а то е равносилно с равенството [c]_R=[d]_R. Това показва, че Iў(eq) е предикатът за равенство в C/R и значи структурата S/R е нормална. По теорема 2 множеството на затворените формули, които са верни в тази структура, съвпада с множеството на затворените формули, които са верни в S.

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