Logika Nieskończona

Spisu treści:

Logika Nieskończona
Logika Nieskończona

Wideo: Logika Nieskończona

Wideo: Logika Nieskończona
Wideo: 1. Доказательство в интуиционистской и классической логиках 2024, Marzec
Anonim

Nawigacja wejścia

  • Treść wpisu
  • Bibliografia
  • Narzędzia akademickie
  • Podgląd PDF znajomych
  • Informacje o autorze i cytacie
  • Powrót do góry

Logika nieskończona

Po raz pierwszy opublikowano 23 stycznia 2000; rewizja merytoryczna pt 26.02.2016

Tradycyjnie, wyrażenia w systemach formalnych uważano za oznaczające skończone inskrypcje, które - przynajmniej w zasadzie - mogą być faktycznie zapisane w notacji pierwotnej. Jednak fakt, że formuły (pierwszego rzędu) można utożsamiać z liczbami naturalnymi (poprzez „numerację Gödla”), a zatem ze zbiorami skończonymi, sprawia, że nie jest już konieczne traktowanie formuł jako inskrypcji i sugeruje możliwość kształtowania „języków” niektórych których formuły byłyby naturalnie identyfikowane jako nieskończone zbiory. „Język” tego rodzaju nazywany jest językiem nieskończonym: w tym artykule omawiam te języki nieskończone, które można uzyskać w prosty sposób z języków pierwszego rzędu, pozwalając koniunkcjom, dysjunkcjom i, być może, sekwencjom kwantyfikatora, być nieskończonym długość. W trakcie dyskusji okaże się, że o ile siła ekspresyjna takich języków znacznie przewyższa siłę ich finitarnych (pierwszego rzędu) odpowiedników, bardzo niewiele z nich posiada „atrakcyjne” cechy (np. Zwartość i kompletność) ten ostatni. W związku z tym na szczególną uwagę zasługują nieskończone języki, które faktycznie posiadają te cechy.

W § 1 jest podana podstawowa składnia i semantyka języków nieskończonych; ich ekspresyjna siła jest następnie pokazywana za pomocą przykładów. Paragraf 2 jest poświęcony tym nieskończonym językom, które dopuszczają tylko skończone sekwencje kwantyfikatorów: języki te okazują się względnie grzeczne. Paragraf 3 poświęcony jest omówieniu problemu zwartości języków nieskończonych i jego związku z czysto teoretycznymi pytaniami dotyczącymi „dużych” liczebników kardynalnych. W §4 jest naszkicowany argument, który pokazuje, że większość języków „nieskończonych kwantyfikatorów” ma naturę drugiego rzędu i jest tym samym wysoce niekompletna. W paragrafie 5 znajduje się krótki opis pewnej szczególnej klasy podjęzyków języków nieskończonych, dla których można udowodnić zadowalające uogólnienie twierdzenia o zwięzłości. Ta sekcja zawiera podsekcję dotyczącą definicji dopuszczalnych zestawów. Uwagi historyczne i bibliograficzne podano w §6.

  • 1. Definicja i podstawowe właściwości języków infinitarnych
  • 2. Języki skończonych kwantyfikatorów
  • 3. Właściwość zwartości
  • 4. Niekompletność języków nieskończenie ilościowych
  • 5. Podjęzyki języka L (ω 1, ω) i twierdzenie o zwartości Barwego

    5.1 Definicja pojęcia zbioru dopuszczalnego

  • 6. Uwagi historyczne i bibliograficzne
  • Bibliografia
  • Narzędzia akademickie
  • Inne zasoby internetowe
  • Powiązane wpisy

1. Definicja i podstawowe właściwości języków infinitarnych

Mając parę κ, λ nieskończonych kardynałów, takich jak λ ≤ κ, definiujemy klasę języków nieskończonych, w każdym z których możemy tworzyć spójniki i dysjunkcje zbiorów formuł o liczności <κ oraz kwantyfikacje na ciągach zmiennych o długości < λ.

Niech L - (finitarny) język bazowy - będzie dowolnym, ale ustalonym językiem pierwszego rzędu z dowolną liczbą symboli pozalogicznych. Język infinitary L (κ, λ) ma następujące podstawowe symbole:

  • Wszystkie symbole L.
  • Zbiór Var poszczególnych zmiennych, gdzie liczność Var (napisana: | Var |) to κ
  • Operator logiczny ∧ (koniunkcja nieskończona)

Klasę preformuł L (κ, λ) definiuje się rekurencyjnie w następujący sposób:

  • Każda formuła L jest preformulą;
  • jeśli φ i ψ są preformułami, więc są φ∧ψ i ¬φ;
  • jeśli Φ jest zbiorem preformuł takich, że | Φ | <κ, to ∧Φ jest preformułą;
  • jeśli φ jest preformulą, a X ⊆ Var to takie, że | X | <λ, to ∃ X φ jest preformułą;
  • wszystkie preformuły są zdefiniowane w powyższych punktach.

Jeśli Φ jest zbiorem preformuł indeksowanych przez zbiór I, powiedzmy Φ = {φ i: i ∈ I}, to zgadzamy się napisać ∧Φ dla:

i ∈ I  φ

lub jeśli ja jest zbiorem liczb naturalnych, piszemy ∧Φ dla:

φ 0 ∧ φ 1 ∧…

Jeśli X jest zbiorem pojedynczych zmiennych indeksowanych przez porządkową α, powiedzmy X = {x ξ: ξ <α}, zgadzamy się zapisać (∃ x ξ) ξ <α φ dla ∃ X φ.

Operatory logiczne ∨, →, ↔ są zdefiniowane w zwykły sposób. Wprowadzamy również operatory ∨ (dysjunkcja nieskończona) i ∀ (kwantyfikacja uniwersalna) wg

∨Φ = df ¬∧ {¬φ: φ ∈ Φ}

∀Xφ = df ¬∃X¬φ,

i stosuj podobne konwencje jak przy ∧, ∃.

Zatem L (κ, λ) jest językiem nieskończonym uzyskanym z L przez dopuszczenie koniunkcji i dysjunkcji o długości <κ oraz kwantyfikacji [1] długości <λ. Języki L (κ, ω) nazywane są językami z kwantyfikatorami skończonymi, pozostałe języki z kwantyfikatorami nieskończonymi. Zauważ, że L (ω, ω) to po prostu samo L.

Zwróć uwagę na następującą anomalię, która może wystąpić w języku nieskończonym, ale nie w języku finitarnym. W języku L (ω 1, ω), który pozwala na policzalnie nieskończone spójniki, ale tylko skończone kwantyfikacje, istnieją preformuły z tak dużą liczbą zmiennych wolnych, że nie można ich „zamknąć” w zdania L (ω 1, ω) przez prefiksowanie kwantyfikatorów. Tak jest na przykład w przypadku L (ω 1, ω) -preformula

x 0 <x 1 ∧ x 1 <x 2 ∧… ∧ x n <x n +1 …,

gdzie L zawiera symbol relacji binarnej <. Z tego powodu robimy, co następuje

Definicja. Formuła L (κ, λ) to preformula zawierająca zmienne wolne od <λ. Zbiór wszystkich wzorów L (κ, λ) będzie oznaczony przez Form (L (κ, λ)) lub po prostu Form (κ, λ), a zbiór wszystkich zdań przez Wysłane (L (κ, λ)) lub po prostu wysłane (κ, λ).

W związku z tym należy zauważyć, że generalnie nic nie zyskałoby na rozważeniu „języków” L (κ, λ) z λ> κ. Na przykład w „języku” L (ω, ω 1) formuły będą miały tylko skończenie wiele zmiennych wolnych, podczas gdy będzie mnóstwo „bezużytecznych” kwantyfikatorów, zdolnych do wiązania nieskończenie wielu zmiennych wolnych. [2]

Po zdefiniowaniu składni L (κ, λ) naszkicujemy następnie jego semantykę. Ponieważ pozalogiczne symbole L (κ, λ) to tylko symbole L i to właśnie te symbole określają formę struktur, w których dany język pierwszego rzędu ma być interpretowany, naturalne jest zdefiniowanie L (κ, λ) - ma być po prostu strukturą L. Pojęcie wzoru L (κ, λ) spełnianego w strukturze L A (przez ciąg elementów z dziedziny A) jest zdefiniowane w taki sam sposób indukcyjny, jak dla wzorów L, z tym że musimy dodać dwa dodatkowe klauzule odpowiadające klauzulom dla ∧Φ i ∃Xφ w definicji preformuły. W tych dwóch przypadkach naturalnie definiujemy:

∧Φ jest spełnione w A (przez zadany ciąg) ⇔ dla wszystkich φ ∈ Φ, φ jest spełnione w A (przez sekwencję);

∃ X φ jest spełniony A ⇔ istnieje ciąg elementów z domeną A w bijective korespondencji z X, która spełnia cp w A.

Te nieformalne definicje należy zaostrzyć w ramach rygorystycznego rozwoju, ale ich znaczenie powinno być jasne dla czytelnika. Teraz dostępne stają się zwykłe pojęcia prawdy, ważności, spełnialności i modelu dla formuł i zdań L (κ, λ). W szczególności, jeśli A jest strukturą L i σ ∈ Wysłane (κ, λ), napiszemy A ⊨ σ dla A jest modelem σ, a ⊨ σ dla σ jest ważne, to znaczy dla wszystkich A, A ⊨ σ. Jeśli Δ ⊆ Sent (κ, λ), napiszemy Δ ⊨ σ, ponieważ σ jest logiczną konsekwencją Δ, to znaczy każdy model Δ jest modelem σ.

Podajemy teraz kilka przykładów, które mają na celu ukazanie mocy ekspresyjnej języków nieskończonych L (κ, λ) z κ ≥ ω 1. W każdym przypadku dobrze wiadomo, że omawianego pojęcia nie można wyrazić w żadnym języku pierwszego rzędu.

Charakterystyka standardowego modelu arytmetyki w L (ω 1, ω). Tutaj standardowym modelem arytmetyki jest struktura N = ⟨N, +, ·, s, 0⟩, gdzie N to zbiór liczb naturalnych, +, · i 0 mają swoje zwykłe znaczenie, a s jest operacją następczą. Niech L będzie pierwszego rzędu odpowiedni język dla N. Wówczas klasa struktur L izomorficznych do N pokrywa się z klasą modeli koniunkcji następujących zdań L (ω 1, ω) (gdzie 0 to nazwa 0):

m ∈ωn ∈ω s m 0 + s n 0 = s m + n 0

m ∈ωn ∈ω s m 0 · s n 0 = s m · n 0

m ∈ωn ∈ω− {m} s m 0 ≠ s n 0

∀ x ∨ m ∈ω x = s m 0

Terminy s n x są definiowane rekurencyjnie przez

s 0 x = x
s n +1 x = s (s n x)

Charakterystyka klasy wszystkich zbiorów skończonych w L (ω 1, ω). Tutaj język bazowy nie ma symboli pozalogicznych. Klasa wszystkich zbiorów skończonych pokrywa się zatem z klasą modeli zdania L (ω 1, ω)

n ∈ω ∃ v 0 … ∃ v n ∀ x (x = v 0 ∨… ∨ x = v n).

Definicja prawdy w L (ω 1, ω) dla policzalnego języka podstawowego L. Niech L będzie policzalnym językiem pierwszego rzędu (na przykład językiem arytmetyki lub teorii mnogości), który zawiera nazwę n dla każdej liczby naturalnej n, i niech σ 0, σ 1,… będzie wyliczeniem jego zdań. Następnie formuła L (ω 1, ω)

Tr (x) = dfn ∈ω (x = n ∧ σ n)

jest predykatem prawdy dla L o tyle, o ile zdanie

Tr (n) ↔ σ n

obowiązuje dla każdego n.

Charakterystyka uporządkowania w L (ω 1, ω 1). Język bazowy L zawiera tutaj symbol predykatu binarnego ≤. Niech σ 1 będzie zwykłym zdaniem L charakteryzującym uporządkowanie liniowe. Wówczas klasa struktur L, w których interpretacja ≤ jest dobrze uporządkowana, pokrywa się z klasą modeli zdania L (ω 1, ω 1) σ = σ 1 ∧ σ 2, gdzie

σ 2 = df (∀ v n) n ∈ω ∃ x [∨ n ∈ω (x = v n) ∧ ∧ n ∈ω (x ≤ v n)].

Zwróć uwagę, że zdanie σ 2 zawiera nieskończony kwantyfikator: wyraża zasadniczo twierdzenie drugiego rzędu, że każdy policzalny podzbiór ma najmniejszą liczbę składową. W rzeczywistości można wykazać, że obecność tego nieskończonego kwantyfikatora jest niezbędna: klasy dobrze uporządkowanych struktur nie można scharakteryzować w żadnym języku kwantyfikatorów skończonych. Ten przykład wskazuje, że języki z kwantyfikatorami nieskończonymi, takie jak L (ω 1, ω 1), zachowują się raczej jak języki drugiego rzędu; zobaczymy, że mają one wspólne wady ostatnich (niekompletność), a także niektóre z ich zalet (duża siła wyrazu).

Wiele rozszerzeń języków pierwszego rzędu można przetłumaczyć na języki nieskończone. Na przykład rozważmy uogólniony język kwantyfikatora L (Q 0) otrzymany z L przez dodanie nowego symbolu kwantyfikatora Q 0 i interpretację Q 0 x φ (x), ponieważ istnieje nieskończenie wiele x takich, że φ (x). Łatwo zauważyć, że zdanie Q 0 x φ (x) ma te same modele co zdanie L (ω 1, ω)

¬∨ n ∈ω ∃ v 0 … ∃ v n ∀ x [φ (x) → (x = v 0 ∨… ∨ x = v n)].

Zatem L (Q 0) można w naturalny sposób przetłumaczyć na L (ω 1, ω). Innym językiem możliwym do przetłumaczenia na L (ω 1, ω) w tym sensie jest słaby język drugiego rzędu otrzymany przez dodanie policzalnego zestawu monadycznych zmiennych predykatów do L, które są następnie interpretowane jako rozciągające się na wszystkie skończone zbiory indywiduów.

Można również wprowadzić języki z dowolnie długimi spójnikami, dysjunkcjami i (prawdopodobnie) kwantyfikacjami. Dla ustalonego nieskończonego kardynała λ język L (∞, λ) jest zdefiniowany przez określenie jego klasy formuł Form (∞, λ), które mają być sumą zbiorów Forma (κ, λ) nad wszystkimi κ ≥ λ). Zatem L (∞, λ) dopuszcza dowolnie długie spójniki i dysjunkcje w tym sensie, że jeśli Φ jest arbitralnym podzbiorem Formy (∞, λ), to zarówno ∧Φ, jak i ∨Φ są członkami Formy (∞, λ). Ale L (∞, λ) dopuszcza tylko kwantyfikacje długości <λ: wszystkie jego wzory mają <λ zmiennych wolnych. Język L (∞, ∞) jest z kolei definiowany przez określenie jego klasy formuł, Form (∞, ∞), które mają być sumą wszystkich nieskończonych kardynałów λ klas Formularz (∞, λ). Tak więc L (∞, ∞) pozwala na dowolnie długie kwantyfikacje oprócz dowolnie długich koniunkcji i dysjunkcji. Zauważ, że Forma (∞, λ) i Forma (∞, ∞) są klasami właściwymi w sensie teorii mnogości Gödela-Bernaysa. Spełnienie wzorów L (∞, λ) i L (∞, ∞) w konstrukcji można zdefiniować przez oczywiste rozszerzenie odpowiedniego pojęcia dla L (κ, λ).

2. Języki skończonych kwantyfikatorów

Zauważyliśmy, że języki z kwantyfikatorami nieskończonymi, takie jak L (ω 1, ω 1), przypominają języki drugiego rzędu, ponieważ umożliwiają kwantyfikację nieskończonych zbiorów indywiduów. Fakt, że jest to niedozwolone w językach skończonych kwantyfikatorów, sugeruje, że mogą one być pod pewnymi względami bliższe swoim odpowiednikom pierwszego rzędu, niż mogłoby się wydawać na pierwszy rzut oka. Zobaczymy, że rzeczywiście tak jest, zwłaszcza w przypadku L (ω 1, ω).

Język L (ω 1, ω) zajmuje szczególne miejsce wśród języków nieskończonych, ponieważ - podobnie jak języki pierwszego rzędu - dopuszcza skuteczny aparat dedukcyjny. W rzeczywistości dodajmy do zwykłych aksjomatów pierwszego rzędu i reguł wnioskowania nowy schemat aksjomatów

∧Φ → φ

dla dowolnego policzalnego zbioru Φ ⊆ Form1, ω) i dowolnego φ ∈ Φ, wraz z nową regułą wnioskowania

φ 0, φ 1,…, φ n,…
n ∈ω φ n

i pozwolić, aby odliczenia miały policzalną długość. Pisząc ⊢ * dla wyprowadzalności w tym sensie, mamy wtedy

L (ω 1, ω) - twierdzenie o kompletności. Dla każdego σ ∈ Wysłane1, ω), ⊨ σ ⇔ ⊢ * σ

Jako bezpośredni wniosek wnioskujemy, że ten aparat dedukcyjny jest odpowiedni do dedukcji z policzalnych zbiorów przesłanek w L (ω 1, ω). Oznacza to, że z oczywistym rozszerzeniem notacji mamy dla dowolnego policzalnego zbioru Δ ⊆ Wysłane1, ω)

(2.1) Δ ⊨ σ ⇔ Δ⊢ * σ

To twierdzenie o zupełności można udowodnić, modyfikując zwykły dowód zupełności Henkina dla logiki pierwszego rzędu lub stosując metody algebraiczne Boole'a. Podobne argumenty, zastosowane do odpowiednich dalszych rozszerzeń aksjomatów i reguł wnioskowania, dają analogiczne twierdzenia o zupełności dla wielu innych języków kwantyfikatorów skończonych.

Jeśli dopuszcza się tylko dedukcje o policzalnej długości, to nie można utworzyć aparatu dedukcyjnego dla L (ω 1, ω), który byłby odpowiedni do dedukcji z dowolnych zbiorów przesłanek, to znaczy dla których (2.1) obowiązywałby dla każdego zbioru Δ ⊆ Wysłane1, ω), niezależnie od liczności. Wynika to z prostej obserwacji, że istnieje język L pierwszego rzędu i niepoliczalny zbiór Γ zdań L (ω 1, ω), taki że Γ nie ma modelu, ale każdy policzalny podzbiór Γ ma. Aby to zobaczyć, niech L będzie językiem arytmetyki powiększonym o ω 1 nowe symbole stałe { c ξ: ξ <ω 1 } i niech Γ będzie zbiorem L (ω 1, ω) -zdań {σ} ∪ { cξc η: ξ ≠ η}, gdzie σ to L (ω 1, ω) -zdanie charakteryzujące standardowy model arytmetyki. Ten przykład pokazuje również, że twierdzenie o zwartości zawodzi dla L (ω 1, ω), a więc również dla dowolnego L (κ, λ) z κ ≥ ω 1.

Innym wynikiem, który zachodzi w przypadku pierwszego rzędu, ale zawodzi dla L (κ, ω) z κ ≥ ω 1 (a także dla L (ω 1, ω 1), chociaż jest to trudniejsze do udowodnienia) jest forma normalna przedrostka twierdzenie. Zdanie jest przedrostkiem, jeśli wszystkie jego kwantyfikatory pojawiają się z przodu; podajemy przykład zdania L (ω 1, ω), które nie jest równoznaczne z koniunkcją zdań poprzedzających. Niech L będzie językiem pierwszego rzędu bez symboli pozalogicznych i niech σ będzie zdaniem L (ω 1, ω), które charakteryzuje klasę zbiorów skończonych. Załóżmy, że σ są równoważne koniunkcji

i ∈ I σ i

prenex L (ω 1, ω) -zdania σ i. Wtedy każde σ i ma postać

Q 1 x 1 … Q n x n φ i (x 1,…, x n),

gdzie każde Q k jest ∀ lub ∃, a φ i jest (prawdopodobnie nieskończoną) koniunkcją lub dysjunkcją formuł o postaci x k = x l lub x k ≠ x l. Ponieważ każde σ i jest zdaniem, w każdym φ i jest tylko skończenie wiele zmiennych i łatwo zauważyć, że każde φ i jest wówczas równoważne formule pierwszego rzędu. W związku z tym każde σ i można traktować jako zdanie pierwszego rzędu. Ponieważ zakłada się, że σ jest równoważne koniunkcji σ i, wynika z tego, że σ i zbiór Δ = {σ i: i ∈ I} mam te same modele. Ale oczywiście σ, a więc także Δ, mają modele wszystkich skończonych liczebności; twierdzenie o zwięzłości dla zbiorów zdań pierwszego rzędu implikuje teraz, że Δ, a zatem również σ, ma model nieskończony, co zaprzecza definicji σ.

Wracając do twierdzenia Löwenheima-Skolema, stwierdzamy, że wersja skierowana w dół ma odpowiednie uogólnienia na L (ω 1, ω) (i rzeczywiście, wszystkie języki nieskończone). W rzeczywistości można pokazać w podobny sposób, jak dla zbiorów zdań pierwszego rzędu, że jeśli Δ ⊆ Sent1, ω) ma nieskończony model liczności ≥ | Δ |, to ma model liczności, większy z ℵ 0, | Δ |. W szczególności każde zdanie L (ω 1, ω) z modelem nieskończonym ma policzalny model.

Z drugiej strony, twierdzenie Löwenheima-Skolema w górę w swojej zwykłej formie zawodzi dla wszystkich języków nieskończonych. Na przykład zdanie L (ω 1, ω) charakteryzujące standardowy model arytmetyki ma model liczności ℵ 0, ale nie ma modeli o jakiejkolwiek innej liczności. Jednak nie wszystko jest tutaj stracone, jak zobaczymy.

Definiujemy liczbę Hanf h (L) języka L jako najmniejszą kardynalną κ, tak że jeśli zdanie L ma model liczności κ, to ma modele o arbitralnie dużej liczności. Łatwo jest ustalić istnienie h (L). Dla każdego zdania L σ nie posiadającego modeli o arbitralnie dużej liczności niech κ (σ) będzie najmniejszą kardynalną κ taką, że σ nie ma modelu liczności κ. Jeśli λ jest supremum wszystkich κ (σ), to jeśli zdanie L ma model liczności λ, to ma modele o arbitralnie dużej liczności.

Zdefiniuj kardynałów μ (α) rekurencyjnie według

μ (0) = 0
μ (α + 1) = 2 μ (α)
μ (λ) = α <λ μ (α), dla granicy λ.

Wtedy można to wykazać

h (L (ω 1, ω)) = μ (ω 1),

podobne wyniki dla innych języków z kwantyfikatorami skończonymi. Wartości liczb Hanf języków kwantyfikatorów nieskończonych, takich jak L (ω 1, ω 1), są wrażliwe na obecność lub w inny sposób dużych kardynałów, ale w każdym przypadku muszą znacznie przekraczać wartości L (ω 1, ω).

Wynikiem dla L, który uogólnia na L (ω 1, ω), ale na żaden inny nieskończony język jest

Twierdzenie o interpolacji Craiga: Jeśli σ, τ ∈ Wysłane1, ω) są takie, że ⊨ σ → τ, to istnieje θ ∈ Wysłane1, ω) takie, że ⊨ σ → θ i ⊨ θ → τ, a każdy symbol pozalogiczny występujący w θ występuje zarówno w σ, jak i τ.

Dowód jest dość prostym rozszerzeniem sprawy pierwszego rzędu.

Na koniec wymieniamy jeszcze jeden wynik, który ładnie uogólnia na L (ω 1, ω), ale żaden inny nieskończony język. Powszechnie wiadomo, że jeśli A jest dowolną skończoną strukturą L z tylko skończoną liczbą relacji, istnieje zdanie L σ charakteryzujące A aż do izomorfizmu. Dla L (ω 1, ω) mamy następujące uogólnienie znane jako

Twierdzenie Scotta o izomorfizmie. Jeśli jest policzalny L-struktura tylko przeliczalnie wielu relacji, to nie jest to L (ω 1, ω) -sentence którego klasa policzalnych modeli zbiega się z klasy L-struktur izomorficzna z A.

Ograniczenie do policzalnych struktur jest istotne, ponieważ policzalność nie może być w ogólności wyrażona przez L (ω 1, ω) -zdanie.

Język L (∞, ω) można również zaliczyć do języka skończonych kwantyfikatorów. Szczególne znaczenie ma koncepcja ekwiwalencji struktur względem tego języka: dwie (podobne) struktury A i B (∞, ω) - równoważne, napisane A∞ω B, jeśli te same zdania L (∞, ω) posiadają zarówno a i B. Zależność tę można przede wszystkim scharakteryzować za pomocą pojęcia izomorfizmu częściowego. Częściowy izomorfizm między A i B to niepusta rodzina P map, taka że:

  • Dla każdego p ∈ P, dom (p) jest podstrukturą A, ran (p) jest podstrukturą B, a p jest izomorfizmem jego domeny na jego zakres; i
  • Jeśli p ∈ P, a ∈ A, b ∈ B, to istnieje r, s ∈ P oba rozciągające się p tak, że a ∈ dom (r), b ∈ biegły (s) (własność „tam iz powrotem”).

Jeśli istnieje częściowe izomorfizm między A i B, to mówimy, że i B są częściowo izomorficzne i zapisu ≅ p B. Mamy wtedy

Twierdzenie Karpa o częściowym izomorfizmie.

Do innych podobnych struktur, B, ≡ ∞ω B ⇔ ≅ p B.

Istnieje również wersja twierdzenia Scotta o izomorfizmie dla L (∞, ω), a mianowicie,

(2.2) Biorąc pod uwagę dowolną strukturę A, istnieje zdanie L (∞, ω) σ takie, że dla wszystkich struktur B, Ap BB ⊨ σ.

Izomorfizm częściowy i równoważność (∞, ω) są związane z pojęciem izomorfizmu Boole'a. Aby to zdefiniować, musimy wprowadzić ideę modelu teorii mnogości o wartościach boolowskich. Biorąc pod uwagę pełną algebrę Boole'a B, wszechświat V (B) zbiorów o wartościach B, znany również jako rozszerzenie B wszechświata V zbiorów, uzyskuje się przez pierwsze zdefiniowanie rekurencyjnie na α,

V α (B) = {x: x jest funkcją ∧ zakres (x) ⊆ B ∧ ∃ξ <α [dziedzina (x) ⊆ V ξ (B)]}

a następnie ustawienie

V (B) = {x: ∃α (x ∈ V α (B))}.

Składowe V (B) nazywane są zbiorami o wartości B. Można teraz łatwo zauważyć, że zbiór o wartościach B jest dokładnie funkcją o wartościach B z dziedziną zbiorem zbiorów o wartościach B. Teraz niech L będzie językiem pierwszego rzędu teorii mnogości i niech L (B) będzie językiem otrzymanym przez dodanie do L nazwy każdego elementu V (B) (użyjemy tego samego symbolu dla elementu i jego nazwy). Można teraz skonstruować odwzorowanie [·] (B) (zdań) języka L (B) na B: dla każdego zdania σ z L (B), elementem [σ] (B) z B jest „ Wartość prawdy logicznej σ w V (B). To odwzorowanie [·] (B) jest zdefiniowane tak, aby przesłać wszystkie twierdzenia teorii mnogości Zermelo-Fraenkla do górnego elementu 1 B, tj. Do „prawdy”; w związku z tym V (B) można traktować jako model teorii mnogości o wartościach boolowskich. Ogólnie, jeśli [σ] (B) = 1, mówimy, że σ jest ważne w V (B) i piszemy V (B) ⊨ σ.

Teraz każdy x ∈ V ma kanonicznego przedstawiciela x w V (B), co jest satysfakcjonujące

x = y iff V (B) ⊨ x = y

x ∈ y iff V (B) ⊨ x ∈ y

Mówimy, że dwie podobne struktury A, B są izomorficzne Boole'a, zapisane Ab B, jeśli dla jakiejś kompletnej algebry Boole'a B mamy V (B)AB, to znaczy, jeśli istnieje rozszerzenie logiczne wszechświat zbiorów, w których kanoniczne reprezentacje A i B są izomorficzne o wartości logicznej 1. Można wtedy wykazać, że:

(2.3) ≡ ∞ω BAb B.

Wynik ten można wzmocnić poprzez sformułowanie teorii kategorii. W tym celu potrzebujemy pojęcia a (n) (elementarnego) toposu. Aby wprowadzić tę koncepcję, zacznijmy od rodzinnej kategorii Zestaw zbiorów i odwzorowań. Zestaw ma następujące kluczowe właściwości:

  1. Istnieje „terminal” obiekt 1 taki, że dla każdego obiektu X istnieje unikalna mapa X → 1 (dla 1 możemy wziąć dowolny zestaw jednoelementowy, w szczególności {0}).
  2. Każda para obiektów X, Y ma iloczyn kartezjański X × Y.
  3. dla dowolnej pary obiektów można utworzyć „wykładniczy” obiekt Y X wszystkich map z X → Y.
  4. Istnieje obiekt „wartości prawdy” Ω taki, że dla każdego obiektu X istnieje naturalna zgodność między podobiektami (podzbiorami) X i mapami X → Ω. (Dla Ω możemy przyjąć zbiór 2 = {0,1}; mapy X → Ω są wtedy charakterystycznymi funkcjami na X.)

Wszystkie te cztery warunki można sformułować w języku teorii kategorii - kategoria spełniająca je nazywa się toposem. Kategoria Zestaw to topos; tak samo jest (i) kategoria Zbiór (B) zbiorów o wartościach boolowskich i odwzorowań w dowolnym rozszerzeniu boolowskim V (B) wszechświata zbiorów; (ii) kategorię snopów zbiorów w przestrzeni topologicznej; (iii) kategoria wszystkich diagramów map zbiorów

X 0 → X 1 → X 2 →…

Obiekty każdej z tych kategorii mogą być traktowane jako zbiory, które różnią się w pewien sposób: w przypadku (i) algebry Boole'a; w przypadku (ii) nad przestrzenią topologiczną; w przypadku (iii) ponad (dyskretny) czas. Można więc wyobrazić sobie topos jako wszechświat „zmiennych” zbiorów. Znana kategoria Set jest specjalnym ograniczającym przypadkiem toposu, w którym „wariacja” obiektów została zredukowana do zera.

Podobnie jak w teorii mnogości, „operatory logiczne” można zdefiniować na obiekcie wartości prawdy w dowolnym toposie. To są mapy ¬: Ω → Ω; ∧, ∨, ⇒: Ω × Ω → Ω odpowiadające logicznym operacjom negacji, koniunkcji, dysjunkcji i implikacji. Dzięki tym operacjom Ω staje się algebrą Heytinga, uosabiając w ten sposób w ogóle prawa nie klasycznej, ale intucjonistycznej logiki. W tym sensie logika intuicjonistyczna jest „zinternalizowana” w topos: logika intuicjonistyczna jest logiką zbiorów zmiennych. (Oczywiście logika klasyczna jest uwewnętrzniona w pewnych topozach, na przykład Set and Set (B) dla dowolnej pełnej algebry Boole'a B).

Każdy topos można wyobrazić sobie jako możliwy „wszechświat dyskursu”, w którym można interpretować twierdzenia matematyczne i wykonywać konstrukcje matematyczne. Twierdzenia matematyczne są interpretowane w toposie E przez wyrażenie w języku wewnętrznym E - teoretyczną wersję zwykłego języka teorii mnogości. W sposób analogiczny do trafności o wartościach boolowskich można wprowadzić odpowiednie pojęcie ważności w E zdania σ jego języka wewnętrznego. Ponownie piszemy E ⊨ σ dla „σ jest ważne w E”.

O toposie E mówi się, że jest pełny, jeśli dla dowolnego zbioru I kopower składający się z I [3]I 1 jego obiektu końcowego istnieje w E. ∐ I 1 można uważać za kanonicznego reprezentanta w E zbioru JA; w związku z tym piszemy to po prostu jako ja. (W V (B) pokrywa się to z I, jak zdefiniowano wcześniej.) Wszystkie wymienione powyżej toposy są pełne.

Teraz niech E będzie pełnym toposem. Jeśli A = (A, R,…) jest strukturą, napisz A dla (A, R,…). O dwóch strukturach A i B mówi się, że są toposami izomorficznymi, zapisanymi At B, jeśli dla niektórych toposów E zdefiniowanych w kategorii zbiorów mamy E ⊨ A ≅ B. Innymi słowy, dwie struktury są toposami izomorficznymi, jeśli ich kanoniczni przedstawiciele są izomorficzni w wewnętrznym języku niektórych toposów. Można to wtedy wykazać

(2.4) ≡ ∞ω B ⇔ ≅ T B.

W związku z tym równoważność (∞, ω) można uznać za izomorfizm w skrajnie ogólnym kontekście wszechświatów zbiorów „zmiennych”. Pod tym względem (∞, ω) - równoważność jest „niezmiennym” pojęciem izomorfizmu.

3. Właściwość zwartości

Jak widzieliśmy, twierdzenie o zwartości w swojej zwykłej formie zawodzi dla wszystkich języków nieskończonych. Niemniej jednak interesujące jest ustalenie, czy języki nieskończone spełniają jakąś odpowiednio zmodyfikowaną wersję twierdzenia. Okazuje się, że ten tak zwany problem zwartości ma naturalny związek z pytaniami czysto teoretycznymi, obejmującymi „duże” liczby kardynalne.

Konstruujemy następującą definicję. Niech κ będzie nieskończonym kardynałem. Mówi się, że język L jest κ- zwarty (względnie słabo κ -kompaktowy), jeśli ilekroć Δ jest zbiorem L- zdań (odpowiednio zbiorem L- zdań o liczności ≤ κ) i każdy podzbiór Δ liczności < κ ma model, podobnie jak Δ. Zauważ, że zwykłe twierdzenie o zwartości dla L jest dokładnie twierdzeniem, że L jest ω-zwarty. Jednym z powodów odpowiedniego znaczenia właściwości κ-zwartości jest następujący. Nazwij L κ- zakończone (lub słabo κ- zakończone), jeśli istnieje system dedukcyjny P dla L z dedukcjami długości <κ taki, że jeśli Δ jest P- spójnym [4] zbiorem L- zdania (czyli takie, że | Δ | ≤ κ), to Δ ma model. Zauważ, że takie P będzie adekwatne do dedukcji z dowolnych zbiorów przesłanek (o mocy ≤ κ) w sensie §2. Łatwo zauważyć, że jeśli L jest κ-kompletna lub słabo κ-pełna, to L jest κ-zwarta lub słabo κ-zwarta. Zatem, jeśli potrafimy wykazać, że dany język nie jest (słabo) κ-zwarty, to nie może istnieć dla niego system dedukcyjny z dedukcjami o długości <κ odpowiednimi do dedukcji z dowolnych zbiorów przesłanek (o mocy ≤ κ).

Okazuje się, że w rzeczywistości większość języków L (κ, λ) nie jest nawet słabo zwarta, a dla tych, które są, κ musi być wyjątkowo dużym kardynałem. Będziemy potrzebować kilku definicji.

Mówi się, że nieskończony kardynał κ jest słabo niedostępny, jeśli

(a) λ <κ → λ + <κ, (gdzie λ + oznacza kardynalnego następcę λ) i

(b) | Ja | <κ i λ i <κ (dla wszystkich i ∈ I) ⇒ ∑ i ∈ I λ i <κ.

Jeśli dodatkowo

c) λ <κ ⇒ 2 λ <κ,

wtedy mówi się, że κ jest (silnie) niedostępne. Ponieważ ℵ 0 jest niedostępne, normalną praktyką jest skupianie uwagi na niedostępnych lub słabo niedostępnych kardynałach, którzy przekraczają ℵ 0. W związku z tym niedostępni lub słabo niedostępni kardynałowie będą zawsze traktowani jako niepoliczalni. Jest oczywiste, że tacy kardynałowie - jeśli istnieją - muszą być niezwykle liczni; i faktycznie twierdzenie o niezupełności Gödla implikuje, że istnienia nawet słabo niedostępnych kardynałów nie można dowieść na podstawie zwykłych aksjomatów teorii mnogości.

Nazwijmy kardynalny κ zwarty (względnie słabo zwarty), jeśli język L (κ, κ) jest κ-zwarty (względnie słabo κ-zwarty). Następnie mamy następujące wyniki:

(3.1) ℵ 0 jest zwarty. Jest to oczywiście tylko zwięzły sposób wyrażenia twierdzenia o zwartości dla języków pierwszego rzędu.

(3.2) κ jest słabo zwarte ⇒ L (κ, ω) jest słabo κ- zwarte ⇒ κ jest słabo dostępne. W związku z tym zgodne jest (ze zwykłymi aksjomatami teorii mnogości) założenie, że żaden język L (κ, ω) z κ ≥ ω 1 nie jest słabo κ-zwarty, a fortiori słabo κ-kompletny.

(3.3) Załóżmy, że κ jest niedostępne. Wtedy κ jest słabo zwarty ⇔ L (κ, ω) jest słabo κ-zwarty. Również κ jest słabo zwarte ⇒ istnieje zbiór κ niedostępnych przed κ. Tak więc słabo zwarty, niedostępny kardynał jest niezwykle duży; w szczególności nie może być pierwszą, drugą,…, n- ,… niedostępną.

(3.4) κ jest zwarte ⇒ κ jest niedostępne. (Ale wynik bezpośrednio powyżej odwrotny zawodzi).

Niech Constr oznacza aksjomat konstruowalności Gödla; Przypomnijmy, że Constr jest zgodny ze zwykłymi aksjomatami teorii mnogości.

(3.5) Jeśli Constr utrzymuje, to nie ma zwartych kardynałów.

(3.6) Załóżmy Constr i niech κ będzie niedostępne. Wtedy κ jest słabo zwarte ⇔ L (ω 1, ω) jest słabo κ - zwarte dla wszystkich L.

(3.7) Jeśli Constr zachodzi, to nie ma kardynałów κ, dla których L (ω 1, ω) jest zwarty. W związku z tym zgodne jest ze zwykłymi aksjomatami teorii mnogości przypuszczenie, że nie ma takiego kardynalnego κ, że wszystkie języki L (ω 1, ω) są κ -kompletne. Wynik ten należy porównać z faktem, że wszystkie języki pierwszego rzędu są ω-pełne.

Znaczenie tych wyników jest takie, że twierdzenie o zwartości zawodzi bardzo źle dla większości języków L (κ, λ) z κ ≥ ω 1.

W tym miejscu warto zwrócić uwagę na pewne historyczne uwagi. W latach trzydziestych matematycy badali różne wersje tak zwanego problemu miary zbiorów, problemu, który powstał w związku z teorią miary Lebesgue'a na kontinuum. W szczególności sformułowano następujące, bardzo proste pojęcie miary. Jeśli X jest zbiorem, miara (policzalnie addytywna dwuwartościowa nietrywialna) na X jest odwzorowaniem μ na zbiorze potęg P X do zbioru {0, 1} spełniające:

(a) μ (X) = 1, (b) μ ({x}) = μ (∅) = 0 dla wszystkich x ∈ X i

(c) jeśli A jest policzalną rodziną wzajemnie rozłącznych podzbiorów X, to μ (∪ A) = ∑ {μ (Y): Y ∈ A }.

Oczywiście to, czy dany zbiór obsługuje taką miarę, zależy tylko od jej liczności, więc naturalne jest zdefiniowanie kardynała κ jako mierzalnego, jeśli wszystkie zbiory o liczności κ obsługują taką miarę. Szybko zdano sobie sprawę, że mierzalny kardynał musi być niedostępny, ale fałsz odwrotności został ustalony dopiero w latach sześćdziesiątych XX wieku, kiedy Tarski wykazał, że mierzalne kardynały są słabo zwarte, a jego uczeń Hanf pokazał, że pierwsze, drugie itd. Niedostępne nie są słabo dostępne. zwarty (por. (3.3)). Chociaż konkluzja, że mierzalne kardynały muszą być potwornie duże, jest teraz zwykle dowodzona bez okrężnej zwięzłości i nieskończonych języków, pozostaje faktem, że te idee zostały wykorzystane do ustalenia wyniku w pierwszej kolejności.

4. Niekompletność języków nieskończenie ilościowych

Prawdopodobnie najważniejszym wynikiem dotyczącym języków pierwszego rzędu jest twierdzenie o zupełności Gödla, które oczywiście mówi, że zbiór wszystkich prawidłowych formuł dowolnego języka pierwszego rzędu L można wygenerować z prostego zbioru aksjomatów za pomocą kilku prostych reguł wnioskowanie. Główną konsekwencją tego twierdzenia jest to, że jeśli formuły L są kodowane jako liczby naturalne w jakiś konstruktywny sposób, to zbiór (kodów) ważnych zdań jest wyliczalny rekurencyjnie. Zatem kompletność języka pierwszego rzędu oznacza, że zbiór jego ważnych zdań można zdefiniować w szczególnie prosty sposób. W związku z tym wydaje się rozsądne, biorąc pod uwagę dowolny język L, odwrócić tę implikację i zasugerować, że jeśli zbiór prawidłowego L-zdania nie są definiowalne w prosty sposób, wtedy nie można ustalić żadnego znaczącego wyniku kompletności dla L lub, jak powiemy, L jest niekompletne. W tej części zamierzamy wykorzystać tę sugestię do naszkicowania dowodu, że „większość” języków nieskończonych kwantyfikatorów jest niekompletnych w tym sensie.

Najpierw przedstawmy formalne pojęcie definiowalności w następujący sposób. Jeśli L jest językiem, A jest strukturą L, a X podzbiorem domeny A z A, mówimy, że X jest definiowalne w A wzorem φ (x, y 1,…, y n) z L, jeśli istnieje jest sekwencja A 1, …, a n od elementów takich, że x jest podzbiór wszystkich elementów x ∈ A, dla których φ (x, A 1, …, a n) posiada w A.

Teraz napisz Val (L) dla zbioru wszystkich prawidłowych L- zdań, tj. Tych, które zawierają się w każdej L- strukturze. Aby nadać znaczenie stwierdzeniu „Val (L) jest definiowalna”, musimy sprecyzować

  1. struktura C (L) - struktura kodowania dla L;
  2. szczególna mapa jeden-jeden - mapa kodowania - zbioru formuł L w dziedzinie C (L).

Następnie, jeśli zidentyfikujemy Val (L) z jego obrazem w C (L) pod mapą kodowania, będziemy interpretować stwierdzenie „Val (L) jest definiowalne” jako stwierdzenie „Val (L), traktowane jako podzbiór domena C (L), jest definiowana w C (L) wzorem L ”.

Na przykład, gdy L jest językiem arytmetyki pierwszego rzędu L, Gödel pierwotnie używał jako struktury kodowania standardowego modelu, a jako kodowania odwzorowuje dobrze znaną funkcję uzyskaną z twierdzenia o faktoryzacji pierwszego rzędu dla liczb naturalnych. Rekurencyjna wyliczalność Val (L) oznacza zatem po prostu, że zbiór kodów („liczby Gödela”) elementów Val (L) jest definiowalny w ℕ za pomocą wzoru L o postaci ∃ y φ (x, y), gdzie φ (x, y) jest formułą rekurencyjną.

Inną równoważną strukturą kodowania dla języka arytmetyki pierwszego rzędu jest struktura [5] ⟨H (ω), ∈ ⨡ H (ω)⟩ zbiorów dziedzicznie skończonych, gdzie zbiór x jest dziedzicznie skończony, jeśli x, jego elementy, jego członkowie, członkowie itd., są wszyscy skończeni. Ta struktura kodowania uwzględnia fakt, że formuły pierwszego rzędu są naturalnie traktowane jako zbiory skończone.

Przechodząc teraz do przypadku, w którym L jest językiem nieskończonym L (κ, λ), jaka byłaby odpowiednia struktura kodowania w tym przypadku? Na początku zwróciliśmy uwagę, że języki nieskończone są sugerowane przez możliwość myślenia o formułach jako o obiektach teorii mnogości, więc spróbujmy uzyskać naszą strukturę kodowania, zastanawiając się, za jakiego rodzaju obiektami teorii zbiorów powinniśmy przyjąć formuły nieskończone. Biorąc pod uwagę fakt, że dla każdej formy φ∈ (κ, λ), φ i jego podformuł, podformuł itd. Mają długość <κ, [6]chwilowa refleksja ujawnia, że formuły L (κ, λ) „odpowiadają” zbiorom x dziedzicznie o liczności <κ w tym sensie, że x, jego członkowie, jego członkowie, itd., wszystkie mają moc <κ. Zbiór wszystkich takich zbiorów jest oznaczony jako H (κ). H (ω) to zbiór dziedzicznie skończonych zbiorów wprowadzonych powyżej, a H (ω 1) zbiór wszystkich dziedzicznie policzalnych zbiorów.

Dla uproszczenia załóżmy, że jedynym pozalogicznym symbolem języka bazowego L jest binarny symbol predykatu ∈ (dyskusję można łatwo rozszerzyć na przypadek, w którym L zawiera dodatkowe symbole pozalogiczne). Kierując się powyższymi uwagami, jako strukturę kodującą dla L (κ, λ) przyjmujemy strukturę,

H (κ) = df ⟨H (κ), ∈ ⨡ H (κ)⟩.

Teraz możemy zdefiniować mapę kodowania Form (κ, λ) na H (κ). Najpierw do każdego podstawowego symbolu s L (κ, λ) przypisujemy obiekt kodu s ∈ H (κ) w następujący sposób. Niech {v ξ: ξ <κ} będzie wyliczeniem poszczególnych zmiennych L (κ, λ).

Symbol Obiekt kodu Notacja
¬ 1 ¬
2
3
4
5
= 6 =
v ξ ⟨0, ξ⟩ v ξ

Następnie do każdej φ ∈ Form (κ, λ) przypisujemy obiekt kodu φ rekurencyjnie w następujący sposób:

V ξ = V r | = df V ξ , = , V r | ⟩, V Ę, ∈ V r | = df V Ę, , , V r | ⟩;

dla φ, ψ ∈ Form (κ, λ),

cp ∧ * F = df cp , , * F

¬φ = df Kontakty , cp

∃ X cp = df { x X ∈ X} cp ⟩;

i wreszcie jeśli Φ ⊆ Forma (κ, λ) z | Φ | <κ,

∧Φ = df { cp : φ ∈ Φ}⟩.

Mapa φ ↦ φ z Form (κ, λ) do H (κ) jest łatwo dostrzegalna jako jedno-jeden i jest wymaganą mapą kodowania. W związku z tym zgadzamy się na identyfikację Val (L (κ, λ)) z jego obrazem w H (κ) pod tą mapą kodowania.

Kiedy Val (L (κ, λ)) jest definiowalnym podzbiorem H (κ)? Aby odpowiedzieć na to pytanie, potrzebujemy następujących definicji.

Formuła L nazywana jest formułą Δ 0 - jeśli jest równoważna formule, w której wszystkie kwantyfikatory mają postać ∀ x ∈ y lub ∃ x ∈ y (tj. ∀ x (x ∈ y →…) lub ∃ x (x ∈ y ∧…)). Formuła L jest formułą Σ 1 - jeśli jest równoważna formule, którą można zbudować z formuł atomowych i ich negacji przy użyciu tylko operatorów logicznych ∧, ∨, ∀ x ∈ y, ∃ x. Mówi się, że podzbiór X zbioru A jest Δ 0 (odp. Σ 1) na A, jeśli można go zdefiniować w strukturze ⟨A, ∈ ⨡ A⟩ za pomocą wzoru Δ 0 - (odpowiednio Σ 1 -) na L.

Na przykład, jeśli w zwykły sposób utożsamiamy zbiór liczb naturalnych ze zbiorem H (ω) zbiorów dziedzicznie skończonych, to dla każdego X ⊆ H (ω) mamy:

X jest Δ 0 na H (ω) ⇔ X jest rekurencyjne

X jest Σ 1 na H (ω) ⇔ X jest rekurencyjnie wyliczalne.

Zatem pojęcia zbioru Δ 0 - i Σ 1 można uznać za uogólnienia odpowiednio pojęć zbioru rekurencyjnego i zbioru rekurencyjnie wyliczalnego.

Twierdzenie o kompletności dla L implikuje, że Val (L) - uważany za podzbiór H (ω) - jest wyliczalny rekurencyjnie, a zatem Σ 1 na H (ω). Podobnie, twierdzenie o zupełności dla L (ω 1, ω) (patrz §2) implikuje, że Val (L (ω 1, ω)) - uważany za podzbiór H (ω 1) - wynosi Σ 1 na H (ω 1)). Jednak ten przyjemny stan rzeczy całkowicie się załamuje, gdy tylko zostanie osiągnięte L (ω 1, ω 1). Bo można to udowodnić

Twierdzenie Scotta o niezdefiniowalności dla L (ω 1, ω 1). Val (L (ω 1, ω 1)) nie jest definiowalna w H (ω 1) nawet formułą L (ω 1, ω 1) -; stąd a fortiori Val (L (ω 1, ω 1)) nie jest Σ 1 na H (ω 1).

Twierdzenie to zostało udowodnione w taki sam sposób, jak dobrze znany wynik, że zbiór (kodów) ważnych zdań języka drugiego rzędu aritemetyki L 2 nie jest definiowalny w swojej strukturze kodowania second. Aby otrzymać ten drugi wynik, najpierw zauważa się, że ℕ charakteryzuje się pojedynczym zdaniem L 2, a następnie pokazuje, że gdyby wynik był fałszywy, to „prawda w ℕ” dla zdań L 2 byłaby definiowana przez L 2 -formula, naruszając tym samym twierdzenie Tarskiego o nieokreśloności prawdy.

W związku z tym, aby udowodnić twierdzenie Scotta o nieokreśloności zgodnie z powyższymi wskazówkami, należy ustalić:

(4.1) Charakteryzowalność struktury kodującej H (ω 1) w L (ω 1, ω 1): istnieje zdanie L (ω 1, ω 1) τ 0 takie, że dla wszystkich L-struktur A, A ⊨ τ 0A ≅ H (ω 1).

(4.2) Nieokreśloność prawdy dla L (ω 1, ω 1) - zdania w strukturze kodującej: nie ma L (ω 1, ω 1) -formuły φ (v 0) takiej, że dla wszystkich L (ω 1, ω 1) -zdania σ, H (ω 1) σ ↔φ ( σ ).

(4.3) Istnieje wyraz t (v 0, v 1) z L (ω 1, ω 1) taki, że dla każdej pary zdań σ, τ z L (ω 1, ω 1), H (ω 1) ⊨ [t ( σ , τ ) = σ → τ ].

(4.1) dowodzi analiza teoretycznej definicji H (ω 1) i wykazanie, że można ją „wewnętrznie” sformułować w L (ω 1, ω 1). (4.2) zostało ustalone w podobny sposób, jak twierdzenie Tarskiego o nieokreśloności prawdy dla języków pierwszego lub drugiego rzędu. (4.3) uzyskuje się poprzez sformalizowanie definicji mapy kodowania σ ↦ σ w L (ω 1, ω 1).

Uzbrojeni w te fakty, możemy otrzymać twierdzenie Scotta o nieokreśloności w następujący sposób. Przypuśćmy, że to fałsz; wtedy byłoby L (ω 1, ω 1) -formuła θ (v 0) taka, że dla wszystkich L (ω 1, ω 1) -zdania σ,

(4.4) H (ω 1) ⊨ θ ( σ ) iff σ ∈ Val (L (ω 1, ω 1)).

Niech τ 0 będzie zdaniem podanym w (4.1). Wtedy mamy dla wszystkich L (ω 1, ω 1) -zdania σ,

H (ω 1) ⊨ σ iff (τ 0 → σ) ∈ Val (L (ω 1, ω 1)),

więc przez (4.4),

H (ω 1) ⊨ σ iff H (ω 1) ⊨ θ ( τ 0 → σ ).

Jeśli t jest terminem podanym w (4.3), wynikałoby z tego

H (ω 1) ⊨ σ ↔θ (t ( τ 0 , σ )).

Teraz napisz φ (v 0) dla wzoru L (ω 1, ω 1) θ (t ( τ 0 , σ )). Następnie

H (ω 1) σ ↔φ ( σ ),

zaprzeczający (4.2) i uzupełniający dowód.

Zatem Val (L (ω 1, ω 1)) nie jest definiowalna nawet formułą L (ω 1, ω 1) - więc a fortiori L (ω 1, ω 1) jest niekompletna. Podobne argumenty pokazują, że twierdzenie Scotta o nieokreśloności jest nadal aktualne, gdy ω 1 zostanie zastąpione przez dowolnego następcę kardynalnego κ +; w związku z tym wszystkie języki L (κ +, κ +) są niekompletne. [7]

5. Podjęzyki języka L (ω 1, ω) i twierdzenie o zwartości Barwego

Biorąc pod uwagę to, co teraz wiemy o językach nieskończonych, wydaje się, że L (ω 1, ω) jest jedynym, który zachowuje się w miarę dobrze. Z drugiej strony niepowodzenie twierdzenia o zwartości w uogólnianiu na L (ω 1, ω) w jakikolwiek użyteczny sposób jest poważną wadą, jeśli chodzi o zastosowania. Spróbujmy bardziej szczegółowo przeanalizować tę awarię.

Przypomnijmy sobie z §4, że możemy zakodować formuły języka pierwszego rzędu L jako zbiory dziedzicznie skończone, tj. Jako elementy składowe H (ω). W takim przypadku każdy skończony zbiór (kodów) zdań L jest również składnikiem H (ω), z czego wynika, że twierdzenie o zwartości dla L można sformułować w postaci:

(5.1) Jeśli Δ ⊆ Wysłane (L) jest takie, że każdy podzbiór Δ 0 ⊆ Δ, Δ 0 ∈ H (ω) ma model, to samo dotyczy Δ.

Teraz dobrze wiadomo, że (5.1) jest bezpośrednią konsekwencją uogólnionego twierdzenia o zupełności dla L, które, podane w postaci podobnej do (5.1), staje się twierdzeniem:

(5.2) Jeśli Δ ⊆ Wysłane (L) i σ ∈ Wysłane (L) spełniają Δ ⊨ σ, wówczas istnieje odliczenie D σ z Δ takie, że D ∈ H (ω). [8]

W §2 zauważyliśmy, że twierdzenie o zwartości dla L (ω 1, ω) zawodzi bardzo silnie; w rzeczywistości skonstruowaliśmy zbiór Γ ⊆ Wysłane1, ω) taki, że

(5.3) Każdy policzalny podzbiór Γ ma model, ale Γ go nie ma.

Przypomnijmy też, że wprowadziliśmy pojęcie dedukcji w L (ω 1, ω); skoro takie odliczenia mają policzalną długość, szybko wynika z (5.3)

(5.4) Istnieje zdanie [9] σ ∈ Wysłane1, ω) takie, że Γ ⊨ σ, ale nie ma dedukcji σ w L (ω 1, ω) z Γ.

Teraz formuły L (ω 1, ω) można zakodować jako elementy składowe H (ω 1) i jest jasne, że H (ω 1) zamyka się w wyniku tworzenia policzalnych podzbiorów i sekwencji. Odpowiednio (5.3) i (5.4) można zapisać:

(5.3 bis) Każde Γ 0 ⊆ Γ takie, że Γ 0 ∈ H (ω 1) ma model, ale Γ nie;

(5.4 bis) Istnieje zdanie σ ∈ Wysłane1, ω) takie, że Γ ⊨ σ, ale nie ma dedukcji D ∈ H (ω 1) z σ z Γ.

Wynika z tego, że (5.1) i (5.2) zawodzą, gdy „L” zostanie zastąpione przez „L (ω 1, ω)”, a „H (ω)” „H (ω 1)”. Ponadto można wykazać, że zbiór Γ ⊆ Wysłane1, ω) w (5.3 bis) i (5.4 bis) można przyjąć jako taken 1 na H (ω 1). Zatem twierdzenia o zwartości i uogólnionej zupełności zawodzą nawet dla Σ 1- zbiorów L (ω 1, ω) -zdań.

Widzimy z (5.4 bis), że powodem, dla którego uogólnione twierdzenie o zupełności zawodzi dla zbioru Σ 1 -zestawów w L (ω 1, ω) jest to, że, z grubsza mówiąc, H (ω 1) nie jest „zamknięte” w wyniku formułowania dedukcji z Σ 1 - zbiory zdań w H (ω 1). Aby więc temu zaradzić, naturalne wydaje się zastąpienie H (ω 1) zbiorami A, które w pewnym sensie są zamknięte w wyniku tworzenia takich dedukcji, a następnie rozważenie tylko tych formuł, których kody są w A.

Podajemy teraz szkic, jak można to zrobić.

Najpierw identyfikujemy symbole i wzory L (ω 1, ω) z ich kodami w H (ω 1), jak w §4. Dla każdego policzalnego przechodniego [10] zbioru A, niech

L A = Forma (L (ω 1, ω)) ∩ A.

Mówimy, że L A jest podjęzykiem L (ω 1, ω), jeśli spełnione są następujące warunki:

  1. L ⊆ L A
  2. jeśli φ, ψ ∈ L A, to φ ∧ ψ ∈ L A i ¬φ ∈ L A
  3. jeśli φ ∈ L A i x ∈ A, to ∃ x φ ∈ L A
  4. jeśli φ (x) ∈ L A i y ∈ A, to φ (y) ∈ L A
  5. jeśli φ ∈ L A, to każda podformuła φ jest w L A
  6. Jeśli Φ ⊆ L i Φ ∈ A, a następnie L ∧Φ ∈ A.

Pojęcie odliczenia w L A jest zdefiniowane w zwyczajowy sposób; Jeśli Δ jest zestaw zdań L A i cp ∈ L A, a następnie odjęcie cp z hemibursztynianu w L A jest odjęcie cp z hemibursztynianu w L (ω 1, ω), z których każdy wzór w L A. Mówimy, że φ można wyprowadzić z Δ w L A, jeśli istnieje dedukcja D of z Δ w L A; w tych warunkach piszemy Δ ⊢ A φ. Generalnie D nie będzie członkiem A; aby zapewnić, że takie odliczenie znajdzie się w A, konieczne będzie nałożenie dalszych warunków na A.

Niech być policzalny przechodni ustawione tak, że L jest podjęzykiem L (ω 1, co) i pozwolić Δ być zestaw zdań L A. Mówimy, że A (lub, przez nadużywanie terminologii, L A) jest Δ- zamknięte, jeśli dla dowolnego wzoru φ z L A takiego, że Δ ⊢ A there, istnieje odliczenie D φ z Δ takie, że D ∈ A. Można wykazać, że jedynym policzalnym językiem, który jest Δ zamknięty dla dowolnego Δ, jest język pierwszego rzędu L, tj. Gdy A = H (ω). Jednak J. Barwise odkrył, że istnieją policzalne zbiory A ⊆ H (ω 1), których języki L A różnią się od L, a jednak są Δ zamknięte dla wszystkich Σ 1- zbiory zdań Δ. Takie zbiory A nazywane są zbiorami dopuszczalnymi; z grubsza mówiąc, są one rozszerzeniami dziedzicznie skończonych zbiorów, w których teoria rekurencji - a zatem teoria dowodu - jest nadal możliwa (pełna definicja znajduje się w sekcji 5.1 poniżej).

Z wyniku Barwise natychmiast uzyskuje się

Twierdzenie o zwartości prętowej. Niech A będzie policzalnym zbiorem dopuszczalnym i niech Δ będzie zbiorem zdań L A, który jest Σ 1 na A. Jeżeli każdy Δ '⊆ Δ taki, że Δ' ∈ A ma model, to tak samo ma Δ.

Obecność „Σ 1” w tym miejscu wskazuje, że to twierdzenie jest uogólnieniem twierdzenia o zwartości dla rekurencyjnie wyliczalnych zbiorów zdań.

Inna wersja twierdzenia o zwartości Barwisa, przydatna do konstruowania modeli teorii mnogości, jest następująca. Niech ZFC będzie zwykłym zbiorem aksjomatów teorii mnogości Zermelo-Fraenkla, w tym aksjomatem wyboru. Następnie mamy:

5.5 Twierdzenie. Niech A będzie policzalnym zbiorem przechodnim takim, że A = ⟨A, ∈ ⨡ A⟩ jest modelem ZFC. Jeśli Δ jest zbiorem zdań L A, które można zdefiniować w A formułą języka teorii mnogości i jeśli każde Δ '⊆ Δ takie, że Δ' ∈ A ma model, to samo dzieje się z Δ.

Na zakończenie podajemy proste zastosowanie tego twierdzenia. Niech A = ⟨A, ∈ ⨡ A⟩ będzie modelem ZFC. Mówi się, że model B = ⟨B, E⟩ ZFC jest prawidłowym końcowym przedłużeniem A, jeśli (i) AB, (ii) AB, (iii) a ∈ A, b ∈ B, bEa ⇒ b ∈ A. Zatem właściwe rozszerzenie modelu ZFC jest poprawnym rozszerzeniem, w którym żaden „nowy” element nie występuje „przed” „starym” elementem. Udowadniamy, że nasza aplikacja 5.5

5.6 Twierdzenie. Każdy policzalny model przechodni ZFC ma odpowiednie rozszerzenie końcowe.

Dowód. Niech A = ⟨A, ∈ ⨡ A⟩ będzie przechodnim modelem ZFC i niech L będzie językiem pierwszego rzędu teorii mnogości powiększonej o nazwę a dla każdego a ∈ A i dodatkową stałą c. Niech Δ będzie zbiorem L A -zdań składających się z:

  • wszystkie aksjomaty ZFC;
  • ca, dla każdego a ∈ A;
  • ∀ x (x ∈ a → ∨ b ∈ a x = b), dla każdego a ∈ A;
  • ab, dla każdego a ∈ b ∈ A.

Można łatwo wykazać, że Δ jest podzbiorem A, który można zdefiniować w A formułą języka teorii mnogości. Ponadto każdy podzbiór Δ '⊆ Δ taki, że Δ' ∈ A ma model. Dla zbioru C wszystkich a ∈ A, dla których a występuje w Δ ', należy do A - ponieważ Δ' ma - i jeśli interpretujemy c jako dowolny element (koniecznie niepustego) zbioru A - C, to A jest a model Δ '. Odpowiednio, (5.5) implikuje, że Δ ma model ⟨B, E⟩. Jeżeli interpretuje każdą stałą A jako element a ∈ A, to ⟨B, E⟩ jest właściwa końca rozbudowa A. Dowód jest kompletny.

Czytelnik szybko zauważy, że twierdzenie o zwartości pierwszego rzędu nie da takiego wyniku.

5.1 Definicja pojęcia zbioru dopuszczalnego

Mówi się, że niepusty zbiór przechodni A jest dopuszczalny, gdy spełnione są następujące warunki:

  1. jeśli a, b ∈ A, to {a, b} ∈ A i ∪ A ∈ A;
  2. jeśli a ∈ A i X ⊆ A jest Δ 0 na A, to X ∩ a ∈ A;
  3. jeśli a ∈ A, X ⊆ A jest Δ 0 na A i ∀ x ∈ a ∃ y (<x, y> ∈ X), to dla jakiegoś b ∈ A, ∀ x ∈ a ∃ y ∈ b (<x, y> ∈ X).

Warunek (ii) - Δ 0 - schemat separacji - jest ograniczoną wersją aksjomatu separacji Zermelo. Warunek (iii) - podobnie osłabiona wersja aksjomatu zamiany - można nazwać Δ 0 - schematem zamiany.

Dość łatwo zauważyć, że jeśli A jest zbiorem przechodnim takim, że <A, ∈ | A> jest modelem ZFC, to A jest dopuszczalne. Mówiąc bardziej ogólnie, wynik jest nadal utrzymywany, gdy aksjomat zestawu mocy jest pomijany w ZFC, tak że zarówno H (ω), jak i H (ω 1) są dopuszczalne. Ponieważ jednak to ostatnie jest niepoliczalne, twierdzenie o zwartości Barwisa nie ma do niego zastosowania.

6. Uwagi historyczne i bibliograficzne

§§ 1 i 2. Wydaje się, że nieskończone języki zdań i predykatów pojawiły się po raz pierwszy w druku w pracach Scotta i Tarskiego [1958] oraz Tarskiego [1958]. Twierdzenie o zupełności dla L (ω 1, ω), jak również dla innych języków nieskończonych, zostało udowodnione przez Karpa [1964]. Obliczenia liczby Hanfa dla L (ω 1, ω) zostały po raz pierwszy przeprowadzone przez Morleya [1965]. Niedefiniowalność porządków dobrze w językach skończonych kwantyfikatorów została udowodniona przez Karpa [1965] i Lopeza-Escobara [1966]. Twierdzenie o interpolacji dla L (ω 1, ω) zostało udowodnione przez Lopeza-Escobara [1965], a twierdzenie Scotta o izomorfizmie dla L (ω 1, ω) przez Scotta [1965].

Twierdzenie Karpa o częściowym izomorfizmie zostało po raz pierwszy udowodnione w Karp [1965]; patrz także Barwise [1973]. Wynik (2.2) pojawia się w Chang [1968], wynik (2.3) w Ellentuck [1976], a wynik (2.4) w Bell [1981].

§ 3. Wyniki (3.2) i (3.3) są zasługą Hanfa [1964], z pewnymi udoskonaleniami Lopeza-Escobara [1966] i Dickmanna [1975], natomiast (3.4) udowodnił Tarski. Wynik (3,5) zawdzięczamy Scottowi [1961], (3,6) Bellowi [1970] i [1972]; i (3.7) Bell [1974]. Wymiernych kardynałów po raz pierwszy rozważali Ulam [1930] i Tarski [1939]. O tym, że mierzalne kardynały są słabo zwarte, zwrócił uwagę Tarski [1962].

§ 4. Odnośnie twierdzenia o nieokreślalności dla L (ω 1, ω 1). Uwagi Carol Karp (1964, 166), „Na Międzynarodowym Kongresie Logiki, Metodologii i Filozofii Nauki na Uniwersytecie Stanforda w 1960 r. Dana Scott rozpowszechniła zarys dowodu na niemożność stworzenia w pełni definiowalnego systemu formalnego (γ +, γ +) języki z jednym dwumiejscowym symbolem predykatu oprócz symbolu równości”. Scott nigdy nie opublikował swojego wyniku, a w pełni szczegółowy dowód pojawił się po raz pierwszy w Karp [1964]. Podejście do przyjętego tutaj twierdzenia jest oparte na rachunku podanym w Dickmann [1975].

§ 5. Oryginalna motywacja do wyników przedstawionych w tej sekcji pochodzi z Kreisel; w swoim [1965] wskazał, że nie ma przekonujących podstaw do wybierania formuł nieskończoności wyłącznie ze względu na „długość”, i zaproponował zamiast tego zastosowanie kryteriów definiowalności lub „domknięcia”. Sugestia Kreisela została z wielkim sukcesem podjęta przez Barwise'a [1967], gdzie udowodniono jego twierdzenie o zwartości. Pojęcie zbioru dopuszczalnego wywodzi się od Platka [1966]. Twierdzenie (5.6) zaczerpnięto z Keislera [1974].

Więcej informacji na temat języków nieskończonych można znaleźć w: Aczel [1973], Dickmann [1975], Karp [1964], Keisler [1974] i Makkai [1977]. Przydatny opis związku między językami nieskończonymi i dużymi kardynałami można znaleźć w rozdziale 10 książki Drake [1974].

Bibliografia

  • Aczel, P., 1973, „Infinitary Logic and the Barwise Compactness Theorem”, Proceedings of the 1971 Bertrand Russell Memorial Logic Conference (Uldum, Dania), J. Bell, J. Cole, G. Priest i A. Slomson (red..), Leeds: Bertrand Russell Memorial Logic Conference, 234–277.
  • Barwise, J., 1967, Infinitary Logic and Admiable Sets. Ph. D. Praca magisterska, Uniwersytet Stanforda.
  • –––, 1973, „Back and Forth through Infinitary Logic. Studies in Model Theory”, w: Studies in Mathematics (tom 8), Buffalo: Mathematical Association of American, str. 5–34.
  • –––, 1975, Dopuszczalne zbiory i struktury, Berlin: Springer-Verlag.
  • Barwise, J. and S. Feferman (red.), 1985, Handbook of Model-Theoretic Logics, New York: Springer-Verlag.
  • Baumgartner, J., 1974, „The Hanf number for full L ω 1, ω events (without GCH)”, Journal of Symbolic Logic, 39: 575–578.
  • Bell, JL, 1970, „Weak Compactness in Restricted Second-Order Languages”, Biuletyn PAN, 18: 111–114.
  • –––, 1972, „On the Relationship between Weak Compactness in L ω 1, ω, L ω 1, ω 1 and Restricted Second-Order Languages”, Archive for Mathematical Logic, 15: 74–78.
  • –––, 1974, „On Compact Cardinals”, Zeitschrift für Mathematical Logik und Grundlagen der Mathematik, 20: 389–393.
  • –––, 1981, „Isomorphism of Structures in S-toposes”, Journal of Symbolic Logic, 43 (3): 449–459.
  • Chang CC, 1968, „Some Remarks on the Model Theory of Infinitary Languages”. in The Syntax and Semantics of Infinitary Languages (Lecture Notes in Mathematics: Volume 72), J. Barwise (red.), Springer-Verlag, Berlin, 36-63.
  • Dickmann, MA, 1975, Large Infinitary Languages, Amsterdam: Holandia Północna.
  • Drake, FR, 1974, Teoria mnogości: wprowadzenie do wielkich kardynałów, Amsterdam: North-Holland Publishing Company.
  • Ellentuck, E., 1976, „Categoricity Regained”, Journal of Symbolic Logic, 41 (3): 639–643.
  • Hanf, WP, 1964, Incompactness in Languages with Infinitely Long Expressions, Amsterdam: North-Holland.
  • Karp, C., 1964, Languages with Expressions of Infinite Length, Amsterdam: North-Holland.
  • –––, 1965, „Finite-Quantifier Equivalence” w The Theory of Models, J. Addison, L. Henkin i A. Tarski (red.), Amsterdam: North-Holland, 407–412.
  • Keisler, HJ, 1974, Model Theory for Infinitary Logic, Amsterdam: Północna Holandia.
  • Keisler, HJ i Julia F. Knight, 2004, „Barwise: Infinitary Logic And Admiable Sets”, Journal of Symbolic Logic, 10 (1): 4–36
  • Kolaitis, P. i M. Vardi, 1992, „Fixpoint Logic vs. Infinitary Logic in Finite-Model Theory”, Proceedings of the Seventh Annual IEEE Symposium on Logic in Computer Science (LICS '92), IEEE, str. 46-57; dostępny online, doi: 10.1109 / LICS.1992.185518
  • Kreisel, G., 1965, „Model-Theoretic Invariants, Applications to Recursive and Hyperarithmetic Operations”, w The Theory of Models, J. Addison, L. Henkin i A. Tarski (red.), Amsterdam: North-Holland, 190-205.
  • Kueker, D., 1975, „Back-and-ahead arguments in infinitary languages”, w Infinitary Logic: In Memoriam Carol Karp (Lecture Notes in Mathematics: Volume 492), D. Kueker (red.), Berlin: Springer-Verlag.
  • Lopez-Escobar, EGK, 1965, „An Interpolation Theorem for Infinitely Long Sentences”, Fundamenta Mathematicae, 57: 253–272.
  • –––, 1966, „On Defining Well-Orderings”, Fundamenta Mathematicae, 59: 13–21.
  • Makkai, M., 1977, „Admiable Sets and Infinitary Logic”, Handbook of Mathematical Logic, J. Barwise (red.), Amsterdam: North-Holland, 233-282.
  • Morley, M., 1965, „Omitting Classes of Elements”, The Theory of Models, J. Addison, L. Henkin i A. Tarski (red.), Amsterdam: North-Holland, 265-273.
  • Nadel, M. 1985, „L ω 1, ω and Admiable Fragments”, w: J. Barwise i S. Feferman (red.) 1985, 271–287.
  • Platek, R., 1966, Foundations of Recursion Theory, Ph. D. Praca magisterska, Uniwersytet Stanforda.
  • Scott, D., 1961, „Measurable Cardinals and Constructable Sets”, Biuletyn PAN, 9: 521–524.
  • –––, 1965, „Logic with Denumerably Long Formulas and Finite Strings of Quantifiers”, The Theory of Models, J. Addison, L. Henkin i A. Tarski (red.), Amsterdam: North-Holland, 329-341.
  • Scott, D. i A. Tarski, 1958, „The sentential calcus with infinitely long expressions”, Colloquium Mathematicum, 16: 166–170.
  • Shelah, Saharon, 2012, „Nice infinitary logics”, Journal of the American Mathematical Society, 25: 395-427, dostępne online, doi: 10.1090 / S0894-0347-2011-00712-1
  • Tarski, A., 1939, „Ideale in völlständingen Mengenkörpern I”, Fundamenta Mathematicae, 32: 140–150.
  • –––, 1958, „Uwagi o logice predykatów z nieskończenie długimi wyrażeniami”, Colloquium Mathematicum, 16: 171–176.
  • –––, 1962, „Niektóre problemy i wyniki istotne dla podstaw teorii mnogości”, w: E, Nagel, P. Suppes i A. Tarski (red.), Logic, Methodology and Philosophy of Science, Stanford: Stanford University Press 123-135.
  • Ulam, S., 1930, „Zur Masstheorie in der algemeinen Mengenlehre”, Fundamenta Mathematicae, 16: 140–150.

Narzędzia akademickie

człowiek ikona
człowiek ikona
Jak cytować ten wpis.
człowiek ikona
człowiek ikona
Zobacz wersję PDF tego wpisu w Friends of the SEP Society.
ikona Inpho
ikona Inpho
Poszukaj tego tematu wpisu w Internet Philosophy Ontology Project (InPhO).
ikona dokumentów phil
ikona dokumentów phil
Ulepszona bibliografia tego wpisu na PhilPapers, z linkami do jego bazy danych.

Inne zasoby internetowe

Zalecane: