Logika infinitarna - Infinitary logic

Nieskończonej logiki jest logika , która pozwala nieskończenie długie wypowiedzi i / lub nieskończenie długie dowodów . Niektóre logiki nieskończone mogą mieć inne właściwości niż te, które występują w standardowej logice pierwszego rzędu . W szczególności logika nieskończona może nie być zwarta lub kompletna . Pojęcia zwięzłości i kompletności, które są równoważne w logice skończonej, czasami nie są takie w logice nieskończonej. Dlatego dla logiki nieskończonej definiuje się pojęcia silnej zwartości i silnej kompletności. Ten artykuł dotyczy logiki nieskończonej typu Hilberta , ponieważ zostały one dogłębnie zbadane i stanowią najprostsze rozszerzenie logiki finitarnej. Nie są to jednak jedyne nieskończone logiki, które zostały sformułowane lub zbadane.

Rozważenie, czy pewna nieskończona logika zwana Ω-logiką jest kompletna, obiecuje rzucić światło na hipotezę kontinuum .

Słowo o notacji i aksjomat wyboru

Ponieważ jest prezentowany język o nieskończenie długich formułach, nie można ich wprost zapisać. Aby obejść ten problem, stosuje się szereg udogodnień notacyjnych, które, mówiąc ściśle, nie są częścią języka formalnego. służy do wskazania wyrażenia, które jest nieskończenie długie. Tam, gdzie nie jest jasne, długość sekwencji jest później odnotowywana. Tam, gdzie ten zapis staje się niejednoznaczny lub zagmatwany, sufiksy takie jak są używane do wskazania nieskończonej dysjunkcji w zbiorze formuł o liczności . Ten sam zapis można na przykład zastosować do kwantyfikatorów . Ma to reprezentować nieskończoną sekwencję kwantyfikatorów: kwantyfikator dla każdego gdzie . ${\ displaystyle \ cdots}$${\ displaystyle \ bigvee _ {\ gamma <\ delta} {A _ {\ gamma}}}$ ${\ displaystyle \ delta}$${\ displaystyle \ forall _ {\ gamma <\ delta} {V _ {\ gamma}:}}$${\ displaystyle V _ {\ gamma}}$${\ Displaystyle \ gamma <\ delta}$

Wszelkie użycie przyrostków i nie są częścią formalnych języków nieskończonych. ${\ displaystyle \ cdots}$

Przyjmuje się aksjomat wyboru (jak to często robi się przy omawianiu logiki nieskończonej), ponieważ jest to konieczne, aby mieć rozsądne prawa dystrybutywności.

Definicja logiki nieskończonej typu Hilberta

Logika nieskończona pierwszego rzędu L _{α , β} , α regularna , β = 0 lub ω ≤ β ≤ α , ma ten sam zestaw symboli co logika finitarna i może wykorzystywać wszystkie reguły tworzenia formuł logiki finitarnej wraz z kilka dodatkowych:

• Biorąc pod uwagę zestaw formuł to i są formułami. (W każdym przypadku sekwencja ma długość .) ${\ Displaystyle A = \ {A _ {\ gamma} | \ gamma <\ delta <\ alfa \}}$${\ Displaystyle (A_ {0} \ lor A_ {1} \ lor \ cdots)}$${\ Displaystyle (A_ {0} \ ziemia A_ {1} \ ziemia \ cdots)}$${\ displaystyle \ delta}$
• Biorąc pod uwagę zestaw zmiennych i formułę, a następnie formuły i . (W każdym przypadku sekwencja kwantyfikatorów ma długość ). ${\ Displaystyle V = \ {V _ {\ gamma} | \ gamma <\ delta <\ beta \}}$${\ displaystyle A_ {0}}$${\ displaystyle \ forall V_ {0}: \ forall V_ {1} \ cdots (A_ {0})}$${\ Displaystyle \ istnieje V_ {0}: \ istnieje V_ {1} \ cdots (A_ {0})}$${\ displaystyle \ delta}$

Pojęcia zmiennych wolnych i powiązanych stosuje się w ten sam sposób do formuł nieskończonych. Podobnie jak w logice finitarnej, formuła, której wszystkie zmienne są związane, nazywana jest zdaniem .

Teoria T w nieskończonej logiki jest zbiorem zdań w logice. Dowód w logice nieskończonej z teorii T jest sekwencją zdań długości, która spełnia następujące warunki: Każde zdanie jest albo logicznym aksjomatem, elementem T , albo jest wywnioskowane z poprzednich twierdzeń przy użyciu reguły wnioskowania. Tak jak poprzednio, można zastosować wszystkie reguły wnioskowania w logice finitarnej, łącznie z dodatkową: ${\ displaystyle L _ {\ alpha, \ beta}}$${\ displaystyle \ gamma}$

• Biorąc pod uwagę zestaw stwierdzeń , które wystąpiły wcześniej w dowodzie, można je wywnioskować. ${\ Displaystyle A = \ {A _ {\ gamma} | \ gamma <\ delta <\ alfa \}}$${\ displaystyle \ land _ {\ gamma <\ delta} {A _ {\ gamma}}}$

Poniżej przedstawiono logiczne schematy aksjomatów specyficzne dla logiki nieskończonej. Globalne zmienne schematów: i takie . ${\ displaystyle \ delta}$${\ displaystyle \ gamma}$${\ displaystyle 0 <\ delta <\ alpha}$

• ${\ Displaystyle ((\ ziemia _ {\ epsilon <\ delta} {(A _ {\ delta} \ oznacza A _ {\ epsilon})}) \ oznacza (A _ {\ delta} \ oznacza \ ziemia _ {\ epsilon <\ delta} {A _ {\ epsilon}}))}$
• Dla każdego , ${\ Displaystyle \ gamma <\ delta}$${\ Displaystyle ((\ ziemia _ {\ epsilon <\ delta} {A _ {\ epsilon}}) \ oznacza A _ {\ gamma})}$
• Prawa dystrybucji Changa (dla każdego ):, gdzie lub , i ${\ displaystyle \ gamma}$${\ Displaystyle (\ lor _ {\ mu <\ gamma} {(\ ziemia _ {\ delta <\ gamma} {A _ {\ mu, \ delta}})})}$${\ Displaystyle \ forall \ mu \ forall \ delta \ istnieje \ epsilon <\ gamma: A _ {\ mu, \ delta} = A _ {\ epsilon}}$${\ Displaystyle A _ {\ mu, \ delta} = \ neg A _ {\ epsilon}}$${\ Displaystyle \ forall g \ in \ gamma ^ {\ gamma} \ istnieje \ epsilon <\ gamma: \ {A _ {\ epsilon}, \ neg A _ {\ epsilon} \} \ subseteq \ {A _ {\ mu, g (\ mu)}: \ mu <\ gamma \}}$
• Na , gdzie jest zamawianie dołek ${\ displaystyle \ gamma <\ alpha}$${\ Displaystyle ((\ ziemia _ {\ mu <\ gamma} {(\ lor _ {\ delta <\ gamma} {A _ {\ mu, \ delta}})}) \ implikuje (\ lor _ {\ epsilon < \ gamma ^ {\ gamma}} {(\ land _ {\ mu <\ gamma} {A _ {\ mu, \ gamma _ {\ epsilon} (\ mu)})}})}$${\ Displaystyle \ {\ gamma _ {\ epsilon}: \ epsilon <\ gamma ^ {\ gamma} \}}$${\ displaystyle \ gamma ^ {\ gamma}}$

Ostatnie dwa schematy aksjomatów wymagają aksjomatu z wyboru, ponieważ pewne zbiory muszą być dobrze uporządkowane . Ostatni schemat aksjomatów jest ściśle rzecz biorąc niepotrzebny, jak implikują to prawa dystrybutywności Changa, jednak jest on włączony jako naturalny sposób pozwalający na naturalne osłabienie logiki.

Kompletność, zwartość i silna kompletność

Teoria to dowolny zestaw zdań. Prawdziwość zdań w modelach jest definiowana przez rekurencję i będzie zgodna z definicją logiki finitarnej, w której oba są zdefiniowane. Biorąc pod uwagę teorię T oświadczenie uważa się za ważne dla teorii T , czy prawdą jest, we wszystkich modelach T .

Logiczne jest kompletna, jeśli na każde zdanie S ważny w każdym modelu istnieje dowód S . Jest silnie kompletne, jeżeli dla dowolnej teorii T dla każdego zdania S obowiązują w T jest dowodem S z T . Nieskończona logika może być kompletna, ale nie jest całkowicie kompletna. ${\ displaystyle L _ {\ alpha, \ beta}}$

Kardynał jest słabo zwarty podczas każdego teorii T w zawierających najwyżej wielu wzorach, jeśli każdy S T o liczności mniej niż ma wzór, to T posiada wzór. Kardynał jest wysoce kompaktowe , gdy dla każdej teorii T w bez ograniczeń rozmiarów, jeśli każdy S T o liczności mniej niż ma wzór, to T posiada wzór. ${\ Displaystyle \ kappa \ neq \ omega}$${\ displaystyle L _ {\ kappa, \ kappa}}$${\ displaystyle \ kappa}$ ${\ displaystyle \ subseteq}$ ${\ displaystyle \ kappa}$${\ Displaystyle \ kappa \ neq \ omega}$${\ displaystyle L _ {\ kappa, \ kappa}}$ ${\ displaystyle \ subseteq}$ ${\ displaystyle \ kappa}$

Pojęcia wyrażalne w logice nieskończonej

W języku teorii mnogości podstawę wyraża następujące zdanie :

${\ Displaystyle \ forall _ {\ gamma <\ omega} {V _ {\ gamma}:} \ neg \ land _ {\ gamma <\ omega} {V _ {\ gamma +} \ in V _ {\ gamma}}. \ ,}$

W przeciwieństwie do aksjomatu fundacji, stwierdzenie to nie dopuszcza niestandardowych interpretacji. Pojęcie zasadności można wyrazić jedynie za pomocą logiki, która dopuszcza nieskończenie wiele kwantyfikatorów w pojedynczym stwierdzeniu. W konsekwencji wiele teorii, w tym arytmetyka Peano , których nie da się właściwie aksjomatyzować w logice finitarnej, może mieć odpowiednią logikę infinitarną. Inne przykłady obejmują teorie pól niearchimedialnych i grup wolnych od skrętów . Te trzy teorie można zdefiniować bez użycia nieskończonej ilościowej; potrzebne są tylko nieskończone połączenia.

Kompletna nieskończona logika

Dwie nieskończone logiki wyróżniają się swoją kompletnością. To są i . Pierwsza jest standardową logiką finitarną pierwszego rzędu, a druga jest logiką nieskończoną, która dopuszcza tylko instrukcje o policzalnej wielkości. ${\ Displaystyle L _ {\ omega, \ omega}}$${\ displaystyle L _ {\ omega _ {1}, \ omega}}$

${\ Displaystyle L _ {\ omega, \ omega}}$ jest również mocno kompletny, zwarty i mocno zwarty.

${\ displaystyle L _ {\ omega _ {1}, \ omega}}$ nie jest zwarty, ale jest kompletny (zgodnie z aksjomatami podanymi powyżej). Ponadto spełnia wariant właściwości interpolacji Craiga .

Jeśli jest silnie kompletne (zgodnie z aksjomatami podanymi powyżej), to jest silnie zwarte (ponieważ dowody w tych logikach nie mogą używać ani więcej podanych aksjomatów). ${\ displaystyle L _ {\ alpha, \ alpha}}$${\ displaystyle \ alpha}$${\ displaystyle \ alpha}$

Bibliografia

• Karp, Carol R. (1964), Languages ​​with expressions of infinite length , Amsterdam: North-Holland Publishing Co., MR   0176910
• Barwise, Kenneth Jon (1969), „Infinitary logic and admossible sets”, Journal of Symbolic Logic , 34 (2): 226–252, doi : 10.2307 / 2271099 , JSTOR   2271099 , MR   0406760