Bewijs door contrapositie

Het bewijs door contrapositie is een methode om het wiskundig bewijs te geven van de stelling

als A dan B,

door het bewijzen van de stelling

als niet B dan niet A.

In de klassieke logica is deze laatste stelling equivalent aan de eerste: een bewijs van de ene stelling is ook een bewijs van de ander.

In de intuïtionistische logica zijn beide stellingen niet equivalent. Een bewijs van (als A dan B) impliceert wel dat (als niet B dan niet A) geldt, maar de implicatie in de andere richting geldt daar niet.

Voorbeeld

De volgende stelling kunnen we met contrapositie bewijzen:

Gegeven een positief geheel getal n. Als n geen kwadraat is, dan is ${\sqrt {n}}$ irrationaal.

We bewijzen de equivalente stelling:

Gegeven een positief geheel getal n. Als ${\sqrt {n}}$ rationaal is, dan is n een kwadraat.

We nemen daartoe aan dat ${\sqrt {n}}$ rationaal is. Dan kunnen we positieve gehele getallen a en b vinden zodat ${\sqrt {n}}={\frac {a}{b}}$ en ggd(a,b) = 1. Nu geldt dat $n={\frac {a^{2}}{b^{2}}}$ niet verder vereenvoudigd kan worden. Dus geldt in het bijzonder dat b² = 1, want n is een geheel getal. Dus n = a². Daarmee is de equivalente stelling bewezen en dus, door contrapositie, ook de oorspronkelijke.