Bewijs door oneindige afdaling

Een bewijs door oneindige afdaling is een vorm van een wiskundig bewijs die bij verzamelingen kan worden toegepast die aftelbaar en welgeordend zijn, in het bijzonder bij de natuurlijke getallen. Het bewijs berust erop dat in zulke verzamelingen geen oneindige rij kleiner wordende elementen kan voorkomen. Daarmee wordt net zoals in een bewijs uit het ongerijmde een tegenspraak aangetoond.

Men bewijst het niet bestaan van een element uit die verzameling met een bepaalde eigenschap, door aan te tonen dat als er zo'n element bestaat, er ook een kleiner element moet bestaan met die eigenschap. Zo ontstaat een oneindige keten van elementen kleiner dan het veronderstelde element, terwijl er maar eindig veel van dergelijke elementen zijn.

Voorbeeld

Het is door oneindige afdaling te bewijzen dat wortel 2 irrationaal is:

Stel dat ${\sqrt {2}}$ rationaal is, dan zijn er natuurlijke getallen $p$ en $q$ zodat

${\sqrt {2}}={\frac {p}{q}}$

Er geldt nu

$2q^{2}=p^{2}$

Maar dat betekent dat het natuurlijke getal $p$ even is, dus is $p^{2}$ een viervoud. Maar dan is $2q^{2}$ kennelijk een viervoud, waaruit blijkt dat ook $q$ even is.

We kunnen daarom twee natuurlijke getallen aanwijzen, $p'=p/2$ en $q'=q/2$ kleiner dan $p$ respectievelijk $q$, zodat ${\sqrt {2}}={\frac {p'}{q'}}$. Dit levert een oneindige afdaling, dus een tegenspraak.

Het gestelde, dat ${\sqrt {2}}$ rationaal is, is dus onjuist. □

Door Euclides is dit getaltheoretische bewijs in Boek 10 van De Elementen gegeven.