Technische Hochschule Darmstadt Fachbereich Mathematik

Über die Entscheidbarkeit der Theorie der Quadrupel

Diplomarbeit von Jon Nedelmann

Betreuer: Prof. Dr. Christian Herrmann

�

Darmstadt, im April 1996

Nous laisserons ce monde-ci aussi sot et aussi méchant que nous l’avons trouvé en y arrivant.

Voltaire

Inhaltsverzeichnis

Einleitung 4

1 Rein injektive Moduln 6 1.1 Positiv primitive Formeln . . . . . . . . . . . . . . . . . . . . . . . . 6 1.2 Typen und p.p. Typen . . . . . . . . . . . . . . . . . . . . . . . . . . 13 1.3 Rein injektive Moduln . . . . . . . . . . . . . . . . . . . . . . . . . . 16 1.4 Hüllen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20 1.5 Unzerlegbare Moduln . . . . . . . . . . . . . . . . . . . . . . . . . . . 22

2 Der Raum der unzerlegbaren Moduln 25 2.1 Unzerlegbare Typen . . . . . . . . . . . . . . . . . . . . . . . . . . . 25 2.2 Konstruktion des Raumes der unzerlegbaren Moduln . . . . . . . . . 28 2.3 Mehr über elementare Äquivalenz . . . . . . . . . . . . . . . . . . . . 30 2.4 Entscheidbarkeit im Raum der unzerlegbaren Moduln . . . . . . . . . 34 2.5 Matrizen und p.p. Typen . . . . . . . . . . . . . . . . . . . . . . . . . 36

3 Moduln über Polynomringen 41 3.1 Moduln über kommutativen Ringen . . . . . . . . . . . . . . . . . . . 41 3.2 Unzerlegbare K[x]-Moduln . . . . . . . . . . . . . . . . . . . . . . . 47 3.3 Entscheidbarkeit . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51

4 Die Theorie der Quadrupel 54 4.1 Übertragung von Entscheidbarkeit bei Interpretationen . . . . . . . . 54 4.2 Zwei Interpretationen . . . . . . . . . . . . . . . . . . . . . . . . . . . 57 4.3 Entscheidbarkeit bei Quadrupeln . . . . . . . . . . . . . . . . . . . . 62 5 Bemerkungen zu den Ergebnissen 65 Literaturverzeichnis 67

Einleitung

Ein Vektorraum mit vier fest vorgegebenen Unterräumen wird ein Quadrupel genannt. Damit wir diese Struktur innerhalb der Logik erster Stufe beschreiben können, wählen wir als Signatur für die Quadrupel über einem Körper K die Signatur der K-Vektorräume zusammen mit vier einstelligen Relationssymbolen. In dieser Arbeit wird gezeigt, daß, wenn wir bestimmte Bedingungen an den Körper K stellen, die Theorie der Quadrupel über dem Körper K entscheidbar ist. Das ist nichts Neues. W. Baur bewies diese Behauptung in [3]. Unser Weg zu diesem Ergebnis unterscheidet sich aber sehr von dem Weg, den Baur eingeschlagen hatte: Wir sprechen so wenig wie möglich über Quadrupel, dafür um so mehr über Moduln, bewegen uns also in dem Gebiet, das mit ,,Modelltheorie von Moduln” umschrieben wird.

So werden in den ersten beiden Kapiteln dieser Arbeit die Begriffe aus diesem Gebiet, die wir benötigen, eingeführt. Von zentraler Bedeutung ist dabei der Raum der unzerlegbaren Moduln, ein topologischer Raum, dessen Punkte Isomorphietypen bestimmter Moduln sind. Dieser Raum wurde von M. Ziegler (siehe [10]) eingeführt und hat sich als sehr hilfreich bei Entscheidbarkeitsproblemen erwiesen. Im dritten Kapitel erhalten wir dann auch mit Hilfe dieses Raums die Entscheidbarkeit der Theorie der Moduln über einem Polynomring (von Polynomen über einem geeigneten Körper), im vierten Kapitel beweisen wir schließlich die Entscheidbarkeit der Theorie der Quadrupel. Hierbei sind Interpretationen der Quadrupel in bestimmten Moduln eine wichtige Hilfe.

An dieser Stelle möchte ich mich bei allen bedanken, die mich bei der Erstellung dieser Arbeit unterstützt haben; besonders danke ich meinem Betreuer Christian Herrmann für die vielen langen Diskussionen, in denen diese Arbeit ihre Form gefunden hat. Für das Korrekturlesen bedanke ich mich bei Gaby Böhm und JanO Droese.

Bemerkungen zur Notation

Mit x̄, ā etc. werden Tupel (x_{0}, …, x_{n−1}), (a_{0}, …, a_{m−1}) bezeichnet. Die Länge eines solchen Tupels ist entweder aus dem Zusammenhang bekannt oder von nebensächlicher Bedeutung. Außerdem schreiben wir oft ā ∈ A für (a_{0}, …, a_{n−1}) ∈ A^{n} und, wenn f : A → B eine Abbildung ist, fā für (fa_{0}, …, fa_{n−1}).

Sei A eine Struktur und φ(x_{0}, …, x_{n−1}) eine Formel in derselben Signatur wie A mit den freien Variablen x_{0}, …, x_{n−1}, dann ist φ(A^{n}) die Menge {ā ∈ A; A ⊧ φ[ā]}, wir nennen sie die durch φ(x̄) in A definierte Relation. Wir erlauben auch Parameter. Wenn ψ(x_{0}, …, x_{n−1}, ȳ) eine weitere Formel derselben Signatur ist und b̄ ∈ A gilt, dann bezeichnen wir mit ψ(A^{n}, b̄) die Menge {ā ∈ A : A ⊧ ψ[ā, b̄]}. Diese Menge wird die durch ψ(x̄, ȳ) in A definierte Relation mit den Parametern b̄ genannt. Ab und zu vergessen wir auch hier n und schreiben der besseren Lesbarkeit wegen φ(A) und ψ(A, b̄) anstatt φ(A^{n}) bzw. ψ(A^{n}, b̄).

Wir verwenden Zermelo-Fraenkelsche Mengenlehre mit Auswahlaxiom, alle Formeln sind Formeln erster Stufe. Wenn es nicht anders angegeben wird, bewegen wir uns in der Sprache der Moduln. In dieser Arbeit ist mit einem Modul entweder ein links R-Modul über einem assoziativen Ring R mit 1 oder ein links A-Modul über einer assoziativen Algebra A mit 1 gemeint. Die Signatur unserer Sprache enthält also die Zeichen +, −, 0 und für jedes Element r ∈ R bzw. a ∈ A ein einstelliges Funktionssymbol.

Mit M, M′, M_{0}, M_{1}, … werden immer Moduln bezeichnet, T_{left-R} steht für die Axiome der links R-Moduln.

Kapitel 1

Rein injektive Moduln

1.1 Positiv primitive Formeln

Definition. Eine Formel heißt positiv primitiv bzw. p.p. Formel, wenn sie zu einer Formel der Form

(1.1) ∃x̄(γ_{1}(x̄, ȳ) ∧ … ∧ γ_{k}(x̄, ȳ))

äquivalent ist, wobei die γ_{i} (1 ≤ i ≤ k) atomar sind. In der Sprache der Moduln hat eine atomare Formel die Gestalt

(1.2)  ∑_{i=0}^{n−1} r^{i}x^{i} + ∑_{j=0}^{m−1} s^{j}y^{j} = 0  (r^{i}, s^{j} ∈ R).

Aus algebraischer Sicht drückt eine p.p. Formel aus, ob eine endliche Menge von Gleichungen mit denselben Parametern eine für alle Gleichungen gemeinsame Lösung besitzt. Die durch eine p.p. Formel definierte Relation ist das Bild unter einer Projektion einer Lösungsmenge eines linearen Gleichungssystems. Existieren keine Parameter, dann ist das Gleichungssystem homogen.

Lemma 1.1 Homomorphismen erhalten positiv primitive Formeln, das heißt, haben wir einen Modulhomomorphismus f : M → M′, dann folgt aus M ⊧ φ[ā] sofort M′ ⊧ φ[f(ā)], wobei φ eine p.p. Formel und ā ∈ M ist.

Beweis. Sei f : M → M′ ein Homomorphismus und γ(x̄, ȳ) eine atomare Formel wie in (1.2) ; M ⊧ γ[ā, b̄] bedeutet

(1.3)  ∑_{i=0}^{n−1} r^{i}a^{i} + ∑_{j=0}^{m−1} s^{j}b^{j} = 0.

Daraus folgt

(1.4)  ∑_{i=0}^{n−1} r^{i}f(a^{i}) + ∑_{j=0}^{m−1} s^{j}f(b^{j}) = 0,

also M′ ⊧ γ[fā, fb̄], dasselbe gilt, wenn γ eine Konjunktion von atomaren Formeln ist. Wegen fā ∈ M′ impliziert M ⊧ ∃x̄γ(x̄, b̄) die Gültigkeit von M′ ⊧ ∃x̄γ(x̄, fb̄), und die Behauptung ist bewiesen. □

Lemma 1.2

(i)

Sei φ(x_{0}, …, x_{n−1}) eine p.p. Formel, dann ist φ(M^{n}) eine Untergruppe der dem Modul M^{n} unterliegenden abelschen Gruppe, wir nennen sie eine p.p. definierbare Untergruppe von M^{n}.

(ii)

Sei φ(x_{0}, …, x_{n−1}, ȳ) eine p.p. Formel und ā ∈ M. Dann ist φ(M^{n}, ā) leer oder eine Nebenklasse von φ(M^{n}, ¯0).

(iii)

Seien ā, b̄ ∈ M und φ(x, ȳ) eine p.p. Formel. Dann sind φ(x, ā) und φ(x, b̄) entweder äquivalent oder kontradiktorisch modulo M, das heißt

M ⊧ ∀x((φ(x, ā) ↔ φ(x, b̄)) ∨ (φ(x, ā) ↔ ¬φ(x, b̄))).

(iv)

Die geordnete Menge der p.p. definierbaren Untergruppen von M^{n} ist ein Unterverband des Untergruppenverbandes von M^{n}. Dieser Unterverband ist modular. Die Verbandsoperationen sind folgendermaßen erklärt:

φ(M^{n}) ∩ ψ(M^{n}) = (φ ∧ ψ)(M^{n}),
φ(M^{n}) + ψ(M^{n}) = (φ + ψ)(M^{n}).

Dabei ist (φ + ψ)(x̄) die p.p. Formel ∃ȳ∃z̄(φ(ȳ) ∧ ψ(z̄) ∧ x̄ = ȳ + z̄).

Beweis. (i) Sei γ(x_{0}, …, x_{n−1}) die Gleichung

(1.5)  ∑_{i=0}^{n−1} r^{i}x^{i} = 0  mit r^{i} ∈ R.

Durch Einsetzen in (1.5) erhalten wir

(1.6) \begin{matrix}M & ⊧ & γ[¯0] \\ M & ⊧ & γ[ā] ∧ γ[b̄] → γ[ā − b̄]. \end{matrix}

Eine p.p. Formel drückt nun aber aus, ob eine Lösung für die in ihr enthaltenen Gleichungen existiert, wenn alle Gleichungen dieselben Parameter haben. Deshalb überträgt sich (1.6) auf p.p. Formeln.

(ii) Aus (i) folgt

(1.7) M ⊧ φ[c̄, ā] → (φ[d̄, ¯0] ↔ φ[c̄ + d̄, ā]).

Gilt also M ⊧ φ[c̄, ā], dann ist φ(M^{n}, ā) eine Nebenklasse von φ(M^{n}, ¯0), ist M ⊭ φ[c̄, ā], dann ist φ(M^{n}, ā) leer.

(iii) Weil φ(M, ā) und φ(M, b̄) Nebenklassen von φ(M, ¯0) sind, ist entweder φ(M, ā) = φ(M, b̄) oder φ(M, ā) ∩ φ(M, b̄) = ∅.

(iv) Die Formel φ(ȳ) ∧ ψ(ȳ) ist äquivalent zu der p.p. Formel

(1.8) ∃x̄(γ_{1}(x̄, ȳ) ∧ … ∧ γ_{k+m}(x̄, ȳ)) ,

wobei die Gleichungen γ_{1} bis γ_{k} die Gleichungen aus φ und die restlichen Gleichungen die aus ψ sind. Damit ist φ ∧ ψ wieder eine p.p. Formel. Aus (1.8) läßt sich sofort ablesen, daß (φ ∧ ψ)(M^{n}) tatsächlich der Schnitt von φ(M^{n}) und ψ(M^{n}) und deswegen auch das Infimum der beiden im Untergruppenverband ist. Sei M ⊧ φ[c̄], dann gilt auch M ⊧ φ[c̄] ∧ ψ[¯0] und damit M ⊧ (φ + ψ)[c̄]. Daraus erhalten wir

(1.9) φ(M^{n}) ∪ ψ(M^{n}) ⊆ (φ + ψ)(M^{n}).

Angenommen, wir haben die folgenden Inklusionen

(1.10) φ(M^{n}) ∪ ψ(M^{n}) ⊆ ϕ(M^{n}) ⊆ (φ + ψ)(M^{n})

und c̄ wäre ein Tupel von Elementen aus (φ + ψ)(M^{n}). Dann wäre c̄ = ā + b̄ mit ā ∈ φ(M^{n}) und b̄ ∈ ψ(M^{n}) und deswegen ā + b̄ in ϕ(M^{n}) enthalten. Wir folgern ϕ(M^{n}) = (φ + ψ)(M^{n}) und unsere Definition des Supremums war richtig. Unser Verband ist Unterverband eines Untermodulverbandes (von zum Beispiel ℤ-Moduln) und damit modular. □

Ein Beispiel: Sei M = ℤ_{2} ⊕ ℤ_{4}. Der Untergruppenverband hat die Gestalt des linken Diagramms, während der Verband der p.p. definierbaren Untergruppen gerade die Kette auf der rechten Seite ist; rechts neben ihr stehen p.p. Formeln, welche die entsprechenden Untergruppen definieren.

o  o  x = x
[figure]
o  o  o  o  4x = 0
[figure]
o  o  o  o  2x = 0 ∧ ∃y(x = 2y)
[figure]
o  o  x = 0

Unser nächstes Ziel ist es, zu zeigen, daß in der Sprache der Moduln die p.p. Formeln eine Eliminationsmenge bilden, das heißt, daß jede Formel boolesche Kombination von p.p. Formeln (modulo einer vollständigen Theorie) ist. Dafür brauchen wir noch ein wenig Vorbereitung.

Für eine Gruppe G und eine Untergruppe H von G schreiben wir (G : H) für den Index von H in G.

Lemma 1.3 (B.H. Neumann) Sei G eine Gruppe, seien H_{1}, …, H_{n} Untergruppen von G und a_{1}, …, a_{n} Elemente von G. Nun sei G die Vereinigung der Menge der Nebenklassen X = {H_{1}a_{1}, …, H_{n}a_{n}}, aber nicht Vereinigung einer echten Teilmenge von X. Damit ist (G : ⋂_{i=1}^{n} H_{i}) ≤ n!. Insbesondere hat jede der Gruppen H_{i} einen endlichen Index in G.

Beweis. Es sei H = ⋂_{i=1}^{n} H_{i}. Wir zeigen

(1.11)  (H_{j} : H) ≤ (n − 1)!  für 1 ≤ j ≤ n.

Wegen (1.11) ist jede Nebenklasse H_{i}a_{i} Vereinigung von höchstens (n − 1)! Nebenklassen von H, damit ist G Vereinigung von höchstens n! Nebenklassen, womit das Lemma bewiesen ist. (1.11) folgt aus dem Fall m = 1 folgender Behauptung:

(1.12) Sei 1 ≤ m ≤ n und seien K_{1}, …, K_{m} die Untergruppen H_{i(1)}, …, H_{i(m)} für bestimmte i(1) ≤ … ≤ i(m), dann ist (K_{1} ∩…∩K_{m} : H) ≤ (n−m)!

Wir zeigen (1.12) durch absteigende Induktion über m. Im Fall m = n ist nichts zu beweisen. Sei nun (1.12) bewiesen für m + 1; seien K_{1}, …, K_{m} Gruppen wie in der Annahme von (1.12) und sei K = ⋂_{j=1}^{m} K_{j}. Wegen der Minimalität von X existiert ein g ∈ X, das nicht in ⋃_{j=1}^{m} H_{i(j)}a_{i(j)} enthalten ist. Damit ist für jedes j (1 ≤ j ≤ m) H_{i(j)}a_{i(j)} disjunkt zu H_{i(j)}g und deshalb auch disjunkt zu Kg, so daß H_{i(j)}a_{i(j)}g^{−1} und K disjunkt sind. Nun ist für ein beliebiges i mit 1 ≤ i ≤ n die Menge K ∩ (H_{i}a_{i}g^{−1}) entweder leer oder eine Nebenklasse (K ∩ H_{i})y_{i}. Wir wissen, daß sie leer ist, wenn i = i(j) für ein j ist. Also ist K Vereinigung von höchstens n − m Nebenklassen (K ∩ H_{i})y_{i}, die alle nach Induktionsannahme Vereinigung von höchstens (n − m − 1)! Nebenklassen von H sind, damit ist (1.12) bewiesen. □

Korollar 1.4 Sei H_{0} eine weitere Untergruppe und a_{0} ein weiteres Element von G. Ist H_{0}a_{0} ⊆ ⋃_{i=1}^{n} H_{i}a_{i} und (H_{0} : H_{0} ∩ H_{i}) unendlich für i > k, dann gilt sogar H_{0}a_{0} ⊆ ⋃_{i=1}^{k} H_{i}a_{i}.

Beweis. Wir wählen eine minimale Teilmenge Δ ⊆ {1, …, n} aus, so daß

(1.13) H_{0} ⊆ ⋃_{i∈Δ} H_{i}a_{i}a_{0}^{−1}

erfüllt ist. Dann gilt

(1.14) H_{0} = ⋃_{i∈Δ} H_{i}a_{i}a_{0}^{−1} ∩ H_{0}.

Nach dem vorhergehenden Lemma muß (H_{0} : H_{0} ∩ H_{i}) für alle i ∈ Δ endlich sein. □

Lemma 1.5 Sei (A_{i} : 0 ≤ i ≤ k) eine endliche Familie von Mengen. Wenn A_{0} endlich ist, gilt

A_{0} ⊆ ⋃_{i=1}^{k} A_{i} ⇔ ∑_{Δ⊆{1,...,k}}(−1)^{|Δ|}|A_{0} ∩ ⋂_{i∈Δ} A_{i}| = 0.

Beweis. Auf der rechten Seite werden zuerst die Elemente von A_{0} gezählt, dann werden für jedes i ∈ {1, …, k} die Elemente im Schnitt A_{0} ∩ A_{i} abgezogen. Ist A_{0} ∩ A_{i} ∩ A_{j} für i ≠ j nicht leer, dann wurden die Elemente im Schnitt zweimal abgezogen, also werden für alle i, j ∈ {1, …, k} mit i ≠ j die Mächtigkeiten von A_{0} ∩ A_{i} ∩ A_{j} wieder dazu addiert usw.. Damit ist die Summe gleich Null, wenn A_{0} Teilmenge der Vereinigung ist, ansonsten wäre sie größer Null. □

Satz 1.6 In der Sprache der Moduln ist jede Formel äquivalent modulo M zu einer booleschen Kombination von p.p. Formeln.

Beweis. Wir müssen zeigen: Ist ψ(x, ȳ) äquivalent zu einer booleschen Kombination von p.p. Formeln modulo M, dann ist das auch ∀xψ(x, ȳ); p.p. Formeln sind abgeschlossen unter Konjunktion, deshalb ist ψ äquivalent modulo M zu einer Formel der Form

(1.15) φ_{0}(x, ȳ) → φ_{1}(x, ȳ) ∨ … ∨ φ_{n}(x, ȳ) (φ_{i} ist eine p.p. Formel).

Sei H_{i} = φ_{i}(M, ¯0). Für jedes Tupel ā in M ist φ_{i}(M, ā) leer oder eine Nebenklasse von H_{i}. Wähle Indizes derart, daß (H_{0} : H_{0} ∩ H_{i}) endlich ist für i = 1, …, k und unendlich für i = k + 1, …, n. Nun folgt aus Korollar 1.4

(1.16) M ⊧ ∀xψ(x, ā) ↔ ∀x(φ_{0}(x, ā) → φ_{1}(x, ā) ∨ … ∨ φ_{k}(x, ā)).

Die rechte Seite der Formel ist äquivalent zu φ_{0}(M, ā) ⊆ ⋃_{i=1}^{k} φ_{i}(M, ā) bzw.

(1.17) φ^{0}(M, ā)/(H^{0} ∩ … ∩ H^{k}) ⊆ ⋃_{i=1}^{k} φ^{i}(M, ā)/(H^{0} ∩ … ∩ H^{k}).

Die Menge auf der linken Seite von (1.17) ist endlich, also können wir Lemma 1.5 anwenden. Dazu betrachten wir genauer für Δ ⊆ {1, …, k} die Mengen

(1.18) X^{Δ} = φ^{0}(M^{n}, ā)/(H^{0} ∩ … ∩ H^{k}) ∩ ⋂_{i∈Δ} φ^{i}(M^{n}, ā)/(H^{0} ∩ … ∩ H^{k}).

X_{Δ} ist entweder leer, das heißt, M ist kein Modell des Satzes

(1.19) ∃x(φ_{0}(x, ā) ∧ ⋀_{i∈Δ} φ_{i}(x, ā)),

dem wir den Namen φ_{Δ} geben, oder X_{Δ} besteht aus

m_{Δ} = (H_{0} ∩ ⋂_{i∈Δ} H_{i} : (H_{0} ∩ … ∩ H_{k})) Nebenklassen von H_{0} ∩ … ∩ H_{k}.

Aus dem Lemma 1.5 folgt nun, daß (1.17) äquivalent zu der Aussage

(1.20)  ∑_{M⊧φ_{Δ}}(−1)^{|Δ|}m_{Δ} = 0

ist. Setzen wir

(1.21) \begin{matrix}Λ & = & \{Γ ∈ ℙ(ℙ(\{1, …, k\})) : ∑_{Δ∈Γ} −1^{|Δ|}m_{Δ} = 0\} und \\ φ_{Γ} & = & ⋀_{Δ∈Γ} φ_{Δ} ∧ ⋀_{Δ∉Γ} ¬φ_{Δ}, \end{matrix}

dann ist ∀xψ(x, ȳ) äquivalent zu der Formel

(1.22)  ⋁_{Γ∈Δ} φ_{Γ},

die eine boolesche Kombination von p.p. Formeln ist. □

Betrachten wir die Größen m_{Δ} aus dem vorangegangenen Beweis noch einmal genauer. Ausführlich geschrieben ist

(1.23) m_{Δ} = ((φ_{0} ∧ ⋀_{i∈Δ} φ_{i})(M, ¯0) : (φ_{0} ∧ … ∧ φ_{k})(M, ¯0)),

m_{Δ} ist also der Index einer p.p. definierbaren Untergruppe in einer p.p. definierbaren Gruppe. Dieser Sachverhalt ist so interessant, daß wir für ihn einige neue Schreibweisen einführen. Seien φ, ψ zwei p.p. Formeln. Gilt M ⊧ ψ → φ, so ist ψ(M^{n}) ein Untergruppe von φ(M^{n}). In dieser Situation schreiben wir φ/ψ(M) für (φ(M^{n}) : ψ(M^{n})). Dieser Tatbestand ist für jeden Modul erfüllt, wenn ψ → φ eine wahre Aussage innerhalb der Theorie der Moduln ist. Wir nennen ein Paar (φ, ψ) von p.p. Formeln, das diese Bedingung erfüllt, eine Invarianzaussage und schreiben φ/ψ anstatt (φ, ψ). Invarianzaussagen werden im zweiten Kapitel eine sehr wichtige Rolle spielen. Das hat zwei Gründe: Der erste Grund ist der nächste Satz, der zweite die folgende Beobachtung: Sei φ/ψ_{≥k} der Satz

(1.24) ∀x̄_{1} … ∀x̄_{k}∃x̄(φ(x̄) ∧ ⋀_{i=1}^{k} ¬ψ(x̄ − x̄_{i})).

Mit ihm erhalten wir die Äquivalenz

(1.25) M ⊧ φ/ψ_{≥k} ⇔ φ/ψ(M) ≥ k.

Als nächstes bilden wir den Satz φ/ψ_{=k} = φ/ψ_{≥k} ∧ ¬φ/ψ_{≥k+1} und erhalten

(1.26) M ⊧ φ/ψ_{=k} ⇔ φ/ψ(M) = k.

Wir können also die Behauptung, eine p.p. definierbare Untergruppe hat den Index n in einer p.p. definierbaren Gruppe, innerhalb der Sprache der Moduln ausdrücken. Jetzt der versprochene erste Grund:

Satz 1.7 Zwei Moduln M_{1} und M_{2} sind genau dann elementar äquivalent, wenn für alle Invarianzaussagen φ/ψ von p.p. Formeln in einer freien Variablen entweder φ/ψ(M_{1}) und φ/ψ(M_{2}) beide unendlich sind, oder φ/ψ(M_{1}) = φ/ψ(M_{2}) gilt.

Beweis. Sind die beiden Moduln elementar äquivalent, dann gilt vor allem

(1.27) M_{1} ⊧ φ/ψ_{=k} ⇔ M_{2} ⊧ φ/ψ_{=k}

für alle Invarianzaussagen φ/ψ und alle natürlichen Zahlen k, was die angegebenen Bedingungen impliziert. Andererseits folgt aus φ/ψ(M_{1}) = φ/ψ(M_{2}) für alle Invarianzaussagen φ/ψ, daß die Größen m_{Δ} aus dem Beweis des Satzes 1.6 für M_{1} und M_{2} gleich sind. Außerdem ist M_{1} genau dann ein Modell von φ_{Δ}, wenn M_{2} eines ist. Das bedeutet, daß ein Satz zur selben booleschen Kombination von p.p. Sätzen äquivalent ist, egal ob wir modulo M_{1} oder modulo M_{2} rechnen; p.p. Sätze sind immer erfüllt (die Gleichungen haben die gemeinsame Lösung ¯0), und darum ist M_{1} ein Modell eines Satzes genau dann, wenn M_{2} es ist. □

Lemma 1.8 Zu jeder Formel φ(x̄) und jedem Modul M existiert eine boolesche Kombination von p.p. Formeln ϕ(x̄) und eine Konjunktion θ von Sätzen der Form η/ψ_{=k} (dabei sind η und ψ p.p. Formeln in einer freien Variablen) so, daß

T_{left-R} ⊢ θ → ∀x̄(φ(x̄) ↔ ϕ(x̄)) und M ⊧ θ

gilt.

Beweis. Die Formel φ(x̄) ist nach Satz 1.6 äquivalent modulo M zu einer booleschen Kombination von p.p. Formeln ϕ(x̄). Andererseits ist die Theorie Th(M) durch T = T_{left-R} ∪ {η/ψ_{=η/ψ(M)} : η/ψ ist eine Invarianzaussage } axiomatisiert. Wir erhalten also

(1.28) T ⊢ ∀x̄(φ(x̄) ↔ ϕ(x̄)).

Aus dem Endlichkeitssatz folgt, daß endlich viele Sätze

φ_{1}/ψ_{1=φ_{1}/ψ_{1}(M)}, …, φ_{n}/ψ_{n=φ_{n}/ψ_{n}(M)}

existieren, so daß, wir schreiben θ für ihre Konjunktion,

(1.29) T_{left-R} ∪ {θ} ⊢ ∀x̄(φ(x̄) ↔ ϕ(x̄))

bzw.

(1.30) T_{left-R} ⊢ θ → ∀x̄(φ(x̄) ↔ ϕ(x̄))

gilt. □

1.2 Typen und p.p. Typen

Ganz viele Definitionen. Sei L eine beliebige Signatur, A eine L-Struktur, X eine Teilmenge von A und b̄ ein Tupel von Elementen aus A. Der vollständige Typ von b̄ über X (bezüglich A mit den freien Variablen x̄), in Zeichen tp_{A}(b̄/X), ist als die Menge aller Formeln ψ(x̄, ā) definiert, wobei ψ(x̄, ȳ) eine L-Formel, ā aus X und A ein Modell von ψ[b̄, ā] ist. Die Elemente aus X werden die Parameter des vollständigen Typen genannt. Wir schreiben tp_{A}(b̄) anstatt tp_{A}(b̄/∅). Bemerke, wenn B eine elementare Erweiterung von A ist, dann ist tp_{B}(b̄/X) = tp_{A}(b̄/X).

Sei p(x̄) eine Menge von L-Formeln, die freien Variablen der Formeln aus p(x̄) seien in x̄ enthalten und die Parameter der Formeln seien aus X. Diese Menge p(x̄) ist ein vollständiger Typ über X (bezüglich A), wenn sie der vollständige Typ eines Tupels b̄ über X bezüglich einer elementaren Erweiterung von A ist. Vollständige Typen bezeichnen wir mit kleinen lateinischen Buchstaben. Ein Typ über X ist eine Teilmenge eines vollständigen Typen über X. Typen bezeichnen wir mit großen griechischen Buchstaben. Ein Typ Φ(x̄) über X wird durch ein Tupel b̄ in A realisiert, wenn Φ ⊆ tp_{A}(b̄/X) gilt. Außerdem sagen wir, die Menge Θ(x̄) von L-Formeln mit Parametern aus A wird in A endlich realisiert, wenn für jede endliche Teilmenge Ψ von Θ

(2.1) A ⊧ ∃x̄ ⋀ Ψ(x̄)

erfüllt ist.

Lemma 1.9 Φ(x_{0}, …, x_{n−1}) ist genau dann ein Typ über X bezüglich A, wenn Φ in A endlich realisiert wird.

Beweis. Wir setzen voraus, daß Φ in A endlich realisiert ist. Sei ā eine Sequenz von Elementen aus A, die A erzeugen und c̄ = (c_{0}, …, c_{n−1}) ein n-Tupel von paarweise verschiedenen Konstanten, die nicht in der Signatur von L vorkommen; T sei die Theorie

(2.2) Th(A, ā) ∪ Φ(c̄).

Dabei bezeichnet Th(A, ā) die Theorie der Struktur, die aus A entsteht, wenn die Elemente aus ā als Konstanten in die Signatur hinzugenommen werden. Wir behaupten, daß jede endliche Teilmenge von T ein Modell hat. Denn sei U eine endliche Teilmenge von T und Ψ die Menge {ψ(x̄) ∈ Φ : ψ(c̄) ∈ U}, dann gilt nach Voraussetzung A ⊧ ∃x̄ ⋀ Ψ(x̄), also existiert ein Tupel b̄ ∈ A mit A ⊧ ⋀ Ψ[b̄]. Durch die Interpretation c_{i}^{A} = b_{i} (0 ≤ i ≤ n − 1) wird A zu einem Modell von U. Aus dem Kompaktheitssatz folgt, daß T ein Modell hat, nennen wir es C. Weil A von ā erzeugt wird, hat jedes Element von A die Gestalt t^{(A,ā)}, wobei t ein variablenfreier Term der Signatur L(ā) ist. Wegen C ⊧ Th(A, ā) gilt

(2.3) (A, ā) ⊧ ϕ[b̄] ⇔ C ⊧ ϕ[b̄]

für jede atomare Formel ϕ, und deshalb ist die durch

(2.4) f(t^{(A,ā)}) = t^{C}

definierte Abbildung f : A → C|_{L} eine elementare Einbettung. Mit Φ(x̄) ⊆ tp_{C}(c̄/X) folgt die Rückrichtung, die andere Richtung ist trivial. □

Die oben gegebenen Definitionen lassen sich leicht auf p.p. Formeln übertragen, so ist zum Beispiel der vollständige p.p. Typ von b̄ über X die Menge aller p.p. Formeln ψ(x̄, ā), die ā ∈ X und A ⊧ ψ[b̄, ā] erfüllen. Ist Φ(x̄) ein Typ, dann bezeichnet Φ^{+}(x̄) die Menge der p.p. Formeln aus Φ(x̄), die wir den p.p. Teil von Φ(x̄) nennen, Φ^{−}(x̄) ist die Menge aller Negationen von p.p. Formeln aus Φ(x̄).

Als nächstes wollen wir Verbindungen zwischen vollständigen Typen und ebenfalls vollständigen p.p. Typen in der Sprache der Moduln herstellen. Aus Satz 1.6 folgt sofort:

(2.5) tp_{M}^{+}(b̄/X) ∪ tp_{M}^{−}(b̄/X) ⊢_{M} tp_{M}(b̄/X)

für beliebige Teilmengen X von M und beliebige Tupel b̄ ∈ M. Wann ist aber ein vollständiger Typ schon allein durch seinen p.p. Teil bestimmt? Das folgende Lemma gibt die Antwort:

Lemma 1.10 Für A ⊆ M sei S^{+}(A) = {tp_{M}^{+}(b̄/A) : b̄ ∈ M}. Dann gilt

tp_{M}^{+}(b̄/A) ⊢_{M} tp_{M}(b̄/A) ⇔ tp_{M}^{+}(b̄/A) ist maximal in S^{+}(A).

Beweis. Angenommen, tp_{M}^{+}(b̄/A) ⊬_{M} tp_{M}(b̄/A), das heißt, es existiert eine Formel ψ(x̄, ā) ∈ tp_{M}(b̄/A) und ein Modell M_{0} von Th(M) ∪ tp_{M}^{+}(b̄/A) mit M_{0} ⊭ ψ[b̄, ā]. Dann gibt es aber eine Formel ¬ψ̃(x̄, ȳ) ∈ tp_{M}^{−}(b̄/A) mit M_{0} ⊭ ¬ψ̃[b̄, ā]. Nun ist tp_{M}^{+}(b̄/A) ∪ {ψ̃(x̄, ā)} in M_{0} realisiert, also ist tp_{M}^{+}(b̄/A) nicht maximal in S^{+}(A).

Zum Beweis der Gegenrichtung nehmen wir an, daß tp_{M}^{+}(b̄/A) nicht maximal sei, dann ist tp_{M}^{+}(b̄/A) ⊂ tp_{M}^{+}(c̄/A) für ein c̄ ∈ A, und es existiert eine p.p. Formel ψ(x̄, ȳ) mit M ⊧ ψ[c̄, ā] für ein ā ∈ A, aber M ⊭ ψ[b̄, ā]. Nun ist ¬ψ(x̄, ā) Element von tp_{M}(b̄/A), aber nicht aus tp_{M}^{+}(b̄/A) ableitbar. □

Lemma 1.10 gab uns eine Antwort auf die oben gestellte Frage, jedoch ist diese Antwort nicht sehr befriedigend, denn es stellt sich sofort die Frage, wann denn S^{+}(A) maximal ist? Diese Frage läßt sich beantworten, indem wir sagen, wie für die Menge A eine Menge B ,,aussieht”, aus der die Tupel b̄ gewählt werden können. Damit haben wir ein Kriterium gefunden, mit dem wir gut arbeiten können.

Definitionen. Wir nennen eine partielle Abbildung f von M_{1} nach M_{2} einen partiellen Homomorphismus, wenn

(2.6) M_{1} ⊧ φ[ā] ⇒ M_{2} ⊧ φ[fā]

gilt, wobei φ eine p.p. Formel und ā ∈ dom(f) ist. Gilt sogar

(2.7) M_{1} ⊧ φ[ā] ⇔ M_{2} ⊧ φ[fā],

dann nennen wir f einen partiellen Isomorphismus. Seien A, B Teilmengen des Moduls M und A ⊆ B. Wir sagen, die Inklusion i : A ↪ B ist p.p. wesentlich, wenn jeder partielle Homomorphismus f : B → M_{1} von M nach M_{1}, dessen Einschränkung auf A ein partieller Isomorphismus ist, dann auch ein partieller Isomorphismus ist.

Lemma 1.11 Seien A, B und M wie oben. Die Inklusion i : A ↪ B ist genau dann p.p. wesentlich, wenn für alle b̄ ∈ B der vollständige p.p. Typ tp_{M}^{+}(b̄/A) maximal in S^{+}(A) ist.

Beweis. Angenommen, tp_{M}^{+}(b̄/A) ist nicht maximal. Dann existiert ein Tupel c̄ ∈ M mit tp_{M}^{+}(b̄/A) ⊂ tp_{M}^{+}(c̄/A). Sei φ(x̄, ā) ∈ tp_{M}^{+}(c̄/A)\tp_{M}^{+}(b̄/A). Der Modul M_{0} sei eine elementare Erweiterung von M, welche die Eigenschaft hat, daß jeder partielle Homomorphismus f : M_{1} → M_{0} zu einem Homomorphismus fortgesetzt werden kann. Ein solcher Modul M_{0} existiert, zum Beispiel erfüllt die rein injektive Hülle von M, die wir in ein paar Seiten einführen werden, diese Aufgabe. Sei g = id_{A} ∪ {(b̄, c̄)} Dann ist g ein partieller Homomorphismus von M nach M_{0}. Wir erweitern ihn zu einem partiellen Homomorphismus f auf B; f ist kein partieller Isomorphismus, denn M ⊧ ¬φ[b̄, ā] und M_{0} ⊧ φ[c̄, ā], aber partiell isomorph auf A, also ist i : A ↪ B nicht p.p. wesentlich.

Nun sei tp_{M}^{+}(b̄/A) maximal in S^{+}(A). Sei f : B → C ein partieller Homomorphismus von M nach M_{1}, der auf A partiell isomorph ist. Wir erweitern den partiellen Homomorphismus f^{−1}|_{f(A)} zu einem partiellen Homomorphismus g von M_{1} in die oben definierte elementare Erweiterung M_{0} von M, so daß dom g = C erfüllt ist. Für alle b̄ ∈ B ist deshalb tp_{M}^{+}(b̄/A) ⊆ tp_{M}^{+}(gf(b̄)/A). Wegen der Maximalität von tp_{M}^{+}(b̄/A) können wir das Inklusionszeichen durch das Gleichheitszeichen ersetzen, und wir wissen, daß g ∘ f und f partielle Isomorphismen sind. Damit ist i : A ↪ B p.p. wesentlich. □

1.3 Rein injektive Moduln

Definition. Sei M_{1} Untermodul von M_{2}. Wir sagen, daß M_{1} rein in M_{2} ist, oder daß M_{2} eine reine Erweiterung von M_{1} ist, wenn für jede endliche Menge E von Gleichungen mit Parametern in M_{1} eine Lösung in M_{1} existiert, wenn E schon eine Lösung in M_{2} hat.

Nun wird die Tatsache, daß eine endliche Menge von Gleichungen mit Parametern ā aus M_{1} eine Lösung besitzt, durch eine p.p. Formel der Gestalt

(3.1) ∃x̄(γ_{1}(x̄, ā) ∧ … ∧ γ_{k}(x̄, ā))

ausgedrückt; dabei sind die γ_{i}(x̄, ā) gerade die Gleichungen von E. Diese Überlegung zeigt, daß die nächste Definition sinnvoll ist:

Definition. Eine Einbettung heißt rein, wenn sie Negationen von p.p. Formeln erhält.

Letzteres kann auch durch p.p. Typen ausgedrückt werden. Sei f : M_{1} → M_{2} eine reine Einbettung. Weil f ein Einbettung ist, gilt tp_{M_{1}}^{+}(b̄/A) ⊆ tp_{M_{2}}^{+}(fb̄/fA), weil f rein ist, die umgekehrte Inklusion; also hätten wir auch definieren können, f ist eine reine Einbettung, wenn tp_{M_{1}}^{+}(b̄/A) = tp_{M_{2}}^{+}(fb̄/fA) für alle b̄ ∈ M_{1} und A ⊆ M_{1} gilt.

Beispiel. Direkte Summanden sind rein in ihrer Summe, denn sei zum Beispiel M_{0} ein direkter Summand von M und pr : M → M_{0} die Projektion. Gilt M ⊧ φ[ā] für eine p.p. Formel φ und ā ∈ M_{0}, dann ist M_{0} ⊧ φ[pr(ā)] und natürlich ā = pr(ā).

Lemma 1.12 Für eine p.p. Formel φ(x_{0}, …, x_{n−1}) und eine Familie (M_{i} : i ∈ I) von Moduln gilt

φ((⨁_{i∈I} M_{i})^{n}) = ⨁_{i∈I} φ(M_{i}^{n}).

Beweis. Sei ⨁_{i∈I} M_{i} ⊧ φ[ā], dann gilt, weil die Summanden rein in ihrer Summe sind, M_{i} ⊧ φ[ā_{i}] für alle i ∈ I und ā = ∑_{i∈I} ā_{i}. Also ist die Menge auf der linken Seite in der auf der rechten enthalten. Sei nun andererseits M_{i} ⊧ φ[ā_{i}] für alle i ∈ I und ā = ∑_{i∈I} ā_{i}. Produkte und direkte Summen erhalten p.p. Formeln, denn läßt sich eine Gleichung mit Parametern ā in einem Modul M lösen, dann auch in jeder direkten Summe, die M als Summanden enthält (Ein formaler Beweis kann durch Induktion über den Formelaufbau erfolgen.). Wir haben also ⨁_{i∈I} M_{i} ⊧ φ[ā_{i}] für alle i ∈ I und damit ⨁_{i∈I} M_{i} ⊧ φ[ā]. Die rechte Menge ist auch in der linken enthalten. □

Korollar 1.13 Für jede Invarianzaussage φ/ψ gilt

φ/ψ(⨁_{i∈I} M_{i}) = ∏_{i∈I} φ/ψ(M_{i}) = φ/ψ(∏_{i∈I} M_{i}).

Dabei vereinbaren wir, daß für alle n ∈ ℕ, n · ∞ = ∞ · n = ∞ gerechnet wird.

Beweis. Die Rechnung

φ/ψ(⨁_{i∈I} M_{i}) = (φ(⨁_{i∈I} M_{i}) : ψ(⨁_{i∈I} M_{i}))
= (⨁_{i∈I} φ(M_{i}) : ⨁_{i∈I} ψ(M_{i}))
= ∏_{i∈I}(φ(M_{i}) : ψ(M_{i}))
= ∏_{i∈I} φ/ψ(M_{i})

beweist die erste Gleichung, der Beweis für die zweite Gleichung verläuft analog. □

Korollar 1.14 Für jede Familie (M_{i} : i ∈ I) von Moduln gilt

⨁_{i∈I} M_{i} ≡ ∏_{i∈I} M_{i}.

Beweis. Die Behauptung folgt sofort aus Satz 1.7 und Korollar 1.13. □

Ein Modul M wird injektiv genannt, wenn es zu jeder Einbettung φ : M_{1} → M_{2} und jedem Homomorphismus ψ : M_{1} → M einen Homomorphismus ϕ : M_{2} → M gibt, der ϕ ∘ φ = ψ erfüllt. Wir interessieren uns für den Spezialfall, daß φ eine reine Einbettung ist, und erhalten den folgenden Begriff:

Definition. Ein Modul M ist rein injektiv, wenn es zu jeder reinen Einbettung φ : M_{1} → M_{2} und jedem Homomorphismus ψ : M_{1} → M einen Homomorphismus ϕ : M_{2} → M gibt, so daß das Diagramm

M_{2}
[figure: ϕ]
[figure: M_{1}; φ; ψ; M]

kommutiert.

Satz 1.15 Für jeden Modul M sind die folgenden Aussagen äquivalent:

(a) M ist rein injektiv.

(b) M ist ein direkter Summand in jeder reinen Erweiterung.

(c) Jeder p.p. Typ über A ⊆ M, der in M endlich realisiert ist, ist in M realisiert.

Beweis. (a)⇒(b): Sei M_{0} eine reine Erweiterung von M. Wir wenden die Definition auf das Diagramm

\begin{matrix}M_{0} \\ M & & \overline{id ^{}} & M \end{matrix}

an, um einen Homomorphismus h : M_{0} → M zu erhalten. Damit ist

(3.2) M_{0} = M ⊕ ker h.

(b)⇒(c): Sei Φ(x̄) ein Typ über A, der in M endlich realisiert ist. Nach Lemma 1.9 ist Φ(x̄) in einer elementaren Erweiterung M_{0} von M realisierbar, sei c̄ ∈ M_{0} eine solche Realisierung. Jede elementare Erweiterung ist rein und deshalb gibt es nach (b) einen Modul M_{1}, so daß M_{0} = M ⊕ M_{1} gilt. Damit hat c̄ die Gestalt c̄ = (m̄, n̄) mit m̄ ∈ M und n̄ ∈ M_{1}. Homomorphismen übertragen die Gültigkeit von p.p. Formeln, die Projektion von M_{0} auf M ist ein Homomorphismus. Es folgt, daß Φ in M durch m̄ realisiert wird.

(c)⇒(a): Wir gehen von der Situation

\begin{matrix}M_{2} \\ M_{1} & ^{f } & \overline{g ^{}} & M \end{matrix}

aus, wobei f eine reine Einbettung ist, und suchen einen Homomorphismus g̃ : M_{2} → M, so daß das dann enstandene Diagramm kommutiert. Sei h : A → M eine maximale Erweiterung von g unter der Bedingung, daß h ein partieller Homomorphismus von M_{2} nach M ist. Der p.p. Typ

(3.3) \begin{matrix}Φ(x) & = & h(tp_{M_{2}}^{+}(b/A)) \\ & = & \{φ(x, h(ā)) : M_{2} ⊧ φ[b, ā], ā ∈ A, φ ist eine p.p. Formel \} \end{matrix}

ist in M endlich realisiert, denn sind zum Beispiel die Formeln φ_{i}(x, h(ā)) (i < n) in Φ, dann ist M_{2} ⊧ ∃x ⋀_{i<n} φ_{i}(x, ā) und deshalb M ⊧ ∃x ⋀_{i<n} φ_{i}(x, h(ā)). Aus (c) folgt, daß Φ(x) in M realisiert wird durch ein c ∈ M. Dann ist h̃ = h ∪ {(b, c)} eine Erweiterung von h; h war aber maximal gewählt, also muß dom(h) = M_{2} sein, wir setzen g̃ = h̃ und haben die Behauptung bewiesen. □

Korollar 1.16 M ist genau dann rein injektiv, wenn jeder partielle Homomorphismus von M_{0} nach M zu einem Homomorphismus von M_{0} nach M erweitert werden kann.

Die Behauptung folgt sofort aus dem Beweisschritt (c)⇒(a) des letzten Beweises.

Lemma 1.17 Erfüllt M die absteigende Kettenbedingung für p.p. definierbare Untergruppen, dann ist M rein injektiv.

Beweis. Angenommen, es existiert keine unendlich absteigende Folge von p.p. definierbaren Untergruppen von M. Dann existiert für jeden p.p. Typ Φ(x̄) über A ⊆ M eine endliche Konjunktion von Formeln aus Φ(x̄), so daß die durch sie definierte Gruppe minimal ist, sei ⋀_{i<m} φ_{i}(x̄, ā_{i}) diese Konjunktion. Jetzt nehmen wir an, daß Φ(x̄) endlich in M realisiert wird, also gilt M ⊧ ∃x̄ ⋀_{i<m} φ_{i}(x̄, ā_{i}). Damit existiert ein ā ∈ M mit M ⊧ ⋀_{i<m} φ_{i}[ā]. Wegen der Minimalität der durch unsere Konjunktion definierten Gruppe gilt ā ∈ ϕ(M^{n}, b̄) mit b̄ ∈ A für alle ϕ ∈ Φ, Φ wird durch ā realisiert. Mit Satz 1.15 folgt nun die Behauptung. □

1.4 Hüllen

Definition. Sei A Teilmenge eines rein injektiven Moduls M. H(A) wird eine Hülle von A in M genannt, wenn folgendes gilt:

(i) H(A) ist ein rein injektiver reiner Untermodul von M mit A ⊆ H(A).

(ii)

Ist B ein rein injektiver reiner Untermodul von M mit A ⊆ B ⊆ H(A), dann ist B = H(A).

Satz 1.18 Sei A Teilmenge eines rein injektiven Moduls M, dann existiert eine Hülle H(A) von A in M; ist H(B) eine Hülle von B in einem rein injektiven Modul M_{0}, und ist f : A → B ein partieller Isomorphismus von M nach M_{0}, dann kann f zu einem Isomorphismus von H(A) nach H(B) erweitert werden.

Beweis. Sei X die Menge aller Untermoduln von M, die A enthalten, und zwar derart, daß

(4.1) C ∈ X ⇔ i : A ↪ C ist p.p. wesentlich

gilt. X ist nicht leer, zum Beispiel ist das Erzeugnis ⟨A⟩_{M} von A in X enthalten, denn für einen partiellen Isomorphismus f : A → B von M nach M_{0} sind die beiden folgenden Implikationen für eine p.p. Formel φ erfüllt:

(4.2) \begin{matrix}M ⊧ φ[ā] ∧ φ[b̄] & ⇒ & M ⊧ φ[ā − b̄] ⇒ M_{0} ⊧ φ[f(ā − b̄)] \\ M_{0} ⊧ φ[fā] ∧ φ[fb̄] & ⇒ & M_{0} ⊧ φ[fā − fb̄] ⇒ M ⊧ φ[ā − b̄]. \end{matrix}

Damit ist die Menge {ā : M ⊧ φ[ā] ⇔ M_{0} ⊧ φ[fā]} ein Untermodul von M^{n}, der A^{n} und damit auch ⟨A⟩_{M}^{n} enthält, und die Abbildung i : A ↪ ⟨A⟩_{M} ist p.p. wesentlich. Wir wenden das Zornsche Lemma auf die Menge X an und erhalten ein maximales Element aus X, nennen wir es D. Sei Φ(x̄) ein p.p. Typ über einer Teilmenge von D, der in D endlich realisiert wird. Wir wählen einen maximalen p.p. Typ p(x̄) ∈ S^{+}(D), der Φ(x̄) enthält; p(x̄) wird durch ein Tupel b̄ ∈ M in M realisiert. Aus Lemma 1.11 folgt, daß i : D ↪ D∪{b̄} p.p. wesentlich ist und damit auch j : A ↪ D∪{b̄}. D war aber maximal gewählt, das bedeutet b̄ ∈ D, und nach Satz 1.15 ist D rein injektiv. Gilt M ⊧ φ[ā] für eine p.p. Formel φ mit Parametern aus D, dann ist φ wiederum in einem maximalen p.p. Typen über D enthalten, der in M durch ein Tupel b̄ ∈ M realisiert wird. Mit demselben Argument wie oben ist b̄ ∈ D und damit D rein in M.

Sei nun auch E ein rein injektiver reiner Untermodul von M und A ⊆ E ⊆ D. Weil E rein injektiv ist, existiert ein Homomorphismus g : M → E, der eingeschränkt auf E die Identität ist. Also ist g|_{A} ein partieller Isomorphismus von M nach E. Dann ist aber auch g|_{D} ein partieller Isomorphismus und D = E.

Jetzt zur zweiten Behauptung des Satzes: Weil H(B) rein in M_{0} ist, ist der partielle Isomorphismus f : A → B von M nach M_{0} auch ein partieller Isomorphismus von M nach H(B). Dieser kann nach Korollar 1.16 zu einem Homomorphismus f′ : M → H(B) erweitert werden; f′|_{H(A)} ist dann ein partieller Homomorphismus von M nach H(B) und, weil i : A ↪ H(A) p.p. wesentlich ist, auch ein Isomorphismus von H(A) nach H(B). □

Satz 1.18 sagt, daß Hüllen bis auf Isomorphie eindeutig bestimmt sind, er sagt aber mehr als nur das: Ein Typ der Gestalt p(x) = tp_{M}^{+}(a)∪tp_{M}^{−}(a) wird p.p. vollständig genannt. Angenommen nicht nur a sondern auch ein anderes Element b ∈ M realisiert p, dann ist f = (a, b) ein partieller Isomorphismus von M nach M. Das bedeutet aber, daß H(a) und H(b) zueinander isomorph sind; H(a) ist also durch p bestimmt, und darum schreiben wir oft H(p) für H(a).

Definitionen. Wir brauchen ein paar Begriffe aus der Modelltheorie: Sei λ eine Kardinalzahl und A eine Struktur. Wir sagen, A ist λ-saturiert, wenn für jede Menge X von Elementen aus A mit |X| < λ jeder vollständige Typ mit einer freien Variablen über X bezüglich A durch Elemente aus A realisiert wird. Außerdem sagen wir, daß A saturiert ist, wenn A |A|-saturiert ist, und daß A schwach saturiert ist, wenn A 0-saturiert ist.

Satz 1.19 Sei λ eine beliebige Kardinalzahl. Jede Struktur ist elementar äquivalent zu einer λ-saturierten Struktur.

Lemma 1.20 Ist die Struktur M λ-saturiert, die Kardinalität der Struktur M′ kleiner λ und M ≡ M′, dann existiert eine elementare Einbettung von M′ in M.

Beweise für sowohl Satz 1.19 als auch Lemma 1.20 findet man in [6].

Satz 1.21 Ist der R-Modul M (|R| + ℵ_{0})^{+}-saturiert, dann ist M rein injektiv.

Beweis. Sei f : M → M_{1} eine elementare Erweiterung. Wir behaupten, daß für jeden k-Tupel m̄_{1} ∈ M_{1} ein k-Tupel b̄ ∈ M existiert, so daß für jede p.p. Formel ϕ(x_{0}, …, x_{n−1}, y_{0}, …, y_{k−1}) und für jeden n-Tupel m̄ ∈ M

(4.3) M_{1} ⊧ ϕ[m̄, m̄_{1}] ⇒ M ⊧ ϕ[m̄, b̄]

gilt. Wir beweisen (4.3) durch Induktion über k: Weil elementare Erweiterungen unter anderem rein sind, gilt M_{1} ⊧ ϕ[m̄] ⇒ M ⊧ ϕ[m̄]. Sei nun (4.3) für alle p.p. Formeln, deren freie Variablen in der Menge {x_{0}, …, x_{n−1}, y_{0}, …, y_{k−1}} enthalten sind, gezeigt. Wir betrachten die Menge Ψ(z) aller p.p. Formeln ψ(m̄, b̄|_{k}, z), für die M_{1} ⊧ ψ[m̄, m̄_{1}|_{k}, m_{1k}] gilt. Aus Lemma 1.2 (iii) folgt, daß für jede p.p. Formel ϕ(x̄, y) und ā, c̄, b ∈ M genau dann aus M ⊧ ϕ[ā, b] die Aussage M ⊧ ϕ[c̄, b] folgt, wenn M ⊧ ∀z(ϕ(ā, z) ↔ ϕ(c̄, z)) erfüllt ist. Wegen M ⪯ M_{1} gilt dasselbe für M_{1} anstelle von M. Also muß in Ψ für jede p.p. Formel nur jeweils eine Belegung mit Parametern berücksichtigt werden, das bedeutet aber, |Ψ| ≤ |R| + ℵ_{0}. Aus der (|R|+ℵ_{0})^{+}-Saturiertheit von M folgt, daß Ψ in M durch ein Element a ∈ M realisiert wird; sei b_{k} = a, damit ist (4.3) erfüllt. Sei nun Φ(x̄) ein p.p. Typ über A ⊆ M, der in M endlich realisiert ist. Dann ist Φ in einer elementaren Erweiterung M_{2} von M realisiert. Aus (4.3) folgt sofort, daß Φ in M durch ein Tupel b̄ ∈ M realisiert ist. Nach Satz 1.15 ist damit M rein injektiv. □

Definition. Ein Modul \overline{M} wird eine rein injektive Hülle von M genannt, wenn er die beiden folgenden Eigenschaften erfüllt:

(i) \overline{M} ist rein injektiv und eine reine Erweiterung von M.

(ii)

Ist M_{0} ebenfalls eine rein injektive und reine Erweiterung von M, dann ist \overline{M} zu einem reinen Untermodul von M_{0} isomorph, der entsprechende Isomorphismus ist auf M die Identität.

Satz 1.22 Jeder Modul besitzt eine rein injektive Hülle, die bis auf Isomorphie eindeutig ist, der entsprechende Isomorphismus ist auf dem Modul selbst die Identität.

Beweis. Sei λ die Kardinalzahl max{|M|^{+}, (|R| + ℵ_{0})^{+}} und M_{1} ein λ-saturierter Modul, der elementar äquivalent zu M ist. Nach Lemma 1.20 ist M eine elementare Unterstruktur von M_{1}, nach Satz 1.21 ist M_{1} rein injektiv. Der Modul M_{1} ist also eine rein injektive elementare Erweiterung von M. Nun sei \overline{M} die Hülle von M in M_{1}; \overline{M} ist rein injektiv, und weil die erste Erweiterung elementar war, ist M auf jeden Fall rein in \overline{M}. M_{0} sei nun eine zweite rein injektive reine Erweiterung von M. Die Identität auf M ist ein partieller Isomorphismus von M_{1} nach M_{0}, dieser kann zu einem Isomorphismus von \overline{M} auf die Hülle von M in M_{0} fortgesetzt werden, die mit Sicherheit rein in M_{0} ist. □

Korollar 1.23 Jeder Modul ist eine elementare Unterstruktur seiner rein injektiven Hülle; damit ist vor allem jeder Modul elementar äquivalent zu einem rein injektiven Modul.

Beweis. Wir konstruierten \overline{M} als reinen Untermodul einer elementaren Erweiterung von M, damit ist auch \overline{M} selbst eine elementare Erweiterung von M. □

1.5 Unzerlegbare Moduln

Definition. Ein Modul, der nicht der Nullmodul ist, heißt unzerlegbar, wenn im Fall, daß er die direkte Summe von zwei Moduln ist, einer der beiden Summanden der Nullmodul ist.

Lemma 1.24 Direkte Summanden rein injektiver Moduln sind rein injektiv.

Beweis. Sei M rein injektiv und M_{0} ein direkter Summand von M. Wenn p ein p.p. Typ über A ⊆ M_{0} ist, der in M_{0} endlich realisiert wird, dann wird p in M realisiert; weil nun aber M_{0} rein in M ist, wird p auch in M_{0} realisiert und damit ist M_{0} rein injektiv. □

Lemma 1.25 Sei M rein injektiv und nicht der Nullmodul. M ist genau dann unzerlegbar, wenn M = H(a) für alle a ∈ M\{0} gilt.

Beweis. Wenn M = M_{0} ⊕ M_{1} eine nichttriviale Zerlegung ist und a ∈ M_{0}\{0}, dann kann M nicht die Hülle von a sein, denn M_{0} ist rein in M und nach Lemma 1.24 rein injektiv. Angenommen, M ≠ H(a) für ein a ∈ M\{0}; i : H(a) ↪ M ist eine reine Einbettung, und weil H(a) rein injektiv ist, existiert ein Homomorphismus h : M → H(a), so daß M = H(a) ⊕ ker(h) eine nichttriviale Zerlegung von M ist. □

Ob ein rein injektiver Modul unzerlegbar ist, kann an seinem Endomorphismenring abgelesen werden:

Satz 1.26 (Zimmermann, Zimmermann-Huisgen) Ein rein injektiver Modul M, der nicht der Nullmodul ist, ist genau dann unzerlegbar, wenn sein Endomorphismenring lokal ist, das heißt, für alle f ∈ End(M) ist f oder 1 − f ein Automorphismus von M.

Beweis. Sei M = M_{1} ⊕ M_{2} eine nichttriviale Zerlegung von M, pr_{1} und pr_{2} die entsprechenden Projektionen. Dann ist pr_{1} + pr_{2} = 1, aber weder pr_{1} noch pr_{2} sind Automorphismen von M.

Wir nehmen jetzt an, M sei unzerlegbar und f sei ein Endomorphismus von M und 1 − f kein Automorphismus. Wir müssen zeigen, daß f dann ein Automorphismus ist. Wähle ein a ∈ M\{0}. Dann ist M = H(a) und jeder Endomorphismus g von M, der eingeschränkt auf a ein partieller Isomorphismus ist, ist ein Automorphismus. Sei f(a) = b. Nach Annahme ist 1 − f kein partieller Isomorphismus auf a, also existiert eine p.p. Formel φ, so daß

(5.1) M ⊧ ¬φ[a] ∧ φ[a − b]

erfüllt ist. Sei jetzt Φ(x) ein p.p. Typ, der tp_{M}^{+}(b) erweitert, mit φ(a − x) konsistent und unter diesen Bedingungen maximal ist. Sei Φ(x) ∪ {φ(x − a)} durch c realisiert; dann gilt (5.2) tp_{M}^{+}(a) ⊆ tp_{M}^{+}(b) ⊆ tp_{M}^{+}(c) und deshalb existiert ein Endomorphismus g, der den partiellen Homomorphismus a ↦ c erweitert. Die Gleichung (5.3) a − g(c) = (g + 1)(a − c) zusammen mit M ⊧ φ[a − c] impliziert M ⊧ φ[a − g(c)]; g(c) realisiert damit auch Φ(x) ∪ {φ(a − x)}. Weil wir Φ maximal gewählt hatten, gilt (5.4) tp_{M}^{+}(c) = tp_{M}^{+}(g(c)) = Φ und weil M = H(c) ist, ist g ein Automorphismus. Das bedeutet aber (5.5) tp_{M}^{+}(b) ⊆ tp_{M}^{+}(c) = tp_{M}^{+}(a) ⊆ tp_{M}^{+}(b) und damit ist auch f ein Automorphismus. □

Der Raum der unzerlegbaren Moduln

2.1 Unzerlegbare Typen

Definition. Sei p(x) ein p.p. vollständiger Typ. Wir nennen p unzerlegbar, wenn H(p) unzerlegbar ist.

Satz 2.1 Ein p.p. vollständiger Typ p ist genau dann unzerlegbar, wenn die Formel x = 0 nicht in p enthalten ist und für je zwei p.p. Formeln ψ_{1}, ψ_{2}, die nicht in p enthalten sind, eine p.p. Formel φ ∈ p existiert, so daß (ψ_{1} ∧φ)+(ψ_{2} ∧φ) auch nicht in p liegt.

Beweis. Sei a ∈ M\{0} so gewählt, daß H(a) = H(p) gilt. Wir nehmen zuerst an, daß p die Bedingung oben nicht erfüllt. Ist x = 0 in p, dann ist a = 0, was nicht sein darf. Seien jetzt zwei p.p. Formeln ψ_{1} und ψ_{2}, die nicht in p enthalten sind, gegeben, so daß für alle φ ∈ p^{+}

(1.1) (ψ_{1} ∧ φ) + (ψ_{2} ∧ φ) ∈ p

gilt. Dann ist

(1.2) Φ = {a = x + y, ψ_{1}(x), ψ_{2}(y)} ∪ p^{+}(x) ∪ p^{+}(y)

ein Typ, der in H(a) endlich realisiert wird; weil H(a) rein injektiv ist, wird Φ in H(a) realisiert. Sei (b, c) eine solche Realisierung. Wähle einen Endomorphismus f von H(a) derart, daß f(a) = b gilt. Wegen H(a) ⊧ ψ_{1}[f(a)] ist f kein Automorphismus, wegen H(a) ⊧ ψ_{2}[(1 − f)(a)] ist 1 − f auch kein Automorphismus, darum ist End(H(a)) nicht lokal und H(a) nicht unzerlegbar.

Jetzt die umgekehrte Beweisrichtung: Angenommen, End(H(a)) ist nicht lokal. Wir haben also einen Endomorphismus f von H(a), so daß weder f noch 1 − f ein Automorphismus ist. Dann sind f|_{a} und (1 − f)|_{a} auch nicht partiell isomorph, damit existieren p.p. Formeln ψ_{1} und ψ_{2}, die nicht in p enthalten sind, mit

(1.3) H(a) ⊧ ψ_{1}[f(a)] ∧ ψ_{2}[(1 − f)(a)].

Aus

(1.4) a = f(a) + (1 − f)(a)

folgt H(a) ⊧ ((ψ_{1} ∧ φ) + (ψ_{2} ∧ φ))[a] für alle φ ∈ p^{+}. □

Wir wollen auf der Menge der Invarianzaussagen eine Ordnung einführen, so daß

(1.5) φ/ψ ≤ φ′/ψ′ ⇒ φ/ψ(M) ≤ φ′/ψ′(M)

für jeden Modul M gilt. Aus

(1.6) ψ(M^{n}) ≤ ψ′(M^{n}) ≤ φ′(M^{n}) ≤ φ(M^{n})

folgt sofort φ′/ψ′(M) ≤ φ/ψ(M) und aus der Modularität des Verbandes der p.p. definierbaren Untergruppen erhält man für beliebige p.p. Formeln ψ, θ die Gleichung (ψ/ψ ∧ θ)(M) = (ψ + θ/θ)(M). Durch diese Beobachtungen motiviert definieren wir: Sei X die kleinste Menge von Paaren von p.p. Formeln, in der

(1.7) (φ/ψ, φ′/ψ′) enthalten ist, wenn ψ ⊢ ψ′ ⊢ φ′ ⊢ φ (modulo der Theorie der Moduln) gilt und

(1.8) (φ/φ ∧ θ, φ + θ/θ), (φ + θ/θ, φ/φ ∧ θ) für alle p.p. Formeln φ, θ enthalten sind.

Wir bilden die transitive Hülle von X und bezeichnen die erhaltene Relation mit ≤.

Lemma 2.2 Die auf der Menge der Invarianzaussagen eingeführte Relation ≤ ist eine Ordnungsrelation und erfüllt (1.5).

Beweis. Nach Definition ist die Relation transitiv, aus (1.7) folgt die Reflexivität, aus φ ≤ ψ und ψ ≤ φ folgt, daß φ ↔ ψ eine Tautologie innerhalb der Theorie der Moduln ist. Aus (1.7) folgt auch sofort die Gültigkeit von (1.5). □

Wir schreiben φ/ψ ∈ p für den Ausdruck φ ∈ p ∧ ¬ψ ∈ p, dabei ist φ/ψ eine Invarianzaussage und p ein Typ.

Lemma 2.3 Sei Ψ eine endliche Teilmenge eines unzerlegbaren Typen p. Dann existiert eine Invarianzaussage φ/ψ ∈ p, so daß für alle p.p. Formeln ϕ die beiden Implikationen

¬ϕ ∈ Ψ ⇒ ϕ ∧ φ ⊢ ψ
ϕ ∈ Ψ ⇒ φ ⊢ ϕ

erfüllt sind. Damit ist φ∧¬ψ → ⋀ Ψ eine Tautologie, dabei steht ⊢ wieder für Folgern modulo der Theorie der Moduln.

Beweis. Seien θ_{1}/ϕ_{1}, θ_{2}/ϕ_{2} ∈ Ψ. Dann gilt ϕ_{1}, ϕ_{2} ∉ p und deshalb existiert nach Satz 2.1 eine p.p. Formel φ′ ∈ p, so daß

(1.9)  ψ̄ = (φ′ ∧ ϕ_{1}) + (φ′ ∧ ϕ_{2}) ∉ p

gilt. Setze φ̄ = φ′ ∧θ_{1} ∧θ_{2}. Aus der p.p. Vollständigkeit von p folgt φ̄ ∈ p und ¬ψ̄ ∈ p. Wegen

(1.10) ϕ_{1} ∧ φ′ ∧ θ_{1} ∧ θ_{2} ⊢ (φ′ ∧ ϕ_{1}) + (φ′ ∧ ϕ_{2}) ⊢ φ′ ∧ θ_{1} ∧ θ_{2} ⊢ θ_{1}

ist φ̄/ψ̄ eine Invarianzaussage, und zusammen mit einer ähnlichen Rechnung folgt

(1.11)  ϕ_{i} ∧ φ̄ ⊢ ψ̄ ⊢ φ̄ ⊢ θ_{i}  (i = 1, 2).

Weil Ψ endlich ist, ist auch die Menge der Invarianzaussagen θ/χ ∧ θ mit θ, ¬χ ∈ Ψ endlich. Durch wiederholtes Anwenden der oben angegebenen Prozedur erhalten wir eine Invarianzaussage φ/ψ mit der Eigenschaft

(1.12)  χ ∧ θ ∧ φ ⊢ ψ ⊢ φ ⊢ θ  für alle θ, ¬χ ∈ Ψ.

Ist also ϕ ∈ Ψ, dann haben wir φ ⊢ ϕ, ist ¬ϕ ∈ Ψ, dann gilt ϕ ∧ φ ⊢ ϕ ∧ φ ∧ θ ⊢ ψ, wobei θ ∈ Ψ beliebig gewählt ist. □

Lemma 2.4 Sei φ/ψ eine Invarianzaussage, wobei φ und ψ p.p. Formeln in einer freien Variablen sind; wenn φ/ψ(M) > 1 erfüllt ist, dann existiert ein unzerlegbarer Typ, der in M endlich realisiert wird und φ/ψ enthält.

Beweis. Sei Φ die Menge aller p.p. Formeln und Negationen von p.p. Formeln mit der freien Variablen x, die zu φ(x), ¬ψ(x) oder ¬(x = 0) äquivalent sind (modulo der Theorie der Moduln). Sei X die Menge aller p.p. Typen mit der freien Variablen x, so daß für jedes Element Ψ ∈ X die Menge Ψ ∪ Φ in M endlich realisiert werden kann. Wegen Φ^{+} ∈ X ist X nicht leer, außerdem ist X durch Inklusion induktiv geordnet. Wir wählen mit dem Zornschen Lemma ein maximales Element p^{+} aus X aus und setzen (1.13) p = p^{+} ∪ {¬ϕ : ϕ ∉ p^{+} und ϕ(x) ist eine p.p. Formel }.

Aus Lemma 1.10 folgt p^{+} ∪ Φ ⊢_{M} ¬θ für alle p.p. Formeln θ mit θ ∉ p; p hat damit die Gestalt tp_{M}^{+}(a) ∪ tp_{M}^{−}(a) für ein a ∈ M und ist damit p.p. vollständig. Wir zeigen mit Hilfe des Satzes 2.1, daß p unzerlegbar ist. Seien also zwei p.p. Formeln ψ_{1}, ψ_{2} ∉ p gegeben. Aus der p.p. Vollständigkeit von p folgt, daß Formeln φ̄ ∈ p^{+}, ¬ψ̄_{1}, …, ¬ψ̄_{n} ∈ Φ existieren derart, daß

(1.14) ⋀{φ̄, ¬ψ̄_{1}, …, ¬ψ̄_{n}} ⊢_{M} ¬ψ_{1} ∧ ¬ψ_{2}

erfüllt ist. Außerdem existiert für zwei Formeln ¬ϕ_{1}, ¬ϕ_{2} ∈ Φ eine Formel ϕ_{3} ∈ Φ^{+}, so daß

(1.15) ¬((ϕ_{3} ∧ ϕ_{1}) + (ϕ_{3} ∧ ϕ_{2})) ∈ p

gilt. Wegen (1.15) können nun φ̂_{i} ∈ Φ^{+} (1 ≤ i ≤ n) mit folgenden Eigenschaften bestimmt werden:

(1.16) \begin{matrix}ψ̂_{1} & = & (ψ_{1} ∧ φ̂_{1}) + (ψ_{2} ∧ φ̂_{1}) \\ ψ̂_{i+1} & = & (ψ̄_{i+1} ∧ φ̂_{i+1}) + (ψ̂_{i} ∧ φ̂_{i+1}) \\ ¬ψ̂_{n} & ∈ & p. \end{matrix}

Sei φ = φ̄ ∧ φ̂_{1} ∧ … ∧ φ̂_{n}. Dann gilt M ⊧ φ ∧ ¬ψ̂_{n} → ¬ψ̂_{1}. Also M ⊧ φ ∧ ψ̂_{1} → ψ̂_{n} und deshalb M ⊧ (φ ∧ ψ_{1}) + (φ ∧ ψ_{2}) → ψ̂_{n}. Das impliziert (φ ∧ ψ_{1}) + (φ ∧ ψ_{2}) ∉ p, und p ist unzerlegbar. □

2.2 Konstruktion des Raumes der unzerlegbaren Moduln

Wenn wir isomorphe Moduln nicht unterscheiden, dann kann jeder rein injektive unzerlegbare Modul durch einen unzerlegbaren Typen beschrieben werden. Es folgt, daß die Isomorphietypen unzerlegbarer rein injektiver R-Moduln eine Menge bilden, für die wir I(R) schreiben. Lemma 2.3 ermöglicht es uns, eine Topologie auf I(R) einzuführen. Wir schreiben M^{∼} für den Isomorphietyp von M, das heißt M^{∼} = {M′ : M ≅ M′}. Für jede Invarianzaussage φ/ψ von p.p. Formeln in einer freien Variablen schreiben wir

(φ/ψ) = {M^{∼} ∈ I(R) : φ/ψ(M) > 1}.

Wegen M ≅ M′ ⇒ φ/ψ(M) = φ/ψ(M′) ist gegen diese Schreibweise nichts einzuwenden.

Satz 2.5 Die Menge {(φ/ψ) : φ/ψ ist eine Invarianzaussage} ist eine Basis für eine Topologie auf I(R).

Beweis. Sei p ein unzerlegbarer Typ, H(p)^{∼} ∈ (φ_{i}/ψ_{i}) für i = 1, 2 und p durch a ∈ H(p) realisiert. Wegen φ_{i}/ψ_{i}(H(p)) > 1 gibt es Elemente a_{1}, a_{2} ∈ H(p), so daß

(2.1)  H(p) ⊧ φ_{i}[a_{i}] ∧ ¬ψ_{i}[a_{i}]  (i = 1, 2)

erfüllt ist. Aus Lemma 1.11 folgt

(2.2) tp_{H(p)}^{+}(a_{i}/{a, a_{i}}) ⊢_{H(p)} tp_{H(p)}(a_{i}/{a, a_{i}}),

also existieren p.p. Formeln ϕ_{i}(x, a) ∈ tp_{H(p)}^{+}(a_{i}/{a, a_{i}}) mit

(2.3) ϕ_{i}(x, a) ⊢_{H(p)} φ_{i}(x) ∧ ¬ψ_{i}(x).

Deshalb ist die Menge

(2.4) Ψ = {∃y(ϕ_{i}(y, x) ∧ φ_{i}(y)), ∀y(ϕ_{i}(y, x) → ¬ψ_{i}(y)) : (i = 1, 2)}

in p enthalten. Lemma 2.3 sichert uns nun die Existenz einer Invarianzaussage θ/χ ∈ p mit θ ∧ ¬χ → ⋀ Ψ zu. Das bedeutet

(2.5) H(p) ∈ (θ/χ) ⊆ (φ_{i}/ψ_{i}).

Damit erfüllt die Menge {(φ/ψ) : φ/ψ ist eine Invarianzaussage} eine hinreichende Bedingung für eine Basis. □

Wir nennen I(R) mit der oben definierten Topologie den Raum der unzerlegbaren R-Moduln.

Korollar 2.6 Die abgeschlossenen Teilmengen von I(R) sind genau die Mengen

I_{M} = {H(p)^{∼} ∈ I(R) : p ist endlich realisierbar in M und ein unzerlegbarer Typ}

Beweis. Sei A eine abgeschlossene Teilmenge von I(R) und M_{0} = ⨁{M : M^{∼} ∈ A}. Dann ist A = I_{M_{0}}. Sei I_{M} gegeben. Bezeichne mit X die Menge {(φ/ψ) ∈ I(R) : φ/ψ(M) = 1}. Die Aussage φ/ψ(M) = 1 ist äquivalent zu M ⊧ ∀x(φ(x) ↔ ψ(x)). Sei H(p) ein Summand von M; weil H(p) rein in M ist, haben wir H(p) ⊧ ∀x(φ(x) ↔ ψ(x)) und damit φ/ψ(H(p)) ≯ 1. Gilt aber φ/ψ(H(p)) > 1, dann existiert ein Element a ∈ H(p) ⊆ M mit M ⊧ φ[a] ∧ ¬ψ[a], also gilt φ/ψ(M) > 1. Insgesamt haben wir

(2.6) φ/ψ(M) = 1 ⇔ φ/ψ(H(p)) = 1.

Es folgt I_{M} = I(R)\ ⋃ X, und damit ist I_{M} abgeschlossen. □

2.3 Mehr über elementare Äquivalenz

Definition. Zwei Teilmengen A und B eines rein injektiven Moduls M werden voneinander unabhängig genannt, wenn für jede p.p. Formel φ(x̄, ȳ)

(3.1)  M ⊧ φ[ā, b̄] ⇒ M ⊧ φ[¯0, b̄]  (und damit auch M ⊧ φ[ā, ¯0])

erfüllt ist, wobei ā ein beliebiges Tupel aus A und b̄ ein beliebiges Tupel aus B ist.

Lemma 2.7 Seien A und B voneinander unabhängig und i : B ↪ B′ eine p.p. wesentliche Einbettung. Dann sind

(i) A und B′ voneinander unabhängig und
(ii) M = H(A) ⊕ H(B) ⊕ M_{0}.

Beweis.(i) Mit 0_{A} werde die Abbildung ā ↦ ¯0 für alle ā ∈ A bezeichnet. Aus (3.1) folgt, daß f = id_{B} ∪ 0_{A} ein partieller Endomorphismus von M ist; wegen M ⊧ φ[¯0, b̄] ∧ φ[ā, ¯0] → φ[ā, b̄] ist f sogar ein partieller Automorphismus. Weil B′ eine p.p. wesentliche Erweiterung von B ist, ist auch id_{B′} ∪ 0_{A} ein partieller Automorphismus von M, und (3.1) behält seine Gültigkeit, wenn wir die Tupel b̄ aus B′ wählen.

(ii) Zweimaliges Anwenden von (i) ergibt, daß H(A) und H(B) voneinander unabhängig sind und daß id_{H(A)} ∪ 0_{H(B)} ein partieller Homomorphismus von M ist. Wir erweitern diesen zu einem Homomorphismus h : M → H(A). Dann ist M = H(A) ⊕ ker h, H(B) ist aber ein direkter Faktor von ker h. □

Sei U ein rein injektiver unzerlegbarer Modul. Wir bezeichnen mit card_{U}(M) die Kardinalität der Menge aller direkten Faktoren von M, die isomorph zu U sind.

Lemma 2.8 Ist M rein injektiv und schwach saturiert, und ist M_{0} rein injektiv und außerdem elementar äquivalent zu M, dann gilt

card_{U}(M_{0}) ≤ card_{U}(M).

Beweis. Sei p ein unzerlegbarer Typ, so daß H(p) = U erfüllt ist und sei κ eine Kardinalzahl. Der Typ

(3.2) \begin{matrix}p_{κ}(x̄) = ⋃_{i<κ} p(x_{i}) & ∪ & \{φ(x_{i1}, …, x_{in}) → φ(0, x_{i2}, …, x_{in}) : \\ & & φ ist eine p.p. Formel , i_{1}, …, i_{n} < κ, i_{k} ≠ i_{l} für k ≠ l\} \end{matrix}

wird in M_{0} realisiert, wenn M_{0} κ zu U isomorphe Untermoduln enthält, die voneinander unabhängig sind und deren direkte Summe nach Lemma 2.7 ein direkter Faktor von M_{0} ist. Das bedeutet aber nichts anderes als κ ≤ card_{U}(M_{0}). Ist nun p_{κ}(x̄) in M_{0} realisiert, dann ist vor allem p_{κ}(x̄) in M_{0} endlich realisiert. Wegen der elementaren Äquivalenz von M und M_{0} ist damit p_{κ}(x̄) aber auch in M endlich realisiert und wegen der schwachen Saturiertheit von M auch in M realisiert. Deswegen ist die Implikation

(3.3) card_{U}(M_{0}) ≥ κ ⇒ card_{U}(M) ≥ κ

für jede beliebige Kardinalzahl κ erfüllt, daraus folgt die Behauptung. □

Satz 2.9 Sei M ein schwach saturierter rein injektiver Modul. Wenn M eine Zerlegung

M = \overline{⨁_{i∈I} U_{i}} ⊕ E

besitzt, wobei die Moduln U_{i} rein injektiv und unzerlegbar sind, und E keine unzerlegbaren direkten Faktoren hat, dann sind M und \overline{⨁_{i∈I} U_{i}} elementar äquivalent.

Beweis. Nach Satz 1.7 müssen wir zeigen, daß für jede Invarianzaussage φ/ψ entweder φ/ψ(M) = φ/ψ(\overline{⨁_{i∈I} U_{i}}) erfüllt ist, oder daß beide Kardinalzahlen unendlich sind. Das zeigen wir, indem wir

(3.4) φ/ψ(E) > 1 ⇒ φ/ψ(\overline{⨁_{i∈I} U_{i}}) = ∞

nachweisen. Dafür nehmen wir an, daß φ/ψ(E) > 1 gilt. Lemma 2.4 sichert uns die Existenz eines unzerlegbaren Typen, der in E endlich realisiert ist und φ/ψ enthält. Darum existiert ein rein injektiver Modul M_{1}, der elementar äquivalent zu E ist, und ein unzerlegbarer Modul U mit card_{U}(M_{1}) > 0. Aus \overline{⨁_{i∈I} U_{i}} ⊕ M_{1} ≡ M und Lemma 2.8 folgt

(3.5) \begin{matrix}card_{U}(\overline{⨁_{i∈I} U_{i}}) + card_{U}(M_{1}) & = & card_{U}(\overline{⨁_{i∈I} U_{i}} ⊕ M_{1}) \\ & ≤ & card_{U}(M) \\ & = & card_{U}(\overline{⨁_{i∈I} U_{i}}). \end{matrix}

Aus (3.5) folgt mit card_{U}(M_{1}) > 1, daß card_{U}(\overline{⨁_{i∈I} U_{i}}) = ∞ gilt; aus Korollar 1.13 erhalten wir φ/ψ(\overline{⨁_{i∈I} U_{i}}) = ∞. □

Korollar 2.10 Jeder rein injektive Modul M ist elementar äquivalent zu einer direkten Summe rein injektiver unzerlegbarer Moduln.

Beweis. Wegen Satz 1.19 können wir davon ausgehen, daß M schwach saturiert ist. Sei (U_{i} : i ∈ I) eine Familie von rein injektiven unzerlegbaren Moduln, so daß die Summe ∑_{i∈I} U_{i} direkt, rein in M und maximal mit dieser Eigenschaft ist. Dann ist

(3.6) H(∑_{i∈I} U_{i}) ≅ \overline{⨁_{i∈I} U_{i}}

ein direkter Summand in M = H(∑_{i∈I} U_{i}) ⊕ E. Aus der Maximalität der Familie (U_{i} : i ∈ I) folgt, daß E keine direkten unzerlegbaren Faktoren besitzt. Nach Satz 2.9 ist M elementar äquivalent zu \overline{⨁_{i∈I} U_{i}}, und Korollar 1.23 wiederum sagt, daß ⨁_{i∈I} U_{i} elementar äquivalent zu \overline{⨁_{i∈I} U_{i}} und damit zu M ist. □

Definition. Für einen Modul M und einen unzerlegbaren Modul U definieren wir

(3.7) Sz_{U}(M) = min{log_{φ/ψ(U)}φ/ψ(M) : φ/ψ ist eine Invarianzaussage};

dabei erweitern wir die Rechengesetze des Logarithmus um die folgenden Konventionen:

(3.8)  \begin{matrix}log_{1}(x) & = & log_{x}(∞) = ∞ \\ log_{α}(1) & = & log_{∞}(β) = 0  (α > 1, β < ∞). \end{matrix}

Lemma 2.11 Wenn M rein injektiv und schwach saturiert ist, dann gilt

Sz_{U}(M) = card_{U}(M) (mod ∞).

Beweis. Aus

(3.9) φ/ψ(M) = φ/ψ(U^{card_{U} (M)} ⊕ M_{0}) ≥ φ/ψ(U)^{card_{U} (M)}

folgt Sz_{U}(M) ≥ card_{U}(M). Um die zweite Ungleichung zu beweisen, wählen wir einen unzerlegbaren Typ p, so daß H(p) = U gilt. Wir unterscheiden zwei Fälle:

Fall 1: U ⊕ U ≡ U; Sz_{U}(M) > 0 impliziert φ/ψ(M) > 1 für alle φ/ψ ∈ p, damit ist aber p in M endlich realisiert, und wir haben card_{U}(M) > 0. Aus M ≡ M ⊕ U^{m} für alle m ∈ ℕ erhalten wir card_{U}(M) = ∞ und daraus Sz_{U}(M) ≤ card_{U}(M).

Fall 2: U ⊕ U ≢ U; in diesem Fall enthält p eine Invarianzaussage φ̄/ψ̄, für die φ̄/ψ̄(U) < ∞ gilt. Wir beweisen (3.10) n < Sz_{U}(M) ⇒ n < card_{U}(M)

durch vollständige Induktion über n. Aus (3.10) folgt sofort Sz_{U}(M) ≤ card_{U}(M). Sei (3.10) für n bewiesen und n + 1 ≤ Sz_{U}(M). Wir haben dann eine Zerlegung M = U^{n} ⊕ M_{0}. Für jede endliche Teilmenge Ψ von p existiert nach Lemma 2.3 eine Invarianzaussage φ/ψ ∈ p mit φ ∧ ¬ψ → ⋀ Ψ, vor allem ist φ/ψ ≤ φ̄/ψ̄, wenn φ̄/ψ̄ in Ψ ist, und damit φ/ψ(U) endlich, zum Beispiel φ/ψ(U) = m. Die Ungleichung

(3.11) m^{Sz_{U} (M)} ≤ φ/ψ(M) = m^{n} · φ/ψ(M_{0})

impliziert φ/ψ(M_{0}) > 1. Es folgt, daß für jede endliche Teilmenge Ψ von p die Aussage ∃x ⋀ Ψ(x) erfüllt ist, das heißt, p ist endlich realisierbar in M_{0}. Deswegen ist der Typ p_{n+1}, den wir im Beweis von Lemma 2.8 kennengelernt haben, realisiert in M, und wir haben n + 1 < card_{U}(M), was zu beweisen war. □

Satz 2.12 M_{1} und M_{2} sind genau dann elementar äquivalent, wenn Sz_{U}(M_{1}) = Sz_{U}(M_{2}) für alle unzerlegbaren Moduln U gilt.

Beweis. Nach Satz 1.19 sind M_{1} und M_{2} jeweils elementar äquivalent zu einem schwach saturierten Modul M_{3} bzw. M_{4}; diese beiden Moduln sind elementar äquivalent laut Satz 2.9, wenn sie bis auf Isomorphie die gleichen unzerlegbaren Moduln in gleicher Anzahl (modulo ∞) als direkte Summanden enthalten, dies ist aber nach Lemma 2.11 der Fall, wenn Sz_{U}(M_{1}) = Sz_{U}(M_{2}) für alle unzerlegbaren Moduln U erfüllt ist. □

Korollar 2.13 Wenn {(φ/ψ) : φ/ψ ∈ S} eine Basis von I(R) ist, dann ist für die Aussage, M_{1} und M_{2} sind elementar äquivalent,

φ/ψ(M_{1}) = φ/ψ(M_{2}) für alle φ/ψ ∈ S

eine notwendige und hinreichende Bedingung.

Beweis. Die Behauptung ist erfüllt, wenn Sz_{U}(M_{1}) bzw. Sz_{U}(M_{2}) allein durch die Invarianzaussagen, die in S vorkommen, bestimmt werden können. Dazu müssen wir zeigen, daß für einen rein injektiven schwach saturierten Modul

(3.12) min{log_{φ/ψ(U)}φ/ψ(M) : φ/ψ ∈ S} ≤ card_{U}(M)

erfüllt ist. Das folgt mit dem Beweis von Lemma 2.11 und

(3.13) U ⊕ U ≢ U impliziert, φ/ψ(U) ist endlich für ein φ/ψ ∈ S.

Sei φ̄/ψ̄(U) endlich und größer 1, dann existiert ein φ/ψ ∈ S mit (φ/ψ) ⊆ (φ̄/ψ̄). Angenommen, φ/ψ(U) ist nicht endlich. Dann existiert eine elementare Erweiterung N = U ⊕ M′ von U, so daß φ/ψ(N) > |U| ist. Nun ist aber φ/ψ(M′) > 1 und auch φ̄/ψ̄(M′) > 1, das ist ein Widerspruch zur Endlichkeit von φ̄/ψ̄(U) = φ̄/ψ̄(N). □

2.4 Entscheidbarkeit im Raum der unzerlegbaren Moduln

Nun wollen wir unser gesammeltes Wissen über den Raum I(R) dazu benutzen, bestimmte Theorien von R-Moduln auf Entscheidbarkeit zu untersuchen. Dafür brauchen wir aber noch ein paar Hilfsmittel aus Modell- und Rekursionstheorie.

Definition. Eine Theorie T einer Sprache L ist rekursiv axiomatisierbar, wenn T = Th(A) für eine rekursiv aufzählbare Menge A von Sätzen aus L ist. Eine Theorie ist vollständig, wenn T Modelle hat und je zwei dieser Modelle elementar äquivalent sind; eine dazu äquivalente Aussage ist: Für jeden Satz ϕ aus L ist entweder ϕ oder ¬ϕ in T enthalten.

Satz 2.14 Wenn die Theorie T einer rekursiv aufzählbaren Sprache L rekursiv axiomatisierbar und vollständig ist, dann ist T entscheidbar.

Beweis. Die Sätze von T können rekursiv aufgezählt werden, denn sei T = Th(A) und A rekursiv aufzählbar, dann können alle endlichen Folgen von Worten der Sprache L aufgezählt werden und die Folgen, die keine Beweise aus A sind, wieder gestrichen werden. Sei S = (ψ_{1}, ψ_{2}, …) so eine Aufzählung, genauer gesagt, eine Aufzählung der jeweils letzten Worte dieser endlichen Folgen. Um zu entscheiden, ob ϕ ∈ T eine wahre Aussage ist, fangen wir an, alle Konsequenzen aufzuzählen und kontrollieren für jedes ψ_{i}, ob ϕ = ψ_{i} oder ¬ϕ = ψ_{i} gilt. Weil T vollständig ist, muß eine der beiden Alternativen bei einem Schritt auftauchen, dann ist entschieden, ob ϕ ∈ T gilt oder nicht. □

Satz 2.15 (Feferman-Vaught)

(i)

Sind die Theorien der Moduln U_{i} (i < n < ω) entscheidbar, dann ist auch die Theorie von ∏_{i<n} U_{i} entscheidbar.

(ii)

Sei κ eine Kardinalzahl und M ein Modul. Die Theorie von M^{κ} ist genau dann entscheidbar, wenn die von M entscheidbar ist.

Für den Beweis verweisen wir auf die Originalarbeit [5, S.78-79].

Satz 2.16 Sei R ein rekursiv aufzählbarer Ring und T eine rekursiv axiomatisierbare Theorie von R-Moduln, die

M_{0} ⊕ M_{1} ⊧ T ⇔ M_{0} ⊧ T und M_{1} ⊧ T

erfüllt. Wenn (φ_{i}/ψ_{i})_{i∈ℕ} eine rekursive Aufzählung einer Basis des Raumes der unzerlegbaren Moduln I(R) = {U_{i}^{∼} : i ∈ ℕ} ist und wenn φ_{i}/ψ_{i}(U_{j}) rekursiv von i und j abhängt, dann ist T entscheidbar.

Beweis. Nach Korollar 2.13 sind zwei Modelle M_{1} und M_{2} von T elementar äquivalent, wenn φ_{i}/ψ_{i}(M_{1}) = φ_{i}/ψ_{i}(M_{2}) für alle i ∈ ℕ gilt. Damit ist die Theorie des rein injektiven unzerlegbaren Moduls U_{i}

(4.1) T_{i} = T ∪ {φ_{j}/ψ_{j=φ_{j}/ψ_{j}(U_{i})} : j ∈ ℕ}

vollständig und rekursiv axiomatisierbar, also entscheidbar. Nach Korollar 2.10 und Korollar 1.23 hat ein Satz ϕ ein Modell, wenn ein Modul, der direkte Summe rein injektiver unzerlegbarer Moduln ist, ein Modell von ϕ ist. Korollar 1.14 erlaubt es, anstelle der direkten Summe ein direktes Produkt zu betrachten. Bleibt zu zeigen, daß wir in der Situation ∏_{i∈I} U_{i} ⊧ ϕ für einen Satz ϕ nur endlich viele rein injektive unzerlegbare Faktoren brauchen, um Satz 2.15 anwenden zu können. Nach Lemma 1.8 existiert eine Konjunktion θ von Sätzen der Gestalt φ/ψ_{=k} und eine boolesche Kombination von p.p. Sätzen χ so, daß

(4.2) T_{left-R} ⊢ θ → (ϕ ↔ χ) und ∏_{i∈I} U_{i} ⊧ θ

gilt. Sei φ/ψ_{=k} aus θ. Wegen φ/ψ(∏_{i∈I} U_{i}) = ∏_{i∈I} φ/ψ(U_{i}) kann es nur endlich viele Moduln U_{i_{1}}, …, U_{i_{n}} mit φ/ψ(U_{i_{j}}) > 1 geben. Es folgt, daß wir endlich viele Moduln auswählen können, so daß deren Produkt Modell von θ ist. Sei M dieses Produkt. Jetzt gilt M ⊧ ϕ genau dann, wenn M ⊧ χ gilt. Aus M ⊭ χ folgt aber sofort ∏_{i∈I} U_{i} ⊭ χ, ein Widerspruch zu (4.2) . Ein ähnliches Argument zeigt, daß wir nur endliche und in höchstens endlich vielen Fällen abzählbare Potenzen der U_{i} betrachten müssen.

Wir erhalten also, daß T ⊢ ϕ genau dann gilt, wenn jeder rein injektive Modul M, der Modell von T ist, auch Modell von ϕ ist. Andererseits gilt M ≡ ∏_{j<n} U_{i_{j}}^{κ_{j}} mit n, i_{j} ∈ ℕ und κ_{j} höchstens abzählbare Kardinalzahl. Nach Voraussetzung sind die U_{i_{j}} Modelle von T. Ob für gegebenes i_{j} der Modul U_{i_{j}} ein Modell von ϕ ist, ist aber entscheidbar und damit nach Satz 2.15 auch, ob M ⊧ ϕ gilt. Insgesamt erhalten wir eine Aufzählung der rein injektiven unzerlegbaren Moduln, die Modell von T sind und damit bis auf elementare Äquivalenz eine Aufzählung (M_{i} : i ∈ I) aller Modelle von T, so daß ‘M_{i} ⊧ ϕ oder nicht’ entscheidbar ist. Deswegen ist sowohl die Theorie T als auch ihr Komplement rekursiv axiomatisierbar, und T ist entscheidbar. □

2.5 Matrizen und p.p. Typen

Eine p.p. Formel φ(x̄) kann in einer Matrixschreibweise

(5.1) ∃ȳ(x̄ȳ)H_{φ} = 0

beschrieben werden, wobei H_{φ} = \binom{R_{φ}}{S_{φ}} eine Rechteckmatrix ist, in der der Block R_{φ} für die Variablen x̄ und S_{φ} für die Variablen ȳ zuständig ist. Für unsere Absichten genügt es, nur Formeln in einer freien Variablen zu betrachten, das bedeutet, R_{φ} besteht nur aus einer Zeile r̄_{φ}. Wir schreiben φ_{H}(x) für die durch H = \binom{r}{S} beschriebene Formel.

Beispiel. Sei R = ℤ. Ist φ(x̄) die p.p. Formel ∃y(x−ny = 0), dann ist H_{φ} die Matrix \binom{1}{−n}.

Sei jetzt Φ ein p.p. Typ in der freien Variablen x. Mit I(Φ) bezeichnen wir die Menge aller Matrizen H für die H = H_{φ} für eine Formel φ ∈ Φ gilt.

Definition. Sei I eine Menge von Matrizen. Wir sagen, I ist abgeschlossen, wenn diese Menge die folgenden drei Bedingungen erfüllt:

(i)

Ist H ∈ I und G eine Matrix, so daß das Produkt HG gebildet werden kann, dann ist HG ∈ I.

(ii)

Ist für eine beliebige Matrix G,

( \begin{matrix}1 \\ & G \\ 0 \end{matrix} ) H ∈ I,

dann ist H ∈ I.

(iii)

Sind \binom{r̄}{S}, \binom{r̄′}{S′} in I, dann ist auch

( \begin{matrix}r̄ & r̄′ \\ S \\ & S′ \end{matrix} ) ∈ I.

Definition. Der Abschluß ⟨H⟩ einer Matrix H ist die kleinste abgeschlossene Menge von Matrizen, die H enthält.

Lemma 2.17 Seien G, H Matrizen; G ∈ ⟨H⟩ gilt genau dann, wenn Matrizen X und Y existieren, so daß

(5.2)  ( \begin{matrix}1 \\ & Y \\ 0 \end{matrix} ) G = HX

gilt.

Beweis. Die Rückrichtung folgt sofort aus den Definitionen. Für die entgegengesetzte Richtung reicht es aus, folgendes zu zeigen: Wenn H gegeben ist, dann ist die Menge I aller Matrizen G, für die es Matrizen X und Y gibt, die (5.2) erfüllen, abgeschlossen. Dafür gehen wir die Bedingungen (i) - (iii) durch:

(i) Erfüllt G die Aussage (5.2) , und ist B eine Matrix, so daß das Produkt GB existiert, dann ist GB ∈ I, denn

( \begin{matrix}1 \\ & Y \\ 0 \end{matrix} ) GB = HXB.

(ii) Sei

( \begin{matrix}1 \\ & Y_{1} \\ 0 \end{matrix} ) G ∈ I,

das heißt, es existieren Matrizen Y_{2}, X mit

( \begin{matrix}1 \\ & Y_{2} \\ 0 \end{matrix} ) ( \begin{matrix}1 \\ & Y_{1} \\ 0 \end{matrix} ) G = HX,

also

( \begin{matrix}1 \\ & Y_{2}Y_{1} \\ 0 \end{matrix} ) G = HX,

und damit ist G ∈ I.

(iii) Angenommen,

( \begin{matrix}1 \\ & Y_{1} \\ 0 \end{matrix} ) ( r̄ ; S ) = HX_{1} und ( \begin{matrix}1 \\ & Y_{2} \\ 0 \end{matrix} ) ( \begin{matrix} & r̄′ \\ S′ \end{matrix} ) = HX_{2},

dann haben wir

( \begin{matrix}1 \\ & Y_{1} \\ & & Y_{2} \\ 0 \end{matrix} ) ( \begin{matrix}r̄ & r̄′ \\ S \\ & S′ \end{matrix} ) = HX_{1}X_{2}.

□

Satz 2.18 Sei Φ(x) ein p.p. Typ. Dann ist I(Φ) eine abgeschlossene Menge.

Beweis. Wir gehen wieder die Bedingungen (i)-(iii) durch:

(i) Sei H ∈ I(Φ), dann ist die Formel ∃ȳ(xȳ)H = 0 in Φ, damit ist aber für beliebiges aber passendes G die Formel ∃ȳ(xȳ)HG = 0 in Φ, also HG ∈ I(Φ).

(ii) Aus

( \begin{matrix}1 \\ & G \\ 0 \end{matrix} ) ( r̄ ; S ) ∈ I(Φ)

folgt ∃ȳ(xr̄ + (ȳGS) = 0) ∈ Φ, daraus wiederum folgt \binom{r̄}{S} ∈ I(Φ).

(iii) Eine leichte Rechnung zeigt, daß φ mit

H_{φ} = ( \begin{matrix}r̄ & r̄′ \\ S \\ & S′ \\ 0 \end{matrix} )

äquivalent zu φ_{H} ∧ φ_{H′} ist. □

Wir führen einige Bezeichnungen ein: Sei H eine m×k-Matrix über R (Wir schreiben auch H für den durch sie definierten Homomorphismus H : R^{k} → R^{m}), M_{H} = R^{m}/H(R^{k}) der Kokern von H und π_{H} : R^{m} → M_{H} der dazu gehörige kanonische Morphismus. Außerdem sei i : R ↪ R^{m} die Einbettung in die erste Komponente, f_{H} = π_{H} ∘ i, a_{H} = f_{H}(1) und b̄_{H} = π_{H}((e_{2}, …, e_{m})), wobei e_{i} der Vektor mit einer 1 an Stelle i und Nullen an den anderen Stellen ist.

Lemma 2.19

(i) φ_{H} ist in tp_{M_{H}}^{+}(a_{H}) enthalten.

(ii)

Ist c ein Element des Moduls M, und gilt M ⊧ φ_{H}[c], dann existiert ein Morphismus von M_{H} nach M mit a_{H} ↦ c.

Beweis. (i) Die Formel φ_{H} ist in tp_{M_{H}}^{+}(a_{H}) enthalten, wenn

(5.3) (a_{H}, b̄_{H})H = ¯0

erfüllt ist. Nun ist aber (a_{H}, b̄_{H}) = (π(e_{1}), …, π(e_{m})), also wird (5.3) zu

(5.4) π_{H}1_{m} · H = (π_{H}(h_{1}), …, π_{H}(h_{n})) = ¯0; dabei ist n die Zeilenlänge von H.

(ii) Aus M ⊧ φ_{H}[c] folgt, daß ein Tupel d̄∈ M mit cd̄H = ¯0 existiert. Wir definieren f : R ⊕ R^{m−1} → M durch (e_{1}, (e_{2}, …, e_{m})) ↦ (c, d̄); damit ist (f(h_{1}), …, f(h_{n})) die Nullmatrix und deswegen ker π_{H} ⊆ ker f. Also faktorisiert f durch π_{H} mit einem Homomorphismus von M_{H} nach M, der (a_{H}, b̄_{H}) auf (c, d̄) abbildet. □

Satz 2.20 Für eine Matrix H sei Φ der p.p. Typ von a_{H} bezüglich M_{H}. Dann ist I(Φ) = ⟨H⟩.

Beweis. Der Fall ⟨H⟩ ⊆ I(Φ) folgt aus Lemma 2.19 (i).

Sei nun G eine m′ × k′ Matrix in I(Φ). Wir benutzen Lemma 2.17, um G ∈ ⟨H⟩ zu zeigen. Nach Lemma 2.19 existiert ein Homomorphismus g : M_{G} → M_{H} mit g(a_{G}) = a_{H}, so daß

R^{m} \overline{π_{H}_{}}M_{H}
[figure: R]
[figure: R^{m′}; π_{G}; M_{G}; g]

kommutiert. Außerdem existiert eine Abbildung g′ : R^{m′} → R^{m}, so daß auch das Rechteck kommutiert, also g ∘ π_{G} = π_{H} ∘ g′. Wir ändern notfalls g′ ab, indem wir den ersten Basisvektor e′_{1} von R^{m′} auf e_{1} abbilden und die restlichen genauso wie davor. Dadurch erhalten wir das folgende Diagramm:

R^{m} \overline{π_{H}_{}}M_{H}
[figure: R]
[figure: R^{m′}; g; ′; π_{G}; M_{G}; g]

Jetzt kommutieren sowohl Dreieck als auch Rechteck. Sei G′ = ( \begin{matrix}a & b̄ \\ c̄ & D \end{matrix} ) die Matrix

der Abbildung g′ (D ist eine (m − 1) × (m′ − 1) Matrix). Aus G′e′_{1} = e_{1} folgt a = 1 und c̄ = 0. Aus π_{G}(G) = 0 folgt g ∘ π_{G}(G) = π_{H} ∘ g′(G) = 0 und daraus g′(G) ⊆ ker π_{H} = im H. Das bedeutet aber, daß eine Matrix X mit G′G = HX existiert, was zu beweisen war. □

Wir schreiben M_{φ} und a_{φ} für M_{H} bzw. a_{H}, wenn H_{φ} = H ist.

Satz 2.21 Unter der Voraussetzung T_{left-R} ⊢ ψ → φ sind die folgenden Aussagen äquivalent:

(a) T_{left-R} ⊢ φ/ψ_{=1}.

(b) M_{φ} ⊧ ψ[a_{φ}].

(c) M ⊧ φ/ψ_{=1} für jeden endlich erzeugten R-Modul M.

(d) U ⊧ φ/ψ_{=1} für jeden unzerlegbaren R-Modul U.

Beweis. Die Implikation (a)⇒(d) ist trivial. Der Modul M aus (c) ist elementar äquivalent zu einem direkten Produkt unzerlegbarer rein injektiver Moduln ∏_{i∈I} U_{i}. Aus φ/φ ∧ ψ(U_{i}) = 1 für alle i ∈ I folgt φ/φ ∧ ψ(M) = 1. Das beweist (d)⇒(c). Die Implikation (c)⇒(b) folgt aus der Tatsache, daß M_{φ} endlich erzeugt ist; bleibt noch (b)⇒(a): Gilt für einen beliebigen Modul M die Aussage M ⊧ φ[b], dann existiert nach Lemma 2.19 ein Homomorphismus f : M_{φ} → M mit f(a_{φ}) = b. Weil p.p. Formeln von Homomorphismen erhalten werden, gilt M ⊧ φ → ψ und deswegen M ⊧ φ/(φ ∧ ψ)_{=1}. Weil M beliebig gewählt war, folgt daraus (a). □

Moduln über Polynomringen

In diesem Kapitel wollen wir mit Hilfe von Satz 2.16 zeigen, daß für bestimmte Polynomringe K[x] die Theorie der K[x]-Moduln entscheidbar ist. Um diesen Satz anwenden zu können, brauchen wir eine rekursive Aufzählung aller Isomorphietypen rein injektiver unzerlegbarer K[x]-Moduln, dafür müssen wir erst einmal alle rein injektiven unzerlegbaren Moduln über jenem Ring kennen; mit dieser Klassifikation werden wir uns in den nächsten beiden Abschnitten beschäftigen.

3.1 Moduln über kommutativen Ringen

Innerhalb dieses Abschnittes ist R immer ein kommutativer Ring.

Definitionen. S ⊆ R wird eine multiplikative Teilmenge von R genannt, wenn 1 in S enthalten ist, 0 nicht und wenn r und s in S enthalten sind, dann auch rs. Für einen R-Modul M erhalten wir die Lokalisierung M_{S} von M bei S durch die folgende Prozedur:

Wir bilden zuerst den S-Torsionsmodul τ_{S}M = {m ∈ M : sm = 0 für ein s ∈ S}.

Danach bilden wir ,,Brüche”, deren Zähler aus Elementen des nach dem S-Torsions-modul faktorisierten Modul und deren Nenner aus Elementen aus S bestehen. Formal hingeschrieben sieht das dann so aus: X sei die Menge (M/τ_{S}M) × S; Θ sei die durch

(1.1) (m, s)Θ(m′, s′) ⇔ (∃t ∈ S) t(s′m − sm′) = 0

definierte Äquivalenzrelation auf X. Jetzt setzen wir M_{S} = X/Θ und schreiben \frac{m}{s} für die Äquivalenzklasse von (m, s). Wir führen eine Addition

(1.2) plus^{M_{S}}(\frac{m}{s}, \frac{m′}{s′}) = \frac{s′m + sm′}{ss′}

auf M_{S} und zusätzlich eine Multiplikation

(1.3) times^{R_{S}}(\frac{r}{s}, \frac{r′}{s′}) = \frac{rr′}{ss′}

auf R_{S} ein.

Es läßt sich leicht nachrechnen, daß die in (1.2) und (1.3) definierten Operationen wohldefiniert sind und daß deswegen R_{S} ein Ring und M_{S} ein R_{S}-Modul ist. Ist P ein Primideal, dann ist R\P eine multiplikative Teilmenge von R; wir schreiben M_{(P)} anstatt M_{R\P} und sprechen von der Lokalisierung von M bei P. Mit π_{S} : M → M_{S} bezeichnen wir den natürlichen Homomorphismus, der m ∈ M auf (m + τ_{S}(M))/1 abbildet, mit p_{S} : M^{n} → M_{S}^{n} die durch x̄ ↦ (π_{S}(x_{0}), …, π_{S}(x_{n−1})) definierte Abbildung.

Lemma 3.1 Sei S eine multiplikative Teilmenge von R und φ(x_{0}, …, x_{n−1}) eine p.p. Formel. Dann gilt

φ(M_{S}) = R_{S} · p_{S}(φ(M)).

Beweis durch Induktion über den Formelaufbau. Sei zuerst φ(x̄) eine einzelne Gleichung, zum Beispiel

(1.4)  ∑_{i=0}^{n−1} r^{i}x^{i} = 0.

Ist ā ∈ M eine Lösung dieser Gleichung, dann gilt auch

(1.5)  ∑_{i=0}^{n−1} r^{i}(π^{S}(a^{i})) = 0;

wir haben also p_{S}(φ(M)) ⊆ φ(M_{S}) und damit auch R_{S} · p_{S}(φ(M)) ⊆ φ(M_{S}). Sei andererseits (a_{0}^{∼}/s_{0}, …, a_{n−1}^{∼}/s_{n−1}) ∈ φ(M_{S}) (a_{i} sei Repräsentant der Äquivalenzklasse a_{i}^{∼}); wir setzen

(1.6)  s = ∏_{i=0}^{n−1} s^{i}  und  c^{i} = a^{i} ∏_{i≠j} s^{j}.

Aus

(1.7)  ∑_{i=0}^{n−1} r^{i} \frac{a_{i}}{s_{i}} = 0

folgt dann

(1.8) \frac{∑_{i=0}^{n−1} r_{i}c_{i}}{s} = 0

und daraus

(1.9)  ∑_{i=0}^{n−1} r^{i}c^{i} ∈ τ^{S}M.

Damit existiert ein t ∈ S mit t(∑_{i=0}^{n−1} r_{i}c_{i}) = 0 und

(1.10) (a_{0}^{∼}/s_{0}, …, a_{n−1}^{∼}/s_{n−1}) = st(c_{0}^{∼}t/1, …, c_{n−1}^{∼}t/1) ∈ (φ(M))_{S}.

Die Behauptung ist also wahr für Gleichungen, damit auch für Konjunktionen von Gleichungen. Jetzt der Schritt mit dem Existenzquantor: Aus M ⊧ ∃xφ(x, ā) folgt M ⊧ φ[b, ā] für ein b ∈ M, daraus M_{S} ⊧ φ[π_{S}(b), p_{S}(ā)] bzw. M_{S} ⊧ ∃xφ(x, p_{S}(ā)). Gilt andererseits M_{S} ⊧ ∃xφ(x, c̄), dann auch M_{S} ⊧ φ[d, c̄] für ein d ∈ M_{S}. Nach Induktionsannahme existiert ein q ∈ R_{S} mit (d, c̄) = q · p_{S}(b, ē) und M ⊧ φ[b, ē]. □

Lemma 3.2 Sei S eine multiplikative Teilmenge von R.

(i)

Die Inklusion i : A ↪ M ist genau dann p.p. wesentlich, wenn auch i_{S} : π_{S}(A) ↪ M_{S} p.p. wesentlich ist.

(ii)

M ist genau dann ein reiner Untermodul von M′ (als R-Modul), wenn M_{S} ein reiner Untermodul von M′_{S} ist (als R_{S}-Modul).

(iii)

M ist genau dann ein rein injektiver unzerlegbarer R-Modul, wenn M_{S} ein rein injektiver unzerlegbarer R_{S}-Modul ist.

Beweis. (i) Wie schon erwähnt wurde, ist π_{S} natürlich, das bedeutet, wenn f : M → M′ ein Homomorphismus ist, dann auch π_{S}f : M_{S} → M′_{S} definiert durch

(1.11) (m + τ_{S}(M))/s ↦ (fm + τ_{S})(M′)/s,

und das Diagramm

[figure: M; f; M′; M_{S}; π_{S}; π_{S}f; M_{S}′; π_{S}]

kommutiert. Wenn f|_{A} ein partieller Homomorphismus von M nach M′ ist, dann ist π_{S}f|_{π_{S}(A)} ein partieller Homomorphismus von M_{S} nach M′_{S} und

(1.12) M ⊧ φ[ā] ⇔ M′ ⊧ φ[fā] für alle ā ∈ M ist genau dann erfüllt, wenn M_{S} ⊧ φ[p_{S}(ā)] ⇔ M′_{S} ⊧ φ[p_{S}(fā)] erfüllt ist. Nach Lemma 3.1 haben alle b̄ ∈ M_{S} mit M_{S} ⊧ φ[b̄] die Gestalt q · p_{S}(ā) mit q ∈ R_{S}, daraus folgt die Rückrichtung des Beweises.

(ii) Sei M_{S} rein in M′_{S}. Aus M′ ⊧ φ[b̄] mit b̄ ∈ M folgt M′_{S} ⊧ φ[p_{S}(b̄)]. Wegen p_{S}(b̄) ∈ M_{S} gilt M_{S} ⊧ φ[p_{S}(b̄)] und damit M ⊧ φ[b̄]. Ähnlich geht die andere Richtung des Beweises.

(iii) Sei M rein injektiv und das Diagramm M_{2S} ^{}^{ϕ} M_{1S} ^{ψ}^{}M_{S} gegeben, wobei ϕ eine reine Einbettung ist. Dann ist nach (ii) i : M_{1} → M_{2} auch rein, und es existiert ein Homomorphismus φ : M_{2} → M; weil π_{S} natürlich ist, kommutiert

[figure: M_{2}; φ; M; M_{2S}; π_{S}; π_{S}φ; M_{S}; π_{S}]

und damit ist ψ = π_{s}φ ∘ ϕ; M_{S} ist also auch rein injektiv. Die andere Beweisrichtung geht nach demselben Prinzip. Angenommen, M sei nicht unzerlegbar. Dann existiert ein a ∈ M mit M = H(a)⊕M′ und M′ ≠ 0. Sei b̄ ∈ M′, φ eine p.p. Formel, pr : M → M′ die Projektion auf M′ und i : M′ ↪ M die Inklusion. Aus M ⊧ φ[a, b̄] folgt M ⊧ φ[i ∘ pr a, i ∘ pr b̄] und daraus M ⊧ φ[0, b̄]. Also gilt

(1.13) M ⊧ ∃x((φ(x, b̄) → φ(0, b̄)) ∧ ¬(x = 0))

für alle p.p. Formeln φ und bestimmte Tupel b̄ aus M. Dann gilt auch

(1.14) M_{S} ⊧ ∃x((φ(x, p_{S}(b̄)) → φ(0, p_{S}(b̄))) ∧ ¬(x = 0)).

Daraus folgt, daß M_{S} eine nichttriviale Zerlegung besitzt. Die andere Beweisrichtung ist wieder analog. □

Satz 3.3 Zu jedem unzerlegbaren R-Modul M existiert ein maximales Ideal P von R, so daß π_{P} : M → M_{(P)} ein Isomorphismus ist, dabei wird M_{(P)} auch als R-Modul aufgefaßt.

Beweis. Weil R kommutativ ist, ist die Multiplikation mit einem Element aus R ein Endomorphismus von M. Nach Satz 1.26 ist der Endomorphismenring A von M lokal. Sei I die Teilmenge von A, die alle nichtinvertierbaren Elemente von A, das sind alle Endomorphismen, die keine Automorphismen sind, enthält. Ist x ∈ I, dann ist 1 ∉ xA und damit xA ≠ A, daraus folgt auch wieder x ∈ I. Nun gilt für jedes echte Ideal J und für jedes y ∈ J, yA ≠ A, ergo y ∈ I. Die Menge I ist also nichts anderes als die Vereinigung aller Ideale von A. Weil A lokal ist, hat A genau ein maximales Ideal, das muß dann zwangsläufig schon I sein. Eine Folgerung ist, daß wenn f und g keine Automorphismen sind, dann ist f + g auch keiner. Damit ist

L = {r ∈ R : x ↦ rx ist kein Automorphismus }

ein Ideal von R. Wir erweitern L zu einem maximalen Ideal P. Für jedes Element r′ ∈ R\P ist die Abbildung x ↦ r′x ein Automorphismus von M, damit hat M schon auf natürliche Weise eine R_{(P)}-Struktur, woraus die Behauptung folgt. □

Als nächstes wollen wir die Struktur eines Polynomringes K[x] über einem gegebenen Körper K untersuchen; genauer gesagt betrachten wir die Lokalisierung von K[x] bei einem Primideal P. Der Idealverband des so erhaltenen Ringes hat eine so einfache Struktur, daß eine Klassifikation der unzerlegbaren K[x]_{(P)}-Moduln möglich ist, was im nächsten Abschnitt passieren wird. Mit der Hilfe von Lemma 3.2 und Satz 3.3 können wir dann das Ergebnis auf K[x]-Moduln übertragen. Sei also K ein Körper und P ein Primideal des Polynomrings K[x]. Polynomringe sind Hauptidealringe, das heißt, jedes Ideal wird von einem Polynom erzeugt, sei zum Beispiel P = ⟨p(x)⟩. Die Lokalisierung von K[x] bei P besteht dann genau aus den rationalen Funktionen \frac{f}{g} mit der Zusatzbedingung, daß p kein Teiler von g ist. Sei I_{P} die Menge \{\frac{f}{g} ∈ K[x]_{(P)} : f ∈ P }.

Satz 3.4 Der Idealverband von K[x]_{(P)} ist die Kette

K[x]_{(P)} ⊇ I_{P} ⊇ I_{P}^{2} ⊇ I_{P}^{3} ⊇ … ⊇ I_{P}^{n} ⊇ … ⊇ {0}.

Beweis. I_{P} ist ein Ideal von K[x]_{(P)}, denn sind \frac{f}{g} , \frac{f′}{g′} ∈ I_{P}, dann ist fg′ + f′g ∈ P und damit \frac{f}{g} + \frac{f′}{g′} ∈ I_{P}. Aus h ∈ K[x] und f ∈ P folgt fh ∈ P, also \frac{f}{g} · \frac{h′}{g′} ∈ I_{P}, außerdem ist \frac{0}{g} ∈ I_{P}, dabei sind g und g′ beliebig aus K[x]\P. Wir erhalten also ein Ideal von K[x]_{(P)}, wenn die Polynome, die im Zähler stehen, ein Ideal von K[x] bilden; aus der Maximalität von P folgt, daß auch I_{P} maximal ist.

Seien Q bzw. Q_{(P)} die Quotientenkörper von K[x] bzw. K[x]_{(P)}. Die Abbildung i : Q_{(P)} → Q gegeben durch \frac{f}{g} ↦ f ∘ g^{−1} ist ein Isomorphismus. Ist y ∈ Q_{(P)}\K[x]_{(P)}, dann hat i(y) die Gestalt \frac{f}{g}, und p teilt g. Wir können annehmen, daß ggT(f, g) = 1 ist, also ist (i(y))^{−1} = \frac{g}{f} ∈ K[x]_{(P)} und i^{−1}((i(y))^{−1}) = y^{−1} ∈ K[x]_{(P)}. Jetzt seien J_{P} und J′_{P} zwei Ideale von K[x]_{(P)}. Sei y ∈ J_{P} und y ∉ J′_{P}, dann gilt für alle z ≠ 0 aus J′_{P}, z^{−1}y ∉ K[x]_{(P)}, wäre das nicht so, dann wäre zz^{−1}y = y ∈ J′_{P}, ein Widerspruch. Damit ist aber y^{−1}z ∈ K[x]_{(P)} und z = y(y^{−1}z) ∈ J_{P}, also ist J′_{P} ⊆ J_{P}.

Wir wissen nun, daß die Ideale von K[x]_{(P)} linear durch Inklusion geordnet sind und daß I_{P} das einzige maximale Ideal ist. Sei J ⊆ P ein weiteres Ideal von K[x]; J wird von einem Vielfachen von p erzeugt, zum Beispiel von r = qp, dabei besitzt q eine Zerlegung q = p^{n}s mit n ≥ 0 und p teilt nicht s. Wir folgern daraus

(1.15) \begin{matrix}J_{P} & = & \{\frac{f}{g} ∈ K[x]_{(P)} : f ∈ J\} \\ & = & \{\frac{tp^{n}sp}{sh} : h ∉ P und t ∈ K[x]\} \\ & = & \{\frac{rp^{n+1}}{h} : h ∉ P und r ∈ K[x]\} \\ & = & I_{p}^{n+1}. \end{matrix}

Jedes in I_{P} enthaltene Ideal ist also eine Potenz von I_{P}, und der Beweis ist abgeschlossen. □

Integritätsbereiche, deren Ideale diese Bedingung erfüllen, werden Bewertungsringe mit dem diskreten Rang 1 genannt. Woher dieser Name kommt, interessiert uns hier nicht. Im nächsten Abschnitt werden wir alle unzerlegbaren Moduln über einem solchen Ring angeben. Aus der Gestalt des Idealverbandes eines solchen Rings folgt, daß er ein Hauptidealring ist.

3.2 Unzerlegbare K[x]-Moduln

Lemma 3.5 Zu jeder Matrix H mit Einträgen aus einem Hauptidealring R existieren invertierbare Matrizen X und Y über R, so daß XHY eine Diagonalmatrix ist.

Ein Beweis dieses Lemmas findet man in [2, S. 527].

Satz 3.6 Sei R ein Hauptidealring.

(i)

Jede p.p. Formel φ(x̄) ist äquivalent modulo M zu einer Konjunktion von Formeln der Form

∃ȳ(p^{k}ȳ = t(x̄)) bzw. t(x̄) = 0,

wobei p ∈ R prim und t(x̄) ein Term ist. Die erste Formel drückt eine Teilbarkeitsbedingung aus, wir kürzen sie durch p^{k}|t(x̄) ab, und, um eine einheitliche Schreibweise zu erhalten, schreiben wir 0|t(x̄) für die zweite Formel. Die Struktur dieser Formeln kann noch deutlicher gemacht werden: Jede Formel der Form p^{k}|t(x̄) wird durch eine Formel p^{k}|p^{l}t′(x̄) beschrieben, wobei, es sei t′(x̄) = ∑_{i=1}^{n} r_{i}x_{i}, der größte gemeinsame Teiler von {r_{1}, …, r_{n}} gleich 1 und l < k ist.

(ii)

Hat φ(x) nur eine freie Variable, dann haben die Formeln aus (ii) die einfache Gestalt

p^{k}|p^{l}x bzw. rx = 0.

Beweis. (i) Die in φ(x̄) enthaltenen Gleichungen seien γ_{1}(x̄, ȳ), …, γ_{k}(x̄, ȳ), eine Gleichung γ_{i} habe die Gestalt

(2.1)  ∑_{j=1}^{n} r^{ij}x^{i} + ∑_{l=1}^{m} s^{il}y^{l} = 0.

Wir setzen T = (r_{ij})_{i=1,...,k;j=1,...,n} und S = (s_{il})_{i=1,...,k;l=1,...,m}. Nach Lemma 3.5 existieren Matrizen X, Y, so daß XSY eine Diagonalmatrix diag(s′_{1}, …, s′_{m′}) ist, und sei U = XT = (r′_{ij})_{i=1,...,m′;j=1,...,n}. Sei nun t_{i}(x̄) der Term ∑_{j=1}^{n} r′_{ij}x_{j}, außerdem γ′_{i}(x̄, z̄) die Gleichung t_{i}(x̄) + s′_{i}z_{i} = 0 und φ′(x̄) die Formel ∃z̄(γ′_{1}(x̄, z̄) ∧ … ∧ γ′_{m′}(x̄, z̄)).

X und Y sind invertierbar, das bedeutet aber, die Gleichungen γ_{i} sind lösbar, wenn es die Gleichungen γ′_{i} sind und umgekehrt; φ(x̄) und φ′(x̄) sind also äquivalent. Die Formel ∃z_{i}γ′_{i} ist genau die Aussage s′_{i}|t_{i}(x̄). Wegen der eindeutigen Primfaktorzerlegung in Hauptidealringen gilt

(2.2) rs|t(x̄) ⇔ r|t(x̄) und s|t(x̄), wenn ggT(r, s) = 1 ist. Deshalb können wir jede Formel r|t(x̄) mit r ≠ 0 durch eine Konjunktion von Formeln der Form p^{k}|t_{i}(x̄) ersetzen, wobei p prim ist. Sei schließlich r_{i} = ggT(r′_{i1}, …, r′_{in}) und t_{ij} = r′_{ij}/r_{i}. Angenommen, p^{l} teilt r_{i}, aber p^{l+1} teilt r_{i} nicht mehr, dann ist p^{k}|t_{i}(x̄) äquivalent zu p^{k}|p^{l} ∑_{j=1}^{n} t_{ij}x_{j}. Ist l ≥ k, dann ist die Formel trivialerweise erfüllt und kann weggelassen werden. Insgesamt haben wir gezeigt, daß φ′(x̄) alle gewünschten Eigenschaften erfüllt. (ii) folgt sofort aus (i). □

Korollar 3.7 Sei R wieder ein Hauptidealring und M_{0} ein Untermodul von M. M_{0} ist dann und nur dann rein in M, wenn für alle r ∈ R, rM ∩ M_{0} = rM_{0} erfüllt ist.

Beweis. Die Inklusion rM_{0} ⊆ rM ∩ M_{0} ist immer erfüllt; wenn m = rn ∈ rM ∩ M_{0} gilt, dann haben wir M ⊧ ∃x(m = rx) und, weil M_{0} rein in M ist, M_{0} ⊧ ∃x(m = rx), daraus folgt m ∈ rM_{0}. Für die andere Beweisrichtung wählen wir eine p.p. Formel φ(x̄) und ein Tupel ā aus M_{0}, so daß M ⊧ φ[ā] gilt. Nach Satz 3.6 ist φ(x̄) äquivalent zu einer Konjunktion von Formeln der Form r|t(x̄); sei nun r|t(x̄) eine in dieser Konjunktion vorkommende Formel. Aus M ⊧ φ[ā] folgt M ⊧ r|t[ā], nach Voraussetzung ist deswegen t[ā] ∈ rM_{0}. Dies gilt für alle in der Konjunktion enthaltenen Formeln, also gilt M_{0} ⊧ φ[ā], und M_{0} ist rein in M. □

Satz 3.8 Sei R ein Bewertungsring mit dem diskreten Rang 1; sein maximales Ideal werde mit P = pR, sein Quotientenkörper, aufgefaßt als R-Modul, werde mit Q bezeichnet. Die rein injektiven unzerlegbaren R-Moduln sind

(i) R/P^{n}  n ≥ 1
(ii) Q/R
(iii) Q
(iv) \overline{R}  die rein injektive Hülle von R.

Beweis. Zuerst zeigen wir, daß die aufgelisteten Moduln rein injektiv und unzerlegbar sind.

(i) Die Ideale von R/P^{n} entsprechen den Idealen von R, die P^{n} enthalten. Das sind die Ideale, die von einem Teiler von p^{n} erzeugt werden. Davon gibt es aber nur endlich viele. Damit erfüllt R/P^{n} die absteigende Kettenbedingung für Ideale. Die Untermoduln von R/P^{n} sind gerade die Ideale von R/P^{n}, also erfüllt R/P^{n} auch die absteigende Kettenbedingung für Untermoduln, erst recht die für p.p. definierbare Untergruppen. Nach Lemma 1.17 ist R/P^{n} damit rein injektiv. Der einzige minimale nichttriviale Untermodul von R/P^{n} ist P^{n−1}/P^{n}, deswegen ist R/P^{n} subdirekt irreduzibel und damit direkt unzerlegbar.

(ii) & (iii) Für jedes n ≠ 0 in R und jedes Element q aus Q existiert ein Element q′ aus Q, so daß nq′ = q erfüllt ist. Denn hat q die Gestalt \frac{r}{s}, können wir einfach q′ = \frac{r}{ns} wählen. Eine analoge Aussage gilt für Q/R. Moduln mit dieser Eigenschaft heißen teilbar. In der Kategorie der Moduln über einem Hauptidealring ist jeder Modul, der teilbar ist, injektiv. Weil reine Einbettungen spezielle Einbettungen sind, ist jeder injektive Modul rein injektiv, unter anderem sind dies Q und Q/R. Sei M ein nichttrivialer Untermodul von Q und q ∈ M mit q ≠ 0. Ist q ∉ R, dann gilt q = \frac{r}{s}, sR = P^{n} und rP = P^{n+k} mit k > 0 oder r = 1. Aus P^{n+k} ⊆ P^{n} folgt q^{−1}R ⊆ R, daraus q^{−1} ∈ R und daraus R ⊆ qR. Ist q ∈ R, dann ist qR = R oder qR = P^{n} für ein n ∈ ℕ. Weil R ∩ P^{k} = P^{k} und P^{n} ∩ P^{m} = P^{n} für n ≥ m gilt, haben zwei nichttriviale Untermoduln von Q immer einen nichttrivialen Schnitt, Q muß also unzerlegbar sein. Der Beweis für Q/R verläuft wieder analog.

(iv) \overline{R} ist nach Definition rein injektiv. Sei f ein Endomorphismus von \overline{R}. Angenommen, (1 − f)|_{R} ist nicht injektiv. Dann existiert ein r ≠ 0 in R mit r − f(r) = 0 bzw. f(r) = r. Ist r ein invertierbares Element, dann folgt mit f(r) = r·f(1), daß f(1) = 1 und f|_{R} = 1_{R} ist. Ist r nicht invertierbar, dann liegt r in einem Ideal P^{n} (n ∈ ℕ), und wir können o.B.d.A. r = p^{n} setzen. Das bedeutet f(p^{n}) = p^{n} bzw. f(s) = s für alle s ∈ P^{n}. Wäre f nicht injektiv, dann liegt das von einem Element aus R \ P^{n} erzeugte Ideal im Kern von f; dieses Ideal wiederum würde P^{n} enthalten, ein Widerspruch. Damit muß f|_{R} injektiv sein. Wir erhalten, daß entweder f|_{R} oder (1 − f)|_{R} ein partieller Isomorphismus von \overline{R} nach \overline{R} ist. Weil i : R → \overline{R} p.p. wesentlich ist, ist dann auch f oder 1 − f ein Automorphismus. Damit ist der Endomorphismenring von \overline{R} lokal. Nach Satz 1.26 ist \overline{R} unzerlegbar.

Zweitens zeigen wir, daß unsere Liste vollständig ist.

R ist ein Hauptidealring, also wird P von einem einzigen Element erzeugt, dem wir den Namen p gegeben haben. Sei M ein rein injektiver unzerlegbarer R-Modul und a ein Element von M mit a ≠ 0. Betrachte den Annulator ann_{R}(a) = {r ∈ R : ra = 0} und die Höhe h(a) = max{n ∈ ℕ ∪ {∞} : a ∈ P^{n} · M}; ann_{R}(a) ist ein Ideal von R, hat also die Gestalt ann_{R}(a) = P^{n+1} oder ann_{R}(a) = {0}. Nun gilt im ersten Fall ann_{R}(p^{n}a) = P, wir können also a so ersetzen, daß ann_{R}(a) = P oder ann_{R}(a) = {0} erfüllt ist. Wir betrachten die vier verschiedenen Möglichkeiten:

(a) Wenn ann_{R}(a)=P und h(a) = n ∈ ℕ gilt, wähle ein b ∈ M mit p^{n}b = a; die Abbildung φ : R → Rb gegeben durch r ↦ rb ist ein R-Modulhomomorphismus, aus ann_{R}(a) = P folgt P a = 0 und ker φ = P^{n+1}. Aus dem Homomorphiesatz erhalten wir, daß R/P^{n+1} und Rb zueinander isomorph sind. Wir wählen jetzt ein beliebiges r ∈ R. Angenommen, x ∈ rM ∩ Rb, dann ist x = rm für ein m ∈ M und x = sb für ein s ∈ R. Außerdem existiert ein t ∈ R mit s = p^{l}t für ein l ∈ ℕ, und p teilt nicht t. Wir betrachten zuerst den Spezialfall r = p^{k} für ein k ∈ ℕ und behaupten:

(2.3) Gilt p^{l}tb = p^{k}m und p teilt nicht t, dann ist k ≤ l.

Weil t und p^{n+1} teilerfremd sind, existieren x, y ∈ R mit (2.4) 1 = tx + p^{n+1}y und p teilt nicht x.

Zusammen mit p^{n+1}b = 0 erhalten wir p^{l}b = p^{l}stxb = p^{k}xm. Daraus wiederum folgt a = p^{l+(n−l)}b = p^{k+(n−l)}xm und daraus k + n − l ≤ n bzw. k ≤ l. Damit ist (2.3) bewiesen. Sei nun im allgemeinen r = p^{k} · r′ eine Zerlegung von r, so daß r′ nicht von p geteilt wird. Aus (2.3) folgt k ≤ l. Wieder existieren x, y ∈ R mit

(2.5) 1 = r′x + p^{n+1}y mit x, y ∈ R.

Es folgt b = r′xb und

(2.6) p^{l}tb = r′xp^{l}tb = r′p^{k}xtp^{l−k}b ∈ rRb.

Insgesamt erhalten wir rM ∩ Rb = rRb, nach Korollar 3.7 ist Rb rein in M; Rb ist aber selbst rein injektiv, darum ein direkter Summand von M, also muß Rb schon ganz M sein, wir haben M = Rb ≅ R/P^{n+1}.

(b) Sei ann_{R}(a) = P und h(a) = ∞. Wir betrachten die Menge

(2.7) Φ((x_{i})_{i∈ℕ}) = {x_{0} = a} ∪ {px_{i+1} = x_{i} : i ∈ ℕ};

Φ wird in M endlich realisiert; weil M rein injektiv ist, dann auch realisiert, sei (a_{i})_{i∈ℕ} eine solche Realisierung. Q/R und der von (a_{i})_{i∈ℕ} erzeugte Modul sind zueinander isomorph, der Isomorphismus ist durch a_{i} ↦ \frac{1}{p^{i+1}} + R festgelegt. Damit existiert eine Einbettung f : Q/R → M; weil Q/R injektiv ist, ist dieser Modul ein direkter Summand von M und deshalb M ≅ Q/R.

(c) Jetzt sei ann_{R}(a) = {0} und h(a) = ∞. Damit ist a auf eindeutige Weise teilbar durch alle r ∈ R \ {0}, das heißt, M ⊧ ∃x(rx = a); daraus folgt, daß Qa ein wohldefinierter Untermodul von M und isomorph zu Q ist; wiederum aus der Injektivität von Q folgt M ≅ Qa ≅ Q.

(d) Bleibt noch der Fall ann_{R}(a) = {0} und h(a) = n ∈ ℕ. Wähle ein b ∈ M mit p^{n}b = a. Rb ≅ R ist dann rein in M, also ist M = H(Rb) = \overline{Rb} = \overline{R}. □

Korollar 3.9 Die unzerlegbaren rein injektiven Moduln über einem Polynomring K[x] sind bis auf Isomorphie

(i) K[x]/P^{n}  P ist ein Primideal und n ≥ 1
(ii) K(x)/K[x]_{(P)}
(iii) K(x)
(iv) \overline{K[x]_{(P)}}.

Beweis. Nach Satz 3.4 ist K[x]_{(P)} ein Bewertungsring mit dem diskreten Rang 1, wobei P ein beliebiges Primideal von K[x] ist. Die Lokalisierungen bei P sind

(a) K[x]_{(P)}/P^{n} · K[x]_{(P)}

(b) K(x)_{(P)}/K[x]_{(P)}

(c) K(x)_{(P)}

(d) \overline{K(x)_{(P)}}.

All diese Moduln kommen in der Liste des Satzes 3.8 vor, sie sind also rein injektiv und unzerlegbar. Aus Lemma 3.2 (iii) folgt, daß die aufgeführten K[x]-Moduln rein injektiv und unzerlegbar sind. Angenommen, es existiert ein weiterer K[x]-Modul M, der zwar rein injektiv und unzerlegbar ist, aber zu keinem der angegebenen isomorph. Nach Satz 3.3 existiert ein Primideal P, so daß M und M_{(P)} zueinander isomorph sind. M_{(P)} wiederum ist zu keinem der unter (a)-(d) aufgelisteten Moduln isomorph und taucht nicht in der Liste des Satzes 3.8 auf; M_{(P)} kann also nicht rein injektiv und unzerlegbar sein, ein Widerspruch zu der Behauptung, M habe diese Eigenschaften. Unsere Liste ist also auch vollständig. □

3.3 Entscheidbarkeit

Mit K bezeichnen wir nun einen rekursiv aufzählbaren unendlichen algebraisch abgeschlossenen Körper. Wir beweisen in diesem Abschnitt, daß die Theorie der K[x]- Moduln entscheidbar ist. Dafür gehen wir Schritt für Schritt die Voraussetzungen des Satzes 2.16 durch. Aus der Aufzählbarkeit von K folgt, daß auch der Ring K[x] sowie die Sprache L der K[x]-Moduln rekursiv aufzählbar sind. Außerdem ist die Theorie T der K[x]-Moduln rekursiv axiomatisierbar. Weil p.p. Formeln an ihrem syntaktischen Aufbau erkennbar sind, gibt es auch einen Algorithmus, der gerade die p.p. Formeln in L, die eine freie Variable x haben, aufzählt. Selbstverständlich ist M_{0} ⊕ M_{1} ein K[x]-Modul, wenn M_{0} und M_{1} welche sind.

Als nächstes sind wir an einer Aufzählung aller rein injektiven unzerlegbaren K[x]- Moduln interessiert. Betrachten wir die Liste des Korollars 3.9: Wir wählen ein festes Primideal P von K[x]. Die Funktion F_{P} : ℕ \ {0} → K[x] − Mod definiert durch

(3.1)  \begin{matrix}1 & ↦ K(x)/K[x]_{(P)} \\ 2 & ↦ \overline{K[x]_{(P)}} \\ n & ↦ K[x]/P^{n−2}  für n ≥ 3 \end{matrix}

ist offensichtlich rekursiv. Um eine effektive Aufzählung aller rein injektiven unzerlegbaren Moduln zu erhalten, müssen wir fordern, daß die Primideale des Rings K[x] rekursiv aufzählbar sind. Primideale in K[x] sind Ideale, die von einem irreduziblen Polynom erzeugt werden; weil K algebraisch abgeschlossen ist, sind die irreduziblen Polynome gerade die von Grad 1; diese können wir wieder aufzählen und damit auch die Primideale von K[x]. Sei f eine Funktion, die diese Aufzählung leistet. Die Funktion F : ℕ → K[x] − Mod definiert durch

(3.2)  \begin{matrix}0 & ↦ & K(x) \\ n & ↦ & F_{f(pr_{1}(τ(n)))}(pr_{2}(τ(n)))  für n ≥ 1 \end{matrix}

zählt die gewünschten Moduln auf, dabei ist τ eine rekursive Funktion, die ℕ \ {0} bijektiv auf ℕ × ℕ abbildet, und pr_{1}, pr_{2} sind die Projektionen auf die erste bzw. zweite Komponente. Wir schreiben (U_{i} : i ∈ ℕ) für diese Aufzählung.

Welche Paare (φ, ψ) von p.p. Formeln kommen nun für eine Basis in Frage? Wenn für eine Theorie T die Aussage T ⊢ ψ → φ gilt, dann ist auch T ⊢ φ ∧ ψ ↔ ψ erfüllt. Gehen wir also von einer rekursiven Aufzählung i ↦ φ_{i} der p.p. Formeln aus, erhalten wir durch

(3.3) i ↦ (φ_{pr_{1}(τ(i))}, φ_{pr_{1}(τ(i))} ∧ φ_{pr_{2}(τ(i))})

eine Aufzählung von Paaren (φ, ψ), für die entweder φ/ψ(M) = 1 oder φ/ψ(M) > 1 gilt, wobei M ein beliebiger Modul ist. Wir erhalten eine Basis, wenn wir die Paare auswählen können, für die φ/ψ(U_{i}) > 1 für ein i ∈ ℕ gilt. Wir brauchen also ein Entscheidungsverfahren, das uns mitteilt, ob letzteres zutrifft. Danach müssen wir beweisen, daß für einen gegebenen Modul U_{i} und eine Invarianzaussage φ/ψ der Wert φ/ψ(M) effektiv berechnet werden kann.

Korollar 3.10 Wir können Invarianzaussagen φ/ψ, so daß die Mengen (φ/ψ) eine Basis von I(K[x]) bilden, rekursiv aufzählen.

Beweis. Wir wissen schon, daß wir die Paare, für die φ/ψ(M) = 1 oder φ/ψ(M) > 1 für jeden Modul M gilt, aufzählen können. Was bleibt, ist zu entscheiden, ob für eine gegebene Invarianzaussage φ/ψ ein i ∈ ℕ mit φ/ψ(U_{i}) > 1 existiert. Das ist nach Satz 2.21 genau dann nicht der Fall, wenn M_{φ} ⊧ ψ[a_{φ}] erfüllt ist. Aus Satz 2.20 folgt, daß dies äquivalent zu H_{ψ} ∈ ⟨H_{φ}⟩ ist. Nach Lemma 2.17 ist dies der Fall, wenn Matrizen X und Y existieren, so daß

(3.4)  ( \begin{matrix}1 \\ & Y \\ 0 \end{matrix} ) H^{ψ} ∈ ⟨H^{φ}⟩

gilt. Sei nun n die Spaltenlänge von H_{ψ} und m die Zeilenlänge von H_{φ}. Wir fassen Y als eine (n − 1) × (n − 1) Matrix, X als eine m × m Matrix und deren Einträge als Variablen auf; damit geht (3.4) in ein lineares Gleichungssystem über. Mit den Anforderungen, die wir an den Körper K gestellt haben, ist dieses Gleichungssystem auf rekursive Weise lösbar. □

Die letzte offene Frage ist, ob φ_{i}/ψ_{i}(U_{j}) effektiv berechenbar ist. Es stellt sich heraus, daß in unserer Situation diese Frage eine triviale Antwort besitzt.

Satz 3.11 Sei M ein K[x]-Modul. Dann gilt für alle n ≥ 1 und alle Invarianzaussagen in einer freien Variablen

M ⊧ φ/ψ_{≥2} ⇒ M^{n} ⊧ φ/ψ_{≥2}.

Damit impliziert φ/ψ(M) > 1 die Aussage φ/ψ(M) = ∞.

Beweis. Nach Satz 3.6 vereinfacht sich der Satz φ/ψ_{≥2} für p.p. Formeln φ, ψ in einer freien Variablen zu

(3.5) ∀x_{1}∀x_{2}∃x(p|x ∧ ¬(q|x − x_{1}) ∧ ¬(q|x − x_{2})).

Dabei ist p|x eine Abkürzung für ∃y(p · y = x) bzw. f · x = 0 für ein f ∈ K[x], wenn p = 0 ist. Seien ā, b̄ ∈ M^{n}. Nach Annahme existiert für alle i < n ein x_{i} mit p|x_{i}, ¬(q|x_{i} − a_{i}) und ¬(q|x_{i} − b_{i}); daraus folgt p|x̄ und ¬(q|x̄ − ā) und ¬(q|x̄ − b̄). Schließlich erhalten wir

(3.6) \begin{matrix}φ/ψ(M) > 1 & ⇒ & φ/ψ(M^{n}) > 1  für alle n ∈ ℕ \\ & ⇔ & φ/ψ(M) > n  für alle n ∈ ℕ \\ & ⇔ & φ/ψ(M) = ∞.  □ \end{matrix}

Wir haben es geschafft, alle Voraussetzungen des Satzes 2.16 zu erfüllen und erhalten damit:

Satz 3.12 Ist K ein rekursiv aufzählbarer algebraisch abgeschlossener unendlicher Körper, dann ist die Theorie der K[x]-Moduln entscheidbar.

Die Theorie der Quadrupel

Wir werden den Höhepunkt des vorangegangenen Kapitels, für geeignetes K ist die Theorie der K[x]-Moduln entscheidbar, nun benutzen, um die Entscheidbarkeit der Theorie der Quadrupel über K zu beweisen. Sehr wichtig ist dabei die Beobachtung, daß es eine Kategorie von Moduln gibt, die der Kategorie der Quadrupel ,,sehr ähnlich” ist. Diese Kategorie ist die der Moduln über der Wegalgebra über K des Köchers D̃_{4}. Dadurch ist es möglich, die meiste Zeit über Moduln zu reden, unsere bisherigen Ergebnisse anzuwenden und trotzdem zum Schluß eine Aussage über Quadrupel zu erhalten. Interpretationen erlauben uns, diese drei verschiedenen Kategorien zu vergleichen, deshalb wird im ersten Abschnitt das benötigte Wissen über Interpretationen bereitgestellt.

4.1 Übertragung von Entscheidbarkeit bei Interpretationen

Definition. Sei L eine Signatur. Eine nichtverschachtelte atomare Formel der Signatur L ist eine atomare Formel der folgenden Form:

(1.1) x = y, c = y für eine Konstante c aus L, F (x̄) = y für ein Funktionssym- bol F aus L oder Rx̄ für ein Relationssymbol R aus L.

Eine Formel wird nichtverschachtelt genannt, wenn alle atomaren Teilformeln nicht verschachtelt sind.

Beispiel. Die atomaren nichtverschachtelten Formeln in der Sprache der Moduln haben die Gestalt

x = y, x + y = z, − x = y, x = 0, f_{r}(x) = y,

dabei ist f_{r} die Skalarmultiplikation mit r ∈ R.

Lemma 4.1 Sei L eine Signatur. Jede atomare Formel ϕ(x̄) aus L ist äquivalent zu einer nichtverschachtelten Formel aus L.

Beweis durch Beispiel. F (G(x), z) = c ist äquivalent zu

(1.2) ∀u∀w(G(x) = u ∧ F (u, z) = w → c = w).

Es sollte nun klar geworden sein, wie im allgemeinen eine Formel ,,entschachtelt” werden kann. □

Sei jetzt K eine weitere Signatur, A eine K-Struktur und B eine L-Struktur. Eine Interpretation Γ von B in A besteht aus

(1.3) einer Formel ∂_{Γ}(x) der Signatur K,

(1.4) einer Formel ϕ_{Γ}(x_{0}, …, x_{m−1}) der Signatur K für jede nichtverschachtelte atomare Formel ϕ(y_{0}, …, y_{m−1}) der Signatur L,

(1.5) einer surjektiven Abbildung f_{Γ} : ∂_{Γ}(A) → dom(B),

so daß für alle nichtverschachtelten Formeln ϕ aus L und allen ā ∈ ∂_{Γ}(A)

(1.6) B ⊧ ϕ[f_{Γ}ā] ⇔ A ⊧ ϕ_{Γ}[ā]

erfüllt ist. Wir schreiben =_{Γ} für ϕ_{Γ}, wenn ϕ die Formel y_{0} = y_{1} ist. Es existieren einige Sätze der Signatur K, die in A erfüllt sein müssen, nur weil Γ eine Interpretation ist. Diese Sätze drücken folgendes aus:

(i) =_{Γ} definiert eine Äquivalenzrelation auf ∂_{Γ}(A),

(ii) für jede nichtverschachtelte atomare Formel ϕ von L gilt A ⊧ ϕ_{Γ}[ā] mit ā ∈ ∂_{Γ}(A), wenn A ⊧ ϕ_{Γ}[b̄] erfüllt ist, wobei b̄ ∈ ∂_{Γ}(A) und jedes b_{i} =_{Γ}-äquivalent zu a_{i} ist.

(iii)

Ist ϕ(y_{0}) eine Formel aus L der Form c = y_{0}, dann existiert ein a ∈ ∂_{Γ}(A),
so daß alle b ∈ ∂_{Γ}(A), für die A ⊧ φ_{Γ}[b] gilt, =_{Γ}-äquivalent zu a sind.

(iv)

Ist φ(x_{0}, …, x_{n−1}, y) eine Formel aus L der Form F (x_{0}, …, x_{n−1}) = y, dann existiert ein a ∈ ∂_{Γ}(A), so daß alle b ∈ ∂_{Γ}(A) mit

A ⊧ φ_{Γ}[c̄, a] ⇔ A ⊧ φ_{Γ}[c̄, b]

für ein Tupel c̄ ∈ ∂_{Γ}(A) auch =_{Γ}-äquivalent zu a sind.

Diese Sätze werden die Verträglichkeitsbedingungen von Γ genannt und mit Admis(Γ) bezeichnet.

Satz 4.2 (Reduktionssatz) Sei A eine K-Struktur, B eine L-Struktur und Γ eine Interpretation von B in A. Für jede Formel ϕ(ȳ) der Sprache L existiert eine Formel ϕ_{Γ}(x̄) der Sprache K derart, daß für alle ā ∈ ∂_{Γ}(A)

B ⊧ ϕ[f_{Γ}ā] ⇔ A ⊧ ϕ_{Γ}[ā]

erfüllt ist.

Beweis. Jede Formel aus L ist nach Lemma 4.1 äquivalent zu einer Formel aus L, in der alle atomaren Unterformeln nichtverschachtelt sind. Damit folgt die Behauptung für atomare Formeln aus (1.6) . Für zusammengesetzte Formeln definieren wir

(1.7) \begin{matrix}(¬ϕ)_{Γ} & = & ¬(ϕ_{Γ}), \\ (ϕ ∧ ψ)_{Γ} & = & ϕ_{Γ} ∧ ψ_{Γ}, \\ (ϕ ∨ ψ)_{Γ} & = & ϕ_{Γ} ∨ ψ_{Γ}, \\ (∀yϕ)_{Γ} & = & ∀x(∂_{Γ}(x) → ϕ_{Γ}), \\ (∃yϕ)_{Γ} & = & ∃x(∂_{Γ}(x) ∧ ϕ_{Γ}). \end{matrix}

Durch Induktion über den Formelaufbau läßt sich nun die Behauptung leicht beweisen, was wir uns hier sparen wollen. □

Die Zuordnung ϕ ↦ ϕ_{Γ} des Reduktionssatzes hängt nur von (1.3) und (1.4) ab, damit definieren diese beiden Teile der Definition von Γ eine Interpretation von L in K.

Satz 4.3 Sei Γ eine Interpretation einer Signatur L in einer Signatur K. Dann existiert für jede K-Struktur A, die ein Modell von Admis(Γ) ist, eine bis auf Isomorphie eindeutige L-Struktur B und eine Abbildung f : ∂_{Γ}(A) → dom(B), so daß Γ zusammen mit f eine Interpretation von B in A ist.

Beweis. Wir definieren eine Relation ∼ auf ∂_{Γ}(A) durch

(1.8) a ∼ a′ ⇔ A ⊧=_{Γ} [a, a′]

Wegen der ersten Verträglichkeitsbedingung ist ∼ eine Äquivalenzrelation; dom(B) sei die Menge aller Äquivalenzklassen a^{∼} mit a ∈ ∂_{Γ}(A). Für jedes Relationssymbol R aus L definieren wir R^{B} durch

(1.9) (a_{0}^{∼}, …, a_{m−1}^{∼}) ∈ R^{B} ⇔ A ⊧ ϕ_{Γ}[a_{0}, …, a_{m−1}],

dabei ist ϕ(y_{0}, …, y_{m−1}) die Formel Ry_{0} … y_{m−1}. Die zweite Verträglichkeitsbedingung erlaubt diese Konstruktion. Die Definitionen für Konstanten und Operationen von B sind ähnlich und durch die dritte bzw. vierte Verträglichkeitsbedingung gerechtfertigt. Wir definieren f : ∂_{Γ}(A) → dom B durch f(a) = a^{∼}; f ist surjektiv und B wurde so definiert, daß (1.6) erfüllt wird. Also ist Γ zusammen mit f eine Interpretation von B in A. Sei Γ zusammen mit g eine Interpretation von C in A. Für jedes a ∈ ∂_{Γ}(A) sei i(f(a)) = g(a). Wir behaupten, dadurch ist ein Isomorphismus i : B → C gegeben. Aus f(a) = f(a′) folgt A ⊧=_{Γ} [a, a′] und daraus g(a) = g(a′); i ist also wohldefiniert und auf ähnliche Weise kann auch die Injektivität von i gezeigt werden; außerdem ist i surjektiv, weil g surjektiv ist. □

Wir schreiben ΓA für die Struktur B des vorangegangenen Satzes.

Definition. Seien T und U Theorien in den Signaturen K bzw. L. Die Interpretation Γ ist eine totale Interpretation von U in T, wenn Γ eine Interpretation von L in K ist, jedes Modell von T auch ein Modell von Admis(Γ) ist, für jedes Modell A von T die Struktur ΓA ein Modell von U ist, und für jedes Modell C von U ein Modell D von T mit ΓD ≅ C existiert.

Satz 4.4 Seien T und U Theorien in den Signaturen K bzw. L und Γ eine totale Interpretation von U in T. Wenn L eine rekursiv aufzählbare Sprache ist, T eine entscheidbare Theorie und die Abbildung, die jede Formel ϕ aus L auf die Formel ϕ_{Γ} abbildet, rekursiv ist, dann ist auch U entscheidbar.

Beweis. Sei ϕ ein Satz in der Signatur L; ϕ wird rekursiv in die Formel ϕ_{Γ} übersetzt. Weil T entscheidbar ist, wissen wir, ob ϕ_{Γ} in T ist oder nicht. Angenommen, ϕ_{Γ} ist in T. Weil für jedes Modell B von U ein Modell A von T mit ΓA ≅ B existiert, so daß A ⊧ ϕ_{Γ} ⇔ B ⊧ ϕ gilt, ist damit ϕ ∈ U. Angenommen, ϕ_{Γ} ist nicht in T, dann existiert ein Modell C von T mit C ⊭ ϕ_{Γ} und damit ΓC ⊭ ϕ; ΓC ist aber ein Modell von U, also ist ϕ nicht in U. □

4.2 Zwei Interpretationen

Definition. Unter einem Köcher verstehen wir einen gerichteten Graphen, der keine Kreise enthält. Sei Γ ein Köcher und K(Γ) der K-Vektorraum, der als Basis alle Wege des Köchers Γ hat, vor allem existiert für jede Ecke x in K(Γ) ein Weg der Länge 0, wir bezeichnen ihn mit x|x. Wir führen eine Multiplikation auf K(Γ) ein: Multiplikation der Basiselemente ist einfach die Komposition von Wegen, das Produkt von zwei nichtverbindbaren Wegen ist 0. Dann setzen wir bilinear die Multiplikation auf K(Γ) fort. Ist Γ_{0} die Eckenmenge von Γ und endlich, dann ist ∑_{x∈Γ_{0}} x|x das neutrale Element der Multiplikation. Die so entstandene Algebra wird die Wegalgebra über K des Köchers Γ genannt.

Beispiel. Der erweiterte Dynkin-Köcher D̃_{4} hat folgendes Aussehen:

1  2
[figure]

0

[figure]
3  4

Wir interessieren uns für Moduln über der Algebra K(D̃_{4}). Mit e_{ij} bezeichnen wir den Pfeil von i nach j (i, j ∈ {0, …, 4} wie im Bild) und mit f_{e_{ij}} die Skalarmultiplikation mit dem Element e_{ij}.

Definition. Sei L die Signatur der K-Vektorräume und L^{+} die Erweiterung von L durch die vier einstelligen Relationssymbole R_{1}, …, R_{4}. Wir nennen eine L^{+}- Struktur V ein Quadrupel über dem Körper K, wenn das L-Redukt V |_{L} ein K-Vektorraum und R_{i}^{V} für i = 1, …, 4 jeweils eine einem Unterraum von V |_{L} zugrundeliegende Menge ist. Das bedeutet, die Menge, die aus den Axiomen für einen K-Vektorraum zusammen mit den Axiomenmengen

{∀x∀y(R_{i}x ∧ R_{i}y → R_{i}(f_{k}(x + y))) : k ∈ K} ∪ {R_{i}0}

für i = 1, …, 4 besteht, axiomatisiert die Theorie der Quadrupel; dabei ist f_{k} die einstellige Operation ‘Skalarmultiplikation mit k’. Weniger formal schreiben wir V = (U_{0}, …, U_{4}), dabei ist U_{0} unser Vektorraum und die restlichen U_{i} die entsprechenden Unterräume. Ein Quadrupel wird regulär genannt, wenn

(2.1) ∀x∃_{=1}y∃_{=1}z(x = y + z ∧ R_{i}y ∧ R_{j}z)

für die Fälle 1 ≤ i < j ≤ 3 und i = 3, j = 4 erfüllt ist.

Wir vereinbaren einige Schreibweisen, die wir innerhalb dieses Abschnittes einhalten werden: Mit L bezeichnen wir die Signatur der K-Vektorräume, mit L^{D} die der K(D̃_{4})-Moduln und mit L^{+} die Signatur der Quadrupel über K.

Satz 4.5 Es existiert eine totale Interpretation Γ der Theorie der Quadrupel über K in der Theorie der K(D̃_{4})-Moduln. Umgekehrt existiert auch eine totale Interpretation Λ der Theorie der K(D̃_{4})-Moduln in der Theorie der Quadrupel.

Beweis. Jeder K(D̃_{4})-Modul M ist auch ein K-Vektorraum mit einer Zerlegung

(2.2) M = 1^{K(D̃_{4})} · M = (∑_{i=0}^{4} f^{e_{ii}})M = ⨁_{i=0}^{4} f^{e_{ii}}(M).

Sei x ∈ f_{e_{i0}}(M), das heißt x = f_{e_{i0}}(f_{a_{1}}m_{1} + … + f_{a_{n}}m_{n}) mit a_{j} ∈ K(D̃_{4}) und m_{j} ∈ M. Aus e_{i0} · e_{jk} = 0 für k ≠ i folgt x = f_{e_{i0}}(f_{e_{00}}m) oder x = 0, auf jeden Fall x ∈ f_{e_{00}}(M). Wir können uns deshalb die Skalarmultiplikationen f_{e_{i0}} als lineare Abbildungen der K-Vektorräume f_{e_{ii}}(M) (i = 1, …, 4) in den K-Vektorraum f_{e_{00}}(M) vorstellen. Setzen wir U_{0} = f_{e_{00}}(M) und U_{i} = f_{e_{i0}}(M) für i = 1, …, 4, dann erhalten wir ein Quadrupel; wir geben ihm den Namen ΓM. Wir gehen jetzt diesen Weg zurück und definieren einen K(D̃_{4})-Modul ΛQ zu dem Quadrupel Q = (V_{0}, …, V_{4}): Es sei dom(ΛQ) = ⨁_{i=0}^{4} V_{i}, und mit Hilfe der Inklusion ε_{i} : V_{i} ↪ ⨁_{i=0}^{4} V_{i} definieren wir die Skalarmultiplikation auf ΛQ:

(2.3)  \begin{matrix}f_{e_{ii}}|_{ε_{j}V_{j}} & = & \{ \begin{matrix}1_{V_{i}} & i = j \\ 0_{V_{j}} & i ≠ j \end{matrix} \\ f_{e_{i0}}|_{ε_{j}V_{j}} & = & \{ \begin{matrix}ε_{0}ε_{i}^{−1} & i = j \\ 0_{V_{j}} & i ≠ j \end{matrix} \\ f_{e_{ij}} & = & 0_{V_{0}}  sonst. \end{matrix}

Wir geben nun die Bestandteile der Interpretation Γ an; ∂_{Γ}(x) sei die Formel ∃y(x = f_{e_{00}}y), dann ist ∂_{Γ}(M) = U_{0}; sei weiterhin f_{Γ} die Identität auf U_{0}. Es ist leicht zu zeigen, daß jeder K(D̃_{4})-Modul ein Modell von Admis(Γ) ist. Jetzt brauchen wir eine effektive Übertragung ϕ ↦ ϕ_{Γ} für atomare nichtverschachtelte Formeln in der Sprache L^{+}, so daß

(2.4) ΓM ⊧ ϕ[ā] ⇔ M ⊧ ϕ_{Γ}[ā]

für alle ā ∈ U_{0} gilt. Bei den Formeln y_{0} = y_{1}, y_{0} + y_{1} = y_{2}, y_{0} = −y_{1}, y_{0} = 0 müssen wir nur y durch x ersetzen. Für sie die Gültigkeit von (2.4) nachzuweisen ist trivial. Bleiben die Fälle f_{k}(y_{0}) = y_{1} für k ∈ K und R_{i}y_{0} für i = 1, …, 4. Im ersten Fall ist ϕ_{Γ} die Formel f_{k·1^{K(D̃_{4})}}(x_{0}) = x_{1}, im zweiten ∃x_{1}(f_{e_{i0}}x_{1} = x_{0}). Wir zeigen (2.4) für den zweiten Fall, der erste ist klar. Gilt ΓM ⊧ R_{i}a, dann ist a ∈ U_{i} = f_{e_{i0}}(M), also ist a = f_{e_{i0}}(b) für ein b ∈ M und M ⊧ ϕ_{Γ}[a]. Aus M ⊧ ϕ_{Γ}[a] folgt wiederum a ∈ U_{i} und daraus ΓM ⊧ R_{i}a. Es bleibt zu zeigen, daß Γ total ist. Daß es für jeden Modul M ein Quadrupel ΓM gibt, haben wir schon oben gesehen. Wegen Γ∘ΛQ = Q existiert zu jedem Quadrupel Q ein K(D̃_{4})-Modul M, nämlich ΛQ, mit ΓM ≅ Q.

Nun zu den Einzelheiten der Interpretation Λ: ∂_{Λ}(x) ist die Formel x = x, also ∂_{Λ}(U) = V_{0}; f_{Λ} : V_{0} → ΛQ is definiert durch m ↦ (m, 0, 0, 0). Wir brauchen wieder eine Übersetzung ϕ ↦ ϕ_{Λ} für die atomaren nichtverschachtelten Formeln aus L^{D}, so daß (2.5) ΛQ ⊧ ϕ[f_{Λ}ā] ⇔ Q ⊧ ϕ_{Λ}[ā]

für alle ā ∈ V_{0} erfüllt ist. Der einzige interessante Fall ist derjenige der Formel f_{w}(x) = y, und auch hierbei brauchen wir nur den Fall w = e_{ij} zu betrachten. Dann ist ϕ_{Λ} die Formel R_{i}x ∧ x = y, wenn i = j oder j = 0 ist. Ansonsten ist ϕ_{Λ} die Formel R_{i}x ∧ y = 0. Diese Formeln beschreiben präzise die in (2.3) definierte Skalarmultiplikation, so daß mit dieser Hilfe die Gültigkeit von (2.5) für diese Formeln ohne Probleme nachgewiesen werden kann.

Mit Λ ∘ ΓM = M und der Existenz von ΛQ für jedes Quadrupel Q folgt, daß Γ total ist. □

Daß die Theorien der Quadrupel und der K(D̃_{4})-Moduln jeweils ineinander interpretierbar sind, hat für uns den Vorteil, daß wir uns über Entscheidbarkeitsprobleme in der jeweils günstigeren Theorie Gedanken machen können und dann die Ergebnisse in die andere Theorie übertragen können. Unsere Interpretationen haben noch eine weitere schöne Eigenschaft:

Korollar 4.6 Endlich erzeugte K(D̃_{4})-Moduln werden in endlich erzeugten Quadrupeln interpretiert und umgekehrt. Genauso werden unzerlegbare K(D̃_{4})-Moduln in unzerlegbaren Quadrupeln interpretiert und umgekehrt.

Beweis. Aus der Konstruktion von ΓM und ΛQ im vorigen Beweis folgt sofort, daß diese Strukturen endlich erzeugt bzw. unzerlegbar sind, wenn M bzw. Q es sind. □

Einen entscheidenden Schritt weiter zur Entscheidbarkeit der Theorie der Quadrupel kommen wir mit dem folgenden Satz.

Satz 4.7 Es existiert eine totale Interpretation Γ der Theorie der regulären Quadrupel über K in der Theorie der K[x]-Moduln.

Beweis. Das besondere an dieser Interpretation ist ihre Zweidimensionalität, das bedeutet, jeder Variablen x in ϕ wird in ϕ_{Γ} ein Paar (x_{1}, x_{2}) von Variablen zugeordnet. Als erstes geben wir die Übersetzung der atomaren nichtverschachtelten Formeln aus L^{+} an:

\begin{matrix}ϕ & ϕ_{Γ} \\ x = y & x_{1} = y_{1} ∧ x_{2} = y_{2} \\ x + y = z & x_{1} + y_{1} = z_{1} ∧ x_{2} + y_{2} = z_{2} \\ −x = y & −x_{1} = y_{1} ∧ −x_{2} = y_{2} \\ x = 0 & x_{1} = 0 ∧ x_{2} = 0 \\ R_{1}x & x_{2} = 0 \\ R_{2}x & x_{1} = 0 \\ R_{3}x & x_{1} = x_{2} \\ R_{4}x & x_{1} = φ(x_{2}) \\ f_{k}(x) = y & f_{k}(x_{1}) = y_{1} ∧ f_{k}(x_{2}) = y_{2}. \end{matrix}

Dabei ist φ die Multiplikation mit dem Polynom x. Jetzt schauen wir uns an, wie wir von einem K[x]-Modul M zu dem Quadrupel ΓM kommen: Seien V_{1} = M × 0, V_{3} = 0 × M, V = V_{1} × V_{3}, V_{2} = {(m, m) : m ∈ M} und V_{4} = {(m, φ(m)) : m ∈ M}. Selbstverständlich ist ΓM ein Quadrupel. Wir müssen überprüfen, ob ΓM regulär ist. Das folgt aus V = V_{1} ⊕ V_{2} = V_{1} ⊕ V_{3} = V_{2} ⊕ V_{3} = V_{3} ⊕ V_{4}. Weiterhin sei ∂_{Γ}(x_{1}, x_{2}) einfach x_{1} = x_{1} ∧ x_{2} = x_{2} und f_{Γ} : M^{2} → ΓM definiert durch (x_{1}, x_{2}) ↦ x_{1} + x_{2}. Nun müssen wir die Liste der Formeln ϕ durchgehen, ob jeweils

(2.6) ΓM ⊧ ϕ[ā_{1} + ā_{2}] ⇔ M ⊧ ϕ_{Γ}[ā_{1}, ā_{2}]

gilt. Im ersten Fall folgt aus M ⊧ a_{1} = b_{1}∧a_{2} = b_{2} sofort ΓM ⊧ a_{1}+a_{2} = b_{1}+b_{2}; nach Konstruktion ist aber dom(ΓM) = M ⊕M, deshalb folgt aus ΓM ⊧ a_{1} +a_{2} = b_{1} +b_{2} auch wieder M ⊧ a_{1} = b_{1} ∧ a_{2} = b_{2}. Ähnlich ist die Argumentation, wenn ϕ eine der Formeln x + y = z, −x = y oder x = 0 ist.

Als letztes brauchen wir für jedes reguläre Quadrupel Q einen K[x]-Modul M, so daß ΓM ≅ Q gilt. Sei also Q = (V, V_{1}, …, V_{4}) gegeben. Sei M erst einmal V_{1} als K-Vektorraum. Wir definieren einen Endomorphismus φ : M → M, der dann als Multiplikation mit dem Polynom x interpretiert wird. Wegen V = V_{2} + V_{3} und V_{2} ∩ V_{3} = 0 ist f : V_{1} → V_{3} mit f(a) = b, wenn a + b ∈ V_{2} gilt, ein Homomorphismus. Aus V_{1} ∩ V_{2} = 0 folgt, daß f injektiv ist, aus V_{3} ⊆ V_{1} + V_{2}, daß f surjektiv ist; f ist also ein Isomorphismus, ebenso ist g : V_{3} → V_{1} mit g(a) = b, wenn a + b ∈ V_{4} gilt, ein Isomorphismus. Die Abbildung φ = g ∘ f : V_{1} → V_{1} ist ein Automorphismus und M = (V_{1}, φ) unser K[x]-Modul. Außerdem haben wir gezeigt, daß in jedem regulären Quadrupel die Unterräume V_{1} und V_{3} zueinander isomorph sind. Sei (U, U_{1}, …, U_{4}) das Quadrupel ΓM; mit U_{1} = V_{1} erhalten wir U_{3} ≅ V_{3} und schließlich ΓM ≅ Q. □

4.3 Entscheidbarkeit bei Quadrupeln

In diesem Abschnitt sei K ein algebraisch abgeschlossener rekursiv aufzählbarer unendlicher Körper.

Lemma 4.8 Die beiden folgenden Aussagen sind äquivalent:

(a) Für eine Invarianzaussage ϕ/ψ in einer freien Variablen gilt T_{left-D̃_{4}} ⊢ ϕ/ψ_{=1}.

(b) Für jeden unzerlegbaren endlichdimensionalen K(D̃_{4})-Modul M gilt M ⊧ ϕ/ψ_{=1}.

Beweis. O. B. d. A. ist M endlich erzeugt aber nicht notwendigerweise unzerlegbar. Denn die Dimension von M als Vektorraum über K ist endlich, und deswegen ist M direkte Summe von unzerlegbaren endlichdimensionalen K(D̃_{4})-Moduln. Also impliziert M ⊧ ϕ/ψ_{>1} sofort U ⊧ ϕ/ψ_{>1}, wobei U eben ein endlichdimensionaler unzerlegbarer K(D̃_{4})-Modul ist. Jetzt erhalten wir unsere Behauptung mit Hilfe des Satzes 2.21. □

Lemma 4.9 Es ist rekursiv entscheidbar, ob für eine Invarianzaussage ϕ/ψ von p.p. Formeln in einer freien Variablen und ein k ∈ ℕ der Satz ϕ/ψ_{=k} in der Theorie der K(D̃_{4})-Moduln liegt oder nicht.

Beweis. Wir hatten vorausgesetzt, daß K ein unendlicher Körper ist. Damit folgt aus ϕ/ψ(M) > 1 sofort ϕ/ψ(M) = ∞ und deswegen müssen wir nur den Fall k = 1 betrachten. Wir bezeichnen mit Γ die Interpretation des Satzes 4.5 und benutzen die im Beweis dieses Satzes eingeführten Schreibweisen. Mit Γ_{K[x]} bezeichnen wir die Interpretation des Satzes 4.7. Aus Korollar 4.6 und Lemma 4.8 folgt, daß genau dann T_{left-D̃_{4}} ⊢ ϕ/ψ_{=1} gilt, wenn

(i) für jedes reguläre Quadrupel Q ein K[x]-Modul M mit Γ_{K[x]}M = Q und M ⊧ ((ϕ/ψ_{=1})_{Λ})_{Γ_{K[x]}} existiert und

(ii)

Q′ ⊧ (ϕ/ψ_{=1})_{Λ} ist für jedes nichtreguläre endlichdimensionale unzerlegbare Quadrupel Q′ erfüllt.

Damit ist in der Situation T_{left-D̃_{4}} ⊬ ϕ/ψ_{=1} entweder (i) oder (ii) verletzt. Weil die Übersetzungen Q ↦ ΛQ, M′ ↦ ΓM′, M ↦ Γ_{K[x]}M, φ ↦ φ_{Λ} bzw. φ ↦ φ_{Γ_{K[x]}} rekursiv sind, ist nach Satz 4.5 und 4.7 entscheidbar, ob (i) verletzt ist oder nicht.

An dieser Stelle zitieren wir ein sehr tiefliegendes Ergebnis: Es existiert eine Klassifikation der unzerlegbaren endlichdimensionalen Quadrupel. Eine Liste findet man in [4] (die Quadrupel mit Defekt 0 entsprechen den Quadrupeln, die wir regulär genannt haben). Das bedeutet, die nichtregulären endlichdimensionalen unzerlegbaren Quadrupel sind rekursiv aufzählbar. Andererseits ist Q′ ⊧ (ϕ/ψ_{=1})_{Λ} äquivalent zu

(3.1) ΛQ′ ⊧ ϕ/ψ_{=1}.

Aus Satz 2.21 erhalten wir, daß für alle unzerlegbaren endlichdimensionalen Quadrupel Q′ die Aussage (3.1) erfüllt ist, wenn M_{ϕ} ⊧ ψ[a_{ϕ}] gilt. Satz 2.20 wiederum sagt, das ist gleichbedeutend zu H_{ψ} ∈ ⟨H_{φ}⟩. Die Gültigkeit der letzten Aussage ist nach Lemma 2.17 und dem Beweis von 3.10 durch das Lösen eines linearen Gleichungssystems nachprüfbar. Wir können nun entscheiden, ob T_{left-D̃_{4}} ⊢ φ gilt, indem wir die Konsequenzen von T_{left-D̃_{4}} aufzählen und beobachten, ob φ in dieser Liste auftaucht. Andererseits können wir mit Hilfe von (i) und dem Durchprobieren der Moduln ΛQ′ mit Q′ aus (ii) versuchen, T_{left-D̃_{4}} ⊢ φ zu widerlegen. Eine der beiden Methoden führt dann zum Erfolg. □

Lemma 4.10 Sei ψ eine boolesche Kombination von p.p. Sätzen. Dann ist entscheidbar, ob T_{left-D̃_{4}} ⊢ ψ ↔ ⊤ gilt.

Beweis. Gilt ψ in einem K(D̃_{4})-Modul nicht, dann gilt ψ gleich in allen K(D̃_{4})- Moduln nicht. Also haben wir T_{left-D̃_{4}} ⊢ ψ ↔ ⊤ oder T_{left-D̃_{4}} ⊢ ψ ↔ ⊥. Zählen wir die Konsequenzen von T_{left-D̃_{4}} auf, erscheint in dieser Aufzählung ψ ↔ ⊥ oder ψ ↔ ⊤. Damit ist entschieden, ob ψ ↔ ⊤ gilt. □

Satz 4.11 Die Theorie der K(D̃_{4})-Moduln ist entscheidbar.

Beweis. Aus T_{left-D̃_{4}} ⊬ φ für einen Satz φ folgt, daß T_{left-D̃_{4}} ∪ {¬φ} konsistent ist. Nach Lemma 1.8 existiert eine boolesche Kombination ψ von p.p. Sätzen mit T_{left-D̃_{4}} ⊢ ψ ↔ ⊤ und eine boolesche Kombination θ von Sätzen der Form ϕ/ψ_{=1} (von p.p. Formeln in einer freien Variablen) mit T_{left-D̃_{4}} ∪ {θ} ⊢ ¬φ ↔ ψ.

Damit erhalten wir folgendes Entscheidungsverfahren für den Satz φ: Wir erstellen eine Liste, in der alle Konsequenzen von T_{left-D̃_{4}} stehen. Wir erstellen eine Liste, in der für jeweils jede boolesche Kombination θ von p.p. Sätzen der Form ϕ/ψ_{=1} für p.p. Formeln in einer freien Variablen, die konsistent mit T_{left-D̃_{4}} ist, die Konsequenzen von T_{left-D̃_{4}} ∪ {θ} stehen. Aus Lemma 4.9 folgt, daß die Frage, ob T_{left-D̃_{4}} ∪ {θ} konsistent ist, entscheidbar ist, und damit sind beide Listen auf rekursive Weise erstellbar. Außerdem zählen wir auch die booleschen Kombinationen von p.p. Sätzen ψ mit T_{left-D̃_{4}} ⊢ ψ ↔ ⊤ in einer dritten Liste auf. Das erlaubt uns Lemma 4.10. Wir testen nun, ob φ in der ersten Liste auftaucht. Gleichzeitig testen wir, ob ¬φ ↔ ψ für ein ψ aus der dritten Liste in der zweiten Liste auftaucht. Wir arbeiten die dritte Liste so ab, daß für jeden Satz ψ aus dieser Liste ¬φ ↔ ψ mit jeder Konsequenz aus der zweiten Liste verglichen wird. Jetzt muß φ in der ersten oder für ein ψ aus der dritten Liste ¬φ ↔ ψ in der zweiten Liste auftauchen. □

Aus Satz 3.12 folgt sofort:

Korollar 4.12 Die Theorie der Quadrupel über einem rekursiv aufzählbaren unendlichen algebraisch abgeschlossenen Körper ist entscheidbar.

Bemerkungen zu den Ergebnissen

Um den roten Faden nicht zu verlieren, habe ich jeden Umweg zu unserem Ziel, die Entscheidbarkeit der Theorie der Quadrupel zu beweisen, vermieden; ein paar Bemerkungen halte ich aber doch noch für angebracht:

Zu Kapitel 1 & 2: Meine beiden Hauptquellen sind [10] und [9]. Die benutzten modelltheoretischen Hilfsmittel sind recht bescheiden: Quantorenelimination, Typen und der Begriff der Saturiertheit spielen eine Rolle, der einzige tieferliegende Satz, der verwendet wurde, ist der Kompaktheitssatz. Wir benutzten keine Stabilitätstheorie: Jede vollständige Theorie von Moduln ist stabil, damit ist eine Unterteilung solcher Theorien in stabil, superstabil oder total transzendent möglich. Total transzendente Theorien haben viele wünschenswerte Eigenschaften. Andererseits ist eine vollständige Theorie von Moduln genau dann total transzendent, wenn für jedes Modell M von T der Modul M^{(ℵ_{0})} rein injektiv ist, und wir sind wieder bei einem von uns viel benutzten Begriff angekommen.

Zu Kapitel 3: Wir hatten uns bei der Entscheidbarkeit der Theorie der K[x]-Moduln auf den Fall, daß K ein rekursiv aufzählbarer algebraisch abgeschlossener unendlicher Körper ist, beschränkt. Natürlich können wir auf die rekursive Aufzählbarkeit nicht verzichten, wenn wir an algorithmischen Problemen interessiert sind; ansonsten muß nur gewährleistet sein, daß ein Algorithmus existiert, der von jedem Element aus K[x] die irreduziblen Faktoren bestimmt. Jeder endliche Körper, der Körper der rationalen Zahlen und jeder algebraisch abgeschlossene abzählbare Körper erfüllt diese Eigenschaft. Ist K aber endlich und M ein K[x]-Modul, dann gilt der Schluß

M ⊧ φ/ψ_{>1} ⇒ M ⊧ φ/ψ_{=∞}

im allgemeinen nicht. Wir müssen dann einen Algorithmus angeben, der φ/ψ(M) berechnet.

Zu Kapitel 4: Wir können den Körper K genauso wie in der Bemerkung zu Kapitel 3 wählen, und die Theorie der Quadrupel über K bleibt weiterhin entscheidbar. Es mag überrascht haben, daß wir K(D̃_{4})-Moduln eingeführt haben, zum Beweis der Entscheidbarkeit der Theorie dieser Moduln auf Quadrupel zurückgegriffen haben und dann die Entscheidbarkeit der Theorie der Quadrupel aus der Entscheidbarkeit der K(D̃_{4})-Moduln abgeleitet haben. Das lag aber nur daran, daß eine Klassifikation der unzerlegbaren endlichdimensionalen Quadrupel zitierfähig vorliegt, eine Klassifikation der K(D̃_{4})-Moduln aber nicht.

Literaturverzeichnis

[1] Anderson, F. W., Fuller, K. R., Rings and Categories of Modules, GTM, Springer-Verlag, New York 1974.

[2] Artin, M., Algebra, Birkhäuser Advanced Texts, Bael 1993.

[3] Baur, W., On the elementary theory of quadruples of vector spaces, Annals of mathematical logic 19, 1980.

[4] Brenner, S., Four Subspaces of a Vector space, Journal of Algebra 29, 1974.

[5] Feferman S., Vaught R.L., The first order properties of products of algebraic systems, Fundamenta Mathematicae XLVII, 1959.

[6] Hodges, W., Model Theory, Encyclopedia of mathematics and its applications 42, Cambridge University Press, Cambridge 1993.

[7] Jensen, C. U., Lenzing H., Model theoretic algebra, Gord and Breach science Publishes, New York 1989.

[8] Pierce R. S., Associative algebras, GTM, Springer-Verlag, New York 1982.

[9] Prest, M., Model Theory and Modules, London Mathematical Society Lecture Note Series 130, Cambridge University Press, Cambridge 1988.

[10] Ziegler, M., Model theory of modules, Ann. Pure Appl. Logic 26, 1984.

Hiermit erkläre ich, daß diese Arbeit von mir selbständig erstellt wurde, und ich keine außer den genannten Hilfsmitteln benutzt habe.

Darmstadt, der 10. April 1996