Elõzõ rész

1900-ban a párizsi matematikai kongresszuson David Hilbert 23 probléma köré csoportosította a 20. század matematikájára váró legfontosabb feladatokat. Ezek lettek a híres Hilbert-problémák. Bár a századfordulón nem lehetett pontosan elõre látni, hogy a 20. században a matematika milyen fejlõdési irányt vesz (gondoljunk csak arra, hogy például a valószínûségszámítás vagy a számítógép-elmélet szinte teljes mértékig e században fejlõdött ki), Hilbert problémái jelentõs hatással voltak a matematika fejlõdésére. A problémák egy része egy-egy konkrét kérdés, mások egy-egy elmélet kifejlesztését vetik fel. Mi most három megoldhatatlansági problémát ismertetünk.

  Az 1. probléma: a kontinuum-hipotézis. Hogy a problémát megfogalmazhassuk, vegyük észre, hogy bizonyos, látszólag eltérõ nagyságú halmazok elemei között is létesíthetõ kölcsönösen egyértelmû megfeleltetés. Például a 11. ábra mutatja, hogy az egész számokból (pozitív, negatív vagy 0) és a pozitív egész számokból álló halmazok elemei között van ilyen megfeleltetés, és ugyanez az ábra ad egy ilyen megfeleltetést egy szakasz és egy kétszer olyan hosszú szakasz pontjai között.

  Megmutatható azonban, hogy egy szakasz (vagy a számegyenes) pontjai és az egész számok között nem lehet kölcsönösen egyértelmû megfeleltetést megadni. Ez az észrevétel vezetett a múlt században a halmazelmélet kifejlõdéséhez elsõsorban George Cantor német matematikus munkássága nyomán, aki két halmazt, amelyek elemei között létezik kölcsönösen egyértelmû megfeleltetés, “ugyanakkorának” tekintett. A fent említett eredmény szerint a számegyenes és az egész számok halmaza nem “ugyanakkora”, viszont minden, a számegyenesen megfigyelhetõ végtelen halmazról kiderült, hogy az vagy “ugyanakkora”, mint az egész számegyenes, vagy pedig “ugyanakkora” mint az egész számok halmaza. Például a racionális számok halmaza az egész számok halmazával, míg az irracionális számok halmaza az egész számegyenessel hozható kölcsönösen egyértelmû megfeleltetésbe. Cantor fogalmazta meg azt a hipotézist (kontinuum-hipotézis), hogy ez általában is így van, a számegyenes bármely végtelen részhalmaza vagy az egész számegyenessel, vagy pedig az egész számokkal hozható kölcsönösen egyértelmû megfeleltetésbe (és persze csak az egyikkel). Ennek eldöntése lett az 1. számú Hilbert-probléma.

  Kiderült, hogy bizonyos értelemben ennek eldöntése lehetetlen. Pontosabban a következõrõl van szó. Már a görög matematikában felmerült az az igény, hogy a matematikai állításokat bizonyos alapvetõ állításokból, ún. axiómákból vezessük le pusztán logikai úton. Az axiomatikus módszer újabb megerõsítést nyert a századforduló tájékán éppen a halmazelméletben felmerült látszólagos ellentmondások nyomán, amelyek kiküszöbölésére ismét az axiomatikus megalapozáshoz fordultak, és a mai napig ezt tekintjük a “matematikai precizitás” alapjának. Mármost a kontinuum-hipotézissel kapcsolatban kiderült, hogy sem õ maga, sem pedig a tagadása nem vezethetõ le a halmazelmélet többi axiómáiból (feltéve, hogy az axiómák között nincs ellentmondás; ha ugyanis van, akkor bármi levezethetõ). E két tényt 1963-ban Paul Cohen amerikai és 1938-ban Kurt Gödel osztrák matematikus igazolta egy-egy olyan új módszer segítségével (forszolás ill. konstruálhatóság), amely a halmazelmélet fejlõdésének rendkívüli lökést adott. Az ilyen lehetetlenségi bizonyítások az ún. modellmódszeren alapszanak: olyan modellt mutatunk, amely minden axiómának megfelel, de amelyben a kérdéses állítás (ebben az esetben a kontinuum-hipotézis vagy annak tagadása) nem teljesül. Ekkor persze az adott állítás nem is vezethetõ le az axiómákból (tulajdonképpen ugyanez a híres bolyai–Lobacsevszkij-geometria alapja: mind Bolyai János, mind pedig Nyikolaj Ivanovics Lobacsevszkij egy olyan geometriai modellt konstruáltak – “semmibõl egy új, más világot teremtettek” –, amelyben a geometria axiómái teljesülnek, de a nevezetes párhuzamossági axióma nem igaz).

  Jegyezzük meg, hogy Gödel és Cohen eredményei nem válaszolják meg a kontinuum kérdését: ma sem tudjuk, hogy igaz-e a kontinuum-hipotézis (az általunk használt “standard” számegyenesen); csak az derült ki, hogy ez logikailag eldönthetetlen a többi axiómából (azaz vannak olyan “nemstandard” számegyenesek, amelyeken igaz a kontinuum-hipotézis, meg vannak olyanok is, amelyeken nem igaz; de ez nem válaszolja meg azt a kérdést, hogy a “standard” számegyenesen igaz-e).

  A 3. probléma: poliéderek átdarabolása. Viszonylag egyszerûen igazolható, hogy bármely két azonos területû sokszög átdarabolható egymásba, azaz egyenes vágásokkal a sokszögek ugyanazokra a darabokra bonthatók (Bolyai–Gerwien-tétel). Ez annyira alapvetõ állítás, hogy gyakran használják a területfogalom kialakítására. A térbeli megfelelõ probléma nyitott maradt (a sokszög térbeli megfelelõje a poliéder), márpedig ez fontos kérdés a geometria megalapozása, pontosabban a térfogatfogalom kialakítása szempontjából. Emiatt lett ez a 3. számú Hilbert-probléma: igaz-e, hogy ugyanakkora térfogatú poliéderek átdarabolhatók egymásba? (A probléma eredeti megfogalmazása kissé más volt, tulajdonképpen azt kérdezte, hogy két azonos alapú és azonos magasságú tetraéder átdarabolható-e egymásba.) Ezt a Hilbert-problémát oldották meg leghamarabb, ugyanis Max Dehn német matematikus még ugyanabban az évben megmutatta, hogy a szabályos tetraéder (azaz egy olyan háromszög alapú piramis, amelynek minden oldala ugyanolyan hosszú) nem darabolható át kockába. A bizonyítás a dolgozat elsõ részében tárgyalt invariáns módszer: egy olyan alkalmas j függvényt kell konstruálni, amelyre egy egész test j értéke megegyezik a részek j értékei összegével, egy elmozgatott test j értéke ugyanaz, mint az eredetié, és amelyre minden kocka j értéke nulla, de a szabályos tetraéder j értéke nem az. Ilyen j létezése esetén persze azonnal következik az átdarabolás lehetetlensége.

  A 10. probléma: diofantoszi egyenletek megoldhatósága. Diofantoszi egyenletnek nevezzük az olyan sokismeretlenes egész együtthatós polinom-egyenleteket, amelyeknek pozitív egész megoldásait keressük. Például:

tipikus diofantoszi egyenletek, azonban xⁿ+yⁿ = zⁿ nem az, ha az ismeretlenek x, y, z és n (mivel itt az n ismeretlen a kitevõben szerepel), de minden egyes konkrét rögzített n-re az, azaz
 

x2+y2 = z2, x3+y3 = z3, x4+y4 = z4, ...

(3)

mindegyike diofantoszi egyenlet. Mint már említettük, a megoldásokat a pozitív egész számok között keressük. Például az elõzõ sorban az elsõ egyenlet egy megoldása x=3, y=4, z=5, egy másik x=5, y=12, z=13, és lényegében minden megoldás megkapható x = q²–p², b = 2pq és z = q²+p² alakban, ahol p és q egész számok. Ezzel ellentétben a második és harmadik egyenletnek nincs megoldása, és a híres nagy Fermat-probléma pontosan az volt, hogy az elsõ egyenlet kivételével a (3) egyenleteknek nincs megoldása az egész számok körében (ezt 1995-ben igazolta Andrew Wiles amerikai matematikus Richard Taylor segítségével).

  Mármost Hilbert 10. problémája az, hogy adjunk eljárást annak felismerésére, hogy egy adott diofantoszi egyenletnek van-e megoldása. Ez mai szóhasználattal úgy fogalmazható, hogy írjunk olyan számítógépes programot, hogy a gépnek megadva egy tetszõleges diofantoszi egyenlet együtthatóit, az véges sok lépésben eldönti, hogy az adott egyenletnek van-e megoldása a pozitív egész számok között, vagy nincs. Hangsúlyozzuk, hogy az eljárásnak minden egyenletrõl el kell tudni döntenie azt, hogy az megoldható-e. Gondoljuk meg, hogy egy ilyen eljárás mennyire hatékony lenne: már beszéltünk a (3) egyenletek megoldhatatlanságáról. Wiles elõtt több ezerrõl igazolták, hogy az adott egyenlet megoldhatatlan (például az x³+y³ = z³, ill. az x⁴+y⁴ = z⁴ egyeneltekre Leonhard Euler, minden idõk egyik legkiválóbb svájci származású matematikusa igazolta a megoldhatatlanságot), azonban ezek bizonyítása szinte minden n-re más-más gondolatot követelt. Mármost a Hilbert által kért eljárás minden egyes konkrét egyenletrõl megmutatta volna, hogy annak nincs megoldása, azaz sok-sok tételt helyettesített volna (bár a nagy Fermat-tételt nem igazolta volna pontosan abból az okból, hogy az xⁿ+yⁿ = zⁿ egyenletben n nem lehet a változók között).

  A 10. probléma megoldhatatlan: ilyen eljárás (program) megadása lehetetlen. Ezt Jurij Matijasevics orosz matematikus igazolta 1969-ben. A bizonyítás érdekessége, hogy Julia Robinson és Martin Davis munkái alapján már az ötvenes évek elején ismert volt, hogy a 10. probléma megoldása lehetetlen, feltéve, hogy létezik egy bizonyos tulajdonságú sorozat. Matijasevics azt mutatta meg (és ez persze messze nem volt egyszerû), hogy a sokat használt, és közel 700 éves Fibonacci-sorozat rendelkezik az adott tulajdonsággal.

Az 1972. évi közgazdasági Nobel-díjat (megosztva) Kenneth Arrow amerikai matematikus-közgazdász kapta. E magas elismerésben jelentõs szerepe volt Arrow egy 20 évvel korábbi dolgozatának, ugyanis Arrow 1950-ben azzal az eredménnyel lepte meg a világot, hogy bizonyos szavazási procedúrákban demokrácia lehetetlen. Bár az eredmény nem mély (a bizonyítása nem nehezebb, mint az elsõ rész 3. feladatáé és összehasonlíthatatlanul könnyebb, mint a fentiekben felsorolt matematikai tételeké), mégis érdemes röviden tárgyalni, hogy mirõl is van itt szó.

  Tételezzük fel, hogy egy közösség tagjai (akiket választóknak nevezünk és akik száma n) listás szavazáson kívánnak k jelöltet sorba állítani oly módon, hogy a szavazás során minden választó a jelölteket egy rangsorba állítja, és az így beérkezett sorrendek (listák) alapján kívánják a végsõ sorrendet felállítani. Például egy százezer felnõttet számláló városban (n=100 000) kívánnak öt jelölt közül (k=5) köztisztviselõt választani, és a végsõ lista elsõ helyezettje lesz a polgármester, a második helyezett az alpolgármester, a harmadik a jegyzõ, a negyedik a pénztáros, és az ötödik helyezett a portás. Vagy mondjuk ugyanezen város lakói eldöntik, hogy a stadion, uszoda, szabadidõpark ill. golfpálya megépítését milyen sorrendben végezzék el (ez esetben értelemszerûen négy jelölt van, azaz k=4). A beérkezõ listákat (szavazatokat) sokféle módszerrel ki lehet értékelni; de bármi legyen is a kiértékelés módszere, az elõre rögzített kell, hogy legyen, és minden lehetséges szavazási eredményre adnia kell egy végsõ sorrendet. Figyeljük meg, hogy semmi olyat nem mondtunk, hogy a legtöbb szavazatot kapott jelölt lesz a polgármester; a városlakók dönthetnek úgy, hogy mondjuk a férfiak között a legkevesebb szavazatot kapó legyen az. Állapodjunk meg abban is, hogy azt megengedjük, hogy a végeredményben “döntetlen” álljon fel bizonyos jelöltek között (azaz a végsõ listán egyik sem elõzi meg a másikat). A kiértékelés természetesen tartalmazhat preferenciákat ill. speciális szempontokat, de tételezzük fel, hogy mindenképpen teljesíti az alábbi két természetes feltételt:

  A) Ha minden lista ugyanaz, akkor az lesz a végeredmény is (azaz ha mindenki ugyanazt a sorrendet akarja, akkor valóban az legyen a végeredmény),

  B) Függetlenség: hogy két jelölt, X és Y közül a végleges listán melyik elõzi meg a másikat, csak attól függ, hogy az egyes szavazók az X és az Y közül melyiket helyezték a másik elébe, és nem függ attól, hogy a további jelölteket ezekhez képest hogyan rangsorolták. Másszóval, ha van két szavazásunk, és a két szavazás során minden egyes személy szavazólapjain X és Y ugyanolyan sorrendben van (persze lehet, hogy az egyik szavazónál X elõzi meg Y-t, míg egy másiknál fordítva, Y elõzi meg X-et), akkor a két szavazás kimenetele az X és Y szempontjából azonos: vagy mindkettõben X elõzi meg Y-t, vagy mindkettõben Y elõzi meg X-et, vagy mindkétszer döntetlen van az X és Y között.

  Vegyük észre, hogy a fenti feltételeknek még a diktatúra is megfelel, ugyanis ha van egy diktátor, akinek a szavazata lesz a végeredmény a többiek szavazatától függetlenül, akkor ez a kiértékelési eljárás nyilván teljesíti az A és B feltételeket. Hogy demokratikus legyen a választás, követeljük még meg, hogy

  C) Nincs diktátor (azaz olyan ember, akinek a szavazata adja a végeredményt).

  Lehetnének további demokratikus kikötések (mint például, hogy az egyes emberek szavazata ugyanannyit számítson), de feleslegesek, mert már a fentiek sem teljesíthetõk, ugyanis, Arrow lehetetlenségi tétele szerint ha legalább három jelölt van, , akkor nincs olyan kiértékelési eljárás, amely az A, B és C feltételeknek eleget tenne. Jegyezzük meg, hogy ha csak két jelölt van, és az nyer, aki több szavazatot kap (szavazategyenlõségnél legyen döntetlen), akkor ez a többségi eljárás nyilvánvalóan teljesíti az A, B és C feltételeket. A dolog nyitja az ártatlannak tûnõ függetlenségi B feltételben van, ugyanis A és B alapján alkalmas szavazási listákat ügyesen használva szûkebb és szûkebb diktátorcsoportokat lehet mutatni a szavazók között, mígnem egyetlen emberbõl áll a végén a csoport, és az diktátor lesz.

  Itt meg is állunk a lehetetlenségi eredmények bemutatásával, bár a sort sokáig lehetne folytatni. Mint láttuk, ilyen tételek természetesen adódnak a matematika belsõ harmóniájából és a matematikai tudomány fejlõdésébõl. A lehetetlenségi eredmények gyakran egy-egy sokat vizsgált témakört zárnak le (mint pl. az ötödfokú egyenletek megoldóképlete, vagy a kör négyszögesítése); legtöbbször egy új fejlõdési irányt indítanak el (szinte minden fenti eredmény kiindulópontja egy új matematikai területnek), de az is elõfordul, hogy krízisszerû helyzetet idéznek elõ (mint például a görögök számára az a tény, hogy 2 nem áll elõ p/q alakban, ahol p és q egész számok, vagy gondoljunk Gödel nemteljességi tételeire). Tulajdonképpen minden valamirevaló matematikai eredmény mellett ott van, vagy ott kell, hogy legyen egy javíthatatlansági tétel, amely azt mondja ki, hogy az adott eredmény lényeges javítása lehetetlen. Ez adja meg az eredmények teljességét, és ad bizonyos értelemben garanciát arra, hogy amit csinálunk, annak van értelme.