Beweis von Quantorenregeln

Question

Aufgabe:

Folgende Quantorenregel soll bewiesen werden:
$$\exists x \in A \forall y \in B : p(x,y) \Rightarrow \forall y \in B \exists x \in A : p(x,y)$$

Problem/Ansatz:

Ich komme einfach nicht mit Beweisen von Quantorenregeln klar. Ich habe versucht über die Regel:

$$\neg(A \Rightarrow B) \Leftrightarrow A \land \neg B$$

das ganze umzuformen, komme aber auch da nicht weiter:

Die rechte Seite sieht dann wie folgt aus:
$$(\exists x \in A \forall y \in B : p(x,y)) \land \neg(\forall y \in B \exists x \in A : p(x,y))$$
Auflösen der Negation auf der rechten Seite ergibt:
$$(\exists x \in A \forall y \in B : p(x,y)) \land (\exists y \in B \forall x \in A : \neg(p(x,y)))$$

Für die linke Seite folgt dann:

$$\neg(\exists x \in A \forall y \in B : p(x,y) \Rightarrow \forall y \in B \exists x \in A : p(x,y))$$

keine Ahnung wie man das dann "ausklammert". Unter der Annahme, dass die Negation der Implikation nur dann wahr ist, wenn B falsch ist und A wahr ist, könnte man vielleicht schreiben:

 $$\exists x \in A \forall y \in B : p(x,y) \Rightarrow \neg(\forall y \in B \exists x \in A : p(x,y))$$

Das führt dann aber zu:

$$\exists x \in A \forall y \in B : p(x,y) \Rightarrow \exists y \in B \forall x \in A : \neg p(x,y))$$

Und nu? Ich scheine mir da zu viele Gedanken zu machen. Es gibt doch sicherlich einen einfacheren Weg???

Comments

Manchmal kann Verbalisierung durch Ausformulierung helfen.

Answer 1

Das geht wirklich viel einfacher.

Angenommen, die linke Seite der Implikation ist wahr. Dann gibt es also \(x_0\), so dass \(p(x_0,y)\) wahr ist für alle \(y\). Dann ist aber auch die rechte Seite wahr, denn sei \(y\) gegeben, dann gibt es ein \(x\) mit \(p(x,y)\) ist wahr, nämlich eben dieses \(x_0\). Fertig.

Der Unterschied zwischen linker und rechter Seite ist, dass links das \(x_0\) für alle \(y\) das gleiche sein muss, rechts aber das \(x\) von \(y\) abhängen darf. Daher gilt die umgekehrte Richtung nicht.

Comments

Warum ist das jetzt ein Beweis und nicht einfach nur die Wiedergabe dessen, was da in Symbolen ausgedrückt ist?

---

Der Beweis ist der Abschnitt mit "Angenommen...". Der folgende Abschnitt eine Erklärung.

Ein Folgerung \(A\implies B\) weist man nach, indem man annimmt, dass \(A\) wahr ist und dann (mit logischen Schlüssen) folgert, dass \(B\) wahr ist.

Wie bei jedem math. Satz, der in Vor. und Beh. gegliedert formuliert ist.

---

Mein Unverständnis ist jetzt leider einfach "eine Ebene tiefer" gewandert und ich frage mich welche "logischen Schlüsse" in deinem Beweis enthalten sind. Es klingt nach wie vor für mich so, als hättest du einfach die in Symbolen enthaltene Schreibweise aufgeschrieben.

So als ob ich sage:

Zu zeigen ist:

$$\neg(X \Rightarrow Y) \Leftrightarrow X \land \neg Y$$

Angenommen es gilt nicht: wenn X dann Y. Das ist genau dann wahr wenn X wahr ist und Y falsch ist.

Hier hab ich doch jetzt nichts bewiesen sondern einfach nur in Worten aufgeschrieben was da steht???

---

Die Abfolge logischer Schlüsse erkennst Du an den Schlüsselworten (in fast jedem Beweis enthalten) wie "Dann....", "denn..." (enthält Begründung). Ein Beweis muss nicht Formeln/Terme/Quantoren enthalten und in einem weiteren Sinne ist JEDER Beweis nichts anderes als "das, was da steht", anders (in kleinen Denkschritten) aufgeschrieben, ja, auch Worte sind zulässig. Findest Du denn einen Fehler oder eine Lücke in den logischen Schritten? Dann wäre es kein Beweis.

Zu Deinem "So als ob ich sage....": Du schreibst die Beh. einfach ab. Das habe ich NICHT gemacht, beachte die Argumentation mit dem \(x_0\), die ich ja noch erklärt habe.

---

Vielen Dank schon mal soweit für deine Hilfe! Ich versuche das wirklich zu verstehen, so dass ich es auch jemanden erklären könnte.

Ich stocke gerade bei den kleinen Denkschritten: Welche sind das in deinem Beweis?

Ich habe die Behauptung ja in meinem zweiten Beispiel auch nicht einfach abgeschrieben, oder?

Ich habe ja gesagt, dass die linke Seite nicht gelte und daraus dann folgt

$$X \land \neg B $$ (und umgekehrt), was nichts anderes ist, als da ausgeschrieben steht. Ich habe demzufolge auch keine kleinen Denkschritte "dazwischen". Das mit dem $$x_0$$ ist natürlich ein Denkschritt, der aber irgendwie formal wirkt, weil er das $$x$$ nur in $$x_0$$ umbenennt, oder??

Ich steh irgendwie immer noch auf dem Schlauch tut mir leid :(

---

Ich hab Dir doch erklärt woran man die Denkschritte erkennt. Die Benennung als \(x_0\) dient zur Hervorhebung, aber im zweiten Schritt (eingeleitet mit dem zweiten "Dann") wird nämlich das gesuchte \(x\) genau angegeben. Das ist also sogar ein konstruktiver Beweis, mach Dir das klar.
Wir haben hier zwei getrennte Aussageformen, die jeweils unterschiedlich quantisiert sind. Die \(x,y\) sind (Informatik-Sprech) "lokale Variablen" (nur gültig in ihrer eigenen Aussage) und haben erstmal nichts miteinander mit ihren Namensvettern in der anderen Aussage zu tun. Daher ist es auch nicht sinnvoll, das besondere \(x\) in der ersten Aussage als \(x\) bezeichnet zu lassen, weil es mit dem \(x\) in der zweiten Aussage nichts zu tun hat
Der Beweis schafft dann die Verbindung.
In Deinem Beispiel hast Du abgeschrieben, weil Du angenommen hast, dass die linke Seite gelte (und nicht "nicht gelte"!).

---

Okay ich versuch das einfach mal an einem anderen Beispiel nachzuvollziehen und vielleicht kannst du mir sagen, ob ich das verstanden habe:

Beweis das folgende Quantorenregel falsch ist (also der Beweis, dass verschiedene Quantoren nicht vertauscht werden können:

$$\exists x \in A \forall y \in B : p(x,y) \Leftrightarrow \forall y \in B \exists x \in A : p(x,y)$$

Ich würde hier jetzt einfach sagen, dass der rechte Teil bedeutet:

Für alle y aus B existiert mindestens ein x aus A für das gilt p(x,y).

Das x kann ein einziges x sein, so dass für alle y gilt, dass sie zu diesem einem x in Beziehung p(x,y) stehen. Die rechte Seite bedeutet demgegenüber aber, dass es mindestens ein x zu jedem y gibt, das in Beziehung p(x,y) steht. Es sind also zwangsläufig mindestens so viele x wie y, es könnten aber auch mehr sein. Bei der rechten Seite könnten es ebenfalls mehrere sein, es könnte aber auch, wie gesagt nur ein einziges sein, daher sind die Aussagen nicht äquivalent.

So richtig?

---

Nein, es geht nicht um mehrere x zu einem y. Ich hab Dir doch in der allerersten Antwort schon erklärt, warum die Rückrichtung nicht gilt.

Versuch es mit einem Beispiel: \(A=B\subset \R\) und \(p(x,y)= x\le y\). Wie lautet die linke Seite verbal formuliert, und wie die rechte?

---

Linke Seite: Die Menge A ist identisch mit B die eine Teilmenge der reellen Zahlen ist.

Rechte Seite: x ist kleiner gleich y

Und ja ich weiß das die Rückrechnung nicht geht, das wollte ich ja beweisen? (Beweis das Quantoren nicht vertauscht werden können).

---

Was machst Du da jetzt? Mein Beispiel sind Angaben zur Aufgabenstellung ganz oben, setz es in die Implikation ein.

Du sollst nicht zeigen, dass die Rückrichtung nicht gilt, sondern dass die Hinrichtung gilt.