Unendliche Logik

Eintragsnavigation

• Eintragsinhalt
• Literaturverzeichnis
• Akademische Werkzeuge
• Freunde PDF Vorschau
• Autor und Zitierinfo
• Zurück nach oben

Unendliche Logik

Erstveröffentlichung am 23. Januar 2000; inhaltliche Überarbeitung Fr 26. Februar 2016

Traditionell wurden Ausdrücke in formalen Systemen als endliche Inschriften bezeichnet, die - zumindest im Prinzip - tatsächlich in primitiver Notation geschrieben werden können. Die Tatsache, dass Formeln (erster Ordnung) mit natürlichen Zahlen (über die „Gödel-Nummerierung“) und damit mit endlichen Mengen identifiziert werden können, macht es jedoch nicht länger erforderlich, Formeln als Inschriften zu betrachten, und legt die Möglichkeit nahe, einige „Sprachen“zu gestalten von deren Formeln natürlich als unendliche Mengen identifiziert würden. Eine „Sprache“dieser Art wird als unendliche Sprache bezeichnet: In diesem Artikel diskutiere ich jene unendlichen Sprachen, die auf einfache Weise aus Sprachen erster Ordnung erhalten werden können, indem Konjunktionen, Disjunktionen und möglicherweise Quantifizierersequenzen unendlich sein können Länge. Im Verlauf der Diskussion wird sich zeigen, dass die Ausdruckskraft solcher Sprachen zwar die ihrer endlichen Gegenstücke (erster Ordnung) bei weitem übersteigt, aber nur sehr wenige von ihnen die „attraktiven“Merkmale (z. B. Kompaktheit und Vollständigkeit) von besitzen Letzteres. Dementsprechend verdienen die unendlichen Sprachen, die tatsächlich diese Merkmale besitzen, besondere Aufmerksamkeit.

In §1 sind die grundlegende Syntax und Semantik unendlicher Sprachen festgelegt; Ihre Ausdruckskraft wird dann anhand von Beispielen dargestellt. §2 ist jenen unendlichen Sprachen gewidmet, die nur endliche Quantifizierersequenzen zulassen: Diese Sprachen erweisen sich als relativ brav. §3 widmet sich einer Diskussion des Kompaktheitsproblems für unendliche Sprachen und seiner Verbindung mit rein satztheoretischen Fragen zu „großen“Kardinalzahlen. In §4 wird ein Argument skizziert, das zeigt, dass die meisten „Infinite Quantifier“-Sprachen von zweiter Ordnung sind und ipso facto sehr unvollständig sind. § 5 gibt einen kurzen Überblick über eine bestimmte spezielle Klasse von Subsprachen unendlicher Sprachen, für die eine zufriedenstellende Verallgemeinerung des Kompaktheitssatzes bewiesen werden kann. Dieser Abschnitt enthält einen Unterabschnitt zur Definition zulässiger Mengen. Historische und bibliographische Bemerkungen sind in §6 enthalten.

• 1. Definition und grundlegende Eigenschaften unendlicher Sprachen
• 2. Sprachen mit endlichen Quantifizierern
• 3. Die Kompaktheitseigenschaft
• 4. Unvollständigkeit von Infinite-Quantifier-Sprachen
• 5. Subsprachen von L (ω ₁, ω) und des Barwise Compactness Theorem

  5.1 Definition des Konzepts der zulässigen Menge

• 6. Historische und bibliographische Bemerkungen
• Literaturverzeichnis
• Akademische Werkzeuge
• Andere Internetquellen
• Verwandte Einträge

1. Definition und grundlegende Eigenschaften unendlicher Sprachen

Wenn ein Paar κ, λ von unendlichen Kardinälen gegeben ist, so dass λ ≤ κ ist, definieren wir eine Klasse von unendlichen Sprachen, in denen wir Konjunktionen und Disjunktionen von Mengen von Formeln der Kardinalität <κ und Quantifizierungen über Sequenzen von Variablen der Länge <bilden können λ.

Sei L - die (endliche) Basissprache - eine willkürliche, aber feste Sprache erster Ordnung mit einer beliebigen Anzahl von extralogischen Symbolen. Die unendliche Sprache L (κ, λ) hat folgende Grundsymbole:

• Alle Symbole von L.
• Eine Menge Var einzelner Variablen, wobei die Kardinalität von Var (geschrieben: | Var |) κ ist
• Ein logischer Operator ∧ (unendliche Konjunktion)

Die Klasse der Vorformeln von L (κ, λ) ist rekursiv wie folgt definiert:

• Jede Formel von L ist eine Vorformel;
• wenn φ und ψ Vorformeln sind, sind es auch φ∧ψ und ¬φ;
• wenn Φ eine Menge von Vorformeln ist, so dass | Φ | <κ, dann ist ∧Φ eine Vorformel;
• wenn φ eine Vorformel ist und X ⊆ Var so ist, dass | X | <λ, dann ist ∃ X φ eine Vorformel;
• Alle Vorformeln werden durch die obigen Abschnitte definiert.

Wenn Φ eine Menge von Vorformeln ist, die durch eine Menge I indiziert sind, sagen wir Φ = {φ _i: i ∈ I}, dann stimmen wir zu, ∧Φ zu schreiben für:

∧ _{i ∈ I}  φ

oder, wenn ich die Menge natürlicher Zahlen bin, schreiben wir ∧Φ für:

φ ₀ ∧ φ ₁ ∧…

Wenn X eine Menge einzelner Variablen ist, die durch eine Ordnungszahl α indiziert sind, sagen wir X = {x _ξ: ξ <α}, stimmen wir zu, (∃ x _ξ) _{ξ <α} φ für ∃ X φ zu schreiben.

Die logischen Operatoren ∨, →, ↔ werden in üblicher Weise definiert. Wir führen auch die Operatoren ∨ (infinitäre Disjunktion) und ∀ (universelle Quantifizierung) durch ein

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

∀Xφ = _df ¬∃X¬φ,

und wende ähnliche Konventionen an wie für ∧, ∃.

Somit ist L (κ, λ) die unendliche Sprache, die aus L erhalten wird, indem Konjunktionen und Disjunktionen der Länge <κ und Quantifizierungen ^[1] der Länge <λ zugelassen werden. Die Sprachen L (κ, ω) werden als Finite-Quantifizierer-Sprachen bezeichnet, die übrigen Infinite-Quantifizierer-Sprachen. Beachten Sie, dass L (ω, ω) nur L selbst ist.

Beachten Sie die folgende Anomalie, die in einer unendlichen Sprache auftreten kann, jedoch nicht in einer endlichen. In der Sprache L (ω ₁, ω), die zählbar unendliche Konjunktionen, aber nur endliche Quantifizierungen erlaubt, gibt es Vorformeln mit so vielen freien Variablen, dass sie nicht durch Präfixieren von Quantifizierern in Sätze von L (ω ₁, ω) „geschlossen“werden können. Dies ist beispielsweise bei der L (ω ₁, ω) -Vorformel der Fall

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

wobei L das binäre Beziehungssymbol <enthält. Aus diesem Grund machen wir folgendes

Definition. Eine Formel von L (κ, λ) ist eine Vorformel, die <λ freie Variablen enthält. Die Menge aller Formeln von L (κ, λ) wird mit Form (L (κ, λ)) oder einfach Form (κ, λ) und die Menge aller Sätze mit Sent (L (κ, λ)) oder bezeichnet einfach gesendet (κ, λ).

Beachten Sie in diesem Zusammenhang, dass im Allgemeinen nichts gewonnen werden würde, wenn „Sprachen“L (κ, λ) mit λ> κ betrachtet würden. Beispielsweise haben Formeln in der "Sprache" L (ω, ω ₁) nur endlich viele freie Variablen, während es eine Vielzahl von "nutzlosen" Quantifizierern gibt, die unendlich viele freie Variablen binden können. ^[2]

Nachdem wir die Syntax von L (κ, λ) definiert haben, skizzieren wir als nächstes seine Semantik. Da die extralogischen Symbole von L (κ, λ) nur die von L sind und diese Symbole die Form der Strukturen bestimmen, in denen eine bestimmte Sprache erster Ordnung interpretiert werden soll, ist es natürlich, ein L (κ, λ) -Struktur soll einfach eine L-Struktur sein. Die Vorstellung, dass eine Formel von L (κ, λ) in einer L-Struktur A (durch eine Folge von Elementen aus der Domäne von A) erfüllt ist, wird auf dieselbe induktive Weise wie für Formeln von L definiert, außer dass wir zwei hinzufügen müssen zusätzliche Klauseln, die den Klauseln für ∧Φ und ∃Xφ in der Definition der Vorformel entsprechen. In diesen beiden Fällen definieren wir natürlich:

∧Φ ist in A (durch eine gegebene Folge) erfüllt ⇔ für alle φ ∈ Φ, φ ist in A (durch die Folge) erfüllt;

∃ X φ ist in A erfüllt ⇔ es gibt eine Folge von Elementen aus der Domäne von A in bijektiver Entsprechung mit X, die φ in A erfüllt.

Diese informellen Definitionen müssen in einer rigorosen Entwicklung verschärft werden, aber ihre Bedeutung sollte dem Leser klar sein. Nun werden die üblichen Begriffe von Wahrheit, Gültigkeit, Erfüllbarkeit und Modell für Formeln und Sätze von L (κ, λ) verfügbar. Insbesondere wenn A eine L-Struktur ist und σ ∈ gesendet wird (κ, λ), schreiben wir A ⊨ σ für A ist ein Modell von σ, und ⊨ σ für σ ist gültig, dh für alle A, A. ⊨ σ. Wenn Δ ⊆ gesendet wird (κ, λ), schreiben wir Δ ⊨ σ für σ ist eine logische Konsequenz von Δ, dh jedes Modell von Δ ist ein Modell von σ.

Wir geben nun einige Beispiele, um die Ausdruckskraft der unendlichen Sprachen L (κ, λ) mit κ ≥ ω ₁ darzustellen. In jedem Fall ist bekannt, dass der betreffende Begriff in keiner Sprache erster Ordnung ausgedrückt werden kann.

Charakterisierung des Standardmodells der Arithmetik in L (ω ₁, ω). Hier ist das Standardmodell der Arithmetik die Struktur N = ⟨N, +, ·, s, 0⟩, wobei N die Menge der natürlichen Zahlen ist, +, · und 0 ihre übliche Bedeutung haben und s die Nachfolgeoperation ist. Sei L die für N geeignete Sprache erster Ordnung. Dann fällt die Klasse der zu N isomorphen L-Strukturen mit der Klasse der Modelle der Konjunktion der folgenden L (ω ₁, ω) -Sätze zusammen (wobei 0 ein Name von 0 ist):

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

Die Begriffe s ⁿ x werden rekursiv durch definiert

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

Charakterisierung der Klasse aller endlichen Mengen in L (ω ₁, ω). Hier hat die Basissprache keine extralogischen Symbole. Die Klasse aller endlichen Mengen fällt dann mit der Klasse der Modelle des L (ω ₁, ω) -Satzes zusammen

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

Wahrheitsdefinition in L (ω ₁, ω) für eine zählbare Basissprache L. Sei L eine zählbare Sprache erster Ordnung (zum Beispiel die Sprache der Arithmetik oder der Mengenlehre), die für jede natürliche Zahl n einen Namen n enthält, und sei σ ₀, σ ₁,… eine Aufzählung seiner Sätze. Dann die L (ω ₁, ω) -Formel

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

ist insofern ein Wahrheitsprädikat für L, als der Satz

Tr (n) ↔ σ _n

ist gültig für jedes n.

Charakterisierung von Well-Ordnungen in L (ω ₁, ω ₁). Die Basissprache L enthält hier ein binäres Prädikatsymbol ≤. Sei σ ₁ der übliche L-Satz, der lineare Ordnungen charakterisiert. Dann stimmt die Klasse der L-Strukturen, in der die Interpretation von ≤ eine gute Ordnung ist, mit der Klasse der Modelle des Satzes L (ω ₁, ω ₁) σ = σ ₁ ∧ σ ₂ überein, wobei

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

Beachten Sie, dass der Satz σ ₂ einen unendlichen Quantifizierer enthält: Er drückt die im Wesentlichen Behauptung zweiter Ordnung aus, dass jede zählbare Teilmenge ein kleinstes Mitglied hat. Es kann tatsächlich gezeigt werden, dass das Vorhandensein dieses unendlichen Quantifizierers wesentlich ist: Die Klasse gut geordneter Strukturen kann in keiner Sprache endlicher Quantifizierer charakterisiert werden. Dieses Beispiel zeigt, dass sich Sprachen mit unendlichen Quantifizierern wie L (ω ₁, ω ₁) eher wie Sprachen zweiter Ordnung verhalten. wir werden sehen, dass sie die Mängel der letzteren (Unvollständigkeit) sowie einige ihrer Vorteile (starke Ausdruckskraft) teilen.

Viele Erweiterungen von Sprachen erster Ordnung können in unendliche Sprachen übersetzt werden. Betrachten Sie zum Beispiel die verallgemeinerte Quantifizierersprache L (Q ₀), die aus L erhalten wird, indem Sie ein neues Quantifizierersymbol Q ₀ hinzufügen und Q ₀ x φ (x) interpretieren, da unendlich viele x existieren, so dass φ (x). Es ist leicht zu erkennen, dass der Satz Q ₀ x φ (x) die gleichen Modelle wie der L (ω ₁, ω) -Satz hat

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

Somit ist L (Q ₀) im natürlichen Sinne in L (ω ₁, ω) übersetzbar. Eine andere Sprache, die in diesem Sinne in L (ω ₁, ω) übersetzbar ist, ist die schwache Sprache zweiter Ordnung, die durch Hinzufügen eines zählbaren Satzes monadischer Prädikatvariablen zu L erhalten wird, die dann so interpretiert werden, dass sie sich über alle endlichen Sätze von Individuen erstrecken.

Es können auch Sprachen mit beliebig langen Konjunktionen, Disjunktionen und (möglicherweise) Quantifizierungen eingeführt werden. Für einen festen unendlichen Kardinal λ wird die Sprache L (∞, λ) definiert, indem ihre Klasse von Formeln, Form (∞, λ), als die Vereinigung über alle κ ≥ λ der Mengen Form (κ, λ) spezifiziert wird). Somit erlaubt L (∞, λ) beliebig lange Konjunktionen und Disjunktionen in dem Sinne, dass, wenn Φ eine beliebige Teilmenge der Form (∞, λ) ist, sowohl ∧Φ als auch ∨Φ Mitglieder der Form (∞, λ) sind. Aber L (∞, λ) lässt nur Quantifizierungen der Länge <λ zu: Alle seine Formeln haben <λ freie Variablen. Die Sprache L (∞, ∞) wird wiederum definiert, indem ihre Klasse von Formeln, Form (∞, ∞), als Vereinigung aller Klassen über alle unendlichen Kardinäle λ spezifiziert wird Form (∞, λ). L (∞, ∞) erlaubt also beliebig lange Quantifizierungen zusätzlich zu beliebig langen Konjunktionen und Disjunktionen. Beachten Sie, dass Form (∞, λ) und Form (∞, ∞) richtige Klassen im Sinne der Gödel-Bernays-Mengenlehre sind. Die Zufriedenheit der Formeln von L (∞, λ) und L (∞, ∞) in einer Struktur kann durch eine offensichtliche Erweiterung des entsprechenden Begriffs für L (κ, λ) definiert werden.

2. Sprachen mit endlichen Quantifizierern

Wir haben bemerkt, dass Sprachen mit unendlichen Quantifizierern wie L (ω ₁, ω ₁) Sprachen zweiter Ordnung ähneln, da sie die Quantifizierung über unendliche Mengen von Individuen ermöglichen. Die Tatsache, dass dies in Sprachen mit endlichen Quantifizierern nicht zulässig ist, legt nahe, dass diese in gewisser Hinsicht näher an ihren Gegenstücken erster Ordnung liegen als auf den ersten Blick ersichtlich. Wir werden sehen, dass dies tatsächlich der Fall ist, insbesondere im Fall von L (ω ₁, ω).

Die Sprache L (ω ₁, ω) nimmt unter den unendlichen Sprachen einen besonderen Platz ein, weil sie - wie Sprachen erster Ordnung - einen wirksamen deduktiven Apparat zulässt. In der Tat wollen wir zu den üblichen Axiomen und Inferenzregeln erster Ordnung das neue Axiomschema hinzufügen

∧Φ → φ

für jede zählbare Menge Φ Φ Form (ω ₁, ω) und jede φ ∈ Φ zusammen mit der neuen Inferenzregel

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

∧ n ∈ω φ n

und erlauben, dass Abzüge von zählbarer Länge sind. Wenn wir ⊢ * für die Ableitbarkeit in diesem Sinne schreiben, haben wir dann die

L (ω ₁, ω) - Vollständigkeitssatz. Für jedes gesendete σ ∈ (ω ₁, ω) gilt ⊨ σ ⇔ ⊢ * σ

Als unmittelbare Folge schließen wir, dass dieser deduktive Apparat für Abzüge von zählbaren Mengen von Prämissen in L (ω ₁, ω) geeignet ist. Das heißt, mit der offensichtlichen Erweiterung der Notation haben wir für jede zählbare Menge Δ ⊆ Sent (ω ₁, ω)

(2.1) Δ ⊨ σ ⇔ Δ⊢ * σ

Dieser Vollständigkeitssatz kann durch Modifizieren des üblichen Henkin-Vollständigkeitsnachweises für Logik erster Ordnung oder durch Anwendung boolesch-algebraischer Methoden bewiesen werden. Ähnliche Argumente, die auf geeignete weitere Erweiterungen der Axiome und Inferenzregeln angewendet werden, ergeben analoge Vollständigkeitssätze für viele andere Sprachen mit endlichen Quantifizierern.

Wenn nur Abzüge von zählbarer Länge zugelassen werden, kann kein deduktiver Apparat für L (ω ₁, ω) eingerichtet werden, der für Abzüge von beliebigen Mengen von Prämissen geeignet ist, dh für die (2.1) für jede Menge Δ gelten würde ⊆ Gesendet (ω ₁, ω), unabhängig von der Kardinalität. Dies folgt aus der einfachen Beobachtung, dass es eine Sprache erster Ordnung L und eine unzählige Menge Γ von L (ω ₁, ω) -Sätzen gibt, so dass Γ kein Modell hat, aber jede zählbare Teilmenge von Γ. Um dies zu sehen, sei L die Sprache der Arithmetik, ergänzt durch ω ₁ neue konstante Symbole { c _ξ: ξ <ω ₁ }, und sei Γ die Menge der L (ω ₁, ω) -Sätze {σ} ∪ { c_{& xi;} & ne; c _η: ξ ≠ η}, wobei σ die L (ω ₁, ω) -sentence das Standardmodell der arithmetischen charakterisieren. Dieses Beispiel zeigt auch, dass der Kompaktheitssatz für L (ω ₁, ω) und damit auch für jedes L (κ, λ) mit κ ≥ ω ₁ fehlschlägt.

Ein weiteres Ergebnis, das im Fall erster Ordnung gilt, aber für L (κ, ω) mit κ ≥ ω ₁ (und auch für L (ω ₁, ω ₁), obwohl dies schwieriger zu beweisen ist) fehlschlägt, ist die Prenex-Normalform Satz. Ein Satz ist prenex, wenn alle seine Quantifizierer vorne erscheinen; Wir geben ein Beispiel für einen L (ω ₁, ω) -Satz, der nicht einer Konjunktion von Prenex-Sätzen entspricht. Sei L die Sprache erster Ordnung ohne extralogische Symbole und sei σ der L (ω ₁, ω) -Satz, der die Klasse der endlichen Mengen charakterisiert. Angenommen, σ wäre äquivalent zu einer Konjunktion

∧ _{i ∈ I} σ _i

von Prenex L (ω ₁, ω) -Sätzen σ _i. Dann hat jedes σ _i die Form

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

wobei jedes Q _k ∀ oder ∃ ist und φ _i eine (möglicherweise unendliche) Konjunktion oder Disjunktion von Formeln der Form x _k = x _l oder x _k ≠ x _{l ist}. Da jedes σ _i ein Satz ist, gibt es in jedem φ _i nur endlich viele Variablen, und es ist leicht zu erkennen, dass jedes φ _i dann einer Formel erster Ordnung entspricht. Dementsprechend kann jedes σ _i als Satz erster Ordnung angesehen werden. Da angenommen wird, dass σ der Konjunktion von σ _i äquivalent ist, folgt, dass σ und die Menge Δ = {σ _i: i ∈ I} haben die gleichen Modelle. Aber offensichtlich haben σ und damit auch Δ Modelle aller endlichen Kardinalitäten; Der Kompaktheitssatz für Sätze von Sätzen erster Ordnung impliziert nun, dass Δ und damit auch σ ein unendliches Modell hat, das der Definition von σ widerspricht.

Wenn wir uns dem Löwenheim-Skolem-Theorem zuwenden, stellen wir fest, dass die Abwärtsversion angemessene Verallgemeinerungen für L (ω ₁, ω) (und in der Tat für alle unendlichen Sprachen) aufweist. Tatsächlich kann man auf die gleiche Weise wie für Sätze von Sätzen erster Ordnung zeigen, dass wenn Δ ⊆ Gesendet (ω ₁, ω) ein unendliches Kardinalitätsmodell ≥ | Δ | hat, es ein Kardinalitätsmodell hat, das größer ist als ℵ ₀, | Δ |. Insbesondere hat jeder L (ω ₁, ω) -Satz mit einem unendlichen Modell ein zählbares Modell.

Andererseits scheitert der aufwärts gerichtete Löwenheim-Skolem-Satz in seiner üblichen Form für alle unendlichen Sprachen. Zum Beispiel hat der L (ω ₁, ω) -Satz, der das Standardmodell der Arithmetik charakterisiert, ein Kardinalitätsmodell ℵ _0, aber keine Modelle einer anderen Kardinalität. Hier ist jedoch nicht alles verloren, wie wir sehen werden.

Wir definieren die Hanf-Zahl h (L) einer Sprache L als den kleinsten Kardinal κ, so dass ein L- Satz, wenn er ein Kardinalitätsmodell κ hat, Modelle beliebig großer Kardinalität hat. Die Existenz von h (L) ist leicht festzustellen. Für jeden L- Satz σ, der keine Modelle mit beliebig großer Kardinalität besitzt, sei κ (σ) der kleinste Kardinal κ, so dass σ kein Modell der Kardinalität κ hat. Wenn λ das Supremum aller κ (σ) ist, dann hat ein Satz von L, wenn er ein Kardinalitätsmodell λ hat, Modelle beliebig großer Kardinalität.

Definieren Sie die Kardinäle μ (α) rekursiv durch

μ (0)	=	ℵ 0
μ (α + 1)	=	2 μ (α)
μ (λ)	=	∑ α <λ μ (α) für die Grenze λ.

Dann kann das gezeigt werden

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

Ähnliche Ergebnisse gelten für andere Sprachen mit endlichen Quantifizierern. Die Werte der Hanf-Zahlen von Sprachen mit unendlichen Quantifizierern wie L (ω ₁, ω ₁) sind empfindlich gegenüber dem Vorhandensein oder Nichtvorhandensein großer Kardinäle, müssen jedoch in jedem Fall die von L (ω ₁, ω) stark überschreiten.

Ein Ergebnis für L, das auf L (ω ₁, ω), aber auf keine andere unendliche Sprache verallgemeinert wird, ist das

Craig-Interpolationssatz: Wenn σ, τ ∈ gesendet (ω ₁, ω) so sind, dass ⊨ σ → τ, dann gibt es θ ∈ gesendet (ω ₁, ω), so dass ⊨ σ → θ und ⊨ θ → τ und jeweils Das in θ vorkommende extralogische Symbol tritt sowohl in σ als auch in τ auf.

Der Beweis ist eine einigermaßen einfache Erweiterung des Falls erster Ordnung.

Schließlich erwähnen wir ein weiteres Ergebnis, das sich gut auf L (ω ₁, ω), aber auf keine andere unendliche Sprache verallgemeinern lässt. Es ist bekannt, dass, wenn A eine endliche L-Struktur mit nur endlich vielen Beziehungen ist, es einen L-Satz σ gibt, der A bis zum Isomorphismus charakterisiert. Für L (ω ₁, ω) haben wir die folgende Verallgemeinerung bekannt als

Scotts Isomorphismus-Theorem. Wenn A eine zählbare L-Struktur mit nur zählbar vielen Beziehungen ist, dann gibt es einen L (ω ₁, ω) -Satz, dessen Klasse zählbarer Modelle mit der Klasse der L-Strukturen übereinstimmt, die mit A isomorph sind.

Die Beschränkung auf zählbare Strukturen ist wesentlich, da die Zählbarkeit im Allgemeinen nicht durch einen L (ω ₁, ω) -Satz ausgedrückt werden kann.

Die Sprache L (∞, ω) kann auch als Sprache mit endlichen Quantifizierern gezählt werden. Das Konzept der Äquivalenz von Strukturen in Bezug auf diese Sprache ist von besonderer Bedeutung: Wir nennen zwei (ähnliche) Strukturen A und B (∞, ω) - äquivalent, geschrieben A ≡ _∞ω B, wenn die gleichen Sätze von L (∞, ω) arretiert in A und B. Diese Beziehung kann zunächst durch den Begriff des partiellen Isomorphismus charakterisiert werden. Ein partieller Isomorphismus zwischen A und B ist eine nicht leere Familie P von Karten, so dass:

• Für jedes p ∈ P ist dom (p) eine Unterstruktur von A, ran (p) ist eine Unterstruktur von B und p ist ein Isomorphismus seiner Domäne auf seinen Bereich; und
• Wenn p ∈ P, a ∈ A, b ∈ B, dann gibt es r, s ∈ P, die beide p so erweitern, dass a ∈ dom (r), b ∈ ran (s) (Eigenschaft „hin und her“).

Wird ein Teil Isomorphismus zwischen existiert A und B, sagen wir, dass A und B sind teilweise isomorph und Schreib A ≅ _p B. Wir haben dann

Karps partieller Isomorphismus-Satz.

Für alle ähnliche Strukturen A, B, A ≡ _∞ω B ⇔ A ≅ _P B.

Es gibt auch eine Version von Scotts Isomorphismus-Theorem für L (∞, ω), nämlich

(2.2) Da jede Struktur A gibt es einen L (∞, ω) -sentence σ, so dass für alle Strukturen B, A ≅ _p B ⇔ B ⊨ σ.

Partieller Isomorphismus und (∞, ω) -Äquivalenz hängen mit dem Begriff des Booleschen Isomorphismus zusammen. Um dies zu definieren, müssen wir die Idee eines Booleschen Modells der Mengenlehre einführen. Bei einer vollständigen Booleschen Algebra B wird das Universum V ^(B) von B-Wert-Mengen, auch als B-Erweiterung des Universums V von Mengen bekannt, erhalten, indem zunächst rekursiv auf α definiert wird.

V _α ^(B) = {x: x ist eine Funktion ∧ Bereich (x) ⊆ B ∧ <ξ <α [Domäne (x) ⊆ V _ξ ^(B)]}

und dann einstellen

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

Mitglieder von V ^(B) werden B-Wert-Mengen genannt. Es ist nun leicht zu erkennen, dass eine Menge mit B-Wert genau eine Funktion mit B-Wert ist, wobei eine Menge von Mengen mit B-Wert eine Domäne ist. Nun sei L die Sprache erster Ordnung der Mengenlehre und L ^(B) die Sprache, die durch Hinzufügen eines Namens für jedes Element von V ^(B) zu L erhalten wird (wir werden das gleiche Symbol für das Element und seinen Namen verwenden).. Man kann nun eine Abbildung [·] ^(B) der (Sätze der) Sprache L ^(B) in B erstellen: Für jeden Satz σ von L ^(B) ist das Element [σ] ^(B) von B das „ Boolescher Wahrheitswert”von σ in V ^(B). Diese Abbildung [·] ^(B) ist so definiert, dass alle Sätze der Zermelo-Fraenkel-Mengenlehre an das oberste Element 1 von B gesendet werden, dh an die „Wahrheit“; Dementsprechend kann V ^(B) als ein Boolesches Modell der Mengenlehre angesehen werden. Wenn [σ] ^(B) = 1 ist, sagen wir im Allgemeinen, dass σ in V ^(B) gültig ist, und schreiben V ^(B) ⊨ σ.

Jetzt hat jedes x ∈ V einen kanonischen Repräsentanten x in V ^(B), der erfüllt

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

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

Wir sagen, dass zwei ähnliche Strukturen A, B boolesch isomorph sind, geschrieben A ≅ _b B, wenn wir für eine vollständige Boolesche Algebra B V ^(B) ⊨ A ≅ B haben, dh wenn es eine boolesche Erweiterung von gibt Universum von Mengen, in denen die kanonischen Repräsentanten von A und B mit dem Booleschen Wert 1 isomorph sind. Es kann dann gezeigt werden, dass:

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

Dieses Ergebnis kann durch kategorietheoretische Formulierung verstärkt werden. Dazu benötigen wir das Konzept eines (n) (elementaren) Topos. Um dieses Konzept einzuführen, beginnen wir mit der familiären Kategorie Set von Sets und Mappings. Set hat die folgenden Schlüsseleigenschaften:

1. Es gibt ein "Terminal" -Objekt 1, so dass es für jedes Objekt X eine eindeutige Karte X → 1 gibt (für 1 können wir eine beliebige Ein-Element-Menge nehmen, insbesondere {0}).
2. Jedes Objektpaar X, Y hat ein kartesisches Produkt X × Y.
3. Für jedes Objektpaar kann man aus X → Y das „exponentielle“Objekt Y ^X aller Karten bilden.
4. Es gibt ein "Wahrheitswert" -Objekt Ω, so dass für jedes Objekt X eine natürliche Entsprechung zwischen Unterobjekten (Teilmengen) von X und Karten X → Ω besteht. (Für Ω können wir die Menge 2 = {0,1} nehmen; Karten X → Ω sind dann charakteristische Funktionen auf X.)

Alle vier Bedingungen können in kategorietheoretischer Sprache formuliert werden - eine Kategorie, die sie erfüllt, wird als Topos bezeichnet. Die Kategorie Set ist ein Topos; ebenso (i) die Kategorie Menge ^(B) von Mengen und Zuordnungen mit Booleschen Werten in jeder Booleschen Erweiterung V ^(B) des Universums von Mengen; (ii) die Kategorie von Garben von Mengen auf einem topologischen Raum; (iii) die Kategorie aller Diagramme von Karten von Mengen

X ₀ → X ₁ → X ₂ →…

Die Objekte jeder dieser Kategorien können als Mengen betrachtet werden, die auf irgendeine Weise variieren: im Fall (i) über eine Boolesche Algebra; im Fall (ii) über einem topologischen Raum; im Fall (iii) über (diskrete) Zeit. Ein Topos kann also als ein Universum von „variablen“Mengen verstanden werden. Die bekannte Kategorie Set ist der spezielle Grenzfall eines Topos, bei dem die „Variation“der Objekte auf Null reduziert wurde.

Genau wie in der Mengenlehre können in jedem Topos „logische Operatoren“für das Wahrheitswertobjekt definiert werden. Dies sind Karten ¬: Ω → Ω; ∧, ∨, ⇒: Ω × Ω → Ω entsprechend den logischen Operationen Negation, Konjunktion, Disjunktion und Implikation. Mit diesen Operationen wird Ω zu einer Heyting-Algebra, die im Allgemeinen die Gesetze nicht der klassischen, sondern der intutionistischen Logik verkörpert. In diesem Sinne wird intuitionistische Logik in einem Topos „verinnerlicht“: Intuitionistische Logik ist die Logik von Variablensätzen. (Natürlich wird die klassische Logik in bestimmten Toposen verinnerlicht, zum Beispiel Set und Set ^(B) für jede vollständige Boolesche Algebra B.)

Beliebige Topos können als mögliches „Diskursuniversum“konzipiert werden, in dem mathematische Aussagen interpretiert und mathematische Konstruktionen ausgeführt werden können. Mathematische Aussagen werden in einem Topos E durch Ausdruck in der internen Sprache von E interpretierbar gemacht - einer typentheoretischen Version der üblichen Sprache der Mengenlehre. In analoger Weise zur Booleschen Gültigkeit kann man in E einen geeigneten Begriff der Gültigkeit eines Satzes σ seiner inneren Sprache einführen. Wieder schreiben wir E ⊨ σ für "σ ist gültig in E".

Ein Topos E gilt als voll, wenn für jede Menge I die I-fache Kopower ^[3] ∐ _I 1 seines Endobjekts in E existiert. ∐ _I 1 kann als kanonischer Vertreter in E der Menge angesehen werden ICH; dementsprechend schreiben wir es einfach so wie ich. (In V ^(B) stimmt dies mit I überein, wie zuvor definiert.) Alle oben genannten Topos sind voll.

Nun sei E ein voller Topos. Wenn A = (A, R,…) eine Struktur ist, schreiben Sie A für (A, R,…). Zwei Strukturen A und B werden als toposisomorph bezeichnet, geschrieben als A ≅ _t B, wenn für einige Topos E, die über die Kategorie von Mengen definiert sind, E ⊨ A ≅ B gilt. Mit anderen Worten, zwei Strukturen sind Topos isomorph, wenn ihre kanonischen Vertreter in der internen Sprache einiger Topos isomorph sind. Es kann dann gezeigt werden, dass

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

Dementsprechend kann die (∞, ω) -Äquivalenz als Isomorphismus im extrem allgemeinen Kontext von Universen von "variablen" Mengen angesehen werden. In dieser Hinsicht ist die (∞, ω) -Äquivalenz ein "invarianter" Begriff des Isomorphismus.

3. Die Kompaktheitseigenschaft

Wie wir gesehen haben, versagt der Kompaktheitssatz in seiner üblichen Form für alle unendlichen Sprachen. Dennoch ist es von Interesse festzustellen, ob unendliche Sprachen eine geeignet modifizierte Version des Satzes erfüllen. Dieses sogenannte Kompaktheitsproblem hat einen natürlichen Zusammenhang mit rein satztheoretischen Fragen, die „große“Kardinalzahlen betreffen.

Wir konstruieren die folgende Definition. Sei κ ein unendlicher Kardinal. Eine Sprache L wird als κ-kompakt (bzw. schwach κ-kompakt) bezeichnet, wenn Δ immer dann eine Menge von L- Sätzen (bzw. eine Menge von L- Sätzen der Kardinalität ≤ κ) und jede Teilmenge von Δ der Kardinalität <ist κ hat ein Modell, Δ auch. Beachten Sie, dass der übliche Kompaktheitssatz für L genau die Behauptung ist, dass L ω-kompakt ist. Ein Grund für die entsprechende Bedeutung der Eigenschaft der κ-Kompaktheit ist der folgende. Nenne L κ- vollständig (bzw. schwach κ-vollständig), wenn es ein deduktives System P für L mit Abzügen der Länge <κ gibt, so dass, wenn Δ eine P- konsistente ^[4] Menge von ist L- Sätze (bzw. so, dass | Δ | ≤ κ), dann hat Δ ein Modell. Beachten Sie, dass ein solches P für Abzüge von beliebigen Prämissensätzen (Kardinalität ≤ κ) im Sinne von §2 ausreichend ist. Es ist leicht zu erkennen, dass wenn L κ-vollständig oder schwach κ-vollständig ist, L κ-kompakt oder schwach κ-kompakt ist. Wenn wir also zeigen können, dass eine gegebene Sprache nicht (schwach) κ-kompakt ist, kann es kein deduktives System für sie geben, dessen Abzüge der Länge <κ für Abzüge von beliebigen Prämissenmengen (Kardinalität ≤ κ) angemessen sind.

Es stellt sich tatsächlich heraus, dass die meisten Sprachen L (κ, λ) nicht einmal schwach κ-kompakt sind, und für diejenigen, die es sind, muss κ ein außerordentlich großer Kardinal sein. Wir werden einige Definitionen brauchen.

Ein unendlicher Kardinal κ soll schwach unzugänglich sein, wenn

(a) λ <κ → λ ⁺ <κ (wobei λ ⁺ den Kardinalnachfolger von λ bezeichnet) und

b) | Ich | <κ und λ _i <κ (für alle i ∈ I) ⇒ ∑ _{i ∈ I} λ _i <κ.

Wenn zusätzlich

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

dann soll κ (stark) unzugänglich sein. Da ℵ _{0 nicht} zugänglich ist, ist es üblich, die Aufmerksamkeit auf diejenigen unzugänglichen oder schwach unzugänglichen Kardinäle zu beschränken, die ℵ ₀ überschreiten. Dementsprechend werden unzugängliche oder schwach unzugängliche Kardinäle immer als unzählig angesehen. Es ist klar, dass solche Kardinäle - wenn sie existieren - extrem groß sein müssen; und tatsächlich impliziert der Gödel-Unvollständigkeitssatz, dass die Existenz selbst schwach unzugänglicher Kardinäle nicht mit den üblichen Axiomen der Mengenlehre bewiesen werden kann.

Nennen wir einen Kardinal κ compact (bzw. schwach kompakt), wenn die Sprache L (κ, κ) κ-kompakt ist (bzw. schwach κ-kompakt). Dann haben wir folgende Ergebnisse:

(3.1) ℵ ₀ ist kompakt. Dies ist natürlich nur eine prägnante Art, den Kompaktheitssatz für Sprachen erster Ordnung auszudrücken.

(3.2) κ ist schwach kompakt ⇒ L (κ, ω) ist schwach κ- kompakt ⇒ κ ist schwach unzugänglich. Dementsprechend ist es konsistent (mit den üblichen Axiomen der Mengenlehre) anzunehmen, dass keine Sprache L (κ, ω) mit κ ≥ ω ₁ schwach κ-kompakt oder erst recht schwach κ-vollständig ist.

(3.3) Angenommen, κ ist nicht zugänglich. Dann ist κ schwach kompakt ⇔ L (κ, ω) ist schwach κ-kompakt. Auch ist auch κ schwach kompakt ⇒ es gibt eine Menge von κ unzugänglich vor κ. Somit ist ein schwach kompakter unzugänglicher Kardinal außerordentlich groß; insbesondere kann es nicht der erste, zweite,…, n- ^te,… unzugänglich sein.

(3.4) κ ist kompakt ⇒ κ ist nicht zugänglich. (Aber durch das Ergebnis unmittelbar oben schlägt das Gegenteil fehl.)

Lassen Sie Constr für Gödels Axiom der Konstruierbarkeit stehen; Denken Sie daran, dass Constr mit den üblichen Axiomen der Mengenlehre übereinstimmt.

(3.5) Wenn Constr hält, gibt es keine kompakten Kardinäle.

(3.6) Nehmen Sie Constr an und lassen Sie κ unzugänglich sein. Dann ist κ schwach kompakt ⇔ L (ω ₁, ω) ist für alle L schwach κ-kompakt.

(3.7) Wenn Constr gilt, gibt es keine Kardinäle κ, für die L (ω ₁, ω) kompakt ist. Dementsprechend stimmt es mit den üblichen Axiomen der Mengenlehre überein anzunehmen, dass es keinen Kardinal κ gibt, so dass alle Sprachen L (ω ₁, ω) κ-vollständig sind. Diesem Ergebnis steht die Tatsache gegenüber, dass alle Sprachen erster Ordnung ω-vollständig sind.

Die Bedeutung dieser Ergebnisse besteht darin, dass der Kompaktheitssatz für die meisten Sprachen L (κ, λ) mit κ ≥ ω ₁ sehr schlecht versagt.

Einige historische Bemerkungen sind hier angebracht. In den 1930er Jahren untersuchten Mathematiker verschiedene Versionen des sogenannten Maßproblems für Mengen, ein Problem, das im Zusammenhang mit der Theorie des Lebesgue-Maßes auf dem Kontinuum auftrat. Insbesondere wurde der folgende sehr einfache Maßbegriff formuliert. Wenn X eine Menge ist, ist ein (zählbar additives zweiwertiges nichttriviales) Maß auf X eine Abbildung μ auf der Potenzmenge P X auf die Menge {0, 1}, die erfüllt:

(a) μ (X) = 1, (b) μ ({x}) = μ (∅) = 0 für alle x ∈ X und

(c) Wenn A eine zählbare Familie von voneinander getrennten Teilmengen von X ist, dann ist μ (∪ A) = ∑ {μ (Y): Y ∈ A }.

Ob ein gegebener Satz ein solches Maß unterstützt, hängt natürlich nur von seiner Kardinalität ab. Daher ist es natürlich, einen Kardinal κ als messbar zu definieren, wenn alle Sätze von Kardinalität κ ein Maß dieser Art unterstützen. Es wurde schnell klar, dass ein messbarer Kardinal unzugänglich sein muss, aber die Falschheit der Umkehrung wurde erst in den 1960er Jahren festgestellt, als Tarski zeigte, dass messbare Kardinäle schwach kompakt sind und sein Schüler Hanf zeigte, dass der erste, zweite usw. unzugänglich nicht schwach ist kompakt (vgl. (3.3)). Obwohl die Schlussfolgerung, dass messbare Kardinäle ungeheuer groß sein müssen, heute normalerweise bewiesen wird, ohne den Umweg durch schwache Kompaktheit und unendliche Sprachen zu machen, bleibt die Tatsache bestehen, dass diese Ideen in erster Linie verwendet wurden, um das Ergebnis zu ermitteln.

4. Unvollständigkeit von Infinite-Quantifier-Sprachen

Das wahrscheinlich wichtigste Ergebnis bei Sprachen erster Ordnung ist der Gödel-Vollständigkeitssatz, der natürlich besagt, dass die Menge aller gültigen Formeln einer Sprache erster Ordnung L aus einer einfachen Menge von Axiomen mit Hilfe einiger einfacher Regeln von erzeugt werden kann Inferenz. Eine Hauptfolge dieses Theorems ist, dass, wenn die Formeln von L auf konstruktive Weise als natürliche Zahlen codiert werden, die Menge von (Codes von) gültigen Sätzen rekursiv aufzählbar ist. Die Vollständigkeit einer Sprache erster Ordnung impliziert daher, dass die Menge ihrer gültigen Sätze auf besonders einfache Weise definierbar ist. Dementsprechend erscheint es angesichts einer beliebigen Sprache L vernünftig, diese Implikation umzukehren und vorzuschlagen, dass, wenn die Menge des gültigen L gilt-Sätze sind nicht auf einfache Weise definierbar, dann kann für L kein aussagekräftiges Vollständigkeitsergebnis festgestellt werden, oder, wie wir noch sagen werden, dass L unvollständig ist. In diesem Abschnitt werden wir diesen Vorschlag verwenden, um einen Beweis zu skizzieren, dass „die meisten“unendlichen Quantifizierersprachen in diesem Sinne unvollständig sind.

Lassen Sie uns zunächst den formalen Begriff der Definierbarkeit wie folgt einführen. Wenn L eine Sprache, A eine L- Struktur und X eine Teilmenge der Domäne A von A ist, sagen wir, dass X in A durch eine Formel φ (x, y ₁,…, y _n) von L definiert werden kann, wenn es vorhanden ist ist eine Folge a ₁,…, a _n von Elementen von A, so dass X die Teilmenge aller Elemente x ∈ A ist, für die φ (x, a ₁,…, a _n) in A gilt.

Schreiben Sie nun Val (L) für die Menge aller gültigen L- Sätze, dh derjenigen, die in jeder L- Struktur enthalten sind. Um der Aussage „Val (L) ist definierbar“eine Bedeutung zuzuweisen, müssen wir angeben

1. eine Struktur C (L) - die Codierungsstruktur für L;
2. eine bestimmte Eins-Eins-Karte - die Codierungskarte - des Satzes von Formeln von L in die Domäne von C (L).

Wenn wir dann Val (L) mit seinem Bild in C (L) unter der Codierungskarte identifizieren, interpretieren wir die Aussage „Val (L) ist definierbar“als die Aussage „Val (L), die als Teilmenge der Die Domäne von C (L) ist in C (L) durch eine Formel von L definierbar. “

Wenn beispielsweise L die Sprache L erster Ordnung der Arithmetik ist, verwendete Gödel ursprünglich als Codierungsstruktur das Standardmodell der Arithmetik ℕ und als Codierungskarte die bekannte Funktion, die aus dem Primfaktorisierungssatz für natürliche Zahlen erhalten wurde. Die rekursive Aufzählbarkeit von Val (L) bedeutet dann einfach, dass der Satz von Codes ("Gödel-Zahlen") von Mitgliedern von Val (L) in ℕ durch eine L-Formel der Form ∃ y φ (x, y) definiert werden kann. wobei φ (x, y) eine rekursive Formel ist.

Eine andere äquivalente Codierungsstruktur für die Sprache erster Ordnung der Arithmetik ist die Struktur ^[5] ⟨H (ω), ∈ ⨡ H (ω)⟩ erblich endlicher Mengen, wobei eine Menge x erblich endlich ist, wenn x ihre Mitglieder sind, seine Mitglieder usw. sind alle endlich. Diese Codierungsstruktur berücksichtigt die Tatsache, dass Formeln erster Ordnung natürlich als endliche Mengen angesehen werden.

Wenn wir uns nun dem Fall zuwenden, in dem L eine unendliche Sprache L (κ, λ) ist, was wäre in diesem Fall eine geeignete Codierungsstruktur? Wir haben am Anfang bemerkt, dass unendliche Sprachen durch die Möglichkeit vorgeschlagen wurden, Formeln als satztheoretische Objekte zu betrachten. Versuchen wir also, unsere Codierungsstruktur zu erhalten, indem wir darüber nachdenken, welche Art von satztheoretischen Objekten wir als unendliche Formeln betrachten sollten. Angesichts der Tatsache, dass für jede φ∈- Form (κ, λ) φ und ihre Unterformeln, Unterformeln usw. alle die Länge <κ haben, ^[6]Die Reflexion eines Augenblicks zeigt, dass Formeln von L (κ, λ) Mengen x entsprechen, die erblich der Kardinalität <κ sind, in dem Sinne, dass x, seine Mitglieder, seine Mitglieder usw. alle Kardinalität <κ sind. Die Sammlung aller dieser Mengen ist H (κ) geschrieben. H (ω) ist die Sammlung der oben eingeführten erblich endlichen Mengen und H (ω ₁) die aller erblich zählbaren Mengen.

Nehmen wir der Einfachheit halber an, dass das einzige extralogische Symbol der Basissprache L das binäre Prädikatsymbol ∈ ist (die Diskussion kann leicht auf den Fall erweitert werden, in dem L zusätzliche extralogische Symbole enthält). Geleitet von den obigen Ausführungen nehmen wir als Codierungsstruktur für L (κ, λ) die Struktur,

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

Nun können wir die Codierungskarte der Form (κ, λ) in H (κ) definieren. Zunächst weisen wir jedem Grundsymbol s von L (κ, λ) ein ^{Codeobjekt ⌈} s ^⌉ ∈ H (κ) wie folgt zu. Sei {v _ξ: ξ <κ} eine Aufzählung der einzelnen Variablen von L (κ, λ).

Symbol	Codeobjekt	Notation
¬	1	⌈ ¬ ⌉
∧	2	⌈ ∧ ⌉
∧	3	⌈ ∧ ⌉
∃	4	⌈ ∃ ⌉
∈	5	⌈ ∈ ∈
=	6	⌈ = ⌉
v ξ	⟨0, ξ⟩	⌈ v ξ ξ

Dann ordnen wir jeder φ ∈ Form (κ, λ) das ^{Codeobjekt ⌈} φ ^⌉ rekursiv wie folgt zu:

^⌈ v _ξ = v _{& eegr;} ^⌉ = _df ⟨ ^⌈ v _ξ ^⌉, ^⌈ = ^⌉, ^⌈ v _{& eegr;} ^⌉ ⟩, ^⌈ v _{& xi;} ∈ V _{& eegr;} ^⌉ = _df ⟨ ^⌈ v _{& xi;} ^⌉, ^⌈ ∈ ^⌉, ^⌈ v _{& eegr;} ^⌉ ⟩;

für φ ψ ψ Form (κ, λ),

^⌈ & phiv; & psgr; ∧ ^⌉ = _df ⟨ ^⌈ & phiv; ^⌉, ^⌈ ∧ ^⌉, ^⌈ & psgr; ^⌉ ⟩

^⌈ ¬φ ^⌉ = _df ⟨ ^⌈ ¬ ^⌉, ^⌈ & phiv; ^⌉ ⟩

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

und schließlich, wenn Φ Φ Form (κ, λ) mit | Φ | <κ,

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

Die Abbildung φ ↦ ^⌈ φ ^⌉ von Form (κ, λ) in H (κ) ist leicht als Eins zu sehen und ist die erforderliche Codierungskarte. Dementsprechend stimmen wir zu, Val (L (κ, λ)) mit seinem Bild in H (κ) unter dieser Codierungskarte zu identifizieren.

Wann ist Val (L (κ, λ)) eine definierbare Teilmenge von H (κ)? Um diese Frage zu beantworten, benötigen wir die folgenden Definitionen.

Eine L-Formel wird als Δ ₀ - Formel bezeichnet, wenn sie einer Formel entspricht, in der alle Quantifizierer die Form ∀ x ∈ y oder ∃ x ∈ y (dh ∀ x (x ∈ y →…) oder ∃ x haben (x ∈ y ∧…)). Eine L-Formel ist eine Σ ₁ - Formel, wenn sie einer entspricht, die aus Atomformeln und ihren Negationen nur mit den logischen Operatoren ∧, ∨, ∀ x ∈ y, ∃ x aufgebaut werden kann. Eine Teilmenge X einer Menge A heißt Δ ₀ (bzw. Σ ₁) auf A, wenn sie in der Struktur ⟨A, ∈ ∈ A⟩ durch eine Δ ₀ - (bzw. Σ ₁ -) Formel von L definierbar ist.

Wenn wir zum Beispiel die Menge der natürlichen Zahlen auf übliche Weise mit der Menge H (ω) erblich endlicher Mengen identifizieren, dann haben wir für jedes X ⊆ H (ω):

X ist Δ ₀ auf H (ω) ⇔ X ist rekursiv

X ist Σ ₁ auf H (ω) ⇔ X ist rekursiv aufzählbar.

Somit können die Begriffe von Δ ₀ - und Σ ₁ -Satz als Verallgemeinerungen der Begriffe von rekursiver bzw. rekursiv aufzählbarer Menge angesehen werden.

Der Vollständigkeitssatz für L impliziert, dass Val (L) - als Teilmenge von H (ω) betrachtet - rekursiv aufzählbar ist und daher Σ ₁ für H (ω). In ähnlicher Weise impliziert der Vollständigkeitssatz für L (ω ₁, ω) (siehe §2), dass Val (L (ω ₁, ω)) - als Teilmenge von H (ω ₁) betrachtet - Σ ₁ auf H (ω _{1) ist}). Dieser angenehme Zustand bricht jedoch vollständig zusammen, sobald L (ω ₁, ω ₁) erreicht ist. Denn man kann beweisen

Scotts Undefinierbarkeitssatz für L (ω ₁, ω ₁). Val (L (ω ₁, ω ₁)) ist in H (ω ₁) selbst durch eine L (ω ₁, ω ₁) - Formel nicht definierbar; daher ist ein Fortiori Val (L (ω ₁, ω ₁)) nicht Σ ₁ auf H (ω ₁).

Dieser Satz wird auf die gleiche Weise bewiesen wie das bekannte Ergebnis, dass die Menge der (Codes von) gültigen Sätzen der Sprache zweiter Ordnung der arithemetischen L ² in ihrer Codierungsstruktur ℕ nicht zweiter Ordnung definierbar ist. Um dieses letztere Ergebnis zu erhalten, beobachtet man zuerst, dass ℕ durch einen einzelnen L ² -Satz gekennzeichnet ist, und zeigt dann, dass, wenn das Ergebnis falsch wäre, die „Wahrheit in ℕ“für L ² -Sätze durch ein L ² definierbar wäre -Formel, wodurch Tarskis Theorem über die Undefinierbarkeit der Wahrheit verletzt wird.

Um Scotts Undefinierbarkeitssatz in der obigen Richtung zu beweisen, muss man folglich Folgendes feststellen:

(4.1) Charakterisierbarkeit der Codierungsstruktur H (ω ₁) in L (ω ₁, w ₁): Es ist ein L (ω ₁, ω ₁) -sentence τ ₀, so dass für alle L-Strukturen A, A ⊨ τ ₀ ⇔ A ≅ H (ω ₁).

(4.2) Undefinierbarkeit der Wahrheit für L (ω ₁, ω ₁) - Sätze in der Codierungsstruktur: Es gibt keine L (ω ₁, ω ₁) -Formel φ (v ₀), so dass für alle L (ω ₁, ω ₁) -Sätze σ, H (ω ₁) ⊨ σ↔φ (^⌈ σ ^⌉).

(4.3) Es gibt einen Term t (v ₀, v ₁) von L (ω ₁, ω ₁), so dass für jedes Satzpaar σ τ von L (ω ₁, ω ₁) H (ω ₁) ⊨ [t (^⌈ σ ^⌉, ^⌈ τ ^⌉) = ^⌈ σ → τ ^⌉].

(4.1) wird bewiesen, indem die satztheoretische Definition von H (ω ₁) analysiert und gezeigt wird, dass sie in L (ω ₁, ω ₁) „intern“formuliert werden kann. (4.2) ist ähnlich wie Tarskis Satz über die Undefinierbarkeit der Wahrheit für Sprachen erster oder zweiter Ordnung aufgestellt. (4.3) wird erhalten, indem die Definition der Codierungskarte σ σ ^⌈ σ ^⌉ in L (ω ₁, ω ₁) formalisiert wird.

Mit diesen Tatsachen können wir Scotts Undefinierbarkeitssatz auf folgende Weise erhalten. Angenommen, es wäre falsch; dann gäbe es eine L (ω ₁, ω ₁) -Formel θ (v ₀), so dass für alle L (ω ₁, ω ₁) -Sätze σ,

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

Sei τ ₀ der in (4.1) angegebene Satz. Dann haben wir für alle L (ω ₁, ω ₁) -Sätze σ,

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

so dass durch (4.4),

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

Wenn t der in (4.3) angegebene Term ist, würde sich daraus folgen

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

Schreiben Sie nun φ (v ₀) für die L (ω ₁, ω ₁) -Formel θ (t (^⌈ τ ₀ ^⌉, ^⌈ σ ^⌉)). Dann

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

widersprechen (4.2) und den Beweis vervollständigen.

Somit Val (L (ω ₁, w ₁)) nicht definierbar sogar durch einen L (ω ₁, ω ₁) - Formel, so erst recht L (ω ₁, ω ₁) ist unvollständig. Ähnliche Argumente zeigen, dass Scotts Undefinierbarkeitssatz weiterhin gilt, wenn ω ₁ durch einen Nachfolgekardinal κ ^{+ ersetzt wird}; dementsprechend sind die Sprachen L (κ ⁺, κ ⁺) alle unvollständig. ^[7]

5. Subsprachen von L (ω ₁, ω) und des Barwise Compactness Theorem

Angesichts dessen, was wir jetzt über unendliche Sprachen wissen, scheint es, dass L (ω ₁, ω) der einzige ist, der sich einigermaßen gut benimmt. Andererseits ist das Versagen des Kompaktheitssatzes, auf irgendeine nützliche Weise auf L (& ohgr; ₁, & ohgr;) zu verallgemeinern, ein schwerwiegender Nachteil, was Anwendungen betrifft. Versuchen wir, diesen Fehler genauer zu analysieren.

Wir erinnern uns an § 4, dass wir die Formeln einer Sprache erster Ordnung L als erblich endliche Mengen codieren können, dh als Mitglieder von H (ω). In diesem Fall ist jede endliche Menge von (Codes von) L-Sätzen auch ein Mitglied von H (ω), und daraus folgt, dass der Kompaktheitssatz für L in der folgenden Form angegeben werden kann:

(5.1) Wenn Δ ⊆ gesendet (L) so ist, dass jede Teilmenge Δ ₀ ⊆ Δ, Δ ₀ ∈ H (ω) ein Modell hat, hat Δ dies auch.

Nun ist bekannt, dass (5.1) eine unmittelbare Folge des verallgemeinerten Vollständigkeitssatzes für L ist, der in ähnlicher Form wie in (5.1) zur Behauptung wird:

(5.2) Wenn Δ ⊆ Sent (L) und σ ∈ Sent (L) Δ ⊨ σ erfüllen, gibt es einen Abzug D von σ von Δ, so dass D ∈ H (ω). ^[8]

In §2 haben wir bemerkt, dass der Kompaktheitssatz für L (ω ₁, ω) sehr stark versagt; Tatsächlich haben wir eine Menge Γ Γ Sent (ω ₁, ω) so konstruiert, dass

(5.3) Jede zählbare Teilmenge von Γ hat ein Modell, Γ jedoch nicht.

Denken Sie auch daran, dass wir den Begriff des Abzugs in L (ω ₁, ω) eingeführt haben; da solche Abzüge von zählbarer Länge sind, folgt aus (5.3) schnell, dass

(5.4) Es gibt einen Satz ^[9] σ ∈ Sent (ω ₁, ω), so dass Γ Γ σ, aber es gibt keinen Abzug von σ in L (ω ₁, ω) von Γ.

Nun können die Formeln von L (ω ₁, ω) als Mitglieder von H (ω ₁) codiert werden, und es ist klar, dass H (ω ₁) unter Bildung zählbarer Teilmengen und Sequenzen geschlossen wird. Dementsprechend können (5.3) und (5.4) geschrieben werden:

(5.3 bis) Jedes Γ ₀ ⊆ Γ, so dass Γ ₀ ∈ H (ω ₁) ein Modell hat, Γ jedoch nicht;

(5.4 bis) Es gibt einen Satz σ ∈ Sent (ω ₁, ω), so dass Γ Γ σ, aber es gibt keinen Abzug D ∈ H (ω ₁) von σ von Γ.

Daraus folgt, dass (5.1) und (5.2) fehlschlagen, wenn "L" durch "L (ω ₁, ω)" und "H (ω)" durch "H (ω ₁)" ersetzt wird. Darüber hinaus kann gezeigt werden, dass die Menge Γ Γ Sent (ω ₁, ω) in (5.3 bis) und (5.4 bis) auf H (ω ₁) als Σ _{1 angenommen werden kann}. Somit scheitern die Sätze über Kompaktheit und verallgemeinerte Vollständigkeit selbst für Σ ₁ -Sätze von L (ω ₁, ω) -Sätzen.

Wir sehen aus (5.4 bis), dass der Grund, warum der verallgemeinerte Vollständigkeitssatz für Σ ₁ -Sätze in L (ω ₁, ω) fehlschlägt, darin besteht, dass H (ω ₁) grob gesagt unter der Bildung von Abzügen nicht „geschlossen“wird aus Σ ₁ -Sätzen in H (ω ₁). Um dies zu beheben, erscheint es natürlich, H (ω ₁) durch Mengen A zu ersetzen, die in gewisser Weise unter der Bildung solcher Ableitungen geschlossen werden, und dann nur die Formeln zu betrachten, deren Codes in A sind.

Wir geben nun eine Skizze, wie dies getan werden kann.

Zunächst identifizieren wir die Symbole und Formeln von L (ω ₁, ω) mit ihren Codes in H (ω ₁) wie in §4. Für jede zählbare transitive ^[10] Menge A sei

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

Wir sagen, dass L _A eine Subsprache von L (ω ₁, ω) ist, wenn die folgenden Bedingungen erfüllt sind:

1. L ⊆ L _A.
2. wenn φ, ψ ψ L _A, dann φ ∧ ψ ∈ L _A und ¬φ ∈ L _A.
3. wenn φ ∈ L _A und x ∈ A, dann ist ∃ x φ ∈ L _A.
4. wenn φ (x) ∈ L _A und y ∈ A ist, dann ist φ (y) ∈ L _A.
5. wenn φ ∈ L _{A ist}, ist jede Unterformel von φ in L _A.
6. wenn Φ ⊆ L _A und Φ ∈ A, dann ∧Φ ∈ L _A.

Der Begriff des Abzugs in L _A wird in üblichen Weise definiert ist; Wenn Δ eine Menge von Sätzen von L _A und φ ∈ L _{A ist}, dann ist ein Abzug von φ von Δ in L _A ein Abzug von φ von Δ in L (ω ₁, ω), dessen Formel in L _{A steht}. Wir sagen, dass φ von Δ in L _A ableitbar ist, wenn es einen Abzug D von φ von Δ in L _{A gibt}; unter diesen Bedingungen schreiben wir Δ ⊢ _A φ. Im Allgemeinen wird D kein Mitglied von A sein; Um sicherzustellen, dass ein solcher Abzug in A zu finden ist, müssen A weitere Bedingungen auferlegt werden.

Sei A eine zählbare transitive eingestellt werden, dass L _A eine Subsprache von L (ω ₁, ω) und lassen Δ eine Menge von Sätzen von L sein _A. Wir sagen, dass A (oder durch Missbrauch der Terminologie L _A) Δ- geschlossen ist, wenn für eine Formel φ von L _A, so dass Δ ⊢ _A φ, ein Abzug D von φ von Δ vorliegt, so dass D ∈ A. Es kann gezeigt werden, dass die einzige zählbare Sprache, die für beliebiges Δ Δ-geschlossen ist, die Sprache erster Ordnung L ist, dh wenn A = H (ω). J. Barwise entdeckte jedoch, dass es zählbare Mengen A ⊆ H (ω ₁) gibt, deren entsprechende Sprachen L _A sich von L unterscheiden und dennoch für alle Σ ₁ Δ-geschlossen sind- Sätze von Sätzen Δ. Solche Mengen A werden zulässige Mengen genannt; grob gesagt handelt es sich um Erweiterungen der erblich endlichen Mengen, in denen die Rekursionstheorie - und damit die Beweistheorie - noch möglich ist (für die vollständige Definition siehe Abschnitt 5.1 unten).

Aus Barwise's Ergebnis erhält man sofort die

Barweiser Kompaktheitssatz. Sei A eine zählbare zulässige Menge und sei Δ eine Menge von Sätzen von L _A, die auf A Σ _{1 ist}. Wenn jedes Δ '⊆ Δ so ist, dass Δ' ∈ A ein Modell hat, dann tut dies auch Δ.

Das Vorhandensein von "Σ ₁ " zeigt an, dass dieser Satz eine Verallgemeinerung des Kompaktheitssatzes für rekursiv aufzählbare Sätze ist.

Eine andere Version des Barwise-Kompaktheitssatzes, die zur Konstruktion von Modellen der Mengenlehre nützlich ist, ist die folgende. Sei ZFC die übliche Menge von Axiomen für die Zermelo-Fraenkel-Mengen-Theorie, einschließlich des Axioms der Wahl. Dann haben wir:

5.5 Satz. Sei A eine zählbare transitive Menge, so dass A = ⟨A, ∈ ∈ A⟩ ein Modell von ZFC ist. Wenn Δ eine Menge von Sätzen von L _A ist, die in A durch eine Formel der Sprache der Mengenlehre definiert werden kann, und wenn jedes Δ '⊆ Δ so ist, dass Δ' ∈ A ein Modell hat, so tut dies auch Δ.

Abschließend geben wir eine einfache Anwendung dieses Theorems. Sei A = ⟨A, ∈ ∈ A⟩ ein Modell von ZFC. Ein Modell B = ⟨B, E⟩ von ZFC soll eine richtige Enderweiterung von A sein, wenn (i) A ⊆ B, (ii) A ≠ B, (iii) a ∈ A, b ∈ B, bEa ⇒ b ∈ A. Somit ist eine ordnungsgemäße Enderweiterung eines ZFC- Modells eine ordnungsgemäße Erweiterung, bei der kein "neues" Element "vor" einem "alten" Element steht. Als unsere Anwendung von 5.5 beweisen wir

5.6 Satz. Jedes zählbare transitive Modell von ZFC hat eine ordnungsgemäße Endextension.

Beweis. Sei A = ⟨A, ∈ ∈ A⟩ ein transitives Modell von ZFC und sei L die Sprache erster Ordnung der Mengenlehre, ergänzt durch einen Namen a für jedes a ∈ A und eine zusätzliche Konstante c. Lassen Δ die Menge der L sein _A -Sätze umfassend:

• alle Axiome von ZFC;
• c ≠ a für jedes a ∈ A;
• ∀ x (x ∈ a → ∨ _{b ∈ a} x = b) für jedes a ∈ A;
• a ∈ b, für jedes a ∈ b ∈ A.

Es ist leicht zu zeigen, dass Δ eine Teilmenge von A ist, die in A durch eine Formel der Sprache der Mengenlehre definiert werden kann. Außerdem hat jede Teilmenge Δ '⊆ Δ, so dass Δ' ∈ A ein Modell hat. Für die Menge C aller a ∈ A, für die a in Δ 'vorkommt, gehört A - da Δ' dies tut - und wenn wir c als ein Mitglied der (notwendigerweise nicht leeren) Menge A - C interpretieren, dann ist A a Modell von Δ '. Dementsprechend impliziert (5.5), dass Δ ein Modell ⟨B, E⟩ hat. Wenn wir jede Konstante interpretieren a als das Element a ∈ A, dann ⟨B, E⟩ ist eine richtige End-Verlängerung der A. Der Beweis ist vollständig.

Der Leser wird schnell erkennen, dass der Kompaktheitssatz erster Ordnung dieses Ergebnis nicht liefert.

5.1 Definition des Konzepts der zulässigen Menge

Eine nicht leere Transitivmenge A gilt als zulässig, wenn folgende Bedingungen erfüllt sind:

1. wenn a, b ∈ A, dann {a, b} ∈ A und ∪ A ∈ A;
2. wenn a ∈ A und X ⊆ A Δ ₀ auf A ist, dann ist X ∩ a ∈ A;
3. wenn a ∈ A, X ⊆ A auf A Δ ₀ ist und ∀ x ∈ a ∃ y (<x, y> ∈ X), dann ist für einige b ∈ A ∀ x ∈ a ∃ y ∈ b (<x), y> ∈ X).

Bedingung (ii) - das Δ ₀ - Trennungsschema - ist eine eingeschränkte Version von Zermelos Trennungsaxiom. Bedingung (iii) - eine ähnlich geschwächte Version des Ersetzungsaxioms - kann als Δ ₀ - Ersetzungsschema bezeichnet werden.

Es ist ziemlich leicht zu erkennen, dass wenn A eine transitive Menge ist, so dass <A, ∈ | A> ist ein Modell von ZFC, dann ist A zulässig. Allgemeiner bleibt das Ergebnis bestehen, wenn das Potenzsatzaxiom in ZFC weggelassen wird, so dass sowohl H (ω) als auch H (ω ₁) zulässig sind. Da letzteres jedoch unzählig ist, gilt der Barwise-Kompaktheitssatz nicht für ihn.

6. Historische und bibliographische Bemerkungen

§§ 1 und 2. Unendliche Satz- und Prädikatsprachen scheinen mit den Arbeiten von Scott und Tarski [1958] und Tarski [1958] erstmals explizit gedruckt worden zu sein. Der Vollständigkeitssatz für L (ω ₁, ω) sowie für andere unendliche Sprachen wurde von Karp [1964] bewiesen. Die Hanf-Zahlenberechnungen für L (ω ₁, ω) wurden erstmals von Morley [1965] durchgeführt. Die Nichtdefinierbarkeit von Ordnungen in Sprachen mit endlichen Quantifizierern wurde von Karp [1965] und Lopez-Escobar [1966] bewiesen. Der Interpolationssatz für L (ω ₁, ω) wurde von Lopez-Escobar [1965] und der Scott-Isomorphismus-Satz für L (ω ₁, ω) von Scott [1965] bewiesen.

Karps partieller Isomorphismus-Satz wurde erstmals in Karp [1965] bewiesen; siehe auch Barwise [1973]. Ergebnis (2.2) erscheint in Chang [1968], Ergebnis (2.3) in Ellentuck [1976] und Ergebnis (2.4) in Bell [1981].

§ 3. Die Ergebnisse (3.2) und (3.3) stammen von Hanf [1964] mit einigen Verfeinerungen von Lopez-Escobar [1966] und Dickmann [1975], während (3.4) von Tarski bewiesen wurde. Ergebnis (3.5) geht auf Scott [1961], (3.6) auf Bell [1970] und [1972] zurück; und (3.7) an Bell [1974]. Messbare Kardinäle wurden erstmals von Ulam [1930] und Tarski [1939] in Betracht gezogen. Die Tatsache, dass messbare Kardinäle schwach kompakt sind, wurde in Tarski [1962] festgestellt.

§ 4. Bezüglich des Undefinierbarkeitssatzes für L (ω ₁, ω ₁). Carol Karp bemerkt (1964, 166): „Auf dem Internationalen Kongress für Logik, Methodik und Wissenschaftstheorie an der Stanford University im Jahr 1960 verteilte Dana Scott einen Entwurf eines Beweises für die Unmöglichkeit eines vollständig definierbaren formalen Systems für (γ +), γ +) Sprachen mit einem einzigen Prädikatsymbol mit zwei Stellen zusätzlich zum Gleichheitssymbol. “Scott veröffentlichte sein Ergebnis nie und ein vollständig detaillierter Beweis erschien zuerst in Karp [1964]. Die Herangehensweise an den hier gewählten Satz basiert auf der Darstellung von Dickmann [1975].

§ 5. Die ursprüngliche Motivation für die in diesem Abschnitt vorgestellten Ergebnisse kam von Kreisel; In seinem [1965] wies er darauf hin, dass es keine zwingenden Gründe für die Wahl von Infinitivformeln nur aufgrund der „Länge“gebe, und schlug stattdessen vor, Definierbarkeits- oder „Abschluss“-Kriterien anzuwenden. Kreisels Vorschlag wurde von Barwise [1967] mit großem Erfolg aufgegriffen, wo sein Kompaktheitssatz bewiesen wurde. Der Begriff der zulässigen Menge geht auf Platek [1966] zurück. Satz (5.6) stammt von Keisler [1974].

Zur weiteren Lektüre zum Thema der unendlichen Sprachen siehe Aczel [1973], Dickmann [1975], Karp [1964], Keisler [1974] und Makkai [1977]. Eine nützliche Darstellung der Verbindung zwischen unendlichen Sprachen und großen Kardinälen findet sich in Kapitel 10 von Drake [1974].

Literaturverzeichnis

• Aczel, P., 1973, "Infinitary Logic and the Barwise Compactness Theorem", Proceedings der Bertrand Russell Memorial Logic Conference von 1971 (Uldum, Dänemark), J. Bell, J. Cole, G. Priest und A. Slomson (Hrsg.), Leeds: Bertrand Russell Memorial Logic Conference, 234–277.
• Barwise, J., 1967, Infinitary Logic and Admissible Sets. Ph. D. Diplomarbeit, Stanford University.
• –––, 1973, „Hin und her durch unendliche Logik. Studies in Model Theory”, in Studies in Mathematics (Band 8), Buffalo: Mathematical Association of American, S. 5–34.
• –––, 1975, Zulässige Mengen und Strukturen, Berlin: Springer-Verlag.
• Barwise, J. und S. Feferman (Hrsg.), 1985, Handbook of Model-Theoretic Logics, New York: Springer-Verlag.
• Baumgartner, J., 1974, „Die Hanf-Zahl für vollständige L _{ω 1, ω-} Sätze (ohne GCH)“, Journal of Symbolic Logic, 39: 575–578.
• Bell, JL, 1970, „Schwache Kompaktheit in eingeschränkten Sprachen zweiter Ordnung“, Bulletin der Polnischen Akademie der Wissenschaften, 18: 111–114.
• –––, 1972, „Über die Beziehung zwischen schwacher Kompaktheit in L _{ω 1, ω}, L _{ω 1, ω 1 und eingeschränkten Sprachen zweiter Ordnung“, Archiv für mathematische Logik, 15: 74–78.}
• –––, 1974, „On Compact Cardinals“, Zeitschrift für Mathematische Logik und Grundlagen der Mathematik, 20: 389–393.
• –––, 1981, „Isomorphismus von Strukturen in S-Toposen“, Journal of Symbolic Logic, 43 (3): 449–459.
• Chang, CC, 1968, "Einige Bemerkungen zur Modelltheorie unendlicher Sprachen". in Die Syntax und Semantik unendlicher Sprachen (Lecture Notes in Mathematics: Band 72), J. Barwise (Hrsg.), Springer-Verlag, Berlin, 36-63.
• Dickmann, MA, 1975, Large Infinitary Languages, Amsterdam: Nordholland.
• Drake, FR, 1974, Set Theory: Eine Einführung in große Kardinäle, Amsterdam: North-Holland Publishing Company.
• Ellentuck, E., 1976, "Categoricity Regained", Journal of Symbolic Logic, 41 (3): 639–643.
• Hanf, WP, 1964, Inkompaktheit in Sprachen mit unendlich langen Ausdrücken, Amsterdam: Nordholland.
• Karp, C., 1964, Sprachen mit unendlichen Ausdrücken, Amsterdam: Nordholland.
• –––, 1965, „Finite-Quantifier Equivalence“in The Theory of Models, J. Addison, L. Henkin und A. Tarski (Hrsg.), Amsterdam: Nordholland, 407–412.
• Keisler, HJ, 1974, Modelltheorie für unendliche Logik, Amsterdam: Nordholland.
• Keisler, HJ und Julia F. Knight, 2004, „Barwise: Infinitary Logic And Admissible Sets“, Journal of Symbolic Logic, 10 (1): 4–36
• Kolaitis, P. und 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, S. 46-57;; online verfügbar, doi: 10.1109 / LICS.1992.185518
• Kreisel, G., 1965, "Modelltheoretische Invarianten, Anwendungen auf rekursive und hyperarithmetische Operationen", in The Theory of Models, J. Addison, L. Henkin und A. Tarski (Hrsg.), Amsterdam: Nordholland, 190-205.
• Kueker, D., 1975, „Hin- und Her-Argumente in unendlichen Sprachen“, in Infinitary Logic: In Memoriam Carol Karp (Vorlesungsskript in Mathematik: Band 492), D. Kueker (Hrsg.), Berlin: Springer-Verlag.
• Lopez-Escobar, EGK, 1965, „Ein Interpolationssatz für unendlich lange Sätze“, Fundamenta Mathematicae, 57: 253–272.
• –––, 1966, „Über die Definition von Ordnungen“, Fundamenta Mathematicae, 59: 13–21.
• Makkai, M., 1977, "Zulässige Mengen und unendliche Logik", Handbuch der mathematischen Logik, J. Barwise (Hrsg.), Amsterdam: Nordholland, 233-282.
• Morley, M., 1965, "Auslassen von Klassen von Elementen", The Theory of Models, J. Addison, L. Henkin und A. Tarski (Hrsg.), Amsterdam: North-Holland, 265-273.
• Nadel, M. 1985, "L _{ω 1, ω} and Admissible Fragments", in J. Barwise und S. Feferman (Hrsg.) 1985, 271–287.
• Platek, R., 1966, Grundlagen der Rekursionstheorie, Ph. D. Diplomarbeit, Stanford University.
• Scott, D., 1961, „Messbare Kardinäle und konstruierbare Mengen“, Bulletin der Akademie der polnischen Wissenschaften, 9: 521–524.
• –––, 1965, „Logik mit unzählig langen Formeln und endlichen Strings von Quantifizierern“, The Theory of Models, J. Addison, L. Henkin und A. Tarski (Hrsg.), Amsterdam: North-Holland, 329-341.
• Scott, D. und A. Tarski, 1958, „Der Sententialkalkül mit unendlich langen Ausdrücken“, Colloquium Mathematicum, 16: 166–170.
• Shelah, Saharon, 2012, "Nice infinitary logics", Journal der American Mathematical Society, 25: 395-427, online verfügbar, doi: 10.1090 / S0894-0347-2011-00712-1
• Tarski, A., 1939, „Ideale in Mengenständingen Mengenkzahl I“, Fundamenta Mathematicae, 32: 140–150.
• –––, 1958, „Bemerkungen zur Prädikatenlogik mit unendlich langen Ausdrücken“, Colloquium Mathematicum, 16: 171–176.
• –––, 1962, „Einige Probleme und Ergebnisse, die für die Grundlagen der Mengenlehre relevant sind“, in E, Nagel, P. Suppes und A. Tarski (Hrsg.), Logik, Methodik und Wissenschaftstheorie, Stanford: Stanford University Press 123-135.
• Ulam, S., 1930, „Zur Masstheorie in der al-Mengenlehre“, Fundamenta Mathematicae, 16: 140–150.

Akademische Werkzeuge

	Wie man diesen Eintrag zitiert.
	Vorschau der PDF-Version dieses Eintrags bei den Freunden der SEP-Gesellschaft.
	Schlagen Sie dieses Eintragsthema im Internet Philosophy Ontology Project (InPhO) nach.
	Erweiterte Bibliographie für diesen Eintrag bei PhilPapers mit Links zu seiner Datenbank.

Andere Internetquellen

Eine Einführung in die unendliche Logik von David Marker (Mathematik, Statistik und Informatik, Universität von Illinois / Chicago)