Факторизация на структура относно конгруентност в нея

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

Нека е дадена една структура S = (Σ,D,I). Конгруентност в S ще наричаме ще наричаме кое да е подмножество R на D² със следните пет свойства, където dRd' означава, че (d,d') принадлежи на R:
Рефлексивност. За всяко d от C е в сила съотношението dRd.
Симетричност. Всеки два елемента d и d' на D, удовлетворяващи условието dRd', удовлетворяват и условието d'Rd.
Транзитивност. Всеки три елемента d, d' и d'' на D, удовлетворяващи условията dRd' и d'Rd'', удовлетворяват и условието dRd''.
Съгласуваност с функциите на S. Всеки път, когато ω е n-местен функционален символ на Σ с n>0 и d₁, …, d_n, d₁, …, d_n са елементи на D, удовлетворяващи условията d₁Rd₁, …, d_nRd_n, налице е и съотношението I(ω)(d₁,…,d_n) R I(ω)(d₁,…,d_n). Съгласуваност с предикатите на S. Всеки път, когато π е n-местен предикатен символ на Σ с n>0 и d₁, …, d_n, d₁, …, d_n са елементи на D, удовлетворяващи условията d₁Rd₁, …, d_nRd_n, налице е равенството I(π)(d₁,…,d_n) = I(π)(d₁,…,d_n). Поне една конгруентност в S със сигурност съществува, а именно множеството на двойките от D² с равни пръв и втори член. Понякога обаче съществуват и други.

Пример 1. Нека S = (Σ,D,I), където Σ = ({f,g},{p},ρ), ρ(f) = ρ(g) = ρ(p) = 2, D е множеството на положителните цели числа, за всеки две числа d₁ и d₂ от D I(f)(d₁,d₂) и I(g)(d₁,d₂) са съответно най-големият общ делител на числата d₁ и d₂ и тяхното най-малко общо кратно, а I(p)(d₁,d₂) = 1 точно тогава, когато d₁ и d₂ са взаимно прости (т.е. когато I(f)(d₁,d₂) = 1). Нека съотношението dRd' е налице между две числа d и d' от D точно тогава, когато простите делители на d и на d' са едни и същи. Тогава R е конгруентност в S.

Забележка 1. Като се използва наличието на условието за симетричност в горната дефиниция, лесно се вижда, че ако в условието за съгласуваност с предикатите на S заменим знака за равенство със знака ≤ , ще получим дефиниция, еквивалентна на нея.

Нека S = (Σ,D,I) е структура, а R е конгруентност в S. Ще дефинираме една нова структура, която ще наричаме фактор-структура на S относно R и ще означаваме с S/R. Ще направим това по следния начин. От първите три условия в дефиницията за конгруентност е ясно, че R е релация на еквивалентност в D, следователно можем да образуваме фактор-множеството D/R на D относно R (елементите на D/R са класовете на еквивалентност в D, породени от R, т.е. множествата [d] = {d' | dRd'}, отговарящи на елементите d на D). Полагаме S/R = (Σ,D/R,I^), където I^ е интерпретиращото съответствие, дефинирано така: I^(ω) = [I(ω)] за всеки нулместен функционален символ ω на Σ и I^(π) = I(π) за всеки нулместен предикатен символ π на Σ, а при n>0 и произволни d₁, …, d_n от D имаме I^(ω)([d₁],…,[d_n]) = [I(ω)(d₁,…,d_n)] за всеки n-местен функционален символ ω на Σ и I^(π)([d₁],…,[d_n]) = I(π)(d₁,…,d_n) за всеки n-местен предикатен символ π на Σ. Този начин на определяне на I^(ω)([d₁],…,[d_n]) и I^(π)([d₁],…,[d_n]) е коректен благодарение на условията за съгласуваност от дефиницията за конгруентност и на обстоятелството, че за произволни d и d' от D равенството [d] = [d'] е равносилно със съотношението dRd'.

Пример 2. Нека S и R са както в пример 1. Ще дадем едно по-прегледно описание на съответната фактор-структура S/R. За всяко крайно множество P от прости числа да означим с *P множеството на числата от D с множество на простите делители P. Тогава D/R се състои от всевъзможните множества *P, съответстващи на крайни множества P от прости числа, като на различни P отговарят различни *P. При това за всеки две крайни множества P₁ и P₂ от прости числа са в сила равенствата f^S/R(*P₁,*P₂) = *(P₁∩P₂) и g^S/R(*P₁,*P₂) = *(P₁∪P₂), а равенството p^S/R(*P₁,*P₂) = 1 е изпълнено точно тогава, когато сечението на P₁ и P₂ е празно.

Ще покажем, че в известен смисъл структурите S и S/R са неразличими посредством разглеждания език на предикатното смятане.

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

Доказателство. Нека за всяка оценка v в S оценката v^ се дефинира чрез равенството v^(ξ) = [v(ξ)]. Тогава τ^{S/R,v^} = [τ^S,v] за всеки терм τ при сигнатура Σ и φ^{S/R,v^} = φ^S,v за всяка формула φ при тази сигнатура. Твърдението, отнасящо се за термове, се доказва чрез индукция, съобразена с дефиницията за терм, а твърдението, отнасящо се за формули – чрез индукция, съобразена с дефиницията на понятието формула. Верността на първото равенство в случаите, когато термът τ е константа или променлива, произтича непосредствено от дефинициите на I^ и на v^: ако τ е константа, то

τ^{S/R,v^} = I^(τ) = [I(τ)] = [τ^S,v], а ако τ е променлива, то τ^{S/R,v^} = v^(τ) = [v(τ)] = [τ^S,v]. Индуктивната стъпка в доказателството на първото равенство също е лесна: ако τ = ω(τ₁,…,τ_n), където ω е n-местен функцонален символ с n>0, τ₁, …, τ_n са термове и τ_i^{S/R,v^} = [τ_i^S,v], i = 1,…,n, то τ^{S/R,v^} = I^(ω)(τ₁^{S/R,v^},…,τ_n^{S/R,v^}) = I^(ω)([τ₁^S,v],…,[τ_n^S,v]) = [I(ω)([τ₁^S,v],…,[τ_n^S,v])] = [τ^S,v]. Лесни са също проверката на второто равенство за случая, когато φ е атомарна формула, и индуктивните стъпки, отговарящи на образуването на отрицание, на конюнкция и на дизюнкция. Остава да разгледаме случаите на генерализация и на екзистенциализация на формула, имаща доказваното свойство. Нека φ е формула, имаща това свойство при всеки избор на оценката v, а ξ е променлива. Трябва да докажем, че и формулите ∀ξφ и ∃ξφ имат това свойство. Ще направим това за първата от тях, а за втората разсъжденията са аналогични. За произволна оценка v имаме (∀ξφ)^{S/R,v^} = min{φ^{S/R,v^[ξ→[d]]} | d∈D} = min{φ^{S/R,v[ξ→d]^} | d∈D} = min{φ^S,v[ξ→d] | d∈D} = (∀ξφ)^S,v. С това показахме, че формулата ∀ξφ има желаното свойство. От доказаното равенство, отнасящо се за формули, е непосредствено ясно, че всяка формула, тъждествено вярна в структурата S/R, е тъждествено вярна и в структурата S. В обратното се убеждаваме, като използваме същото равенство и обстоятелството, че всяка оценка в структурата S/R може да се представи във вида v^ при подходящ избор на оценка v в S. _□

Забележка 2. За по-нататъшната ни работа е особено важен случаят, когато за някой двуместен предикатен символ π в сигнатурата на структурата S съответният предикат π^S има множество на истинност R. В този случай предикатът π^S/R е предикатът за равенство в S, т.е. множеството на истинност на този предикат е подмножеството на (D/R)², състоящо се от двойките с равни пръв и втори член. И наистина, за всеки два елемента d и d' на D ще бъде в сила равенството π^S/R(([d],[d']) = π^S(d,d'), поради което равенството π^S/R([d],[d']) = 1 ще бъде равносилно със съотношението dRd', а то от своя страна е равносилно с равенството [d] = [d'].

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