|
|
Теорема на Ербран. Ако едно множество от безкванторни формули не притежава модел, то някое крайно множество от затворени частни случаи на формули от това множество е неизпълнимо.
Доказателство. Нека е дадено едно множество Γ от безкванторни формули, което не притежава модел. Тогава, както знаем, множеството Γ° на всички техни затворени частни случаи е неизпълнимо. За всяка формула F от Γ° да изберем по едно крайно множество ΔF от затворени дизюнкти, което я представя. Нека Δ е обединението на така избраните множества от дизюнкти, т.е. Δ се състои от онези дизюнкти, които принадлежат поне на едно от множествата ΔF . Очевидно Δ е едно неизпълнимо множество от затворени дизюнкти. По следствието от теоремата за компактност за затворени дизюнкти някое крайно подмножество на Δ също е неизпълнимо. То обаче се съдържа в обединението на множествата ΔF1, …, ΔFn , съответни на някои краен брой F1, …, Fn от Γ°. Ясно е, че и множеството на формулите F1, …, Fn също ще е неизпълнимо. □
Забележка. Теоремата на Ербран често се изказва в следния вид, равносилен на горния: ако едно множество от универсални затворени формули е неизпълнимо, то някое крайно множество от затворени частни случаи на техни безкванторни части също е неизпълнимо.
Последно изменение: 16.06.2004 г.
|
|