Die Sprache der Mathematik: Prädikatenlogik

Worüber reden?

Die Aussagenlogik allein reicht noch nicht aus, um Mathematik zu betreiben. Man kann mit ihr zwar Aussagen verknüpfen, aber nicht weiter präzisieren, um welche Aussagen es sich dabei handelt.

Elementare Aussagen, die sich nicht mehr in kürzere Aussagen zerlegen lassen, atomare Formeln, setzen Objekte miteinander in Beziehung oder weisen ihnen Eigenschaften zu. Um dies zu formalisieren, umfasst eine prädikatenlogische Sprache Relationen und Terme. Ein Term steht für irgendein Objekt und eine Relation für eine Eigenschaft, die bestimmte Objekte haben oder nicht, das heißt, eine Relation weist Objekten Wahrheitswerte zu.

Beispiel: Steht etwa die zweistellige Relation $R(t_1,t_2)$ für "$t_1$ kann $t_2$ essen.", der Term $v$ für "Vogel", $k$ für "Kirsche" und $m$ für "Mensch", so sind die folgenden Aussagen richtig:

• $R(m,v)\wedge R(v,k)$ – „Der Mensch isst Vögel und der Vogel isst Kirschen.“
• $R(m,k)\wedge \mathrm{\neg }R(k,m)$ – „Der Mensch isst Kirschen und die Kirsche isst keine Menschen.“
• $R(v,k)\vee R(v,m)\vee R(v,v)$ – „Der Vogel isst Kirschen oder der Vogel isst Menschen oder der Vogel isst Vögel.“

In diesem Beispiel sind die Terme einfach Konstanten: Das $v$ etwa bezeichnet in der ganzen Sprache immer das gleiche Objekt, den Vogel. Was aber, wenn man etwa die Aussage "Der Mensch kann alles essen." formulieren will? Oder: "Es gibt etwas, was der Vogel essen kann."? Dazu brauchen wir weitere Sprachelemente:

Variablen und Quantoren

Eine Variable ist ein Symbol, das für unterschiedliche Objekte stehen kann. Zu einer prädikatenlogischen Formelsprache gehören unendlich viele Variablen, etwa $x_0,x_1,x_2,\dots$, oder $x,y,z,\dots$. Nun sagt aber eine Formel, in der eine nicht näher spezifizierte Variable vorkommt, nichts mehr aus und ihr Wahrheitswert wird davon abhängen, für welches Objekt sie nun steht: Eine Formel mit solch einer freien Variablen ist keine Aussage mehr.

Die Quantoren $\mathrm{\forall }$ - "für alle" - und $\mathrm{\exists }$ - "es existiert ein" - legen fest, wofür eine Variable stehen soll. Ist $A$ eine Formel, in der etwa die Variable $x$ frei vorkommt, so sagt $\mathrm{\forall }xA$ aus, dass $A$ für alle $x$ zutrifft, $A$ also immer wahr ist, egal für welches Objekt $x$ steht, und $\mathrm{\exists }xA$ sagt aus, dass $A$ für mindestens ein $x$ zutrifft, es also mindestens ein Objekt gibt, mit dem die Formel $A$ wahr wird, wenn man es für $x$ einsetzt.

Beispiel: Sind der Vogel, der Mensch und die Kirsche die einzigen Objekte, über die unsere Sprache spricht, so sind die folgenden Aussagen wahr:

• $\mathrm{\forall }xR(m,x)$ – „Der Mensch kann alles essen.“
• $\mathrm{\exists }xR(v,x)$ – „Es gibt etwas, das Vögel essen.“
• $\mathrm{\neg }\mathrm{\exists }x(R(x,x)\wedge R(x,m))$ – „Es gibt nichts, was sich selbst und Menschen isst.“

In der letzten Formel wurden Klammern verwendet, da konventionsgemäß die Quantoren stärker binden als die Junktoren.

Funktionen

Da man nicht für alle Objekte, über die man sprechen möchte, eine eigene Konstante einführen will, verwendet man Funktionen und lässt auch für die einzelnen Terme noch komplexere Ausdrücke zu. Eine Funktion ordnet einem oder mehreren Objekten ein weiteres zu. Sind etwa $t_1,t_2,t_3$ Terme (die wiederum Funktionen enthalten können) und ist $f$ eine dreistellige Funktion, so ist auch $f(t_1,t_2,t_3)$ wieder ein Term (der für das Objekt steht, das die Funktion f den Objekten zuweist, für die die drei Terme stehen).

Beispiel: Wenn die Objekte, über die unsere Sprache sprechen soll, beispielsweise die natürlichen Zahlen sind, so könnten wir etwa die folgenden Symbole einführen:

• die Konstanten 0 und 1 für die Null und die Eins
• die Relation $t_1<t_2$ für "$t_1$ ist kleiner als $t_2$"
• die Relation $t_1=t_2$ für "$t_1$ ist gleich $t_2$"
• die Funktionen + und * für die Addition und die Multiplikation, also für die Funktion, die je zwei Zahlen ihre Summe bzw. ihr Produkt zuordnet

(Häufig wird für zweistellige Funktionen und Relationen die Infix-Schreibweise verwendet; anstatt $+(x,y)$ schreiben wir $x+y$.) Diese Sprache ist nun bereits mächtig genug, um viele Aussagen über die natürlichen Zahlen zu formulieren:

• $\mathrm{\forall }x\mathrm{\forall }y(x+1=y+1\to x=y)$
• $0<1\wedge \mathrm{\neg }0=1$
• $\mathrm{\forall }x(x\cdot 0=0\wedge x\cdot 1=x)$