Пример

Да разгледаме структура S, удовлетворяваща следните условия:
1. Носител на S е множеството N={0,1,2,3,…}.
2. Множеството на истинност на двуместния предикатен символ p се състои от наредените двойки (d₁,d₂), където d₁,d₂∈N и d₁>d₂.
3. Всеки път, когато ω е функционален символ с ненулев брой n на аргументите, при всеки избор на d₁, …, d_n в N са в сила неравенствата ω^S(d₁,…,d_n)≥d_i, i=1,…,n.

Очевидно формулата ∃x p(x,y) е тъждествено вярна в структурата S. Нека σ е произволна субституция, за която x е променлива на терма σy (най-простата такава субституция е [y/x]). Ще покажем, че формулата ∃x p(x,σy) не е изпълнима в S. За целта първо отбелязваме, че за всеки терм τ, всяка негова променлива ξ и всяка оценка v е в сила неравенството τ^S,v≥v(ξ) (това се доказва чрез индукция, съобразена с дефиницията за терм). Да допуснем сега, че формулата ∃x p(x,σy) е вярна в S при някоя оценка v. Тогава ще съществува такъв елемент d на N, че формулата p(x,σy) да е вярна в S при оценката v[x→d], т.е. да е в сила неравенството d>(σy)^S,v[x→d]. Това обаче е невъзможно, защото (σy)^S,v[x→d]≥v[x→d](x)=d.

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