Kurs:Einführung in die mathematische Logik (Osnabrück 2011-2012)/Vorlesung 5

Aus Wikiversity
Zur Navigation springen Zur Suche springen



Weitere Axiomensysteme

In der letzten Vorlesung haben wir gesehen, wie man die Gruppenaxiome in der Prädikatenlogik erster Stufe formulieren kann. Eine Gruppe im herkömmlichen mathematischen Sinn ist prädikatenlogisch formuliert eine Menge zusammen mit einer Interpretation für eine Konstante und ein zweistelliges Funktionssymbol (nämlich ein ausgezeichnetes Element und eine Verknüpfung), unter der gemäß der Modellbeziehung die Gruppenaxiome gültig sind.

Wir geben ein weiteres Beispiel, das die Beziehung zwischen mathematischer und prädikatenlogischer Formulierung deutlich machen soll.


Definition  

Eine Relation auf einer Menge heißt Ordnungsrelation oder Ordnung, wenn folgende drei Bedingungen erfüllt sind.

  1. Es ist für alle .
  2. Aus und folgt stets .
  3. Aus und folgt .

Neben den Variablen besteht das zugehörige Symbolalphabet allein aus einem zweistelligen Relationssymbol, das wir ebenfalls mit bezeichnen. Die für eine Ordnung verlangten Eigenschaften führen zu dem folgenden einstufigen Axiomensystem .

In einer Menge mit einer zweistelligen Relation gilt das Axiomensystem genau dann, wenn die Relation eine Ordnungsrelation ist.



Die Folgerungsbeziehung

Mit Axiomensystemen verbindet man die Vorstellung, dass daraus „wichtige“ weitere Eigenschaften beweisbar sind. In einer jeden Gruppe gelten nicht nur die Gruppenaxiome, sondern auch alle Gesetzmäßigkeiten, die man aus den Gruppenaxiomen folgern kann. Dies wird in der mathematischen Logik durch den Folgerungsbegriff präzisiert.


Definition  

Es sei ein Symbolalphabet erster Stufe, eine Menge von -Ausdrücken und ein -Ausdruck. Man sagt, dass aus folgt, geschrieben , wenn für jede -Interpretation mit auch gilt.

Die Folgerungsbeziehung verwendet also das gleiche Symbol wie die Gültigkeitsbeziehung. Dass aus einer gewissen Ausdrucksmenge ein gewisser Audruck folgt, erfordert eine mathematische Argumentation, die aufzeigt, dass eine Menge mit zusätzlichen Strukturen, die erfüllt, stets auch erfüllen muss.


Beispiel  

In einer Gruppe ist das neutrale Element, das es aufgrund der Definition einer Gruppe geben muss, eindeutig bestimmt. Mathematisch wird dies so bewiesen: Sei das neutrale Element der Gruppe, und sei ein weiteres Element, das ebenfalls die Eigenschaft des neutralen Elements erfüllt, d.h. es gilt für alle . Dann gilt einerseits , da neutrales Element ist, und andererseits , da auch neutrales Element ist. Also ist insgesamt und und stimmen überein.

Die Eindeutigkeit des neutralen Elementes kann man als den Ausdruck

ansetzen, und die obige mathematische Argumentation bedeutet, dass der Ausdruck aus den Gruppenaxiomen folgt, also die Folgerungsbeziehung

vorliegt.




Allgemeingültige Ausdrücke

Definition  

Es sei ein Symbolalphabet und ein -Ausdruck in der Prädikatenlogik erster Stufe. Man nennt allgemeingültig (oder eine semantische Tautologie), wenn er in jeder -Interpretation gilt, also wahr ist.

Allgemeingültige Ausdrücke sind Tautologien im semantischen Sinn. Wir werden später noch Tautologien im syntaktischen Sinn kennenlernen und die Übereinstimmung der beiden Konzepte zeigen. Da ein allgemeingültiger Ausdruck in jeder Interpretation gilt, kann man auch sagen, dass aus der leeren Ausdrucksmenge folgt, also gilt. Beispiele sind die Ausdrücke

oder

(wobei ein Ausdruck ist). Wenn die Gruppenaxiome sind, und die im obigen Beispiel erwähnte Eindeutigkeitsausssage für das neutrale Element ist, so ist auch

allgemeingültig.


Definition  

Es sei ein Symbolalphabet und es sei ein -Ausdruck in der Prädikatenlogik erster Stufe. Man nennt erfüllbar, wenn es eine -Interpretation mit gibt.

Für eine Ausdrucksmenge bedeutet die Erfüllbarkeit, dass die darin enthaltenen Ausdrücke simultan in einer Interpretation erfüllbar sind. Zwischen Allgemeingültigkeit und Erfüllbarkeit besteht die Beziehung, dass genau dann allgemeingültig ist, wenn die Negation nicht erfüllbar ist.

Zwischen Folgerung und Erfüllbarkeit besteht der folgende Zusammenhang.


Lemma

Es gilt genau dann, wenn nicht erfüllbar ist.

Beweis

Siehe Aufgabe 5.4.




Das Koinzidenzlemma

Die folgende Aussage, das Koinzidenzlemma, zeigt, dass der Wert eines Terms und die Gültigkeit eines Ausdrucks unter einer Interpretation nur von den in dem Term bzw. 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. 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 eine durchnummerierte (und abzählbare) Variablenmenge zugrunde.


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

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
  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.

Die folgende Aussage, das Substitutionslemma, geben wir ohne Beweis. Es 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



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

PDF-Version dieser Vorlesung

Arbeitsblatt zur Vorlesung (PDF)