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.

Az $x^{2}=2y^{2}$ egyenlet felhasználásával: $x_{1}^{2}=(2y-x)^{2}=4y^{2}-4xy+x^{2}=2y^{2}+x^{2}-4xy+x^{2}=2\cdot (y^{2}-2xy+x^{2})=2\cdot (x-y)^{2}=2y_{1}^{2}$ tehát $(x_{1},y_{1})$ is megoldása az egyenletnek.

Tudjuk, hogy ha az egyenlet megoldható, akkor van olyan megoldás is, amiben y minimális. Azonban ahogy láttuk, ilyen nincs, mert tetszőleges megoldásból lehet kisebbet készíteni. Eszerint a ${\sqrt {2}}$ racionális volta nem állja meg a helyét, tehát ${\sqrt {2}}$ irracionális.

Hasonlóan, ha tetszőleges megoldás helyett a legkisebb megoldásból indulunk ki, akkor a kisebb megoldás létezése megcáfolja annak legkisebb voltát. Érvelhetünk úgy is, hogy minden $y_{1}<y$-hoz is készíthető kisebb y, tehát készíthető y-oknak végtelen $y>y_{1}>y_{2}>y_{3}>\ldots$ sorozata, ami a természetes számok alulról korlátos volta miatt lehetetlen, tehát ismét ellentmondáshoz jutunk.