Neskončna Logika

Kazalo:

Neskončna Logika
Neskončna Logika

Video: Neskončna Logika

Video: Neskončna Logika
Video: Дмитрий Гусев: "Что такое логика, и какую роль она играет в нашей жизни? " 2024, Marec
Anonim

Vstopna navigacija

  • Vsebina vpisa
  • Bibliografija
  • Akademska orodja
  • Prijatelji PDF predogled
  • Informacije o avtorju in citiranju
  • Nazaj na vrh

Neskončna logika

Prvič objavljeno 23. januarja 2000; vsebinska revizija, 26. februarja 2016

Tradicionalno so izrazi v formalnih sistemih označeni kot končni napisi, ki so - vsaj načeloma - sposobni dejansko biti zapisani v primitivni zapisu. Vendar pa dejstvo, da se formule (prvega reda) lahko poistovetijo z naravnimi števili (prek "Gödel-ovega oštevilčenja") in s tem s končnimi množicami, ni treba več obravnavati formul kot napisov in predlaga možnost, da se "jeziki" oblikujejo nekatere katerih formule bi bile seveda opredeljene kot neskončne množice. Takšen "jezik" se imenuje infinitarni jezik: v tem članku razpravljam o tistih infinitarnih jezikih, ki jih je mogoče pridobiti naravnost iz jezikov prvega reda, tako da omogočimo, da so konjunkcije, ločitve in po možnosti kvantifikantne sekvence neskončne dolžino. Med razpravo bo razvidno, da čeprav izrazna moč takih jezikov daleč presega moč njihovih končnih (prvega reda), le redki od njih imajo "privlačne" lastnosti (npr. Kompaktnost in popolnost) slednje. V skladu s tem imajo infinitarni jeziki, ki dejansko imajo te lastnosti, posebno pozornost.

V 1. členu sta določena osnovna skladnja in semantika infinitarnih jezikov; njihova izrazna moč se nato prikaže s primeri. Odstavek 2 je namenjen tistim infinitarnim jezikom, ki dovoljujejo le omejena zaporedja kvantifikatorjev: ti jeziki se izkažejo za razmeroma dobro obnašanje. §3 je namenjen razpravi o problematičnosti kompaktnosti infinitarnih jezikov in njeni povezavi s čisto postavljenimi teoretičnimi vprašanji o „velikih“kardinalnih številkah. V §4 je skiciran argument, ki kaže, da ima večina "neskončnih kvantifikatorskih" jezikov narave drugega reda in je, ipso facto, zelo nepopolna. V členu 5 je kratek prikaz določenega posebnega razreda podjezikov infinitarnih jezikov, za katerega je mogoče dokazati zadovoljivo posplošitev teorema o kompaktnosti. Ta razdelek vključuje pododdelek o definiciji dopustnih nizov. Zgodovinske in bibliografske opombe so podane v §6.

  • 1. Opredelitev in osnovne lastnosti neskončnih jezikov
  • 2. Jeziki končnih količnikov
  • 3. Lastnost kompaktnosti
  • 4. Nepopolnost jezikov neskončno kvantifikatorja
  • 5. Podjezika L (ω 1, ω) in teorem barverzne kompaktnosti

    5.1 Opredelitev koncepta dopustnega niza

  • 6. Zgodovinske in bibliografske opombe
  • Bibliografija
  • Akademska orodja
  • Drugi internetni viri
  • Povezani vnosi

1. Opredelitev in osnovne lastnosti neskončnih jezikov

Glede na par κ, λ neskončnih kardinalov, tako da je λ ≤ κ, določimo razred infinitarnih jezikov, v katerem lahko oblikujemo veznike in ločitve sklopov formul kardinalnosti <κ in kvantifikacije za zaporedja spremenljivk dolžine < λ.

Naj bo L - (končni) osnovni jezik - poljuben, a fiksni jezik prvega reda s poljubnim številom ekstraloških simbolov. Infinitarni jezik L (κ, λ) ima naslednje osnovne simbole:

  • Vsi simboli L
  • Nabor Var posameznih spremenljivk, kjer je kardinalnost Var (zapisano: | Var |) κ
  • Logični operator ∧ (infinitarna veznica)

Razred preformul L (κ, λ) je rekurzivno opredeljen na naslednji način:

  • Vsaka formula L je predoblika;
  • če sta φ in pre predformule, potem sta ∧ψ∧ψ in φφ;
  • če je a skupek preformul, tako da | | | <κ, potem je a predoblika;
  • če je φ predformula in X ⊆ Var tak, da | X | <λ, potem je ∃ X φ preformula;
  • vse preformule so opredeljene z zgornjimi določbami.

Če je a množica predformul, indeksiranih z množico I, recimo Φ = {φ i: i ∈ I}, se strinjamo, da zapišemo ∧Φ za:

i ∈ I  φ

ali če sem množica naravnih števil, zapišemo ∧Φ za:

φ 0 ∧ φ 1 ∧…

Če je X množica posameznih spremenljivk, indeksiranih z zaporedno α, recimo X = {x ξ: ξ <α}, se strinjamo, da za ∃ X φ zapišemo (∃ x ξ) ξ <α φ.

Logični operatorji ∨, →, ↔ so definirani na običajen način. Uvajamo tudi operatorja ∨ (infinitarna disjunkcija) in ∀ (univerzalno količinsko določanje) s

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

∀Xφ = df ∃∃X¬φ,

in uporabljajo podobne konvencije kot za ∧, ∃.

Tako je L (κ, λ) infinitarni jezik, pridobljen iz L, tako da dovoljujemo veznike in disjunkcije dolžine <κ in kvantifikacije [1] dolžine <λ. Jeziki L (κ, ω) se imenujejo jeziki s končnim kvantifikatorjem, ostali jeziki neskončno kvantifikatorjev. Upoštevajte, da je L (ω, ω) samo L sam.

Opazite naslednjo anomalijo, ki se lahko pojavi v infinitarnem jeziku, ne pa v končnem. V jeziku L (ω 1, ω), ki omogoča vidno neskončno veznike, vendar le končne količinske vrednosti, obstajajo predoblike s toliko prostih spremenljivk, da jih ni mogoče "zapreti" v stavke L (ω 1, ω) s predpono kvantifikatorjev. Tak primer je na primer za L (ω 1, ω) -preformula

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

kjer L vsebuje simbol binarne relacije <. Zaradi tega naredimo naslednje

Opredelitev. Formula L (κ, λ) je preformula, ki vsebuje <λ proste spremenljivke. Niz vseh formul L (κ, λ) bomo označili z Obrazec (L (κ, λ)) ali preprosto Oblika (κ, λ) in nabor vseh stavkov s Sent (L (κ, λ)) oz. preprosto Poslano (κ, λ).

V zvezi s tem upoštevajte, da na splošno nič ne bi bilo mogoče pridobiti z upoštevanjem „jezikov“L (κ, λ) z λ> κ. Na primer, v "jeziku" L (ω, ω 1) bodo formule imele le končno veliko prostih spremenljivk, medtem ko bo na voljo množica "neuporabnih" kvantifikatorjev, ki lahko vežejo neskončno veliko prostih spremenljivk. [2]

Ko smo definirali skladnjo L (κ, λ), smo skicirali njeno semantiko. Ker so ekstraloški simboli L (κ, λ) ravno tisti od L in ravno ti simboli določajo obliko struktur, v katerih bo treba razlagati dani jezik prvega reda, je naravno določiti L (κ, λ) -struktura je preprosto L-struktura. Pojem formule L (κ, λ), ki je izpolnjena v L-strukturi A (z zaporedjem elementov iz domene A), je opredeljen na enak induktivni način kot za formule L, le da moramo dodati dve dodatne določbe, ki ustrezajo klavzulama ∧Φ in ∃Xφ v definiciji predoblike. V teh dveh primerih seveda definiramo:

∧Φ je izpolnjen v A (z določenim zaporedjem) ⇔ za vse φ ∈ Φ, φ je v A (po zaporedju);

∃ X φ izpolnjujejo v A ⇔ je zaporedje elementov iz domene A v bijektivna dopisovanje z X, ki ustreza φ v A.

Te neuradne opredelitve je treba strogo poostriti, njihov pomen pa mora biti bralcu jasen. Zdaj so na voljo običajni pojmi resnice, veljavnosti, izpolnljivosti in modela za formule in stavke L (κ, λ). Še posebej, če je A L-struktura in σ ∈ Sent (κ, λ), zapišemo A ⊨ σ za A je model σ, in σ za σ velja, torej za vse A, A ⊨ σ. Če je Δ ⊆ poslano (κ, λ), zapišemo Δ σ za σ, je logična posledica Δ, torej je vsak model Δ model σ.

Zdaj dajemo nekaj primerov, namenjenih prikazovanju izrazne moči infinitarnih jezikov L (κ, λ) z κ ≥ ω 1. V vsakem primeru je dobro znano, da zadevnega pojma ni mogoče izraziti v nobenem jeziku prvega reda.

Karakterizacija standardnega aritmetičnega modela v L (ω 1, ω). Tu je standardni aritmetični model struktura N = ⟨N, +, ·, s, 0⟩, kjer je N množica naravnih števil, +, · in 0 imajo svoje običajne pomene in s je naslednica. Če je L prvega reda jezik primeren za N. Nato razred L-struktur, izomorfnih na N, sovpada s razredom modelov veznika naslednjih stavkov L (ω 1, ω) (kjer je 0 ime 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

Izraze s n x rekurzivno definiramo s

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

Karakterizacija razreda vseh končnih nizov v L (ω 1, ω). Tu osnovni jezik nima ekstraloških simbolov. Razred vseh končnih nizov potem sovpada s razredom modelov L (ω 1, ω)

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

Opredelitev resnice v L (ω 1, ω) za števni osnovni jezik L. Naj bo L števni jezik prvega reda (na primer jezik aritmetike ali teorije množic), ki vsebuje ime n za vsako naravno število n in naj bo σ 0, σ 1,… naštevanje njegovih stavkov. Nato je L (ω 1, ω) -formula

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

je resnica predikat za L, kolikor je stavek

Tr (n) ↔ σ n

velja za vsako n.

Karakterizacija vrstnega reda v L (ω 1, ω 1). Osnovni jezik L tukaj vključuje binarni predikatni simbol ≤. Naj bo σ 1 običajni stavek L, ki označuje linearne zaporedje. Nato razred L-struktur, v katerih je interpretacija ≤ dobro urejenega, sovpada s razredom modelov stavka L (ω 1, ω 1) stavek σ = σ 1 ∧ σ 2, kjer

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

Opazite, da stavek σ 2 vsebuje neskončen količnik: izraža v bistvu trditev drugega reda, da ima vsaka številska podmnožica najmanj člana. Dejansko je mogoče pokazati, da je prisotnost tega neskončnega kvantifikata bistvenega pomena: razreda dobro urejenih struktur ni mogoče določiti v nobenem jeziku s končnim kvantifikatorjem. Ta primer kaže, da se neskončno kvantifikatorji, kot je L (ω 1, ω 1), ponašajo podobno kot jeziki drugega reda; videli bomo, da si delijo pomanjkljivosti latterjev (nepopolnosti), pa tudi nekatere njihove prednosti (močna izrazna moč).

Veliko razširitev jezikov prvega reda je mogoče prevesti v infinitarne jezike. Na primer, upoštevajte posplošeni jezik kvantifikatorja L (Q 0), pridobljenega iz L, tako da dodate nov kvantifikator Q 0 in interpretirate Q 0 x φ (x), saj obstaja neskončno veliko x takšnih, da je φ (x). Lahko vidimo, da ima stavek Q 0 x φ (x) enake modele kot L (ω 1, ω)

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

Tako je L (Q 0) v naravnem smislu prevedljiv v L (ω 1, ω). Drugi jezik v tem smislu, ki ga lahko prevedemo v L (ω 1, ω), je šibek jezik drugega reda, ki ga dobimo z dodajanjem števljivega niza monadskih predikatnih spremenljivk v L, ki se nato razlagajo tako, da segajo v vse končne skupine posameznikov.

Prav tako se lahko uvedejo jeziki s poljubno dolgimi vezniki, ločitvami in (mogoče) kvantifikacijami. Pri fiksnem neskončnem kardinalu λ je jezik L (∞, λ) opredeljen tako, da se določi njegov razred formul, oblika (∞, λ), ki naj bo zveza v vseh κ ≥ λ množic Form (κ, λ). Tako L (∞, λ) omogoča poljubno dolgih veznikov in disjunkdja v smislu, da če Φ je poljubna podmnožica oblika, potem tako ∧Φ in ∨Φ so (∞ N, N) člani Oblika (∞ N, N). Toda L (∞, λ) priznava le količinsko opredelitev dolžine <λ: vse njegove formule imajo <λ proste spremenljivke. Jezik L (∞, ∞) je opredeljen po vrsti, tako da določi razred formul, Form (∞, ∞), ki bo združitev vseh neskončnih kardinalov λ, razredov Obrazec (∞, λ). Torej L (∞, ∞) poleg poljubno dolgih veznic in disjunkcij omogoča poljubno dolge kvantifikacije. Upoštevajte, da sta oblika (∞, λ) in oblika (∞, ∞) pravilna razreda v smislu teorije množic Gödel-Bernays. Zadovoljstvo formul L (∞, λ) in L (∞, ∞) v strukturi je mogoče opredeliti z očitnim podaljšanjem ustreznega pojma za L (κ, λ).

2. Jeziki končnih količnikov

Opazili smo, da so jeziki neskončno kvantifikatorjev, kot je L (ω 1, ω 1), podobni jezikom drugega reda, kolikor omogočajo količinsko določitev za neskončne množice posameznikov. Dejstvo, da to ni dovoljeno v jezikih s končnim kvantifikatorjem, kaže na to, da so ti morda v določenih pogledih bližje njihovim kolegom prvega reda, kot je morda razvidno na prvi pogled. Videli bomo, da je res tako, zlasti v primeru L (ω 1, ω).

Jezik L (ω 1, ω) zavzema posebno mesto med infinitarnimi jeziki, saj podobno kot jeziki prvega reda omogoča učinkovit deduktivni aparat. Pravzaprav dodajmo k običajnim aksiomom prvega reda in pravilom sklepanja novo shemo aksiomov

∧Φ → φ

za vsak števni niz Φ ⊆ obrazec1, ω) in kateri koli φ ∈ Φ, skupaj z novim pravilom sklepanja

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

in omogočajo odbitke, ki jih je mogoče šteti. V tem smislu zapišemo for * za prepoznavnost, imamo to

L (ω 1, ω) - Teorem o popolnosti. Za kateri koli σ ∈ Sent1, ω), ⊨ σ ⇔ ⊢ * σ

Kot neposreden zaključek sklepamo, da je ta deduktivni aparat primeren za odbitke iz štetljivih nizov prostorov v L (ω 1, ω). To pomeni, da imamo očitno razširitev zapisov za vsako številsko množico Δ ⊆ Poslano1, ω)

(2.1) Δ ⊨ σ ⇔ Δ⊢ * σ

Ta izrek o popolnosti je mogoče dokazati s spremembo običajnega Henkinovega dokaza popolnosti za logiko prvega reda ali z uporabo logičnih algebričnih metod. Podobni argumenti, uporabljeni za primerne nadaljnje povečanje aksiomov in pravil sklepanja, prinašajo analogne teoreme popolnosti za številne druge jezike s končnim kvantifikatorjem.

Če se dovolijo samo odbitki števčne dolžine, potem ni mogoče postaviti nobenega odbitnega aparata za L (ω 1, ω), ki bi bil primeren za odbitke iz poljubnih nizov prostorov, torej za katere bi (2.1) veljalo za vsak niz Δ ⊆ Poslano1, ω), ne glede na kardinalnost. To izhaja iz preprostega opažanja, da obstaja jezik L prvega reda in nešteta množica Γ L (ω 1, ω) -sodnosti, tako da Γ nima modela, ampak ima vsak števni podvrsti of. Če želite to videti, naj bo L jezik aritmetike, dopolnjen s ω 1 novimi stalnimi simboli { c ξ: ξ <ω 1 } in naj bo the množica L (ω 1, ω) -stenc {σ} ∪ { cξc η: ξ ≠ η}, kjer je σ L (ω 1, ω) -država, ki označuje standardni model aritmetike. Ta primer tudi kaže, da izrek kompaktnosti ne deluje za L (ω 1, ω) in tako tudi za kateri koli L (κ, λ) z κ ≥ ω 1.

Drug rezultat, ki velja v primeru prvega reda, vendar ne ustreza L (κ, ω) z κ ≥ ω 1 (in tudi za L (ω 1, ω 1), čeprav je to težje dokazati), je prednastavna normalna oblika izrek. Stavek je predponi, če so vsi njegovi kvantifikatorji prikazani spredaj; podajamo primer L (ω 1, ω) -razločitve, ki ni enakovredna vezju predpristopnih stavkov. Naj bo L jezik prvega reda brez ekstraloških simbolov in naj bo σ L (ω 1, ω) -država, ki označuje razred končnih množic. Predpostavimo, da je σ enakovreden vezniku

i ∈ I σ i

predpone L (ω 1, ω) -sodnosti σ i. Potem je vsak σ i oblike

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

kjer je vsak Q k ∀ ali ∃ in je φ i (morda infinitarna) veznica ali disjunkcija formul v obliki x k = x l ali x k ≠ x l. Ker je vsak σ i stavek, je v vsakem φ i le končno veliko spremenljivk in enostavno je razbrati, da je potem vsak φ i enakovreden formuli prvega reda. V skladu s tem se lahko vsak σ i šteje za stavek prvega reda. Ker se σ domneva, da je enak konjunkciji σ i, izhaja, da sta σ in množica Δ = {σ i: i ∈ I} imajo enake modele. Toda očitno ima σ in s tem tudi Δ modele vseh končnih kardinalnosti; teorem kompaktnosti za množice stavkov prvega reda zdaj pomeni, da ima Δ in s tem tudi σ neskončen model, ki je v nasprotju z definicijo σ.

Če pogledamo na izrek Löwenheim-Skolem, ugotovimo, da ima različica navzdol ustrezne posplošitve na L (ω 1, ω) (in v resnici na vse infinitarne jezike). V resnici lahko na podoben način pokažemo kot za sklope stavkov prvega reda, da če ima Δ ⊆ poslano1, ω) neskončen model kardinalnosti ≥ | Δ |, ima model kardinalnosti večji od ℵ 0, | Δ |. Še posebej ima vsaka L (ω 1, ω) -država z neskončnim modelom števni model.

Po drugi strani pa naraščajoči izrek Löwenheim-Skolem v običajni obliki ne uspe za vse infinitarne jezike. Na primer, L (ω 1, ω) -država, ki označuje standardni model aritmetike, ima model kardinalnosti ℵ 0, vendar nima modelov nobene druge kardinalnosti. Vendar tukaj vse ni izgubljeno, kot bomo videli.

Hanfkovo število h (L) jezika L definiramo kot najmanj kardinalnega κ tako, da če ima L -model model kardinalnosti κ, ima modele poljubno velike kardinalnosti. Obstoj h (L) je hitro ugotovljen. Za vsak L- stavek σ, ki nima modelov poljubno velike kardinalnosti, naj bo κ (σ) najmanj kardinal κ, tako da σ nima modela kardinalnosti κ. Če je λ vrhunec vseh κ (σ), potem, če ima stavek L model kardinalnosti λ, ima modele poljubno velike kardinalnosti.

Kardinale μ (α) določite rekurzivno s

μ (0) = 0
μ (α + 1) = 2 μ (α)
μ (λ) = α <λ μ (α), za mejo λ.

Potem se lahko to pokaže

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

podobni rezultati veljajo tudi za druge jezike končnih količnikov. Vrednosti Hanfovih števil neskončno kvantifikatorskih jezikov, kot je L (ω 1, ω 1), so občutljive na prisotnost ali drugače velikih kardinalov, vendar morajo v vsakem primeru močno presegati vrednosti L (ω 1, ω).

Rezultat za L, ki se posplošuje na L (ω 1, ω), vendar v nobenem drugem infinitarnem jeziku ni

Craigova interpolacijska teorema: Če so σ, τ ∈ Sent1, ω) taki, da je ⊨ σ → τ, potem je θ ∈ Sent1, ω), tako da ⊨ σ → θ in ⊨ θ → τ, in vsak ekstraloški simbol, ki se pojavlja v θ, se pojavlja v σ in τ.

Dokaz je precej preprost podaljšek primera prvega reda.

Na koncu omenimo še en rezultat, ki se lepo posploši na L (ω 1, ω), vendar na nobenega drugega infinitarnega jezika. Dobro je znano, da če je A katera končna L-struktura z le končno veliko razmerji, obstaja stavek L σ, ki označuje A do izomorfizma. Za L (ω 1, ω) imamo naslednjo posplošitev, znano kot

Scottova teorema o izomorfizmu. Če je števno L-struktura s samo števno mnogo odnosov, potem je L (ω 1, ω) -sentence katerih razred štejejo, modelov sovpada z razreda L-struktur izomorfnih z A.

Omejitev števnih struktur je bistvenega pomena, ker štetja na splošno ni mogoče izraziti z L (ω 1, ω) -državo.

Jezik L (∞, ω) se lahko šteje tudi kot jezik s končnim kvantifikatorjem. Koncept enakovrednosti struktur glede na ta jezik je posebnega pomena: imenujemo dve (podobni) strukturi A in B (∞, ω) - enakovredni, zapisani A∞ω B, če sta enaka stavka L (∞, ω) ima v obeh A in B. To razmerje lahko najprej označimo s pojmom delnega izomorfizma. Delni izomorfizem med A in B je neprazna družina P zemljevidov, tako da:

  • Za vsak p ∈ P je dom (p) podstruktura A, ran (p) je podstruktura B in p je izomorfizem njene domene na njegovo območje; in
  • Če so p ∈ P, a ∈ A, b ∈ B, potem obstajajo r, s ∈ P obe podaljšani p, tako da je a ∈ dom (r), b ∈ ran (s) (lastnost "naprej in nazaj").

Če obstaja delna izomorfizem med A in B, pravimo, da in B sta delno izomorfna in pisati ≅ p B. Nato imamo

Karpova teorija o delnem izomorfizmu.

Za vse podobne strukture, B, ≡ ∞ω BA- ≅ str B.

Obstaja tudi različica Scottovega teorema o izomorfizmu za L (∞, ω), in sicer:

(2.2) Glede vsaka konstrukcija, da je L (∞, ω) -sentence σ tako, da je za vse strukture B, A- ≅ p BB ⊨ σ.

Delni izomorfizem in (∞, ω) -ekvivalenca sta povezana s pojmom boolovega izomorfizma. Da bi to opredelili, moramo predstaviti idejo o logičnem modelu teorije množic. Glede na popolno logično algebro B B, se vesolje V (B) množic z vrednostjo B, znano tudi kot B-podaljšek vesolja V nizov, dobi tako, da najprej določimo rekurzivno na α,

V α (B) = {x: x je funkcija ∧ območje (x) ⊆ B ∧ ∃ξ <α [domena (x) ⊆ V ξ (B)]}

in nato nastavitev

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

Člani V (B) se imenujejo množice z vrednostjo B. Zdaj je zlahka videti, da je B-vrednotena množica natančno funkcija B -vrednotenja, domena pa niz B-vrednotenih nizov. Zdaj naj bo L jezik prvega reda teorije množic in L (B) jezik, ki ga dobimo tako, da v L dodamo ime vsakega elementa V (B) (uporabili bomo isti simbol za element in njegovo ime). Zdaj je mogoče sestaviti preslikavo [·] (B) (stavkov) jezika L (B) v B: za vsak stavek σ L (B) je element [σ] (B) iz B " Boolova resnična vrednost "σ v V (B). To preslikavo [·] (B) je določeno tako, da pošlje vse teoreme teorije množic Zermelo-Fraenkel na zgornji element 1 B, torej na "resnico"; v skladu s tem se lahko V (B) obravnava kot boolov model s teorijo množic. Na splošno, če je [σ] (B) = 1, rečemo, da je σ veljavno v V (B), in zapišemo V (B) ⊨ σ.

Zdaj ima vsak x ∈ V kanoničnega predstavnika x v V (B), ki izpolnjuje

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

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

Pravimo, da sta podobne strukture, B so Boolean izomorfna, napisana ≅ b B, če je nekaj popolno Boolova algebra B, imamo V (B)AB, ki je, če je logični podaljšek od vesolje množic, v katerih sta kanonična predstavnika A in B izomorfna z boolovo vrednostjo 1. Nato lahko pokažemo, da:

(2.3) ≡ ∞ω BAb B.

Ta rezultat je mogoče okrepiti s kategorijsko teoretično formulacijo. Za to potrebujemo koncept (n) (elementarnega) toposa. Za uvedbo tega pojma začnemo z družinsko kategorijo Nabora nizov in preslikav. Set ima naslednje ključne lastnosti:

  1. Obstaja "terminal" objekt 1, tako da za kateri koli objekt X obstaja edinstven zemljevid X → 1 (za 1 lahko vzamemo poljuben niz elementov, zlasti {0}).
  2. Kateri koli par predmetov X, Y ima kartuzijanski izdelek X × Y.
  3. za kateri koli par objektov lahko iz X → Y tvorimo "eksponentni" predmet Y X vseh zemljevidov.
  4. Predmet Ω resnične vrednosti Ω je tak, da za vsak objekt X obstaja naravno ujemanje med podobjekti (podmnožji) X in zemljevidi X → Ω. (Za Ω lahko vzamemo množico 2 = {0,1}; zemljevidi X → Ω so nato značilne funkcije na X.)

Vse štiri pogoje lahko oblikujemo v teoretičnem jeziku o kategorijah - kategorija, ki jih izpolnjuje, se imenuje topos. Kategorija Set je topos; zato so tudi (i) kategorija Set (B) logičnih-cenjene aparatov in preslikave v vsakem logični podaljšek V (B) vesolja zbirk; (ii) kategorijo snopov sklopov na topološkem prostoru; (iii) kategorijo vseh diagramov zemljevidov nizov

X 0 → X 1 → X 2 →…

Predmeti vsake od teh kategorij se lahko obravnavajo kot množice, ki se na nek način razlikujejo: v primeru (i) nad logično algebro; v primeru (ii) nad topološkim prostorom; v primeru (iii) daljši (diskretni) čas. Torej je topos mogoče razumeti kot vesolje "spremenljivih" nizov. Znana kategorija Set je poseben omejevalni primer toposa, pri katerem je "variacija" predmetov zmanjšana na nič.

Tako kot v teoriji množic, je mogoče v katerem koli toposu na objektu vrednosti resnice definirati tudi "logične operaterje". To so zemljevidi ¬: Ω → Ω; ∧, ∨, ⇒: Ω × Ω → Ω, ki ustrezajo logičnim operacijam negacije, konjunkcije, disjunkcije in implikacije. S temi operacijami Ω postane Heytingova algebra in tako na splošno uteleša zakone ne klasične, temveč intuicijske logike. V tem smislu je intuicijska logika "internalizirana" v topos: intuicijska logika je logika spremenljivih nizov. (Seveda je klasična logika ponotranjena v določenih topovih, na primer Set in Set (B) za katero koli popolno logično algebro B.)

Vsak topos je mogoče zamisliti kot "vesolje diskurza", v katerem se lahko razlagajo matematične trditve in se izvajajo matematične konstrukcije. Matematične trditve postanejo interpretirane v toposu E z izražanjem znotraj notranjega jezika E - tipično-teoretična različica običajnega jezika teorije množic. Na način, ki je analogen veljavi Boolove vrednosti, lahko v stavku σ svojega notranjega jezika vnesemo ustrezen pojem veljavnosti. Spet pišemo E ⊨ σ za „σ velja v E“.

Kaže se, da je topos E poln, če za katero koli množico I -postojna moč [3]I 1 njegovega končnega predmeta obstaja v E. ∐ I 1 se lahko šteje za kanoničnega predstavnika v E množice JAZ; v skladu s tem pišemo preprosto kot jaz. (V V (B) to sovpada z I, kot je bilo predhodno opredeljeno.) Vsi zgoraj omenjeni predlogi so polni.

Zdaj naj bo E poln topos. Če je A = (A, R,…) struktura, napišite A za (A, R,…). Dve strukturi A in B naj bi bili topos izomorfni, napisani At B, če za nekatere topose E, definirane v kategoriji nizov, imamo E ⊨ A ≅ B. Z drugimi besedami, dve strukturi sta topos izomorfni, če sta njuna kanonična predstavnika izomorfna v notranjem jeziku nekaterih toposov. Nato je mogoče pokazati, da

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

Skladno s tem (∞, ω) -ekvivalenca je mogoče obravnavati kot izomorfizem v izjemno splošnem kontekstu univerzumov "spremenljivih" nizov. V tem pogledu (∞, ω) -ekvivalenca je "invariantno" pojmovanje izomorfizma.

3. Lastnost kompaktnosti

Kot smo videli, izrek kompaktnosti v svoji običajni obliki ne uspe za vse infinitarne jezike. Kljub temu je koristno ugotoviti, ali infinitarni jeziki izpolnjujejo neko ustrezno spremenjeno različico izrekanja. Izkazalo se je, da ima ta tako imenovani problem kompaktnosti naravno povezavo s čisto postavljenimi teoretičnimi vprašanji, ki vključujejo „velika“kardinalna števila.

Konstruiramo naslednjo definicijo. Naj bo κ neskončen kardinal. Za jezik L rečemo, da je κ- kompakten (torej šibko κ-kompakten), če je Δ niz L- izrazov (torej niz L- vsebnosti kardinalnosti ≤ κ) in vsak podvrsta Δ kardinalnosti < κ ima model, tako tudi Δ. Opazite, da je običajni izrek kompaktnosti za L ravno trditev, da je L ω-compact. Eden od razlogov za pomembnost lastnosti κ-kompaktnosti je naslednji. Pokličite L κ- (odvisno od šibko κ- dokončano), če obstaja deduktivni sistem P za L z odbitki dolžine <κ tako, da če je Δ P- skladen [4] niz L- stavki (kar pomeni, da | Δ | ≤ κ), potem ima Δ model. Upoštevajte, da bo takšen P ustrezen za odbitke iz poljubnih nizov prostorov (kardinalnosti ≤ κ) v smislu §2. Zlahka vidimo, da če je L κ-popoln ali šibko κ-popoln, potem je L κ-kompakten ali šibko κ-kompakten. Če torej lahko pokažemo, da dani jezik ni (šibko) κ-kompakten, potem zanj ne more biti deduktivnega sistema z odbitki dolžine <κ, ki so primerni za odbitke iz poljubnih nizov prostorov (kardinalnosti ≤ κ).

V resnici se izkaže, da večina jezikov L (κ, λ) sploh ni šibko κ-kompaktna in mora biti za tiste, ki to so, izjemno velik kardinal. Potrebovali bomo nekaj opredelitev.

Brezkončni kardinal κ naj bi bil zelo nedostopen, če

(a) λ <κ → λ + <κ, (kjer λ + označuje kardinalnega naslednika λ) in

(b) | I | <κ in λ i <κ (za vse i ∈ I) ⇒ ∑ i ∈ I λ i <κ.

Če poleg

(c) λ <κ ⇒ 2 λ <κ,

potem naj bi bilo κ (močno) nedostopno. Ker je ℵ 0 nedostopno, je običajna praksa omejiti pozornost na tiste nedostopne ali slabo dostopne kardinale, ki presegajo ℵ 0. V skladu s tem bodo nedostopni ali slabo dostopni kardinali vedno obravnavani kot nesprejemljivi. Jasno je, da morajo biti takšni kardinali - če obstajajo - izjemno veliki; in izrek Gödlova o nepopolnosti kaže, da obstoja celo šibko dostopnih kardinalov ni mogoče dokazati iz običajnih aksiomov teorije množic.

Kardinal kličemo κ kompaktno (torej šibko kompakten), če je jezik L (κ, κ) κ-kompakten (torej šibko κ-kompakten). Nato imamo naslednje rezultate:

(3.1) ℵ 0 je kompakten. To je seveda le jedrten način izražanja izrek o kompaktnosti za jezike prvega reda.

(3.2) κ je šibko kompakten ⇒ L (κ, ω) je šibko κ- kompakten ⇒ κ je šibko nedostopen. V skladu s tem je skladno (z običajnimi aksiomi teorije množic) domneva, da noben jezik L (κ, ω) z κ ≥ ω 1 ni dovolj κ-kompakten ali, atiotiori, slabo κ-popoln.

(3.3) Predpostavimo, da je κ nedostopna. Potem je κ šibko kompakten ⇔ L (κ, ω) je šibko κ- kompakten. Prav tako je tudi κ šibko kompakten ⇒ pred κ je niz κ nedostopnih. Tako je šibko kompakten nedostopni kardinal izjemno velik; zlasti ne more biti prvi, drugi, …, nth, … nedostopen.

(3.4) κ je kompakten, κ κ je nedostopen. (Toda rezultat, ki je takoj zgoraj, obratno ne uspe.)

Naj Constr stoji za Gödelov aksiom konstrukbilnosti; opomnimo, da je Constr skladen z običajnimi aksiomi teorije množic.

(3.5) Če Constr drži, potem ni kompaktnih kardinalov.

(3.6) Predpostavimo, da je Constr in naj bo κ nedostopna. Potem je κ šibko kompakten ⇔ L (ω 1, ω), šibko κ- kompakten za vse L.

(3.7) Če drži Constr, potem ni kardinalov κ, za katere je L (ω 1, ω) kompakten. Skladno s tem je skladno z običajnimi aksiomi teorije množic domneva, da ni kardinala κ tako, da so vsi jeziki L (ω 1, ω) κ-popolni. Ta rezultat je v nasprotju s tem, da so vsi jeziki prvega reda ω-popolni.

Uvoz teh rezultatov je, da izrek kompaktnosti za večino jezikov L (κ, λ) z κ ≥ ω 1 ne deluje zelo slabo.

Nekaj zgodovinskih pripomb je na vrsti tukaj. V tridesetih letih prejšnjega stoletja so matematiki raziskovali različne različice tako imenovanega problema meritev za množice, ki so nastale v povezavi s teorijo Lebesgue mere o kontinuumu. Zlasti je bil oblikovan naslednji zelo preprost pojem ukrepa. Če je X množica, je (X aditivno dvomestno netrivialno) merilo na X preslikava μ na množico moči P X na množico {0, 1}, ki izpolnjuje:

(a) μ (X) = 1, (b) μ ({x}) = μ (∅) = 0 za vse x ∈ X in

(c) če je A katera koli številska družina medsebojno ločenih podskupin X, je μ (∪ A) = ∑ {μ (Y): Y ∈ A }.

Očitno je, ali določeni niz podpira takšen ukrep, odvisno samo od njegove kardinalnosti, zato je naravno, da se kardinal κ definira kot merljiv, če vsi sklopi kardinalnosti κ podpirajo takšno merilo. Hitro je bilo ugotovljeno, da mora biti merljivi kardinal nedostopen, a lažnost obratnega je bila ugotovljena šele v šestdesetih letih prejšnjega stoletja, ko je Tarski pokazal, da so merljivi kardinali šibko kompaktni, njegov učenec Hanf pa je pokazal, da prvi, drugi itd. Nedostopni niso slabo kompakten (prim. (3.3)). Čeprav je ugotovitev, da morajo biti merljivi kardinali monstruozno veliki, zdaj običajno dokazana, ne da bi se sprehodili s šibko kompaktnostjo in infinitarnimi jeziki, ostaja dejstvo, da so te ideje uporabljene za določitev rezultata na prvi stopnji.

4. Nepopolnost jezikov neskončno kvantifikatorja

Verjetno najpomembnejši rezultat o jezikih prvega reda je Gödelov izrek o popolnosti, ki seveda pravi, da je nabor vseh veljavnih formul katerega koli jezika prvega reda L mogoče generirati iz preprostega niza aksiomov s pomočjo nekaj neposrednih pravil sklepanje. Glavna posledica tega izrekanja je, da če so formule L na nek konstruktiven način kodirane kot naravna števila, potem je nabor (kod) veljavnih stavkov rekurzivno številčen. Tako popolnost jezika prvega reda pomeni, da je nabor njegovih veljavnih stavkov mogoče določiti na zelo preprost način. Zato bi bilo smiselno, če bi poljuben jezik L preoblikoval to vsebino in predlagal, če je niz veljavnih L-sodnosti ni mogoče določiti na preprost način, potem za L ni mogoče ugotoviti nobenega smiselnega rezultata popolnosti ali, kot bomo rekli, da je L nepopoln. V tem razdelku bomo uporabili ta predlog za skiciranje dokaza, da je "večina" neskončnih količinskih jezikov v tem smislu nepopolnih.

Naj najprej predstavimo formalni pojem določljivosti. Če je L jezik, A - L struktura in X podvrsta domene A of A, rečemo, da je X določljiv v A s formulo φ (x, y 1,…, y n) L, če obstaja je zaporedje 1, …, A n elementov zasnovan, da je x podmnožica vseh elementov x ∈ A, za katero φ (x, A 1, …, A n) ima v A.

Zdaj napišite Val (L) za niz vseh veljavnih L- izrazov, torej tistih, ki vsebujejo vsako L- strukturo. Za dodelitev pomena stavku "Val (L) je mogoče določiti", moramo določiti

  1. struktura C (L) - kodirna struktura za L;
  2. poseben zemljevid z enim samim - kodirni zemljevid - nabora formul L v domeno C (L).

Potem, če identificiramo Val (L) s svojo sliko v C (L) v kodirnem zemljevidu, bomo izjavo "Val (L) določljiv" razlagali kot stavek "Val (L), ki velja za podmnožico domena C (L), ki jo je mogoče določiti v C (L) s formulo L."

Na primer, ko L je prvega reda jezik L aritmetika, Gödel prvotno uporabljena kot kodiranje strukturi standardni model aritmetično ℕ in kot kodiranje zemljevid znano funkcijo, pridobljene od predsednika razcepa izrek za naravnih števil. Rekurzivna številčnost Val (L) potem preprosto pomeni, da je nabor kod ("Gödlove številke") članov Val (L) določljiv v ℕ z L-formulo v obliki ∃ y φ (x, y), kjer je φ (x, y) rekurzivna formula.

Druga, enakovredna, kodirna struktura za aritmetični jezik prvega reda je struktura [5] ⟨H (ω), ∈ ⨡ H (ω)⟩ dedno končnih nizov, kjer je množica x dedno končna, če x, njeni člani, njeni člani članov itd., so vsi končni. Ta struktura kodiranja upošteva dejstvo, da se formule prvega reda seveda štejejo za končne množice.

Zdaj, ko gre za primer, v katerem je L infinitarni jezik L (κ, λ), kakšna bi bila v tem primeru primerna struktura kodiranja? Na začetku smo opozorili, da je infinitarne jezike predlagala možnost razmišljanja formul kot postavljenih teoretičnih predmetov, zato poskusimo pridobiti našo kodirno strukturo z razmišljanjem o tem, kakšne množice s teoretičnimi predmeti bi morali sprejeti kot infinitarne formule. Glede na dejstvo, da je za vsako φ∈ oblika, so (κ N, N), φ in njenih subformulas, subsubformulas itd vse dolžine <κ, [6]trenutek premislek razkrije, da formule L (κ, λ) "ustrezajo" setom x dedno kardinalnosti <κ v smislu, da so x, njeni člani, člani članov itd. vsi kardinalnosti <κ. Zbirka vseh takih sklopov je zapisana H (κ). H (ω) je zbirka zgoraj naštetih dedno omejenih nizov, H (ω 1) pa skupina vseh dedno štetljivih nizov.

Za poenostavitev predpostavimo, da je edini ekstraloški simbol osnovnega jezika L binarni predikatni simbol ∈ (razprava se zlahka razširi na primer, v katerem L vsebuje dodatne ekstraloške simbole). Na podlagi zgornjih ugotovitev kot kodirno strukturo za L (κ, λ) vzamemo strukturo,

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

Sedaj lahko določite kodiranje zemljevid Obrazec (κ N, N) v H (κ). Najprej vsakemu osnovnemu simbolu s L (κ, λ) dodelimo kodni objekt s ∈ H (κ) na naslednji način. Naj bo {v ξ: ξ <κ} naštevanje posameznih spremenljivk L (κ, λ).

Simbol Objekt kode Zapis
¬ 1 ¬
2
3
4
5
= 6 =
v ξ ⟨0, ξ⟩ v ξ

Nato vsakem φ ∈ obrazcu (κ, λ) dodelimo kodni objekt φ rekurzivno, kot sledi:

proti ξ = V 'H = df proti ξ , = , proti ' H ⟩, proti £ ∈ proti 'H = df proti £ , , proti ' H ⟩;

za φ, ψ ∈ oblika (κ, λ),

φ ∧ ψ = df φ , , ψ

¬φ = df ¬ , φ

∃ X φ = df, { x : x ∈ X}, φ ⟩;

in končno, če je Φ ⊆ obrazec (κ, λ) z | Φ | <κ,

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

Na zemljevidu ↦ φ φ iz Form (κ N, N) je H (κ) se lahko vidi, da je 1-1 in je zahtevana kodiranja zemljevid. V skladu s tem se strinjamo, da bomo na tej kodirni karti identificirali Val (L (κ, λ)) s svojo sliko v H (κ).

Kdaj je Val (L (κ, λ)) določljiva podmnožica H (κ)? Za odgovor na to vprašanje potrebujemo naslednje opredelitve.

Formula L se imenuje Δ 0 - formula, če je enakovredna formuli, v kateri so vsi kvantifikatorji v obliki ∀ x ∈ y ali ∃ x ∈ y (tj. (X (x ∈ y →…) ali ∃ x (x ∈ y ∧…)). Formula L je formula Σ 1, če je enakovredna tisti, ki jo je mogoče sestaviti iz atomskih formul in njihovih negacij z uporabo le logičnih operaterjev ∧, ∨, ∀ x ∈ y, ∃ x. Za podvrsto X niza A naj bi bilo Δ 0 (odsek Σ 1) na A, če je v strukturi ⟨A, ∈ ⨡ A def določljivo s formulo Δ 0 - (torej Σ 1 -) iz L.

Če na primer identificiramo množico naravnih števil z množico H (ω) dedno končnih nizov na običajen način, imamo za vsak X ⊆ H (ω):

X je Δ 0 na H (ω) ⇔ X je rekurziven

X je Σ 1 na H (ω) ⇔ X je rekurzivno številčno.

Tako lahko pojma Δ 0 - in Σ 1 - štejemo kot posploševanja pojmov rekurzivni in rekurzivno številčni niz.

Teorem o popolnosti za L pomeni, da je Val (L) - ki ga štejemo za podmnožico H (ω) - rekurzivno števljiv in zato Σ 1 na H (ω). Podobno iz teorema popolnosti za L (ω 1, ω) (glej §2) sledi, da je Val (L (ω 1, ω)) - ki ga štejemo za podmnožico H (ω 1) - Σ 1 na H (ω 1). Vendar se to prijetno stanje popolnoma zruši, takoj ko dosežemo L (ω 1, ω 1). Za eno se lahko dokaže

Scottova teorem o nedefiniranosti za L (ω 1, ω 1). Val (L (ω 1, ω 1)) v H (ω 1) ni mogoče določiti niti s formulo L (ω 1, ω 1); torej a fortiori Val (L (ω 1, ω 1)) na H (ω 1) ni Σ 1.

Ta izrek je izkazalo na skoraj enak način, kot je znano, tako da komplet (kodeksov) veljavnih stavkov jezika v drugega reda v arithemetic L 2 ni drugega reda, opredeljeno v kodiranja strukturi ℕ. Da bi dobili ta slednji rezultat, ena najprej ugotavlja, da je ℕ značilna ena L 2 -sentence, nato pa kaže, da, če bi bila posledica napačne, potem je "resnica v ℕ" za L 2 -sentences bi bilo opredeljeno z L 2 -formula, s čimer se krši Tarski izrek o nedoločljivosti resnice.

V skladu s tem je za dokaz Scottovega teorema o nedoločljivosti treba določiti:

(4.1) Karakterističnost kodirne strukture H (ω 1) v L (ω 1, ω 1): obstaja L (ω 1, ω 1) -razsežnost τ 0, tako da je za vse L-strukture A, A ⊨ τ 0A ≅ H (ω 1).

(4.2) Nedoločljivost resnice za L (ω 1, ω 1) - stavki v kodirni strukturi: L (ω 1, ω 1) -formule φ (v 0) ni takšne, da bi za vse L (ω 1, ω 1) -sodnosti σ, H (ω 1) ⊨ σ↔φ ( σ ).

(4.3) Obstaja izraz t (v 0, v 1) L (ω 1, ω 1), tako da je za vsak par stavkov σ, τ L (ω 1, ω 1), H (ω 1) ⊨ [t ( σ , τ ) = σ → τ ].

(4.1) je dokazano z analizo številčno-teoretične definicije H (ω 1) in pokaže, da jo je mogoče "interno" formulirati v L (ω 1, ω 1). (4.2) je vzpostavljen na približno enak način kot Tarski izrek o nedoločljivosti resnice za jezike prvega ali drugega reda. (4.3) dobimo s formalizacijo definicije kodirne karte σ ↦ σ v L (ω 1, ω 1).

Oboroženi s temi dejstvi lahko dobimo Scottovega teorema o nedoločljivosti na naslednji način. Recimo, da je bila napačna; potem bi obstajala L (ω 1, ω 1) -formula θ (v 0) taka, da je za vse L (ω 1, ω 1) -sodnosti σ,

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

Naj bo τ 0 stavek iz (4.1). Potem imamo za vse L (ω 1, ω 1) -sodnosti σ,

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

tako da (4.4)

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

Če je t izraz, naveden v (4.3), bi sledil temu

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

Zdaj napišite φ (v 0) za L (ω 1, ω 1) -formulo θ (t ( τ 0 , σ )). Potem

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

v nasprotju (4.2) in dopolni dokaz.

Tako Val (L (ω 1, ω 1)) ni mogoče določiti niti s formulo L (ω 1, ω 1), zato je fortiori L (ω 1, ω 1) nepopoln. Podobni argumenti kažejo, da Scottov teorem o nedoločljivosti še naprej velja, kadar ω 1 nadomesti kateri koli naslednik kardinala κ +; zato so jeziki L (κ +, κ +) vsi nepopolni. [7]

5. Podjezika L (ω 1, ω) in teorem barverzne kompaktnosti

Glede na to, kar zdaj vemo o infinitarnih jezikih, se zdi, da je L (ω 1, ω) edini, ki ga je mogoče dobro obnašati. Po drugi strani pa je neuspeh teorema o kompaktnosti na kakršen koli uporaben način posplošljiv na L (ω 1, ω), kar zadeva aplikacije. Poskusimo podrobneje analizirati to napako.

Iz §4 se spomnimo, da lahko formule jezika prvega reda L kodiramo kot dedno končne množice, tj. Kot člane H (ω). V tem primeru je vsak končni niz (kodi) stavkov L tudi član H (ω) in iz tega sledi, da lahko izrek kompaktnosti za L navedemo v obliki:

(5.1) Če je Δ ⊆ poslano (L) takšno, da ima vsaka podvrsta Δ 0 ⊆ Δ, Δ 0 ∈ H (ω) model, potem tudi Δ.

Zdaj je dobro znano, da je (5.1) neposredna posledica posplošenega teorema popolnosti za L, ki v obliki, podobni obliki iz (5.1), postane trditev:

(5.2) Če Δ ⊆ Sent (L) in σ ∈ Sent (L) izpolnjujeta Δ ⊨ σ, potem je odbitek D σ od Δ tako, da je D ∈ H (ω). [8]

V §2 smo ugotovili, da izrek kompaktnosti za L (ω 1, ω) zelo močno ne uspe; pravzaprav smo konstruirali niz Γ ⊆ Poslano1, ω), tako da

(5.3) Vsaka številska podvrsta Γ ima model, vendar Γ ne.

Spomnimo se tudi, da smo uvedli pojem odbitka v L (ω 1, ω); ker so takšni odbitki štetljive dolžine, iz (5.3) hitro izhaja, da

(5.4) Obstaja stavek [9] σ ∈ Sent1, ω) tak, da je Γ ⊨ σ, vendar v L (ω 1, ω) od Γ ni odbitka σ.

Zdaj lahko formule L (ω 1, ω) kodiramo kot člane H (ω 1), in jasno je, da je H (ω 1) zaprt pod tvorbo števnih podmnožic in zaporedij. V skladu s tem (5.3) in (5.4) se lahko zapiše:

(5.3 bis) Vsak Γ 0 ⊆ Γ tak, da ima Γ 0 ∈ H (ω 1) model, vendar Γ ne;

(5.4 bis) Obstaja stavek σ ∈ Sent1, ω), da je Γ ⊨ σ, vendar odbitka D ∈ H (ω 1) od σ od Γ ni.

Iz tega sledi, da (5.1) in (5.2) ne uspeta, kadar „L“nadomesti z „L (ω 1, ω)“in „H (ω)“z „H (ω 1)“. Poleg tega je mogoče pokazati, da je množica Γ ⊆ poslana1, ω) v (5.3 bis) in (5.4 bis) lahko Σ 1 na H (ω 1). Torej teoremi kompaktnosti in posplošene popolnosti ne uspevajo niti za Σ 1 -se skupine L (ω 1, ω) -sodnosti.

Iz (5.4 bis) vidimo, da je razlog, da posplošena teorema popolnosti ne izpolnjuje Σ 1 -seštevilk L (ω 1, ω), ta, da grobo rečeno, H (ω 1) pri tvorbi odbitkov ni "zaprt" iz Σ 1 -setov stavkov v H (ω 1). Da bi to odpravili, bi bilo naravno, da bi H (ω 1) nadomestili z množicami A, ki so v določenem smislu zaprte pri oblikovanju takšnih odbitkov, nato pa bi upoštevali samo tiste formule, katerih kodi so v A.

Zdaj dajemo skico, kako je to mogoče storiti.

Najprej prepoznamo simbole in formule L (ω 1, ω) s svojimi kodami v H (ω 1), kot v §4. Za vsak števni prehod [10] nastavimo A, pustimo

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

Pravimo, da je L A podjezik L (ω 1, ω), če so izpolnjeni naslednji pogoji:

  1. L ⊆ L A
  2. če φ, ψ ∈ L A, potem φ ∧ ψ ∈ L A in ¬φ ∈ L A
  3. če sta φ ∈ L A in x ∈ A, potem je ∃ x φ ∈ L A
  4. če sta φ (x) ∈ L A in y ∈ A, potem je φ (y) ∈ L A
  5. če je φ ∈ L A, je vsaka podformula φ v L A
  6. če Φ ⊆ L in Φ ∈ A, potem ∧Φ ∈ L A.

Pojem odbitka v L A je opredeljen na običajen način; če Δ je niz stavkov L A in φ ∈ L A, nato odšteje φ iz Í v L A je odbitek φ iz Í v L (ω 1, ω), od katerih vsak formulo V L A. Pravimo, da je φ mogoče sklepati iz Δ v L A, če je odbitek D φ od Δ v L A; pod temi pogoji zapišemo Δ ⊢ A φ. Na splošno D ne bo član A; da bi zagotovili, da je mogoče takšen odbitek najti v A, bo treba A postaviti dodatne pogoje.

Naj bo števno prehodni nastavi tako, da L je na sublanguage L (ω 1, w) in pustimo Δ se sklop stavkov L A. Pravimo, da je A (ali z zlorabo terminologije L A) zaprt za Δ, če za katero koli formulo φ L A, tako da je Δ A, odbitek D φ od Δ, tako da je D ∈ A. Pokaže se, da je edini števni jezik, ki je Δ-zaprt za poljuben Δ, jezik prvega reda L, torej kadar je A = H (ω). Vendar je J. Barwise odkril, da obstajajo številčne množice A ⊆ H (ω 1), katerih ustrezni jeziki L A se razlikujejo od L in so Δ-zaprti za vse Σ 1- množice stavkov Δ. Takšni nizi A se imenujejo dopustni nizi; v grobem gledano gre za podaljške dedno omejenih skupin, v katerih je teorija rekurzije - in s tem tudi dokazna teorija - še mogoča (za popolno opredelitev glej oddelek 5.1 spodaj).

Iz Barwise rezultata dobimo takoj

Izrek tečaja kompaktnosti. Naj je A števen dopustni niz in naj bo Δ niz stavkov L A, ki je Σ 1 na A. Če ima vsak Δ '⊆ Δ tak, da ima Δ' ∈ A model, potem to velja tudi za Δ.

Prisotnost "Σ 1 " tukaj kaže, da je ta izrek posploševanje teorema kompaktnosti za rekurzivno naštete nize stavkov.

Naslednja različica teorema kompaktnosti Barwise, uporabna za konstruiranje modelov teorije množic, je naslednja. Naj ZFC je običajno niz aksiomov za Zermelo-Fraenkel teorije množic, vključno z aksiom izbire. Potem imamo:

5.5 Teorem. Naj bo A števen prehodni niz, takšen, da je A = ⟨A, ∈ ⨡ A⟩ model ZFC. Če je Δ nabor stavkov L A, ki ga je v A mogoče določiti s formulo jezika teorije množic in če ima vsak Δ '⊆ Δ tak, da ima Δ' ∈ A model, potem tudi Δ.

Za zaključek podajamo preprosto uporabo tega izrekanja. Naj bo A = ⟨A, ∈ ⨡ A⟩ model ZFC. Model B = ⟨B, E⟩ ZFC naj bi bil pravi končni podaljšek A, če (i) AB, (ii) AB, (iii) a ∈ A, b ∈ B, bEa ⇒ b ∈ A. Zato je ustrezna končnica modela ZFC pravilno končnica, v kateri noben „nov“element ne pride „pred“noben „stari“element. Kot je naša uporaba 5,5 dokazujemo

5.6 Izrek. Vsak števni prehodni model ZFC ima ustrezen končni podaljšek.

Dokaz. Naj je A = ⟨A, ∈ ⨡ A⟩ prehodni model ZFC in naj bo L jezik prvega reda teorije množic, dopolnjen z imenom a za vsakega a ∈ A in dodatno konstanto c. Naj bo Δ nabor L - stavkov, ki obsega:

  • vsi aksiomi ZFC;
  • ca, za vsako a ∈ A;
  • ∀ x (x ∈ a → ∨ b ∈ a x = b), za vsako a ∈ A;
  • ab, za vsako a ∈ b ∈ A.

Z lahkoto je razvidno, da je Δ podvrsto A, ki jo je v A mogoče določiti s formulo jezika teorije množic. Prav tako ima vsaka podvrsta Δ '⊆ Δ takšna, da ima Δ' ∈ A model. Za množico C vseh a ∈ A, ki se pojavi v Δ ', spada v A - saj Δ' to deluje - in tako, če razlagamo c kot katerega koli člana (nujno nepopolnega) množice A - C, potem je A a model Δ '. V skladu s tem (5.5) pomeni, da ima Δ model ⟨B, E⟩. Če razlagamo vsak konstantno a kot element a ∈ A, potem ⟨B, E⟩ je pravilno končni podaljšek A. Dokaz je popoln.

Bralec bo hitro videl, da izrek kompaktnosti prvega reda ne bo prinesel tega rezultata.

5.1 Opredelitev koncepta dopustnega niza

Nepopolni prehodni niz A naj bi bil dopusten, če so izpolnjeni naslednji pogoji:

  1. če je a, b ∈ A, potem {a, b} ∈ A in ∪ A ∈ A;
  2. če sta a ∈ A in X ⊆ A Δ 0 na A, potem je X ∩ a ∈ A;
  3. če je a ∈ A, X ⊆ A Δ 0 na A in ∀ x ∈ a ∃ y (<x, y> ∈ X), potem je pri nekaterih b ∈ A ∀ x ∈ a ∃ y ∈ b (<x, y> ∈ X).

Pogoj (ii) - shema ločevanja Δ 0 - je omejena različica Zermelovega aksioma ločitve. Pogoj (iii) - podobno oslabljena različica nadomestitvenega aksioma - lahko imenujemo shema nadomestitve Δ 0.

Precej enostavno je videti, da če je A prehodna množica taka, da je <A, ∈ | A> je model ZFC, potem je A dovoljen. Na splošno velja, da rezultat še naprej velja, če izpustimo aksiom nastavljene moči iz ZFC, tako da sta dopustna tako H (ω) kot H (ω 1). Ker pa slednje ni mogoče šteti, izrek Barwise kompaktnosti zanj ne velja.

6. Zgodovinske in bibliografske opombe

§ 1 in 2. Zdi se, da sta se infinitarni propozicijski in predikatni prvi izrecno pojavili v tisku z dokumenti Scotta in Tarskega [1958] in Tarskega [1958]. Teorem o popolnosti za L (ω 1, ω), pa tudi za druge infinitarne jezike, je dokazal Karp [1964]. Izračun Hanfovega števila za L (ω 1, ω) je prvi izvedel Morley [1965]. Nedoločljivost vrstnega reda urejanja v jezikih s končnim kvantifikatorjem sta dokazala Karp [1965] in Lopez-Escobar [1966]. Interpolacijski izrek za L (ω 1, ω) je dokazal Lopez-Escobar [1965], Scottov izomorfizem za L (ω 1, ω) pa Scott [1965].

Karpov teorem o delnem izomorfizmu je bil prvič dokazan pri Karpu [1965]; glej tudi Barwise [1973]. Rezultat (2.2) se pojavi v Changu [1968], rezultat (2.3) v Evinceucku [1976] in rezultat (2.4) v Bellu [1981].

§ 3. Rezultati (3.2) in (3.3) so posledica Hanfa [1964], z nekaj natančnostmi Lopez-Escobarja [1966] in Dickmanna [1975], medtem ko je (3.4) dokazal Tarski. Rezultat (3.5) je posledica Scotta [1961], (3.6) do Bella [1970] in [1972]; in (3.7) Bellu [1974]. Merljive kardinale sta najprej obravnavala Ulam [1930] in Tarski [1939]. To, da so merljivi kardinali šibko kompaktni, so opazili v Tarškem [1962].

§ 4. Glede izrek o nedoločljivosti za L (ω 1, ω 1). Carol Karp (1964, 166) opomni: "Na mednarodnem kongresu za logiko, metodologijo in filozofijo znanosti na univerzi Stanford leta 1960 je Dana Scott obkrožil oris dokazila o nemožnosti popolnega določljivega formalnega sistema za (γ +, γ +) jezikov z enim dvodelnim predikatnim simbolom poleg simbola enakosti. " Scott svojega rezultata nikoli ni objavil, popolnoma podroben dokaz pa se je prvič pojavil v Karpu [1964]. Pristop k teoremu, ki je bil sprejet tu, temelji na poročilu, ki ga je navedel Dickmann [1975].

§ 5. Izvirna motivacija za rezultate, predstavljene v tem razdelku, je prišla iz družbe Kreisel; v svojem [1965] je opozoril, da ni nobenih prepričljivih razlogov za izbiro infinitarnih formul izključno na podlagi "dolžine", in predlagal, da se uporabijo merila za določljivost ali "zapiranje". Kreiseljev predlog je Barwise [1967] z velikim uspehom sprejel, kjer je bil dokazan njegov izrek kompaktnosti. Pojem dopustne množice je posledica Platek [1966]. Teorem (5.6) je vzet iz Keislerja [1974].

Za nadaljnje branje o temi infinitarnih jezikov glej Aczel [1973], Dickmann [1975], Karp [1964], Keisler [1974] in Makkai [1977]. Koristno poročilo o povezavi med infinitarnimi jeziki in velikimi kardinali je na voljo v poglavju 10 Drakea [1974].

Bibliografija

  • Aczel, P., 1973, "Infinitarna logika in teorem o barradni kompaktnosti", Zborniki Memorialne logične konference Bertrand Russell iz leta 1971 (Uldum, Danska), J. Bell, J. Cole, G. Priest in A. Slomson (eds.), Leeds: Bertrand Russell Memorial Logic Conference, 234–277.
  • Barwise, J., 1967, Infinitarna logika in dopustni kompleti. Dr. Teza, Univerza Stanford.
  • –––, 1973, „Nazaj in naprej skozi neskončno logiko. Študije teorije modelov ", v Študijah matematike (zvezek 8), Buffalo: Ameriško matematično združenje, str. 5–34.
  • –––, 1975, Dovoljeni sklopi in strukture, Berlin: Springer-Verlag.
  • Barwise, J. in S. Feferman (ur.), 1985, Handbook of Model-Theoretic Logics, New York: Springer-Verlag.
  • Baumgartner, J., 1974, »Hanfova številka za popolne L ω 1, ω stavke (brez GCH)«, Journal of Symbolic Logic, 39: 575–578.
  • Bell, JL, 1970, „Šibka kompaktnost v omejenih jezikih drugega reda“, Bilten Poljske akademije znanosti, 18: 111–114.
  • –––, 1972, „O razmerju med šibko kompaktnostjo v L ω 1, ω, L ω 1, ω 1 in omejenimi jeziki drugega reda“, Arhiv za matematično logiko, 15: 74–78.
  • –––, 1974, „O kompaktnih kardinalih“, Zeitschrift za matematični Logik in Grundlagen der Mathematik, 20: 389–393.
  • –––, 1981, „Izomorfizem struktur v S-topovih“, Journal of Symbolic Logic, 43 (3): 449–459.
  • Chang, CC, 1968, "Nekaj opomb k vzorčni teoriji neskončnih jezikov". v Sintaksi in semantika neskončnih jezikov (Lekcije za matematiko: zvezek 72), J. Barwise (ur.), Springer-Verlag, Berlin, 36–63.
  • Dickmann, MA, 1975, Veliki neskončni jeziki, Amsterdam: Severna Holandija.
  • Drake, FR, 1974, Teorija kompleta: uvod v velike kardinale, Amsterdam: North-Holland Publishing Company.
  • Evinceuck, E., 1976, "Ponovna kategoričnost", Journal of Symbolic Logic, 41 (3): 639–643.
  • Hanf, WP, 1964, Nekompromisnost jezikov z neskončno dolgimi izrazi, Amsterdam: Severna Holandija.
  • Karp, C., 1964, Jeziki z izrazi neskončne dolžine, Amsterdam: Severna Holandija.
  • –––, 1965, „Končna kvantifikatorska ekvivalenca“v Teoriji modelov, J. Addison, L. Henkin in A. Tarski (ur.), Amsterdam: Severna Holandija, 407–412.
  • Keisler, HJ, 1974, Modelna teorija za infinitarno logiko, Amsterdam: Severna Holandija.
  • Keisler, HJ, in Julia F. Knight, 2004, "Barwise: Infinitary Logic in dopustne garniture", Journal of Symbolic Logic, 10 (1): 4–36
  • Kolaitis, P. in M. Vardi, 1992, »Fikspoint Logic vs. Infinitary Logic v teoriji končnih modelov«, Zbornik sedmega letnega simpozija IEEE o logiki v računalništvu (LICS '92), IEEE, str. 46–57; na voljo na spletu, doi: 10.1109 / LICS.1992.185518
  • Kreisel, G., 1965, "Modelno-teoretični invarijanti, aplikacije za rekurzivne in hiperraritmetične operacije", v Theory of Models, J. Addison, L. Henkin in A. Tarski (ur.), Amsterdam: Severna Holandija, 190–205.
  • Kueker, D., 1975, "Argumenti za nazaj in naprej v infinitarnih jezikih", v Infinitary Logic: In Memoriam Carol Karp (Lekcije za matematiko: zvezek 492), D. Kueker (ur.), Berlin: Springer-Verlag.
  • Lopez-Escobar, EGK, 1965, "Interpolacijska teorema za neskončno dolge kazni", Fundamenta Mathematicae, 57: 253–272.
  • –––, 1966, „O določitvi urejanja dobrega reda“, Fundamenta Mathematicae, 59: 13–21.
  • Makkai, M., 1977, "Dovoljeni kompleti in infinitarna logika", Priročnik matematične logike, J. Barwise (ur.), Amsterdam: North-Holland, 233-282.
  • Morley, M., 1965, "Izpuščanje razredov elementov", Teorija modelov, J. Addison, L. Henkin in A. Tarski (ur.), Amsterdam: North-Holland, 265-273.
  • Nadel, M. 1985, „L ω 1, ω in dopustni fragmenti“, J. Barwise in S. Feferman (ur.) 1985, 271–287.
  • Platek, R., 1966, Temelji teorije rekurzije, dr. Teza, Univerza Stanford.
  • Scott, D., 1961, "Merljivi kardinali in konstrukcijske garniture", Bilten Akademije poljskih znanosti, 9: 521–524.
  • –––, 1965, »Logika s številno dolgimi formulami in končnimi nizi kvantifikatorjev«, Teorija modelov, J. Addison, L. Henkin in A. Tarski (ur.), Amsterdam: Severna Holandija, 329–341.
  • Scott, D. in A. Tarski, 1958, »Čutni izračun z neskončno dolgimi izrazi«, Colloquium Mathematicum, 16: 166–170.
  • Shelah, Saharon, 2012, "Lepa infinitarna logika", Časopis Ameriškega matematičnega društva, 25: 395-427, na voljo na spletu, 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, „Opombe k predikatni logiki z neskončno dolgimi izrazi“, Colloquium Mathematicum, 16: 171–176.
  • –––, 1962, „Nekateri problemi in rezultati, pomembni za temelje teorije množic“, v E, Nagel, P. Suppes in A. Tarski (ur.), 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.

Akademska orodja

sep man ikona
sep man ikona
Kako navajati ta vnos.
sep man ikona
sep man ikona
Predogled PDF različice tega vnosa pri Društvu prijateljev SEP.
ikona
ikona
Poiščite to temo vnosa pri projektu Internet Filozofija Ontologija (InPhO).
ikona papirjev phil
ikona papirjev phil
Izboljšana bibliografija za ta vnos pri PhilPapers s povezavami do njegove baze podatkov.

Drugi internetni viri

Priporočena: