Kurs:Einführung in die mathematische Logik (Osnabrück 2018)/Vorlesung 11

Aus Wikiversity
Wechseln zu: Navigation, Suche



Quantorenaxiome und -regeln

Wir besprechen nun die Tautologien und Ableitungsregeln, die mit den Quantoren zusammenhängen. Wir arbeiten allein mit dem Existenzquantor und wir arbeiten nur mit nichtleeren Grundmengen. Letzteres ist Voraussetzung dafür, dass es überhaupt eine Variablenbelegung geben kann. Bei den jetzt einzuführenden Axiomen handelt es sich um eine Tautologie (genauer gesagt um ein Schema von Tautologien), nämlich die Existenzeinführung im Sukzedens und um eine Schlussregel, nämlich die Existenzeinführung im Antezedens. Für letztere ist die exakte Formulierung und der Korrektheitsnachweis nicht trivial.


Axiom  

Es sei ein Symbolalphabet erster Stufe, ein -Ausdruck, eine Variable und ein -Term. Dann ist

Diese Tautologie bedeutet inhaltlich gesprochen, dass man bei einem Ausdruck, für den man einen erfüllenden Term gefunden hat, auf die entsprechende Existenzaussage schließen kann. Diese Tautologie ist allgemeingültig: Wenn in einer Interpretation die Beziehung

gilt, so ist dies nach dem Substitutionslemma äquivalent zu

und das bedeutet wiederum

Einen wichtigen Spezialfall dieser Tautologie erhält man für , nämlich (unabhängig davon, ob in vorkommt oder nicht)

Für den Allquantor (den wir als Abkürzung verstehen) ergibt sich die entsprechende Tautologie

Streng genommen ergibt sich diese Variante in dieser Form aber erst unter Verwendung der Existenzeinführung im Antezedens, siehe weiter unten und Aufgabe 12.17 und Aufgabe 11.1.


Axiom  

Es sei ein Symbolalphabet erster Stufe, und seien -Ausdrücke, und seien Variablen. Dann gilt die folgende Regel: Wenn

gilt und wenn weder in noch in frei vorkommt, so gilt auch

Ein Spezialfall dieser Ableitungsregel (bei ) ist, dass man aus unter der Bedingung, dass nicht frei in vorkommt, auf schließen kann.

Die Allvariante dieser Schlussregel ist die Alleinführung im Sukzedens. Sie besagt, dass man aus

unter der Bedingung, dass weder in noch in frei vorkommt, auf

schließen kann. Wir geben ein Beispiel für diese Version (mit ), wie sie in der mathematischen Praxis vorkommt.


Beispiel  

Nehmen wir an, wir möchten die Aussage beweisen, dass in einem jeden Monoid das neutrale Element eindeutig bestimmt ist. Wir formalisieren diese Aussage als

wobei die Konjunktion der zwei Monoidaxiome (also Assoziativität und Existenz des neutralen Elementes) und ist. In ist nicht gebunden, in schon. In einem mathematischen Beweis wird man sich dann ein „festes, aber beliebiges“ Monoid „denken“, und darin ein „festes, aber beliebiges“ . Für dieses beweist man dann die Aussage, dass wenn für alle gilt, dass dann sein muss. Im Beweis selbst wird nicht über quantifiziert, dies steckt gewissermaßen in der gewählten Beliebigkeit drin. Man beweist also eher[1] die Aussage

und betrachtet dies als einen Beweis für die oben notierte Version. Da in gar nicht oder allenfalls gebunden vorkommt, ist die Ableitbarkeit beider Versionen auch prädikatenlogisch gleichwertig. Insofern spiegelt sich in der Alleinführung im Sukzedens eine wichtiger Aspekt der mathematischen Praxis.


Die Existenzeinführung im Antezedens ist die einzige syntaktische Gesetzmäßigkeit, deren Korrektheit nicht unmittelbar klar ist.



Lemma  

Die Existenzeinführung im Antezedens ist eine korrekte Regel.

Beweis  

Es sei allgemeingültig, d.h.

für jede -Interpretation . Wir müssen zeigen, dass dann auch allgemeingültig ist (unter den gegebenen Voraussetzungen). Sei dazu eine Interpretation mit

Aufgrund der Modellbeziehung bedeutet dies, dass es ein (aus der Grundmenge der Interpretation) mit

gibt. Die Variable kommt nach Voraussetzung in nicht frei vor, d.h. bei , dass in nicht frei vorkommt. Wir können daher das Koinzidenzlemma anwenden und erhalten

Diese Aussage gilt trivialerweise auch bei . Damit gilt auch

Wir schreiben dies (etwas künstlich) als

Darauf können wir das Substitutionslemma (für die Interpretation und den Term ) anwenden und erhalten

Wegen der vorausgesetzten Allgemeingültigkeit von folgt

Da in nicht frei vorkommt, liefert das Koinzidenzlemma


Bemerkung  

Die Variablenbedingung in der Existenzeinführung im Antezedenz ist wesentlich. Das zeigt am besten die Betrachtung , wobei darin die Variable frei vorkommen möge (also z.B. , wobei ein einstelliges Relationssymbol sei). Dann ist natürlich

richtig, und die Variablenbedingung an , bezogen auf diesen Ausdruck, ist nicht erfüllt. Die Aussage

die man unter Missachtung dieser Variablenbedingung ableiten könnte, ist keine Tautologie. Aus der Existenz eines Elementes , das die Relation erfüllt, folgt ja keineswegs, dass die Relation für alle Elemente gilt. Diese Ableitungsregel lässt sich also insbesondere nicht durch eine interne Tautologie ersetzen.



Definition  

Ein Ausdruck heißt ableitbar im Prädikatenkalkül (oder eine syntaktische Tautologie), wenn er sich aus den Grundtautologien, also

durch sukzessive Anwendung der Ableitungsregeln Modus Ponens und der Existenzeinführung im Antezedens erhalten lässt. Die Ableitbarkeit wird durch

ausgedrückt.



Abgeleitete Regeln und weitere Tautologien

Bisher haben wir lediglich den Modus Ponens und die Existenzeinführung im Antezedens als Ableitungsregeln für den syntaktischen Kalkül zur Verfügung. Daraus ergeben sich allerdings sofort neue Ableitungsregeln, mit denen man neue Tautologien herleiten kann. Die Hinrichtung in der folgenden Aussage kommt häufig implizit in einer mathematischen Argumentation vor. Man beweist eine Aussage für beliebige, aber feste Elemente, und fasst dies als einen Beweis für die entsprechende Allaussage auf.



Lemma  

Es sei ein Symbolalphabet erster Stufe, ein -Ausdruck und eine Variable.

Dann ist genau dann, wenn ist.

Beweis  

Nach der Allquantorversion von Axiom 11.1 ist

also

Daher folgt aus

mittels Modus Ponens direkt


Sei umgekehrt gegeben. Es sei ein beliebiger Ausdruck, in dem nicht vorkomme. Nach Axiom 3.8  (2) und Modus Ponens ergibt sich

und

Auf diese beiden abgeleiteten Ausdrücke wird nun die Allquantorversion der Existenzeinführung im Antezedens (also die Alleinführung im Sukzedens) angewendet. Dies ist möglich, da in überhaupt nicht und in nicht frei vorkommt. Man erhält

und

Daraus ergibt sich mit der Fallunterscheidungsregel


Diese Aussage bedeutet aber keineswegs, dass man den Allquantor überall weglassen oder hinzufügen könnte. Sie bedeutet lediglich, dass bei einem Ausdruck, der als Ganzes als eine Tautologie erwiesen ist, auch der entsprechende Allausdruck eine Tautologie ist und umgekehrt. Semantisch betrachtet beruht diese Äquivalenz darauf, dass die Allgemeingültigkeit von bedeutet, dass bei einer beliebigen (Struktur- und) Variablenbelegung die entstehende Aussage ohne freie Variable wahr wird. Da ist also eine Allaussage schon miteingebunden. Insbesondere gilt nicht .

Für den Existenzquantor gilt die entsprechende Äquivalenz nicht. Zwar ergibt sich aus direkt (und zwar unabhängig davon, ob in vorkommt oder nicht; die Allgemeingültigkeit beruht darauf, dass nur nichtleere Grundmengen betrachtet werden), aber nicht umgekehrt. Beispielsweise ist

aber ist keine Tautologie.



Lemma  

Die folgenden Ausdrücke sind im Prädikatenkalkül ableitbar.

Beweis  

(1). Durch Existenzeinführung im Sukzedenz haben wir

und

und daraus

Dabei ist hinten gebunden und somit kann man mit der Existenzeinführung im Antezedens auf

schließen. Da auch hinten gebunden ist, ergibt sich


(2) wird ähnlich wie (1) bewiesen oder darauf zurückgeführt.


Für die (Nicht)-Vertauschbarkeit des Allquantors mit dem Existenzquantor siehe Aufgabe 11.21.



Lemma  

Die folgenden Ausdrücke sind im Prädikatenkalkül ableitbar.

Beweis  

(1). Aufgrund der Alleinführung im Antezedens ist

und

Dies konjugiert (unter Verwendung von Lemma 3.16  (2)) ergibt

Ferner haben wir die aussagenlogische Tautologie

Damit ergibt sich aufgrund der Transitivität der Implikation die Ableitung

Da vorne und in gebunden vorkommt, gilt nach der Alleinführung im Sukzedens auch


Zu (2) siehe Aufgabe 11.8 und Aufgabe 11.9.

(3). Aufgrund der Alleinführung im Antezedens ist

was wir als

schreiben. Wegen ist auch

was wir als

schreiben. Im Sukzedens ist gebunden, daher folgt aus der Existenzeinführung im Antezedens

was aussagenlogisch äquivalent zur Behauptung ist.

Zu (4) siehe Aufgabe 11.10.


Die folgende Aussage zeigt, dass man quantifizierte Aussagen im Wesentlichen mit beliebigen Variablen formulieren kann.



Lemma  

Es sei ein Ausdruck über einem erststufigen Symbolalphabet und seien Variablen. Die Variable komme in nicht und die Variable komme in allenfalls frei vor.

Dann ist

Beweis  

Nach Axiom 11.1, angewendet auf , ist

Da in gebunden vorkommt und in gar nicht, kann man Axiom 11.2 anwenden und erhält




Die Ableitungsbeziehung

Analog zur Folgerungsbeziehung definieren wir die Ableitungsbeziehung aus einer Ausdrucksmenge.


Definition  

Es sei ein Symbolalphabet, eine Menge an -Ausdrücken

und ein weiterer -Ausdruck. Man sagt, dass aus ableitbar ist, geschrieben
wenn es endlich viele Ausdrücke derart gibt, dass

gilt.

Man kann sich also wieder fragen, welche Ausdrücke aus einer vorgegebenen Ausdrucksmenge , beispielsweise einem Axiomensystem einer Sprache erster Stufe, ableitbar sind. Unser „unbedingter“ Prädikatenkalkül, der die syntaktischen Tautologien generiert, führt zu einem entsprechenden Regelsatz für die Ableitbarkeit aus . Dies ist näher an der mathematischen Praxis, da man sich dort in einem bestimmten mathematischen Kontext bewegt (z.B. der Gruppentheorie) und daher unter der Voraussetzung arbeitet, dass eine gewisse Ausdrucksmenge (z.B. die Gruppenaxiome) vorliegt, aus der heraus man etwas beweisen möchte.



Fußnoten
  1. Diese Unschärfe in der Begrifflichkeit ist kaum zu vermeiden, da eine formale Interpretation oder Rekonstruktion dessen, was in der mathematischen Praxis passiert, nie ganz eindeutig ist.


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

PDF-Version dieser Vorlesung

Arbeitsblatt zur Vorlesung (PDF)