Diagramm (Logik)

In der mathematischen Logik bezeichnet ein Diagramm eine bestimmte Menge von Aussagen, mit der sich Beziehungen zwischen Modellen ausdrücken lassen. Die Verwendung solcher Diagramme bezeichnet man als Diagrammmethode. Sie wurde unabhängig von A. I. Malzew und A. Robinson eingeführt.

Definition

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

$\begin{array}{cc}D(ℳ)& =\{\phi (\overrightarrow{m}):ℳ\models \phi (\overrightarrow{m}),\phi \in L\text{ atomar},\overrightarrow{m}\text{ in }M\}\\ & \cup \{\mathrm{\neg }\phi (\overrightarrow{m}):ℳ\models \mathrm{\neg }\phi (\overrightarrow{m}),\phi \in L\text{ atomar},\overrightarrow{m}\text{ in }M\}\end{array}$

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

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

Beispielanwendung

Gewisse Beziehungen zwischen Modellen lassen sich durch Diagramme ausdrücken, was hier anhand eines einfachen Beispiels gezeigt werden soll. Es gilt

Für zwei $L$-Modelle $ℳ$ und $𝒩$ mit Trägermengen $M\subset N$ sind äquivalent:

• $ℳ$ ist Untermodell von $𝒩$.
• $(𝒩,M)\models D(ℳ)$, das heißt, das um die Konstanten $M$ erweiterte Modell ist ein $L(M)$-Modell des Diagramms von $ℳ$.

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

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

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

• $ℳ$ ist monomorph einbettbar in $𝒩$ (isomorph zu einer Unterstruktur).
• Es gibt eine $L(M)$-Expansion von $𝒩$, die Modell von $D(ℳ)$ ist.

Weitere Diagramme

Man kann die Aussagenmengen, die das Diagramm ausmachen, ändern und so zu weiteren Diagrammbegriffen kommen.

Positives Diagramm

Das positive Diagramm eines Modells $ℳ$ ist

$D_{+}(ℳ)=\{\phi (\overrightarrow{m}):ℳ\models \phi (\overrightarrow{m}),\phi \in L\text{ atomar},\overrightarrow{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:

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

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 $L$-Modell $ℳ$ mit Trägermenge $M$ gegeben, so ist die Gesamtheit aller in $ℳ$ gültigen $L(M)$-Formeln $\phi (\overrightarrow{m})$ nichts anderes als die Theorie des erweiterten Modells $(ℳ,M)$, bei dem jede neue Konstante $m$ durch sich selbst interpretiert wird. Diese Theorie bezeichnet man mit $\mathrm{T}\mathrm{h}(ℳ,M)$ und nennt sie das elementare Diagramm von $ℳ$.

Mit diesem Begriff lässt sich die elementare Einbettbarkeit charakterisieren. Für zwei $ℳ$ und $𝒩$ sind äquivalent:

• $ℳ$ lässt sich in $𝒩$ elementar einbetten.
• Es gibt eine $L(M)$-Expansion von $𝒩$, die Modell von $\mathrm{T}\mathrm{h}(ℳ,M)$ ist.

Für zwei $L$-Modelle $ℳ$ und $𝒩$ mit Trägermengen $M\subset N$ sind äquivalent:

• $ℳ$ ist elementare Unterstruktur von $𝒩$.
• $(𝒩,M)\models \mathrm{T}\mathrm{h}(ℳ,M)$, das heißt das um die Konstanten $M$ erweiterte Modell ist ein $L(M)$-Modell des elementaren Diagramms von $ℳ$.