teoria zgodna z ω - ω-consistent theory

W logice matematycznej , ω-zgodny (lub omega-spójny , zwany także numerycznie segregative ) teoria jest teoria (zbiór zdań ), który jest nie tylko (składniowo) spójne (czyli nie udowodnić sprzeczność ), ale także unika udowodnienie pewnych nieskończonych kombinacji zdań, które są intuicyjnie sprzeczne. Nazwa pochodzi od Kurta Gödla , który wprowadził to pojęcie w toku dowodzenia twierdzenia o niezupełności .

Definicja

Mówi się, że teoria T interpretuje język arytmetyki, jeśli istnieje tłumaczenie formuł arytmetycznych na język T, tak że T jest w stanie udowodnić podstawowe aksjomaty liczb naturalnych w tym tłumaczeniu.

T , który interpretuje arytmetyczne jest ω-niezgodne , gdy na niektórych własności P liczb naturalnych (określone przez wzór na języku T ) T dowodzi, P (0) P (1), P (2), i tak dalej (to znaczy dla każdej standardowej liczby naturalnej n , T dowodzi, że zachodzi P ( n )), ale T również dowodzi, że istnieje pewna liczba naturalna n (koniecznie niestandardowa) taka, że P ( n ) zawodzi . To nie może generować sprzeczność w T ponieważ T mogą nie być w stanie wykazać dla każdej konkretnej wartości N , że P ( n ) nie tylko, że nie jest taki n .

T jest ω-spójne , jeśli jest nie ω-niespójne.

Istnieje słabsza, ale blisko spokrewniona właściwość Σ _{1 -} dźwięk. Teoria T jest Σ _{1 -} rozsądna (lub 1 - zgodna , w innej terminologii), jeśli każde Σ ⁰_{1 -} zdanie dające się udowodnić w T jest prawdziwe w standardowym modelu arytmetyki N (tj. Struktura zwykłych liczb naturalnych z dodaniem i mnożenie). Jeśli T jest wystarczająco silne, aby sformalizować rozsądny model obliczeń , Σ ₁ -dźwięk jest równoznaczne z wymaganiem, aby za każdym razem, gdy T udowodnił, że maszyna Turinga C zatrzymuje się, to C faktycznie się zatrzymuje. Każda teoria zgodna z ω jest dźwiękiem Σ ₁ , ale nie odwrotnie.

Mówiąc bardziej ogólnie, możemy zdefiniować analogiczne pojęcie dla wyższych poziomów hierarchii arytmetycznej . Jeśli Γ jest zbiorem zdań arytmetycznych (zazwyczaj Σ ⁰_n dla pewnego n ), teoria T jest Γ-poprawna, jeśli każde Γ-zdanie możliwe do udowodnienia w T jest prawdziwe w modelu standardowym. Kiedy Γ jest zbiorem wszystkich formuł arytmetycznych, Γ-poprawność nazywana jest po prostu (arytmetyczną) poprawnością. Jeśli język T składa się tylko z języka arytmetyki (w przeciwieństwie np. Do teorii mnogości ), to system dźwiękowy to taki, którego model można traktować jako zbiór ω, zwykły zbiór matematycznych liczb naturalnych. Przypadek ogólnego T jest inny, patrz ω-logika poniżej.

Σ _n -soundness ma następującą interpretację obliczeniową: jeśli teoria dowodzi, że program C używający a Σ _{n −1} - oracle zatrzymuje się, to C faktycznie zatrzymuje się.

Przykłady

Spójne, niespójne teorie ω

Napisz PA dla teorii arytmetyki Peano i Con (PA) dla wyrażenia arytmetyki, które formalizuje twierdzenie „PA jest spójne”. Con (PA) mógłby mieć postać „Dla każdej liczby naturalnej n , n nie jest liczbą Gödla dowodu z PA, że 0 = 1”. (To sformułowanie używa 0 = 1 zamiast bezpośredniej sprzeczności; to daje ten sam wynik, ponieważ PA z pewnością dowodzi ¬0 = 1, więc gdyby okazało się, że 0 = 1 również mielibyśmy sprzeczność, az drugiej strony, gdyby PA udowadnia sprzeczność, wtedy dowodzi wszystkiego , w tym 0 = 1.)

Zakładając, że PA jest naprawdę spójne, wynika z tego, że PA + ¬Con (PA) jest również spójne, bo gdyby tak nie było, to PA udowodniłoby Con (PA) ( reductio ), zaprzeczając drugiemu twierdzeniu Gödla o niekompletności . Jednak PA + ¬Con (PA) nie jest zgodny ω. Dzieje się tak, ponieważ dla dowolnej liczby naturalnej n , PA + ¬Con (PA) dowodzi, że n nie jest liczbą Gödla dowodu, że 0 = 1 (sama PA dowodzi tego faktu; dodatkowe założenie ¬Con (PA) nie jest potrzebne). Jednak PA + ¬Con (PA) dowodzi, że dla pewnej liczby naturalnej n , n jest liczbą Gödla takiego dowodu (jest to po prostu bezpośrednie przekształcenie twierdzenia ¬Con (PA)).

W tym przykładzie aksjomat ¬Con (PA) to Σ ₁ , stąd system PA + ¬Con (PA) jest w rzeczywistości Σ ₁ -niedźwięczny, a nie tylko ω-niespójny.

Arytmetycznie poprawne, niespójne teorie ω

Niech T będzie PA razem z aksjomatami c ≠ n dla każdej liczby naturalnej n , gdzie c jest nową stałą dodaną do języka. Wtedy T jest poprawne arytmetycznie (jak każdy niestandardowy model PA można rozszerzyć do modelu T ), ale ω-niespójne (jak się okazuje i c ≠ n dla każdej liczby n ). ${\ Displaystyle \ istnieje x \, c = x}$

Σ _1- dźwiękowe ω-niespójne teorie wykorzystujące tylko język arytmetyki można skonstruować w następujący sposób. Niech I Σ _n będzie subteorią PA ze schematem indukcji ograniczonym do Σ _n- formuł, dla dowolnego n > 0. Teoria I Σ _{n + 1} jest ostatecznie aksjomatyzowalna, niech więc A będzie jej pojedynczym aksjomatem i rozważmy teorię T = I Σ _n + Kontakty . Możemy założyć, że A jest instancją schematu indukcyjnego, który ma postać

{\ Displaystyle \ forall w \, [B (0, w) \ ziemia \ forall x \, (B (x, w) \ do B (x + 1, w)) \ do \ forall x \, B (x , w)].}

Jeśli oznaczymy wzór

{\ Displaystyle \ forall w \, [B (0, w) \ ziemia \ forall x \, (B (x, w) \ do B (x + 1, w)) \ do B (n, w)]}

przez P ( n ), to dla każdej liczby naturalnej n teoria T (a właściwie nawet czysty rachunek predykatów) dowodzi P ( n ). Z drugiej strony, T dowodzi formułę , ponieważ jest logicznie równoważne do aksjomatu ¬ A . Dlatego T jest niespójny ω. ${\ Displaystyle \ istnieje x \, \ neg P (x)}$

Można wykazać, że T to Π _{n + 3 -} dźwięk. W rzeczywistości jest to Π _{n + 3} - konserwatywne w stosunku do (oczywiście rozsądnej) teorii I Σ _n . Argument jest bardziej skomplikowany (opiera się na udowodnieniu zasady odbicia Σ _{n + 2} dla I Σ _n w I Σ _{n + 1} ).

Nieprawidłowe arytmetycznie, teorie zgodne z ω

Niech ω-Con (PA) będzie zdaniem arytmetycznym formalizującym stwierdzenie „PA jest zgodne z ω”. Wtedy teoria PA + ¬ω-Con (PA) jest błędna ( dokładnie Σ _3- niesprawna), ale ω-spójna. Argument jest podobny do pierwszego przykładu: odpowiednia wersja warunków derywalności Hilberta-Bernaysa-Löba zachodzi dla „predykatu udowodnienia” ω-Prov ( A ) = ¬ω-Con (PA + ¬ A ), a zatem spełnia warunek analogia drugiego twierdzenia o niezupełności Gödla.

ω-logic

Pojęcie teorii arytmetyki, których liczby całkowite są prawdziwymi liczbami całkowitymi matematycznymi, jest ujmowane przez ω-logikę . Niech T będzie teorią w policzalnym języku, która zawiera jednoargumentowy symbol predykatu N przeznaczony do przechowywania tylko liczb naturalnych, a także określonych nazw 0, 1, 2, ..., po jednym dla każdej (standardowej) liczby naturalnej (która mogą być oddzielnymi stałymi lub stałymi wyrazami, takimi jak 0, 1, 1 + 1, 1 + 1 + 1, ... itd.). Zwróć uwagę, że samo T może odnosić się do bardziej ogólnych obiektów, takich jak liczby rzeczywiste lub zbiory; tak więc w modelu T obiekty spełniające N ( x ) to te, które T interpretuje jako liczby naturalne, z których nie wszystkie muszą być nazwane jedną z określonych nazw.

System ω-logiki zawiera wszystkie aksjomaty i reguły zwykłej logiki predykatów pierwszego rzędu, łącznie z, dla każdej T- formuły P ( x ) z określoną wolną zmienną x , nieskończoną regułą ω o postaci:

Z wnioskowania .

{\ Displaystyle P (0), P (1), P (2), \ ldots}

{\ Displaystyle \ forall x \, (N (x) \ do P (x))}

Oznacza to, że jeśli teoria stwierdza (tj. Dowodzi) P ( n ) oddzielnie dla każdej liczby naturalnej n podanej przez jej określoną nazwę, to również stwierdza P zbiorczo dla wszystkich liczb naturalnych naraz poprzez ewidentny skończony, powszechnie określany ilościowo odpowiednik nieskończenie wielu poprzednicy reguły. W przypadku teorii arytmetyki, czyli takiej, która ma dziedzinę zamierzoną z liczbami naturalnymi, takimi jak arytmetyka Peano , predykat N jest zbędny i można go pominąć w języku, a konsekwencją reguły dla każdego P jest uproszczenie do . ${\ Displaystyle \ forall x \, P (x)}$

Ω-model T to model T, którego dziedzina obejmuje liczby naturalne i którego określone nazwy i symbol N są standardowo interpretowane, odpowiednio, jako te liczby i predykat mający tylko te liczby jako dziedzinę (skąd nie ma niestandardowych liczb) . Jeśli w języku nie ma N, to to, co byłoby domeną N, musi być domeną modelu, tj. Model zawiera tylko liczby naturalne. (Inne modele T mogą interpretować te symbole w sposób niestandardowy; na przykład dziedzina N nie musi być nawet policzalna.) Te wymagania powodują, że zasada ω brzmi w każdym modelu ω. Konsekwencją twierdzenia o typach omijających jest również sytuacja odwrotna: teoria T ma model ω wtedy i tylko wtedy, gdy jest spójny w logice ω.

Istnieje ścisłe powiązanie logiki ω ze spójnością ω. Teoria spójna w logice ω jest również zgodna z ω (i poprawna arytmetycznie). Odwrotna sytuacja jest fałszywa, ponieważ spójność w logice ω jest znacznie silniejszym pojęciem niż spójność ω. Jednakże zachodzi następująca charakterystyka: teoria jest zgodna z ω wtedy i tylko wtedy, gdy jej domknięcie w niezagospodarowanych zastosowaniach reguły ω jest spójne.

Stosunek do innych zasad spójności

Jeśli teoria T jest rekurencyjnie aksjomatyzowalna , ω-spójność ma następującą charakterystykę, za sprawą Craiga Smoryńskiego :

T jest zgodne z ω wtedy i tylko wtedy, gdy jest spójne.

{\ Displaystyle T + \ mathrm {RFN} _ {T} + \ mathrm {Th} _ {\ Pi _ {2} ^ {0}} (\ mathbb {N})}

Tutaj jest zbiorem wszystkich Π ⁰₂ -zdań ważnych w standardowym modelu arytmetyki i jest zasadą jednorodnego odbicia dla T , która składa się z aksjomatów ${\ Displaystyle \ mathrm {Th} _ {\ Pi _ {2} ^ {0}} (\ mathbb {N})}$ ${\ displaystyle \ mathrm {RFN} _ {T}}$

{\ Displaystyle \ forall x \, (\ mathrm {Prz} _ {T} (\ ulcorner \ varphi ({\ kropka {x}}) \ urcorner) \ do \ varphi (x))}

dla każdej formuły z jedną wolną zmienną. W szczególności teoria T, która w języku arytmetyki jest ostatecznie aksjomatyzowalna, jest ω-spójna wtedy i tylko wtedy, gdy T + PA jest -sidna. ${\ displaystyle \ varphi}$ ${\ displaystyle \ Sigma _ {2} ^ {0}}$

Uwagi

^ WVO Quine (1971), Teoria zbiorów i jej logika .
^ Smoryński, "Twierdzenia o niezupełności", Handbook of Mathematical Logic , 1977, s. 851.
^ Definicję tej symboliki można znaleźć w hierarchii arytmetycznej .
^ J. Barwise (red.), Handbook of Mathematical Logic , North-Holland, Amsterdam, 1977.
^ Smoryński, Craig (1985). Samoodniesienie i logika modalna . Berlin: Springer. ISBN 978-0-387-96209-2 . Sprawdzone w Boolos, G .; Smoryński, C. (1988). „Samoodniesienie i logika modalna”. The Journal of Symbolic Logic . 53 : 306. doi : 10,2307 / 2274450 . JSTOR 2274450 .

Bibliografia

Kurt Gödel (1931). „Über formal unentscheidbare Sätze der Principia Mathematica und verwandter Systeme I”. W Monatshefte für Mathematik . Przetłumaczone na język angielski jako O formalnie nierozstrzygalnych propozycjach Principia Mathematica i powiązanych systemów .

[quine-1] WVO Quine (1971), Teoria zbiorów i jej logika .

[2] Smoryński, "Twierdzenia o niezupełności", Handbook of Mathematical Logic , 1977, s. 851.

[3] Definicję tej symboliki można znaleźć w hierarchii arytmetycznej .

[4] J. Barwise (red.), Handbook of Mathematical Logic , North-Holland, Amsterdam, 1977.

[5] Smoryński, Craig (1985). Samoodniesienie i logika modalna . Berlin: Springer. ISBN 978-0-387-96209-2 . Sprawdzone w Boolos, G .; Smoryński, C. (1988). „Samoodniesienie i logika modalna”. The Journal of Symbolic Logic . 53 : 306. doi : 10,2307 / 2274450 . JSTOR 2274450 .

Languages

In other projects