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

Aus Wikiversity



Peano-Axiome

Wir besprechen nun, inwiefern man die natürlichen Zahlen axiomatisieren kann, und was davon erststufig durchführbar ist. Dazu diskutieren wir die Peano-Axiome, wobei wir mit der zweitstufigen Version beginnen.


Axiom  

Eine Menge mit einem ausgezeichneten Element (die Null) und einer (Nachfolger)-Abbildung

heißt natürliche Zahlen (oder Dedekind-Peano-Modell für die natürlichen Zahlen), wenn die folgenden Dedekind-Peano-Axiome erfüllt sind.

  1. Das Element ist kein Nachfolger (die Null liegt also nicht im Bild der Nachfolgerabbildung).
  2. Jedes ist Nachfolger höchstens eines Elementes (d.h. die Nachfolgerabbildung ist injektiv).
  3. Für jede Teilmenge gilt: Wenn die beiden Eigenschaften
      • ,
      • mit jedem Element
      ist auch ,

    gelten, so ist .

    Mit zweitstufig ist gemeint, dass nicht nur über die Elemente der Menge , die man axiomatisch charakterisieren will, quantifiziert wird, sondern auch über beliebige Teilmengen dieser Menge. Mit dieser Axiomatik lassen sich ausgehend von der Nachfolgerfunktion die Addition und die Multiplikation rekursiv einführen, und es lässt sich zeigen, dass je zwei Modelle für diese zweistufigen Peano-Axiome „isomorph“ sind, dass es also zwischen ihnen eine strukturerhaltende Bijektion gibt. Das im Wesentlichen eindeutig bestimmte Modell für diese Arithmetik bezeichnen wir mit .

    Wir betrachten zwei erststufige Varianten. Dabei wird die Nachfolgerfunktion beibehalten und das Induktionsaxiom, das oben für beliebige Teilmengen formuliert war, wird durch ein Induktionsaxiom für die in der Sprache formulierbaren Ausdrücke ersetzt. Das Induktionsaxiom gilt somit lediglich für Teilmengen, die in der gegebenen Sprache charakterisierbar sind.


    Axiom  

    Die Peano-Axiome für die Nachfolgerfunktion in der ersten Stufe werden (in der Sprache zur Symbolmenge mit einer Konstanten und einem einstelligen Funktionssymbol ) folgendermaßen definiert.

    1. .
    2. .
    3. Für jeden Ausdruck von mit einer freien Variablen gilt

    Aus der obigen zweitstufigen Formulierung der Axiomatik, die nur die Nachfolgerabbildung verwendet, kann man in jedem Modell in eindeutiger Weise eine Addition und eine Multiplikation definieren. Dafür ist das obige erststufige Axiomensystem zu schwach. Stattdessen werden wir unter der Peano-Arithmetik das folgende Axiomensystem verstehen, das mit zwei Konstanten und und zwei zweistelligen Operationen und auskommt. Die Nachfolgerfunktion ist dann durch definiert und es braucht dafür kein eigenes Funktionssymbol.


    Axiom  

    Die Peano-Axiome für Addition und Multiplikation in der ersten Stufe werden (in der Sprache zur Symbolmenge mit den beiden Konstanten und und zwei zweistelligen Funktionssymbolen und ) folgendermaßen definiert.

    1. .
    2. .
    3. .
    4. .
    5. .
    6. .
    7. Für jeden Ausdruck von mit einer freien Variablen gilt

    Die Axiome und entsprechen dabei direkt den Nachfolgeraxiomen von oben. Die Axiome und spiegeln die Grundregeln in der zweistufigen Peano-Arithmetik für die rekursive Definition der Addition wider, und die Axiome und entsprechen den Grundregeln für die rekursive Definition der Multiplikation. Bekanntlich gelten diese Axiome für die natürlichen Zahlen. Anders als bei der obigen zweitstufigen Axiomatik gibt es aber von verschiedene Modelle (nicht Standard-Arithmetiken), die die erststufige Peano-Arithmetik erfüllen. Dies ist aber kein „zufälliges“ Defizit der gewählten Axiomatik, sondern dahinter verbirgt sich eine grundsätzliche Schwäche der Sprache erster Stufe, die durch die Gödelschen Unvollständigkeitssätze präzisiert werden wird.



    Kalkül der Prädikatenlogik

    Gegeben sei ein Symbolalphabet einer Sprache erster Stufe und damit die zugehörige Termmenge und die zugehörige Ausdrucksmenge. Wir möchten die logisch wahren Aussagen einer solchen Sprache syntaktisch charakterisieren. Mathematische Aussagen sind im Allgemeinen „wenn-dann“-Aussagen, d.h. sie behaupten, dass, wenn gewisse Voraussetzungen erfüllt sind, dann auch eine gewisse Folgerung erfüllt ist.

    Wenn man einen Beweis eines Satzes der Gruppentheorie oder der elementaren Arithmetik entwirft, so sind dabei die Axiome der Gruppentheorie bzw. die Peano-Axiome stets präsent. Wenn die Gruppenaxiome bezeichnen und die Aussage, dass das neutrale Element eindeutig bestimmt ist, bezeichnet, so folgt aus . Mit der Folgerungsbeziehung kann man dies als

    formulieren. Dies kann man auch so ausdrücken, dass

    allgemeingültig ist, also dass

    gilt. So kann man jede Folgerung aus einer endlichen Ausdrucksmenge „internalisieren“, also durch einen allgemeingültigen Ausdruck der Form

    wiedergegeben, wobei vorne die Ausdrücke aus konjugiert werden. Die Folgerungsbeziehung (zumindest aus endlichen Ausdrucksmengen) kann also vollständig durch allgemeingültige Ausdrücke verstanden werden.

    Wir besprechen nun die syntaktische Variante der allgemeingültigen Ausdrücke, nämlich die syntaktischen prädikatenlogischen Tautologien. Über den soeben besprochenen Zusammenhang ergibt sich daraus auch ein Ableitungskalkül, der das syntaktische Analogon zur Folgerungsbeziehung ist. Da wir Ausdrücke der Form als Grundtyp für eine mathematische Aussage ansehen, arbeiten wir allein mit den Junktoren und lesen und als Abkürzungen. Man könnte auch noch bzw. eliminieren und durch die verbleibenden beiden Junktoren ausdrücken, doch würde dies zu recht unleserlichen Formulierungen führen.

    Der prädikatenlogische Kalkül, den wir vorstellen wollen, soll es erlauben, „alle“ prädikatenlogischen allgemeingültigen Ausdrücke formal abzuleiten. Der Aufbau dieses Kalküls geschieht wiederum rekursiv (und für beliebige Symbolalphabete gleichzeitig). D.h. man hat eine Reihe von Anfangstautologien (oder Grundtautologien) und gewisse Schlussregeln, um aus schon nachgewiesenen Tautologien neue zu produzieren. Sowohl die Anfangstautologien als auch die Schlussregeln sind aus der mathematischen Beweispraxis vertraut.

    Zur Formulierung dieses Kalküls verwenden wir die Schreibweise

    Sie bedeutet, dass der Ausdruck in der Prädikatenlogik (erster Stufe zu einem gegebenen Alphabet) ableitbar ist, also eine Tautologie (im syntaktischen Sinne) ist.



    Aussagenlogische Tautologien

    In den folgenden aussagenlogischen Tautologien sind und beliebige Ausdrücke. Um Klammern zu sparen verwenden wir die Konvention, dass die Negation sich auf das folgende Zeichen bezieht und dass die Konjunktion stärker bindet als die Implikation.


    Axiom  

    Für eine Aussagenvariablenmenge und beliebige Ausdrücke legt man folgende (syntaktische) Tautologien axiomatisch fest.

    1. und

    Diese Tautologien sind also die Startglieder. Dabei stehen für beliebige Ausdrücke der Prädikatenlogik erster Stufe (in der Aussagenlogik werden diese Tautologien einfach mit Aussagenvariablen formuliert). Das Axiom (3) besagt die Transitivität der Implikation, Axiom (5) heißt Widerspruchsaxiom und Axiom (6) heißt Fallunterscheidungsaxiom.

    Um überhaupt aus diesen Axiomen weitere Tautologien generieren zu können, braucht man Ableitungsregeln. Davon gibt es lediglich eine.

    Modus ponens

    Aus und folgt .

    Wir wollen uns nicht lange an aussagenlogischen Tautologien aufhalten. Eine Durchsicht der angeführten Tautologien zeigt, dass es sich auch um semantische Tautologien, also allgemeingültige Ausdrücke, handelt.

    Bemerkung  

    Die aussagenlogischen Axiome der Form führen zu entsprechenden Schlussregeln, d.h. Vorschriften, wie man aus (schon etablierten) syntaktischen Tautologien neue Tautologien erhält. Wir gehen unter diesem Gesichtspunkt die Axiome durch.

    Aus folgt .

    Dies ergibt sich aus der Voraussetzung aus und dem Modus ponens.

    Aus folgt (und ebenso ).

    Dies ergibt sich aus nach Fakt ***** und der Voraussetzung mittels Modus ponens. Umgekehrt gilt die sogenannte Konjunktionsregel, d.h. aus und folgt auch . Dies ergibt sich aus

    (was aus den Axiomen folgt, siehe Aufgabe 6.5) aus den Voraussetzungen durch eine zweifache Anwendung des Modus ponens.

    Aus und ergibt sich . Diese Regel heißt Kettenschlussregel. Nach der obigen abgeleiteten Konjunktionsregel folgt aus den Voraussetzungen direkt und daraus und dem Kettenschlussaxiom mit dem Modus ponens .




    Lemma  

    Es ist

    Beweis  

    Nach Axiom 6.4  (3) ist

    Die beiden Bestandteile des Vordersatzes gelten nach Fakt *****, so dass auch ihre Konjunktion ableitbar ist. Daher ist auch der Nachsatz ableitbar.



    Lemma  

    Beweis  

    1. Nach Axiom 6.4  (2) ist

      und daher mit Axiom 6.4  (4) auch

      Der Vordersatz ist nach Fakt ***** ableitbar, also auch der Nachsatz.

    2. Nach Teil (1) ist

      und (unter Verwendung von Fakt ***** und Aufgabe *****)

      Daher gilt auch (nach der Regelversion zu Teil (1))

      und

      bzw. unter Verwendung von Axiom 6.4  (4) und der Assoziativität der Konjunktion

      und

      Nach Axiom 6.4  (3) ist mit der Abkürzung

      Da die beiden Teilaussagen im Vordersatz ableitbar sind, ist auch der Nachsatz ableitbar, was unter Verwendung von Axiom 6.4  (4) zur Behauptung umformulierbar ist.


    Die folgende Aussage gibt eine „interne Version“ des Modus Ponens, der ja nach Definition eine Schlussregel ist.


    Lemma  

    Es ist

    Beweis  

    Nach Axiom 6.4  (6) ist

    und Axiom 6.4  (5) kann man wegen Axiom 6.4  (4) zu

    umformulieren. Daraus und aus (Fakt *****)

    ergibt sich mit der Regelversion zu Lemma 6.7  (2)

    und daraus durch den Kettenschluss die Behauptung.



    Lemma  

    1. Aus und folgt .
    2. Aus und ergibt sich .

    Beweis  

    1. Sei

      und

      Nach Bemerkung ***** gilt auch

      und daraus ergibt sich mit Axiom 6.4  (3), der Konjunktionsregel und dem Modus ponens

      Mittels des Kettenschlusses ergibt sich daraus und aus Axiom 6.4  (2) die Behauptung.

    2. Siehe Aufgabe 6.8.


    Die folgenden Tautologien machen wichtige Aussagen über das Negationszeichen. Die Tautologie (2) ist eine wichtige Variante der Widerspruchstautologie und die Tautologie (5) heißt Kontraposition.


    Lemma  

    Beweis  

    1. Die Fallunterscheidungstautologie liefert

      Aus (Fakt *****)

      ergibt sich daraus die Behauptung.

    2. Nach Axiom 6.4  (3) gilt

      und nach Axiom 6.4  (5) gilt

      Nach Lemma 6.8  (1) folgt

      woraus nach Teil (1) die Behauptung mit der Kettenschlussregel folgt.

    3. Nach Axiom 6.4  (1) ist

      Nach Axiom 6.4  (5) ist

      was wir mit Axiom 6.4  (4) zu

      umformulieren können. Daraus ergibt sich

      mit der Fallunterscheidungsregel.

    4. Nach Axiom 6.4  (1) ist

      Nach Axiom 6.4  (5) ist

      was wir zu

      umformulieren können. Daraus ergibt sich

      mit der Fallunterscheidungsregel.

    5. Es ist nach Axiom 6.4  (1)

      und damit auch

      Ferner ist nach einer Variante von Axiom 6.4  (5)

      Nach Lemma 6.7 ist

      woraus sich

      ergibt. Mit der Fallunterscheidungsregel folgt die Behauptung.

    6. Dies folgt aus (3), (4) und (5).




    Gleichheitstautologien

    Es gelten die beiden folgenden Tautologien für die Gleichheit.


    Axiom  

    Es sei ein Symbolalphabet, seien - Terme und sei ein - Ausdruck. Dann sind die beiden folgenden Ausdrücke syntaktische Tautologien.

    Diese beiden Axiome heißen Gleichheitsaxiom und Substitutionsaxiom.

    In der folgenden Aussage wird ein wichtiger Begriff für eine syntaktische Tautologie, eine Ableitungsregel oder einen ganzen formalen Kalkül verwendet, den der Korrektheit. Er besagt, dass die Tautologie auch (im semantischen Sinn) allgemeingültig ist bzw. dass der Kalkül nur wahre Aussagen liefert. Die weiter oben axiomatisch formulierten aussagenlogischen Tautologien sind korrekt, d.h. sie (und auch jede weitere daraus mittels Modus Ponens ableitbare Tautologie) sind allgemeingültig, wie eine direkte Durchsicht zeigt. Die folgende Aussage zeigt, dass auch die eben postulierten Gleichheitsaxiome allgemeingültig sind und dass der Kalkül daher korrekt ist.



    Lemma  

    Beweis  

    Es sei eine beliebige - Interpretation. (1). Aufgrund der Bedeutung des Gleichheitszeichens unter jeder Interpretation gilt , also


    (2). Es gelte

    also und . Das bedeutet einerseits . Andererseits gilt nach dem Substitutionslemma

    Wegen der Termgleichheit gilt somit auch

    und daher, wiederum aufgrund des Substitutionslemmas, auch




    Korollar  

    Aus den Gleichheitsaxiomen lassen sich folgende Gleichheitstautologien ableiten (dabei sind Terme, ein -stelliges Funktionssymbol und ein -stelliges Relationssymbol).

    Beweis  

    (1). Aufgrund der Gleichheitsaxiome haben wir

    und

    wobei eine Variable sei, die weder in noch in vorkomme. Daher sind die beiden substituierten Ausdrücke gleich bzw. . Eine aussagenlogische Umstellung der zweiten Zeile ist

    so dass sich aus der ersten Zeile mittels Modus ponens

    ergibt.
    (2). Es sei wieder eine Variable, die weder in noch in noch in vorkomme. Eine Anwendung des Substitutionsaxioms liefert

    Nach Einsetzen und einer aussagenlogischen Umstellung ist dies die Behauptung.
    Für (3) siehe Aufgabe *****.
    (4). Es sei eine Variable, die weder in einem der noch in einem der vorkommt. Für jedes gilt nach Axiom *****  (2) (mit ) dann

    also

    Diese Ableitbarkeiten gelten auch, wenn man die Vordersätze durch ihre Konjunktion

    ersetzt. Durch die Transitivität der Implikation ergibt sich daher




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

    PDF-Version dieser Vorlesung

    Arbeitsblatt zur Vorlesung (PDF)