Diagramm (Logik)

In d​er mathematischen Logik bezeichnet e​in Diagramm e​ine bestimmte Menge v​on Aussagen, m​it der s​ich Beziehungen zwischen Modellen ausdrücken lassen. Die Verwendung solcher Diagramme bezeichnet m​an als Diagrammmethode. Sie w​urde unabhängig v​on A. I. Malzew u​nd A. Robinson eingeführt.[1]

Definition

Es sei ${\displaystyle {\mathcal {M}}}$ ein Modell zu einer Sprache ${\displaystyle L}$ der Prädikatenlogik erster Stufe. Ist ${\displaystyle M}$ der Träger von ${\displaystyle {\mathcal {M}}}$ , so heißt

${\displaystyle {\begin{aligned}D({\mathcal {M}})&=\{\varphi ({\vec {m}}):{\mathcal {M}}\models \varphi ({\vec {m}}),\,\varphi \in L{\text{ atomar}},{\vec {m}}{\text{ in }}M\}\\&=\{\neg \varphi ({\vec {m}}):{\mathcal {M}}\models \neg \varphi ({\vec {m}}),\,\varphi \in L{\text{ atomar}},{\vec {m}}{\text{ in }}M\}\end{aligned}}}$

das Diagramm, oder auch das atomare Diagramm von ${\displaystyle {\mathcal {M}}}$ . Dabei steht ${\displaystyle {\vec {m}}}$ für ein Tupel mit Elementen aus ${\displaystyle M}$ von jeweils passender Länge, so dass die Elemente des Tupels die freien Variablen der Formel ${\displaystyle \varphi \in L}$ ersetzen. Eine Formel heißt atomar, wenn es sich um eine Termgleichung oder um eine Relation handelt. Demnach besteht das Diagramm von ${\displaystyle {\mathcal {M}}}$ aus allen Termgleichungen, Termungleichungen, Relationen und negierten Relationen von Elementen aus ${\displaystyle M}$ , die im Modell ${\displaystyle {\mathcal {M}}}$ gelten.

Geht man von ${\displaystyle L}$ mittels Konstantenexpansion zur Sprache ${\displaystyle L(M)}$ über, in der also jedes Individuum aus ${\displaystyle M}$ als Konstante hinzugefügt wird, so ist das Diagramm die Menge der im Modell gültigen atomaren oder negierten atomaren ${\displaystyle L(M)}$ -Aussagen.

Beispielanwendung

Gewisse Beziehungen zwischen Modellen lassen s​ich durch Diagramme ausdrücken, w​as hier anhand e​ines einfachen Beispiels gezeigt werden soll. Es gilt[2]

Für zwei ${\displaystyle L}$ -Modelle ${\displaystyle {\mathcal {M}}}$ und ${\displaystyle {\mathcal {N}}}$ mit Trägermengen ${\displaystyle M\subset N}$ sind äquivalent:

• ${\displaystyle {\mathcal {M}}}$ ist Untermodell von ${\displaystyle {\mathcal {N}}}$ .
• ${\displaystyle ({\mathcal {N}},M)\models D({\mathcal {M}})}$ , das heißt, das um die Konstanten ${\displaystyle M}$ erweiterte Modell ist ein ${\displaystyle L(M)}$ -Modell des Diagramms von ${\displaystyle {\mathcal {M}}}$ .

Zum Beweis sei zunächst ${\displaystyle {\mathcal {M}}}$ Untermodell von ${\displaystyle {\mathcal {N}}}$ . Bestehende Termgleichungen, Termungleichungen, Relationen und deren Negationen von Elementen aus ${\displaystyle M}$ gelten dann auch im größeren Modell ${\displaystyle {\mathcal {N}}}$ , das heißt ${\displaystyle {\mathcal {N}}\models \varphi ({\vec {m}})}$ für alle atomaren oder negierten, atomaren ${\displaystyle L}$ -Formeln ${\displaystyle \varphi }$ , für die ${\displaystyle \varphi ({\vec {m}})}$ gilt, das heißt ${\displaystyle {\mathcal {N}}}$ ist Modell für jede ${\displaystyle L(M)}$ -Aussage aus dem Diagramm von ${\displaystyle {\mathcal {M}}}$ .

Ist umgekehrt ${\displaystyle ({\mathcal {N}},M)\models D({\mathcal {M}})}$ , so ist zu zeigen, dass ${\displaystyle M}$ die ${\displaystyle L}$ -Konstanten enthält und dass die ${\displaystyle L}$ -Funktionen und ${\displaystyle L}$ -Relationen von ${\displaystyle M}$ genau die entsprechenden, auf ${\displaystyle M}$ eingeschränkten Funktionen bzw. Relationen von ${\displaystyle N}$ sind. Wir zeigen das am Beispiel der Funktionen. Sei ${\displaystyle f}$ eine ${\displaystyle L}$ -Funktion und ${\displaystyle f^{\mathcal {M}}:M^{n}\rightarrow M}$ bzw. ${\displaystyle f^{\mathcal {N}}:N^{n}\rightarrow N}$ deren Interpretation in ${\displaystyle {\mathcal {M}}}$ bzw. ${\displaystyle {\mathcal {N}}}$ . Ist ${\displaystyle {\vec {m}}\in M^{n}}$ und ${\displaystyle f^{\mathcal {M}}({\vec {m}})=m_{0}\in M}$ , so ist ${\displaystyle f({\vec {m}})=m_{0}}$ eine ${\displaystyle L(M)}$ -Aussage aus dem Diagramm von ${\displaystyle {\mathcal {M}}}$ . Da ${\displaystyle ({\mathcal {N}},M)\models D({\mathcal {M}})}$ , folgt ${\displaystyle f^{\mathcal {N}}({\vec {m}})=m_{0}}$ , das heißt ${\displaystyle f^{\mathcal {M}}}$ ist die Einschränkung von ${\displaystyle f^{\mathcal {N}}}$ . Die Konstanten und Relationen werden genauso behandelt.

Das lässt sich verallgemeinern, indem man von der Teilmengenbeziehung ${\displaystyle M\subset N}$ zu einer monomorphen Einbettung ${\displaystyle F:M\rightarrow N}$ (d. h. ${\displaystyle F}$ ist ein injektiver starker Homomorphismus) übergeht. Es sind äquivalent (Diagrammlemma):[3]

• ${\displaystyle {\mathcal {M}}}$ ist monomorph einbettbar in ${\displaystyle {\mathcal {N}}}$ (isomorph zu einer Unterstruktur).
• Es gibt eine ${\displaystyle L(M)}$ -Expansion von ${\displaystyle {\mathcal {N}}}$ , die Modell von ${\displaystyle D({\mathcal {M}})}$ ist.

Weitere Diagramme

Man k​ann die Aussagenmengen, d​ie das Diagramm ausmachen, ändern u​nd so z​u weiteren Diagrammbegriffen kommen.

Positives Diagramm

Das positive Diagramm eines Modells ${\displaystyle {\mathcal {M}}}$ ist[4]

${\displaystyle D_{+}({\mathcal {M}})=\{\varphi ({\vec {m}}):{\mathcal {M}}\models \varphi ({\vec {m}}),\,\varphi \in L{\text{ atomar}},{\vec {m}}{\text{ in }}M\}.}$

Hier werden also nur die atomaren Aussagen betrachtet, die Negationen atomarer Aussagen hingegen nicht mehr. In Analogie zu obiger Verwendung des Diagramms zur monomorphen Einbettbarkeit kann mittels des positiven Diagramms homomorphe Einbettbarkeit charakterisiert werden. Äquivalent sind:[5][6]

• ${\displaystyle {\mathcal {M}}}$ ist homomorph einbettbar in ${\displaystyle {\mathcal {N}}}$ .
• Es gibt eine ${\displaystyle L(M)}$ -Expansion von ${\displaystyle {\mathcal {N}}}$ , die Modell von ${\displaystyle D_{+}({\mathcal {M}})}$ .

Elementares Diagramm

Während man das positive Diagramm durch Einschränkung der betrachteten Aussagen gewonnen hat, lässt man beim sogenannten elementaren Diagramm nun alle Aussagen zu. Ist ein ${\displaystyle L}$ -Modell ${\displaystyle {\mathcal {M}}}$ mit Trägermenge ${\displaystyle M}$ gegeben, so ist die Gesamtheit aller in ${\displaystyle {\mathcal {M}}}$ gültigen ${\displaystyle L(M)}$ -Formeln ${\displaystyle \varphi ({\vec {m}})}$ nichts anderes als die Theorie des erweiterten Modells ${\displaystyle ({\mathcal {M}},M)}$ , bei dem jede neue Konstante ${\displaystyle m}$ durch sich selbst interpretiert wird. Diese Theorie bezeichnet man mit ${\displaystyle \mathrm {Th} ({\mathcal {M}},M)}$ und nennt sie das elementare Diagramm von ${\displaystyle {\mathcal {M}}}$ .[7][8]

Mit diesem Begriff lässt sich die elementare Einbettbarkeit charakterisieren.[9] Für zwei ${\displaystyle {\mathcal {M}}}$ und ${\displaystyle {\mathcal {N}}}$ sind äquivalent:

• ${\displaystyle {\mathcal {M}}}$ lässt sich in ${\displaystyle {\mathcal {N}}}$ elementar einbetten.
• Es gibt eine ${\displaystyle L(M)}$ -Expansion von ${\displaystyle {\mathcal {N}}}$ , die Modell von ${\displaystyle \mathrm {Th} ({\mathcal {M}},M)}$ ist.

Für zwei ${\displaystyle L}$ -Modelle ${\displaystyle {\mathcal {M}}}$ und ${\displaystyle {\mathcal {N}}}$ mit Trägermengen ${\displaystyle M\subset N}$ sind äquivalent:

• ${\displaystyle {\mathcal {M}}}$ ist elementare Unterstruktur von ${\displaystyle {\mathcal {N}}}$ .
• ${\displaystyle ({\mathcal {N}},M)\models \mathrm {Th} ({\mathcal {M}},M)}$ , das heißt das um die Konstanten ${\displaystyle M}$ erweiterte Modell ist ein ${\displaystyle L(M)}$ -Modell des elementaren Diagramms von ${\displaystyle {\mathcal {M}}}$ .

Einzelnachweise

1. Philipp Rothmaler: Einführung in die Modelltheorie, Spektrum Akademischer Verlag 1995, ISBN 978-3-86025-461-5, Seite 93
2. Philipp Rothmaler: Einführung in die Modelltheorie, Spektrum Akademischer Verlag 1995, ISBN 978-3-86025-461-5, Seite 96
3. Philipp Rothmaler: Einführung in die Modelltheorie, Spektrum Akademischer Verlag 1995, ISBN 978-3-86025-461-5, Lemma 6.1.2
4. Philipp Rothmaler: Einführung in die Modelltheorie, Spektrum Akademischer Verlag 1995, ISBN 978-3-86025-461-5, Abschnitt 7.1: Positive Diagramme
5. Philipp Rothmaler: Einführung in die Modelltheorie, Spektrum Akademischer Verlag 1995, ISBN 978-3-86025-461-5, Lemma 7.1.1: Positive Diagramme
6. C. C. Chang, H. J. Keisler: Model Theory, Studies in Logic and the Foundations of Mathematics, Band 73, Elsevier Science 1990, ISBN 0-444-88054-2, Satz 2.1.12
7. Philipp Rothmaler: Einführung in die Modelltheorie, Spektrum Akademischer Verlag 1995, ISBN 978-3-86025-461-5, Abschnitt 8.2: Elementare Abbildungen
8. C. C. Chang, H. J. Keisler: Model Theory, Studies in Logic and the Foundations of Mathematics, Band 73, Elsevier Science 1990, ISBN 0-444-88054-2, Seite 137
9. Philipp Rothmaler: Einführung in die Modelltheorie, Spektrum Akademischer Verlag 1995, ISBN 978-3-86025-461-5, Lemma 8.2.1