Bezgalīgā Loģika

Satura rādītājs:

Bezgalīgā Loģika
Bezgalīgā Loģika

Video: Bezgalīgā Loģika

Video: Bezgalīgā Loģika
Video: Обыкновенные зомби. Как работает ложь (полный выпуск) 2024, Marts
Anonim

Ieejas navigācija

  • Iestāšanās saturs
  • Bibliogrāfija
  • Akadēmiskie rīki
  • Draugu PDF priekšskatījums
  • Informācija par autoru un atsauce
  • Atpakaļ uz augšu

Bezgalīgā loģika

Pirmoreiz publicēts svētdien, 2000. gada 23. janvārī; būtiska pārskatīšana - 2016. gada 26. februāris

Tradicionāli izteicieni formālajās sistēmās tiek uzskatīti par tādiem, kas apzīmē ierobežotus uzrakstus, kurus vismaz principā var faktiski izrakstīt ar primitīvu notāciju. Tomēr tas, ka (pirmās kārtas) formulas var identificēt ar naturāliem skaitļiem (izmantojot “Gödel numerāciju”) un līdz ar to ar ierobežotām kopām, vairs nav jāuzskata formulas kā uzrakstus, un tas liek domāt par “valodu” modificēšanu. kuru formulas dabiski identificētu kā bezgalīgas kopas. Šāda veida “valodu” sauc par infinitāru valodu: šajā rakstā es aplūkoju tās infinitārās valodas, kuras tiešā veidā var iegūt no pirmās kārtas valodām, ļaujot savienojumiem, disjunkcijām un, iespējams, skaitliskām sekvencēm būt bezgalīgām. garums. Diskusijas laikā būs redzams, ka, lai arī šādu valodu izteiksmīgā jauda ievērojami pārsniedz to galīgo (pirmās kārtas) kolēģu spēju, ļoti maz no tām piemīt valodu “pievilcīgajām” iezīmēm (piemēram, kompaktumam un pilnīgumam). pēdējais. Attiecīgi īpaša uzmanība jāpievērš infinitārajām valodām, kurām faktiski piemīt šīs pazīmes.

1. paragrāfā ir noteikta infinitāro valodu pamata sintakse un semantika; viņu izteiksmīgā jauda tiek parādīta, izmantojot piemērus. 2. punkts ir veltīts tām bezgalīgajām valodām, kuras atļauj tikai ierobežotas skaitliskās secības: šīs valodas izrādās samērā izturējušās. 3. punkts ir veltīts diskusijai par infinitāro valodu kompaktuma problēmu un tās saistību ar tīri teorētiskiem jautājumiem par “lieliem” kardināliem. 4. paragrāfā ir ieskicēts arguments, kas parāda, ka lielākajai daļai “bezgalīgā skaitļa” valodu ir otrās kārtas raksturs un, ipso facto, tās ir ļoti nepilnīgas. §5 ir sniegts īss pārskats par īpašu infinitāro valodu apakšvalodu klasi, par kuru var pierādīt apmierinošu kompaktuma teorēmas vispārinājumu. Šajā sadaļā iekļauta apakšiedaļa par pieļaujamo kopu definīciju. Vēsturiskas un bibliogrāfiskas piezīmes ir sniegtas 6. paragrāfā.

  • 1. Bezgalīgo valodu definīcija un pamatīpašības
  • 2. Valodas ierobežotā skaitā
  • 3. Kompaktuma īpašība
  • 4. Bezgalīgo un kvantitatīvo valodu nepilnīgums
  • 5. L (ω 1, ω) apakšvalodas un Bārvesa kompakuma teorija

    5.1. Pieļaujamās kopas jēdziena definīcija

  • 6. Vēsturiskas un bibliogrāfiskas piezīmes
  • Bibliogrāfija
  • Akadēmiskie rīki
  • Citi interneta resursi
  • Saistītie ieraksti

1. Bezgalīgo valodu definīcija un pamatīpašības

Ņemot vērā tādu bezgalīgu kardinālu κ, λ pāri, ka λ ≤ κ, mēs definējam infinitāro valodu klasi, katrā no tām mēs varam veidot kardināluma formulas kopu savienojumus un disjunkcijas <κ, kā arī kvantificēt garuma mainīgo virknes < λ.

Ļaujiet L - (galīgajai) bāzes valodai - būt patvaļīgai, bet fiksētai pirmās kārtas valodai ar jebkuru skaitu ekstraloģisku simbolu. Infinitārajai valodai L (κ, λ) ir šādi pamata simboli:

  • Visi simboli L
  • Atsevišķu mainīgo kopa Var, kurā Var (rakstīts: | Var |) kardinalitāte ir κ
  • Loģisks operators ∧ (bezgalīga savienojums)

Preformulu L klase (κ, λ) tiek rekursīvi definēta šādi:

  • Katra L formula ir iepriekš sagatavota formula;
  • ja φ un ψ ir sagataves, tad arī φ∧ψ un ¬φ;
  • ja Φ ir tādu sagatavju kopums, kas | Φ | <κ, tad ∧Φ ir sagatave;
  • ja φ ir sagatave un X ⊆ Var ir tāds, ka | X | <λ, tad ∃ X φ ir sagatave;
  • visas sagataves ir definētas iepriekšminētajos punktos.

Ja Φ ir priekšformu kopa, kuru indeksē I kopa, teiksim Φ = {φ i: i ∈ I}, tad mēs piekrītam rakstīt ∧Φ:

i ∈ I  φ

vai, ja es esmu naturālo skaitļu kopa, tad write raksta:

φ 0 ∧ φ 1 ∧ …

Ja X ir atsevišķu mainīgo kopums, ko indeksē ar kārtas α, teiksim X = {x ξ: ξ <α}, mēs piekrītam rakstīt (∃ x ξ) ξ <α φ par ∃ X φ.

Loģiskie operatori ∨, →, ↔ tiek definēti kā parasti. Mēs arī iepazīstinām ar operatoriem ∨ (bezgalīga disjunkcija) un ∀ (vispārēja kvantitatīva noteikšana) līdz

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

∀Xφ = df ¬∃X¬φ,

un izmanto līdzīgas konvencijas kā ∧, ∃.

Tādējādi L (κ, λ) ir infinitārā valoda, kas iegūta no L, pieļaujot savienojumus un disjunkcijas garumā <κ un kvantificēšanu [1] garumā <λ. Valodas L (κ, ω) tiek sauktas par galīgās kvantifikatorvalodām, pārējās bezgalīgās kvantifikatorvalodas. Ievērojiet, ka L (ω, ω) ir tikai pati L.

Ievērojiet šo anomāliju, kas var rasties infinitārā valodā, bet ne finišā. Valodā L (ω 1, ω), kas pieļauj skaitāmi bezgalīgus konjunktūras, bet tikai ierobežotus kvantificējumus, ir pirmsformulas ar tik daudziem brīvajiem mainīgajiem, ka tās nevar “aizvērt” L (ω 1, ω) teikumos, pievienojot skaitļus. Tas attiecas, piemēram, uz L (ω 1, ω) formulas

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

kur L ir binārā relācijas simbols <. Šī iemesla dēļ mēs rīkojamies šādi

Definīcija. L (κ, λ) formula ir sagatave, kas satur <λ brīvus mainīgos. Visu L (κ, λ) formulu komplekts tiks apzīmēts ar formu (L (κ, λ)) vai vienkārši ar formu (κ, λ) un visu teikumu kopu ar nosūtītiem (L (κ, λ)) vai vienkārši nosūtīts (κ, λ).

Šajā sakarā ievērojiet, ka kopumā neko nevarētu gūt, apsverot “valodas” L (κ, λ) ar λ> κ. Piemēram, “valodā” L (ω, ω 1) formulām būs tikai bezgalīgi daudz brīvo mainīgo, savukārt būs virkne “bezjēdzīgu” kvantifikatoru, kas spēs saistīt bezgalīgi daudz brīvo mainīgo. [2]

Nosakot L (κ, λ) sintakse, mēs nākamreiz ieskicējam tā semantiku. Tā kā L (κ, λ) ekstraloģiskie simboli ir tikai L simboli un tieši šie simboli nosaka to struktūru formu, kurās ir interpretējama dotā pirmās kārtas valoda, ir dabiski definēt L (κ, λ) struktūrai jābūt vienkārši L struktūrai. Jēdziens L (κ, λ) formulas apmierināšanai L struktūrā A (ar elementu secību no A domēna) tiek definēts tādā pašā induktīvā veidā kā L formulas, izņemot to, ka mums jāpievieno divi papildu klauzulas, kas atbilst for un ∃Xφ teikumiem sagatavju definīcijā. Šajos divos gadījumos mēs, protams, definējam:

∧Φ ir apmierināts ar A (pēc noteiktas secības) ⇔ visiem φ ∈ Φ, φ ir apmierināts ar A (pēc kārtas);

∃ X φ ir izpildīts A ⇔ ir secība no elementiem no domēna A in bijective sarakstē ar X, kas atbilst φ in A.

Šīs neoficiālās definīcijas ir jānostiprina, precīzi izstrādājot, bet to nozīmei jābūt skaidrai lasītājam. Tagad kļūst pieejami parastie L (κ, λ) formulas un teikumu patiesības, derīguma, apmierinātības un formulas un teikuma paraugi. Jo īpaši, ja A ir L-struktūra un σ ∈ Nosūtīts (κ, λ), tad rakstīsim, ka ⊨ σ A ir σ paraugs, un ⊨ σ σ ir derīgs, tas ir, visiem A, A ⊨ σ. Ja Δ ⊆ Nosūtīts (κ, λ), tad Δ ⊨ σ pierakstīsim σ, kas ir loģiskas Δ sekas, tas ir, katrs Δ modelis ir σ paraugs.

Tagad mēs sniedzam dažus piemērus, kas paredzēti, lai parādītu izteiksmīgo spēku infinitārajām valodām L (κ, λ) ar κ ≥ 1. Katrā ziņā ir labi zināms, ka attiecīgo jēdzienu nevar izteikt nevienā pirmās kārtas valodā.

Aritmētikas standarta modeļa raksturojums ar L (ω 1, ω). Šeit standarta aritmētikas modelis ir struktūra N = ⟨N, +, ·, s, 0⟩, kur N ir dabisko skaitļu kopa, +, · un 0 ir to parastās nozīmes, un s ir nākamā operācija. L apzīmē pirmās kārtas valoda piemērota N. Tad klase no L-struktūras isomorphic N sakrīt ar to klases modeļos, kas kopā nākamā L (omega 1, omega) teikums (kur 0 ir nosaukums no 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

Termini s n x ir rekursīvi definēti ar

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

Visu ierobežoto kopu klases raksturojums L (ω 1, ω). Bāzes valodai nav ekstraloģisku simbolu. Tad visu ierobežoto kopu klase sakrīt ar L (ω 1, ω) jūtības modeļu klasi

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

Patiesība definīcija L (ω 1, ω) par skaitāmu bāzes valodu L. Ļaut L ir saskaitāmas pirmās kārtas valoda (piemēram, valoda aritmētiskā vai kopu teorija), kas satur vārdu n katram dabas skaitu n, un σ 0, σ 1,… ir to teikumu uzskaitījums. Tad L (ω 1, ω) formula

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

ir patiesības predikāts L tiktāl, cik teikums

Tr (n) ↔ σ n

ir derīgs katram n.

Labu pasūtījumu raksturojums L (ω 1, ω 1). Bāzes valodā L šeit ir binārs predikāta simbols ≤. Būtu σ 1 parastais L teikums, kas raksturo lineāro secību. Tad L-struktūru klase, kurā ≤ interpretācija ir sakārtota, sakrīt ar L (ω 1, ω 1) teikuma modeļu klasi σ = σ 1 ∧ σ 2, kur

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

Ievērojiet, ka teikumā σ 2 ir bezgalīgs skaitlis: tas izsaka būtībā otrās kārtas apgalvojumu, ka katrai skaitāmai apakškopai ir vismazākais loceklis. Faktiski var parādīt, ka šī bezgalīgā skaitļa klātbūtne ir būtiska: labi sakārtotu struktūru klasi nevar raksturot nevienā ierobežotā un skaitļošanas valodā. Šis piemērs norāda, ka tādas bezgalīgas kvantifikatoru valodas kā L (ω 1, ω 1) drīzāk izturas kā otrās kārtas valodas; mēs redzēsim, ka viņiem ir kopīgi pēdējie trūkumi (nepilnīgums), kā arī dažas no priekšrocībām (izteikta izteiksmīgā spēja).

Daudzus pirmās kārtas valodu paplašinājumus var tulkot infinitārajās valodās. Piemēram, apsveriet vispārināto kvantifikatorvalodu L (Q 0), kas iegūta no L, pievienojot jaunu kvantifikatora simbolu Q 0 un interpretējot Q 0 x φ (x), jo eksistē bezgalīgi daudz x tādu, ka φ (x). Ir viegli redzēt, ka teikumam Q 0 x φ (x) ir tādi paši modeļi kā L (ω 1, ω) -jūtībai.

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

Tādējādi L (Q 0) dabiskā nozīmē ir tulkojams L (ω 1, ω). Vēl viena valoda, kas šajā nozīmē tiek tulkota L (ω 1, ω), ir vāja otrās kārtas valoda, kas iegūta, pievienojot L saskaitāmu monādisko predikātu mainīgo kopu, ko pēc tam interpretē kā diapazonu visās ierobežotajās indivīdu kopās.

Var ieviest arī valodas ar patvaļīgi garu savienojumu, disjunkciju un (iespējams) kvantitatīvu noteikšanu. Par fiksētu bezgalīgu kardināls koeficientu l, valodu L (∞, λ) ir definēts, norādot savu klasi formulas, forma (∞, λ), būt savienība, visā κ ≥ λ, no kopas veidlapas (κ, λ). Tādējādi L (∞, λ) pieļauj patvaļīgi garu savienojumu un disjunkciju tādā nozīmē, ka, ja Φ ir formas (∞, λ) patvaļīga apakškopa, tad gan ∧Φ, gan ∨Φ ir formas (∞, λ) locekļi. Bet L (∞, λ) atzīst tikai garuma <λ kvantificēšanu: visām tās formulām ir <λ brīvi mainīgie. Valoda L (∞, ∞) savukārt tiek definēta, precizējot tās formulu klasi, formu (∞, ∞), lai tā būtu savienība pār visiem bezgalīgajiem kardināliem λ Forma (∞, λ). Tātad L (∞, ∞) pieļauj patvaļīgi garu kvantifikāciju papildus patvaļīgi garam savienojumam un disjunkcijai. Ņemiet vērā, ka forma (∞, λ) un forma (∞, ∞) ir piemērotas klases Gēdela-Bernaisa kopas teorijas izpratnē. L (∞, λ) un L (∞, ∞) formulu apmierinātību struktūrā var definēt ar acīmredzamu attiecīgā jēdziena L (κ, λ) paplašinājumu.

2. Valodas ierobežotā skaitā

Mēs esam atzīmējuši, ka tādas bezgalīgas kvantifikatorvalodas kā L (ω 1, ω 1) atgādina otrās kārtas valodas, jo tās ļauj kvantitatīvi noteikt bezgalīgu indivīdu kopu. Fakts, ka tas nav pieļaujams ierobežotajā skaitliskajā valodā, liek domāt, ka dažos aspektos tie var būt tuvāk viņu pirmās kārtas kolēģiem, nekā varētu šķist no pirmā acu uzmetiena. Mēs redzēsim, ka tas tā patiešām ir, it īpaši L gadījumā (ω 1, ω).

Valoda L (ω 1, ω) ieņem īpašu vietu starp infinitārajām valodām, jo tāpat kā pirmās kārtas valodas, tā atzīst efektīvu deduktīvo aparātu. Faktiski pievienosim parastajām pirmās kārtas aksiomām un secinājumu noteikumiem jauno aksiomu shēmu

∧Φ → φ

jebkurai skaitāmai kopai ⊆ ⊆ veidlapai1, ω) un jebkurai φ ∈ Φ kopā ar jauno secinājumu noteikumu

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

un ļauj atskaitījumiem būt skaitāmiem garumiem. Rakstot ⊢ * atskaitāmībai šajā ziņā, tad mums ir

L (ω 1, ω) - pilnīguma teorēma. Jebkurai nosūtītajai σ ∈ (ω 1, ω), ⊨ σ ⇔ ⊢ * σ

Kā tūlītēju secinājumu mēs secinām, ka šis deduktīvais aparāts ir piemērots atskaitījumiem no saskaitāmām telpu kopām L (ω 1, ω). Tas ir, ar acīmredzamu pagarināšanu pierakstā, mums ir, par jebkuru skaitāmu noteiktā Δ ⊆ Nosūtītās1, ω)

(2.1) Δ ⊨ σ ⇔ Δ⊢ * σ

Šo pilnīguma teorēmu var pierādīt, modificējot parasto Henkina pilnības pierādījumu pirmās kārtas loģikai vai izmantojot Būla-algebriskās metodes. Līdzīgi argumenti, kas piemēroti piemērotiem turpmākiem aksiomu un secinājumu likmju palielinājumiem, dod analoģiskas pilnīguma teorēmas daudzām citām galīgo kvantifikatoru valodām.

Ja tiek pieļauti tikai saskaitāmā garuma atskaitījumi, tad nevar iestatīt deduktīvu aparātu L (ω 1, ω), kas būtu piemērots atskaitījumiem no patvaļīgiem telpu komplektiem, tas ir, kuriem (2.1) būtu jāatrodas par katru komplektu Δ ⊆ Nosūtīts1, ω) neatkarīgi no kardināluma. Tas izriet no vienkārša novērojuma, ka pastāv pirmās kārtas valoda L un neizskaitāms L (ω 1, ω) jūtu kopums that, ka Γ nav modeļa, bet katra saskaitāmā et apakškopa. Lai to redzētu, ļaujiet L būt aritmētikas valodai, kas papildināta ar ω 1 jauniem nemainīgiem simboliem { c ξ: ξ <ω 1 }, un ļaujiet Γ būt L (ω 1, ω) -sajūtu kopai {σ} ∪ { cξc η: ξ ≠ η}, kur σ ir L (ω 1, ω) -jūtība, kas raksturo aritmētikas standarta modeli. Šis piemērs arī parāda, ka kompaktuma teorēma neizdodas L (ω 1, ω) un tātad arī jebkurai L (κ, λ) ar κ ≥ 1.

Vēl viens rezultāts, kas pastāv pirmās kārtas gadījumā, bet neizdodas L (κ, ω) ar κ ≥ 1 (un arī attiecībā uz L (ω 1,) 1), lai gan to ir grūtāk pierādīt), ir prenexa normālā forma teorēma. Teikums tiek papildināts, ja visi tā skaitļi ir parādīti priekšā; mēs sniedzam L (ω 1, ω) teikuma piemēru, kas nav līdzvērtīgs prenexu teikumu savienojumam. Ļaujiet L būt pirmās kārtas valodai bez ekstraloģiskiem simboliem un σ ir L (ω 1, ω) -jūtība, kas raksturo ierobežoto kopu klasi. Pieņemsim, ka σ bija līdzvērtīgi konjunkcijai

i ∈ I σ i

papildinājuma L (ω 1, ω) -jutības σ i. Tad katrs σ i ir formas

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

kur katrs Q k ir ∀ vai ∃ un φ i ir (iespējams, infinitārs) formulu savienojums vai disjunkcija formā x k = x l vai x k ≠ x l. Tā kā katrs σ i ir teikums, katrā φ i ir tikai bezgalīgi daudz mainīgo, un ir viegli redzēt, ka katrs φ i ir līdzvērtīgs pirmās kārtas formulai. Attiecīgi katru σ i var uzskatīt par pirmās kārtas teikumu. Tā kā σ tiek uzskatīts par ekvivalentu σ i konjunkcijai, no tā izriet, ka σ un kopums Δ = {σ i: i ∈ I} ir vieni un tie paši modeļi. Bet acīmredzami, ka σ, tātad arī Δ, ir visu ierobežoto kardinālu modeļi; kompakcijas teorēma pirmās kārtas teikumu kopām tagad nozīmē, ka Δ un tātad arī σ ir bezgalīgs modelis, kas ir pretrunā ar σ definīciju.

Pievēršoties Löwenheim-Skolem teorēmai, mēs secinām, ka lejupejošajai versijai ir atbilstoši vispārinājumi L (ω 1, ω) (un, protams, visām infinitārajām valodām). Faktiski var parādīt gandrīz tāpat kā pirmās kārtas teikumu kopām, ka, ja Δ ⊆ Nosūtītie1, ω) ir bezgalīgs kardināluma modelis ≥ | Δ |, tad tam ir kardināluma modelis, kas lielāks no ℵ 0, | Δ |. Jo īpaši jebkurai L (ω 1, ω) izjūtai ar bezgalīgu modeli ir saskaitāms modelis.

No otras puses, augšupvērstā Lēvenheima-Skolema teorēma tās parastajā formā neizdodas visām infinitārajām valodām. Piemēram, L (ω 1, ω) jutībai, kas raksturo aritmētikas standarta modeli, ir kardinalitātes modelis ℵ 0, bet nav citu kardinālumu paraugu. Tomēr šeit viss nav zaudēts, kā mēs redzēsim.

Mēs definējam L valodas Hanfa skaitli h (L) kā vismazāko kardinālu κ tā, ka, ja L- teicienei ir kardināluma modelis κ, tai ir patvaļīgi lielas kardinālības modeļi. H (L) esamība ir viegli nosakāma. Par katru L- teicienu σ, kurai nav patvaļīgi lielas kardinālības modeļa, ļaujiet κ (σ) būt vismazāk kardinālam κ tā, ka σ nav kardinalitātes modeļa κ. Ja λ ir visu κ (σ) supremums, tad, ja L teikumam ir kardināluma modelis λ, tam ir patvaļīgi lielas kardinalitātes modeļi.

Rekursīvi definējiet kardinālus μ (α) ar

μ (0) = 0
μ (α + 1) = 2 μ (α)
μ (λ) = α <λ μ (α), λ robežai.

Tad to var parādīt

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

līdzīgi rezultāti tiek turēti arī citās ierobežotās skaitļu valodās. Tādu bezgalīgu kvantifikatoru valodu kā L (ω 1, ω 1) Hanfa skaitļu vērtības ir jutīgas pret lielo kardinālu klātbūtni vai kā citādi, bet jebkurā gadījumā tām jābūt ievērojami lielākām par L (ω 1, ω).

Rezultāts L, kas vispārināms uz L (ω 1, ω), bet nav nevienas citas infinitārās valodas, ir

Kreiga interpolācijas teorēma: Ja σ, τ ∈ Nosūtītie1, ω) ir tādi, ka ⊨ σ → τ, tad ir θ ∈ Nosūtītie1, ω) tādi, ka ⊨ σ → θ un ⊨ θ → τ, un katrs ekstraloģisks simbols, kas rodas θ, notiek gan σ, gan τ.

Pierādījums ir pamatoti tiešs pirmās kārtas lietas pagarinājums.

Visbeidzot, mēs pieminam vēl vienu rezultātu, kas labi vispārinās L (ω 1, ω), bet nevienā citā bezgalības valodā. Ir labi zināms, ka, ja A ir kāda ierobežota L-struktūra ar tikai galīgi daudzām attiecībām, pastāv L teikums σ, kas raksturo A līdz izomorfismam. L (ω 1, ω) mums ir šāds vispārinājums, kas pazīstams kā

Skota izomorfisma teorēma. Ja ir saskaitāmas L-struktūra ar tikai countably daudziem attiecības, tad ir L (ω 1, ω) -sentence kura klase skaitāmu modeļu sakrīt ar klases L-struktūru isomorphic ar A.

Ierobežojums attiecībā uz skaitāmām struktūrām ir būtisks, jo skaitāmību parasti nevar izteikt ar L (ω 1, ω) -jūtīgumu.

Valodu L (∞, may) var arī uzskatīt par ierobežotā skaitļa valodu. Konstrukciju ekvivalences jēdzienam attiecībā uz šo valodu ir īpaša nozīme: mēs saucam divas (līdzīgas) struktūras A un B (∞, ω) - ekvivalentas, rakstītas A∞ω B, ja vieni un tie paši L (∞, ω) hold gan A un B. Šīs attiecības, pirmkārt, var raksturot ar jēdzienu par daļēju izomorfismu. Daļējs izomorfisms starp A un B ir bezspēcīga karšu saime P tā, ka:

  • Attiecībā uz katru p ∈ P, dom (p) ir pamatne no A, ran (p) ir pamatne no B, un p ir vesels izomorfisma no savā sfērā uz tās diapazonā; un
  • Ja p ∈ P, a ∈ A, b ∈ B, tad pastāv r, s ∈ P, kas gan p stiepjas, lai ∈ dom (r), b ∈ skrietu (s) (“turp un atpakaļ” īpašums).

Ja pastāv daļējs izomorfisma starp A un B, mēs sakām, ka un B ir daļēji isomorphic un rakstīt ≅ p B. Pēc tam mums ir

Karpas daļējā izomorfisma teorēma.

Par jebkuru līdzīgu struktūru, B, ≡ ∞ω B ⇔ ≅ p B.

Ir arī Skota izomorfisma teorēmas versija L (∞, ω), proti:

(2.2) Ņemot vērā jebkuru struktūru A, L (∞, ω) -jūtība σ ir tāda, ka visām konstrukcijām B, Ap BB ⊨ σ.

Daļējs izomorfisms un (∞, ω) līdzvērtība ir saistīti ar Būla izomorfisma jēdzienu. Lai to definētu, mums jāievieš ideja par Būla vērtēto kopas teorijas modeli. Ņemot vērā pilnīgu Būla algebru B, B vērtības kopu Visumu V (B), kas pazīstams arī kā kopu Visuma B pagarinājums, iegūst, vispirms definējot, rekursīvi uz α,

V α (B) = {x: x ir funkcija ∧ diapazons (x) ⊆ B ∧ ∃ξ <α [domēns (x) ⊆ V ξ (B)]}

un pēc tam iestatīšana

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

V (B) locekļus sauc par B vērtības kopām. Tagad ir viegli redzēt, ka B vērtētā kopa ir tieši B vērtētā funkcija ar domēnu B vērtēto kopu kopu. Ļaujiet L būt kopas teorijas pirmās kārtas valodai un ļaujiet L (B) būt valodai, kas iegūta, pievienojot L nosaukumam katram V (B) elementam (mēs šim elementam un tā nosaukumam izmantosim to pašu simbolu). Tagad var izveidot valodas L (B) (teikumu ) kartējumu [·] (B) B valodā: katram L (B) teikumam σ B elements [σ] (B) ir “Būla patiesības vērtība”σ V (B). Šī kartēšana [·] (B) ir definēta tā, lai visas Zermelo-Fraenkela kopas teorijas teorēmas tiktu nosūtītas uz B augšējo elementu 1, ti, uz “patiesību”; attiecīgi V (B) var uzskatīt par Būla vērtētu kopas teorijas modeli. Kopumā, ja [σ] (B) = 1, mēs sakām, ka σ ir derīgs V (B), un raksta V (B) ⊨ σ.

Tagad katram x ∈ V ir kanonisks reprezentatīvs lielums V (B), kas atbilst

x = y, ja V (B) ⊨ x = y

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

Mēs sakām, ka divas līdzīgas struktūras A, B ir Būla izomorfas, rakstītas Ab B, ja kādai pilnīgai Būla algebrai B mums ir V (B)AB, tas ir, ja ir Būla pagarinājums kopumu kopums, kurā A un B kanoniskie pārstāvji ir izomorfi ar Būla vērtību 1. Tad var parādīt, ka:

(2.3) ≡ ∞ω BAb B.

Šo rezultātu var uzlabot, izmantojot kategoriju teorētisko formulējumu. Šim nolūkam mums ir nepieciešams jēdziens (n) (elementārs) topos. Lai ieviestu šo jēdzienu, mēs sākam ar komplektu kopu un kartējumu pazīstamo kategoriju. Komplektam ir šādas galvenās īpašības:

  1. Pastāv “termināļa” objekts 1 tā, ka jebkuram objektam X ir unikāla karte X → 1 (attiecībā uz 1 mēs varam ņemt jebkuru elementu kopu, it īpaši {0}).
  2. Jebkuram pāra objektam X, Y ir Dekarta izstrādājums X × Y.
  3. jebkuram objektu pārim var izveidot “eksponenciālu” objektu Y X no visām kartēm no X → Y.
  4. Pastāv “patiesības vērtības” objekts Ω tāds, ka katram objektam X ir dabiska atbilstība starp X apakšobjektiem (apakšgrupām) un kartēm X → Ω. (Attiecībā uz Ω mēs varam ņemt kopu 2 = {0,1}; kartes X → Ω ir X raksturīgās funkcijas.)

Visus četrus nosacījumus var formulēt kategoriju teorētiskā valodā - kategorija, kas tos apmierina, tiek saukta par topos. Kategoriju komplekts ir topos; tātad ir arī (i) kategoriju kopa (B), kuru vērtības ir Boolean vērtības, un kartēšana jebkurā kopu Visuma Boole pagarinājumā V (B); ii) komplektu griezumu kategorija topoloģiskajā telpā; iii) visu karšu diagrammu kategorija

X 0 → X 1 → X 2 →…

Katras šīs kategorijas objektus var uzskatīt par kopām, kas kaut kādā veidā mainās: i) gadījumā virs Būla algebra; ii) gadījumā virs topoloģiskās telpas; iii) gadījumā (diskrētajā laikā). Tad topos var tikt iecerēts kā “mainīgu” kopumu visums. Pazīstamais kategoriju komplekts ir īpašs topos ierobežojošs gadījums, kad objektu “variācijas” ir samazinātas līdz nullei.

Tāpat kā noteiktā teorijā, “loģiskos operatorus” patiesības vērtības objektā var definēt jebkurā topos. Tās ir kartes ¬: Ω → Ω; ∧, ∨, ⇒: Ω × Ω → Ω, kas atbilst nolieguma, savienojuma, disjunkcijas un implicēšanas loģiskajām operācijām. Ar šīm operācijām Ω kļūst par Heitinga algebru, tādējādi vispārīgi iemiesojot nevis klasiskās, bet gan intutionistiskās loģikas likumus. Šajā nozīmē intuitīvisma loģika tiek “internalizēta” topos: intuitionistic loģika ir mainīgo kopu loģika. (Protams, klasiskā loģika tiek internalizēta noteiktos mērķos, piemēram, Set un Set (B) jebkurai pilnīgai Būla algebrai B.)

Jebkurus topos var iecerēt kā iespējamus “diskursa visumus”, kuros var interpretēt matemātiskus apgalvojumus un veikt matemātiskas konstrukcijas. Matemātiskie apgalvojumi tiek interpretēti topos E, izsakot E iekšējā valodā - tipoteorētiskās versijas parastajai kopas teorijas valodai. Analogā veidā ar Būla vērtēto derīgumu, tā iekšējās valodas teikuma σ E var ieviest atbilstošu derīguma jēdzienu. Atkal mēs rakstām E ⊨ σ par “σ ir derīgs E”.

Tiek uzskatīts, ka toposts E ir pilns, ja jebkuram I kopumam tā termināļa objekta I-reizes kopējais spēks [3]I 1 atrodas E. ∐ I 1 var uzskatīt par kopas E kanonisko pārstāvi. Es; attiecīgi, mēs to rakstām vienkārši kā es. (V (B) daļā tas sakrīt ar iepriekš definēto I.) Visi iepriekš minētie mērķi ir pilni.

Tagad ļaujiet E būt pilnam topos. Ja A = (A, R,…) ir struktūra, rakstiet A (A, R,…). Divas struktūras A un B tiek uzskatītas par topos izomorfām, kuras raksta At B, ja attiecībā uz dažiem topiem E, kas definēts kopu kategorijā, mums ir E ⊨ A ≅ B. Citiem vārdiem sakot, divas struktūras ir topos izomorfas, ja to kanoniskie pārstāvji ir izomorfiski dažu topos iekšējā valodā. Pēc tam to var parādīt

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

Attiecīgi (∞, ω) ekvivalenci var uzskatīt par izomorfismu “mainīgo” kopu Visumu ārkārtīgi vispārīgajā kontekstā. Šajā ziņā (∞, ω) ekvivalence ir “nemainīgs” izomorfijas jēdziens.

3. Kompaktuma īpašība

Kā redzējām, kompakuma teorēma tās parastajā formā neizdodas visām infinitārajām valodām. Neskatoties uz to, ir interesanti noteikt, vai infinitārās valodas atbilst kādai no atbilstoši modificētajām teorēmas versijām. Šai tā sauktajai kompakuma problēmai ir dabiska saistība ar tīri teorētiskiem jautājumiem, kas saistīti ar “lieliem” kardināliem.

Mēs izstrādājam šādu definīciju. Lai κ būtu bezgalīgs kardināls. Tiek uzskatīts, ka valoda L ir κ- kompakta (attiecīgi vāji κ-kompakta), ja vien Δ ir L- sajūtu kopums (attiecīgi L -veida kardinālības jutību kopums ≤ κ) un katra kardināluma Δ apakškopa < κ ir modelis, tāpat kā Δ. Ievērojiet, ka parastā L kompaktuma teorēma ir precīzi apgalvojums, ka L ir ω-kompakts. Viens no iemesliem, kāpēc tā ir nozīmīga κ-kompaktuma īpašībai, ir šāds. Call L κ- pilns (resp. Vāji κ- pilns), ja ir deduktīvus sistēma P par L ar atskaitījumiem garumu <κ tāds, ka, ja Δ ir P -consistent [4] komplekts L- gaitas (attiecīgi tādas, ka | Δ | ≤ κ), tad Δ ir modelis. Ievērojiet, ka šāds P būs piemērots atskaitījumiem no patvaļīgām telpu kopām (ar kardinālumu ≤ κ) 2. punkta izpratnē. Ir viegli redzēt, ka, ja L ir κ-pilnīgs vai vāji κ-pilnīgs, tad L ir κ-kompakts vai vāji κ-kompakts. Tādējādi, ja mēs varam parādīt, ka dotā valoda nav (vāji) κ-kompakta, tad tai nevar būt deduktīva sistēma ar tādu atskaitījumu garumu <κ, kas piemēroti atskaitījumiem no patvaļīgām telpu kopām (ar kardinālumu ≤ κ).

Faktiski izrādās, ka lielākajai daļai valodu L (κ, λ) nav pat vāji κ-kompakts raksturs, un tām, kuras ir, κ ir jābūt ārkārtīgi lielam kardinālam. Mums būs vajadzīgas dažas definīcijas.

Tiek teikts, ka bezgalīgs kardināls κ ir vāji nepieejams, ja

a) λ <κ → λ + <κ (kur λ + apzīmē λ kardinālo pēcteci) un

(b) | Es | <κ un λ i <κ (visiem i ∈ I) ⇒ ∑ i ∈ I λ i <κ.

Ja papildus

c) λ <κ ⇒ 2 λ <κ,

tad κ tiek uzskatīts par (stipri) nepieejamu. Tā kā ℵ 0 nav pieejams, parasti ir pievērst uzmanību tikai tiem nepieejamajiem vai vāji nepieejamiem kardināliem, kuru vērtība pārsniedz ℵ 0. Attiecīgi, nepieejami vai vāji nepieejami kardināli vienmēr tiks uzskatīti par neuzskaitāmiem. Ir skaidrs, ka šādiem kardināliem - ja tādi pastāv - jābūt ārkārtīgi lieliem; un patiešām Gēdela nepabeigtības teorēma nozīmē, ka pat vāji nepieejamu kardinālu esamību nevar pierādīt ar parasto kopu teorijas aksiomu.

Sauksim kardinālu κ kompaktu (attiecīgi vāji kompaktu), ja valoda L (κ, κ) ir κ kompakta (attiecīgi vāji κ kompakta). Tad mums ir šādi rezultāti:

(3.1) ℵ 0 ir kompakts. Tas, protams, ir tikai kodolīgs veids, kā izteikt kompaktuma teorēmu pirmās kārtas valodām.

(3.2) κ ir vāji kompakts ⇒ L (κ, ω) ir vāji κ- kompakts ⇒ κ ir vāji nepieejams. Attiecīgi ir konsekventi (ar parastajām kopu teorijas aksiomām) pieņemt, ka neviena valoda L (κ, ω) ar κ ≥ 1 nav vāji κ-kompakta vai, vēl jo vairāk, vāji κ-pilnīga.

(3.3) Pieņemsim, ka κ nav pieejams. Tad κ ir vāji kompakts ⇔ L (κ, ω) ir vāji κ- kompakts. Arī κ ir vāji kompakts ⇒ pirms κ ir κ nepieejamību kopums. Tādējādi vāji kompakts nepieejams kardināls ir ārkārtīgi liels; it īpaši tas nevar būt pirmais, otrais, …, n th … nepieejama.

(3.4) κ ir kompakts ⇒ κ nav pieejams. (Bet, ja rezultāts ir tieši virs, sarunāties neizdodas.)

Ļaujiet Constr iestāties par Gödel konstruktīvisma aksiomu; atcerieties, ka Constr ir saskaņā ar parastajām kopu teorijas aksiomām.

(3.5) Ja Constr tur, tad kompaktu kardinālu nav.

(3.6) Pieņemsim, ka Constr un κ ir nepieejama. Tad κ ir vāji kompakts ⇔ L (ω 1, ω) ir vāji κ- kompakts visiem L.

(3.7) Ja Constr ir, tad nav kardinālu κ, kuriem L (ω 1, ω) būtu kompakts. Attiecīgi, tas ir saskaņā ar parastajām kopas teorijas aksiomām, pieņemot, ka nav tāda kardināla κ, ka visas valodas L (ω 1, ω) būtu κ-pilnīgas. Šis rezultāts ir pretstatā faktam, ka visas pirmās kārtas valodas ir ω-pilnīgas.

Šo rezultātu nozīme ir tāda, ka kompaktuma teorēma neizdodas ļoti slikti lielākajai daļai valodu L (κ, λ) ar κ ≥ 1.

Šeit ir sakārtotas dažas vēsturiskas piezīmes. Pagājušā gadsimta trīsdesmitajos gados matemātiķi izpētīja dažādas tā saucamās kopu mēra problēmas versijas, problēma, kas radās saistībā ar Lebesgue mēra teoriju kontinuumā. Jo īpaši tika formulēts šāds ļoti vienkāršs pasākuma jēdziens. Ja X ir kopa, tad (skaitāmi pievienojams divvērtīgs trīsvienīgs) mērs uz X ir karte μ uz jaudas kopu P X līdz {0, 1}, kas atbilst:

a) μ (X) = 1, (b) μ ({x}) = μ (∅) = 0 visiem x ∈ X, un

c) ja A ir jebkura savstarpēji nesadalītu X apakšgrupu saskaitāma saime, tad μ (∪ A) = ∑ {μ (Y): Y ∈ A }.

Acīmredzot tas, vai dotā kopa atbalsta šādu mēru, ir atkarīgs tikai no tā kardinalitātes, tāpēc ir dabiski definēt kardinālu κ, lai tas būtu izmērāms, ja visi kardinalitātes komplekti κ atbalsta šāda veida mēru. Ātri tika saprasts, ka izmērāmam kardinālam jābūt nepieejamam, taču sarunvalodas nepatiesība netika noteikta līdz 1960. gadiem, kad Tarskis parādīja, ka izmērāmie kardināli ir vāji kompakti un viņa students Hanfs parādīja, ka pirmā, otrā utt. Nepieejamība nav vāja. kompakts (sal. (3.3)). Lai gan secinājums, ka izmērāmiem kardināliem jābūt milzīgi lieliem, tagad parasti tiek pierādīts, neveicot apvedceļu caur vāju kompaktumu un infinitārajām valodām, tomēr paliek fakts, ka šīs idejas tika izmantotas, lai vispirms noteiktu rezultātu.

4. Bezgalīgo un kvantitatīvo valodu nepilnīgums

Droši vien vissvarīgākais rezultāts pirmās kārtas valodās ir Gēdela pilnīguma teorēma, kas, protams, saka, ka jebkuras pirmās kārtas valodas L derīgo formulu kopu var ģenerēt no vienkārša aksiomu kopuma, izmantojot dažus tiešus secinājums. Šīs teorēmas galvenās sekas ir tādas, ka, ja L formulas kaut kādā konstruktīvā veidā tiek kodētas kā naturālie skaitļi, tad derīgo teikumu (kodu) kodi ir rekursīvi uzskaitāmi. Tādējādi pirmās kārtas valodas pilnīgums nozīmē, ka tās derīgo teikumu kopums ir definējams īpaši vienkāršā veidā. Tāpēc, ņemot vērā patvaļīgu valodu L, šķiet saprātīgi pārvērst šo nozīmi un ierosināt, ka, ja derīga L-jūtības nav definējamas vienkāršā veidā, tad L nevar noteikt jēgpilnu pabeigtības rezultātu vai, kā mēs teiksim, ka L ir nepilnīgs. Šajā sadaļā mēs izmantosim šo ieteikumu, ieskicējot pierādījumu tam, ka “lielākā daļa” bezgalīgo kvantitatīvo valodu šajā ziņā ir nepilnīgas.

Vispirms ieviesīsim formālu definējamības jēdzienu šādi. Ja L ir valodu, A ir L -structure, un X apakškopa, domēna A A, mēs teikt, ka X ir definējama in A ar formulu φ (x, y 1, …, y n) of L ja tur ir virknei ir 1, …, kas ir n elementus, kas ir tāds, ka x ir apakškopa visu elementu x ∈ A, attiecībā uz kuriem φ (x, A 1, …, kas ir n) piederošo A.

Tagad uzrakstiet Val (L) visām derīgajām L- pazīmēm, ti, tām, kuras ir katrā L- struktūrā. Lai apgalvojumam “Val (L) ir definējams”, tam tiek piešķirta nozīme, mums tas ir jāprecizē

  1. struktūra C (L) - kodēšanas struktūra L;
  2. konkrēta viena karte - kodēšanas karte L formulu kopai C (L) domēnā.

Tad, ja mēs identificējam Val (L) ar tā attēlu C (L) zem kodēšanas kartes, mēs interpretējam apgalvojumu “Val (L) ir definējams” kā paziņojumu “Val (L), kas tiek uzskatīts par C (L) domēns ir definējams C (L) ar formulas L palīdzību.”

Piemēram, ja L ir aritmētikas pirmās kārtas valoda L, Gēdels sākotnēji kā kodēšanas struktūru izmantoja aritmētikas standard standarta modeli un kā kodēšanas karti plaši pazīstamo funkciju, kas iegūta no dabisko skaitļu galvenās faktorizācijas teorēmas. Val (L) rekursīvā skaitīšana nozīmē tikai to, ka Val (L) locekļu kodu kopa (“Gödel skaitļi”) ir definējama ℕ ar L formulu ∃ y φ (x, y), kur φ (x, y) ir rekursīva formula.

Cita, ekvivalenta, aritmētikas pirmās kārtas valodas kodēšanas struktūra ir iedzimtā veidā ierobežoto kopu struktūra [5] ⟨H (∈), ∈ ⨡ H (ω) a, kur kopa x ir iedzimtībā ierobežota, ja x, tad tās locekļi, tās dalībnieku biedri utt., visi ir ierobežoti. Šajā kodēšanas struktūrā tiek ņemts vērā fakts, ka pirmās kārtas formulas dabiski tiek uzskatītas par ierobežotām kopām.

Pievēršoties gadījumam, kad L ir infinitārā valoda L (κ, λ), kāda šajā gadījumā būtu piemērota kodēšanas struktūra? Sākumā mēs atzīmējām, ka infinitārajām valodām tika piedāvāta iespēja domāt par formulām kā kopu teorētiskiem objektiem, tāpēc mēģināsim iegūt savu kodēšanas struktūru, domājot par to, kādiem kopu teorētiskiem objektiem mums vajadzētu būt infiniitālajām formulām. Ņemot vērā faktu, ka katrai φ∈ formai (κ, λ), φ un tā apakšformulas, apakšformas utt. Visi ir <κ, [6]mirkļa pārdomas atklāj, ka L (κ, λ) formulas “atbilst” x parastajām kardinalitātes kopām <κ tādā nozīmē, ka x, tās locekļi, locekļu locekļi utt. visi ir kardinālisma <κ. Visu šādu komplektu kolekcija ir uzrakstīta H (κ). H (ω) ir iedzimtībā ierobežoto kopu kolekcija, kas ieviesta iepriekš, un H (ω 1) ir visu iedzimtā veidā saskaitāmo kopu kolekcija.

Vienkāršības labad pieņemsim, ka pamatvalodas L vienīgais ekstraloģiskais simbols ir binārā predikāta simbols ∈ (diskusiju viegli izvērš līdz gadījumam, kad L satur papildu ekstraloģiskus simbolus). Iepriekš minēto piezīmju vadīti kā L (κ, λ) kodēšanas struktūra,

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

Tagad mēs varam definēt formas (κ, λ) kodēšanas karti H (κ). Pirmkārt, katram L (κ, λ) pamata simbolam mēs piešķiram koda objektu s H (κ) šādi. Ļaujiet {v ξ: ξ <κ} būt L (κ, λ) atsevišķo mainīgo uzskaitījums.

Simbols Koda objekts Apzīmējums
¬ 1 ¬
2
3
4
5
= 6 =
v ξ ⟨0, ξ⟩ v ξ

Pēc tam katrai φ ∈ formai (κ, λ) kodu objektam φ piešķiram rekursīvi šādi:

v ξ = v η = df v ξ , = , v η ⟩, v ξ ∈ v η = df v ξ , , v η ⟩;

φ, ψ ∈ formai (κ, λ),

φ ∧ I' = df φ , , I'

¬φ = df ¬ , φ

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

un, visbeidzot, ja Φ ⊆ veido (κ, λ) ar | Φ | <κ,

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

Karte ↦ φ φ no Form (κ, koeficientu l) pārnes H (κ) ir viegli redzams, ka viens-one and ir nepieciešama kodēšanas karte. Attiecīgi mēs piekrītam identificēt Val (L (κ, λ)) ar attēlu H (κ) zem šīs kodēšanas kartes.

Kad Val (L (κ, λ)) ir H (κ) definējama apakškopa? Lai atbildētu uz šo jautājumu, mums vajadzīgas šādas definīcijas.

L formulu sauc par Δ 0 - formulu, ja tā ir ekvivalenta formulai, kurā visi skaitļi ir formā ∀ x ∈ y vai ∃ x ∈ y (ti, ∀ x (x ∈ y →…) vai ∃ x (x ∈ y ∧…)). L formula ir Σ 1 - formula, ja tā ir ekvivalenta tai, kuru var veidot no atomu formulām un to negatīvām, izmantojot tikai loģiskos operatorus ∧, ∨, ∀ x ∈ y, ∃ x. A kopas X apakškopu X uzskata par Δ 0 (attiecīgi Σ 1) uz A, ja tas ir definējams struktūrā ⟨A, ∈ ⨡ A⟩ pēc Δ 0 - (attiecīgi Σ 1 -) formulas L.

Piemēram, ja mēs dabisko skaitļu kopu identificējam ar iedzimtā veidā ierobežoto kopu H (ω) parastajā veidā, tad katram X ⊆ H (ω) mums ir:

X ir Δ 0 uz H (ω) ⇔ X ir rekursīvs

X ir Σ 1 uz H (ω) ⇔ X ir rekursīvi uzskaitāms.

Tādējādi jēdzienus Δ 0 - un Σ 1 - var uzskatīt par attiecīgi rekursīvās un rekursīvi uzskaitāmās kopas jēdzienu vispārinājumiem.

L pabeigtības teorēma nozīmē, ka Val (L) - tiek uzskatīts par H (ω) apakškopu - ir rekursīvi uzskaitāms, un līdz ar to Σ 1 uz H (ω). Tāpat L (ω 1, ω) pilnīguma teorēma (sk. 2. paragrāfu) nozīmē, ka Val (L (ω 1, ω)) - kas tiek uzskatīts par H (ω 1) apakškopa - ir Σ 1 uz H (ω 1). Tomēr šis patīkamais stāvoklis pilnībā sabrūk, tiklīdz tiek sasniegts L (ω 1, ω 1). Jo viens var pierādīt

Skota nenoteiktības teorēma L (ω 1, ω 1). Val (L (ω 1, ω 1)) nav definējams H (ω 1) pat ar L (ω 1, ω 1) - formulu; tādējādi a fortiori Val (L (ω 1, ω 1)) nav Σ 1 uz H (ω 1).

Šī teorēma tiek pierādīta lielā mērā tāpat kā vispārzināmais rezultāts, ka aritmētikas L 2 otrās kārtas valodas derīgo teikumu (kodu) kopums nav otrās kārtas nosakāms tās kodēšanas struktūrā ℕ. Lai iegūtu šo pēdējo rezultātu, vispirms tiek novērots, ka ℕ ir raksturīga viena L 2 izjūta, un tad parāda, ka, ja rezultāts būtu nepatiess, L 2 izziņu “patiesība ℕ” būtu nosakāma ar L 2 -formula, tādējādi pārkāpjot Tarski teorēmu par patiesības nenoteiktību.

Attiecīgi, lai pierādītu Skota nenoteiktības teorēmu atbilstoši iepriekšminētajam, jānoskaidro:

(4.1) Kodēšanas struktūras H (ω 1) raksturojums L (ω 1, ω 1): ir L (ω 1, ω 1) -jūtība τ 0 tāda, ka visām L-struktūrām A, A ⊨ τ 0A ≅ H (ω 1).

(4.2) L (ω 1, ω 1) - teikumu patiesības nenoteiktība - teikumi kodēšanas struktūrā: L (ω 1, ω 1) -formula φ (v 0) nav tāds, ka visiem L (ω 1, ω 1) -sentences σ, H (ω 1) ⊨ σ↔φ ( σ ).

(4.3) L (ω 1, ω 1) ir tāds termins t (v 0, v 1), ka katram teikumu pārim σ, τ ir L (ω 1, ω 1), H (ω 1). ⊨ [t ( σ , τ ) = σ → τ ].

(4.1.) Tiek pierādīts, analizējot H (ω 1) kopuma teorētisko definīciju un parādot, ka to var “iekšēji” formulēt L (ω 1, ω 1). (4.2.) Ir izveidots tieši tāpat kā Tarski teorēma par patiesības nenoteiktību pirmās vai otrās kārtas valodās. (4.3) tiek iegūts, formalizējot definīciju kodēšanas kartes ↦ σ σ L (ω 1, omega 1).

Apbruņojoties ar šiem faktiem, Skota nenoteiktības teorēmu varam iegūt šādā veidā. Pieņemsim, ka tas bija nepatiesi; tad būtu tāda L (ω 1, ω 1) -formula θ (v 0), ka visām L (ω 1, ω 1) -jūtības σ,

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

Būtu τ 0 teikums, kas norādīts (4.1.). Tad mums visiem L (ω 1, ω 1) -punktiem ir σ,

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

lai līdz (4.4.)

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

Ja t ir termins, kas norādīts (4.3.), Tas izrietētu no tā

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

Tagad uzrakstiet φ (v 0) L (ω 1, ω 1) -formulai θ (t ( τ 0 , σ )). Tad

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

pretrunīgi (4.2.) un aizpildot pierādījumus.

Tādējādi Val (L (ω 1, ω 1)) nav definējams pat ar L (ω 1, ω 1) - formulu, tāpēc a fortiori L (ω 1, ω 1) ir nepilnīgs. Līdzīgi argumenti liecina, ka Skota nenoteiktības teorēma turpina pastāvēt, kad ω 1 tiek aizstāts ar jebkuru pēcteci kardinālu κ +; attiecīgi valodas L (κ +, κ +) ir nepilnīgas. [7]

5. L (ω 1, ω) apakšvalodas un Bārvesa kompakuma teorija

Ņemot vērā to, ko mēs tagad zinām par infinitārajām valodām, šķiet, ka L (ω 1, ω) ir vienīgais, kurš izturējās samērā labi. No otras puses, kompaktuma teorēmas nespēja vispārināt uz L (ω 1, ω) jebkādā lietderīgā veidā ir nopietns trūkums attiecībā uz lietojumiem. Mēģināsim sīkāk analizēt šo kļūmi.

No 4. paragrāfa atcerieties, ka pirmās kārtas valodas L formulas mēs varam kodēt kā iedzimtā veidā ierobežotas kopas, ti, kā H (ω) locekļus. Tādā gadījumā katrs ierobežotais L teikumu (kodu) kopums ir arī H (member) loceklis, un no tā izriet, ka kompakcijas teorēmu L var izteikt šādā formā:

(5.1) Ja Δ ⊆ Nosūtītie (L) ir tādi, ka katrai apakškopai Δ 0 ⊆ Δ, Δ 0 ∈ H (ω) ir modelis, tad tas ir Δ.

Tagad ir labi zināms, ka (5.1.) Ir vispārējās pilnīguma teorēmas L tiešas sekas, kas izteikta formā, kas līdzīga (5.1.) Formai, kļūst par apgalvojumu:

(5.2) Ja Δ ⊆ Nosūtītie (L) un σ ∈ Nosūtītie (L) apmierina Δ ⊨ σ, tad no Δ ir σ atskaitījums D, ka D ∈ H (ω). [8]

2. paragrāfā mēs atzīmējām, ka kompaktuma teorēma L (ω 1, ω) neizdodas ļoti spēcīgi; faktiski mēs izveidojām komplektu Γ ⊆ Nosūtītie1, ω) tā, lai

(5.3) Katrai coun saskaitāmai apakškopai ir modelis, bet Γ nav.

Atgādinām arī to, ka mēs ieviesām atskaitīšanas jēdzienu L (ω 1, ω); tā kā šādiem atskaitījumiem ir nosakāms garums, no (5.3) tas ātri izriet, ka

(5.4) Ir tāds teikums [9] σ ∈ Nosūtīts1, ω), ka Γ ⊨ σ, bet σ nav atņemts L (ω 1, ω) no Γ.

Tagad L (ω 1, ω) formulas var kodēt kā H (ω 1) locekļus, un ir skaidrs, ka H (ω 1) ir aizvērts, veidojot saskaitāmās apakškopas un secības. Attiecīgi (5.3. Un 5.4.) Var rakstīt:

(5.3. Bis) Katrs Γ 0 ⊆ Γ tāds, ka Γ 0 ∈ H (ω 1) ir modelis, bet Γ nav;

(5.4 bis) Ir tāds teikums σ ∈ Nosūtīts1, ω), ka Γ ⊨ σ, bet no σ nav σ atskaitījuma D ∈ H (ω 1).

No tā izriet, ka (5.1.) Un (5.2.) Sabojājas, ja “L” aizstāj ar “L (ω 1, ω)” un “H (ω)” ar “H (ω 1)”. Turklāt var parādīt, ka kopu ⊆ ⊆ Nosūtītās1, ω) (5.3. Bis) un (5.4. Bis) var uzskatīt par Σ 1 uz H (ω 1). Tādējādi kompakuma un vispārinātās pilnīguma teorēmas neizdodas pat L (-1, ω) -jutību Σ 1 -komplektiem.

No (5.4 bis) mēs redzam, ka iemesls, kāpēc vispārinātā pilnīguma teorēma neizdodas Σ 1- grupām L (ω 1, ω), ir tas, ka, rupji runājot, H (ω 1) nav “aizvērts”, veidojot atskaitījumus. no Σ 1 - teikumu kopas H (ω 1). Tātad, lai to labotu, šķiet dabiski H (ω 1) aizstāt ar kopām A, kuras savā ziņā ir slēgtas, veidojot šādus atskaitījumus, un tad ņemt vērā tikai tās formulas, kuru kodi ir A.

Tagad mēs sniedzam skici, kā to var izdarīt.

Pirmkārt, mēs identificējam simbolus un formulas L (ω 1, ω) ar to kodiem H (ω 1), tāpat kā 4. paragrāfā. Par katru saskaitāmu tranzīta [10] kopu A ļaujiet

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

Mēs sakām, ka L A ir L (ω 1, ω) apakšvaloda, ja ir izpildīti šādi nosacījumi:

  1. L ⊆ L A
  2. ja φ, ψ ∈ L A, tad φ ∧ ψ ∈ L A un ¬φ ∈ L A
  3. ja φ ∈ L A un x ∈ A, tad ∃ x φ ∈ L A
  4. ja φ (x) ∈ L A un y ∈ A, tad φ (y) ∈ L A
  5. ja φ ∈ L A, tad katrs φ apakšformula atrodas L A
  6. ja Φ ⊆ L un Φ ∈ A, un pēc ∧Φ ∈ L A.

Atskaitīšanas jēdziens L A ir definēts parastajā veidā; ja Δ ir noteikts teikumiem L A un φ ∈ L A, tad atvilkums φ no Δ L A ir atskaitīšana φ no Δ L (ω 1, ω) katrs formula no kuriem ir L A. Mēs sakām, ka φ ir deducible no Δ ar L A, ja ir atskaitīšana D no φ no Δ ar L A; šajos apstākļos mēs rakstām Δ ⊢ A φ. Kopumā D nebūs A loceklis; lai nodrošinātu, ka šāds atskaitījums ir atrodams A, būs nepieciešams noteikt papildu nosacījumus A.

Ļaujiet A būt saskaitāmai tranzīta kopai, lai L A būtu L (ω 1, ω) apakšvaloda un Δ būtu L A teikumu kopa. Mēs teikt, ka A (vai, ar ļaunprātīgu terminoloģiju, L) ir Δ- slēgts, ja kādu formulu φ no L A tāds, ka Δ ⊢ φ, ir atskaitīšana D no φ no Δ tāds, ka D ∈ A. Var parādīt, ka vienīgā skaitāmā valoda, kas Δ ir aizvērta patvaļīgai Δ, ir pirmās kārtas valoda L, ti, kad A = H (ω). Tomēr J. Barvejs atklāja, ka ir saskaitāmas kopas A ⊆ H (ω 1), kuru atbilstošās valodas L A atšķiras no L un tomēr Δ ir aizvērtas visām Σ 1- teikumu kopas Δ. Šādas kopas A sauc par pieļaujamajām kopām; rupji runājot, tie ir iedzimti ierobežoto kopu paplašinājumi, kuros joprojām ir iespējama rekursijas teorija un līdz ar to arī pierādījumu teorija (pilnīgu definīciju sk. 5.1. sadaļā).

Pēc Bārveja rezultāta uzreiz iegūst

Bārveja kompakuma teorēma. Ļaujiet A skaitāmai pieļaujamai kopai un Δ ir L A teikumu kopa, kas ir Σ 1 uz A. Ja katram Δ '⊆ Δ ir tāds, ka Δ' ∈ A ir modelis, tad tas pats notiek Δ.

“Σ 1” klātbūtne šeit norāda, ka šī teorēma ir kompakcijas teorēmas vispārinājums rekursīvi uzskaitāmiem teikumu kopumiem.

Vēl viena Barwise kompakuma teorēmas versija, kas ir noderīga kopu teorijas modeļu konstruēšanai, ir šāda. Ļaujiet ZFC būt parastam Zermelo-Fraenkel kopas teorijas aksiomu kopumam, ieskaitot izvēlētās aksiomas. Tad mums ir:

5.5. Teorēma. Ļaujiet A būt skaitāmai tranzīta kopai, kas A = ⟨A, ∈ ⨡ A⟩ ir ZFC paraugs. Ja Δ ir L A teikumu kopums, kas ir definējams A ar noteiktas teorijas valodas formulu, un ja katram Δ '⊆ Δ ir tāds, ka Δ' ∈ A ir modelis, tas pats notiek Δ.

Noslēgumā mēs sniedzam vienkāršu šīs teorēmas pielietojumu. Ļaujiet A = ⟨A, ∈ ⨡ A⟩ būt par ZFC modeli. Tiek teikts, ka ZFC paraugs B = ⟨B, E⟩ ir pareizs A gala pagarinājums, ja (i) AB, ii) AB, iii) a ∈ A, b ∈ B, bEa ⇒ b ∈ A. Tādējādi pareizs ZFC modeļa gala pagarinājums ir pareizs paplašinājums, kurā neviens “jauns” elements neatrodas “pirms” neviena “veca” elementa. Kā mūsu 5.5. Piemērošana tiek pierādīta

5.6. Teorēma. Katram ZFC tranzīta modelim ir pienācīgs gala pagarinājums.

Pierādījums. Ļaujiet A = ⟨A, ∈ ⨡ A⟩ būt par ZFC tranzīta modeli un ļaujiet L būt kopas teorijas pirmās kārtas valodai, ko papildina ar vārdu a katram a ∈ A, un ar papildu konstanti c. Ļaujiet, ka Δ ir L A- teicienu kopums, kas sastāv no:

  • visas ZFC aksiomas;
  • ca, katram a ∈ A;
  • ∀ x (x ∈ a → ∨ b ∈ a x = b), katram a ∈ A;
  • ab, katram a ∈ b ∈ A.

Ir viegli parādīt, ka Δ ir A apakškopa, kuru var definēt A ar noteiktas teorijas valodas formulu. Arī katrai apakškopai Δ '⊆ Δ jābūt tādai, lai Δ' ∈ A būtu modelis. Visu a ∈ A kopai, kurai a rodas Δ ', pieder A - jo Δ' tā ir - un tā, ja mēs interpretējam c kā jebkuru (obligāti bezjēdzīgas) kopas A - C locekli, tad A ir a Δ 'modelis. Attiecīgi (5.5.) Nozīmē, ka Δ ir modelis ⟨B, E⟩. Ja mēs interpretēt katru pastāvīgu A kā elements ir ∈ A, tad ⟨B, E⟩ ir pareizi beigu paplašinājums A. Pierādījums ir pilnīgs.

Lasītājs ātri redzēs, ka pirmās kārtas kompaktuma teorēma nedos šo rezultātu.

5.1. Pieļaujamās kopas jēdziena definīcija

Tiek uzskatīts, ka pārejošs komplekts A, kas nav viegls, ir pieņemams, ja ir izpildīti šādi nosacījumi:

  1. ja a, b ∈ A, tad {a, b} ∈ A un ∪ A ∈ A;
  2. ja ∈ A un X ⊆ A ir Δ 0 uz A, tad X ∩ ∈ A;
  3. ja a ∈ A, X ⊆ A ir Δ 0 uz A, un ∀ x ∈ ∃ y (<x, y> ∈ X), pēc tam, kādu b ∈ A, ∀ x ∈ ∃ y ∈ b (<x, y> ∈ X).

Ii) nosacījums - Δ 0 - atdalīšanas shēma - ir ierobežota Zermelo atdalīšanas aksiomas versija. Iii) nosacījumu - līdzīgi novājinātu aizstāšanas aksiomas versiju - var saukt par Δ 0 - aizstāšanas shēmu.

Diezgan viegli redzēt, ka, ja A ir tranzīta kopa tāda, ka <A, ∈ | A> ir ZFC paraugs, tad A ir pieļaujams. Vispārīgāk runājot, rezultāts turpina saglabāties, ja ZFC tiek izlaista jaudas iestatīšanas aksioma, lai būtu pieļaujami gan H (ω), gan H (ω 1). Tomēr, tā kā pēdējais nav uzskatāms, Barwise kompakuma teorēma uz to neattiecas.

6. Vēsturiskas un bibliogrāfiskas piezīmes

§ 1 un 2. Šķiet, ka bezgalīgās ierosināšanas un predikatīvās valodas pirmo reizi skaidri parādījušās drukātā veidā ar Skota un Tarski [1958] un Tarski [1958] rakstiem. L (ω 1, ω), kā arī citu infinitāro valodu pilnīguma teorēmu pierādīja Karps [1964]. Hanfa skaitļa aprēķinus L (ω 1, ω) vispirms veica Morlijs [1965]. Kārtības pasūtījumu nenoteiktību ierobežotajā skaitliskajā valodā pierādīja Karp [1965] un Lopez-Escobar [1966]. Interpolācijas teorēmu L (ω 1, ω) pierādīja Lopess-Eskobars [1965] un Skota izomorfisma teorēma L (ω 1, ω) - Skots [1965].

Karp daļēja izomorfisma teorēma pirmo reizi tika pierādīta Karpā [1965]; sk. arī Barwise [1973]. Rezultāts (2.2) parādās Chang [1968], rezultāts (2.3) Ellentuck [1976] un rezultāts (2.4) in Bell [1981].

§ 3. Rezultāti (3.2) un (3.3) ir saistīti ar Hanfu [1964], dažus precizējumus izdarījuši Lopess-Eskobars [1966] un Diksmans [1975], savukārt (3.4) pierādīja Tarskis. Rezultāts (3.5.) Ir saistīts ar Skotu [1961], (3.6) par Bellu [1970] un [1972]; un (3.7.) Bellam (1974). Izmērāmos kardinālus vispirms uzskatīja Ulams [1930] un Tarski [1939]. Fakts, ka izmērāmie kardināli ir vāji kompakti, tika atzīmēts Tarski [1962].

§ 4. Par L (ω 1, ω 1) nenoteicamības teorēmu. Karola Karpa piezīmes (1964, 166): “Starptautiskajā loģikas, metodoloģijas un zinātnes filozofijas kongresā Stenfordas universitātē 1960. gadā Dana Skota izplatīja izklāstu, kas apliecina pilnīgas definējamas formālās sistēmas neiespējamību (γ +, γ +) valodas ar vienādojumu divvietīgā predikatīvā simbolā papildus vienlīdzības simbolam.” Skots nekad nepublicēja savu rezultātu, un pilnīgi detalizēts pierādījums vispirms parādījās Karpā [1964]. Šeit izmantotā pieeja teorēmai ir balstīta uz Dickmann [1975] sniegto pārskatu.

§ 5. Sākotnējā motivācija rezultātiem, kas sniegti šajā sadaļā, nāca no Kreisel; savā [1965. gadā] viņš norādīja, ka nav pārliecinošu iemeslu, lai izvēlētos bezmācības formulas, pamatojoties tikai uz "garumu", un tā vietā ierosināja izmantot definējamības vai "slēgšanas" kritērijus. Kreisela ierosinājumu ar lieliem panākumiem pieņēma Barvejs [1967], kur tika pierādīta viņa kompaktuma teorēma. Pieļaujamās kopas jēdziens izriet no Platek [1966]. Teorēma (5.6.) Ir ņemta no Keislera [1974].

Papildu lasījumus par infinitārajām valodām skat. Aczel [1973], Dickmann [1975], Karp [1964], Keisler [1974] un Makkai [1977]. Noderīgs pārskats par saikni starp infinitārajām valodām un lieliem kardināliem atrodams Drake [1974] 10. nodaļā.

Bibliogrāfija

  • Aczel, P., 1973, “Infinitārā loģika un Barwise kompakcijas teorēma”, 1971. gada Bertrand Russell Memorial Logic Conference konferences materiāli (Uldum, Dānija), J. Bell, J. Cole, G. Priest un A. Slomson (red.).), Līdsa: Bertranda Rasela piemiņas loģikas konference, 234. – 277.
  • Bārvejs, J., 1967. gads, Infinitārā loģika un pieļaujamie komplekti. Ph. D. Promocijas darbs Stenfordas universitātē.
  • –––, 1973. gads, “Atpakaļ un pa priekšu caur bezgalības loģiku. Pētījumi modeļa teorijā”, matemātikas studijās (8. sējums), Bufalo: Amerikas matemātikas asociācija, 5. – 34. Lpp.
  • –––, 1975, pieļaujamie komplekti un konstrukcijas, Berlīne: Springer-Verlag.
  • Barwise, J. un S. Feferman (red.), 1985, Model-Theoretic Logics rokasgrāmata, Ņujorka: Springer-Verlag.
  • Baumgartner, J., 1974, “Hanfa numurs pilniem L ω 1, ω teikumiem (bez GCH)”, Journal of Symbolic Logic, 39: 575–578.
  • Bells, JL, 1970, “Vāja saderība ierobežotās otrās kārtas valodās”, Polijas Zinātņu akadēmijas biļetens, 18: 111–114.
  • –––, 1972. gads, “Par attiecībām starp vājo kompaktumu L ω 1, ω, L ω 1, ω 1 un ierobežotajām otrās kārtas valodām”, Matemātiskās loģikas arhīvs, 15: 74–78.
  • –––, 1974, “Par kompaktajiem kardināliem”, Zeitschrift für Mathematical Logik und Grundlagen der Mathematik, 20: 389–393.
  • –––, 1981, “S-topozīciju struktūru izomorfisms”, Journal of Symbolic Logic, 43 (3): 449–459.
  • Chang, CC, 1968. gads, “Dažas piezīmes par bezgalīgo valodu modeļa teoriju”. Infinitāro valodu sintaksē un semantikā (lekciju piezīmes matemātikā: 72. sējums), J. Barwise (red.), Springer-Verlag, Berlīne, 36. – 63.
  • Diksmans, MA, 1975, lielas infinitārās valodas, Amsterdama: Ziemeļholande.
  • Drake, FR, 1974, kopas teorija: Ievads lielajiem kardināliem, Amsterdama: Ziemeļholandes izdevniecības uzņēmums.
  • Ellentuck, E., 1976, “Kategoriskums atgūts”, Journal of Symbolic Logic, 41 (3): 639–643.
  • Hanfs, WP, 1964. gads. Valodu nepilnīgums ar bezgalīgi gariem izteicieniem, Amsterdama: Ziemeļholande.
  • Karp, C., 1964, Valodas ar bezgalīga garuma izteiksmēm, Amsterdama: Ziemeļholande.
  • –––, 1965, “Finite-Quantifier Equivalence” modeļu teorijā, J. Addison, L. Henkin un A. Tarski (red.), Amsterdam: North-Holland, 407–412.
  • Keislers, HJ, 1974. gads, Infinitīvās loģikas modeļa teorija, Amsterdama: Ziemeļholande.
  • Keislers, HJ, un Jūlija F. Knita, 2004. gads, “Barvīds: bezgalīgā loģika un pieļaujamie komplekti”, Symbolic Logic žurnāls, 10. (1): 4–36
  • Kolaitis, P. un M. Vardi, 1992, “Fiksētā punkta loģika pret bezgalīgo loģiku ierobežotā modeļa teorijā”, IEEE septītā ikgadējā datorikas loģikas simpozija (LICS '92) raksti, IEEE, 46.-57. Lpp.; pieejams tiešsaistē, doi: 10.1109 / LICS.1992.185518
  • Kreisel, G., 1965, “Modeļa teorētiskie invarianti, pielietojumi rekursīvām un hiperaritmētiskām operācijām”, modeļu teorijā, Dž. Adisons, L. Henkins un A. Tarski (red.), Amsterdama: Ziemeļholande, 190-205.
  • Kueker, D., 1975, “Atpakaļ un atpakaļ argumenti infinitārajās valodās”, Infinitary Logic: In Memoriam Carol Karp (Lekciju piezīmes matemātikā: 492. sējums), D. Kueker (red.), Berlīne: Springer-Verlag.
  • Lopess-Eskobars, EGK, 1965. gads, “Interpolācijas teorēma bezgalīgi ilgiem teikumiem”, Fundamenta Mathematicae, 57: 253–272.
  • –––, 1966. gads, “Par kārtības noteikšanu”, Fundamenta Mathematicae, 59: 13–21.
  • Makkai, M., 1977, “Pieļaujamie komplekti un bezgalīgā loģika”, Matemātiskās loģikas rokasgrāmata, J. Bārvejs (red.), Amsterdama: Ziemeļholande, 233. – 282.
  • Morley, M., 1965, “Izlaižot elementu klases”, modeļu teorija, J. Addison, L. Henkin un A. Tarski (red.), Amsterdam: North-Holland, 265–273.
  • Nadels, M. 1985, “L ω 1, ω un pieļaujamie fragmenti”, J. Barwise un S. Feferman (red.) 1985, 271. – 287.
  • Platek, R., 1966, Rekursijas teorijas pamati, Ph. D. Promocijas darbs Stenfordas universitātē.
  • Skots, D., 1961. gads, “Izmērāmi kardināli un konstruktīvi komplekti”, Polijas Zinātņu akadēmijas biļetens, 9: 521–524.
  • ––– 1965, “Loģika ar kvantitatīvi garu formulu un ierobežotām skaitļu virknēm”, modeļu teorija, Dž. Adisons, L. Henkins un A. Tarski (red.), Amsterdama: Ziemeļholande, 329–341.
  • Skots, D. un A. Tarski, 1958. gads, “Sententais aprēķins ar bezgala gariem izteicieniem”, Colloquium Mathematicum, 16: 166–170.
  • Šīla, Saharona, 2012. gads, “Jaukā infinitārā loģika”, American Mathematical Society žurnāls, 25: 395-427, pieejams tiešsaistē, 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. gads, “Piezīmes par predikātu loģiku ar bezgala gariem izteicieniem”, Colloquium Mathematicum, 16: 171–176.
  • –––, 1962, “Dažas problēmas un rezultāti, kas attiecas uz kopu teorijas pamatiem”, E, Nagel, P. Suppes un A. Tarski (red.), Logic, Science and Science Philosophy, Stanford: Stanford University Press, 123-135.
  • Ulam, S., 1930, “Zur Masstheorie in der algemeinen Mengenlehre”, Fundamenta Mathematicae, 16: 140–150.

Akadēmiskie rīki

sep cilvēks ikona
sep cilvēks ikona
Kā citēt šo ierakstu.
sep cilvēks ikona
sep cilvēks ikona
Priekšskatiet šī ieraksta PDF versiju vietnē SEP Friends.
inpho ikona
inpho ikona
Uzmeklējiet šo ierakstu tēmu interneta filozofijas ontoloģijas projektā (InPhO).
phil papīru ikona
phil papīru ikona
Uzlabota šī ieraksta bibliogrāfija vietnē PhilPapers ar saitēm uz tā datu bāzi.

Citi interneta resursi

Ieteicams: