Oneindige Logica

2023 Auteur: Noah Black | [email protected]. Laatst gewijzigd: 2023-11-26 16:11

Toegang navigatie

• Inhoud van het item
• Bibliografie
• Academische hulpmiddelen
• Vrienden PDF-voorbeeld
• Info over auteur en citaat
• Terug naar boven

Oneindige logica

Voor het eerst gepubliceerd zo 23 jan. 2000; inhoudelijke herziening vr 26 feb 2016

Traditioneel worden uitdrukkingen in formele systemen beschouwd als aanduidingen van eindige inscripties die - althans in principe - in staat zijn om daadwerkelijk in primitieve notatie te worden uitgeschreven. Het feit dat (eerste-orde) formules kunnen worden geïdentificeerd met natuurlijke getallen (via "Gödel-nummering") en dus met eindige verzamelingen, maakt het niet langer nodig om formules als inscripties te beschouwen, en suggereert de mogelijkheid om "talen" te vormen waarvan de formules van nature zouden worden geïdentificeerd als oneindige verzamelingen. Een dergelijke "taal" wordt een oneindige taal genoemd: in dit artikel bespreek ik die oneindige talen die op een eenvoudige manier kunnen worden verkregen uit eerste-orde talen door conjuncties, disjuncties en, mogelijkerwijs, kwantificatiereeksen oneindig te laten zijn lengte. In de loop van de discussie zal blijken dat, hoewel de uitdrukkingskracht van dergelijke talen veel groter is dan die van hun finitaire (eerste-orde) tegenhangers, er maar weinigen de "aantrekkelijke" kenmerken bezitten (bijv. Compactheid en volledigheid) van het laatste. Daarom verdienen de oneindige talen die deze kenmerken wel bezitten, speciale aandacht.

In §1 zijn de basissyntaxis en semantiek van oneindige talen vastgelegd; hun expressieve kracht wordt dan weergegeven door middel van voorbeelden. §2 is gewijd aan die oneindige talen die alleen eindige kwantificatiereeksen toestaan: deze talen blijken relatief braaf te zijn. §3 is gewijd aan een bespreking van het compactheidsprobleem voor oneindige talen en het verband ervan met puur set-theoretische vragen over "grote" kardinale getallen. In §4 wordt een argument geschetst dat aantoont dat de meeste "oneindige kwantificatietalen" talen van de tweede orde zijn en ipso facto zeer onvolledig zijn. §5 geeft een beknopt overzicht van een bepaalde speciale klasse van subtalen van oneindige talen waarvoor een bevredigende veralgemening van de compactheidsstelling kan worden bewezen. Deze sectie bevat een onderafdeling over de definitie van toegestane sets. Historische en bibliografische opmerkingen worden gegeven in §6.

• 1. Definitie en basiseigenschappen van oneindige talen
• 2. Eindig-kwantificatietalen
• 3. De eigenschap Compactheid
• 4. Onvolledigheid van oneindig-kwantificatietalen

• 5. Subtalen van L (ω ₁, ω) en de stelling van de compactheid van Barwise

  5.1 Definitie van het concept van toelaatbare reeks

• 6. Historische en bibliografische opmerkingen
• Bibliografie
• Academische hulpmiddelen
• Andere internetbronnen
• Gerelateerde vermeldingen

1. Definitie en basiseigenschappen van oneindige talen

Gegeven een paar κ, λ van oneindige kardinalen zodat λ ≤ κ, definiëren we een klasse van oneindige talen waarin we conjuncties en disjuncties kunnen vormen van sets van kardinaliteitsformules <κ, en kwantificaties over reeksen variabelen van lengte < λ.

Laat L - de (finitaire) basistaal - een willekeurige maar vaste eerste-orde taal zijn met een willekeurig aantal extralogische symbolen. De oneindige taal L (κ, λ) heeft de volgende basissymbolen:

• Alle symbolen van L
• Een set Var van individuele variabelen, waarbij de kardinaliteit van Var (geschreven: | Var |) κ is
• Een logische operator ∧ (oneindige conjunctie)

De klasse van preformules van L (κ, λ) wordt recursief als volgt gedefinieerd:

• Elke formule van L is een preformula;
• als φ en ψ preformules zijn, dan zijn φ∧ψ en ¬φ;
• als Φ een verzameling preformules is zodat | Φ | <κ, dan is ∧Φ een preformula;
• als φ een preformule is en X ⊆ Var is zodanig dat | X | <λ, dan is ∃ X φ een preformula;
• alle preformules worden gedefinieerd door de bovenstaande clausules.

Als Φ een set preformules is geïndexeerd door een set I, zeg Φ = {φ _i: i ∈ I}, dan spreken we af ∧Φ te schrijven voor:

∧ _{ik ∈ ik}  φ

of, als ik de verzameling natuurlijke getallen is, schrijven we ∧Φ voor:

φ ₀ ∧ φ ₁ ∧…

Als X een set van individuele variabelen is, geïndexeerd door een ordinale α, zeg X = {x _ξ: ξ <α}, spreken we af (∃ x _ξ) _{ξ <α} φ te schrijven voor ∃ X φ.

De logische operatoren ∨, →, ↔ worden op de gebruikelijke manier gedefinieerd. We introduceren ook de operatoren ∨ (oneindige disjunctie) en ∀ (universele kwantificering) door

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

∀Xφ = _df ¬∃X¬φ,

en gebruik vergelijkbare conventies als voor ∧, ∃.

L (κ, λ) is dus de oneindige taal die wordt verkregen uit L door conjuncties en disjuncties met lengte <κ en kwantificaties ^[1] met lengte <λ toe te staan. Talen L (κ, ω) worden eindige-kwantificatietalen genoemd, de overige talen met oneindige kwantificering. Merk op dat L (ω, ω) gewoon L zelf is.

Let op de volgende afwijking die in een oneindige taal kan voorkomen, maar niet in een eindige taal. In de taal L (ω ₁, ω), die oneindig veel conjuncties mogelijk maakt, maar alleen eindige kwantificeringen, zijn er preformules met zoveel vrije variabelen dat ze niet kunnen worden "gesloten" tot zinnen van L (ω ₁, ω) door voorvoegsels te kwantificeren. Dat is bijvoorbeeld het geval voor de L (ω ₁, ω) -preformule

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

waar L het binaire relatiesymbool <bevat. Daarom maken we het volgende

Definitie. Een formule van L (κ, λ) is een preformule die <λ vrije variabelen bevat. De set van alle formules van L (κ, λ) wordt aangeduid met Form (L (κ, λ)) of gewoon Form (κ, λ) en de set van alle zinnen met Sent (L (κ, λ)) of gewoon verzonden (κ, λ).

Merk in dit verband op dat er in het algemeen niets gewonnen zou worden door "talen" L (κ, λ) te beschouwen met λ> κ. In de "taal" L (ω, ω ₁) zullen formules bijvoorbeeld slechts eindig veel vrije variabelen bevatten, terwijl er een groot aantal "nutteloze" kwantificatoren zijn die oneindig veel vrije variabelen kunnen binden. ^[2]

Nadat we de syntaxis van L (κ, λ) hebben gedefinieerd, schetsen we vervolgens de semantiek ervan. Aangezien de extralogische symbolen van L (κ, λ) alleen die van L zijn, en het zijn deze symbolen die de vorm bepalen van de structuren waarin een bepaalde eerste-orde taal moet worden geïnterpreteerd, is het natuurlijk om een L (κ, λ) -structuur om gewoon een L-structuur te zijn. Het idee van een formule van L (κ, λ) waaraan wordt voldaan in een L-structuur A (door een reeks elementen uit het domein van A) wordt op dezelfde inductieve manier gedefinieerd als voor formules van L, behalve dat we er twee moeten optellen extra clausules die overeenkomen met de clausules voor ∧Φ en ∃Xφ in de definitie van preformula. In deze twee gevallen definiëren we natuurlijk:

∧Φ is voldaan in A (door een gegeven reeks) ⇔ voor alle φ ∈ Φ, φ is voldaan in A (door de reeks);

∃ X φ wordt voldaan in een ⇔ er een opeenvolging van elementen uit het domein van A in overeenstemming met bijectieve X die voldoet cp in A.

Deze informele definities moeten worden aangescherpt in een rigoureuze ontwikkeling, maar hun betekenis moet duidelijk zijn voor de lezer. Nu komen de gebruikelijke noties van waarheid, validiteit, tevredenheid en model voor formules en zinnen van L (κ, λ) beschikbaar. In het bijzonder, als A een L-structuur is en σ ∈ Sent (κ, λ), zullen we A ⊨ σ schrijven voor A is een model van σ, en ⊨ σ voor σ is geldig, dat wil zeggen voor alle A, A Σ σ. Als Δ ⊆ Verzonden (κ, λ), zullen we Δ ⊨ σ schrijven omdat σ een logisch gevolg is van Δ, dat wil zeggen dat elk model van Δ een model van σ is.

We geven nu enkele voorbeelden die bedoeld zijn om de expressieve kracht van de oneindige talen L (κ, λ) met κ ≥ ω _{1 weer te geven}. Het is in ieder geval bekend dat het begrip in kwestie niet in een eerste-orde taal kan worden uitgedrukt.

Karakterisering van het standaard rekenmodel in L (ω ₁, ω). Hier is het standaard rekenmodel de structuur N = ⟨N, +, ·, s, 0⟩, waarbij N de verzameling natuurlijke getallen is, +, · en 0 hebben hun gebruikelijke betekenis en s is de opvolger. Zij L de eerste orde talen geschikt is voor N. Dan valt de klasse van L-structuren isomorf naar N samen met de klasse van modellen van de samenstand van de volgende L (ω ₁, ω) zinnen (waarbij 0 een naam is van 0):

∧ _{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

De termen s ⁿ x worden recursief gedefinieerd door

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

Karakterisering van de klasse van alle eindige verzamelingen in L (ω ₁, ω). Hier heeft de basistaal geen extralogische symbolen. De klasse van alle eindige verzamelingen valt dan samen met de klasse van modellen van de L (ω ₁, ω) -zin

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

Waarheidsdefinitie in L (ω ₁, ω) voor een telbare basistaal L. Laat L een telbare eerste-orde taal zijn (bijvoorbeeld de taal van de rekenkunde of verzamelingenleer) die een naam n bevat voor elk natuurlijk getal n, en laat σ ₀, σ ₁, … een opsomming zijn van zijn zinnen. Dan de L (ω ₁, ω) -formule

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

is een waar predikaat voor L, aangezien de zin

Tr (n) ↔ σ _n

is geldig voor elke n.

Karakterisering van goed-ordeningen in L (ω ₁, ω ₁). De basistaal L bevat hier een binair predikaatsymbool ≤. Laat σ ₁ de gebruikelijke L-zin zijn die lineaire ordeningen kenmerkt. Dan valt de klasse van L-structuren waarin de interpretatie van ≤ een goed-ordening is samen met de klasse van modellen van de L (ω ₁, ω ₁) zin σ = σ ₁ ∧ σ ₂, waarbij

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

Merk op dat de zin σ ₂ een oneindige kwantor bevat: het drukt de in wezen tweede-orde-bewering uit dat elke telbare subset een kleinste lid heeft. In feite kan worden aangetoond dat de aanwezigheid van deze oneindige kwantor essentieel is: de klasse van goed geordende structuren kan niet worden gekarakteriseerd in een eindige-kwantificatietaal. Dit voorbeeld geeft aan dat talen met een oneindige kwantificator zoals L (ω ₁, ω ₁) zich gedragen als talen van de tweede orde; we zullen zien dat ze de gebreken van de laatste delen (onvolledigheid) delen, evenals enkele van hun voordelen (sterk expressief vermogen).

Veel uitbreidingen van eerste-orde talen kunnen worden vertaald in oneindige talen. Beschouw bijvoorbeeld de gegeneraliseerde kwantificatietaal L (Q ₀) verkregen uit L door een nieuw kwantiseringssymbool Q ₀ toe te voegen en Q ₀ x φ (x) te interpreteren, aangezien er oneindig veel x zijn zodat φ (x). Het is gemakkelijk te zien dat de zin Q ₀ x φ (x) dezelfde modellen heeft als de L (ω ₁, ω) zin

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

Dus L (Q ₀) is in natuurlijke zin vertaalbaar in L (ω ₁, ω). Een andere taal die in deze zin in L (ω ₁, ω) kan worden vertaald, is de zwakke tweede-orde taal die wordt verkregen door een telbare reeks monadische predicaatvariabelen aan L toe te voegen, die vervolgens worden geïnterpreteerd als variërend over alle eindige groepen individuen.

Talen met willekeurig lange conjuncties, disjuncties en (mogelijk) kwantificaties kunnen ook worden geïntroduceerd. Voor een vaste oneindige kardinaal λ wordt de taal L (∞, λ) gedefinieerd door de klasse van formules, Form (∞, λ), te specificeren om de unie te zijn, over alle κ ≥ λ, van de sets Form (κ, λ)). Dus L (∞, λ) staat willekeurig lange conjuncties en disjuncties toe, in de zin dat als Φ een willekeurige subset van vorm is (∞, λ), dan zijn zowel ∧Φ als members leden van vorm (∞, λ). Maar L (∞, λ) laat alleen kwantificaties van lengte <λ toe: al zijn formules hebben <λ vrije variabelen. De taal L (∞, ∞) wordt op zijn beurt gedefinieerd door het specificeren van de klasse van formules, Form (∞, ∞), om de vereniging te zijn, over alle oneindige kardinalen λ, van de klassen Vorm (∞, λ). Dus L (∞, ∞) staat willekeurig lange kwantificaties toe naast willekeurig lange conjuncties en disjuncties. Merk op dat vorm (∞, λ) en vorm (∞, ∞) goede klassen zijn in de zin van Gödel-Bernays verzamelingenleer. Tevredenheid van formules van L (∞, λ) en L (∞, ∞) in een structuur kan worden gedefinieerd door een duidelijke uitbreiding van het corresponderende begrip voor L (κ, λ).

2. Eindig-kwantificatietalen

We hebben opgemerkt dat talen met oneindige kwantificering zoals L (ω ₁, ω ₁) op talen van de tweede orde lijken, aangezien ze kwantificering mogelijk maken over oneindige groepen individuen. Het feit dat dit in eindige-kwantificatietalen niet is toegestaan, suggereert dat deze in bepaalde opzichten dichter bij hun tegenhangers van de eerste orde liggen dan op het eerste gezicht duidelijk zou kunnen zijn. We zullen zien dat dit inderdaad het geval is, met name in het geval van L (ω ₁, ω).

De taal L (ω ₁, ω) neemt een speciale plaats in onder de oneindige talen omdat het, net als eerste-orde talen, een effectief deductief apparaat toelaat. Laten we in feite het nieuwe axioma-schema toevoegen aan de gebruikelijke eerste-orde axioma's en inferentieregels

∧Φ → φ

voor elke telbare set Φ ⊆ Vorm (ω ₁, ω) en elke φ ∈ Φ, samen met de nieuwe gevolgtregel

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

∧ n ∈ω φ n

en staat toe dat inhoudingen van telbare lengte zijn. ⊢ * schrijven voor afleidbaarheid in deze zin, dan hebben we de

L (ω ₁, ω) - Stelling van volledigheid. Voor elke σ ∈ Verzonden (ω ₁, ω), ⊨ σ ⇔ ⊢ * σ

Als een onmiddellijk gevolgtrekking leiden we af dat dit deductieve apparaat geschikt is voor inhoudingen op telbare verzamelingen gebouwen in L (ω ₁, ω). Dat wil zeggen, met de voor de hand liggende uitbreiding van notatie, hebben we voor elke telbare set Δ ⊆ Sent (ω ₁, ω)

(2.1) Δ ⊨ σ ⇔ Δ⊢ * σ

Deze volledigheidsstelling kan worden bewezen door het gebruikelijke Henkin-volledigheidsbewijs voor eerste-orde logica te wijzigen of door booleaans-algebraïsche methoden te gebruiken. Soortgelijke argumenten, toegepast op geschikte verdere vergrotingen van de axioma's en inferentieregels, leveren analoge volledigheidsstellingen op voor vele andere eindig-kwantificerende talen.

Als alleen aftrekposten van telbare lengte zijn toegestaan, kan er geen aftrekapparaat voor L (ω ₁, ω) worden opgezet dat geschikt is voor aftrek van willekeurige verzamelingen gebouwen, dat wil zeggen waarvoor (2.1) zou gelden voor elke verzameling Δ ⊆ Verzonden (ω ₁, ω), ongeacht de kardinaliteit. Dit volgt uit de simpele observatie dat er een eerste-orde taal L is en een ontelbare set Γ van L (ω ₁, ω) -zintuigen zodat Γ geen model heeft maar elke telbare subset van Γ wel. Om dit te zien, laat L de taal van rekenkunde zijn, vermeerderd met ω ₁ nieuwe constante symbolen { c _ξ: ξ <ω ₁ } en laat Γ de verzameling van L (ω ₁, ω) -zinnen zijn {σ} ∪ { c_ξ ≠ c _η: ξ ≠ η}, waarbij σ de L (ω ₁, ω) zin is die het standaard rekenmodel kenmerkt. Dit voorbeeld laat ook zien dat de compactheidsstelling niet werkt voor L (ω ₁, ω) en dus ook voor elke L (κ, λ) met κ ≥ ω ₁.

Een ander resultaat dat geldt in het eerste-orde-geval maar faalt voor L (κ, ω) met κ ≥ ω ₁ (en ook voor L (ω ₁, ω ₁), hoewel dit moeilijker te bewijzen is), is de prenex normale vorm stelling. Een zin is voorafgegaan als al zijn kwantoren vooraan staan; we geven een voorbeeld van een L (ω ₁, ω) zin die niet gelijk is aan een samenvoeging van pre-ex zinnen. Laat L de eerste-orde taal zijn zonder extralogische symbolen en laat σ de L (ω ₁, ω) zin zijn die de klasse van eindige verzamelingen kenmerkt. Stel dat σ gelijk was aan een conjunctie

∧ _{ik ∈ ik} σ _ik

van prenex L (ω ₁, ω) -gevoelens σ _i. Dan heeft elke σ _i de vorm

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

waarbij elke Q _k ∀ of ∃ is en φ _i een (mogelijk oneindige) conjunctie of disjunctie is van formules met de vorm x _k = x _l of x _k ≠ x _l. Omdat elke σ _i een zin is, zijn er slechts eindig veel variabelen in elke φ _i, en het is gemakkelijk om te zien dat elke φ _i dan equivalent is aan een eerste-ordeformule. Dienovereenkomstig kan elke σ _i worden beschouwd als een eerste-orde-zin. Aangezien wordt aangenomen dat σ equivalent is aan de conjunctie van σ _i, volgt hieruit dat σ en de verzameling Δ = {σ _i: i ∈ I} heb dezelfde modellen. Maar uiteraard hebben σ, en dus ook Δ, modellen van alle eindige kardinaliteiten; de compactheidsstelling voor sets van eerste-orde zinnen impliceert nu dat Δ, en dus ook σ, een oneindig model heeft, wat in tegenspraak is met de definitie van σ.

Wat betreft de stelling van Löwenheim-Skolem, vinden we dat de neerwaartse versie voldoende generalisaties heeft naar L (ω ₁, ω) (en inderdaad naar alle oneindige talen). In feite kan men op vrijwel dezelfde manier aantonen als voor sets van zinnen van de eerste orde dat als Δ ⊆ Verzonden (ω ₁, ω) een oneindig model van kardinaliteit ≥ | Δ | heeft, het een model van kardinaliteit heeft, het grootste van ℵ ₀, | Δ |. In het bijzonder heeft elke L (ω ₁, ω) zin met een oneindig model een telbaar model.

Aan de andere kant faalt de opwaartse stelling van Löwenheim-Skolem in zijn gebruikelijke vorm voor alle oneindige talen. De L (ω ₁, ω) zin die het standaard rekenmodel kenmerkt, heeft bijvoorbeeld een kardinaliteitsmodel ℵ ₀ maar geen modellen van enige andere kardinaliteit. Zoals we zullen zien, is hier echter niet alles verloren.

We definiëren het Hanf-nummer h (L) van een taal L als de minst kardinale κ zodat, als een L- zin een kardinaliteitsmodel heeft, het modellen heeft met een willekeurig grote kardinaliteit. Het bestaan van h (L) is gemakkelijk vast te stellen. Voor elke L- zin σ die geen modellen met een willekeurig grote kardinaliteit bezit, moet κ (σ) de kleinste kardinale κ zijn, zodat σ geen kardinaliteitsmodel heeft κ. Als λ het supremum is van alle κ (σ), dan, als een zin van L een model van kardinaliteit λ heeft, heeft het modellen van willekeurig grote kardinaliteit.

Definieer de kardinalen μ (α) recursief door

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

Dan kan dat worden aangetoond

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

vergelijkbare resultaten voor andere eindige kwantificatietalen. De waarden van de Hanf-getallen van oneindig-kwantificatietalen zoals L (ω ₁, ω ₁) zijn gevoelig voor het al dan niet aanwezig zijn van grote kardinalen, maar moeten in ieder geval die van L (ω ₁, ω) ruim overschrijden.

Een resultaat voor L dat generaliseert naar L (ω ₁, ω) maar naar geen andere oneindige taal is de

Craig Interpolation Theorem: Als σ, τ ∈ Sent (ω ₁, ω) zodanig zijn dat ⊨ σ → τ, dan is er θ ∈ Sent (ω ₁, ω) zodanig dat ⊨ σ → θ en ⊨ θ → τ, en elk extralogisch symbool dat voorkomt in θ komt voor in zowel σ als τ.

Het bewijs is een redelijk eenvoudige uitbreiding van de eerste bestelling.

Ten slotte noemen we nog een resultaat dat mooi generaliseert naar L (ω ₁, ω) maar naar geen andere oneindige taal. Het is bekend dat, als A een eindige L-structuur is met slechts eindig veel relaties, er een L-zin σ is die A kenmerkt tot isomorfisme. Voor L (ω ₁, ω) hebben we de volgende generalisatie bekend als

De stelling van Isomorfisme van Scott. Als A een telbaar L-structuur met slechts aftelbaar vele relaties, dan is er een L (ω ₁, ω) -sentence wier specifieke modellen van telbare samenvalt met de klasse van L-structuren isomorf met A.

De beperking tot telbare structuren is essentieel omdat telbaarheid in het algemeen niet kan worden uitgedrukt door een L (ω ₁, ω) zin.

De taal L (∞, ω) kan ook worden geteld als een eindige kwantificatietaal. Het concept van gelijkwaardigheid van structuren met betrekking tot deze taal is van bijzonder belang: we noemen twee (vergelijkbare) structuren A en B (∞, ω) - equivalent, geschreven A ≡ _∞ω B, als dezelfde zinnen van L (∞, ω) houden in zowel A en B. Deze relatie kan allereerst worden gekarakteriseerd in termen van het begrip partieel isomorfisme. Een gedeeltelijk isomorfisme tussen A en B is een niet-lege familie P van kaarten zodat:

• Voor elke p ∈ P is dom (p) een substructuur van A, is ran (p) een substructuur van B en is p een isomorfisme van zijn domein op zijn bereik; en
• Als p ∈ P, a ∈ A, b ∈ B, dan zijn er r, s ∈ P die beide p uitbreiden zodat a ∈ dom (r), b ∈ liep (s) (eigenschap "heen en weer").

Wanneer een partiële isomorfisme bestaat tussen A en B, zeggen we dat A en B gedeeltelijk isomorf en schrijven A ≅ _p B. We hebben dan

Karp's partiële isomorfismestelling.

Voor soortgelijke structuren A, B, A ≡ _∞ω B ⇔ A ≅ _p B.

Er is ook een versie van Scott's isomorfismestelling voor L (∞, ω), namelijk:

(2.2) Gegeven elke structuur A, is er een L (∞, ω) -zin σ zodanig dat, voor alle structuren B, A ≅ _p B ⇔ B ⊨ σ.

Gedeeltelijk isomorfisme en (∞, ω) -equivalentie zijn gerelateerd aan het begrip Booleaans isomorfisme. Om dit te definiëren moeten we het idee introduceren van een Booleaans gewaardeerd model van verzamelingenleer. Gegeven een complete Booleaanse algebra B, wordt het universum V ^(B) van B-gewaardeerde verzamelingen, ook wel bekend als de B-extensie van het universum V van verzamelingen, verkregen door eerst recursief te definiëren op α,

V _α ^(B) = {x: x is een functie ∧ bereik (x) ⊆ B ∧ ∃ξ <α [domein (x) ⊆ V _ξ ^(B)]}

en dan instellen

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

Leden van V ^(B) worden B-gewaardeerde sets genoemd. Het is nu gemakkelijk te zien dat een B-gewaardeerde set precies een B-gewaardeerde functie is met domein een set B-gewaardeerde sets. Laat L nu de eerste-orde taal van de verzamelingenleer zijn en laat L ^(B) de taal zijn die wordt verkregen door aan L een naam toe te voegen voor elk element van V ^(B) (we zullen hetzelfde symbool gebruiken voor het element en zijn naam). Men kan nu een afbeelding [·] ^(B) van de (zinnen van de) taal L ^(B) in B construeren: voor elke zin σ van L ^(B) is het element [σ] ^(B) van B het “Booleaanse waarheidswaarde”van σ in V ^(B). Deze afbeelding [·] ^(B) is gedefinieerd om alle stellingen van Zermelo-Fraenkel verzamelingenleer naar het bovenste element 1 van B te sturen, dat wil zeggen naar "waarheid"; dienovereenkomstig kan V ^(B) worden beschouwd als een Booleaans gewaardeerd model van verzamelingenleer. Als [σ] ^(B) = 1 zeggen we dat σ geldig is in V ^(B) en schrijven we V ^(B) ⊨ σ.

Nu heeft elke x ∈ V een canonieke representant x in V ^(B), bevredigend

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

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

We zeggen dat twee soortgelijke structuren A, B zijn Boolean isomorf, geschreven A ≅ _b B, dan als we compleet Boolean algebra B, hebben we V ^(B) ⊨ A ≅ B, dat wil zeggen, als er een Boolean uitbreiding van de universum van verzamelingen waarin de canonieke vertegenwoordigers van A en B isomorf zijn met Booleaanse waarde 1. Er kan dan worden aangetoond dat:

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

Dit resultaat kan worden versterkt door categorietheoretische formulering. Hiervoor hebben we het concept van een (n) (elementaire) topos nodig. Om dit concept te introduceren, beginnen we met de familiecategorie Set of sets and mappings. Set heeft de volgende sleuteleigenschappen:

1. Er is een "terminal" -object 1 zodat er voor elk object X een unieke kaart X → 1 is (voor 1 kunnen we elke set met één element nemen, in het bijzonder {0}).
2. Elk paar objecten X, Y heeft een Cartesiaans product X × Y.
3. voor elk paar objecten kan men het "exponentiële" object Y ^X van alle kaarten van X → Y vormen.
4. Er is een "waarheidswaarde" -object Ω zodat er voor elk object X een natuurlijke overeenkomst is tussen subobjecten (subsets) van X en kaarten X → Ω. (Voor Ω kunnen we de set 2 = {0,1} nemen; kaarten X → Ω zijn dan karakteristieke functies op X.)

Alle vier deze voorwaarden kunnen worden geformuleerd in categorietheoretische taal - een categorie die daaraan voldoet, wordt een topos genoemd. De categorie Set is een topos; zo zijn ook (i) de categorie Set ^(B) van Booleaans gewaardeerde sets en toewijzingen in elke Booleaanse extensie V ^(B) van het universum van sets; (ii) de categorie schoven sets op een topologische ruimte; (iii) de categorie van alle diagrammen van kaarten van sets

X ₀ → X ₁ → X ₂ → …

De objecten van elk van deze categorieën kunnen worden beschouwd als verzamelingen die op de een of andere manier variëren: in geval (i) over een Booleaanse algebra; in het geval (ii) boven een topologische ruimte; in het geval (iii) over (discrete) tijd. Een topos kan dan worden opgevat als een universum van "variabele" sets. De bekende categorie Set is het speciale beperkende geval van een topos waarin de "variatie" van de objecten tot nul is teruggebracht.

Net als in de verzamelingenleer kunnen "logische operatoren" worden gedefinieerd op het waarheidswaarde-object in elke topos. Dit zijn kaarten ¬: Ω → Ω; ∧, ∨, ⇒: Ω × Ω → Ω die overeenkomen met de logische bewerkingen van negatie, conjunctie, disjunctie en implicatie. Met deze bewerkingen wordt Ω een Heyting-algebra, en belichaamt dus in het algemeen de wetten niet van klassieke maar van intutionistische logica. In deze zin wordt intuïtionistische logica in een topos 'geïnternaliseerd': intuïtionistische logica is de logica van variabele verzamelingen. (Natuurlijk wordt klassieke logica geïnternaliseerd in bepaalde toposen, bijvoorbeeld Set en Set ^(B) voor elke complete Booleaanse algebra B.)

Elke topos kan worden opgevat als een mogelijk "universum van vertoog" waarin wiskundige beweringen kunnen worden geïnterpreteerd en wiskundige constructies kunnen worden uitgevoerd. Wiskundige beweringen worden interpreteerbaar gemaakt in een topos E door expressie in de interne taal van E - een typetheoretische versie van de gebruikelijke taal van de verzamelingenleer. Op een manier die analoog is aan door Booleaans gewaardeerde validiteit, kan men in E van een zin σ van zijn interne taal een passend begrip van validiteit introduceren. Nogmaals, we schrijven E ⊨ σ voor "σ is geldig in E".

Een topos E zou vol zijn als, voor elke set I, de I-voudige copower ^[3] ∐ _I 1 van zijn eindobject bestaat in E. ∐ _I 1 kan worden beschouwd als de canonieke vertegenwoordiger in E van de set Ik; daarom schrijven we het eenvoudig zoals ik. (In V ^(B) valt dit samen met I zoals eerder gedefinieerd.) Alle bovengenoemde toposes zijn vol.

Laat E nu een volledige topos zijn. Als A = (A, R, …) een structuur is, schrijf dan A voor (A, R, …). Twee structuren A en B zijn topos isomorf, geschreven A ≅ _t B, als we voor sommige topos E gedefinieerd over de categorie van sets E ⊨ A ≅ B hebben. Met andere woorden, twee structuren zijn isomorf topos als hun canonieke vertegenwoordigers isomorf zijn in de interne taal van sommige topo's. Dat kan dan worden aangetoond

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

Dienovereenkomstig (∞, ω) -equivalentie kan worden beschouwd als isomorfisme in de extreem algemene context van universa van "variabele" verzamelingen. In dit opzicht is (∞, ω) -equivalentie een 'onveranderlijke' notie van isomorfisme.

3. De eigenschap Compactheid

Zoals we hebben gezien, faalt de compactheidsstelling in zijn gebruikelijke vorm voor alle oneindige talen. Desalniettemin is het van enig belang om te bepalen of oneindige talen voldoen aan een geschikt aangepaste versie van de stelling. Dit zogenaamde compactheidsprobleem blijkt een natuurlijk verband te hebben met puur set-theoretische vragen over "grote" kardinale getallen.

We construeren de volgende definitie. Laat κ een oneindige kardinaal zijn. Een taal L wordt κ- compact genoemd (resp. Zwak κ-compact) als Δ telkens een set L- zinnen is (resp. Een set L- zinnen kardinaliteit ≤ κ) en elke subset Δ kardinaliteit < κ heeft een model, Δ ook. Merk op dat de gebruikelijke compactheidsstelling voor L precies de bewering is dat L ω-compact is. Een reden voor het belang van de eigenschap κ-compactness is de volgende. Noem L κ- complete (resp. Zwak κ- complete) als er een deductief systeem P voor L is met aftrek van lengte <κ zodat, als Δ een P- consistente ^[4] set is van L- zinnen (resp. Zodanig dat | Δ | ≤ κ), dan heeft Δ een model. Merk op dat een dergelijke P voldoende zal zijn voor aftrek van willekeurige verzamelingen van premissen (van kardinaliteit ≤ κ) in de zin van §2. Het is gemakkelijk te zien dat als L κ-compleet of zwak κ-compleet is, L dan κ-compact of zwak κ-compact is. Als we dus kunnen aantonen dat een bepaalde taal niet (zwak) κ-compact is, dan kan er geen deductief systeem voor zijn met aftrek van lengte <κ die geschikt is voor aftrek van willekeurige verzamelingen van gebouwen (van kardinaliteit ≤ κ).

Het blijkt in feite dat de meeste talen L (κ, λ) zelfs niet zwak κ-compact zijn, en voor degenen die dat wel zijn, moet κ een buitengewoon grote kardinaal zijn. We hebben enkele definities nodig.

Een oneindige kardinaal κ zou zwak ontoegankelijk zijn als

(a) λ <κ → λ ⁺ <κ, (waar λ ⁺ staat voor de kardinale opvolger van λ), en

(b) | Ik | <κ en λ _i <κ (voor alle i ∈ ik) ⇒ ∑ _{ik ∈ ik} λ _ik <κ.

Als daarnaast

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

dan is κ (sterk) ontoegankelijk. Aangezien ℵ ₀ niet toegankelijk is, is het normaal om de aandacht te beperken tot die ontoegankelijke of zwak ontoegankelijke kardinalen die groter zijn dan ℵ ₀. Dienovereenkomstig zullen ontoegankelijke of zwak ontoegankelijke kardinalen altijd als ontelbaar worden beschouwd. Het is duidelijk dat dergelijke kardinalen - als ze bestaan - extreem groot moeten zijn; en inderdaad, de onvolledigheidsstelling van Gödel impliceert dat het bestaan van zelfs zwak ontoegankelijke kardinalen niet kan worden bewezen vanuit de gebruikelijke axioma's van de verzamelingenleer.

Laten we een kardinaal κ compact (resp. Zwak compact) noemen als de taal L (κ, κ) κ-compact is (resp. Zwak κ-compact). Dan hebben we de volgende resultaten:

(3.1) ℵ ₀ is compact. Dit is natuurlijk slechts een beknopte manier om de compactheidsstelling voor eerste-orde talen uit te drukken.

(3.2) κ is zwak compact ⇒ L (κ, ω) is zwak κ- compact ⇒ κ is zwak ontoegankelijk. Dienovereenkomstig is het consistent (met de gebruikelijke axioma's van de verzamelingenleer) om aan te nemen dat geen enkele taal L (κ, ω) met κ ≥ ω ₁ zwak κ-compact is, of, a fortiori, zwak κ-compleet.

(3.3) Stel dat κ ontoegankelijk is. Dan is κ zwak compact ⇔ L (κ, ω) is zwak κ- compact. Ook is κ zwak compact ⇒ er is een set κ ontoegankelijke voor κ. Zo is een zwak compacte ontoegankelijke kardinaal buitengewoon groot; in het bijzonder kan het niet de eerste, tweede, …, n ^de, … ontoegankelijk zijn.

(3.4) κ is compact ⇒ κ is niet toegankelijk. (Maar door het resultaat direct hierboven mislukt het omgekeerde.)

Laat Constr staan voor Gödel's axioma van bouwbaarheid; herinner eraan dat Constr consistent is met de gebruikelijke axioma's van de verzamelingenleer.

(3.5) Als Constr houdt, zijn er geen compacte kardinalen.

(3.6) Neem Constr aan en laat κ ontoegankelijk zijn. Dan is κ zwak compact ⇔ L (ω ₁, ω) is zwak κ- compact voor alle L.

(3.7) Als Constr geldt, zijn er geen kardinalen κ waarvoor L (ω ₁, ω) compact is. Dienovereenkomstig is het consistent met de gebruikelijke axioma's van de verzamelingenleer om te veronderstellen dat er geen kardinaal κ is zodat alle talen L (ω ₁, ω) κ-compleet zijn. Dit resultaat staat in contrast met het feit dat alle talen van de eerste orde ω compleet zijn.

De import van deze resultaten is dat de compactheidsstelling voor de meeste talen L (κ, λ) met κ ≥ ω ₁ zeer slecht faalt.

Enkele historische opmerkingen zijn hier op hun plaats. In de jaren dertig van de vorige eeuw onderzochten wiskundigen verschillende versies van het zogenaamde meetprobleem voor sets, een probleem dat ontstond in verband met de theorie van Lebesgue-maat op het continuüm. In het bijzonder werd het volgende zeer eenvoudige begrip maatstaf geformuleerd. Als X een verzameling is, is een (telbaar additieve niet-triviale niet-triviale) maat op X een kaart μ op de vermogensset P X voor de verzameling {0, 1} die voldoet aan:

(a) μ (X) = 1, (b) μ ({x}) = μ (∅) = 0 voor alle x ∈ X, en

(c) als A een telbare familie is van onderling gescheiden subsets van X, dan μ (∪ A) = ∑ {μ (Y): Y ∈ A }.

Het is duidelijk dat of een gegeven set een dergelijke maat ondersteunt alleen afhangt van zijn kardinaliteit, dus het is normaal om een kardinaal κ te definiëren om meetbaar te zijn als alle sets van kardinaliteit κ een dergelijke maat ondersteunen. Al snel werd ingezien dat een meetbare kardinaal ontoegankelijk moet zijn, maar de onwaarheid van het omgekeerde werd pas in de jaren zestig vastgesteld toen Tarski aantoonde dat meetbare kardinalen zwak compact zijn en zijn student Hanf liet zien dat de eerste, tweede, etc. ontoegankelijke niet zwak zijn compact (zie (3.3)). Hoewel de conclusie dat meetbare kardinalen monsterlijk groot moeten zijn nu normaal wordt bewezen zonder de omweg te maken door zwakke compactheid en oneindige talen, blijft het een feit dat deze ideeën in eerste instantie werden gebruikt om het resultaat vast te stellen.

4. Onvolledigheid van oneindig-kwantificatietalen

Waarschijnlijk het belangrijkste resultaat van eerste-orde talen is de Gödel-volledigheidsstelling, die natuurlijk zegt dat de verzameling van alle geldige formules van elke eerste-orde taal L kan worden gegenereerd uit een eenvoudige reeks axioma's door middel van een paar eenvoudige regels van gevolgtrekking. Een belangrijk gevolg van deze stelling is dat, als de formules van L op een constructieve manier worden gecodeerd als natuurlijke getallen, de reeks (codes van) geldige zinnen recursief te tellen is. De volledigheid van een eerste-orde taal impliceert dus dat de set van zijn geldige zinnen op een bijzonder eenvoudige manier kan worden gedefinieerd. Het lijkt daarom redelijk, gegeven een willekeurige taal L, om deze implicatie om te draaien en te suggereren dat, als de set van geldige L-zinnen zijn niet eenvoudig te definiëren, dan kan voor L geen zinvol volledigheidsresultaat worden vastgesteld, of, zoals we zullen zeggen, dat L onvolledig is. In deze sectie gaan we deze suggestie gebruiken bij het schetsen van een bewijs dat "de meeste" oneindige kwantificatietalen in deze zin onvolledig zijn.

Laten we eerst het formele begrip definieerbaarheid als volgt introduceren. Als L een taal is, A een L- structuur en X een deelverzameling van het domein A van A, dan zeggen we dat X in A definieerbaar is met een formule φ (x, y ₁,…, y _n) van L als er is een sequentie een ₁, …, a _n elementen a, zodanig dat X de deelverzameling van alle elementen x ∈ a waarbij φ (x, a ₁, …, a _n) houdt in a.

Schrijf nu Val (L) voor de set van alle geldige L- zinnen, dat wil zeggen, die in elke L- structuur staan. Om een betekenis toe te kennen aan de verklaring "Val (L) is definieerbaar", moeten we specificeren

1. een structuur C (L) -de coderingsstructuur voor L;
2. een bepaalde een-een-kaart - de coderingskaart - van de set formules van L in het domein van C (L).

Als we vervolgens Val (L) identificeren met zijn afbeelding in C (L) onder de coderingskaart, interpreteren we de verklaring "Val (L) is definieerbaar" als de verklaring "Val (L), beschouwd als een subset van de domein van C (L), is definieerbaar in C (L) met een formule van L.”

Als L bijvoorbeeld de eerste-ordetaal L van rekenkunde is, werd Gödel oorspronkelijk gebruikt als coderingsstructuur voor het standaard rekenmodel ℕ en als codering voor de bekende functie die is verkregen uit de priemfactorisatie-stelling voor natuurlijke getallen. De recursieve opsomming van Val (L) betekent dan simpelweg dat de set codes ("Gödel-nummers") van leden van Val (L) in ℕ definieerbaar is door een L-formule met de vorm ∃ y φ (x, y), waar φ (x, y) een recursieve formule is.

Een andere, equivalente, coderingsstructuur voor de eerste-orde taal van rekenen is de structuur ^[5] ⟨H (ω), ∈ ⨡ H (ω)⟩ van erfelijk eindige verzamelingen, waarbij een verzameling x erfelijk eindig is als x, zijn leden, zijn leden, enz., zijn allemaal eindig. Deze coderingsstructuur houdt rekening met het feit dat formules van de eerste orde van nature als eindige verzamelingen worden beschouwd.

Wat betreft nu het geval waarin L een oneindige taal L is (κ, λ), wat zou in dit geval een geschikte coderingsstructuur zijn? In het begin merkten we op dat oneindige talen werden gesuggereerd door de mogelijkheid om formules als set-theoretische objecten te beschouwen, dus laten we proberen onze coderingsstructuur te verkrijgen door na te denken over wat voor soort set-theoretische objecten we zouden moeten nemen om oneindige formules te zijn. Gezien het feit dat voor elke φ∈- vorm (κ, λ), φ en zijn subformules, subsubformules, enz. Allemaal lengte <κ, ^{[6] zijn}een moment van reflectie onthult dat formules van L (κ, λ) "corresponderen" met sets x die van nature kardinaliteit <κ zijn in de zin dat x, zijn leden, zijn leden, enz., allemaal kardinaliteit <κ. De verzameling van al dergelijke sets is geschreven H (κ). H (ω) is de verzameling van erfelijk eindige verzamelingen die hierboven zijn geïntroduceerd, en H (ω ₁) die van alle erfelijk telbare verzamelingen.

Laten we voor de eenvoud aannemen dat het enige extralogische symbool van de basistaal L het binaire predikaatsymbool ∈ is (de discussie kan gemakkelijk worden uitgebreid tot het geval waarin L extra extralogische symbolen bevat). Geleid door de bovenstaande opmerkingen, als coderingsstructuur voor L (κ, λ) nemen we de structuur,

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

Nu kunnen we de coderingskaart van Form (κ, λ) in H (κ) definiëren. Ten eerste wijzen we aan elk basissymbool s van L (κ, λ) als volgt een ^{codeobject ⌈} s ^⌉ ∈ H (κ) toe. Laat {v _ξ: ξ <κ} een opsomming zijn van de individuele variabelen van L (κ, λ).

Symbool	Code Object	Notatie
¬	1	⌈ ¬ ⌉
∧	2	⌈ ∧ ⌉
∧	3	⌈ ∧ ⌉
∃	4	⌈ ∃ ⌉
∈	5	⌈ ∈ ⌉
=	6	⌈ = ⌉
v ξ	⟨0, ξ⟩	⌈ tegen ξ ⌉

Vervolgens wijzen we aan elke φ ∈ vorm (κ, λ) het ^{codeobject ⌈} φ ^⌉ recursief toe als volgt:

^⌈ v _ξ = v _ij ^⌉ = _df ⟨ ^⌈ v _ξ ^⌉, ^⌈ = ^⌉, ^⌈ v _ij ^⌉ ⟩, ^⌈ v _ξ ∈ v _ij ^⌉ = _df ⟨ ^⌈ v _ξ ^⌉, ^⌈ ∈ ^⌉, ^⌈ v _ij ^⌉ ⟩;

voor φ, ψ ∈ Vorm (κ, λ),

^⌈ cp ∧ yr ^⌉ = _df ⟨ ^⌈ cp ^⌉, ^⌈ ∧ ^⌉, ^⌈ yr ^⌉ ⟩

^⌈ ¬φ ^⌉ = _df ⟨ ^⌈ Â ^⌉, ^⌈ cp ^⌉ ⟩

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

en tenslotte als Φ ⊆ vorm (κ, λ) met | Φ | <κ,

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

De kaart φ ↦ ^⌈ φ ^⌉ van vorm (κ, λ) naar H (κ) is gemakkelijk te zien als een één en is de vereiste coderingskaart. Dienovereenkomstig stemmen we ermee in om Val (L (κ, λ)) te identificeren met zijn afbeelding in H (κ) onder deze coderingskaart.

Wanneer is Val (L (κ, λ)) een definieerbare subset van H (κ)? Om deze vraag te beantwoorden hebben we de volgende definities nodig.

Een L-formule wordt een Δ ₀ - formule genoemd als deze equivalent is aan een formule waarin alle kwantoren de vorm ∀ x ∈ y of ∃ x ∈ y hebben (dwz ∀ x (x ∈ y →…) of ∃ x (x ∈ y ∧…)). Een L-formule is een Σ ₁ -formule als deze equivalent is aan een formule die kan worden opgebouwd uit atomaire formules en hun ontkenningen met alleen de logische operatoren ∧, ∨, ∀ x ∈ y, ∃ x. Een subset X van een set A wordt Δ ₀ (resp. Σ ₁) op A genoemd als het in de structuur ⟨A, ∈ ⨡ A⟩ definieerbaar is met een Δ ₀ - (resp. Σ ₁ -) formule van L.

Als we bijvoorbeeld de verzameling natuurlijke getallen op de gebruikelijke manier identificeren met de verzameling H (ω) van erfelijk eindige verzamelingen, dan hebben we voor elke X ⊆ H (ω):

X is Δ ₀ op H (ω) ⇔ X is recursief

X is Σ ₁ op H (ω) ⇔ X is recursief op te tellen.

Dus de noties van Δ ₀ - en Σ _1- set kunnen worden beschouwd als generalisaties van de noties van respectievelijk recursieve en recursief opsommelbare set.

De volledigheidsstelling voor L impliceert dat Val (L) - beschouwd als een deelverzameling van H (ω) - recursief te tellen is, en dus Σ ₁ op H (ω). Evenzo impliceert de volledigheidsstelling voor L (ω ₁, ω) (zie §2) dat Val (L (ω ₁, ω)) - beschouwd als een subset van H (ω ₁) - Σ _{1 is} op H (ω ₁). Deze prettige stand van zaken stort echter volledig in zodra L (ω ₁, ω ₁) is bereikt. Dat kan men bewijzen

Scotts ondefinieerbaarheidsstelling voor L (ω ₁, ω ₁). Val (L (ω ₁, ω ₁)) is niet definieerbaar in H (ω ₁) zelfs niet met een L (ω ₁, ω ₁) - formule; vandaar a fortiori Val (L (ω ₁, ω ₁)) is niet Σ ₁ op H (ω ₁).

Deze stelling wordt op vrijwel dezelfde manier bewezen als het bekende resultaat dat de verzameling (codes van) geldige zinnen van de tweede-ordetaal van het rekenkundige L ² geen tweede-orde definieerbaar is in zijn coderingsstructuur ℕ. Om dit laatste resultaat te krijgen, merkt men eerst op dat ℕ wordt gekenmerkt door een enkele L ^2- zin, en laat vervolgens zien dat, als het resultaat onwaar was, "waarheid in ℕ" voor L ^2- zinnen zou kunnen worden gedefinieerd door een L ² -formule, waardoor Tarski's stelling over de ondefinieerbaarheid van de waarheid wordt geschonden.

Om Scotts stelling van ondefinieerbaarheid in de bovenstaande zin te bewijzen, moet men daarom vaststellen:

(4.1) Karakterisering van de coderingsstructuur H (ω ₁) in L (ω ₁, ω ₁): er is een L (ω ₁, ω ₁) -zin τ ₀ zodat, voor alle L-structuren A, A ⊨ τ ₀ ⇔ A ≅ H (ω ₁).

(4.2) Ondefinieerbaarheid van waarheid voor L (ω ₁, ω ₁) - zinnen in de coderingsstructuur: er is geen L (ω ₁, ω ₁) -formule φ (v ₀) zodat, voor alle L (ω ₁, ω ₁) -gevoelens σ, H (ω ₁) ⊨ σ↔φ (^⌈ σ ^⌉).

(4.3) Er is een term t (v ₀, v ₁) van L (ω ₁, ω ₁) zodat, voor elk paar zinnen σ, τ van L (ω ₁, ω ₁), H (ω ₁) ⊨ [t (^⌈ σ ^⌉, ^⌈ τ ^⌉) = ^⌈ σ → τ ^⌉].

(4.1) wordt bewezen door de set-theoretische definitie van H (ω ₁) te analyseren en te laten zien dat het “intern” kan worden geformuleerd in L (ω ₁, ω ₁). (4.2) komt op vrijwel dezelfde manier tot stand als Tarski's stelling over de ondefinieerbaarheid van de waarheid voor talen van de eerste of tweede orde. (4.3) wordt verkregen door de definitie van de coderingskaart σ ↦ ^⌈ σ ^⌉ in L (ω ₁, ω ₁) te formaliseren.

Gewapend met deze feiten kunnen we Scotts ondefinieerbaarheidsstelling op de volgende manier verkrijgen. Stel dat het vals was; dan zou er een L (ω ₁, ω ₁) -formule θ (v ₀) zijn zodat, voor alle L (ω ₁, ω ₁) -zintuigen σ,

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

Laat τ ₀ de zin zijn die gegeven wordt in (4.1). Dan hebben we voor alle L (ω ₁, ω ₁) -zintuigen σ,

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

zodat, door (4.4),

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

Als t de term is die gegeven is in (4.3), zou dat daarop volgen

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

Schrijf nu φ (v ₀) voor de L (ω ₁, ω ₁) -formule θ (t (^⌈ τ ₀ ^⌉, ^⌈ σ ^⌉)). Vervolgens

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

in tegenspraak met (4.2) en het voltooien van het bewijs.

Dus Val (L (ω ₁, ω ₁)) is niet definieerbaar, zelfs niet met een L (ω ₁, ω ₁) - formule, dus a fortiori L (ω ₁, ω ₁) is onvolledig. Soortgelijke argumenten tonen aan dat Scotts stelling van ondefinieerbaarheid blijft bestaan wanneer ω ₁ wordt vervangen door een opvolger van kardinaal κ ⁺; daarom zijn de talen L (κ ⁺, κ ⁺) allemaal onvolledig. ^[7]

5. Subtalen van L (ω ₁, ω) en de stelling van de compactheid van Barwise

Gezien wat we nu weten over oneindige talen, lijkt het erop dat L (ω ₁, ω) de enige is die zich redelijk goed gedraagt. Aan de andere kant is het falen van de compactheidsstelling om op een bruikbare manier te generaliseren naar L (ω ₁, ω) een ernstig nadeel wat betreft toepassingen. Laten we proberen deze mislukking in meer detail te analyseren.

Bedenk uit §4 dat we de formules van een eerste-orde taal L kunnen coderen als erfelijk eindige verzamelingen, dat wil zeggen als leden van H (ω). In dat geval is elke eindige set van (codes van) L-zinnen ook lid van H (ω), en daaruit volgt dat de compactheidsstelling voor L kan worden vermeld in de vorm:

(5.1) Als Δ ⊆ Sent (L) zodanig is dat elke subset Δ ₀ ⊆ Δ, Δ ₀ ∈ H (ω) een model heeft, heeft Δ dat ook.

Nu is het algemeen bekend dat (5.1) een direct gevolg is van de gegeneraliseerde volledigheidsstelling voor L, die, in een vorm die lijkt op die van (5.1), de bewering wordt:

(5.2) Als Δ ⊆ Sent (L) en σ ∈ Sent (L) voldoen aan Δ ⊨ σ, dan is er een aftrek D van σ van Δ zodat D ∈ H (ω). ^[8]

In §2 merkten we op dat de compactheidsstelling voor L (ω ₁, ω) zeer sterk faalt; in feite hebben we een set Γ ⊆ Sent (ω ₁, ω) zo geconstrueerd dat

(5.3) Elke telbare subset van Γ heeft een model, maar Γ niet.

Bedenk ook dat we het begrip aftrek in L (ω ₁, ω) hebben geïntroduceerd; aangezien dergelijke aftrekkingen van telbare lengte zijn, volgt snel uit (5.3) dat

(5.4) Er is een zin ^[9] σ ∈ Verzonden (ω ₁, ω) zodat Γ ⊨ σ, maar er is geen aftrek van σ in L (ω ₁, ω) van Γ.

Nu kunnen de formules van L (ω ₁, ω) worden gecodeerd als leden van H (ω ₁), en het is duidelijk dat H (ω ₁) gesloten is onder vorming van telbare subsets en sequenties. Dienovereenkomstig kunnen (5.3) en (5.4) worden geschreven:

(5.3 bis) Elke Γ ₀ ⊆ Γ zodat Γ ₀ ∈ H (ω ₁) een model heeft, maar Γ niet;

(5.4 bis) Er is een zin σ ∈ Verzonden (ω ₁, ω) zodat Γ ⊨ σ, maar er is geen aftrek D ∈ H (ω ₁) van σ van Γ.

Hieruit volgt dat (5.1) en (5.2) mislukken wanneer "L" wordt vervangen door "L (ω ₁, ω)" en "H (ω)" door "H (ω ₁)". Bovendien kan worden aangetoond dat de set Γ ⊆ Sent (ω ₁, ω) in (5.3 bis) en (5.4 bis) kan worden beschouwd als Σ ₁ op H (ω ₁). Dus de compactheid en gegeneraliseerde volledigheidstheorieën falen zelfs voor Σ ₁ -sets van L (ω ₁, ω) -gevoeligheden.

We zien uit (5.4 bis) dat de reden waarom de gegeneraliseerde volledigheidsstelling voor Σ ₁ -sets in L (ω ₁, ω) mislukt, is dat H (ω ₁) ruwweg niet "gesloten" is onder de vorming van inhoudingen vanaf Σ ₁ -reeksen van zinnen in H (ω ₁). Dus om dit te verhelpen, lijkt het logisch om H (ω ₁) te vervangen door sets A die in zekere zin gesloten zijn onder de vorming van dergelijke aftrekkingen, en dan alleen die formules te beschouwen waarvan de codes in A staan.

We geven nu een schets van hoe dit kan.

Eerst identificeren we de symbolen en formules van L (ω ₁, ω) met hun codes in H (ω ₁), zoals in §4. Voor elke telbare transitieve ^[10] set A, laten we

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

We zeggen dat L _A een subtaal is van L (ω ₁, ω) als aan de volgende voorwaarden is voldaan:

1. L ⊆ L _A
2. als φ, ψ ∈ L _A, dan φ ∧ ψ ∈ L _A en ¬φ ∈ L _A
3. als φ ∈ L _A en x ∈ A, dan ∃ x φ ∈ L _A
4. als φ (x) ∈ L _A en y ∈ A, dan φ (y) ∈ L _A
5. als φ ∈ L _A, is elke subformule van φ in L _A
6. Als Φ ⊆ L _A en Φ ∈ A, dan ∧Φ ∈ L _A.

Het begrip aftrek in L _A wordt op de gebruikelijke manier gedefinieerd; als Δ een verzameling zinnen is van L _A en φ ∈ L _A, dan is een aftrek van φ van Δ in L _A een aftrek van φ van Δ in L (ω ₁, ω) waarvan elke formule in L _{A is}. We zeggen dat φ aftrekbaar is van Δ in L _A als er een aftrek D is van φ van Δ in L _A; onder deze omstandigheden schrijven we Δ ⊢ _A φ. Over het algemeen zal D geen lid zijn van A; Om ervoor te zorgen dat een dergelijke aftrek in A te vinden is, zullen aan A nadere voorwaarden moeten worden gesteld.

Zij A een telbaar transitieve ingesteld dat L _A een subtaal van L (ω ₁, ω) en laat Δ zijn een aantal zinnen L _A. We zeggen dat A (of, door misbruik van terminologie, L _A) Δ- gesloten is als er voor elke formule φ van L _A zodanig is dat Δ ⊢ _A φ, een aftrek D van φ is van Δ zodat D ∈ A. Aangetoond kan worden dat de enige telbare taal die Δ-gesloten is voor willekeurige Δ de eerste-orde taal L is, dat wil zeggen wanneer A = H (ω). J. Barwise ontdekte echter dat er telbare sets A ⊆ H (ω ₁) zijn waarvan de corresponderende talen L _A verschillen van L en toch Δ gesloten zijn voor alle Σ ₁- zinnenreeksen Δ. Dergelijke sets A worden toelaatbare sets genoemd; ruwweg zijn het uitbreidingen van de erfelijk eindige verzamelingen waarin recursietheorie - en dus bewijstheorie - nog steeds mogelijk zijn (voor de volledige definitie, zie paragraaf 5.1 hieronder).

Uit het resultaat van Barwise verkrijgt men onmiddellijk de

Stelling van Barwise Compactness. Laat A een telbare toelaatbare verzameling zijn en laat Δ een verzameling zinnen zijn van L _A die Σ _{1 is} op A. Als elke Δ '⊆ Δ zodanig is dat Δ' ∈ A een model heeft, dan heeft Δ dat ook.

De aanwezigheid van "Σ ₁ " hier geeft aan dat deze stelling een veralgemening is van de compactheidsstelling voor recursief opsommen van reeksen zinnen.

Een andere versie van de Barwise compactheidsstelling, nuttig voor het construeren van modellen van verzamelingenleer, is de volgende. Laat ZFC de gebruikelijke set axioma's zijn voor de verzamelingenleer van Zermelo-Fraenkel, inclusief het axioma van keuze. Dan hebben we:

5.5 Stelling. Laat A een telbare transitieve set zijn zodat A = ⟨A, ∈ ⨡ A⟩ een model van ZFC is. Δ als een verzameling zinnen van L _A die kan worden gedefinieerd in een door een formule van de taal van de set theorie en indien elke Δ '⊆ Δ zodat Δ' ∈ A een model, dat doet Δ.

Tot slot geven we een eenvoudige toepassing van deze stelling. Laat A = ⟨A, ∈ ⨡ A⟩ een model zijn van ZFC. Een model B = ⟨B, E⟩ van ZFC zou een goede einduitbreiding van A zijn als (i) A ⊆ B, (ii) A ≠ B, (iii) a ∈ A, b ∈ B, bEa ⇒ b ∈ A. Een goede einduitbreiding van een model van ZFC is dus een goede uitbreiding waarbij geen "nieuw" element "voor" enig "oud" element komt. Als onze toepassing van 5.5 bewijzen we

5.6 Stelling. Elk telbaar transitief model van ZFC heeft een goede end-extension.

Bewijs. Laat A = ⟨A, ∈ ⨡ A⟩ een transitief model van ZFC zijn en laat L de eerste-orde taal van de verzamelingenleer zijn, aangevuld met een naam a voor elk a ∈ A, en een extra constante c. Laat Δ de verzameling L _A- zinnen zijn, bestaande uit:

• alle axioma's van ZFC;
• c ≠ a, voor elk a ∈ A;
• ∀ x (x ∈ a → ∨ _{b ∈ a} x = b), voor elk a ∈ A;
• a ∈ b, voor elk a ∈ b ∈ A.

Het is gemakkelijk aan te tonen dat Δ een subset van A is die in A definieerbaar is door een formule van de taal van de verzamelingenleer. Ook is elke subset Δ '⊆ Δ zodanig dat Δ' ∈ A een model heeft. Voor de verzameling C van alle a ∈ A waarvoor a voorkomt in Δ 'behoort tot A - aangezien Δ' dat doet - en dus, als we c interpreteren als een lid van de (noodzakelijk niet lege) verzameling A - C, dan is A een model van Δ '. Dienovereenkomstig impliceert (5.5) dat Δ een model ⟨B, E⟩ heeft. Als we interpreteren elk constant een als element a ∈ A dan ⟨B, E⟩ een goede end-verlenging van A. Het bewijs is compleet.

De lezer zal snel zien dat de compactheidsstelling van de eerste orde dit resultaat niet zal opleveren.

5.1 Definitie van het concept van toelaatbare reeks

Een niet-lege transitieve set A is ontvankelijk wanneer aan de volgende voorwaarden is voldaan:

1. als a, b ∈ A, dan {a, b} ∈ A en ∪ A ∈ A;
2. als a ∈ A en X ⊆ A Δ ₀ op A is, dan is X ∩ a ∈ A;
3. als a ∈ A, X ⊆ A Δ ₀ op A is, en ∀ x ∈ a ∃ y (<x, y> ∈ X), dan, voor sommige b ∈ A, ∀ x ∈ a ∃ y ∈ b (<x, y> ∈ X).

Voorwaarde (ii) - het Δ ₀ - scheidingsschema - is een beperkte versie van Zermelo's axioma van scheiding. Voorwaarde (iii) - een eveneens verzwakte versie van het vervangingsaspect - kan het Δ ₀ - vervangingsschema worden genoemd.

Het is vrij gemakkelijk te zien dat als A een transitieve verzameling is, zodanig dat <A, ∈ | A> is een model van ZFC, dan is A toegestaan. Meer in het algemeen blijft het resultaat behouden wanneer het axioma van het ingestelde vermogen wordt weggelaten uit ZFC, zodat zowel H (ω) als H (ω ₁) toelaatbaar zijn. Aangezien dit laatste echter niet te tellen is, is de stelling van Barwise over compactheid er niet op van toepassing.

6. Historische en bibliografische opmerkingen

§§ 1 en 2. Infinitaire propositionele en predikaattalen lijken voor het eerst expliciet in druk te zijn verschenen met de artikelen van Scott en Tarski [1958] en Tarski [1958]. De volledigheidsstelling voor L (ω ₁, ω), evenals voor andere oneindige talen, werd bewezen door Karp [1964]. De Hanf-getalberekeningen voor L (ω ₁, ω) werden voor het eerst uitgevoerd door Morley [1965]. Karp [1965] en Lopez-Escobar [1966] hebben de niet-definieerbaarheid van de rangschikking in eindige-kwantificatietalen bewezen. De interpolatiestelling voor L (ω ₁, ω) werd bewezen door Lopez-Escobar [1965] en Scott's isomorfismestelling voor L (ω ₁, ω) door Scott [1965].

Karps partiële isomorfismestelling werd voor het eerst bewezen in Karp [1965]; zie ook Barwise [1973]. Resultaat (2.2) verschijnt in Chang [1968], resultaat (2.3) in Ellentuck [1976] en resultaat (2.4) in Bell [1981].

§ 3. Resultaten (3.2) en (3.3) zijn te danken aan Hanf [1964], met enkele verfijningen van Lopez-Escobar [1966] en Dickmann [1975], terwijl (3.4) werd bewezen door Tarski. Resultaat (3.5) is te danken aan Scott [1961], (3.6) aan Bell [1970] en [1972]; en (3.7) aan Bell [1974]. Meetbare kardinalen werden voor het eerst overwogen door Ulam [1930] en Tarski [1939]. Het feit dat meetbare kardinalen zwak compact zijn, werd opgemerkt in Tarski [1962].

§ 4. Betreffende de ondefinieerbaarheidsstelling voor L (ω ₁, ω ₁). Carol Karp merkt op (1964, 166): “Op het Internationale Congres van Logica, Methodologie en Wetenschapsfilosofie aan de Stanford University in 1960 verspreidde Dana Scott een schets van een bewijs van de onmogelijkheid van een volledig definieerbaar formeel systeem voor (γ +, γ +) talen met een enkel predikaatsymbool met twee plaatsen naast het gelijkheidssymbool.” Scott publiceerde zijn resultaat nooit, en een volledig gedetailleerd bewijs verscheen voor het eerst in Karp [1964]. De benadering van de hier gehanteerde stelling is gebaseerd op het verslag in Dickmann [1975].

§ 5. De oorspronkelijke motivatie voor de resultaten in deze sectie kwam van Kreisel; in zijn [1965] wees hij erop dat er geen dwingende redenen waren om oneindige formules uitsluitend op basis van "lengte" te kiezen, en stelde in plaats daarvan voor om criteria voor definieerbaarheid of "sluiting" te gebruiken. De suggestie van Kreisel werd met groot succes overgenomen door Barwise [1967], waar zijn stelling over compactheid werd bewezen. Het idee van een toelaatbare set is te danken aan Platek [1966]. Stelling (5.6) is afkomstig van Keisler [1974].

Voor meer informatie over oneindige talen, zie Aczel [1973], Dickmann [1975], Karp [1964], Keisler [1974] en Makkai [1977]. Een nuttig verslag van het verband tussen oneindige talen en grote kardinalen is te vinden in hoofdstuk 10 van Drake [1974].

Bibliografie

• Aczel, P., 1973, "Infinitary Logic and the Barwise Compactness Theorem", Proceedings of the 1971 Bertrand Russell Memorial Logic Conference (Uldum, Denmark), J. Bell, J. Cole, G. Priest, en A. Slomson (eds.), Leeds: Bertrand Russell Memorial Logic Conference, 234–277.
• Barwise, J., 1967, Infinitary Logic en toelaatbare sets. Ph. D. Scriptie, Stanford University.
• –––, 1973, “Back and Forth door Infinitary Logic. Studies in Model Theory”, in Studies in Mathematics (Volume 8), Buffalo: Mathematical Association of American, pp. 5–34.
• –––, 1975, toelaatbare sets en structuren, Berlijn: Springer-Verlag.
• Barwise, J. en S. Feferman (redactie), 1985, Handbook of Model-Theoretic Logics, New York: Springer-Verlag.
• Baumgartner, J., 1974, "Het Hanf-nummer voor volledige L _{ω 1, ω} zinnen (zonder GCH)", Journal of Symbolic Logic, 39: 575–578.
• Bell, JL, 1970, "Weak Compactness in Restricted Second-Order Languages", Bulletin van de Poolse Academie van Wetenschappen, 18: 111–114.
• –––, 1972, "Over de relatie tussen zwakke compactheid in L _{ω 1, ω}, L _{ω 1, ω 1, en beperkte tweede-orde talen", Archief voor wiskundige logica, 15: 74–78.}
• –––, 1974, “On Compact Cardinals”, Zeitschrift für Mathematical Logik und Grundlagen der Mathematik, 20: 389–393.
• –––, 1981, “Isomorphism of Structures in S-toposes”, Journal of Symbolic Logic, 43 (3): 449–459.
• Chang, CC, 1968, "Enkele opmerkingen over de modeltheorie van oneindige talen". in The Syntax and Semantics of Infinitary Languages (Lecture Notes in Mathematics: Volume 72), J. Barwise (red.), Springer-Verlag, Berlin, 36-63.
• Dickmann, MA, 1975, grote oneindige talen, Amsterdam: Noord-Holland.
• Drake, FR, 1974, Set Theory: An Introduction to Large Cardinals, Amsterdam: North-Holland Publishing Company.
• Ellentuck, E., 1976, "Categoricity Regained", Journal of Symbolic Logic, 41 (3): 639–643.
• Hanf, WP, 1964, Incompactness in Languages with Infinitely Long Expressions, Amsterdam: Noord-Holland.
• Karp, C., 1964, Talen met uitdrukkingen van oneindige lengte, Amsterdam: Noord-Holland.
• –––, 1965, “Finite-Quantifier Equivalence” in The Theory of Models, J. Addison, L. Henkin, en A. Tarski (red.), Amsterdam: Noord-Holland, 407–412.
• Keisler, HJ, 1974, Model Theory for Infinitary Logic, Amsterdam: Noord-Holland.
• Keisler, HJ en Julia F. Knight, 2004, 'Barwise: Infinitary Logic And Admappled Sets', Journal of Symbolische logica, 10 (1): 4–36
• Kolaitis, P. en M. Vardi, 1992, "Fixpoint Logic vs. Infinitary Logic in Finite-Model Theory", Proceedings of the Seventh Annual IEEE Symposium on Logic in Computer Science (LICS '92), IEEE, pp. 46-57; online beschikbaar, doi: 10.1109 / LICS.1992.185518
• Kreisel, G., 1965, "Model-theoretische invarianten, toepassingen voor recursieve en hyperaritmetische operaties", in The Theory of Models, J. Addison, L. Henkin en A. Tarski (red.), Amsterdam: Noord-Holland, 190-205.
• Kueker, D., 1975, "Heen en weer redeneringen in oneindige talen", in Infinitary Logic: In Memoriam Carol Karp (Lecture Notes in Mathematics: Volume 492), D. Kueker (red.), Berlin: Springer-Verlag.
• Lopez-Escobar, EGK, 1965, "Een interpolatiestelling voor oneindig lange zinnen", Fundamenta Mathematicae, 57: 253–272.
• –––, 1966, “On Defining Well-Orderings”, Fundamenta Mathematicae, 59: 13–21.
• Makkai, M., 1977, "Ontvankelijke sets en oneindige logica", Handbook of Mathematical Logic, J. Barwise (red.), Amsterdam: Noord-Holland, 233-282.
• Morley, M., 1965, "Weglaten van klassen van elementen", The Theory of Models, J. Addison, L. Henkin en A. Tarski (red.), Amsterdam: Noord-Holland, 265-273.
• Nadel, M. 1985, "L _{ω 1, ω} en toelaatbare fragmenten", in J. Barwise en S. Feferman (red.) 1985, 271–287.
• Platek, R., 1966, Foundations of Recursion Theory, Ph. D. Scriptie, Stanford University.
• Scott, D., 1961, "Meetbare kardinalen en bouwbare sets", Bulletin van de Academie van Poolse wetenschappen, 9: 521–524.
• –––, 1965, "Logica met denumereerbaar lange formules en eindige snaren van kwantificatoren", The Theory of Models, J. Addison, L. Henkin en A. Tarski (red.), Amsterdam: Noord-Holland, 329-341.
• Scott, D. en A. Tarski, 1958, 'De sentimentele calculus met oneindig lange uitdrukkingen', Colloquium Mathematicum, 16: 166–170.
• Shelah, Saharon, 2012, "Nice infinitary logics", Journal of the American Mathematical Society, 25: 395-427, online beschikbaar, 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, “Opmerkingen over predikaatlogica met oneindig lange uitdrukkingen”, Colloquium Mathematicum, 16: 171–176.
• –––, 1962, "Enkele problemen en resultaten die relevant zijn voor de grondslagen van de verzamelingenleer", in E, Nagel, P. Suppes en A. Tarski (red.), Logica, Methodologie en Wetenschapsfilosofie, Stanford: Stanford University Press, 123-135.
• Ulam, S., 1930, "Zur Masstheorie in der algemeinen Mengenlehre", Fundamenta Mathematicae, 16: 140–150.

Academische hulpmiddelen

	Hoe deze vermelding te citeren.
	Bekijk een voorbeeld van de PDF-versie van dit item bij de Vrienden van de SEP Society.
	Zoek dit itemonderwerp op bij het Internet Philosophy Ontology Project (InPhO).
	Verbeterde bibliografie voor dit item op PhilPapers, met links naar de database.

Andere internetbronnen