Hilbert tizedik problémája

Az oldal jelenlegi verzióját még nem ellenőrizték tapasztalt közreműködők, és jelentősen eltérhet a 2021. október 10-én felülvizsgált verziótól ; az ellenőrzéshez 1 szerkesztés szükséges .

Hilbert tizedik problémája  egyike annak a 23 problémának , amelyet David Hilbert javasolt 1900. augusztus 8-án a II. Nemzetközi Matematikus Kongresszuson . Ez abból áll, hogy egy univerzális módszert találunk egy tetszőleges algebrai diofantin-egyenlet megoldhatóságának meghatározására . A probléma algoritmikus megoldhatatlanságának bizonyítása körülbelül húsz évig tartott, és Jurij Matiyasevics fejezte be 1970-ben [1] [2] .

A probléma leírása

Hilbert jelentésében a tizedik probléma megfogalmazása a legrövidebb az összes közül:

Adjunk meg egy diofantin egyenletet tetszőleges ismeretlenekkel és egész racionális numerikus együtthatókkal. Jelöljön meg egy módszert, amellyel véges számú művelet után meghatározható, hogy ez az egyenlet megoldható-e racionális egész számokban [3] .

Eredeti szöveg  (német)[ showelrejt] Eine Diophantische Gleichung mit irgend welchen Unbekannten und mit ganzen rationalen Zahlencoefficienten sei vorgelegt: man soll ein Verfahren angeben, nach welchem ​​​​sich mittelst einer endlichen Anzahl von Operationen entscheiden läßt, ob die lözen Rleichbaren is in Zahlen lözen rationalen .

Formálisan a forma egyenletek egész számú [5] megoldásáról beszélünk

ahol  egy polinom egész együtthatókkal és egész kitevőkkel [6] . Az egyenlet foka megegyezik a polinom fokával .

A 23 probléma közül ez az egyetlen megoldhatósági probléma [7] . Hilbert nyilvánvalóan azt hitte, hogy a kívánt módszer létezik, és előbb-utóbb megtalálják [8] . Hilbert idejében fel sem merült az a kérdés, hogy elvileg nem létezik ilyen módszer [9] [10] .

Háttér

Az algebrai egyenletek egész számú megoldása már az ókorban is érdekelte a matematikusokat . Például nagy figyelmet fordítottak az egyenletre : ha annak megoldása természetes számok halmaza , akkor a Pitagorasz - tétellel fordított tétellel derékszögű háromszöget kaphatunk hosszúságú szakaszokból [11] . Eukleidész képleteket adott ennek az egyenletnek az összes egész számú megoldására [12] . Egyes másodfokú egyenlettípusokat és azok rendszereit Alexandriai Diophantus [13] vizsgálta , munkáit később Leonhard Euler , Pierre Fermat , Joseph Louis Lagrange , Carl Friedrich Gauss és más számelméletben foglalkozó matematikusok is felhasználták . Különösen Fermat terjesztette elő híres hipotézisét . 1768-ra Lagrange teljesen feltárta a két ismeretlen másodfokú egyenletének egész számú megoldásának kérdését [14] .

A 19. század során sok matematikus, megoldva Fermat utolsó tételét , megpróbálta tanulmányozni a másodiknál ​​magasabb fokozatú diofantinuszi egyenleteket. Mindazonáltal az ilyen egyenletek megoldásának problémája nyitott maradt : általános módszert nem kaptak, csak speciális módszereket találtak bizonyos típusú egyenletekre. Valószínűleg Hilbert azt gyanította, hogy ezen a területen a további kutatások részletes és mély elméletek megalkotásához vezetnek, nem korlátozódva a diofantini egyenletekre, és ez arra késztette, hogy felsorolja a problémát jelentésében [9] .

Megoldástörténet

Algoritmus keresése

Az 1940-es évekig a tizedik probléma kutatása folyt annak érdekében, hogy megtalálják a szükséges algoritmust legalább néhány diofantini egyenletosztályhoz. Néhány évvel Hilbert jelentése után, 1908-ban Axel Thue kimutatta, hogy a két ismeretlenre vonatkozó Thue-egyenletnek nem lehet végtelen sok egész megoldása [15] . 1938-ban Turalf Skolem közzétett egy módszert olyan diofantin egyenletek tanulmányozására, ahol  egy nem teljes felbontható forma ( egy irreducibilis polinom , amely a racionális számok mezőjében lineáris tényezők szorzatává bővül ), amely bizonyos feltételeknek eleget tesz [16] . Thue eredménye ellenére még a két ismeretlent tartalmazó egyenletek is dacoltak a matematikusok minden erőfeszítésével (az egy ismeretlennel való egyenletek megoldásának algoritmusa Bézout tételéből következik ).

Az 1930-as évek közepén formalizálták az algoritmus fogalmát, és megjelentek a matematikai logikában az algoritmikusan eldönthetetlen halmazok első példái is . Fontos momentum volt Andrei Markov és Emil Post (egymástól függetlenül) bizonyítéka a Thue-i probléma megoldhatatlanságára 1947-ben [17] [18] . Ez volt az első bizonyítéka egy algebrai probléma megoldhatatlanságának. Ez, valamint a diofantini egyenletek kutatóinak nehézségei ahhoz a feltételezéshez vezettek, hogy a Hilbert által igényelt algoritmus nem létezik. Valamivel korábban, 1944-ben Emil Post már azt írta egyik dolgozatában, hogy a tizedik probléma „ megoldhatatlansági bizonyítást kér ” [ 19] . 

Davis hipotézis

Post szavai arra ösztönözték Martin Davis diákot , hogy bizonyítékot keressen arra, hogy a tizedik probléma eldönthetetlen. Davis az egész számokban való megfogalmazásról a természetes számokban való megfogalmazásra tért át, ami természetesebb az algoritmusok elmélete számára [20] . Ez két különböző feladat, de mindegyik a másikhoz vezet. 1953-ban publikált egy tanulmányt, amelyben felvázolta a természetes számok tizedik problémájának megoldásának módját [21] .

Davis a klasszikus diofantini egyenletekkel együtt figyelembe vette azok parametrikus változatát:

ahol egy egész együtthatós polinom két részre - paraméterekre és változókra - osztható.A paraméterértékek egyik halmazára az egyenletnek lehet megoldása, egy másikra nem léteznek megoldások. Davies kiemelte a halmazt , amely tartalmazza a paraméterértékek ( -ek) összes készletét, amelyekre az egyenletnek megoldása van:

Az ilyen jelölést egy halmaz diofantin ábrázolásának nevezte, magát a halmazt pedig Diofantinnak is nevezték . A tizedik probléma megoldhatatlanságának bizonyításához csak azt kellett megmutatni, hogy bármely felsorolható halmaz Diofantin , vagyis meg kell mutatni egy olyan egyenlet megalkotásának lehetőségét, amelynek csak minden ebbe a felsorolható halmazba tartozónak lenne természetes gyökere: mivel Felsorolható halmazok között vannak feloldhatatlanok , akkor a feloldhatatlan halmazt alapul véve lehetetlen lenne olyan általános módszert kapni, amely egyenként meghatározná, hogy egy egyenletnek van-e természetes gyökere ezen a halmazon. Mindez a következő hipotézishez vezette Davist:

A Diophantine és a felsorolható halmazok fogalma egybeesik. Ez azt jelenti, hogy egy halmaz akkor és csak akkor diofantin, ha megszámlálható.

Davis is megtette az első lépést – bebizonyította, hogy bármely felsorolható halmaz ábrázolható így:

Ezt az ábrázolást "Davis normál formának" nevezik. Akkoriban nem sikerült bebizonyítania sejtését azzal, hogy megszabadult az univerzális kvantortól .

Robinson hipotézise

Davistől függetlenül Julia Robinson a tizedik problémán kezdett dolgozni ugyanabban az évben . Kezdetben megpróbálta bebizonyítani Alfred Tarski sejtését, miszerint a kettő összes hatványa nem diofantin, de nem járt sikerrel [22] . Ezt követően Robinson azt a kérdést vizsgálta, hogy a hármasokból álló halmaz Diofantin-e . A hatványozási művelethez nem sikerült diofantusi reprezentációt találnia, ennek ellenére [23] munkájában elegendő feltételt mutatott a létezéséhez:

ráadásul:

Robinson „ exponenciális növekedési függőségnek” nevezte a kapcsolatot , de később ezt a függőséget az ő tiszteletére kezdték elnevezni – „Robinson-függőség”, „Robinson-predikátumok” vagy egyszerűen „JR”.

Joining Forces

1958-ban Martin Davis és Hilary Putnam publikált [24] , amelyben Robinson eredménye alapján az exponenciális-diofantin egyenletek egy osztályát vették figyelembe, amelyek a következő alakúak:

ahol és az exponenciális polinomok, vagyis az összeadás , szorzás és hatványozás  műveletei segítségével kapott változókból és racionális számokból nyert kifejezések , és az ilyen egyenletek diofantin ábrázolását is mutatták. Davis és Putnam bizonyítása azonban tartalmazott egy hiányosságot – a csak prímszámokból álló , tetszőlegesen hosszú aritmetikai sorozatok létezéséről szóló sejtést alkalmazták ( Green-Tao tétel ), amit csak 2004-ben igazoltak.

1961-ben Julia Robinson pótolni tudta ezt a hiányt . Közös munkájukban [25] exponenciális diofantusz-reprezentációt kaptak bármely felsorolható halmazra:

A munka egyik következménye az volt, hogy tetszőleges exponenciális diofantikus egyenletet le lehetett redukálni egy exponenciális diofantini egyenletre, fix számú változóval (legalább három [26] ).

Ahhoz, hogy Davies, Putnam és Robinson eredményét átvigyük a "hétköznapi" diofantini egyenletekre, be kellett bizonyítani, hogy a hármasokból álló halmaz diofantin. Ekkor további ismeretlenek bevezetése árán lehetséges lenne az exponenciálisan diofantin ábrázolást diofantin ábrázolássá fordítani:

Más szóval, a Davis-sejtés teljes bizonyításához csak egy konkrét esetet kellett bizonyítanunk, pontosabban a Robinson-sejtést kell igazolni (olyan polinomot találni, amely minden feltételt kielégít).

Annak ellenére, hogy Diophantus kora óta mélyrehatóan tanulmányozták a kétparaméteres diofantinuszi egyenleteket, akkor még nem volt ismert egyenlet, amely kifejezné az exponenciális növekedés függését. A mesterséges megépítésére tett kísérletek szintén kudarcot vallottak.


Befolyás

Jegyzetek

  1. ↑ Yu. V. Matiyasevics . Felsorolható halmazok diofantin tulajdonsága // A Szovjetunió Tudományos Akadémiájának jelentései. - 1970. - T. 191 , 2. sz . - S. 279-282 .
  2. ↑ Yu. V. Matiyasevics . Hilbert tizedik problémája . - M. : Nauka: Fizikai és matematikai irodalom, 1993. - 223 p. — (Matematikai logika és a matematika alapjai; 26. szám). — ISBN 502014326X .  (nem elérhető link)
  3. ↑ Hilbert jelentésének fordítása német nyelvről - M. G. Shestopal és A. V. Dorofeev , megjelent a Hilbert problémái című könyvben / szerk. P. S. Alexandrova . - M. : Nauka, 1969. - S. 39. - 240 p. — 10.700 példány. Archivált másolat (nem elérhető link) . Letöltve: 2009. november 13. Az eredetiből archiválva : 2011. október 17.. 
  4. ↑ David Hilbert . Vortrag, gehalten auf dem internationalen Mathematiker-Kongreß zu Paris 1900  (német) . - A jelentés szövege, amelyet Hilbert olvasott fel 1900. augusztus 8-án a párizsi II. Nemzetközi Matematikus Kongresszuson. Letöltve: 2009. augusztus 27. Az eredetiből archiválva : 2012. április 8..
  5. ↑ A „Rational Integer” az „integer” szinonimája, lásd Weisstein, Eric W. Rational Integer  (angolul) a Wolfram MathWorld webhelyen .
  6. ↑ V. I. Igoshin. 36. § Megoldhatatlan algoritmikus problémák // Matematikai logika és algoritmusok elmélete. - M . : Akadémia, 2004. - S. 375. - 448 p. - 5100 példány.  — ISBN 5-7695-1363-2 .
  7. ↑ Jurij Matijasevics. Hilbert tizedik problémája : Mit tehetünk a diofantin-egyenletekkel  ? Letöltve: 2009. augusztus 27. Az eredetiből archiválva : 2012. április 10..
  8. ↑ Ezt bizonyítja maga a feladat pozitív megfogalmazása is: „man soll ein Verfahren angeben” („a cselekvés menetét jelezze”, és nem például „jelezze meg, van-e eljárás”).
  9. ↑ 1 2 Yu. I. Hmelevsky. Hilbert tizedik problémájáról // Hilbert problémái / szerk. P. S. Alexandrova . - M . : Nauka, 1969. - S. 141-153. — 240 s. — 10.700 példány. Archivált másolat (nem elérhető link) . Letöltve: 2009. november 13. Az eredetiből archiválva : 2011. október 17.. 
  10. ↑ F. P. Varpakhovsky, A. N. Kolmogorov . Hilbert tizedik feladatának megoldásáról  // Kvant . - 1970. - 7. sz . - S. 38-44 .
  11. ↑ A. A. Bolibrukh . Hilbert tizedik feladata: Diofantusz-egyenletek // Hilbert-feladatok (100 évvel később) . - M. : MTSNMO , 1999. - 24 p. - ( "Matematikai oktatás" könyvtár , 2. szám). - 3000 példányban.
  12. ↑ Simon Singh. 5. függelék. Euklidész bizonyítása végtelen számú Pitagorasz-hármas létezésére // Fermat utolsó tétele = Fermat utolsó tétele / ford. angolról. Yu. A. Danilova. – MTsNMO , 2000.
  13. ↑ Alexandriai Diophantus . Számtan és könyv a sokszögszámokról / per. más görögökkel Yu. N. Veselovsky. - M. : Nauka, 1974. - 328 p. - 17 500 példány. Archivált másolat (nem elérhető link) . Letöltve: 2009. november 13. Az eredetiből archiválva : 2009. december 25.. 
  14. ↑ Leonard Eugene Dickson. A számelmélet története . - 1920. - II. köt.: Diophantine Analysis.  (Angol)
  15. ↑ A. Cs . Bemerkungen über gewisse Annäherungsbrüche algebraischer Zahlen // Videnskabs-selskabets Skrifter I Math.-Naturv. osztály. - 1908. - 3. sz . - S. 1-34 .
  16. ↑ Thoralf Skolem. Diophantische Gleichungen. - Berlin: Springer, 1938. - 128 p.
  17. ↑ Markov cikke - A. A. Markov . Egyes algoritmusok lehetetlensége az asszociatív rendszerek elméletében // A Szovjetunió Tudományos Akadémia jelentései. - M. , 1947. - T. 55 , sz. 7 . - S. 587-590 . , lásd még A. A. Markov monográfiáját . Algoritmusok elmélete  // A Szovjetunió Tudományos Akadémia Matematikai Intézetének közleménye. V. A. Steklova. - M. - L .: A Szovjetunió Tudományos Akadémia Kiadója, 1954. - T. 42 . - S. 3-375 .
  18. ↑ A Post eredményét az EL Post cikkében tették közzé . Egy csütörtöki probléma rekurzív megoldhatatlansága  //  The Journal of Symbolic Logic. - 1947. - 1. évf. 12 , sz. 1 . - P. 1-11 .
  19. ↑ Emil Leon Post . Pozitív egész számok rekurzívan felsorolható halmazai és döntési problémáik  //  Bulletin of the American Mathematical Society. - 1944. - 1. évf. 50 , iss. 5 . - P. 284-316 .
  20. ↑ Az amerikai matematikai hagyományban a 0 természetes szám.
  21. ↑ Martin Davis. Aritmetikai feladatok és rekurzívan felsorolható predikátumok  //  The Journal of Symbolic Logic. - 1953. - 1. évf. 18 , sz. 1 . - P. 33-41 .
  22. ↑ Yu. V. Matiyasevics . Hilbert tizedik problémája: Diophantine Equations in Twentieth Century // Mathematical Events of the Twentieth Century = Mathematical events of the XX century / szerk. A.A. Bolibruch , Yu. S. Osipov , Ya. G. Sinai . - Berlin: Springer , 2006. - S. 185-214. — 545 p. — ISBN 3-540-23235-4 .  (Angol)
  23. ↑ Julia Robinson. Egzisztenciális definiálhatóság az aritmetikában  //  Transactions of the American Mathematical Society. - 1952. - 1. évf. 72 , sz. 3 . - 437-449 .
  24. ↑ Martin Davis, Hilary Putnam. Hilbert tizedik problémájának redukciói  //  The Journal of Symbolic Logic. - 1958. - 1. évf. 23 , sz. 2 . - P. 183-187 .
  25. ↑ Martin Davis, Hilary Putnam, Julia Robinson. Az exponenciális diofantin egyenletek döntési problémája  //  Annals of Mathematics. - 1961. - 1. évf. 74 , sz. 3 . - P. 425-436 .
  26. ↑ Yu. V. Matiyasevics . Exponenciális-diofantin egyenletek algoritmikus megoldhatatlansága három ismeretlennel // Tanulmányok az algoritmusok elméletéből és a matematikai logikából / szerk. A. A. Markov és V. I. Khomich. - M . : Nauka, 1979. - Szám. 3 . - S. 69-78 .
  27. ↑ "Julia Robinson és Hilbert tizedik problémája  " . — ZALA Filmek. Letöltve: 2009. augusztus 27. Az eredetiből archiválva : 2012. április 10..
  28. ↑ Carol Wood. Filmszemle: Julia Robinson és Hilbert tizedik problémája  //  Az Amerikai Matematikai Társaság közleményei. - 2008. - Vol. 55 , sz. 5 . - P. 573-575 . — ISSN 00029920 .
  29. ↑ Margaret A. M. Murray. Egy saját film  //  College Mathematics Journal. – Washington, DC: Mathematical Association of America , 2009. – Vol. 40 , sz. 4 . - P. 306-310 . — ISSN 07468342 .

Irodalom

Linkek

 Hilbert problémák