Koinzidenzlemma

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

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 $p_{1},p_{2},\ldots$ und den booleschen Operationen $\land ,\lor$ und $\neg$ aufgebaut, zum Beispiel $p_{1}\land (p_{2}\lor \neg p_{3}\lor p_{7})\land \neg p_{2}$. Eine Belegung ist eine Abbildung $b$, die jeder Variablen einen der beiden Wahrheitswerte wahr oder falsch zuordnet, woraus dann der Wahrheitswert der Aussage ermittelt werden kann. Ist $\alpha$ eine solche Aussage, schreibt man $b\vDash \alpha$, wenn $\alpha$ durch die Belegung $b$ wahr wird. Formal lässt sich das Koinzidenzlemma nun wie folgt ausdrücken:

• Seien b und b' zwei Belegungen und sei $\alpha$ eine Aussage. Ist $b(p_{i})=b'(p_{i})$ für alle in $\alpha$ vorkommenden Aussagenvariablen, so gilt:

$b\vDash \alpha$ genau dann, wenn $b'\vDash \alpha$.

Prädikatenlogik

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 $S=\{0,1,+,\cdot ,<\}$ zur Bildung von Formeln in der Ring- oder Körpertheorie mit einer Anordnung. Ein Beispiel für eine typische Aussage ist

$\forall b\,\forall c\,(\neg a=0\rightarrow \exists x\,(a\cdot x+b=c))$,

die die Lösbarkeit linearer Gleichungen behauptet, wobei die Variable $a$ frei ist, das heißt noch nicht festgelegt ist. Die Interpretation dieser Formel im Ring $\mathbb {Z}$, das heißt die Konstantensymbole 0 und 1 werden als die ganzen Zahlen 0 und 1 interpretiert, die Funktionssymbole $+,\cdot$ als Addition und Multiplikation und < schließlich als die übliche Größer-Relation, ist bekanntlich falsch, außer wenn $a$ durch +1 oder −1 interpretiert wird. Eine analoge Interpretation im Körper $\mathbb {Q}$ hingegen führt bei jeder Interpretation von $a$ 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 $\alpha$ eine Formel und $M,M\,'$ seien zwei Modelle über derselben Menge. Stimmen die Interpretationen der in $\alpha$ frei vorkommenden Variablen und die Interpretationen sämtlicher in $\alpha$ vorkommenden nicht-logischen Symbole überein, so gilt:

$M\vDash \alpha$ genau dann, wenn $M\,'\vDash \alpha$.

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 $S$ um weitere Symbole, die man zu irgendwelchen Zwecken einsetzen möchte. Der Wahrheitsgehalt der mittels der Symbolmenge $S$ aufgebauten Formeln bleibt davon nach dem Koinzidenzlemma unberührt.