Lõpmatu Loogika

Sisenemise navigeerimine

• Sissesõidu sisu
• Bibliograafia
• Akadeemilised tööriistad
• Sõprade PDF-i eelvaade
• Teave autori ja tsitaadi kohta
• Tagasi üles

Lõpmatu loogika

Esmakordselt avaldatud Pühapäeval 23. jaanuaril 2000; sisuline redaktsioon reedel 26. veebruaril 2016

Traditsiooniliselt peetakse formaalsetes süsteemides esinevaid väljendeid tähistavateks pealdisteks, mida on vähemalt põhimõtteliselt võimalik primitiivsete märkustena välja kirjutada. Kuid asjaolu, et (esimese järgu) valemeid saab identifitseerida naturaalarvudega (Gödeli nummerdamise kaudu) ja seega ka piiratud komplektide abil, ei nõua enam valemeid pealdistena, ja see soovitab võimalust moodustada mõned keeled. kelle valemeid saaks loomulikult määratleda lõpmatute komplektidena. Sellist "keelt" nimetatakse infinitaarseks keeleks: selles artiklis käsitlen neid infinitaarseid keeli, mida on võimalik saada otse esimese astme keeltest, võimaldades konjunktsioonide, disjunktsioonide ja võimaluse korral kvantitatiivsete jadade lõpmatust. pikkus. Arutelu käigus selgub, et kuigi selliste keelte väljendusjõud ületab tunduvalt nende lõplike (esimese järgu) keelte oma, on väga vähestel neist keelte „atraktiivsed” omadused (nt kompaktsus ja terviklikkus). viimane. Seetõttu väärivad erilist tähelepanu infinitaarsed keeled, millel need omadused tegelikult on.

Paragrahvis 1 on sätestatud infinitaarsete keelte põhisüntaks ja semantika; nende väljendusjõudu kuvatakse seejärel näidete abil. Lõige 2 on pühendatud neile infinitaarsetele keeltele, mis võimaldavad ainult piiratud kvantitatiivseid jadasid: need keeled osutuvad suhteliselt hästi käituvateks. Lõige 3 on pühendatud infinitaarsete keelte kompaktsusprobleemile ja selle seosele puhtalt setteoreetiliste küsimustega, mis käsitlevad „suuri” kardinalinumbreid. Lõikes 4 visandatakse argument, mis näitab, et enamikul „lõpmatu kvantifikaatori” keeltest on teise astme keeled ja nad on ipso facto väga puudulikud. §5 annab lühiülevaate infinitaarsete keelte teatavast alamkeelte eriklassist, mille puhul saab kompaktsuse teoreemi rahuldavat üldistust tõestada. See jaotis sisaldab alajaotust lubatud komplektide määratluse kohta. Ajaloolised ja bibliograafilised märkused on esitatud lõikes 6.

• 1. Lõpmatute keelte määratlus ja põhilised omadused
• 2. Piiratud kvantifikaatori keeled
• 3. Kompaktsusomadused
• 4. Lõpmatute ja kvantitatiivsete keelte puudulikkus
• 5. L (ω ₁, ω) alamkeeled ja Barwise kompaktsuse teoreem

  5.1 Lubatava komplekti mõiste määratlus

• 6. Ajaloolised ja bibliograafilised märkused
• Bibliograafia
• Akadeemilised tööriistad
• Muud Interneti-ressursid
• Seotud kirjed

1. Lõpmatute keelte määratlus ja põhilised omadused

Arvestades lõpmatute kardinalide paari κ, λ, nii et λ ≤ κ, määratleme lõpmatute keelte klassi, millest igaühes võime moodustada kardinaalsuse valemi kogumite <κ) ühendusi ja disjunktsioone <κ ning kvantifitseerimisi pikkuse muutujate jadade korral < λ.

Olgu L - (finitaarne) baaskeel - suvaline, kuid fikseeritud esimese astme keel mis tahes arvu ekstraloogiliste sümbolitega. Infinitaarsel keelel L (κ, λ) on järgmised põhisümbolid:

• Kõik sümbolid L
• Üksikute muutujate hulk Var, kus variandi (kirjutatud: | Var |) kardinaalsus on κ
• Loogiline operaator ∧ (infinitaarne konjunktsioon)

Eelvormide klass L (κ, λ) on rekursiivselt määratletud järgmiselt:

• Iga L valem on eelvorm;
• kui φ ja ψ on eelvormid, siis on ka φ∧ψ ja ¬φ;
• kui Φ on eelvormide kogum, mis | Φ | <κ, siis ∧Φ on eelvorm;
• kui φ on eelvorm ja X ⊆ Var on selline, et | X | <λ, siis ∃ X φ on eelvorm;
• kõik eelvormid on määratletud ülaltoodud klauslitega.

Kui Φ on eelvormide kogum, mida indekseeritakse hulgaga I, näiteks Φ = {φ _i: i ∈ I}, lepime kokku, et kirjutame ∧Φ jaoks:

∧ _{i ∈ I}  φ

või kui ma olen naturaalarvude kogum, kirjutame ∧Φ:

φ ₀ ∧ φ ₁ ∧ …

Kui X on individuaalsete muutujate kogum, mida indekseeritakse ordinaalse α abil, näiteks X = {x _ξ: ξ <α}, lepime kokku, et kirjutame (∃ x _ξ) _{ξ <α} φ ∃ X φ jaoks.

Loogilised operaatorid ∨, →, ↔ on määratletud tavapärasel viisil. Tutvustame ka operaatoreid ∨ (infinitaarne disjunktsioon) ja ∀ (universaalne kvantifitseerimine)

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

∀Xφ = _df ¬∃X¬φ,

ja kasutada sarnaseid tavasid nagu ∧, ∃.

Seega L (κ, λ) on infinitaarne keel, mis saadakse L-st, lubades konjunktsioone ja disjunktsioone pikkusega <κ ja kvantifitseerimisega ^[1] pikkusega <λ. Keeli L (κ, ω) nimetatakse lõplikeks kvantifikaatorkeelteks, ülejäänud lõpmatu kvantifikaatori keelteks. Pange tähele, et L (ω, ω) on lihtsalt L ise.

Pange tähele järgmist kõrvalekallet, mis võib tekkida infinitaarses keeles, kuid mitte finitaarses keeles. Keeles L (ω ₁, ω), mis lubab loendamatuid konjunktsioone, kuid ainult piiritletud kvantifikatsioone, on eelvorme, kus on nii palju vabu muutujaid, et neid ei saa kvantifikaatorite eesliite abil L-lauseteks (ω ₁, ω) lauseteks sulgeda. See kehtib näiteks L (ω ₁, ω) -vormi kohta

x ₀ <x ₁ ∧ x ₁ <x ₂ ∧… ∧ x _n <x _{n +1} …,

kus L sisaldab kahendsuhte sümbolit <. Sel põhjusel teeme järgmist

Definitsioon. Valem L (κ, λ) on eelvorm, mis sisaldab <λ vabu muutujaid. Kõigi L (κ, λ) valemite komplekti tähistatakse vormiga (L (κ, λ)) või lihtsalt vormiga (κ, λ) ja kõigi lausete komplektiga Saadetud (L (κ, λ)) või lihtsalt saadetud (κ, λ).

Sellega seoses pange tähele, et üldiselt ei saa midagi kasu, kui vaadelda “keeli” L (κ, λ) λ> κ-ga. Näiteks on keeles „L” (ω, ω ₁) valemites ainult lõplikult palju vabu muutujaid, samas kui on hulk „kasutuid” kvantiive, mis suudavad siduda lõpmata palju vabu muutujaid. ^[2]

Olles määratlenud L (κ, λ) süntaksi, visandame järgnevalt selle semantika. Kuna L (κ, λ) ekstraloogilised sümbolid on lihtsalt L sümbolid ja just need sümbolid määravadki nende struktuuride kuju, milles antud esimese astme keelt tuleb tõlgendada, on loomulik määratleda L (κ, λ) -struktuur peab olema lihtsalt L-struktuur. Mõiste valemist L (κ, λ), mis vastab L-struktuurile A (elementide jadaga domeenist A), on määratletud samal induktiivsel viisil nagu valemi L korral, välja arvatud see, et peame lisama kaks lisaklauslid, mis vastavad form ja ∃Xφ lausetele eelvormi määratluses. Nendel kahel juhul määratleme loomulikult:

∧Φ on rahul A-ga (antud jada järgi) ⇔ kõigi φ ∈ Φ puhul, φ on rahul A-ga (jada järgi);

∃ X φ on täidetud ⇔ on jada elemendid domeeni sisse bijective kirjavahetus X, mis rahuldab ep sisse.

Neid mitteametlikke määratlusi tuleb rangelt täpsustada, kuid nende tähendus peaks olema lugejale selge. Nüüd on saadaval L (κ, λ) valemite ja lausete tavapärased tõe, kehtivuse, rahuldatavuse ja mudeli valemid ja laused. Eriti juhul, kui on L-struktuur ja σ ∈ Saadetud (κ, λ), me kirjutada ⊨ σ jaoks on mudel σ ja ⊨ σ jaoks σ kehtib, see on kõik, ⊨ σ. Kui Δ ⊆ Saadetud (κ, λ), kirjutame Δ ⊨ σ, et σ on Δ loogiline tagajärg, see tähendab, et Δ iga mudel on σ mudel.

Toome nüüd mõned näited, mis on ette nähtud infinitaarsete keelte L (κ, λ) väljendusjõu kuvamiseks κ ≥ ₁. Mõlemal juhul on üldteada, et kõnealust mõistet ei saa väljendada üheski esimese astme keeles.

Aritmeetika standardmudeli iseloomustus L (ω ₁, ω). Aritmeetika standardmudel on siin struktuur N = ⟨N, +, ·, s, 0⟩, kus N on naturaalarvude kogum, +, · ja 0 omavad tavapärast tähendust ja s on sellele järgnev toiming. Olgu L N -le sobiv esimese astme keel. Siis langeb N -le isomorfse L-struktuuride klass kokku järgmiste L (ω ₁, ω) lausete (kus 0 on 0- nimeline nimi) konjunktsiooni mudeliklassiga:

∧ _{m ∈ω} ∧ _{n ∈ω} s ^m 0 + s ⁿ 0 = s ^{m + n} 0

∧ _{m ∈ω} ∧ _{n ∈ω} s ^m 0 · s ⁿ 0 = s ^{m · n} 0

∧ _{m ∈ω} ∧ _{n ∈ω− {m}} s ^m 0 ≠ s ⁿ 0

∀ x ∨ _{m ∈ω} x = s ^m 0

Mõisted s ⁿ x määratletakse rekursiivselt

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

Kõigi lõplike komplektide klassi iseloomustus L (ω ₁, ω). Baaskeeles puuduvad siin ekstraloogilised sümbolid. Kõigi piiritletud komplektide klass langeb siis kokku L (ω ₁, ω) -osavuse mudeliklassiga.

∨ _{n ∈ω} ∃ v ₀ … ∃ v _n ∀ x (x = v ₀ ∨… ∨ x = v _n).

Tõestusmõiste L-ga (ω ₁, ω) loendatava baaskeele L jaoks. Olgu L loendatav esimese astme keel (näiteks aritmeetika või komplektiteooria keel), mis sisaldab nime n iga naturaalarvu n jaoks, ja olgu σ ₀, σ ₁,… selle lausete loend. Siis L (ω ₁, ω) -valem

Tr (x) = _df ∨ _{n ∈ω} (x = n ∧ σ _n)

on tõe predikaat L-le, niivõrd kui lause

Tr (n) ↔ σ _n

kehtib iga n kohta.

Hästi tellimuste iseloomustus L-ga (ω ₁, ω ₁). Baaskeel L hõlmab kahendkomponendi sümbolit ≤. Olgu σ ₁ tavaline L-lause, mis iseloomustab lineaarset järjestust. Siis langeb L-struktuuride klass, milles ≤ tõlgendus on hästi järjestatud, kokku lause L (ω ₁, ω ₁) lause σ = σ ₁ ∧ σ ₂ mudelite klassiga, kus

σ ₂ = _df (∀ v _n) _{n ∈ω} ∃ x [∨ _{n ∈ω} (x = v _n) ∧ ∧ _{n ∈ω} (x ≤ v _n)].

Pange tähele, et lause σ ₂ sisaldab lõpmatut kvantifikaatorit: see väljendab sisuliselt teise järgu väidet, et igal loendataval alamhulgal on vähim liige. Tegelikult saab näidata, et selle lõpmatu kvantifikaatori olemasolu on hädavajalik: hästi järjestatud struktuuride klassi ei saa iseloomustada üheski piiratud kvantitatiivses keeles. See näide näitab, et lõpmatu kvantifikaatori keeled, nagu L (ω ₁, ω ₁), käituvad pigem teise järgu keeltena; näeme, et neil on nii viimaste puudusi (puudulikkus) kui ka mõnda nende eelist (tugev väljendusjõud).

Paljusid esimese astme keelte laiendusi saab tõlkida infinitaarsetesse keeltesse. Näiteks kaaluge L- st saadud üldistatud kvantifikaatori keelt L (Q ₀), lisades uue kvantifikaatori sümboli Q ₀ ja tõlgendades Q ₀ x φ (x), kuna neid on lõpmata palju x, nii et φ (x). On hõlpsasti näha, et lausel Q ₀ x φ (x) on samad mudelid, mis L (ω ₁, ω) -tekstil

¬∨ _{n ∈ω} ∃ v ₀ … ∃ v _n ∀ x [φ (x) → (x = v ₀ ∨… ∨ x = v _n)].

Seega on L (Q ₀) looduslikus mõttes tõlgitav L-ks (ω ₁, ω). Veel üks keel, millesse selles tähenduses saab tõlkida L (ω ₁, ω), on nõrk teise astme keel, mis saadakse, lugedes monadiliste predikaatmuutujate loendatava komplekti L-le, mida tõlgendatakse seejärel vahemikuna kõigist indiviidide piiratud komplektidest.

Kasutada võib ka suvaliselt pikkade konjunktsioonide, disjunktsioonide ja (võimalusel) kvantifikatsioonidega keeli. Fikseeritud lõpmatu kardinali λ jaoks määratletakse keel L (∞, λ), määratledes selle valemi klassi vormi (∞, λ), mis moodustab hulga Vorm (κ, λ) kõigi κ λ suhtes.). Seega L (∞, λ) võimaldab meelevaldselt pikki konjunktsioone ja disjunktsioone selles mõttes, et kui Φ on vormi (∞, λ) suvaline alamhulk, siis on nii ∧Φ kui ka ∨Φ vormi (∞, λ) liikmed. Kuid L (∞, λ) tunnistab ainult kvantifitseerimist pikkusega <λ: kõigil selle valemitel on <λ vabu muutujaid. Keel L (∞, ∞) määratletakse omakorda, määrates selle valemi klassi vormi (∞, ∞), mis on klasside kõigi lõpmatute kardinalide λ liit. Vorm (∞, λ). Niisiis võimaldab L (∞, ∞) lisaks suvaliselt pikkadele konjunktsioonidele ja disjunktsioonidele ka suvaliselt pikki kvantifitseerimisi. Pange tähele, et vorm (∞, λ) ja vorm (∞, ∞) on õiged klassid Gödel-Bernaysi komplekti teooria tähenduses. L (∞, λ) ja L (∞, ∞) valemite rahulolu struktuuris võib määratleda L (κ, λ) vastava mõiste ilmse laiendamise abil.

2. Piiratud kvantifikaatori keeled

Oleme märkinud, et lõpmatu kvantifikaatori keeled, näiteks L (ω ₁, ω ₁), sarnanevad teise järgu keeltega, kuna need võimaldavad kvantifitseerida lõpmatu indiviidide komplekti kaudu. Fakt, et see pole piiratud kvantifikaatorkeeltes lubatud, viitab sellele, et need võivad olla teatud mõttes lähedasemad esimese astme kolleegidele, kui esmapilgul ilmneda võib. Me näeme, et see on tõepoolest nii, eriti L (ω ₁, ω) puhul.

Keel L (ω ₁, ω) on infinitaarsete keelte hulgas erilisel kohal, kuna sarnaselt esimese astme keeltele võimaldab see tõhusat deduktiivset aparaati. Tegelikult lisagem tavalistele esimese astme aksioomidele ja järeldusreeglitele uus aksioomiskeem

∧Φ → φ

mis tahes loendatava hulga ⊆ ⊆ vormi (ω ₁, ω) ja mis tahes φ ∈ Φ jaoks koos uue järelduse reegliga

φ 0, φ 1,…, φ n,…

∧ n ∈ω φ n

ja lubada, et mahaarvamised oleksid loendatava pikkusega. Selles mõttes mahaarvatavuse ing * kirjutamine on meil siis olemas

L (ω ₁, ω) - täielikkuse teoreem. Mis tahes σ ∈ Saadetud (ω ₁, ω) korral ⊨ σ ⇔ ⊢ * σ

Otsese järeldusena järeldame, et see deduktiivne seade on piisav, et teha mahaarvamised loenduslikest ruumikomplektidest L (ω ₁, ω). See tähendab, et märkimise ilmselge laiendamise korral on meil iga loendatava komplekti jaoks Δ ⊆ Saadetud (ω ₁, ω)

(2.1) Δ ⊨ σ ⇔ Δ⊢ * σ

Seda täielikkuse teoreemi saab tõestada, muutes tavalist Henkini täielikkuse tõendit esimese järgu loogika jaoks või kasutades Boole-algebralisi meetodeid. Sarnased argumendid, mida rakendatakse aksioomide ja järeldamisreeglite sobivate edasiste suurendamiste korral, annavad paljude teiste piiratud kvantitatiivsete keelte jaoks analoogsed täielikkuse teoreemid.

Kui lubatakse lihtsalt loendatava pikkuse deduktsioone, siis ei saa seadistada L (ω ₁, ω) deduktiivset aparaati, mis oleks piisav meelevaldsetest ruumikomplektidest tehtavate deduktsioonide jaoks, st mille jaoks (2.1) vastaks iga komplekti Δ ⊆ Saadetud (ω ₁, ω), sõltumata kardinaalsusest. See tuleneb lihtsast tähelepanekust, et on olemas esimese astme keel L ja loendamatu hulk L (ω ₁, ω) -sendeid such, nii et Γ-l pole mudelit, kuid igal loendataval alamhulgal Γ on. Selle nägemiseks olgu L aritmeetika keel, millele on lisatud ω ₁ uut konstantset sümbolit { c _ξ: ξ <ω ₁ }, ja olgu Γ L (ω ₁, ω) -tehete kogum {σ} ∪ { c_ξ ≠ c _η: ξ ≠ η}, kus σ on aritmeetika standardmudelit iseloomustav L (ω ₁, ω) -osavus. See näide näitab ka, et kompaktsuse teoreem ebaõnnestub L (ω ₁, ω) ja samamoodi ka kõigi L (κ, λ) korral, mille κ ≥ ₁.

Teine tulemus, mis kehtib esimese astme juhtumi korral, kuid ebaõnnestub L (κ, ω) korral, kui κ ≥ ₁ (ja ka L (ω ₁, ω ₁), ehkki seda on keerulisem tõestada), on eelnev normaalvorm. teoreem. Lause on prenex, kui kõik selle kvantifikaatorid esinevad ees; toome näite L (ω ₁, ω) -lause kohta, mis ei ole samaväärne prenexi lausetega. Olgu L esimese astme keel ilma ekstraloogiliste sümboliteta ja olgu σ L (ω ₁, ω) -osavus, mis iseloomustab lõplike komplektide klassi. Oletame, et σ olid konjunktsiooniga samaväärsed

∧ _{i ∈ I} σ _i

eelühendi L (ω ₁, ω) tundmuste σ _i. Siis on iga σ _i vormis

Q ₁ x ₁ … Q _n x _n φ _i (x ₁,…, x _n),

kus iga Q _k on ∀ või ∃ ja φ _i on (võib-olla infinitaarne) valemite koosseis või disjunktsioon kujul x _k = x _l või x _k ≠ x _l. Kuna iga σ _i on lause, on igas φ _i ainult lõplikult palju muutujaid ja on lihtne näha, et iga φ _i on siis samaväärne esimese astme valemiga. Seetõttu võib iga σ _i pidada esimese järgu lauseks. Kuna eeldatakse, et σ on samaväärne σ _i konjunktsiooniga, järeldub sellest, et σ ja hulga Δ = {σ _i: i ∈ I} on samad mudelid. Kuid ilmselgelt on σ ja seega ka Δ kõigi piiritletud kardinaalsuste mudelid; esimese astme lausete kompaktsuse teoreem tähendab nüüd, et Δ ja seega ka σ on lõpmatu mudel, mis on vastuolus σ määratlusega.

Pöördudes Löwenheim-Skolemi teoreemi juurde, leiame, et allapoole suunatud versioonil on piisavad üldistused L (ω ₁, ω) ja tõepoolest kõigi infinitaarsete keelte jaoks. Tegelikult saab suuresti samamoodi näidata nagu esimese järgu lausekomplektide puhul, et kui Δ ent Saadetud (ω ₁, ω) kardinaalsuse lõpmatu mudel on ≥ | Δ |, siis on sellel kardinaalsuse mudel suurem. ℵ ₀, | Δ |. Täpsemalt, igal L (ω ₁, ω) -oskusel, millel on lõpmatu mudel, on loendatav mudel.

Teisest küljest tõuseb Löwenheimi-Skolemi teoreem tavalisel kujul kõigi infinitaarsete keelte jaoks. Näiteks aritmeetika standardmudelit iseloomustaval L (ω ₁, ω) -sensendil on kardinaalsuse mudel ℵ _0, kuid muu kardinaalsuse mudeleid pole. Kuid nagu näeme, pole siin kõik kadunud.

Me defineerime keele L Hanfi arvu h (L) kõige vähem kardinaalse κ-ga, nii et kui L- lausel on kardinaalsuse mudel κ, on sellel suvaliselt suure kardinaalsuse mudelid. H (L) olemasolu on hõlpsasti kindlaks tehtud. Iga L- lause puhul σ, millel pole suvaliselt suure kardinaalsuse mudeleid, olgu κ (σ) kõige vähem kardinaalne κ, nii et σ ei oleks kardinaalsuse mudelit κ. Kui λ on kogu κ (σ) supremum, siis kui L lausel on kardinaalsuse mudel λ, on sellel meelevaldselt suure kardinaalsuse mudeleid.

Defineerige kardinalid μ (α) rekursiivselt

μ (0)	=	ℵ 0
μ (α + 1)	=	2 μ (α)
μ (λ)	=	∑ α <λ μ (α), piiriks λ.

Siis saab seda näidata

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

sarnaseid tulemusi ka muude piiratud kvantifikaatori keelte puhul. Lõpmatu kvantifikaatori keelte, näiteks L (ω ₁, ω ₁) Hanfi arvude väärtused on tundlikud suurte kardinalide olemasolu suhtes või mitte, kuid peavad igal juhul ületama L (ω ₁, ω) väärtusi.

Selle L tulemus, mis üldistab L (ω ₁, ω), kuid mitte ühegi teise infinitaarse keele kohta, on

Craigi interpolatsiooni teoreem: Kui σ, τ ∈ Saadetud (ω ₁, ω) on sellised, et ⊨ σ → τ, siis on θ ∈ Saadetud (ω ₁, ω) nii, et ⊨ σ → θ ja ⊨ θ → τ, ja kumbki log-s esinev ebaloogiline sümbol esineb nii σ kui ka τ.

Tõend on esimese astme kohtuasja mõistlik sirgjoonelisus.

Lõpuks mainime veel ühte tulemust, mis üldistab kenasti L (ω ₁, ω), kuid mitte ühtegi teist infinitaarset keelt. On hästi teada, et kui A on mis tahes piiritletud L-struktuur, millel on ainult lõplikult palju seoseid, on olemas L-lause σ, mis iseloomustab A-d kuni isomorfismi. L (ω ₁, ω) jaoks on meil järgmine üldistus, mida nimetatakse

Scotti isomorfismi teoreem. Kui A on loendatav L-struktuur, millel on vaid loendatavalt palju seoseid, siis on olemas L (ω ₁, ω) -tundlikkus, mille loendatavate mudelite klass langeb kokku A -ga isomorfse L-struktuuride klassiga.

Piirang loendatavatele struktuuridele on oluline, kuna loetavust ei saa üldiselt väljendada L (L ₁, ω) -tundlikkusega.

Keelt L (∞, ω) võib samuti lugeda lõpliku kvantitatiivkeelena. Selle keele suhtes struktuuride ekvivalentsuse kontseptsioonil on eriline tähendus: nimetame kahte (sarnast) struktuuri A ja B (∞, ω) - ekvivalentseks, kirjutatud A ≡ _∞ω B, kui L (∞, ω) hoidke nii A- kui ka B- positsioonis. Seda seost saab kõigepealt iseloomustada osalise isomorfismi mõistega. Osaline isomorfism punktide A ja B vahel on kaartide mittepüsiv perekond P nii, et:

• Iga p ∈ P korral on dom (p) A alamstruktuur, ran (p) on B alamstruktuur ja p on selle domeeni isomorfism selle vahemikus; ja
• Kui p ∈ P, a ∈ A, b ∈ B, siis on olemas r, s ∈ P, mis mõlemad sirutuvad p-ga nii, et ∈ dom (r), b ∈ kulgeksid (s) („edasi-tagasi” omadus).

Kui osalise isomorphism vahel ja B, me ütleme, et ja B on osaliselt isomorfsed ja kirjutada ≅ _p B. Siis meil on

Karpi osalise isomorfismi teoreem.

Kõigi sarnaste struktuuride A, B, A ≡ _∞ω B ⇔ A ≅ _p B korral.

Samuti on olemas Scotti isomorfismi teoreemi versioon L (∞, ω) jaoks, nimelt

(2.2) Arvestades mis tahes struktuuri A, on L (∞, ω) -tund σ selline, et kõigi struktuuride B korral on A ≅ _p B ⇔ B ⊨ σ.

Osaline isomorfism ja (∞, ω) -ekvivalentsus on seotud Boolei isomorfismi mõistega. Selle määratlemiseks peame tutvustama tõeväärtusega väärtuste mudeli ideed. Täieliku Boole algebra B korral saadakse B-väärtusega komplektide universum V ^(B), mida tuntakse ka kui komplektide universumi V B-pikendus, kõigepealt, rekursiivselt a-ga,

V _α ^(B) = {x: x on funktsioon ∧ vahemik (x) ⊆ B ∧ ∃ξ <α [domeen (x) ⊆ V _ξ ^(B)]}

ja seejärel seadistamine

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

V ^(B) liikmeid nimetatakse B-väärtusega komplektideks. Nüüd on hõlpsasti näha, et B-väärtusega komplekt on täpselt B-väärtusega funktsioon koos domeeniga B-väärtusega komplektide komplektiga. Nüüd olgu L seatud teooria esimese astme keel ja olgu L ^(B) keel, mis saadakse, lisades L- le iga V ^(B) elemendi nime (me kasutame sama sümbolit elemendi ja selle nime puhul). Nüüd saab konstrueerida keele L ^(B) (lausete) lausete [·] ^(B) B-le: iga lause σ kohta L ^(B) on elemendi ^B elemendiks [σ] ^(B) „ Tõeväärtuse tõeväärtus σ (V ⁾. See kaardistus [·] ^(B) on määratletud nii, et kõik Zermelo-Fraenkeli komplekti teooria teoreemid saadetakse B ülaosale 1, st “tõele”; vastavalt sellele võib V ^(B) pidada Boole'i väärtustatud mudeliteooria mudeliks. Üldiselt, kui [σ] ^(B) = 1, ütleme, et σ kehtib V ^(B) ja kirjutame V ^(B) ⊨ σ.

Nüüd on igal x ∈ V kanooniline esindaja x väärtuses V ^(B), mis vastab

x = y, kui V ^(B) ⊨ x = y

x ∈ y, kui V ^(B) ⊨ x ∈ y

Me ütleme, et kaks sarnast struktuuri A, B on Boolean isomorfsed, kirjutatud A ≅ _b B, kui mõne täieliku Boole algebra B korral on meil V ^(B) ⊨ A ≅ B, see tähendab, et kui komplektide universum, milles A ja B kanoonilised esindajad on isomorfsed Boole-väärtusega 1. Seejärel saab näidata, et:

(2.3) ≡ _∞ω B ⇔ ≅ _b B.

Seda tulemust saab tugevdada kategooriateoreetilise sõnastuse kaudu. Selleks vajame (n) (elementaarse) topos kontseptsiooni. Tutvustada seda mõistet, hakkame koos familiary kategooria Set komplekti ja kaardistamisel. Komplektil on järgmised peamised omadused:

1. On olemas terminali objekt 1, nii et iga objekti X jaoks on ainulaadne kaart X → 1 (ühe jaoks võime võtta mis tahes üheelemendilise komplekti, eriti {0}).
2. Mis tahes objektide paaril X, Y on Descartes'i toode X × Y.
3. suvalise objektide paari jaoks saab kõigi kaartide X → Y abil moodustada eksponentsiaalse objekti Y ^X.
4. On olemas „tõeväärtuse” objekt Ω, nii et iga objekti X jaoks on loomulik vastavus X alamobjektide (alamhulkade) ja kaartide X → between vahel. (Ω jaoks võime võtta komplekti 2 = {0,1}; kaardid X → Ω on siis X-i iseloomulikud funktsioonid.)

Kõiki neid nelja tingimust saab sõnastada kategooriateoreetilises keeles - neid rahuldavat kategooriat nimetatakse topoks. Kategooria Komplekt on topos; nii on ka (i) kategooriate hulgaga ^(B) Boolean-väärtusega komplektide ja vastete komplektide mis tahes Boole-pikendusega V ^(B); ii) topoloogilises ruumis asuvate komplektide kääride kategooria; iii) komplektide kaartide kõigi diagrammide kategooria

X ₀ → X ₁ → X ₂ →…

Kõigi nende kategooriate objekte võib käsitada komplektidena, mis mingil viisil varieeruvad: juhul (i) üle Boolean algebra; ii) juhul topoloogilise ruumi kohal; juhul (iii) üle (diskreetse) aja. Seejärel võib topos olla ette nähtud muutuvate komplektide universumina. Tuttav kategoorias Set on eriline piirata puhul topos, kus "variatsioon" objektid on vähendatud nullini.

Nii nagu seatud teoorias, saab tõelise väärtusega objektil loogilisi operaatoreid määratleda ükskõik millises topos. Need on kaardid ¬: Ω → Ω; ∧, ∨, ⇒: Ω × Ω → Ω, mis vastavad eituse, konjunktsiooni, disjunktsiooni ja implikatsiooni loogilistele toimingutele. Nende toimingutega saab Ω Heytingi algebraks, kehastades seega üldiselt mitte klassikalise, vaid intutionistliku loogika seadusi. Selles mõttes intuitionistlik loogika on internaliseeritud topos: intuitionistic loogika on muutujate loogika. (Muidugi, klassikaline loogika on sisestatud teatavatesse eesmärkidesse, näiteks Set ja Set ^(B) mis tahes täieliku Boole algebra B korral.)

Mis tahes topo võib ette kujutada kui võimalikku “diskursuse universumit”, milles saab tõlgendada matemaatilisi väiteid ja teostada matemaatilisi konstruktsioone. Matemaatilised väited muudetakse tõlgendatavaks topos E-s avalduse kaudu E-keeles - keeleteooria tavalise keeleteooria versioon. Boole'i väärtustatud analoogiaga analoogsel viisil on võimalik sisestada selle sisekeele lause σ sobiv kehtivuse mõiste E-s. Kirjutame jällegi E ⊨ σ sõnale “σ kehtib E”.

Topos E öeldakse olevat täielikult, kui igasuguse set I, I kordne Copower ^[3] ∐ _I 1 selle l~oppobjekt eksisteerib E. ∐ _I 1 võib vaadelda kui kanooniline tüüpiline E komplekti Mina; vastavalt kirjutame selle lihtsalt nagu mina. (Punktis V ^(B) langeb see kokku eespool määratletud punktiga I.) Kõik ülalnimetatud eesmärgid on täis.

Nüüd olgu E täielik topos. Kui A = (A, R,…) on struktuur, kirjutage A (A, R,…) jaoks. Kahte struktuuri A ja B peetakse topos isomorfseks, kirjutades A ≅ _t B, kui mõne komplekti kategooria jaoks määratletud topos E korral on meil E ⊨ A ≅ B. Teisisõnu on kaks struktuuri topos isomorfsed, kui nende kanoonilised esindajad on mõne topos sisekeeles isomorfsed. Seejärel saab seda näidata

(2.4) ≡ _∞ω B ⇔ ≅ _t B.

Sellest lähtuvalt võib (ω, ω) ekvivalentsust pidada isomorfismiks muutuvate komplektide universumite äärmiselt üldises kontekstis. Selles suhtes on (∞, ω) ekvivalentsus isomorfismi “muutumatu” mõiste.

3. Kompaktsusomadused

Nagu nägime, ebaõnnestub kompaktsuse teoreem tavalisel kujul kõigi infinitaarsete keelte puhul. Sellegipoolest on huvitav kindlaks teha, kas infinitaarsed keeled vastavad teoreemi mõnele sobivalt muudetud versioonile. Sellel niinimetatud kompaktsusprobleemil on loomulik seos puhtalt setteoreetiliste küsimustega, mis hõlmavad „suuri” kardinalinumbreid.

Me konstrueerime järgmise määratluse. Olgu κ lõpmatu kardinal. Keelt L peetakse κ-kompaktseks (ehk nõrgalt κ-kompaktseks), kui alati Δ on L- tundmuste kogum (vastavalt L- kardinaalsuse tundmuste komplekt ≤ κ) ja kardinaalsuse Δ iga alamhulk < κ-l on mudel, nii nagu ka Δ-l. Pange tähele, et tavaline kompaktsuse teoreem L jaoks on täpselt väide, et L on kompaktsed. Üks põhjus, miks κ-kompaktsuse omadus on oluline, on järgmine. Kõne L κ- lõppenud (resp. Nõrgalt κ- complete) kui on olemas deduktiivse süsteemi P jaoks L mahaarvamise pikkuse <κ selliselt, et kui Δ on P -consistent ^[4] kogum L- laused (vastavalt sellised, et | Δ | ≤ κ), siis Δ on mudel. Pange tähele, et selline P on piisav mahaarvamiseks suvalistest ruumikomplektidest (kardinaalsus ≤ κ) §2 tähenduses. On hõlpsasti näha, et kui L on κ-täielik või nõrgalt κ-täielik, siis L on κ-kompaktne või nõrgalt κ-kompaktne. Seega, kui suudame näidata, et antud keel ei ole (nõrgalt) κ-kompaktne, siis ei saa selle jaoks olla deduktiivset süsteemi, mille pikkuse deduktsioonid <κ on piisavad meelevaldsete ruumikomplektide (kardinaalsuse ≤ κ) deduktsioonide jaoks.

Tegelikult selgub, et enamik keeli L (κ, λ) ei pruugi olla isegi nõrgalt κ-kompaktsed ja nende jaoks peab κ olema erakordselt suur kardinal. Vajame mõnda määratlust.

Väidetavalt on lõpmatu kardinal κ nõrgalt ligipääsmatu, kui

(a) λ <κ → λ ⁺ <κ (kus λ ⁺ tähistab λ kardinaalset järeltulijat) ja

(b) | I | <κ ja λ _i <κ (kõigi i ∈ I korral) ⇒ ∑ _{i ∈ I} λ _i <κ.

Kui lisaks

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

siis öeldakse, et κ on (tugevalt) ligipääsmatu. Kuna ℵ ₀ on ligipääsmatu, on tavapärane tava piirduda tähelepanu kättesaamatute või nõrgalt juurdepääsematute kardinalidega, mille väärtus ületab ℵ ₀. Sellest lähtuvalt loetakse juurdepääsetamatud või nõrgalt juurdepääsetavad kardinalid alati loendamatuks. On selge, et sellised kardinalid - kui neid on - peavad olema eriti suured; ja tõepoolest tähendab Gödeli mittetäielikkuse teoreem, et isegi nõrgalt ligipääsmatute kardinalide olemasolu pole tõestatud teooria tavaliste aksioomide põhjal.

Kutsugem kardinaalset κ kompaktset (või nõrgalt kompaktset), kui keel L (κ, κ) on κ-kompaktne (vastavalt nõrgalt κ-kompaktne). Siis on meil järgmised tulemused:

(3.1) ℵ ₀ on kompaktne. See on muidugi vaid lühike viis esimese astme keelte kompaktsuse teoreemi väljendamiseks.

(3.2) κ on nõrgalt kompaktne ⇒ L (κ, ω) on nõrgalt κ- kompaktne ⇒ κ on nõrgalt ligipääsmatu. Sellest lähtuvalt on järjepidev (seatud teooria tavaliste aksioomidega) eeldada, et ükski keel L (κ, ω), mille κ ≥ ₁ on nõrgalt κ-kompaktne või a fortiori nõrgalt κ-täielik.

(3.3) Oletame, et κ on ligipääsmatu. Siis on κ nõrgalt kompaktne ⇔ L (κ, ω) on nõrgalt kompaktne. Samuti on ka κ nõrgalt kompaktne ⇒ enne κ on komplekt κ juurdepääsematuid. Seega on nõrgalt kompaktne kättesaamatu kardinal eriti suur; eriti ei saa see olla esimene, teine,…, n.,… ligipääsmatu.

(3.4) κ on kompaktne ⇒ κ on ligipääsmatu. (Kuid vahetult ülaltoodud tulemuse põhjal vastupidine nurjub.)

Las Constr seisab Gödeli konstruktiivsuse aksioomi eest; tuletage meelde, et Constr vastab komplekti teooria tavalistele aksioomidele.

(3.5) Kui Constr peab paika, pole kompaktset kardinali.

(3.6) Oletame, et Constr ja κ on ligipääsmatu. Siis on κ nõrgalt kompaktne ⇔ L (ω ₁, ω) on nõrgalt κ- kompaktne kõigi L korral.

(3.7) Kui Constr peab paika, siis pole ühtegi kardinaali κ, mille korral L (ω ₁, ω) oleks kompaktne. Järelikult on komplekti teooria tavaliste aksioomidega kooskõlas oletus, et pole sellist kardinaalset κ, et kõik keeled L (ω ₁, ω) oleksid κ-täielikud. Sellele tulemusele tuleb vastandada asjaolu, et kõik esimese astme keeled on ω-täielikud.

Nende tulemuste impordiks on see, et kompaktsuse teoreem ebaõnnestub enamiku keelte L (κ, λ) korral κ ≥ ₁ väga halvasti.

Mõned ajaloolised märkused on siin korras. 1930. aastatel uurisid matemaatikud komplektide niinimetatud mõõtmisprobleemi erinevaid versioone, probleem, mis tekkis seoses Lebesgue'i mõõtmise teooriaga pidevuses. Täpsemalt sõnastati järgmine väga lihtne meetme mõiste. Kui X on komplekt, on X (kahekordselt arvestatav mittetriviaalne) mõõdik kaardil μ toitekomplekti P X abil komplektile {0, 1}, mis vastab:

(a) μ (X) = 1, (b) μ ({x}) = μ (∅) = 0 kõigi x ∈ X korral ja

c) kui A on mis tahes X üksteisest lahutatud alamhulkade loetav perekond, siis μ (∪ A) = ∑ {μ (Y): Y ∈ A }.

Ilmselt sõltub see, kas antud komplekt sellist mõõdet toetab, ainult selle kardinaalsusest, seetõttu on loomulik määratleda kardinaalne κ, et see oleks mõõdetav, kui kõik kardinaalsuse komplektid κ toetavad sedalaadi mõõdet. Kiiresti saadi aru, et mõõdetav kardinal peab olema ligipääsmatu, kuid vastupidise võltsus tuvastati alles 1960. aastatel, kui Tarski näitas, et mõõdetavad kardinalid on nõrgalt kompaktsed ja tema õpilane Hanf näitas, et esimene, teine jne pole ligipääsmatuid nõrgalt. kompaktne (vrd (3.3)). Ehkki järeldus, et mõõdetavad kardinalid peavad olema tohutult suured, on nüüd tõestatud, ilma ümbersõitu tegemata nõrga kompaktsuse ja infinitaarsete keelte kaudu, on fakt, et neid ideid kasutati tulemuse kindlakstegemiseks esiteks.

4. Lõpmatute ja kvantitatiivsete keelte puudulikkus

Esimese astme keelte osas on tõenäoliselt kõige olulisem tulemus Gödeli täielikkuse teoreem, mis muidugi ütleb, et mis tahes esimese astme keele L kehtivate valemite komplekti saab genereerida lihtsa aksioomide komplekti abil mõne sirgjoonelise reegli abil. järeldused. Selle teoreemi peamine tagajärg on see, et kui L valemeid kodeeritakse mingil konstruktiivsel viisil naturaalarvudena, siis on kehtivate lausete (koodide) komplekt rekursiivselt loendatav. Esimese astme keele täielikkus tähendab seega, et selle kehtivate lausete komplekt on määratletav eriti lihtsal viisil. Seetõttu tundub suvalise keele L korral mõistlik see tähendus ümber pöörata ja soovitada, et kui kehtiva L- laused pole mõnel lihtsal moel määratletavad, siis ei saa L-le sisulist täielikkuse tulemust kindlaks teha või, nagu ütleme, et L on puudulik. Selles jaotises kasutame seda soovitust visandina, mis tõestab, et “kõige” lõpmatu kvantifikaatori keeled on selles mõttes puudulikud.

Esmalt tutvustame määratletavuse ametlikku mõistet järgmiselt. Kui L on keel, L sambastruktuurist ja X alamhulk domeeni A ütleme, et X on piiritletav valemi järgi φ (x, y ₁, …, y _n) on L, kui seal on järjestuskontrolli ₁, …, et _n elementide A nii, et x on osa kõigist elementidest x ∈ A mis φ (x, et ₁, …, et _n) omab.

Kirjutage Val (L) kõigi kehtivate L- tundmuste komplektile, st nendele, mida hoitakse igas L- struktuuris. Lausele „Val (L) on määratletav” tähenduse omistamiseks peame täpsustama

1. struktuur C (L) - kodeeriv struktuur L jaoks;
2. konkreetne üks kaart - kodeeriv kaart L valemi komplektist C (L) domeeniks.

Siis, kui tuvastame Val (L) selle kujutisega C (L) -ga kodeerimiskaardil, tõlgendame lauset „Val (L) on määratletav” kui lauset „Val (L), mida peetakse domeeni C (L), on piiritletav C (L), mille valem L."

Näiteks kui L on aritmeetika esimese astme keel L, siis kasutas Gödel algselt kodeerimisstruktuurina aritmeetika standard standardmudelit ja kodeerimise kaardina tuntud funktsiooni, mis saadi naturaalarvude algfaktoriseerimisteoreemist. Val (L) rekursiivne loendamine tähendab siis lihtsalt seda, et Val (L) liikmete koodide komplekt (“Gödeli numbrid”) on in-s defineeritav L-valemiga kujul ∃ y φ (x, y), kus φ (x, y) on rekursiivne valem.

Teine, samaväärne, aritmeetika esimese astme keele kodeerimisstruktuur on pärilikult piiratud komplektide struktuur ^[5] ⟨H (ω), ∈ ⨡ H (ω)⟩, kus komplekt x on pärilikult piiratud, kui x, siis selle liikmed, selle liikmete liikmed jne on kõik piiratud. Selles kodeerimisstruktuuris võetakse arvesse asjaolu, et esimese järgu valemeid peetakse loomulikult piiratud hulgaks.

Tulles nüüd juhtumi juurde, kus L on infinitaarne keel L (κ, λ), milline oleks sel juhul sobiv kodeerimisstruktuur? Märkisime alguses, et infinitaarsetele keeltele pakkus võimalust mõelda valemid kui kogumiteoreetilised objektid, nii et proovime saada oma kodeerimisstruktuuri, mõeldes sellele, millised komplekti teoreetilised objektid peaksime infinitaarsete valemite jaoks olema. Arvestades asjaolu, et iga φ∈ vormi (κ, λ) korral on φ ja selle alamvormid, alamvormid jne kõik <κ, ^[6]hetke peegeldus näitab, et L (κ, λ) valemid „vastavad” x-i pärilikult kardinaalsuse kogumitele <κ selles mõttes, et x, selle liikmed, selle liikmed jne on kõik kardinaalsus <κ. Kõigi selliste komplektide kogumik on kirjutatud H (κ). H (ω) on ülaltoodud pärilikult piiratud komplektide kogum ja H (ω ₁) kõigi pärilikult loendatavate komplektide kogum.

Oletagem lihtsuse huvides, et baaskeele L ainus ekstraloogiline sümbol on binaarne predikatsioonisümbol ∈ (arutelu on hõlpsasti laiendatav juhtumile, kus L sisaldab täiendavaid ekstraloogilisi sümboleid). Ülaltoodud märkustest lähtudes võtame L (κ, λ) kodeerimisstruktuurina struktuuri,

H (κ) = _df = H (κ), ∈ ⨡ H (κ)⟩.

Nüüd saame määratleda vormi (κ, λ) kodeerimiskaardi H (κ) -ks. Esiteks määrame igale L (κ, λ) põhisümbolile ^{koodiobjekti ⌈} s ^⌉ H (κ) järgmiselt. Olgu {v _ξ: ξ <κ} L üksikute muutujate loend (κ, λ).

Sümbol	Koodiobjekt	Märge
¬	1	⌈ ¬ ⌉
∧	2	⌈ ∧ ⌉
∧	3	⌈ ∧ ⌉
∃	4	⌈ ∃ ⌉
∈	5	⌈ ∈ ⌉
=	6	⌈ = ⌉
v ξ	0, ξ⟩	⌈ v ξ ⌉

Seejärel määrame igale φ ∈ vormile (κ, λ) ^{koodiobjekti ⌈} φ ^⌉ rekursiivselt järgmiselt:

^⌈ v _ξ = v _{r |} ^⌉ = _df ⟨ ^⌈ v _ξ ^⌉, ^⌈ = ^⌉, ^⌈ v _{r |} ^⌉ ⟩, ^⌈ v _š- ∈ v _{r |} ^⌉ = _df ⟨ ^⌈ v _š- ^⌉, ^⌈ ∈ ^⌉, ^⌈ v _{r |} ^⌉ ⟩;

jaoks φ, ψ ∈ vorm (κ, λ),

^⌈ ep ∧ Rv ^⌉ = _df ⟨ ^⌈ ep ^⌉, ^⌈ ∧ ^⌉, ^⌈ Rv ^⌉ ⟩

^⌈ ¬φ ^⌉ = _df ⟨ ^⌈ Ž ^⌉, ^⌈ ep ^⌉ ⟩

^⌈ ∃ X ep ^⌉ = _df ⟨ ^⌈ ∃ ^⌉, { ^⌈ x ^⌉: x ∈ X}, ^⌈ ep ^⌉ ⟩;

ja lõpuks, kui Φ ⊆ vorm (κ, λ) koos | Φ | <κ,

^⌈ ∧Φ ^⌉ = _df ⟨ ^⌈ ∧ ^⌉, { ^⌈ ep ^⌉: φ ∈ Φ}⟩.

Kaardil ep ↦ ^⌈ ep ^⌉ alates vorm (κ, λ) viiakse H (κ) on kergesti näha, et 1-1 ja on nõutud kodeeriv kaardil. Sellest lähtuvalt lepime kokku, et identifitseerime Val (L (κ, λ)) selle kujutisega H (κ) selle kodeerimiskaardi all.

Millal on Val (L (κ, λ)) H (κ) määratletav alamhulk? Sellele küsimusele vastamiseks vajame järgmisi määratlusi.

L-valemiga nimetatakse Δ ₀ - valemiga kui see on samaväärne valemiga, milles kõik kvantorid on kujul ∀ x ∈ y või ∃ x ∈ y (st ∀ x (x ∈ y → …) või ∃ x (x ∈ y ∧…)). L-valem on Σ ₁ - valem, kui see on samaväärne valemiga, mille saab üles ehitada aatomvalemite ja nende negatiivide põhjal, kasutades ainult loogilisi operaatoreid ∧, ∨, ∀ x ∈ y, ∃ x. Komplekti A alamhulk X on A väärtuseks Δ ₀ (vastavalt Σ ₁), kui see on struktuuris ⟨A, ∈ ⨡ A inable defineeritav L väärtuse Δ ₀ - (vastavalt Σ ₁ -) valemi abil..

Näiteks kui tuvastame naturaalarvude hulga pärilikult piiratud komplektide hulga H (ω) abil tavalisel viisil, siis on meil iga X ⊆ H (ω) jaoks:

X on H (ω) ₀ Δ X on rekursiivne

X on H ₁ H (ω) ⇔ X on rekursiivselt loendatav.

Seega võib Δ ₀ - ja and _1- järgu mõisteid pidada vastavalt rekursiivse ja rekursiivselt loendatava kogumi mõistete üldistusteks.

L täielikkuse teoreem tähendab, et Val (L) - mida peetakse H (ω) alamhulgaks - on rekursiivselt loendatav ja seega and ₁ H (ω) kohta. Samamoodi täielikuks teoreem L (ω ₁, ω) (vt §2) tähendab, et Val (L (ω ₁, ω)) - pidada alagrupis H (ω ₁) - on Σ ₁ aasta H (ω ₁). See meeldiv olukord laguneb aga täielikult, niipea kui L (ω ₁, ω ₁) on saavutatud. Sest üks saab tõestada

Scotti L- i määramatuse teoreem (ω ₁, ω ₁). Val (L (ω ₁, ω ₁)) ei ole H (ω ₁) korral määratav isegi L (ω ₁, ω ₁) - valemi abil; seega a fortiori Val (L (ω ₁, ω ₁)) ei ole H (ω ₁) Σ ₁.

Seda teoreemi tõestatakse sarnaselt üldtuntud tulemusega, et aritmeetika L ² teise astme keele kehtivate lausete (koodide) komplekt ei ole selle kodeerivas struktuuris määratav teise järguga. Et saada seda Viimane tulemus, üks märgib kõigepealt, et ℕ iseloomustab ühe L ² -sentence ja seejärel näitab, et kui tulemus oli vale, siis "tõde ℕ" L ² -sentences oleks määratlematu L ² - valem, rikkudes sellega Tarski tõe määratlematuse teoreemi.

Sellest tulenevalt peab Scotti ülalmääratlematuse teoreemi tõestamiseks kindlaks tegema:

(4.1) Kodeerimisstruktuuri H (ω ₁) iseloomustus L-s (ω ₁, ω ₁): on olemas L (ω ₁, ω ₁) -tund _0, nii et kõigi L-struktuuride A, A ⊨ jaoks τ ₀ ⇔ A ≅ H (ω ₁).

(4.2) L (ω ₁, ω ₁) tõe määratlematus - laused kodeerimisstruktuuris: puudub L (ω ₁, ω ₁) -valem φ (v ₀), nii et kõigi L (ω ₁, ω ₁) -sentences σ, H (ω ₁) ⊨ σ↔φ (^⌈ σ ^⌉).

(4.3) L (ω ₁, ω ₁) puhul on olemas termin t (v ₀, v ₁), nii et iga lausepaari σ korral on L (ω ₁, ω ₁), H (ω ₁) τ ⊨ [t (^⌈ σ ^⌉, ^⌈ τ ^⌉) = ^⌈ σ → τ ^⌉].

(4.1) on tõestatud H (ω ₁) setteoreetilise definitsiooni analüüsimisega ja näidates, et selle saab „sisemiselt” formuleerida L (ω ₁, ω ₁). (4.2) kehtestatakse sarnaselt Tarski teoreemiga tõe määratlematuse kohta esimese või teise järgu keeltes. (4.3) saadakse vormistamise määratlusest kodeeriv kaardilt σ ↦ ^⌈ σ ^⌉ L (ω ₁, co ₁).

Nende faktidega relvastatud viisil saame Šoti määratlematuse teoreemi järgmisel viisil. Oletame, et see oli vale; siis oleks olemas L (ω ₁, ω ₁) -valem θ (v ₀), nii et kõigi L (ω ₁, ω ₁) -tundide σ,

(4.4) H (ω ₁) ⊨ θ (^⌈ σ ^⌉) iff σ ∈ Val (L (ω ₁, ω ₁)).

Olgu τ ₀ punktis 4.1 esitatud lause. Siis on meil kõigi L (ω ₁, ω ₁) tunnuste σ,

H (ω ₁) ⊨ σ iff (τ ₀ → σ) ∈ Val (L (ω ₁, ω ₁)),

nii et (4.4) abil

H (ω ₁) ⊨ σ iff H (ω ₁) ⊨ θ (^⌈ τ ₀ → σ ^⌉).

Kui t on punktis 4.3 esitatud mõiste, siis järgneb see

H (ω ₁) ⊨ σ↔θ (t (^⌈ τ ₀ ^⌉, ^⌈ σ ^⌉)).

Nüüd kirjutada φ (v ₀), L (ω ₁, ω ₁) -formula θ (t (^⌈ t ₀ ^⌉, ^⌈ σ ^⌉)). Siis

H (ω ₁) ⊨ σ↔φ (^⌈ σ ^⌉),

vastandamine (4.2) ja tõendi vormistamine.

Seega pole Val (L (ω ₁, ω ₁)) defineeritav isegi L (ω ₁, ω ₁) - valemi abil, seega on fortiori L (ω ₁, ω ₁) puudulik. Sarnased argumendid näitavad, et Scotti määratlematuse teoreem püsib endiselt siis, kui ω ₁ asendatakse mõne järgneva kardinaliga κ ⁺; vastavalt on keeled L (κ ⁺, κ ⁺) kõik puudulikud. ^[7]

5. L (ω ₁, ω) alamkeeled ja Barwise kompaktsuse teoreem

Arvestades seda, mida me nüüd infinitaarsete keelte kohta teame, näib, et L (ω ₁, ω) on ainus, kes käitub mõistlikult. Teisest küljest on kompaktsuse teoreemi suutmatus üldistada L (ω ₁, ω) mingil kasulikul viisil rakenduste osas tõsiseks puuduseks. Proovime seda tõrget üksikasjalikumalt analüüsida.

Tuletage paragrahvist 4 meelde, et võime kodeerida esimese astme keele valemid pärilikult piiratud hulgana, st H (ω) liikmetena. Sel juhul on iga L-lause lause (koodide) piiratud komplekt ka H (ω) liige ja sellest järeldub, et kompaktsuse teoreemi L jaoks saab esitada kujul:

(5.1) Kui Δ ⊆ Saadetud (L) on selline, et igal alamhulgal Δ ₀ ⊆ Δ, Δ ₀ ∈ H (ω) on mudel, siis ka Δ.

Nüüd on hästi teada, et (5.1) on L üldise terviklikkuse teoreemi otsene tagajärg, mis (5.1) sarnase vormi kohaselt saab väiteks:

(5.2) Kui Δ ⊆ Saadetud (L) ja σ ∈ Saadetud (L) vastavad Δ ⊨ σ, siis arvutatakse Δ Δ-st selline lahutus D, et D ∈ H (ω). ^[8]

Lõikes 2 märkisime, et kompaktsuse teoreem L (ω ₁, ω) ebaõnnestub; tegelikult konstrueerisime komplekti Γ ⊆ Saadetud (ω ₁, ω) selliselt, et

(5.3) Igal loendataval alamhulgal Γ on mudel, kuid Γ mitte.

Samuti tuletage meelde, et juurutasime mahaarvamise mõiste L-ga (ω ₁, ω); kuna sellised mahaarvamised on loendatava pikkusega, järeldub punktist 5.3 kiiresti, et

(5.4) On lause ^[9] σ ∈ Saadetud (ω ₁, ω) selliselt, et Γ ⊨ σ, kuid σ väärtust L ((₁, ω) no-st ei lahutata.

Nüüd saab L (ω ₁, ω) valemeid kodeerida H (ω ₁) liikmeteks ja on selge, et H (ω ₁) on loendatavate alamhulkade ja järjestuste moodustamisel suletud. Seetõttu võib punktid 5.3 ja 5.4 kirjutada:

(5,3 bis) Igal Γ ₀ ⊆ Γ sellisel kujul, et Γ ₀ ∈ H (ω ₁) omaks mudelit, kuid Γ mitte;

(5.4 bis) On lause σ ∈ Saadetud (ω ₁, ω) selline, et Γ ⊨ σ, kuid σ väärtusest Γ ei lahuta D ∈ H (ω ₁).

Sellest järeldub, et (5.1) ja (5.2) ebaõnnestuvad, kui “L” asendatakse sõnadega “L (ω ₁, ω)” ja “H (ω)” sõnadega “H (ω ₁)”. Lisaks saab näidata, et punktides 5.3 (5.3) ja (5.4 bis) esitatud hulga Γ ⊆ Saadetud (ω ₁, ω) väärtuseks H võib olla Σ ₁ (ω ₁). Seega ebaõnnestuvad kompaktsuse ja üldistatud terviklikkuse teoreemid isegi L (ω ₁, ω) -tundlikkuse Σ _1- seti korral.

Näeme (5.4 bis) põhjal, et üldistatud terviklikkuse teoreemi nurjumine Σ _1- seti korral L (ω ₁, ω) on see, et laias laastus ei ole H (ω ₁) „suletud” deduktsioonide moodustamisel. Σ ₁ -st lausekomplektist H-s (ω ₁). Nii et selle parandamiseks näib loomulik asendada H (ω ₁) komplektidega A, mis on mingis mõttes suletud selliste deduktsioonide moodustamise teel, ja seejärel kaaluda ainult neid valemeid, mille koodid asuvad tähes A.

Nüüd anname visandi, kuidas seda teha.

Esiteks tuvastame L (ω ₁, ω) sümbolid ja valemid nende koodidega H (ω ₁), nagu paragrahvis 4. Iga loendatava transitiivse ^[10] komplekti A korral laske

L _A = vorm (L (ω ₁, ω)) ∩ A.

Me ütleme, et L _A on L (ω ₁, ω) alamkeel, kui järgmised tingimused on täidetud:

1. L ⊆ L _A
2. kui φ, ψ ∈ L _A, siis φ ∧ ψ ∈ L _A ja ¬φ ∈ L _A
3. kui φ ∈ L _A ja x ∈ A, siis ∃ x φ ∈ L _A
4. kui φ (x) ∈ L _A ja y ∈ A, siis φ (y) ∈ L _A
5. kui φ ∈ L _A, on kõik every alamvormid L _A-s
6. kui Φ ⊆ L ja Φ ∈ A, siis ∧Φ ∈ L.

Mahaarvamise mõiste (L _A) on määratletud tavapärasel viisil; kui Δ on lausete L _A ja φ ∈ L _A lausekomplekt, siis _A lahutamine Δ-st L _A-s on φ lahutamine Δ-st L (ω ₁, ω), mille iga valem on L _A-s. Me ütleme, et φ on lahutatav Δ-st L _A-s, kui leidub lahutus D of Δ-st L _A-s; nendel tingimustel kirjutame Δ ⊢ _A φ. Üldiselt D ei kuulu A-sse; tagamaks, et selline mahaarvamine leitakse A-st, tuleb A-le kehtestada täiendavad tingimused.

Olgu A loendatav transitiivsete kogum, nii et L _A on L (ω ₁, ω) alamkeel ja olgu, et Δ oleks L _A lausekomplekt. Me ütleme, et A (või terminit kuritarvitades L _A) on Δ- suletud, kui L _A mis tahes valemi φ korral, milleks on Δ ⊢ _{A is}, on Δ lahutatud D such-st, nii et D ∈ A. Võib näidata, et ainus loendatav keel, mis on suvalise Δ korral suletud Δ, on esimese astme keel L, st kui A = H (ω). J. Barwise avastas siiski, et leidub loendatavaid komplekte A ⊆ H (ω ₁), mille vastavad keeled L _A erinevad L-st ja on Δ-suletud kõigi Σ _{1 korral}- lausekomplektid Δ. Selliseid komplekte A nimetatakse lubatud komplektideks; laias laastus on need pärilikult piiratud komplektide laiendid, milles rekursiooniteooria ja seega ka tõestusteooria on endiselt võimalikud (täieliku määratluse leiate allpool punktist 5.1).

Barwise'i tulemusest saab kohe

Barwise kompaktsuse teoreem. Olgu A loendatav lubatav kogum ja Δ olgu L _A lausekomplekt, mis on Σ _{1 A- l}. Kui igal Δ '⊆ Δ on nii, et Δ' ∈ A-l on mudel, siis ka Δ.

„Σ ₁” esinemine siin näitab, et see teoreem on rekursiivselt loendatavate lausekomplektide kompaktsusteoreemi üldistus.

Teine Barwise kompaktsuse teoreemi versioon, mis on kasulik komplektiteooria mudelite konstrueerimiseks, on järgmine. Olgu ZFC Zermelo-Fraenkeli komplekti teooria jaoks tavaline aksioomide komplekt, sealhulgas valitud aksioom. Siis on meil:

5.5 Teoreem. Olgu A loendatav transitiivne komplekt, nii et A = ⟨A, ∈ ⨡ A⟩ on ZFC mudel. Kui Δ on kogum lauset L mis on piiritletav mille valem keele Hulgateooria ja kui iga Δ "⊆ Δ nii, et Δ" ∈ A omab mudel, nii ei Δ.

Kokkuvõtteks anname selle teoreemi lihtsa rakenduse. Olgu A = ⟨A, ∈ ⨡ A⟩ ZFC mudel. Mudeli B = ⟨B, E⟩ of ZFC öeldakse olevat korraliku lõpu pikendamist if (i) ⊆ B, (ii) ≠ B, (iii) ∈ A, b ∈ B, BEA ⇒ b ∈ A. Seega on ZFC mudeli õige lõpplaiend õige laiend, milles ükski “uus” element ei astu ühegi “vana” elemendi ette. Nagu meie rakendus 5,5 tõestame

5.6 Teoreem. Igal loendataval ZFC transitiivsel mudelil on korralik lõpplaiend.

Tõestus. Olgu A = ⟨A, ∈ ⨡ A⟩ on ZFC transitiivne mudel ja L on komplektiteooria esimese astme keel, mida on täiendatud nimega a iga a ∈ A ja täiendava konstandi c korral. Olgu Δ L _A- tundmuste kogum, mis koosneb:

• ZFC kõik aksioomid;
• c ≠ a, iga a ∈ A kohta;
• ∀ x (x ∈ a → ∨ _{b ∈ a} x = b), iga a ∈ A jaoks;
• a ∈ b, iga a ∈ b ∈ A kohta.

On lihtne näidata, et Δ on A alamhulk, mis on A-s määratletav komplektteooria keele valemi abil. Samuti on igal alamhulgal Δ '⊆ Δ nii, et Δ' ∈ A-l on mudel. Kõigi a ∈ A hulga C jaoks, milles a esineb Δ ', kuulub A - kuna Δ' seda teeb - ja nii, kui tõlgendame c kui mõnda (tingimata mittevaba) komplekti A - C liiget, siis A on Δ 'mudel. Järelikult (5.5) tähendab, et A-l on mudel ⟨B, E⟩. Kui me tõlgendame iga konstantne kui element a ∈ A, siis ⟨B, E⟩ on õige lõpu pikendamise. Tõestus on täielik.

Lugeja näeb kiiresti, et esimese astme kompaktsuse teoreem seda tulemust ei anna.

5.1 Lubatava komplekti mõiste määratlus

Väike transitiivne komplekt A on lubatav, kui järgmised tingimused on täidetud:

1. kui a, b ∈ A, siis {a, b} ∈ A ja ∪ A ∈ A;
2. kui a ∈ A ja X ⊆ A on A juures ₀, siis X ∩ a ∈ A;
3. kui a ∈ A, X ⊆ A on A Δ ₀ ja ∀ x ∈ a ∃ y (<x, y> ∈ X), siis mõne b ∈ A korral ∀ x ∈ a ∃ y ∈ b (<x, y> ∈ X).

Tingimus ii - Δ ₀ - eraldusskeem - on Zermelo eraldamise aksioomi piiratud versioon. Tingimust iii - asendamise aksioomi sarnaselt nõrgestatud versiooni - võib nimetada Δ ₀ - asendusskeemiks.

On üsna lihtne näha, et kui A on transitiivne hulk, nii et <A, ∈ | A> on ZFC mudel, siis A on lubatud. Üldisemalt öeldes püsib tulemus ka siis, kui ZFC- st jäetakse välja võimendatud aksioom, nii et nii H (ω) kui ka H (ω ₁) on lubatavad. Kuna viimane on aga loendamatu, ei kehti Barwise kompaktsuse teooria selle suhtes.

6. Ajaloolised ja bibliograafilised märkused

§§ 1 ja 2. Lõpmatute ettepanekute ja predikaatide keeled näivad olevat oma esimese selgesõnalise ilmunud trükisena Scott ja Tarski [1958] ja Tarski [1958] ettekannetega. L (ω ₁, ω), aga ka teiste infinitaarsete keelte täielikkuse teoreemi tõestas Karp [1964]. Hanfi arvu arvutused L (ω ₁, ω) jaoks tehti esmakordselt Morley poolt [1965]. Korrektsete tellimuste määramatust lõplikes kvantitatiivkeeltes tõestasid Karp [1965] ja Lopez-Escobar [1966]. L (ω ₁, ω) interpoleerimise teoreemi tõestas Lopez-Escobar [1965] ja Scotti isomorfismi teoreem L (ω ₁, ω) jaoks Scott [1965].

Karpi osalise isomorfismi teoreemi tõestati esmakordselt Karpis [1965]; vt ka Barwise [1973]. Tulemus (2.2) ilmub Changis [1968], tulemus (2.3) Ellentuckis [1976] ja tulemus (2.4) Bellis [1981].

§ 3. Tulemused (3.2) ja (3.3) tulenevad Hanfist [1964], koos mõningate täpsustustega Lopez-Escobari [1966] ja Dickmanniga [1975], samas kui (3.4) tõestas Tarski. Tulemus (3.5) tuleneb Scottist [1961], (3.6) Bellile [1970] ja [1972]; ja (3.7) Bellile (1974). Mõõdetavaid kardinalid pidasid kõigepealt silmas Ulam [1930] ja Tarski [1939]. Seda, et mõõdetavad kardinalid on nõrgalt kompaktsed, märgiti Tarskis [1962].

§ 4. Mis puudutab L (ω ₁, unde ₁) määramatuse teoreemi. Carol Karpi märkused (1964, 166): “Stanfordi ülikoolis 1960. aastal toimunud loogika, metodoloogia ja teadusfilosoofia rahvusvahelisel kongressil edastas Dana Scott ülevaate dokumendist, mille kohaselt (γ +) pole täielik määratletav formaalne süsteem võimatu., γ +) keeled, millel on lisaks võrdõiguslikkuse sümbolile ka üks kahekohalise predikatsioonisümbol.” Scott ei avaldanud kunagi oma tulemust ja täiesti üksikasjalikud tõendid ilmusid esmakordselt Karpis [1964]. Siin kasutatud lähenemisviis teoreemile põhineb Dickmanni [1975] avaldusel.

§ 5. Selles osas esitatud tulemuste algne motivatsioon tuli Kreiselilt; oma [1965] juhtis ta tähelepanu sellele, et puuduvad kaalukad põhjused infinitaarsete valemite valimiseks üksnes pikkuse alusel, ja tegi selle asemel ettepaneku kasutada määratletavuse või sulgemise kriteeriume. Kreiseli ettepanekut võttis suure eduga vastu Barwise [1967], kus tõestati tema kompaktsuse teoreem. Lubatava komplekti mõiste tuleneb Platekist [1966]. Teoreem (5.6) on võetud Keislerist [1974].

Infinitaarsete keelte teema kohta lähemalt lugemiseks vt Aczel [1973], Dickmann [1975], Karp [1964], Keisler [1974] ja Makkai [1977]. Kasuliku ülevaate infinitaarsete keelte ja suurte kardinalide vahelisest seosest leiate Drake'i [1974] 10. peatükist.

Bibliograafia

• Aczel, P., 1973, “Infinitaarne loogika ja Barwise kompaktsuse teoreem”, 1971. aasta Bertrand Russelli mälestusloogikakonverentsi (Uldum, Taani) artiklid, J. Bell, J. Cole, G. Priest ja A. Slomson (toim).), Leeds: Bertrand Russelli mälestusloogikakonverents, 234–277.
• Barwise, J., 1967, Lõpmatu loogika ja lubatud komplektid. Ph. D. Lõputöö, Stanfordi ülikool.
• –––, 1973, “Tagasi ja edasi läbi lõpmatu loogika. Uuringud mudelateooriast”, matemaatikaõppes (8. köide), Buffalo: American Mathematical Association, lk 5–34.
• –––, 1975, Lubatud komplektid ja konstruktsioonid, Berliin: Springer-Verlag.
• Barwise, J. ja S. Feferman (toim.), 1985, Model-Theoretic Logics käsiraamat, New York: Springer-Verlag.
• Baumgartner, J., 1974, "The Hanf arvu komplektsete L _{ω 1, ω} lausete (ilma GCH)", Journal of Sümbolite Logic, 39: 575-578.
• Bell, JL, 1970, “Nõrk kompaktsus teise astme keeltes”, Poola Teaduste Akadeemia bülletään, 18: 111–114.
• --- 1972 "vahelist suhet Nõrk Tihedus L _{ω 1, ω}, L _{ω 1, ω 1 ja piiratud teist järku Keeled", Arhiiv Matemaatiline loogika, 15: 74-78.}
• –––, 1974, “Kompaktsed kardinalid”, Zeitschrift für Mathematical Logik und Grundlagen der Mathematik, 20: 389–393.
• –––, 1981, “Struktuuride isomorfism S-eesmärkides”, Journal of Symbolic Logic, 43 (3): 449–459.
• Chang, CC, 1968, “Mõned märkused lõpmatute keelte mudelteooria kohta”. aastal lõpulevivate keelte süntaksis ja semantikas (loengu märkused matemaatikas: köide 72.), J. Barwise (toim), Springer-Verlag, Berliin, 36-63.
• Dickmann, MA, 1975, suured sõjaväe keeled, Amsterdam: Põhja-Holland.
• Drake, FR, 1974, Set Theory: sissejuhatus suurtesse kardinalidesse, Amsterdam: Põhja-Hollandi kirjastus.
• Ellentuck, E., 1976, „Kategoorilisus taastatud”, Journal of Symbolic Logic, 41 (3): 639–643.
• Hanf, WP, 1964, Lõpmatute pikkade väljenditega keelte ebakompaktsus, Amsterdam: Põhja-Holland.
• Karp, C., 1964, lõpmatu pikkusega väljendiga keeled, Amsterdam: Põhja-Holland.
• ––– 1965, „Lõplik-kvantitatiivne ekvivalentsus” mudelite teoorias, J. Addison, L. Henkin ja A. Tarski (toim), Amsterdam: Põhja-Holland, 407–412.
• Keisler, HJ, 1974, Lõpmatu loogika mudelteooria, Amsterdam: Põhja-Holland.
• Keisler, HJ ja Julia F. Knight, 2004, “Barwise: lõpmatu loogika ja lubatud komplektid”, ajakiri Symbolic Logic, 10 (1): 4–36
• Kolaitis, P. ja M. Vardi, 1992, “Fixpoint Logic vs Infinitary Logic in finite-Model Theory”, IEEE, seitsmenda iga-aastase arvutiteaduse loogika sümpoosioni (LICS '92) artiklid, IEEE, lk 46–57; saadaval veebis, doi: 10.1109 / LICS.1992.185518
• Kreisel, G., 1965, “Mudeliteoreetilised variandid, rakendused rekursiivsete ja hüperarimeetiliste operatsioonide jaoks”, mudelite teoorias, J. Addison, L. Henkin ja A. Tarski (toim), Amsterdam: Põhja-Holland, 190-205.
• Kueker, D., 1975, “Edasi-tagasi argumendid infinitaarses keeles”, infinitaalses loogikas: In Memoriam Carol Karp (Loengu märkused matemaatikas: köide 492), D. Kueker (toim), Berliin: Springer-Verlag.
• Lopez-Escobar, EGK, 1965, “Lõpmatult pikkade lausete interpoleerimise teoreem”, Fundamenta Mathematicae, 57: 253–272.
• –––, 1966, “Hästikorralduste määratlemisest”, Fundamenta Mathematicae, 59: 13–21.
• Makkai, M., 1977, “Lubatavad komplektid ja lõpmatu loogika”, Matemaatilise loogika käsiraamat, J. Barwise (toim), Amsterdam: Põhja-Holland, 233–282.
• Morley, M., 1965, “Elementide klasside väljajätmine”, modelliteooria, J. Addison, L. Henkin ja A. Tarski (toim), Amsterdam: Põhja-Holland, 265–273.
• Nadel, M. 1985, “L _{ω 1, ω} ja lubatud fragmendid”, J. Barwise ja S. Feferman (toim.) 1985, 271–287.
• Platek, R., 1966, Rekursiooniteooria alused, Ph. D. Lõputöö, Stanfordi ülikool.
• Scott, D., 1961, “Mõõdetavad kardinalid ja kokkupandavad komplektid”, Poola Teaduste Akadeemia bülletään, 9: 521–524.
• ––– 1965, „Loogika kvantitatiivselt pikkade valemitega ja lõplike stringidega”, mudelite teooria, J. Addison, L. Henkin ja A. Tarski (toim), Amsterdam: Põhja-Holland, 329–341.
• Scott, D. ja A. Tarski, 1958, “Senentsiaalne arvutus lõpmata pikkade väljenditega”, Colloquium Mathematicum, 16: 166–170.
• Shelah, Saharon, 2012, “Kena infinitaarne loogika”, American Mathematical Society ajakiri, 25: 395-427, saadaval veebis, 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, “Märkused predikaatloogika kohta lõpmata pikkade väljenditega”, Colloquium Mathematicum, 16: 171–176.
• –––, 1962, “Mõned probleemid ja tulemused, mis on seotud kogumiteooria alustega”, E, Nagel, P. Suppes ja A. Tarski (toim), loogika, metoodika ja teadusfilosoofia, Stanford: Stanford University Press, 123-135.
• Ulam, S., 1930, “Zur Masstheorie in der algemeinen Mengenlehre”, Fundamenta Mathematicae, 16: 140–150.

Akadeemilised tööriistad

	Kuidas seda sissekannet tsiteerida.
	Vaadake selle sissekande PDF-versiooni SEP-i sõprade veebisaidil.
	Otsige seda sisenemisteema Interneti-filosoofia ontoloogiaprojektilt (InPhO).
	Selle kande täiustatud bibliograafia PhilPapersis koos linkidega selle andmebaasi.

Muud Interneti-ressursid

David Markeri (matemaatika, statistika ja arvutiteadus, Illinoisi ülikool / Chicago) alustõde infinitaarsest loogikast