1.10 Umgang mit Quantoren
Satz (Quantorenregeln für den Allquantor ∀ und den Existenzquantor ∃)
Für alle Eigenschaften ℰ und die Quantoren ∀ „für alle“ und ∃ „es gibt“ gilt:
| (a) | ¬ ∀x ℰ(x) | ist äquivalent zu | ∃x ¬ ℰ(x), | |
| ¬ ∃x ℰ(x) | ist äquivalent zu | ∀x ¬ ℰ(x), (Verneinungsregeln) | ||
| (b) | ∀x ∀y ℰ(x, y) | ist äquivalent zu | ∀y ∀x ℰ(x, y), | |
| ∃x ∃y ℰ(x, y) | ist äquivalent zu | ∃y ∃x ℰ(x, y), | ||
| ∃x ∀y ℰ(x, y) | impliziert | ∀y ∃x ℰ(x, y). (Vertauschungsregeln) |
Paare (x, y) mit ℰ(x, y) sind schwarz markiert, andere Paare weiß.
Im rechten Diagramm ist die Aussage ∃x ∀y ℰ(x, y) nicht gültig.
Wir verwenden hier das Zeichen „¬“ für die Negation „nicht“ (vgl. auch Anhänge 1 und 2). Die Ausdrücke werden exemplarisch wie folgt gelesen:
∀x ℰ(x) | für alle x gilt ℰ(x) |
∃x ℰ(x) | es gibt ein x mit ℰ(x) |
¬ ∀x ℰ(x) | nicht für alle x gilt ℰ(x) |
∀x ∀y ℰ(x, y) | für alle x und für alle y gilt ℰ(x, y) |
∀x ∃y ℰ(x, y) | für alle x gibt es ein y mit ℰ(x, y) |
Die erste Zeile von Teil (a) des Satzes besagt also ausformuliert, dass
„nicht für alle x gilt ℰ(x)“ äquivalent ist zu „es gibt ein x, für das ℰ(x) nicht gilt“.
Ebenso besagt die zweite Zeile von Teil (a), dass
„es gibt kein x mit ℰ(x)“ äquivalent ist zu „für alle x gilt non ℰ(x)“.
Wenn es nicht an allen Tagen der Woche regnet, so gibt es einen Tag der Woche, an dem es nicht regnet − und umgekehrt. Und gibt es in einer Klasse kein Kind, das rote Haare hat, so haben alle Kinder der Klasse eine von rot verschiedene Haarfarbe − und umgekehrt.
Die Verneinungsregeln verallgemeinern sich für mehrere Quantoren wie folgt:
Die Aussage … | ist äquivalent zu … |
¬ ∀x ∃y ℰ(x, y) | ∃x ∀y ¬ ℰ(x, y) |
¬ ∃x ∀y ℰ(x, y) | ∀x ∃y ¬ ℰ(x, y) |
¬ ∀x ∃y ∀z ℰ(x, y, z) | ∃x ∀y ∃z ¬ ℰ(x, y, z) |
¬ ∃x ∀y ∃z ℰ(x, y, z) | ∀x ∃y ∀z ¬ ℰ(x, y, z) |
Als Merkregel:
Beim „Reinziehen“ einer Negation werden ∀ und ∃ ausgetauscht
und die Negation landet vor der Eigenschaft, auf die Quantoren wirken.
Beispiel
Sei f : ℝ → ℝ. Dann bedeutet ∀y ∃x f (x) = y, dass f surjektiv ist (wobei die Variablen x und y über ℝ laufen), und ¬ ∀y ∃x f (x) = y ist äquivalent zu ∃y ∀x f (x) ≠ y.
Das ist alles sehr hübsch, aber der Leser wird sich fragen, was dieses Logiktraining mit Analysis zu tun hat. Die Antwort ist: Die Verneinungsregeln werden in der Analysis tatsächlich häufig gebraucht. Begriffe wie
Grenzwert einer Folge, Stetigkeit einer Funktion in einem Punkt,
gleichmäßige Konvergenz einer Funktionenfolge,
Riemann-Integrierbarkeit einer Funktion auf einem Intervall [ a, b ]
besitzen Definitionen, bei denen sich mehrere All- und Existenzquantoren abwechseln. Eine übliche Formulierung der Stetigkeit einer Funktion in einem Punkt p hat zum Beispiel den Typ „∀ ∃ ∀“. Kennt man die Verneinungsregeln, so weiß man, dass die Unstetigkeit der Funktion im Punkt p vom Typ „∃ ∀ ∃“ ist.
Die beiden ersten Aussagen von (b) besagen, dass man Quantoren des gleichen Typs vertauschen darf. Das ist unproblematisch. Suggestiv und besser lesbar schreibt man oft
∀x ∀y ℰ(x, y) als ∀x,y ℰ(x, y) und ∃x ∃y ℰ(x, y) als ∃x,y ℰ(x, y).
Eine große Fehlerquelle stellt dagegen die Vertauschung von verschiedenen Quantoren dar. Die dritte Vertauschungsregel besagt, dass der Übergang von ∃∀ zu ∀∃ erlaubt ist. Eine Eselsbrücke hierzu lautet:
∃in ∀llesfresser darf ∀lles ∃ssen.
Der Übergang von ∀∃ zu ∃∀ führt dagegen oft zu falschen Aussagen. Das obige Diagramm führt den Unterschied zwischen ∃x ∀y ℰ(x, y) und ∀y ∃x ℰ(x, y) vor Augen. Wir betrachten die Relation R = { (x, y) | ℰ(x, y) } als Punktwolke. Anschaulich bedeutet ∃x ∀y ℰ(x, y), dass es eine Senkrechte gibt, die schwarz gefärbt ist. Dagegen bedeutet ∀y ∃x ℰ(x, y), dass alle Waagrechten mindestens einen schwarzen Punkt treffen. Die erste Aussage impliziert die zweite, aber die Umkehrung ist im Allgemeinen nicht richtig. „Einer ist für alles gut“ ist stärker als „Für alles ist irgendwer gut.“