Kurs:Einführung in die mathematische Logik (Osnabrück 2014)/Vorlesung 9

Aus Wikiversity
Zur Navigation springen Zur Suche springen



Freie Variablen

In einem Ausdruck über einem Symbolalphabet nennt man die Variablen, die (und zwar für jedes Vorkommen) innerhalb der Reichweite eines Quantors stehen, gebunden, die anderen frei. Dies wird streng über den Aufbau der Ausdrücke definiert.

  1. für ein -stelliges Relationssymbol und Terme .

  2. für einen Ausdruck .

  3. für Ausdrücke und . Ebenso für .

  4. für einen Ausdruck und eine Variable .

  5. für einen Ausdruck und eine Variable .

Einen Ausdruck ohne freie Variablen nennt man einen Satz, auch wenn diese Bezeichnung nicht ganz glücklich ist, da „Satz“ die Gültigkeit einer Aussage suggeriert. Die Menge der Sätze wird mit bezeichnet, die Menge der Ausdrücke mit genau einer freien Variablen (die aber in dem Ausdruck beliebig oft vorkommen darf) mit .



Das Koinzidenzlemma

Die folgende Aussage, das Koinzidenzlemma, zeigt, dass der Wert eines Terms und die Gültigkeit eines Ausdrucks unter einer Interpretation (bei einer fixierten -Struktur) nur von den in dem Term vorkommenden Variablen bzw. in dem Ausdruck vorkommenden freien Variablen abhängt. Ihr Beweis ist ein typisches Beispiel für einen Beweis durch Induktion über den Aufbau der Terme bzw. Ausdrücke.



Lemma  

Es sei ein Symbolalphabet erster Stufe und eine Teilmenge. Es sei ein -Term und ein -Ausdruck. Es seien zwei -Interpretationen und in einer gemeinsamen Grundmenge gegeben, die auf identisch seien. Dann gelten folgende Aussagen.

  1. Es ist .
  2. Es ist genau dann, wenn (dazu genügt bereits, dass die Interpretationen auf den Symbolen aus und auf den in frei vorkommenden Variablen identisch sind).

Beweis  

(1). Wir führen Induktion über den Aufbau der -Terme. Für den Induktionsanfang müssen wir Variablen und Konstanten aus betrachten. Für eine Variable (oder eine Konstante) aus ist nach Voraussetzung . Im Induktionsschritt können wir annehmen, dass ein -stelliges Funktionssymbol aus gegeben ist sowie -Terme , für die die Interpretationsgleichheit schon gezeigt wurde. Nach Voraussetzung wird in beiden Interpretationen durch die gleiche Funktion interpretiert. Daher ist


(2). Wir führen Induktion über den Aufbau der -Ausdrücke, wobei die zu beweisende Aussage über je zwei Interpretationen zu verstehen ist. Für die Gleichheit und ein Relationssymbol aus folgt die Aussage unmittelbar aus (1), da ja in beiden Interpretationen als die gleiche Relation zu interpretieren ist. Der Induktionsschritt ist für Ausdrücke der Form aufgrund der Modellbeziehung unmittelbar klar. Sei nun ein -Ausdruck der Form gegeben, und es gelte . Dies bedeutet aufgrund der Modellbeziehung, dass es ein derart gibt, dass gilt. Die beiden umbelegten Interpretationen und stimmen auf den Symbolen aus und den in frei vorkommenden Variablen überein: Die Variable wird so oder so als interpretiert und die anderen freien Variablen aus sind auch in frei. Nach Induktionsvoraussetzung gilt und daher wiederum .




Substitution

Wir besprechen nun die Variablensubstitution, wobei wir weitgehend der Darstellung von Ebbinghaus, Flum, Thomas folgen.

Variablen repräsentieren verschiedene Werte, die man für sie einsetzen kann. Auf formaler Ebene bedeutet dies, dass eine oder mehrere Variablen durch gewisse Terme ersetzt werden. Im semantischen Kontext wird dies durch die Uminterpretation von Variablen bei einer Interpretation präzise gemacht. Im syntaktischen Kontext spricht man von Substitution, die wir nun definienren werden. In der Ersetzung macht es einen großen Unterschied, ob gebundene oder freie Variablen vorliegen. Der Ausdruck

bedeutet in einem angeordneten Körper interpretiert, dass die nichtnegative Zahl als Quadrat darstellbar ist (also eine Quadratwurzel besitzt), was für wahr ist, für im Allgemeinen (das hängt von der Interpretation für ab) nicht. Gleichbedeutend (bei einer inhaltlichen Interpretation) mit diesem Ausdruck ist

aber nicht

das nur bei oder wahr ist. Von daher wird die weiter unten zu gebende Definition für die Substitution von Ausdrücken berücksichtigen, ob Variablen frei oder gebunden sind. Ferner wird es wichtig sein, in einem Ausdruck neue Variablen einzuführen. Damit diese Konstruktion eindeutig definiert ist, legen wir entweder eine durchnummerierte (und abzählbare) Variablenmenge zugrunde, oder aber eine beliebig große Variablenmenge, die mit einer Wohlordnung versehen sei.


Definition  

Es sei ein Symbolalphabet einer Sprache erster Stufe gegeben. Es seien paarweise verschiedene Variablen und fixierte -Terme. Dann definiert man rekursiv über den Aufbau der Terme die Substitution für jeden -Term .

  1. Für eine Variable ist
  2. Für eine Konstante ist
  3. Für ein -stelliges Funktionssymbol und Terme ist

Beispiel  

Es seien Konstanten einer erststufigen Sprache, Variablen, ein einstelliges und zweistellige Funktionssymbole. Wir betrachten den Term

und die Substitution

Die Substitution wird durchgeführt, indem man die kleinsten Bestandteile des Termes, also , ersetzt und ansonsten den funktionalen Aufbau des Termes übernimmt. Für diese gilt

und

Also ist

Man beachte, dass das letzte nicht zu ersetzen ist.



Definition  

Es sei ein Symbolalphabet einer Sprache erster Stufe gegeben. Es seien paarweise verschiedene Variablen und fixierte -Terme. Dann definiert man rekursiv über den Aufbau der -Ausdrücke die Substitution für jeden -Ausdruck .

  1. Für Terme setzt man[1]
  2. Für ein -stelliges Relationssymbol und Terme setzt man
  3. Für einen Ausdruck setzt man
  4. Für Ausdrücke und setzt man

    und ebenso für die anderen zweistelligen Junktoren.

  5. Für einen Ausdruck seien diejenigen Variablen (unter den ), die in frei vorkommen. Es sei , falls nicht in vorkommt. Andernfalls sei die erste Variable (in einer fixierten Variablenaufzählung, falls es abzählbar viele Variablen gibt, bzw. in einer fixierten Wohlordnung der Variablenmenge), die weder in noch in vorkommt. Dann setzt man

    und ebenso für den Existenzquantor.


Beispiel  

Es seien Konstanten einer erststufigen Sprache, Variablen (so geordnet), einstellige Funktionssymbole und ein zweistelliges Relationssymbol. Wir betrachten den Ausdruck

und die Substitution

Von den zu substituierenden Variablen ist gebunden und frei. Die Variable kommt in den substituierenden Termen nicht vor. Also ist

Bei der Substitution

kommt jetzt die gebundene Variable in dem substituierenden Term vor. Es ist die nächste Variable in der gegebenen Reihenfolge. Somit ist


Die folgende Aussage, das Substitutionslemma, stiftet eine Beziehung zwischen Substitutionen und Uminterpretationen.

In Verallgemeinerung der Schreibweise für eine Uminterpretation schreiben wir für die sukzessive Uminterpretation der untereinander verschiedenen Variablen (dabei seien Elemente der Grundmenge der Interpretation). Es werden also die als interpretiert und alle anderen Variablen werden gemäß interpretiert.



Lemma  

Es sei ein Symbolalphabet einer Sprache erster Stufe gegeben und es seien paarweise verschiedene Variablen und fixierte -Terme. Es sei eine -Interpretation gegeben. Dann gelten folgende Aussagen.

  1. Für jeden -Term gilt
  2. Für jeden -Ausdruck gilt

Beweis  

Dies wird über den induktiven Aufbau der Terme bzw. der Ausdrücke bewiesen. (1). Für eine Konstante ist die Aussage richtig, da ihre Interpretation unverändert ist. Für eine Variable macht man eine Fallunterscheidung. Wenn

mit einer der an der Substitution beteiligten Variablen ist, so ist

Bei einer an der Substitution nicht beteiligten Variablen ist

Wenn ein -stelliges Funktionssymbol ist und Terme sind, für die die Gleichheit schon bekannt ist, so ist

Fehler beim Parsen (Unbekannte Funktion „\begin{align}“): {\displaystyle {{}} \begin{align} I { \left( { \left( f s_1 \ldots s_n \right) } \frac{ t_1 , \ldots , t_k }{ x_1 , \ldots , x_k } \right) } & = I { \left( f s_1 \frac{ t_1 , \ldots , t_k }{ x_1 , \ldots , x_k } \ldots s_n \frac{ t_1 , \ldots , t_k }{ x_1 , \ldots , x_k } \right) } \\ & = I(f) { \left( I { \left( s_1 \frac{ }{ } \right) } , \ldots , I { \left( s_n \frac{ }{ } \right) } \right) } \\ & = I(f) { \left( { \left( I \frac{ I(t_1) {{<span class="error">Expansion depth limit exceeded</span>}} I(t_k) }{ x_1 {{<span class="error">Expansion depth limit exceeded</span>}} x_k } \right) } (s_1) , \ldots , { \left( I \frac{ I(t_1) {{<span class="error">Expansion depth limit exceeded</span>}} I(t_k) }{ x_1 {{<span class="error">Expansion depth limit exceeded</span>}} x_k } \right) } (s_n) \right) } \\ & = { \left(I \frac{ I(t_1) , \ldots , I(t_k) }{ x_1 , \ldots , x_k } \right) } (f) { \left( { \left(I \frac{ I(t_1) {{<span class="error">Expansion depth limit exceeded</span>}} I(t_k) }{ x_1 {{<span class="error">Expansion depth limit exceeded</span>}} x_k } \right) } { \left( s_1 \right) } , \ldots , { \left(I \frac{ I(t_1) {{<span class="error">Expansion depth limit exceeded</span>}} I(t_k) }{ x_1 {{<span class="error">Expansion depth limit exceeded</span>}} x_k } \right) } { \left( s_n \right) } \right) } \\ & = { \left(I \frac{ I(t_1) , \ldots , I(t_k) }{ x_1 , \ldots , x_k } \right) } { \left( f s_1 \ldots s_n \right) } . \end{align} }

(2). Für einen Ausdruck der Form bedeutet

einfach

Dies ist äquivalent zu

was nach dem ersten Teil einfach

bedeutet. Dies wiederum ist äquivalent zu

Sei nun ein -stelliges Relationssymbol und seien Terme. Die Gültigkeit

bedeutet

und dies bedeutet, dass

Fehler beim Parsen (Syntaxfehler): {\displaystyle { \left( I { \left( s_1 \frac{ t_1 {{<span class="error">Expansion depth limit exceeded</span>|}} t_ }{ x_1 {{<span class="error">Expansion depth limit exceeded</span>|}} x_ } \right) } , \ldots, I { \left( s_n \frac{ t_1 {{<span class="error">Expansion depth limit exceeded</span>|}} t_ }{ x_1 {{<span class="error">Expansion depth limit exceeded</span>|}} x_ } \right) } \right) } }

zur Relation gehört. Nach dem ersten Teil ist dieses Tupel gleich

Wegen ist dies äquivalent zu

Für die weiteren Aussagen beweist man die Äquivalenz durch Induktion über den Aufbau der Ausdrücke, und zwar über alle Interpretationen simultan; dies ist für die aussagenlogischen Junktoren unmittelbar klar. Betrachten wir also einen Ausdruck der Form . Die Gültigkeit

bedeutet gemäß der Festlegung in Definition 9.4, dass

gilt, wobei in nicht vorkommt. Dies bedeutet, dass für jedes der Grundmenge der Interpretation die Beziehung

gilt. Nach Induktionsvoraussetzung (angewendet auf die Interpretation ) bedeutet dies

für alle . Aufgrund des Koinzidenzlemmas ist dies äquivalent zu

Dies ist äquivalent (für alle ) zu

was bei klar ist und bei aus dem Koinzidenzlemma folgt, da dann nicht in vorkommt. Dies bedeutet wiederum

und damit





Fußnoten
  1. Die Klammern unterstreichen hier lediglich den Gesamtausdruck, für den die Substitution durchgeführt wird


<< | Kurs:Einführung in die mathematische Logik (Osnabrück 2014) | >>

PDF-Version dieser Vorlesung

Arbeitsblatt zur Vorlesung (PDF)