Bewijs door contrapositie

Uit Wikipedia, de vrije encyclopedie
Naar navigatie springen Naar zoeken springen

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 irrationaal.

We bewijzen de equivalente stelling:

Gegeven een positief geheel getal n. Als rationaal is, dan is n een kwadraat.

We nemen daartoe aan dat rationaal is. Dan kunnen we positieve gehele getallen a en b vinden zodat en ggd(a,b) = 1. Nu geldt dat 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.