| Съдържание |
Теорема на Льовенхайм-Скулем. Нека е дадена една сигнатура с предикатен символ за равенство. Ако едно множество от формули при тази сигнатура има в предикатното смятане с равенство модел с безкраен носител, то това множество има в предикатното смятане с равенство модел с изброим носител.
Доказателство. Да означим дадената сигнатура със Σ. Без да ограничаваме общността можем да предполагаме, че тя има поне една константа. Нека Γ е множество от формули при сигнатура Σ, което има в предикатното смятане с равенство някакъв модел S с безкраен носител. Без ограничение на общността можем да считаме, че множеството Γ няма в предикатното смятане с равенство модели с краен носител – това бихме могли да осигурим, като за всяко положително цяло число n добавим към Γ някоя затворена формула, която е вярна в нормалните структури, имащи поне n+1 елемента в носителя, но не е вярна в никоя нормална структура, чийто носител е с по-малък брой елементи (например формула от вида ∃ξ0∃ξ1…∃ξnφ, където ξ0, ξ1, …, ξn са различни помежду си променливи, а φ е конюнкция на всички литерали ¬(ξi=ξj), i=0,1,…,n−1, j=i+1,…,n, взети в някаква последователност). Да означим с Ε множеството на аксиомите на равенството при сигнатура Σ. Структурата S е модел на обединението Γ∪Ε в общото предикатно смятане. Като използваме привеждане в пренексен вид и скулемизация, можем в подходящо разширение Σ′ на сигнатурата Σ да намерим такова множество Γ′ от безкванторни формули, че Γ′ има модел в общото предикатно смятане и всеки такъв модел е обогатяване на някой модел на множеството Γ∪Ε в общото предикатно смятане, имащ сигнатура Σ. Понеже формулите от множеството Γ′ са безкванторни и сигнатурата Σ′ има поне една константа, сред моделите на това множество в общото предикатно смятане има и такъв, на който носител е множеството на затворените термове при сигнатура Σ′ (вж. следствието от твърдение 2 в текста „Свеждане на въпроса за съществуване на модел за множество от дизюнкти към същия въпрос за множество от затворени дизюнкти“). Нека S′ е такъв модел на Γ′. Той е обогатяване на някой модел S на множеството Γ∪Ε в общото предикатно смятане, който е със сигнатура Σ, и той разбира се ще има същия носител както S′. Благодарение на това, че в структурата S са верни аксиомите на равенството при нейната сигнатура, съществува такава конгруентност R в S, че фактор-структурата S/R е нормална. Тъй като формулите от Γ са тъждествено верни в S, те са тъждествено верни и в S/R, т.е. структурата S/R е модел за Γ. В такъв случай носителят на структурата S/R е длъжен да бъде безкраен. От друга страна той като фактор-множество на най-много изброимия носител на структурата S също е най-много изброим. Следователно носителят на S/R е изброим. □
Забележка. В днешно време под теорема на Льовенхайм-Скулем често се разбира и по-силното твърдение, което се получава от горната теорема, като се заменят думите „изброим носител“ с думите „произволна безкрайна мощност на носителя“.
Теоремата на Льовенхайм-Скулем поражда един интересен въпрос във връзка с аксиоматичните системи на теорията на множествата. Ако използваме формално записване, една система от аксиоми за теорията на множествата може да се представи като множество, състоящо се от някои затворени формули на предикатното смятане при подходяща сигнатура, за която можем да приемем, че е с предикатен символ за равенство. За да има оправдание доказването на теореми въз основа на споменатата система от аксиоми, много е желателно това множество да притежава модел в предикатното смятане с равенство. Но тогава според теоремата на Льовенхайм-Скулем въпросното множество трябва да има в предикатното смятане с равенство и модел S с някакъв изброим носител D, а това е в привидно противоречие с доказваното в теорията на множествата съществуване на неизброими множества. Скулем е обяснил защо това противоречие е само привидно. А именно – за кое да е множество d в смисъл на S разбира се елементите на D, които принадлежат на d в смисъл на S, образуват множество, равномощно с множеството на естествените числа или с някое негово крайно подмножество, но съответствието, което установява тази равномощност, не е задължено да се представя с функция в смисъл на модела S.
Последно изменение: 9.02.2009 г.