Twierdzenie Trachtenbrota

W logice , teorii modeli skończonych i teorii obliczalności , twierdzenie Trakhtenbrota (dzięki Borisowi Trakhtenbrotowi ) stwierdza, że problem ważności w logice pierwszego rzędu w klasie wszystkich skończonych modeli jest nierozstrzygalny . W rzeczywistości klasa poprawnych zdań nad skończonymi modelami nie jest przeliczalna rekurencyjnie (chociaż jest przeliczalna współrekurencyjnie ).

Twierdzenie Trakhtenbrota implikuje, że twierdzenie Gödla o zupełności (które jest fundamentalne dla logiki pierwszego rzędu) nie obowiązuje w skończonym przypadku. Wydaje się również sprzeczne z intuicją, że bycie ważnym dla wszystkich struktur jest „łatwiejsze” niż tylko dla skończonych.

Twierdzenie zostało po raz pierwszy opublikowane w 1950 roku: „Niemożliwość algorytmu dla problemu rozstrzygalności w klasach skończonych”.

Sformułowanie matematyczne

Postępujemy zgodnie ze sformułowaniami jak u Ebbinghausa i Fluma

Twierdzenie

Spełnialność struktur skończonych nie jest rozstrzygalna w logice pierwszego rzędu .

To znaczy zbiór {φ | φ jest zdaniem logiki pierwszego rzędu, które jest spełnialne wśród struktur skończonych} jest nierozstrzygalne.

Następstwo

Niech σ będzie słownikiem relacyjnym z co najmniej jednym binarnym symbolem relacji.

Zbiór σ-zdań obowiązujących we wszystkich skończonych strukturach nie jest rekurencyjnie przeliczalny .

Uwagi

Oznacza to, że twierdzenie Gödla o kompletności zawodzi w skończoności, ponieważ kompletność implikuje rekurencyjną wyliczalność.
Wynika z tego, że nie ma funkcji rekurencyjnej f takiej, że: jeśli φ ma model skończony, to ma model o rozmiarze co najwyżej f(φ). Innymi słowy, nie ma skutecznego odpowiednika twierdzenia Löwenheima-Skolema w skończoności.

Dowód intuicyjny

Ten dowód pochodzi z rozdziału 10, sekcja 4, 5 Logiki matematycznej autorstwa H.-D. Ebbinghausa.

$M} można$ w najczęstszym dowodzie pierwszego twierdzenia Gödla o niezupełności przy użyciu nierozstrzygalności problemu zatrzymania , dla każdej maszyny Turinga istnieje odpowiednie zdanie arytmetyczne , M $\ displaystyle$ $wyprowadzić$ z , tak że jest prawdziwe wtedy i tylko wtedy, gdy $się$ pustej taśmie. Intuicyjnie, ${\ Displaystyle \ phi _ {M}}$ $,$ że „istnieje liczba naturalna, która jest kodem Gödla dla zapisu obliczeń pustej taśmie, która kończy się zatrzymaniem”.

Jeśli maszyna zatrzymuje się w $skończonych$ krokach, to pełny zapis obliczeń jest również skończony, to istnieje skończony początkowy segment liczb naturalnych taki, że zdanie arytmetyczne $} }}$ jest również prawdziwe w tym początkowym segmencie. Intuicyjnie $dzieje$ się tak, ponieważ w tym przypadku udowodnienie arytmetycznych tylko skończenie wielu liczb.

Jeśli maszyna nie zatrzymuje się w skończonych krokach, to $jest$ $\ displaystyle M}$ w każdym skończonym modelu, ponieważ nie ma skończonego zapisu obliczeń , który $}$ kończy się zatrzymaniem.

$.$ , jeśli $zatrzymuje$ się, jest prawdziwe w niektórych skończonych Jeśli nie zatrzymuje się, $to$ $we$ wszystkich skończonych modelach $prawdziwe$ więc nie zatrzymuje się wtedy i tylko wtedy, gdy $we$ skończonych modelach

Zbiór maszyn, który się nie zatrzymuje, nie jest przeliczalny rekurencyjnie, więc zbiór poprawnych zdań na skończonych modelach nie jest przeliczalny rekurencyjnie.

Alternatywny dowód

W tej sekcji przedstawimy bardziej rygorystyczny dowód Libkina. Zauważ w powyższym stwierdzeniu, że wniosek pociąga za sobą również twierdzenie, i to jest kierunek, w którym tutaj dowodzimy.

Twierdzenie

Dla każdego słownika relacyjnego τ z co najmniej jednym symbolem relacji binarnej nie można rozstrzygnąć, czy zdanie φ słownika τ jest skończenie spełnialne.

Dowód

Zgodnie z poprzednim lematem możemy faktycznie użyć skończenie wielu symboli relacji binarnych. Idea dowodu jest podobna do dowodu twierdzenia Fagina, a maszyny Turinga kodujemy w logice pierwszego rzędu. Chcemy udowodnić, że dla każdej maszyny Turinga M konstruujemy zdanie φ _M słownictwa τ takie, że φ _M jest skończenie spełnialne wtedy i tylko wtedy, gdy M zatrzymuje się na pustym wejściu, co jest równoważne problemowi zatrzymania, a zatem jest nierozstrzygalne.

₀ Niech M= ⟨Q, Σ, δ, q , Q _a , Q _r ⟩ będzie deterministyczną maszyną Turinga z pojedynczą nieskończoną taśmą.

Q to zbiór stanów,
Σ to alfabet wejściowy,
Δ to alfabet taśmy,
δ jest funkcją przejścia,
₀ q to stan początkowy,
Q _a i Q _r to zbiory stanów akceptujących i odrzucających.

Ponieważ mamy do czynienia z problemem zatrzymania na pustym wejściu, możemy założyć wlog, że Δ={0,1} i że 0 oznacza spację, a 1 jakiś symbol taśmy. Definiujemy τ, abyśmy mogli reprezentować obliczenia:

₀ τ := {<, min , T (⋅,⋅), T ₁ (⋅,⋅), (H _q (⋅,⋅)) _{(q ∈ Q)} }

Gdzie:

< jest porządkiem liniowym, a min jest stałym symbolem elementu minimalnego względem < (nasza skończona dziedzina będzie powiązana z początkowym segmentem liczb naturalnych).
₀ T i T1 _to predykaty taśmowe. T _i (s,t) wskazuje, że pozycja s w czasie t zawiera i, gdzie i ∈ {0,1}.
H _q to predykaty głowy. H _q (s,t) wskazuje, że w chwili t maszyna znajduje się w stanie q, a jej głowica znajduje się w pozycji s.

Zdanie φ _M stwierdza, że (i) <, min , T _i oraz H _q są interpretowane jak powyżej oraz (ii) że maszyna ostatecznie się zatrzymuje. Warunek zatrzymania jest równoznaczny ze stwierdzeniem, że H _q∗ (s, t) zachodzi dla pewnych s, t i q∗ ∈ Q _a ∪ Q _r i po tym stanie konfiguracja maszyny się nie zmienia. Konfiguracje zatrzymującej się maszyny (brak zatrzymania nie jest skończony) można przedstawić jako zdanie τ (skończone) (a dokładniej skończoną strukturę τ, która spełnia zdanie). Zdanie φ _M jest: φ ≡ α ∧ β ∧ γ ∧ η ∧ ζ ∧ θ.

Rozkładamy to na składniki:

α stwierdza, że < jest porządkiem liniowym, a min jest jego minimalnym elementem
₀₀ γ definiuje początkową konfigurację M: jest w stanie q , głowa jest w pierwszej pozycji, a taśma zawiera tylko zera: γ ≡ H _{q ₀} ( min , min ) ∧ ∀s T (s, min )
₀ η stwierdza, że w każdej konfiguracji M każda komórka taśmowa zawiera dokładnie jeden element Δ: ∀s∀t(T (s, t) → ¬ T ₁ (s, t))
β nakłada podstawowy warunek spójności na predykaty H _q 's: w dowolnym momencie maszyna znajduje się dokładnie w jednym stanie:

{\ Displaystyle \ forall t \ istnieje! w Q,q\neq q}H_{q}(s,t)\land H_{q'}(s,t))} ζ stwierdza, że ​​w pewnym momencie M jest w stanie zatrzymania

:

{\ Displaystyle \ istnieje s \ istnieje t \ bigvee _ {q \ w Q_ {a} \ kubek Q_ {r}} H_ {q} (s, t)}

θ składa się z koniunkcji zdań stwierdzających, że T _i 's i H _q₀ 's zachowują się dobrze w odniesieniu do przejść M. Na przykład niech δ(q,0)=(q',1, left) oznacza, że jeśli M jest w stanie q czytając 0, to zapisuje 1, porusza się głowę o jedną pozycję w lewo i przechodzi w stan q'. Reprezentujemy ten warunek przez dysjunkcję θ i θ ₁ :

{\ Displaystyle \ theta _ {0} \ równoważnik \ forall s \ forall t (s \ neq {\ podkreślenie {min}} \ ziemia T_ {0} (s, t) \ ziemia H_ {q} (s,t))\do \theta _{2}}

gdzie θ2 _wynosi :

{\ Displaystyle T_ {1} (s, t + 1) \ ziemia H_ {q '} (s-1, t + 1) \ ziemia \ forall s '(s \ neq s' \ do (\bigwedge _{i=0,1}T_{i}(s',t+1)\leftrightarrow T_{i}(s',t)))}

I:

{\ Displaystyle \ theta _ {1} \ równoważnik \ dla wszystkich s \ dla wszystkich t (s={\podkreślenie {min}}\kraj T_{0}(s,t)\kraj H_{q}(s,t))\to \theta_{3}}

gdzie θ3 _wynosi :

${\ Displaystyle T_ {1} (s, t + 1) \ ziemia H_ {q '} (s, t + 1) \ ziemia \ forall s '(s \ neq s' \ do (\ bigwedge _ {i=0,1}T_{i}(s',t+1)\leftrightarrow T_{i}(s',t))}}$

₀ s-1 i t+1 są definiowalnymi skrótami pierwszego rzędu dla poprzednika i następnika zgodnie z uporządkowaniem <. Zdanie θ zapewnia, że zawartość taśmy na pozycji s zmienia się z 0 na 1, stan zmienia się z q na q', reszta taśmy pozostaje taka sama i że głowa przesuwa się do s-1 (czyli o jedną pozycję w lewo ), zakładając, że s nie jest pierwszą pozycją na taśmie. Jeśli tak, to wszystko jest obsługiwane przez θ ₁ : wszystko jest takie samo, z wyjątkiem tego, że głowa nie przesuwa się w lewo, ale pozostaje w miejscu.

Jeśli φ _M ma model skończony, to taki model, który reprezentuje obliczenie M (które zaczyna się od pustej taśmy (tj. taśmy zawierającej wszystkie zera) i kończy się stanem zatrzymania). Jeśli M zatrzymuje się na pustym wejściu, to zbiór wszystkich konfiguracji obliczeń zatrzymania M (kodowanych za pomocą <, T i _i H _q s) jest modelem φ _M , który jest skończony, ponieważ zbiór wszystkie konfiguracje obliczeń zatrzymujących są skończone. Wynika z tego, że M zatrzymuje się na pustym wejściu iff φ _M ma skończony model. Ponieważ zatrzymanie się na pustym wejściu jest nierozstrzygalne, tak samo pytanie, czy φ _M ma skończony model $mathcal {A}}}$ równoważnie, czy φ _M jest skończenie spełnialne) jest również nierozstrzygalne (rekurencyjnie przeliczalne, ZA {\ displaystyle {\ ale nie rekurencyjne). To kończy dowód.

Następstwo

Zbiór zdań skończenie spełnialnych jest rekurencyjnie przeliczalny.

Dowód

Wylicz wszystkie pary $mathcal {A}}, \ phi)}$ $\$ gdzie jest i ${\ Displaystyle {\ mathcal { A}}\modele \phi}$ .

Następstwo

Dla dowolnego słownika zawierającego co najmniej jeden symbol relacji binarnej zbiór wszystkich skończenie ważnych zdań nie jest rekurencyjnie przeliczalny.

Dowód

Z poprzedniego lematu zbiór zdań skończenie spełnialnych jest rekurencyjnie przeliczalny. Załóżmy, że zbiór wszystkich skończenie ważnych zdań jest rekurencyjnie przeliczalny. Ponieważ ¬φ jest skończenie ważne, jeśli φ nie jest skończenie spełnialne, wnioskujemy, że zbiór zdań, które nie są skończenie spełnialne, jest rekurencyjnie przeliczalny. Jeśli zarówno zbiór A, jak i jego uzupełnienie są rekurencyjnie przeliczalne, to A jest rekurencyjne. Wynika z tego, że zbiór zdań skończenie spełnialnych jest rekurencyjny, co jest sprzeczne z twierdzeniem Trakhtenbrota.

^ Trachtenbrot, Borys (1950). „Niemożliwość algorytmu dla problemu rozstrzygalności w klasach skończonych”. Materiały Akademii Nauk ZSRR (w języku rosyjskim). 70 (4): 569–572.
Bibliografia _ _ Flum, Jörg (1995). Teoria modeli skończonych . Springer Science+Business Media. ISBN 978-3-540-60149-4 .
^ Libkin, Leonid (2010). Elementy teorii modeli skończonych . Teksty z informatyki teoretycznej . ISBN 978-3-642-05948-3 .

Boolos, Burgess, Jeffrey. Obliczalność i logika , Cambridge University Press, 2002.
Simpson, S. „Twierdzenia Kościoła i Trachtenbrota”. 2001. [1]

[1] Trachtenbrot, Borys (1950). „Niemożliwość algorytmu dla problemu rozstrzygalności w klasach skończonych”. Materiały Akademii Nauk ZSRR (w języku rosyjskim). 70 (4): 569–572.

[2] Bibliografia _ _ Flum, Jörg (1995). Teoria modeli skończonych . Springer Science+Business Media. ISBN 978-3-540-60149-4 .

[3] Libkin, Leonid (2010). Elementy teorii modeli skończonych . Teksty z informatyki teoretycznej . ISBN 978-3-642-05948-3 .