Oryginalny dowód twierdzenia Gödla o kompletności - Original proof of Gödel's completeness theorem

Dowód twierdzenia Gödla o zupełności podany przez Kurta Gödla w jego rozprawie doktorskiej z 1929 r. (I krótsza wersja dowodu, opublikowana jako artykuł w 1930 r. Zatytułowana „Kompletność aksjomatów rachunku funkcjonalnego logiki” (w języku niemieckim) ) nie jest dziś łatwe do odczytania; używa pojęć i formalizmów, które nie są już używane, oraz terminologii, która jest często niejasna. Wersja podana poniżej jest próbą wiernego odzwierciedlenia wszystkich etapów dowodu i wszystkich ważnych idei, przy jednoczesnym powtórzeniu dowodu we współczesnym języku logiki matematycznej . Ten zarys nie powinien być traktowany jako rygorystyczny dowód twierdzenia.

Założenia

Pracujemy z rachunkiem predykatów pierwszego rzędu . Nasze języki dopuszczają symbole stałe, funkcyjne i relacyjne. Struktury składają się z (niepustych) domen i interpretacji odpowiednich symboli jako stałych członków, funkcji lub relacji w tej dziedzinie.

Zakładamy logikę klasyczną (w przeciwieństwie na przykład do logiki intuicjonistycznej).

Naprawiamy pewną aksjomatyzację (tj. Oparty na składni, obsługiwany przez maszynę system dowodowy) rachunku predykatów: aksjomaty logiczne i reguły wnioskowania. Dowolna z kilku dobrze znanych równoważnych aksjomatyzacji wystarczy. Oryginalny dowód Gödla zakładał system dowodowy Hilberta-Ackermanna.

Zakładamy bez dowodu wszystkie podstawowe dobrze znane wyniki dotyczące naszego formalizmu, których potrzebujemy, takie jak twierdzenie o postaci normalnej lub twierdzenie o poprawności .

Aksjomatyzujemy rachunek predykatów bez równości (czasami myląco nazywany bez tożsamości ), tj. Nie ma specjalnych aksjomatów wyrażających właściwości równości (przedmiotu) jako specjalnego symbolu relacji. Po udowodnieniu podstawowej postaci twierdzenia łatwo będzie rozszerzyć je na przypadek rachunku predykatów z równością .

Stwierdzenie twierdzenia i jego dowód

Poniżej podajemy dwie równoważne formy twierdzenia i pokazujemy ich równoważność.

Później udowodnimy to twierdzenie. Odbywa się to w następujących krokach:

1. Sprowadzenie twierdzenia do zdań (formuł bez wolnych zmiennych) w postaci przedrostka , czyli ze wszystkimi kwantyfikatorami ( ∀ i ∃ ) na początku. Ponadto redukujemy to do formuł, których pierwszym kwantyfikatorem jest ∀ . Jest to możliwe, ponieważ dla każdego zdania istnieje odpowiednik w formie przedrostka, którego pierwszym kwantyfikatorem jest ∀ .
2. Sprowadzając twierdzenie do zdań o postaci ∀ x ₁ ∀ x ₂ ... ∀ x _k ∃ y ₁ ∃ y ₂ ... ∃ y _m φ ( x ₁ ... x _k , y ₁ ... y _m ) . Chociaż nie możemy tego zrobić, po prostu przestawiając kwantyfikatory, pokazujemy, że wystarczy udowodnić twierdzenie dla zdań w tej formie.
3. Na koniec udowodnimy twierdzenie dla zdań o tej formie.
   • W tym celu należy najpierw zauważyć, że zdanie takie jak B = ∀ x ₁ ∀ x ₂ ... ∀ x _k ∃ y ₁ ∃ y ₂ ... ∃ y _m φ ( x ₁ ... x _k , y ₁ . .. y _m ) jest albo obalalna (jej negacja jest zawsze prawdziwa), albo spełnialna, tj. istnieje pewien model, w którym się utrzymuje (może nawet zawsze jest prawdziwa, tj. tautologia); model ten polega po prostu na przypisywaniu wartości prawdziwości do podpozycji, z których zbudowano B. Powodem tego jest kompletność logiki zdań , w której egzystencjalne kwantyfikatory nie odgrywają żadnej roli.
   • Rozszerzamy ten wynik na coraz bardziej złożone i długie zdania, D _n (n = 1,2 ...), zbudowane z B, tak że którekolwiek z nich jest obalalne, a zatem tak jest φ, albo wszystkie są nie do obalenia i dlatego każdy zachowuje się w pewnym modelu.
   • Na koniec używamy modeli, w których trzymanie D _n (na wypadek, gdyby wszystkie nie były obalalne), aby zbudować model, w którym utrzymuje się φ.

Twierdzenie 1. Każdy poprawny wzór (prawdziwy we wszystkich strukturach) jest możliwy do udowodnienia.

To jest najbardziej podstawowa forma twierdzenia o zupełności. Natychmiast przedstawiamy to w formie wygodniejszej dla naszych celów: kiedy mówimy „wszystkie struktury”, ważne jest, aby sprecyzować, że są to klasyczne (Tarskianowskie) interpretacje I, gdzie I = <U, F> (U jest a niepusty (prawdopodobnie nieskończony) zbiór obiektów, podczas gdy F to zbiór funkcji z wyrażeń zinterpretowanej symboliki do U). [Dla kontrastu, tak zwane oblicze „wolnej logiki” może być pustymi zbiorami dla U. Więcej na temat logiki swobodnej można znaleźć w pracy Karela Lamberta.]

Twierdzenie 2. Każdy wzór φ można obalić lub spełnić w jakiejś strukturze.

„φ można obalić” oznacza z definicji „¬φ można udowodnić”.

Równoważność obu twierdzeń

Jeśli Twierdzenie 1 jest prawdziwe, a φ nie jest spełnialne w żadnej strukturze, to ¬φ jest ważne we wszystkich strukturach, a zatem można je udowodnić, a zatem φ można obalić, a Twierdzenie 2 jest prawdziwe . Jeśli z drugiej strony Twierdzenie 2 jest prawdziwe, a φ jest ważne we wszystkich strukturach, to ¬φ nie jest zadowalające w żadnej strukturze i dlatego można je obalić; wtedy ¬¬φ da się udowodnić, a potem φ, tak więc Twierdzenie 1 zachodzi.

Dowód twierdzenia 2: pierwszy krok

Dochodzimy do dowodu Twierdzenia 2 , sukcesywnie ograniczając klasę wszystkich formuł φ, dla których musimy udowodnić, że „φ jest albo obalalna, albo spełniona”. Na początku musimy to udowodnić dla wszystkich możliwych formuł φ w naszym języku. Załóżmy jednak, że dla każdej formuły φ istnieje jakaś formuła ψ zaczerpnięta z bardziej ograniczonej klasy formuł C , taka że „ψ można obalić lub spełnić” → „φ można obalić lub spełnić”. Wtedy, gdy to twierdzenie (wyrażone w poprzednim zdaniu) zostanie udowodnione, to wystarczy, aby udowodnić „φ jest albo obalenia lub spełnialna” tylko dla φ przynależności do klasy C . Jeśli φ jest możliwe do udowodnienia równoważne z ψ ( tj. (Φ≡ψ) jest możliwe do udowodnienia), to rzeczywiście jest tak, że „ψ można obalić lub zadowalać” → „φ można obalić lub zadowalać” ( twierdzenie o poprawności jest potrzebne do Pokaż to).

Istnieją standardowe techniki przepisywania dowolnego wzoru na taki, który nie używa symboli funkcyjnych ani stałych, kosztem wprowadzenia dodatkowych kwantyfikatorów; założymy zatem, że wszystkie formuły są wolne od takich symboli. Artykuł Gödla używa wersji rachunku predykatów pierwszego rzędu, która nie ma na początku żadnej funkcji ani stałych symboli.

Następny uważamy wzór ogólny cp (co funkcjonować nie używa lub stałe symbole) i zastosować formularz prenex twierdzenie znaleźć * F formułę w postaci normalnej taka, że φ≡ψ (ψ jest w postaci normalnej oznacza, że wszystkie kwantyfikatory w * F, jeśli są, znajdują się na samym początku ψ). Wynika z tego, że musimy tylko udowodnić Twierdzenie 2 dla formuł φ w postaci normalnej.

Następnie eliminujemy wszystkie zmienne wolne z φ przez kwantyfikację ich egzystencjalnie: jeśli, powiedzmy, x ₁ ... x _n są wolne w φ, tworzymy . Jeśli ψ jest spełnialne w strukturze M, to z pewnością tak samo jest z φ, a jeśli ψ można obalić, to można je udowodnić, a następnie ¬φ, a zatem φ można obalić. Widzimy, że możemy ograniczyć φ do zdania , czyli formuły bez wolnych zmiennych. ${\ Displaystyle \ psi = \ istnieje x_ {1} ... \ istnieje x_ {n} \ phi}$${\ displaystyle \ neg \ psi = \ forall x_ {1} ... \ forall x_ {n} \ neg \ phi}$

Na koniec chcielibyśmy, ze względów technicznych, aby przedrostek φ (czyli ciąg kwantyfikatorów na początku φ, który ma postać normalną) zaczynał się od kwantyfikatora uniwersalnego i kończył kwantyfikatorem egzystencjalnym. Aby to osiągnąć dla ogólnego φ (z zastrzeżeniem ograniczeń, które już udowodniliśmy), bierzemy jakiś jednomiejscowy symbol relacji F nieużywany w φ i dwie nowe zmienne y i z .. Jeśli φ = (P) Φ , gdzie (P ) oznacza przedrostek φ i Φ dla macierzy (pozostałej, wolnej od kwantyfikatorów części φ), którą tworzymy . Ponieważ jest to łatwe do udowodnienia, łatwo jest to udowodnić. ${\ Displaystyle \ psi = \ forall r (P) \ istnieje z (\ Phi \ klin [F (r) \ vee \ neg F (z)])}$${\ Displaystyle \ forall y \ istnieje z (F (r) \ vee \ neg F (z))}$${\ displaystyle \ phi = \ psi}$

Sprowadzając twierdzenie do wzorów stopnia 1

Nasza formuła ogólna φ jest teraz zdaniem w formie normalnej, a jej przedrostek zaczyna się od uniwersalnego kwantyfikatora, a kończy kwantyfikatorem egzystencjalnym. Nazwijmy klasę wszystkich takich wzorach R . Musimy udowodnić, że każda formuła w R jest możliwa do obalenia lub zadowalająca. Biorąc pod uwagę naszą formułę we, grupujemy ciągi kwantyfikatorów jednego rodzaju w bloki:

${\ Displaystyle \ phi = (\ forall x_ {1} ... \ forall x_ {k_ {1}}) (\ istnieje x_ {k_ {1} +1} ... \ istnieje x_ {k_ {2}} ) ....... (\ dla wszystkich x_ {k_ {n-2} +1} ... \ dla wszystkich x_ {k_ {n-1}}) (\ istnieje x_ {k_ {n-1} +1 } ... \ istnieje x_ {k_ {n}}) (\ Phi)}$

Określamy stopień o być liczba uniwersalnych bloków kwantyfikator rozdzielonych bloków kwantyfikatorem egzystencjalnym, jak wykazano powyżej, w prefiksu . Poniższy lemat, który Gödel zaadaptował z dowodu Skolema na twierdzenie Löwenheima-Skolema , pozwala nam ostro zredukować złożoność formuły rodzajowej, dla której potrzebujemy udowodnić twierdzenie: ${\ displaystyle \ phi}$${\ displaystyle \ phi}$${\ displaystyle \ phi}$

Lemat . Niech k > = 1. Jeśli każda formuła w R stopnia k jest obalalna lub zadowalająca, to tak samo jest z każdą formułą w R stopnia k + 1 .

Komentarz : Weź wzór φ stopnia k + 1 postaci , gdzie jest reszta (jest to więc stopień k-1 ). φ stwierdza, że ​​dla każdego x jest takie, że ... (coś). Byłoby miło mieć predykat Q ', tak aby dla każdego x, Q' (x, y) było prawdziwe wtedy i tylko wtedy, gdy y jest wymagane, aby (coś) było prawdą. Wtedy moglibyśmy napisać wzór na stopień k, który jest równoważny z φ, a mianowicie . Ta formuła jest rzeczywiście równoważna φ, ponieważ stwierdza, że ​​dla każdego x, jeśli istnieje ay, które spełnia Q '(x, y), to (coś) zachodzi, a ponadto wiemy, że istnieje takie ay, ponieważ dla każdego x ', istnieje ay', które spełnia Q '(x', y '). Dlatego φ wynika z tego wzoru. Łatwo też wykazać, że jeśli formuła jest fałszywa, to tak samo jest z φ. Niestety , generalnie nie ma takiego predykatu Q '. Jednak ideę tę można rozumieć jako podstawę dla następującego dowodu lematu. ${\ Displaystyle \ phi = (\ forall x) (\ istnieje r) (\ forall u) (\ istnieje v) (P) \ psi}$${\ Displaystyle (P) \ psi}$${\ displaystyle \ phi}$${\ Displaystyle (\ forall x ') (\ forall x) (\ forall r) (\ forall u) (\ istnieje v) (\ istnieje y') (P) Q '(x', y ') \ klin ( Q '(x, y) \ rightarrow \ psi)}$

Dowód. Niech φ będzie wzorem na stopień k + 1 ; wtedy możemy to zapisać jako

${\ Displaystyle \ phi = (\ forall x) (\ istnieje r) (\ forall u) (\ istnieje v) (P) \ psi}$

gdzie (P) jest pozostałą częścią przedrostka (jest więc stopnia k-1 ) i jest macierzą wolną od kwantyfikatorów . x , y , u i v oznaczają tu raczej krotki zmiennych niż pojedyncze zmienne; np. naprawdę oznacza, gdzie są różne zmienne. ${\ displaystyle \ phi}$${\ displaystyle \ psi}$${\ displaystyle \ phi}$ ${\ displaystyle (\ forall x)}$${\ displaystyle \ forall x_ {1} \ forall x_ {2} ... \ forall x_ {n}}$${\ displaystyle x_ {1} ... x_ {n}}$

Niech teraz x ' i y' będą krotkami wcześniej nieużywanych zmiennych o takiej samej długości, jak odpowiednio x i y , i niech Q będzie wcześniej nieużywanym symbolem relacji, który przyjmuje tyle argumentów, ile jest sumą długości x i y ; rozważamy wzór

${\ Displaystyle \ Phi = (\ forall x ') (\ istnieje y') Q (x ', y') \ klin (\ forall x) (\ forall y) (Q (x, y) \ rightarrow (\ forall u) (\ istnieje v) (P) \ psi)}$

Oczywiście można to udowodnić. ${\ Displaystyle \ Phi \ rightarrow \ phi}$

Ponieważ ciąg kwantyfikatorów nie zawiera zmiennych z x lub y , następującą równoważność można łatwo udowodnić za pomocą dowolnego formalizmu, którego używamy: ${\ Displaystyle (\ forall u) (\ istnieje v) (P)}$

${\ Displaystyle (Q (x, r) \ rightarrow (\ forall u) (\ istnieje v) (P) \ psi) \ equiv (\ forall u) (\ istnieje v) (P) (Q (x, y) \ rightarrow \ psi)}$

A ponieważ te dwie formuły są równoważne, jeśli zastąpimy pierwszą drugą wewnętrzną Φ, otrzymamy wzór Φ 'taki, że Φ≡Φ':

${\ Displaystyle \ Phi '= (\ forall x') (\ istnieje y ') Q (x', y ') \ klin (\ forall x) (\ forall y) (\ forall u) (\ istnieje v) ( P) (Q (x, y) \ rightarrow \ psi)}$

Teraz Φ 'ma postać , gdzie (S) i (S') są pewnymi łańcuchami kwantyfikatorów, ρ i ρ 'są wolne od kwantyfikatorów, a ponadto żadna zmienna (S) nie występuje w ρ' i żadna zmienna (S ') występuje w ρ. W takich warunkach każda formuła postaci , gdzie (T) jest ciągiem kwantyfikatorów zawierającym wszystkie kwantyfikatory w (S) i (S ') przeplecione między sobą w dowolny sposób, ale zachowując względną kolejność wewnątrz (S) i (S') ), będzie odpowiednikiem oryginalnej formuły Φ '(jest to kolejny podstawowy wynik rachunku predykatów pierwszego rzędu, na którym się opieramy). W skrócie, tworzymy Ψ w następujący sposób: ${\ Displaystyle (S) \ rho \ klin (S ') \ rho'}$${\ Displaystyle (T) (\ rho \ wedge \ rho ')}$

${\ Displaystyle \ Psi = (\ forall x ') (\ forall x) (\ forall y) (\ forall u) (\ istnieje y') (\ istnieje v) (P) Q (x ', y') \ klin (Q (x, y) \ rightarrow \ psi)}$

i mamy . ${\ Displaystyle \ Phi '\ equiv \ Psi}$

Teraz jest formułą stopnia k, a zatem z założenia można ją obalić lub spełnić. Jeśli jest zadowalająca w strukturze M , to rozważając , widzimy, że jest również zadowalająca. Jeśli można obalić, to tak jest , co jest temu równoważne; w ten sposób można udowodnić. Teraz możemy zastąpić wszystkie wystąpienia Q w formule możliwej do udowodnienia inną formułą zależną od tych samych zmiennych i nadal otrzymamy formułę możliwą do udowodnienia. ( To jest jeszcze jeden podstawowy wynik rachunku predykatów pierwszego rzędu. W zależności od konkretnego formalizmu przyjętego do rachunku, można go postrzegać jako proste zastosowanie reguły wnioskowania o „podstawieniu funkcjonalnym”, jak w pracy Gödla, lub też być udowodnione, rozważając formalny dowód , zastępując w nim wszystkie wystąpienia Q jakąś inną formułą z tymi samymi wolnymi zmiennymi i zauważając, że wszystkie logiczne aksjomaty w formalnym dowodzie pozostają logicznymi aksjomatami po podstawieniu, a wszystkie reguły wnioskowania nadal mają zastosowanie w ten sam sposób. ) ${\ displaystyle \ Psi}$${\ displaystyle \ Psi}$${\ Displaystyle \ Psi \ equiv \ Phi '\ equiv \ Phi \ wedge \ Phi \ rightarrow \ phi}$${\ displaystyle \ phi}$${\ displaystyle \ Psi}$${\ displaystyle \ Phi}$${\ displaystyle \ neg \ Phi}$${\ displaystyle \ neg \ Phi}$${\ displaystyle \ neg \ Phi}$

W tym konkretnym przypadku zamieniamy Q (x ', y') na wzór . Tutaj (x, y | x ', y') oznacza, że ​​zamiast ψ piszemy inną formułę, w której x i y są zastępowane przez x 'i y'. Q (x, y) jest po prostu zastępowane przez . ${\ displaystyle \ neg \ Phi}$${\ Displaystyle (\ forall u) (\ istnieje v) (P) \ psi (x, y | x ', y')}$${\ Displaystyle (\ forall u) (\ istnieje v) (P) \ psi}$

${\ displaystyle \ neg \ Phi}$ staje się

${\ Displaystyle \ neg ((\ forall x ') (\ istnieje y') (\ forall u) (\ istnieje v) (P) \ psi (x, y | x ', y') \ klin (\ forall x ) (\ forall y) ((\ forall u) (\ exist v) (P) \ psi \ rightarrow (\ forall u) (\ exist v) (P) \ psi))}$

i ta formuła jest możliwa do udowodnienia; ponieważ część podlegająca negacji i po znaku jest oczywiście możliwa do udowodnienia, a część podlegająca negacji i przed znakiem to oczywiście φ, tylko z x i y zastąpionymi przez x ' i y' , widzimy, że jest to możliwe do udowodnienia, a φ jest obalalne. Udowodniliśmy, że φ jest zadowalające lub obalalne, a to kończy dowód lematu . ${\ displaystyle \ wedge}$${\ displaystyle \ wedge}$${\ displaystyle \ neg \ phi}$

Zauważ, że nie mogliśmy użyć zamiast Q (x ', y') od samego początku, ponieważ w tym przypadku nie byłaby to dobrze sformułowana formuła . Dlatego nie możemy naiwnie posługiwać się argumentem zawartym w komentarzu poprzedzającym dowód. ${\ Displaystyle (\ forall u) (\ istnieje v) (P) \ psi (x, y | x ', y')}$${\ displaystyle \ Psi}$

Udowodnienie twierdzenia dla wzorów stopnia 1

Jak pokazano w powyższym lemacie , musimy tylko udowodnić nasze twierdzenie dla formuł φ w R stopnia 1. φ nie może mieć stopnia 0, ponieważ wzory w R nie mają wolnych zmiennych i nie używają stałych symboli. Zatem formuła φ ma ogólną postać:

${\ displaystyle (\ forall x_ {1} ... x_ {k}) (\ istnieje y_ {1} ... y_ {m.}) \ phi (x_ {1} ... x_ {k}, y_ { 1} ... y_ {m.}).}$

Teraz możemy zdefiniować porządkuje K- krotek z liczb naturalnych w następujący sposób: należy przytrzymać jeśli albo , lub , a poprzedza w porządku leksykograficznym . [Tutaj oznacza sumę warunków krotki.] N-tą krotkę w tej kolejności oznaczamy przez . ${\ Displaystyle (x_ {1} ... x_ {k}) <(y_ {1} ... y_ {k})}$${\ Displaystyle \ Sigma _ {k} (x_ {1} ... x_ {k}) <\ Sigma _ {k} (y_ {1} ... y_ {k})}$${\ Displaystyle \ Sigma _ {k} (x_ {1} ... x_ {k}) = \ Sigma _ {k} (y_ {1} ... y_ {k})}$${\ displaystyle (x_ {1} ... x_ {k})}$${\ displaystyle (y_ {1} ... y_ {k})}$${\ Displaystyle \ Sigma _ {k} (x_ {1} ... x_ {k})}$${\ Displaystyle (a_ {1} ^ {n} ... a_ {k} ^ {n})}$

Ustaw formułę jako . Następnie umieść jako ${\ displaystyle B_ {n}}$${\ Displaystyle \ phi (z_ {a_ {1} ^ {n}} ... z_ {a_ {k} ^ {n}}, z _ {(n-1) m + 2}, z _ {(n-1) ) m + 3} ... z_ {nm + 1})}$${\ displaystyle D_ {n}}$

${\ Displaystyle (\ istnieje z_ {1} ... z_ {nm + 1}) (B_ {1} \ klin B_ {2} ... \ klin B_ {n}).}$

Lemat : dla każdego n , φ . ${\ displaystyle \ rightarrow D_ {n}}$

Dowód : przez indukcję n; mamy , gdzie ta druga implikacja zachodzi przez podstawianie zmiennych, ponieważ kolejność krotek jest taka . Ale ostatnia formuła jest równoważna φ. ${\ Displaystyle D_ {k} \ Leftarrow D_ {k-1} \ klin (\ forall z_ {1} ... z _ {(n-1) m + 1}) (\ istnieje z _ {(n-1) m +2} ... z_ {nm + 1}) B_ {n} \ Leftarrow D_ {k-1} \ wedge (\ forall z_ {a_ {1} ^ {n}} ... z_ {a_ {k} ^ {n}}) (\ istnieje y_ {1} ... y_ {m}) \ phi (z_ {a_ {1} ^ {n}} ... z_ {a_ {k} ^ {n}}, y_ {1} ... y_ {m})}$${\ Displaystyle (\ forall k) ({a_ {1} ^ {n}} ... {a_ {k} ^ {n}}) <(n-1) m + 2}$${\ Displaystyle D_ {k-1} \ klin}$

W przypadku przypadku podstawowego jest oczywiście również następstwem φ. Tak więc lemat został udowodniony. ${\ Displaystyle D_ {1} \ equiv (\ istnieje z_ {1} ... z_ {m + 1}) \ phi (z_ {a_ {1} ^ {1}} ... z_ {a_ {k} ^ {1}}, z_ {2}, z_ {3} ... z_ {m + 1}) \ equiv (\ istnieje z_ {1} ... z_ {m + 1}) \ phi (z_ {1} ... z_ {1}, z_ {2}, z_ {3} ... z_ {m + 1})}$

Jeśli można obalić dla jakiegoś n , wynika z tego, że φ można obalić. Z drugiej strony załóżmy, że nie można tego obalić dla żadnego n . Następnie dla każdego n istnieje sposób przypisania wartości prawdziwości do odrębnych podpozycji (uporządkowanych według ich pierwszego pojawienia się w ; „odrębny” oznacza tutaj albo odrębne predykaty, albo odrębne zmienne powiązane) w , taki, który będzie prawdziwy, gdy każde zdanie zostanie ocenione w ten sposób. Wynika to z kompletności leżącej u podstaw logiki zdań . ${\ displaystyle D_ {n}}$${\ displaystyle D_ {n}}$${\ displaystyle E_ {h}}$${\ displaystyle D_ {n}}$${\ displaystyle B_ {k}}$${\ displaystyle D_ {n}}$

Pokażemy teraz, że istnieje takie przypisanie wartości prawdy , aby wszystko było prawdziwe: Pojawiają się w tej samej kolejności we wszystkich ; indukcyjnie zdefiniujemy ogólne przypisanie do nich za pomocą swego rodzaju „większości głosów”: ponieważ istnieje nieskończenie wiele zadań (po jednym dla każdego ), które mają wpływ , albo nieskończenie wiele staje się prawdą, albo nieskończenie wiele czyni je fałszywymi i tylko skończenie wiele czyni je prawdziwymi . W pierwszym przypadku wybieramy generalnie prawdę; w tym drugim przypadku uważamy, że jest to ogólnie fałszywe. Następnie z nieskończenie wielu n, którym przez przypisano tę samą wartość prawdziwości, jak w zadaniu ogólnym, wybieramy ogólne przypisanie do w ten sam sposób. ${\ displaystyle E_ {h}}$${\ displaystyle D_ {n}}$${\ displaystyle E_ {h}}$${\ displaystyle D_ {n}}$${\ displaystyle D_ {n}}$${\ displaystyle E_ {1}}$${\ displaystyle E_ {1}}$${\ displaystyle E_ {1}}$${\ displaystyle E_ {1}}$${\ displaystyle E_ {h-1}}$${\ displaystyle E_ {h}}$

To ogólne przypisanie musi prowadzić do tego, że każdy z i będzie prawdziwy, ponieważ jeśli jeden z nich byłby fałszywy w ramach ogólnego przypisania, również byłby fałszywy dla każdego n> k . Ale to zaprzecza faktowi, że w przypadku skończonego zbioru ogólnych zadań, które pojawiają się w , istnieje nieskończenie wiele n, w których zadanie spełniające warunek jest zgodne z przypisaniem ogólnym. ${\ displaystyle B_ {k}}$${\ displaystyle D_ {k}}$${\ displaystyle B_ {k}}$${\ displaystyle D_ {n}}$${\ displaystyle E_ {h}}$${\ displaystyle D_ {k}}$${\ displaystyle D_ {n}}$

Z tego ogólnego zadania, które czyni wszystko prawdą, konstruujemy interpretację predykatów języka, która czyni makes prawdziwym. Wszechświatem modelu będą liczby naturalne . Każdy predykat i-ary powinien być prawdziwy w stosunku do naturałów dokładnie wtedy, gdy zdanie jest albo prawdziwe w przypisaniu ogólnym, albo nie jest przez nie przypisane (ponieważ nigdy nie pojawia się w żadnym z ). ${\ displaystyle D_ {k}}$${\ displaystyle \ Psi}$${\ Displaystyle (u_ {1} ... u_ {i})}$${\ displaystyle \ Psi (z_ {u_ {1}} ... z_ {u_ {i}})}$${\ displaystyle D_ {k}}$

W tym modelu każda z formuł jest prawdziwa konstrukcyjnie. Ale to implikuje, że samo φ jest prawdziwe w modelu, ponieważ zakres obejmujący wszystkie możliwe k-krotki liczb naturalnych. Zatem φ jest satysfakcjonujące i gotowe. ${\ Displaystyle (\ istnieje y_ {1} ... y_ {m}) \ phi (a_ {1} ^ {n} ... a_ {k} ^ {n}, y_ {1} ... y_ { m})}$${\ displaystyle a ^ {n}}$

Intuicyjne wyjaśnienie

Możemy zapisać każde B _i jako Φ (x ₁ ... x _k , y ₁ ... y _m ) dla niektórych xs, które możemy nazwać „pierwszymi argumentami” i ys, które możemy nazwać „ostatnimi argumentami”.

Weźmy na przykład B ₁ . Jego „ostatnie argumenty” to z ₂ , z ₃ … z _{m + 1} , a dla każdej możliwej kombinacji k tych zmiennych jest jakieś j, więc pojawiają się one jako „pierwsze argumenty” w B _j . Zatem dla dostatecznie dużego n ₁ , D _{n 1} ma tę własność, że „ostatnie argumenty” B ₁ pojawiają się, we wszystkich możliwych kombinacjach k z nich, jako „pierwsze argumenty” w innych B _j- w D _n . Dla każdego B _i istnieje D _{n i} z odpowiednią własnością.

Dlatego w modelu, który spełnia wszystkie D _n -s, istnieją obiekty odpowiadające z ₁ , z ₂ ... a każda kombinacja k z nich pojawia się jako „pierwsze argumenty” w pewnym B _j , co oznacza, że ​​dla każdego k z te obiekty z _{p 1} ... z _{p k} są z _{q 1} ... z _{q m} , co daje spełnienie Φ (z _{p 1} ... z _{p k} , z _{q 1} ... z _{q m} ). Biorąc podmodel tylko z tymi obiektami z ₁ , z ₂ ..., otrzymamy model spełniający φ.

Rozszerzenia

Rozszerzenie rachunku predykatów pierwszego rzędu z równością

Gödel zredukował formułę zawierającą wystąpienia predykatu równości do tych bez niego w rozszerzonym języku. Jego metoda polega na zastąpieniu formuły φ zawierającej pewne przypadki równości wzorem

${\ displaystyle (\ forall x) równanie (x, x) \ klin (\ forall x, r, z) [równanie (x, r) \ rightarrow (równanie (x, z) \ rightarrow równanie (y, z)) ]}$ ${\ Displaystyle \ klin (\ forall x, y, z) [równanie (x, r) \ rightarrow (równanie (z, x) \ rightarrow równanie (z, y))]}$
${\ displaystyle \ wedge}$
${\ Displaystyle (\ forall x_ {1} ... x_ {k}, y_ {1} ... x_ {k}) [(równanie (x_ {1}, y_ {1}) \ klin ... \ klin Eq (x_ {k}, y_ {k})) \ rightarrow (A (x_ {1} ... x_ {k}) \ equiv A (y_ {1} ... y_ {k}))]}$
${\ Displaystyle \ klin ... \ klin}$
${\ Displaystyle (\ forall x_ {1} ... x_ {m}, y_ {1} ... x_ {m.}) [(Eq (x_ {1}, y_ {1}) \ klin ... \ klin Eq (x_ {m.}, y_ {m.})) \ rightarrow (Z (x_ {1} ... x_ {m.}) \ equiv Z (y_ {1} ... y_ {m}))]}$
${\ displaystyle \ wedge}$
${\ displaystyle \ varphi '.}$

Tutaj oznaczamy predykaty występujące w φ (wraz z odpowiadającymi im znakami), a φ 'jest wzorem φ ze wszystkimi wystąpieniami równości zastąpionymi przez nowy predykat Eq . Jeśli tę nową formułę można obalić, oryginalne też było; to samo dotyczy spełnialności, ponieważ możemy przyjąć iloraz spełniającego modelu nowej formuły przez relację równoważności reprezentującą równanie . Iloraz ten jest dobrze zdefiniowany w odniesieniu do innych predykatów, a zatem będzie spełniał pierwotną formułę φ. ${\ displaystyle A ... Z}$${\ displaystyle k ... m}$

Rozszerzenie na policzalne zbiory formuł

Gödel rozważał również przypadek, w którym istnieje policzalnie nieskończony zbiór formuł. Stosując te same redukcje co powyżej, był w stanie rozważyć tylko te przypadki, w których każda formuła ma stopień 1 i nie zawiera zastosowania równości. Dla policzalnego zbioru formuł stopnia 1 możemy zdefiniować jak powyżej; następnie zdefiniuj jako zamknięcie . Pozostała część dowodu przeszła jak poprzednio. ${\ displaystyle \ phi ^ {i}}$${\ displaystyle B_ {k} ^ {i}}$${\ displaystyle D_ {k}}$${\ Displaystyle B_ {1} ^ {1} ... B_ {k} ^ {1}, ..., B_ {1} ^ {k} ... B_ {k} ^ {k}}$

Rozszerzenie na dowolne zbiory formuł

Kiedy istnieje nieskończenie nieskończony zbiór formuł, potrzebny jest Aksjomat Wyboru (lub przynajmniej jego słaba forma). Używając pełnego AC, można dobrze uporządkować formuły i udowodnić niepoliczalny przypadek tym samym argumentem co policzalny, z wyjątkiem indukcji pozaskończonej . Można zastosować inne podejścia, aby udowodnić, że twierdzenie o kompletności w tym przypadku jest równoważne twierdzeniu o ideale Boolean , czyli słabej postaci AC.

Bibliografia

• Gödel, K (1929). „Über die Vollständigkeit des Logikkalküls”. Rozprawa doktorska. Uniwersytet Wiedeński. Cite Journal wymaga |journal= ( pomoc ) Pierwszy dowód twierdzenia o zupełności.
• Gödel, K (1930). „Die Vollständigkeit der Axiome des logischen Funktionenkalküls”. Monatshefte für Mathematik (w języku niemieckim). 37 (1): 349–360. doi : 10.1007 / BF01696781 . JFM   56.0046.04 . S2CID   123343522 . Ten sam materiał co rozprawa, ale z krótszymi dowodami, bardziej zwięzłymi wyjaśnieniami i pominięciem długiego wprowadzenia.

Linki zewnętrzne

• Stanford Encyclopedia of Philosophy : „ Kurt Gödel ” - Juliette Kennedy .
• Biografia MacTutor: Kurt Gödel.