Das Koinzidenzlemma ist ein Satz der mathematischen Logik, der die naheliegende Feststellung trifft, dass der Wahrheitswert einer interpretierten Formel nur von den Interpretationen derjenigen Symbole abhängt, die tatsächlich in der Formel vorkommen.

Aussagenlogik

Bearbeiten

Das Koinzidenzlemma in der Aussagenlogik beschreibt das Verhalten einer gegebenen aussagenlogischen Formel hinsichtlich der Belegung ihrer Aussagenvariablen. Es besagt anschaulich, dass (von der Struktur der Formel selbst abgesehen) der Wahrheitswert einer Formel ausschließlich von den Wahrheitswerten der in der Formel enthaltenen Aussagenvariablen abhängt.

Aussagen sind aus sogenannten Aussagenvariablen   und den booleschen Operationen   und   aufgebaut, zum Beispiel  . Eine Belegung ist eine Abbildung  , die jeder Variablen einen der beiden Wahrheitswerte wahr oder falsch zuordnet, woraus dann der Wahrheitswert der Aussage ermittelt werden kann. Ist   eine solche Aussage, schreibt man  , wenn   durch die Belegung   wahr wird. Formal lässt sich das Koinzidenzlemma nun wie folgt ausdrücken:

  • Seien b und b' zwei Belegungen und sei   eine Aussage. Ist   für alle in   vorkommenden Aussagenvariablen, so gilt[1][2]:
  genau dann, wenn  .

Prädikatenlogik

Bearbeiten

In der Prädikatenlogik werden Formeln durch Modelle interpretiert, wobei jede Variable einem Element der Modellmenge (Universum des Modells) zugeordnet wird. Darüber hinaus werden auch alle nicht-logischen Symbole der sogenannten Signatur in der Modellmenge interpretiert, das heißt einem Konstantensymbol wird ein Element der Modellmenge, einem Funktionssymbol eine Funktion auf der Modellmenge und einem Relationssymbol eine Relation auf der Modellmenge zugeordnet. Eine typische Signatur ist   zur Bildung von Formeln in der Ring- oder Körpertheorie mit einer Anordnung. Ein Beispiel für eine typische Aussage ist

 ,

die die Lösbarkeit linearer Gleichungen behauptet, wobei die Variable   frei ist, das heißt noch nicht festgelegt ist. Die Interpretation dieser Formel im Ring  , das heißt die Konstantensymbole 0 und 1 werden als die ganzen Zahlen 0 und 1 interpretiert, die Funktionssymbole   als Addition und Multiplikation und < schließlich als die übliche Größer-Relation, ist bekanntlich falsch, außer wenn   durch +1 oder −1 interpretiert wird. Eine analoge Interpretation im Körper   hingegen führt bei jeder Interpretation von   zu einer wahren Aussage. Offenbar ist der Wahrheitsgehalt dieser Aussage von der Interpretation der ‚<‘-Relation unabhängig, denn das Symbol < kommt in der Formel gar nicht vor. Genau das ist der Inhalt des Koinzidenzlemmas:

  • Sei   eine Formel und   seien zwei Modelle über derselben Menge. Stimmen die Interpretationen der in   frei vorkommenden Variablen und die Interpretationen sämtlicher in   vorkommenden nicht-logischen Symbole überein, so gilt[3]:
  genau dann, wenn  .

Dieser technische Satz, dessen einfacher Beweis mittels „Induktion über den Aufbau der Formel“ geführt wird, kommt zum Beispiel bei Anwendungen von Symbolerweiterungen zum Einsatz. Dabei erweitert man die Symbolmenge   um weitere Symbole, die man zu irgendwelchen Zwecken einsetzen möchte. Der Wahrheitsgehalt der mittels der Symbolmenge   aufgebauten Formeln bleibt davon nach dem Koinzidenzlemma unberührt.

Einzelnachweise

Bearbeiten
  1. Wolfgang Rautenberg: Einführung in die mathematische Logik, Friedr. Vieweg & Sohn 2002, ISBN 3-528-16754-8, Seite 8 oben
  2. H.-D. Ebbinghaus, J. Flum, W. Thomas: Einführung in die mathematische Logik, Spektrum Akademischer Verlag 1996, ISBN 3-8274-0130-5, Kapitel XI, 4.2
  3. Wolfgang Rautenberg: Einführung in die mathematische Logik, Friedr. Vieweg & Sohn 2002, ISBN 3-528-16754-8, Kapitel 2, Satz 3.1