| Съдържание |
Теорема за компактност за предикатното смятане с равенство. Нека е дадена една сигнатура с предикатен символ за равенство. Ако едно множество от формули при тази сигнатура не притежава модел в предикатното смятане с равенство, то и някое крайно подмножество на това множество не притежава модел в предикатното смятане с равенство.
Доказателство. Нека Γ е множество от формули при дадената сигнатура, което не притежава модел в предикатното смятане с равенство. Да означим с Ε множеството на аксиомите на равенството. Тогава обединението на Γ и Ε не притежава модел в общото предикатно смятане и следователно някое крайно подмножество Β на това обединение също не притежава модел в общото предикатно смятане. Да означим с Γ0 сечението на Β и Γ. Очевидно Γ0 е крайно подмножество на Γ. Тъй като Β се съдържа в обединението на Γ0 и Ε, това обединение нв притежава модел в общото предикатно смятане и следователно Γ0 не притежава модел в предикатното смятане с равенство. □
Разбира се от теоремата за компактност за предикатното смятане с равенство е ясно, че ако при сигнатура с предикатен символ за равенство всяко крайно подмножество на едно множество от формули притежава модел в предикатното смятаме с равенство, то и цялото множество притежава модел в предикатното смятане с равенство. Това твърдение, което очевидно е равносилно на теоремата. има интересни приложения.
Пример 1. Нека Σ е сигнатура с предикатен символ за равенство, а Γ е множество от формули при тази сигнатура, което притежава в предикатното смятане с равенство модел с безкраен носител (в частност, Γ би могло да бъде множеството на всички формули при сигнатура Σ, които са тъждествено верни в дадена нормална структура с тази сигнатура и с носител множеството на естествените числа). Ще покажем, че Γ притежава в предикатното смятане с равенство модел, в който някой елемент на носителя не е явно определим (т.е. не е стойност на никакъв затворен терм). За целта да разширим сигнатурата Σ чрез добавяне на една нова константа α и да означим с Γ′ множеството, състоящо се от формулите от Γ и от всички литерали от вида ¬(α=τ), където τ е затворен терм при сигнатура Σ. Всяко крайно подмножество на Γ′ има нормален модел. И наистина, нека Β е произволно крайно подмножество на Γ. На Β могат да принадлежат само краен брой литерали от гореспоменатия вид. По предположение съществува нормална структура S със сигнатура Σ и с безкраен носител, която е модел за Γ. При това положение в качеството на нормален модел на Β можем да използваме подходящо обогатяване на структурата S – такова, при което константата α се интерпретира като някой елемент на носителя на S, различен от стойностите в S на термовете τ, фигуриращи във въпросните краен брой литерали. Щом всяко крайно подмножество на Γ′ има нормален модел, цялото множество Γ′ също притежава нормален модел. Той е някоя нормална структура S′ с разглежданата разширена сигнатура и в него стойността на константата α е различна от стойността на кой да е затворен терм при сигнатура Σ. Тази структура е обогатяване на някоя структура S′ със сигнатура Σ. Структурата S′ има желаните свойства. Действително, всички формули от Γ, бидейки тъждествено верни в S′, ще бъдат тъждествено верни и в S′. От друга страна стойността на α в S′ е елемент на носителя на S′ и е различна от стойността в S′ на кой да е затворен терм при сигнатура Σ.
Пример 2. Това, което установихме в горния пример, допуска усилване, а именно при същите предположения може да се твърди, че множеството Γ притежава в предикатното смятане с равенство модел, в който безбройно много елементи на носителя не са явно определими. За целта вместо разширяването на сигнатурата Σ чрез добавяне само на една нова константа бихме могли да добавим към Σ безбройно много различни нови константи α0, α1, α2, …, а под Γ′ да разбираме множеството, получено от Γ чрез добавяне на всички литерали от вида ¬(αi=τ), където τ е затворен терм при сигнатура Σ, и всички литерали от вида ¬(αi=αj), където i<j.
Последно изменение: 18.01.2010 г.