Prädikatenlogik/Elementare Äquivalenz für Elemente/Endlicher Fall/Textabschnitt

Aus Wikiversity
Zur Navigation springen Zur Suche springen

Inwiefern kann man die einzelnen Elemente in einer gegebenen -Struktur mit der durch gegebenen Sprache einzeln adressieren bzw. voneinander unterscheiden? Zur Präzisierung dieser Fragestellung dient das Konzept der elementaren Äquivalenz für Elemente.


Definition  

Es sei ein erststufiges Symbolalphabet und eine -Struktur. Wir nennen zwei Elemente elementar äquivalent, wenn für jeden Ausdruck in der einen freien Variablen und jede Variablenbelegung auf die Beziehung

gilt.

Die elementare Äquivalenz drücken wir durch aus. Dabei handelt es sich offenbar um eine Äquivalenzrelation auf der Menge . Wenn

ein -Isomorphismus (also ein Automorphismus) ist, der auf abbildet, so müssen die beiden Elemente elementar äquivalent sein, wie aus Fakt für eine beliebige Interpretation mit und folgt. Zu zwei nicht elementaar äquivalenten Elementen nennen wir einen Ausdruck mit und einen trennenden Ausdruck.


Beispiel  

Es sei ein Symbolalphabet, das neben Variablen aus einem einzigen einstelligen Funktionssymbol besteht und es sei eine -Struktur, wobei als die Permutation mit

interpretiert werde. Hier sind die Äquivalenzklassen zur elementaren Äquivalenz gleich der sogenannten Zykelzerlegung, nämlich gleich , und . Die Ordnung der Elemente kann man in der Sprache zu ausdrücken und erhält dadurch trennende Ausdrücke, beispielsweise ist ein Ausdruck in der einen freien Variablen , der genau dann wahr wird, wenn durch belegt wird. Der Ausdruck

ist ein Ausdruck, der genau dann wahr wird, wenn durch oder belegt wird, u.s.w. Dass oder zueinander elementar äquivalent sind, sieht man am einfachsten, wenn man den Automorphismus betrachtet, der durch die Transposition gegeben ist. Dieser ist nämlich ein -Automorphismus und daher können wir den Isomorphiesatz anwenden.



Beispiel  

Wenn man in der Definition auch Ausdrücke in mehreren freien Variablen zulassen würde, so wären Elemente nur mit sich selbst äquivalent. Betrachten wir dazu den Ausdruck , den wir nennen, und zwei Elemente aus . In der Interpretation sei durch belegt. Dann gilt , denn dies bedeutet , aber , denn dies bedeuet .


Für eine Konstante in , die in als das Element interpretiert wird, ist die zugehörige Äquivalenzklasse einelementig: Sie wird durch den Ausdruck in der einen freien Variablen charakterisiert, der offenbar nur bei der Belegung von durch wahr wird. Wir fragen uns, ob es für jede Äquivalenzklasse zur elementaren Äquivalenz einen solchen charakterisierenden Ausdruck in einer freien Variablen gibt.



Lemma  

Es sei ein Symbolalphabet erster Stufe und eine -Struktur mit der Eigenschaft, dass es in nur endlich viele Klassen zur elementaren Äquivalenz gibt.

Dann gibt es zu jeder Äquivalenzklasse einen -Ausdruck in einer freien Variablen , der die Klasse beschreibt, für den also

gilt.

Beweis  

Es seien die Äquivalenzklassen der elementaren Äquivalenzrelation und sei ein fest gewählter Repräsentant. Wir zeigen, dass es für einen solchen charakterisierenden Ausdruck gibt. Zu jedem gibt es einen Ausdruck in der freien Variablen mit , aber , da ja und nicht elementar äquivalent sind. Wir können annehmen, dass die relevante Variable in jedem dieser Ausdrücke die gleiche ist. Der konjugierte Ausdruck

ist in einer Interpretation (zur -Struktur ) genau dann wahr, wenn die Variable durch ein Element aus belegt wird.



Beispiel  

Für das Symbolalphabet und die natürlichen Zahlen mit der kanonischen Interpretation sind sämtliche Klassen zur elementaren Äquivalenz einelementig und können auch durch Ausdrücke charakterisiert werden, und zwar wird die Zahl durch den Ausdruck mit Strichen eindeutig beschrieben.



Beispiel  

Es sei das Symbolalphabet, das außer Variablen für jedes ein einstelliges Relationssymbol enthält, und es sei

Wir betrachten die Menge , wobei wir das Relationssymbol durch

interpretieren. Zwei Elemente

können dann nicht elementar äquivalent sein, da sie sich nicht gegenseitig teilen können und daher beispielsweise , also , aber nicht , also , gilt. Die Äquivalenzklassen sind also einelementig. Es ist aber nicht möglich, diese Klassen durch einen Ausdruck in dieser Sprache zu charakterisieren, da die Gültigkeitsmengen zu jedem Ausdruck entweder leer sind oder unendlich viele Elemente enthalten, siehe Aufgabe.




Lemma  

Es sei ein Symbolalphabet erster Stufe und eine -Struktur. Für jede elementare Äquivalenzklasse gebe es einen -Ausdruck in einer freien Variablen , der die Klasse beschreibt, für den also

gilt.

Dann gelten folgende Aussagen.

  1. Für jedes -stellige Relationssymbol ist auf den Äquivalenzklassen wohldefiniert.
  2. Für jedes -stellige Funktionssymbol ist auf den Äquivalenzklassen wohldefiniert (und zwar in dem Sinn, dass aus die elementare Äquivalenz folgt).

Beweis  

(1). Es sei ein -stelliges Relationssymbol. Für ein -Tupel aus mit und ein weiteres dazu elementar-äquivalentes Tupel (es gelte also ) müssen wir zeigen. Es seien Ausdrücke in der einen freien (untereinander verschiedenen) Variablen , die die Äquivalenzklassen zu bzw. charakterisieren. Es gilt

wie ja die Belegung von durch zeigt. Ebenso gilt

wie die entsprechende Belegung zeigt. Dies ist jetzt ein Ausdruck in der einen freien Variablen . Wenn man statt mit durch ein anderes elementar äquivalentes Element belegt, so erhält man nach Definition der elementaren Äquivalenz

und damit

Somit hat man den ersten Existenzquantor durch einen Allquantor ersetzt. In dieser Weise fährt man mit den anderen Existenzquantoren fort und erhält schließlich

Einsetzen von für liefert also, da ja auf zutrifft,

und somit .

(2). Die Aussage für Funktionssymbole wird ähnlich bewiesen, siehe Aufgabe.