Beweis mit Widerspruch Beispiel für einen Beweis mit Widerspruch
Wir zeigen nun als Beispiel den Beweis eines Satzes aus der Mengenlehre. Die Grundlagen von Mengen und ihren Beziehungen untereinander werden im Kurs "Mathematische Grundlagen" behandelt.
Wir zeigen die folgende Aussage mithilfe eines Beweises mit Widerspruch:
\(\qquad\) | Seien \(A\) und \(B\) zwei Mengen mit der Eigenschaft \(A \cup B \subseteq A \cap B\), dann sind die Mengen bereits gleich, d.h. es gilt \(A=B\). |
Umformen der zu beweisenden Aussage:
Wir zerlegen diese Behauptung in die folgenden beiden Aussagen:
\(\qquad\) | \(\alpha\enspace : \enspace\) | \(A \cup B \subseteq A \cap B\) |
\(\beta\enspace : \enspace\) | \(A=B\) |
Wir beweisen nun \(\alpha \implies \beta\), also
\(\qquad\) | \((A \cup B \subseteq A \cap B)\implies (A=B)\) |
durch Widerlegung von \(\alpha \land \lnot \beta\), d.h. wir zeigen
\(\qquad\) | Wenn \(A \cup B \subseteq A \cap B\) und \(A \neq B\), dann entsteht ein Widerspruch. |
Beweis mit Widerspruch:
Seien \(A\) und \(B\) zwei Mengen mit der Eigenschaft \(A \cup B \subseteq A \cap B\). Angenommen, es gilt \(A \ne B\), dann gibt es mindestens ein Element \(x\), das in der einen Menge vorhanden ist und in der anderen Menge nicht. Nehmen wir an, dieses \(x\) ist in \(A\) enthalten und in \(B\) nicht, es gilt also \(x\in A\) und \(x\notin B\). Dann ist wegen \(x\in A\) auch \(x\in A \cup B\) und, da nach Voraussetzung \(A\cup B\) Teilmenge von \(A\cap B\) ist, folgt dann auch \(x\in A \cap B\). Dann ist aber \(x\in B\) und dies ist ein Widerspruch zur Annahme \(x\notin B\). Nehmen wir den anderen Fall an, \(x\) ist nicht in \(A\) enthalten, sondern in \(B\), es gilt also \(x\in B\) und \(x\notin A\). Dann ist wegen \(x\in B\) auch \(x\in A \cup B\) und, da nach Voraussetzung \(A\cup B\) Teilmenge von \(A\cap B\) ist, gilt dann auch \(x\in A \cap B\). Dann ist aber \(x\in A\) und dies ist ein Widerspruch zur Annahme \(x\notin A\). Wir haben also gezeigt, dass aus der Voraussetzung \(A \cup B \subseteq A \cap B\) und der Annahme \(A \ne B\) ein Widerspruch entsteht. | |
\(\blacksquare\) |
\(\enspace\)