Diagramm (Logik)

Grundidee und Definition

In der mathematischen Logik ist ein Diagramm eine Menge von Aussagen, mit der Beziehungen zwischen Modellen einer Sprache der Prädikatenlogik erster Stufe beschrieben werden können. Die zugehörige Technik heißt Diagrammmethode.

Sei \mathcal M ein Modell der Sprache L mit Trägermenge M. Sein (atomisches) Diagramm D(\mathcal M) enthält genau alle atomaren Aussagen über Elemente von M, die in \mathcal M wahr sind, sowie die Negationen aller atomaren Aussagen, die in \mathcal M falsch sind. Ein Tupel \vec m setzt dabei die freien Variablen einer Formel durch passende Elemente aus M ein.

Atomare Formeln sind Termgleichungen oder Relationen. Das Diagramm besteht daher aus allen im Modell gültigen Termgleichungen, Termungleichungen, Relationen und negierten Relationen für Elemente aus M. Erweitert man L zur Sprache L(M), indem für jedes Element von M eine Konstante eingeführt wird, ist das Diagramm die Menge aller wahren atomaren oder negierten atomaren L(M)-Aussagen.

Untermodelle und monomorphe Einbettungen

Für zwei L-Modelle \mathcal M und \mathcal N mit M\subset N gilt:

• \mathcal M ist genau dann ein Untermodell von \mathcal N, wenn (\mathcal N,M)\models D(\mathcal M) gilt.

Das bedeutet: Das um die Konstanten aus M erweiterte Modell \mathcal N erfüllt sämtliche Aussagen aus dem Diagramm von \mathcal M. Sind etwa eine Funktion, eine Relation oder eine Gleichung für Elemente aus M in \mathcal M festgelegt, müssen sie in \mathcal N auf diesen Elementen genauso gelten. Beispielsweise folgt aus f^{\mathcal M}(\vec m)=m_0, dass auch f^{\mathcal N}(\vec m)=m_0 gilt. Damit ist f^{\mathcal M} die Einschränkung von f^{\mathcal N} auf M.

Dies verallgemeinert das Diagrammlemma: \mathcal M ist genau dann monomorph in \mathcal N einbettbar, also isomorph zu einer Unterstruktur von \mathcal N, wenn es eine L(M)-Expansion von \mathcal N gibt, die ein Modell von D(\mathcal M) ist. Eine monomorphe Einbettung ist dabei ein injektiver starker Homomorphismus.

Positives Diagramm

Das positive Diagramm eines Modells \mathcal M lautet

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

Es enthält nur wahre atomare Aussagen, aber keine negierten atomaren Aussagen. Es hält somit nur fest, was in einem Modell gilt, nicht ausdrücklich, was nicht gilt.

Damit lässt sich homomorphe Einbettbarkeit beschreiben: \mathcal M ist genau dann homomorph in \mathcal N einbettbar, wenn eine L(M)-Expansion von \mathcal N ein Modell von D_+(\mathcal M) ist.

Elementares Diagramm

Beim elementaren Diagramm werden nicht nur atomare Aussagen betrachtet, sondern alle L(M)-Formeln. Für ein Modell \mathcal M mit Trägermenge M ist es die Theorie des erweiterten Modells (\mathcal M,M):

\mathrm{Th}(\mathcal M,M)

ist die Gesamtheit aller in \mathcal M gültigen L(M)-Formeln \varphi(\vec m), wobei jede neue Konstante m durch sich selbst interpretiert wird.

Damit wird elementare Einbettbarkeit charakterisiert: \mathcal M lässt sich genau dann elementar in \mathcal N einbetten, wenn es eine L(M)-Expansion von \mathcal N gibt, die ein Modell von \mathrm{Th}(\mathcal M,M) ist.

Falls M\subset N, ist \mathcal M genau dann eine elementare Unterstruktur von \mathcal N, wenn (\mathcal N,M)\models\mathrm{Th}(\mathcal M,M) gilt. Dann bleiben also nicht nur atomare Tatsachen, sondern alle Formeln mit Parametern aus M beim Übergang zu \mathcal N wahr.