Kurs:Mathematik fuer Anwender/Quantoren

Quantoren

Wir werden Aussagen über die Elemente einer Menge treffen.
Dabei gab es zwei verschiedene Arten der Aussagen. Zum einen Aussagen, die für alle Elemente einer Menge wahr sind, und zum anderen haben wir Aussagen, die für mindestens ein Element der Menge erfüllt sind.
Dieses ist eine in der Mathematik wesentliche Unterscheidung von Aussagen.

Definition: Allquantor

Es sei $M$ eine Menge und $A(x)$ eine Aussage in Abhängigkeit von $x\in M$.
Die Aussage “Für alle $x\in M$ gilt $A(x)$” ist genau dann wahr, wenn für alle Elemente $x\in M$ die Aussage $A(x)$ wahr ist.
Wir schreiben $\mathrm{\forall }x\in M:A(x)$.
Der Ausdruck “für alle” heißt dabei Allquantor.

Beispiel: Allquantor

• $\mathrm{\forall }a,b\in ℝ:(a\pm b{)}^2=a^2\pm 2ab+b^2$.
• $\mathrm{\forall }x\in \mathbb{Z}:\frac{x}{3}\in \mathbb{Q}$.

Definition: Existenzquantor

Es sei $M$ eine Menge und $A(x)$ eine Aussage in Abhängigkeit von $x\in M$.
Die Aussage “Es existiert ein $x\in M$, für das $A(x)$ gilt” ist genau dann wahr, wenn es ein Objekt $y\in M$ gibt so, dass die Aussage $A(y)$ wahr ist.
Wir schreiben $\mathrm{\exists }x\in M:A(x)$.
Der Ausdruck “es existiert” heißt dabei Existenzquantor.

Beispiel: Existenzquantor

• $\mathrm{\exists }a,b\in \mathbb{N}:a+b=2$.
• $\mathrm{\exists }x\in \mathbb{Z}:x\in \mathbb{N}$.

Lemma: Verneinung Existenzquantor und Allquantor

Es sei $M$ eine Menge und $A(x)$ eine Aussage in Abhängigkeit von $x\in M$. Dann gilt: $\mathrm{\neg }(\mathrm{\forall }x\in M:A(x))\iff \mathrm{\exists }x\in M:\mathrm{\neg }A(x)\text{ und }\mathrm{\neg }(\mathrm{\exists }x\in M:A(x))\iff \mathrm{\forall }x\in M:\mathrm{\neg }A(x).$

Beispiel: Verneinung Existenzquantor und Allquantor

• Wir betrachten die Aussage “Alle Insekten haben sechs Beine”. Wenn wir die Negation dieser Aussage bilden, erhalten wir “Nicht alle Insekten haben sechs Beine”; das ist offensichtlich äquivalent zur Aussage “Es gibt (mindestens) ein Insekt mit einer Beinanzahl, die ungleich sechs ist”.
• Die Aussage $\mathrm{\exists }x\in \mathbb{Z}:x^2=2$ (die übrigens falsch ist), wird negiert von der Aussage “Es gibt kein $x\in \mathbb{Z}$, für das $x^2=2$ gilt” (in Formeln: $\nexists x\in \mathbb{Z}:x^2=2$) und das ist gleichwertig dazu, dass für jede ganze Zahl $x^2\ne 2$ ist.

Treten die Quantoren in Kombination auf, so ist die Reihenfolge für die Bedeutung extrem wichtig:

Lemma: Reihenfolge Existenzquantor und Allquantor

Es seien $M$ und $N$ Mengen und $A(x,y)$ eine Aussage, die von den Variablen $x$ und $y$ mit $x\in M$ und $y\in N$ abhängig ist.

• $\mathrm{\forall }x\in M\mathrm{\exists }y\in N:A(x,y)$ bedeutet, dass es für jedes $x\in M$ ein (möglicherweise verschiedenes) $y\in N$ gibt so, dass $A(x,y)$ gilt.
• $\mathrm{\exists }y\in N\mathrm{\forall }x\in M:A(x,y)$ bedeutet, dass es ein $y\in N$ gibt, das für jedes $x\in M$ dasselbe ist, so, dass $A(x,y)$ gilt.

Beispiel: Reihenfolge Existenzquantor und Allquantor

Sei $M$ die Menge aller Fußballfans und $N$ die Menge aller Fußballvereine und sei für $x\in M$ und $y\in N$ die Aussage $A(x,y):=$"`x ist Fan von y."' gegeben.

$\mathrm{\forall }x\in M\mathrm{\exists }y\in N:A(x,y)$ heißt, dass jeder Fußballfan auch Fan irgendeines Fußballvereins ist.

$\mathrm{\exists }y\in N\mathrm{\forall }x\in M:A(x,y)$ heißt, dass es einen Verein gibt, von dem jeder Fußballfan Fan ist.