„Végtelen leszállás” változatai közötti eltérés
| [ellenőrzött változat] | [ellenőrzött változat] |
kategória |
A megoldhatatlanság induktív bizonyítása |
||
| 4. sor: | 4. sor: | ||
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. |
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 [[teljes indukció|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''<sub>0</sub>-ra bizonyítva van, hogy nem lehet legkisebb megoldás. |
|||
*Az indukciós lépés: Mivel ''k''<sub>0</sub> nem lehet a legkisebb megoldás, ezért annak a ''k'' ≤ ''k''<sub>0</sub> 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. |
|||
[[Kategória:Matematikai logika]] |
[[Kategória:Matematikai logika]] |
||
A lap 2012. november 30., 21:03-kori változata
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 ≤ k0-ra bizonyítva van, hogy nem lehet legkisebb megoldás.
- Az indukciós lépés: Mivel k0 nem lehet a legkisebb megoldás, ezért annak a k ≤ k0 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.