Ponieważ istnieją cykle o dowolnie dużej, skończonej liczbie wierzchołków, oznacza to, że ψ ma dowolnie duży, skończony model. Na podstawie twierdzenia Löwenheima-Skolema wiadomo, że jeśli jakiś zbiór formuł ma modele dowolnych mocy skończonych to ma również model nieskończony. Nazwijmy go G∞. To prowadzi do sprzeczności, ponieważ w takim wypadku (na mocy zdania ψ2) istnieje taki element t uniwersum modelu G∞, że spełniona jest relacja G∞(t,0) co jednak jest sprzeczne z nieskończoną mocą tego modelu (nie istnieją cykle nieskończone).
W przypadku logiki drugiego rzędu (dla której twierdzenie Löwenheima-Skolema w ogólności nie obowiązuje) wyrażenie φ(x,y) istnieje, np:
φ(x,y) = ~∃R2(∀u∀v∀w(R(u,u) ∧ (G(u,v) ⇒ R(u,v)) ∧ ((R(u,v) ∧ R(v,w)) ⇒ R(u,w))) ∧ ~R(x,y))
Można zauważyć, że skoro R jest zwrotnym, przechodnim domknięciem G (na mocy trzech pierwszych warunków z koniunkcji), to ~R(x,y) implikuje, że nie istnieje ścieżka z x do y. Zatem zanegowanie całego wyrażenia jest szukanym φ(x,y).
Zobacz też Rachunek predykatów pierwszego rzędu Twierdzenie Löwenheima-Skolema
Przypisy
Bibliografia
Kategoria:Logika matematyczna