Kontraposition

Kontraposition ist eine Methode, bei der man anstelle eines direkten Beweises die logisch äquivalente Aussage zeigt.

Wenn wir eine Aussage der Form "wenn A, dann B" beweisen wollen, können wir stattdessen beweisen "wenn nicht B, dann nicht A". Da die beiden Aussagen logisch gleich sind, ist der Beweis gültig.

Die Methode ist nützlich, wenn es schwierig ist, direkt von A nach B zu gelangen, es aber leichter ist, rückwärts von nicht-B nach nicht-A zu argumentieren.

Die Kontraposition bietet somit einen alternativen Weg, um zum gleichen Ergebnis zu gelangen.

Vorgehensweise

Ein Beweis durch Kontraposition kann in drei Schritte unterteilt werden:

1. Schreibe die Aussage "wenn A, dann B" um in "wenn nicht B, dann nicht A".
2. Nimm an, dass die Schlussfolgerung B nicht gilt.
3. Zeige logisch, dass dies impliziert, dass auch die Voraussetzung A nicht gelten kann.

Beispiel 1

Wir wollen beweisen: Wenn $ \large n^2 $ ungerade ist, dann ist $ \large n $ ungerade. Direkt kann dies schwierig sein, aber durch Kontraposition wird es zu:

Wenn $ \large n $ gerade ist, dann ist $ \large n^2 $ gerade.

Schreibe $ \large n = 2a $. Dann erhalten wir:

$$ \large n^2 = (2a)^2 = 4a^2 = 2(2a^2) $$

Also ist $ \large n^2 $ gerade. Damit ist die Kontraposition gezeigt, und die ursprüngliche Aussage ist bewiesen.

Beispiel 2

Wir wollen beweisen: Wenn eine ganze Zahl $ \large n $ durch 6 teilbar ist, dann ist sie durch 3 teilbar. Die Kontraposition lautet:

Wenn $ \large n $ nicht durch 3 teilbar ist, dann ist $ \large n $ nicht durch 6 teilbar.

Nehmen wir an, dass $ \large n $ nicht durch 3 teilbar ist. Das bedeutet, dass $ \large n = 3q + r $ mit Rest $ \large r = 1 $ oder $ \large r = 2 $. In beiden Fällen ist $ \large n $ nicht durch 6 teilbar, denn eine Zahl muss mindestens durch 3 teilbar sein, um durch 6 teilbar zu sein. Damit ist die Aussage durch Kontraposition bewiesen.

Beispiel 3

Wir wollen beweisen: Wenn ein Bruch $ \large \frac{a}{b} $ vollständig gekürzt ist, dann sind $ \large a $ und $ \large b $ nicht beide durch dieselbe Primzahl teilbar. Die Kontraposition lautet:

Wenn $ \large a $ und $ \large b $ durch dieselbe Primzahl teilbar sind, dann ist der Bruch $ \large \frac{a}{b} $ nicht vollständig gekürzt.

Nehmen wir an, dass sowohl $ \large a $ als auch $ \large b $ durch eine Primzahl $ \large p $ teilbar sind. Dann können wir schreiben:

$$ \large a = p \cdot m \quad \text{und} \quad b = p \cdot n $$

Der Bruch wird dann zu:

$$ \large \frac{a}{b} = \frac{p \cdot m}{p \cdot n} = \frac{m}{n} $$

Damit kann der Bruch durch $ \large p $ gekürzt werden, was zeigt, dass der ursprüngliche Bruch nicht vollständig gekürzt war. Die Kontraposition ist somit gezeigt, und die ursprüngliche Aussage ist bewiesen.

Beweise durch Kontraposition sind oft kürzer und übersichtlicher als direkte Beweise, wenn man mit zahlentheoretischen Eigenschaften und Teilbarkeit arbeitet. Die Technik bietet eine andere Perspektive auf ein Problem, aber das Ergebnis ist logisch genau dasselbe.