Ein Prädikat ist eine Aussage mit einer Lücke: wahr oder falsch wird sie erst, wenn die Lücke gefüllt oder quantifiziert ist.

Das Prädikat

Definition

Eine Aussage ist ein Satz, der wahr oder falsch ist: „7 ist prim" ist wahr, „8 ist prim" ist falsch.

Ein Prädikat hat diese Eigenschaft nicht. „ $x$ ist prim" ist weder wahr noch falsch: es hängt von $x$ ab. Es ist ein Satz mit einer Lücke, der einen Wahrheitswert liefert, sobald die Lücke gefüllt ist.

Freie Variable, gebundene Variable

Solange die Variable frei bleibt, hat der Satz keinen Wahrheitswert. Zwei Operationen schließen sie:

Operation	Beispiel	Ergebnis
Einsetzen	$P(7)$	Wahr
Allquantifizieren	$\forall x, P(x)$	Falsch über den ganzen Zahlen
Existenzquantifizieren	$\exists x, P(x)$	Wahr über den ganzen Zahlen

Eine quantifizierte Variable heißt gebunden. Ein Satz ohne freie Variable ist eine Aussage — er hat einen Wahrheitswert, und nur einen.

Die Reihenfolge der Quantoren

Zwei Quantoren verschiedener Art vertauschen nicht. Über den ganzen Zahlen, mit $S(x, y)$ für „ $y$ ist größer als $x$ ":

$\forall x\, \exists y,\ S(x, y) \quad \text{ist wahr}$

$\exists y\, \forall x,\ S(x, y) \quad \text{ist falsch}$

Der erste sagt: zu jeder ganzen Zahl gibt es eine größere — und $y$ darf von $x$ abhängen. Der zweite sagt: es gibt eine ganze Zahl, die größer ist als alle — eine größte ganze Zahl, die es nicht gibt.

Dieselben Zeichen, in umgekehrter Reihenfolge, behaupten eine Wahrheit und eine Falschheit. Es ist derselbe Mechanismus, der die Definition des Grenzwerts nicht vertauschbar macht.

Eine quantifizierte Aussage verneinen

Die Verneinung durchquert die Quantoren, indem sie sie tauscht:

$\neg\,\forall x,\ P(x) \iff \exists x,\ \neg P(x)$

$\neg\,\exists x,\ P(x) \iff \forall x,\ \neg P(x)$

„Alle sind prim" zu verneinen ergibt nicht „keine ist prim", sondern „es gibt eine, die es nicht ist". Ein einziges Gegenbeispiel widerlegt einen Allsatz; einen Existenzsatz zu widerlegen erfordert, den ganzen Bereich abzusuchen.

Der Bereich gehört zur Aussage

Ein Prädikat lässt sich nur über einem erklärten Bereich beurteilen. „ $\exists x,\ x^2 = 2$ " ist über $\mathbb{Q}$ falsch und über $\mathbb{R}$ wahr: die Formel hat sich nicht geändert, das Universum schon.

Den Bereich wegzulassen heißt, die Aussage unbestimmt zu lassen — nicht mehrdeutig im Sinn, sondern ohne jeden Wahrheitswert.

Zusammenfassung

Ein Prädikat wird zur Aussage, sobald seine Variablen über einem erklärten Bereich festgelegt oder quantifiziert sind.