Végtelen leszállás

A végtelen leszállás' egy indirekt bizonyítási módszer, ami azon alapul, hogy a természetes számok minden részhalmazának van legkisebb eleme. A módszert Pierre de Fermat fejlesztette ki, és sok eredményéhez ezzel a módszerrel jutott el. A nagy Fermat-tétel n = 4-hez tartozó speciális esete például belátható végtelen leszállással.

Általános eljárás

Az érvelés indirekt, tehát feltesszük, hogy a bizonyítandó állítás nem igaz, vagyis hogy a szóban forgó egyenlet megoldható a természetes számok halmazán. Tudjuk, hogy a természetes számok minden részhalmazának van legkisebb eleme, ezért ha minden feltételezett megoldásból újabb, természetes számokból álló megoldást tudunk készíteni, akkor ellentmondást kaptunk, és a szóban forgó egyenlet nem oldható meg a természetes számok halmazán.

Másként, az egyenlet megoldáshalmazának is van legkisebb eleme, mivel a megoldáshalmaz a természetes számok halmazának része. Ebből készítünk egy még kisebb megoldást a feladat és a természetes számok tulajdonságainak felhasználásával. Ez ellentmond annak, hogy a legkisebb megoldásból indultunk ki, tehát az egyenlet megoldhatatlan.

A megoldhatatlanság induktív bizonyítása

Tegyük fel, hogy egy legkisebb megoldásból tudunk még kisebb megoldást csinálni! Ezen nyugszik a végtelen leszállás alapelve, és amihez konkrét bizonyítás szükséges.

• Az indukció megkezdése: A legkisebb megoldás nem lehet a 0, mert akkor lenne a 0-nál kisebb természetes szám. Mivel nincs ilyen szám, ezért ellentmondásra jutottunk.
• Az indukciós feltevés: Feltesszük, hogy már minden k ≤ k₀-ra bizonyítva van, hogy nem lehet legkisebb megoldás.
• Az indukciós lépés: Mivel k₀ nem lehet a legkisebb megoldás, ezért annak a k ≤ k₀ számok között kell lennie. Ez ellentmond az indukciós feltevésnek.

Tehát a legkisebb megoldás nem létezik, így semmilyen megoldás nincs, tehát az egyenlet megoldhatatlan.

Példa

Állítás: A 2 négyzetgyöke irracionális.

${\sqrt {2}}$ pozitív. Feltesszük indirekt, hogy racionális, tehát vannak olyan $x,y$ természetes számok, hogy ${\sqrt {2}}={\tfrac {x}{y}}$. Négyzetre emelve kapjuk az $x^{2}=2\cdot y^{2}$ egyenletet, aminek megoldásai az $x,y$ természetes számok. Állítjuk, hogy egy adott $x,y$ megoldásból készíthető egy $x_{1},y_{1}$ megoldás, ami abban az értelemben kisebb, hogy $y_{1}<y$.

Az $x^{2}=2y^{2}>y^{2}$ egyenlőtlenség miatt $x>y$, tehát $y_{1}:=x-y$ is természetes szám. Hasonlóan, $(2y)^{2}>2\cdot y^{2}=x^{2}$ miatt $2y>x$, és így $x_{1}:=2y-x$ szintén természetes szám. Emellett még $y>x-y=y_{1}$ is teljesül.