Bewijs door contrapositie

Uit Wikipedia, de vrije encyclopedie
Ga naar: navigatie, zoeken

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[bewerken]

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 ab 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 b2 = 1, want n is een geheel getal. Dus n = a2. Daarmee is de equivalente stelling bewezen en dus, door contrapositie, ook de oorspronkelijke.