Diagramm (Logik)

Menge von Aussagen in der mathematischen 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.[1]

Definition

Bearbeiten

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

 

das Diagramm, oder auch das atomare Diagramm von  . Dabei steht   für ein Tupel mit Elementen aus   von jeweils passender Länge, so dass die Elemente des Tupels die freien Variablen der Formel   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  , die im Modell   gelten.

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

Beispielanwendung

Bearbeiten

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

Für zwei  -Modelle   und   mit Trägermengen   sind äquivalent:

  •   ist Untermodell von  .
  •  , das heißt, das um die Konstanten   erweiterte Modell ist ein  -Modell des Diagramms von  .

Zum Beweis sei zunächst   Untermodell von  . Bestehende Termgleichungen, Termungleichungen, Relationen und deren Negationen von Elementen aus   gelten dann auch im größeren Modell  , das heißt   für alle atomaren oder negierten, atomaren  -Formeln  , für die   gilt, das heißt   ist Modell für jede  -Aussage aus dem Diagramm von  .

Ist umgekehrt  , so ist zu zeigen, dass   die  -Konstanten enthält und dass die  -Funktionen und  -Relationen von   genau die entsprechenden, auf   eingeschränkten Funktionen bzw. Relationen von   sind. Wir zeigen das am Beispiel der Funktionen. Sei   eine  -Funktion und   bzw.   deren Interpretation in   bzw.  . Ist   und  , so ist   eine  -Aussage aus dem Diagramm von  . Da  , folgt  , das heißt   ist die Einschränkung von  . Die Konstanten und Relationen werden genauso behandelt.

Das lässt sich verallgemeinern, indem man von der Teilmengenbeziehung   zu einer monomorphen Einbettung   (d. h.   ist ein injektiver starker Homomorphismus) übergeht. Es sind äquivalent (Diagrammlemma):[3]

  •   ist monomorph einbettbar in   (isomorph zu einer Unterstruktur).
  • Es gibt eine  -Expansion von  , die Modell von   ist.

Weitere Diagramme

Bearbeiten

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

Positives Diagramm

Bearbeiten

Das positive Diagramm eines Modells   ist[4]

 

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]

  •   ist homomorph einbettbar in  .
  • Es gibt eine  -Expansion von  , die Modell von  .

Elementares Diagramm

Bearbeiten

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  -Modell   mit Trägermenge   gegeben, so ist die Gesamtheit aller in   gültigen  -Formeln   nichts anderes als die Theorie des erweiterten Modells  , bei dem jede neue Konstante   durch sich selbst interpretiert wird. Diese Theorie bezeichnet man mit   und nennt sie das elementare Diagramm von  .[7][8]

Mit diesem Begriff lässt sich die elementare Einbettbarkeit charakterisieren.[9] Für zwei   und   sind äquivalent:

  •   lässt sich in   elementar einbetten.
  • Es gibt eine  -Expansion von  , die Modell von   ist.

Für zwei  -Modelle   und   mit Trägermengen   sind äquivalent:

  •   ist elementare Unterstruktur von  .
  •  , das heißt das um die Konstanten   erweiterte Modell ist ein  -Modell des elementaren Diagramms von  .

Einzelnachweise

Bearbeiten
  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