Diagramm (Logik)

aus Wikipedia, der freien Enzyklopädie
Zur Navigation springen Zur Suche springen

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]

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 | Quelltext 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 | Quelltext bearbeiten]

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

Positives Diagramm

[Bearbeiten | Quelltext 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 | Quelltext 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 | Quelltext 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