Bodnár József
Bizonyítás vagy bizonyíték? Az igazság vágya. Egy tudomány születése A matematika hosszú évszázadokig “receptek” gyűjteménye volt csupán. Az ősi kultúrák sok matematikai eredményt ismertek, de nem olyan formában, amilyenben mi: képletekről szó sem volt, bizonyos dolgok kiszámításának módját konkrét példákon, konkrét számértékekkel adták meg. Az i. e. 1800 körüli évekből származó egyiptomi moszkvai papiruszon szerepel a csonka gúla térfogatszámítása, az eljárást konkrét értékekkel írták le. Az eredmény korántsem triviális, a babiloniak például hibásan ismerték. De annak nyomát sem találjuk, minderre hogyan jöttek rá. Arról nem is beszélve, hogy az eredmények helyességét bizonyítsák. 1600 évvel később viszont Arkhimédész már a következőt írja: 1 “Néhány dolgot ugyanis, amely először mechanikai módszerrel vált világossá előttem, geometriailag is bebizonyítottam, mert vizsgálatuk a mondott módszerrel nem tekinthető tényleges bizonyításnak.” Arkhimédész nemcsak hogy részletesen leírja azokat az intuitív megfontolásokat, melyek a legkevésbé sem nyilvánvaló eredményeire vezetik, de időt és fáradságot nem kímélve az eredmény ismeretében a legapróbb részletekig szigorú geometriai bizonyítást ad tételeire. Mindez azt mutatja, hogy teljesen tudatában volt annak, hogy hasonlóan homályos gondolatmenettel esetleg hibás állításokhoz is juthatott volna. Pedagógusok véleménye szerint a matematikaórán a bizonyítási feladatok jelentik a legnagyobb nehézséget. Ennek egyik oka talán az, hogy egy bizonyítási feladat célja valami egészen más, mint például egy szöveges feladaté: olyasvalami, amire a puszta igény is csak évszázadok alatt alakult ki az emberi gondolkodásban. A bizonyítási eljárások elsajátításának csak az után jöhet el az ideje, hogy az ember tudatosítja: az “eddig még mindig igaznak bizonyult” és a “biztosan igaz” nem ugyanazt jelenti. 2
1
Idézi: Simonyi Károly: A fizika kultúrtörténete, negyedik, átdolgozott kiadás, Akadémiai Kiadó, Budapest, 1998, p. 92., 1.4 -2 idézet (A rkh imédész: A módszerrő l) 2 Ezzel kapcsolatban lásd Horváth Géza: Fejleszthető-e az alkotóképesség? Katedra Füzetek, Liliu m Auru m, Dunaszerdahely, 1997, pp. 25 – 26.
Vegyük például a következő feladatot:3 adott egy négyszer négyes tábla, melynek két szembeni saroknégyzetét “letörték”. Kirakható-e ez a hiányos tábla egyszer kettes dominókkal? Ha egy kevés ideig próbálkozunk, az a meggyőződés alakul ki bennünk, hogy a táblát nem lehet kirakni. Érvelhetünk azzal, hogy minden lehetőséget végignéztünk és egyik sem vezetett eredményre. Ilyen egyszerű feladatnál ez el is fogadható: ügyes stratégiával (például visszalépéses, “backtrack” kereséssel) viszonylag kevés eset felsorolása után végzünk. Gondoljuk meg azonban, mi lenne, ha nagyobb, mondjuk nyolcszor nyolcas táblára kérdeznénk ugyanezt (két szembeni saroknégyzet hiányzik). Itt már annyi esettel kéne számolnunk, hogy aligha bírnánk idővel, türelemmel és figyelemmel. Ezenkívül nem látjuk semmilyen mélyebb okát annak, hogy a kirakás lehetetlen. Annyit látunk, hogy sehogyan sem akar sikerülni (1. ábra).
1. ábra: Bizonyíték
és bizonyítás – az előbbi is meggyőzhet minket, de az okot csak az utóbbi mutatja meg A probléma “igazi”, matematikai bizonyítása a következő: színezzük a táblát sakktáblaszerűen. Mivel két szembeni sarokmező hiányzik és ezek azonos színűek voltak, az egyikféle színű mezőből most kettővel több van, mint a másikféléből. De egy egyszer kettes dominó mindig egyszerre fed le egy sötét és egy világos mezőt, így dominókkal csak olyan területet lehet kirakni, melyen a sötét és világos mezők száma megegyezik. A törött sarkú táblánk nem ilyen (sem a négyszer négyes, sem a nyolcszor nyolcas), így ezeket nem lehet kirakni. Ez a bizonyítás. Ez az egyszerű példa kiválóan érzékelteti a matematikai bizonyítás legfőbb tulajdonságait: az univerzalitást, az esztétikumot és a “láthatatlan megjelenítését” (ez utóbbi kifejezés Keith Devlintől származik, aki a rejtett okok feltárására utalt vele). Ezek a tulajdonságok tették alkalmassá a matematikát, hogy csábító erő legyen a világ megértésére. 3
A példa szerepel Simon Singh: A nagy Fermat-sejtés című könyvében (Simon Singh: Velká Fermatova veta, Academia, Praha, 2002, pp. 24 – 27.)
A bizonyítással az ember bizonyos formában elérhette néhány ősi vágyát: az időtlenséget, az igazságot, a tökéletességet, melyek hatására filozófusok és tudósok ére zhették isteni magasságokban magukat. Senki sem gondolt arra, hogy néhány, addig még föl sem tett kérdés arra vár, hogy könyörtelenül éreztesse velünk emberi mivoltunkat. Egy botanikus kifestője. Fogas kérdés A történet 1852-ben kezdődött, amikor Francis Guthrie, 21 éves egyetemi hallgató Anglia térképével játszogatott. Szerette volna úgy kiszínezni a grófságokat, hogy egymással határos területek különböző színt kapjanak. Ehhez mindössze négy szín elegendőnek bizonyult. Guthrie azt kérdezte, vajon elég-e négy szín minden elképzelhető térképhez. (Valójában e miatt az egyetlen kérdése miatt vált híressé a matematikában: később botanikus lett Dél-Afrikában, néhány növényfaj azóta is a nevét viseli.) A kérdés természetes és egyszerű; várhatóan meg is válaszolható. Az ilyen “légből kapott” kérdésekkel azonban nem árt óvatosan bánni. Nagyon könnyen előfordulhat ugyanis, hogy a válaszhoz vezető út korántsem olyan barátságos, mint a kérdés. Guthrie mindenesetre megkérdezte testvérét, Fredericket, aki matematikatanárá hoz, de Morganhoz fordult. Azonban a matematikus is zavarba jött. Éveken keresztül mind többek vallottak kudarcot a problémával kapcsolatban. Ez a sorozatos sikertelenség jelezhette azt, hogy a probléma megoldásához olyan matematikai módszerekre van szüksé g, melyek kifejlesztése még a jövő feladata, de akár azt is, hogy csak egy apró, ügyes ötlet hiányzik, ami eddig még senkinek sem jutott eszébe. Váratlan fordulatok sokaságát tartogatta még a kérdés. A térkép eltűnik. A mate matika színre lép Hogyan nyúl a matematika egy olyan kérdéshez, mint amilyen a térképszínezés problémája? Először is le kell hámoznunk a lényegtelen részeket. A feladat szempontjából nyilvánvalóan teljesen irreleváns egy szóban forgó térkép országainak területnagysága. Az egyetlen, ami számít, az az, hogy mely országok határosak egymással. Itt jegyezzük meg, hogy a kérdést csak olyan térképekre érdemes föltenni, melyeken minden ország területe összefüggő (nem engedünk meg tehát olyan, a gyakorlatban mindazonáltal előforduló eseteket, mint például Alaszkáé vagy Oroszország kalinyingrádi területéé). Ellenkező esetben ugyanis könnyen készíthetnénk olyan térképeket, melyeket csak egy előre megadott számú
színnel lehet színezni, rámutatván néhány egymástól távoli területre, hogy azoknak azonos színűeknek kell lenniük. Most a kérdés egy olyan átfogalmazását adjuk, melyről azonnal látszani fog, hogy ténylegesen az általunk megragadni kívánt részletekkel foglalkozik, mindamellett matematikailag könnyebben leírható, mint egy “térkép”. Azt mondtuk, az az egyedüli fontos információ, hogy mely országok határosak egymással. Képzeljük el, hogy minden országba berajzolunk egy fővárost; tetszőleges helyre. Ezután minden, egymással szomszédos ország fővárosát kössük össze egy, a két ország közös határszakaszán áthaladó útvonallal. Ez megtehető úgy, hogy az utak sehol sem keresztezik egymást (2. ábra). És most felejtsük el az országok határait. Minden országot egy “pont”, a fővárosa képvisel. És azt is rögzítettük, melyek szomszédosak egymással: azok, amelyek fővárosai közt vezet út. A kérdés most így szól: Lehet-e minden fővárosnak (“pontnak”) – négy előre megadott szín közül – színt
2. ábra: Térképből gráf
készül
adni úgy, hogy egymással úttal (“vonallal”) összekötött városok mindig különböző színt kapjanak? Az ilyen, “pontokból” és az azokat összekötő “vonalakból” álló objektumokat már ismeri a matematika: ezek a gráfok. A pontokat a gráf csúcsainak, a vonalakat az éleinek nevezzük. A térképből létrehozott gráfunknak viszont még van egy fontos extra tulajdonsága is: élei nem keresztezik, nem metszik egymást. Matematikailag két gráf teljesen egyformának számít, ha ugyanannyi csúcsuk van és azokat meg lehet egymásnak feleltetni úgy, hogy élek élekbe mennek át, azaz ha a két gráf ugyanannyi pont között ugyanazt a viszonyrendszert szemlélteti. Magyarán: gráfelméletileg teljesen mindegy, hogy egy gráf hogy van lerajzolva. Az azonban, hogy az élek metszik-e egymást, egy “lerajzolásfüggő”, azaz nem gráfelméleti tulajdonság. Az viszont már egyértelműen meghatározott, gráfelméletileg is jól jelleme zhető tulajdonság (Kuratowski-tétel), hogy egy gráfot lehetséges-e úgy lerajzolni, hogy az élei ne messék egymást. Az ilyen gráfokat síkbarajzolható, vagy röviden síkgráfoknak hívjuk. Kérdésünk tehát: minden síkgráf színezhető négy színnel? (Természetesen a csúcsokat akarjuk színezni úgy, hogy összekötött csúcsok ne legyenek egyforma színűek.) Az, hogy legalább négy színre szükség van, világos; három szín ugyanis még egy egyszerű
síkgráfhoz sem elég. A síkgráfokról az 1800-as évek végére már sok mindent tudtak. Bárki érezheti például, hogy egy ilyen gráf nem lehet túlságosan “sűrű”: csúcsszámához képest viszonylag kevés élt tartalmaz. Egy ilyen jellegű tételt fogalmazott meg Euler, melynek kimondásához még egy fogalomra szükségünk van. Rajzoljunk le egy síkgráfot. A legtöbb esetben ezzel a síkot területekre osztottuk: bizonyos területeket körbezárnak a gráfunk élei. (Vigyázzunk, ezek nem azok az “országok”, melyekből a gráf keletkezett!) Ezeket hívjuk a síkgráf lapjainak. Lapnak számítsuk a gráfunk “körüli” maradék – nem korlátos – síkterületet is. Számoljuk össze a lapokat (l) és a csúcsokat (c). Számoljuk meg az éleket is (e). Az előbbi kettő összegéből vonjuk ki az utóbbit. És most jön Euler tétele: eredményül mindig kettőt kell kapnunk. (c – e + l = 2). A 2. ábrán látható gráfra például 7 – 13 + 8 = 2. E tétel bizonyítása 4 egyszerű és tanulságos: kezdjük el lerajzolni síkgráfunkat. Először leteszünk egy csúcsot. Erre az egycsúcsú, él nélküli gráfra igaz a tétel: egy csúcsa, nulla éle és egy lapja (a pontot körülvevő sík) van. Ezután folytassuk a rajzot lépésenként a következőképp: egy már meglevő pontból húzunk egy élet és a végére új csúcsot teszünk, vagy már meglevő két csúcsot kötünk össze éllel. Nyilvánvalóan ilyen lépésekkel tetszőleges síkgráf megrajzolható. Hogyan változik egy-egy lépésnél a c – e + l érték? Első esetben az élszám is, a csúcsszám is eggyel megnő. A kifejezés értéke tehát nem változik. Második esetben új csúcsot nem rajzolunk, de az élszám eggyel nő. Gondoljuk viszont meg, hogy nő a lapszám is: egy már létező területet kettéosztunk az új éllel. A c – e + l érték tehát megint nem változik. És mivel kezdetben értéke 2 volt, a rajz végére is annyi marad. Kész. Euler tételéből a síkgráfok “ritkaságának” egy érdekes megfogalmazása következik. Azt, hogy egy adott csúcshoz hány él csatlakozik, az illető csúcs fokszámának hívjuk. Nem nehéz belátni, hogy minden síkgráfban van legfeljebb ötfokú csúcs. Ha ugyanis nem így lenne, akkor minden csúcsból legalább hat él indulna, azaz az élek száma legalább háromszorosa lenne a csúcsszámnak (a hatot osztjuk kettővel, mert minden él két csúcshoz tartozik, így mindegyiket kétszer számoltuk), vagyis e 3c. Minden lapot élek határolnak, legalább három (élekből álló sokszögek, persze “legalább háromszögek”): így e (3/2)l. (Megint osztunk kettővel, mert minden él két lap határának részét képezi.) De az Euler-összefüggés szerint e = c + l – 2, azaz az egyik egyenlőtlenség azt mondja, hogy l – 2 2c, a másik meg azt, hogy 2c – 4 l, és ez a két becslés egyidejűleg nem
4
Ez a bizonyítás kissé más megfogalmazásban szerepel az alábbi könyvben: Keith Devlin: Matemat ika: a láthatatlan meg jelenítése, Műszaki Kiadó, Typotex Kiadó, Budapest, 2001, pp. 213 – 215.
lehet helyes. Mégsem lehet tehát ilyen sok él: e 3c mégsem igaz: van legfeljebb 5 fokú csúcs. Bizonyításunk az indirekt okoskodás klasszikus esete. Mihez kezdhetünk ezzel az információval? Vegyük észre, hogy ebből a tételből a “hatszín-tétel” szinte azonnal következik – azaz az, hogy minden síkgráf (“térkép”) színezhető hat színnel. A bizonyítás egy másik fontos módszert, a teljes indukciót alkalmazza. Tekintsünk egy tetszőleges síkgráfot. Nagyon fontos, hogy amit most mondunk, az minden síkgráfra igaz. Bármilyen is a síkgráfunk, láttuk, hogy biztosan van benne legfeljebb 5 fokú csúcs. Töröljük le átmenetileg ezt a kevés szomszédú csúcsot és a belőle induló (legfeljebb 5 darab) élt (a szomszédait ne!). Most egy eggyel kevesebb csúccsal rendelkező síkgráfot kaptunk. Ha ezt ki tudnánk színezni legfeljebb hat színnel, akkor az eredetit is. Mert tegyük föl, hogy ezt a kisebbet már kiszíneztük; rajzoljuk most rá vissza a letörölt éleket és csúcsot. A csúcsnak legfeljebb öt szomszédja van, összesen legfeljebb ötféle színnel. De nekünk hat színünk van: színezzük hát a hatodikra az utolsó színtelen csúcsot, és kész: az egész gráfot kiszíneztük. Jó, de honnan tudjuk, hogy színezhető hat színnel az az eggyel kisebb gráf? Egyelőre nem tudjuk. De mindaz, amit az előbb elmondtunk, minden gráfra igaz, így erre a kisebbre is: van egy legfeljebb ötfokú csúcsa, azt letörölve ha a maradék színezhető, akkor ez is.... és így tovább. A csúcsok lassan elfogynak, végül oda jutunk, hogy ha minden 6 csúcsú gráf színezhető hat színnel, akkor minden hétcsúcsú is. De akármilyen hatcsúcsú gráf egészen biztosan színezhető hat színnel: egyszerűen adjunk minden csúcsnak különböző színt. De akkor minden hét-, így minden nyolc-, így minden kilenccsúcsú... így tetszőleges csúcsszámú síkgráf, azaz minden síkgráf színezhető hat színnel, és ezzel készen vagyunk! Az előző gondolatmenetet kevésbé szemléletesen, de sokkal tömörebben is elmondhatjuk: Tegyük föl, hogy vannak hat színnel nem színezhető síkgráfok (esetleg csak egy, esetleg végtelen sok). Nézzük ezek csúcsszámait. Ezen csúcsszámok között van legkisebb. Vegyünk egy ilyen legkisebb, hat színnel nem színezhető síkgráfot (ha több minimális csúcsszámú van, vegyünk egy tetszőleges ilyet). Ennek is van legfeljebb 5 fokú csúcsa. Ezt és a csatlakozó éleket elhagyva kisebb csúcsszámú gráfhoz jutunk. De mivel az eredeti gráf egy minimális ellenpélda volt, ez a kisebb gráf már színezhető hat színnel, és akkor, amint azt már láttuk, az eredeti is, azaz mégsem ellenpélda. Ez az ellentmondás bizonyítja az állítást. Tudjuk tehát, hogy három szín még a legegyszerűbb síkgráfokhoz sem elég, hat azonban már tetszőlegeshez elegendő. Ha azt kérdezzük, mi az a minimális színszám, amivel
tetszőleges térkép kiszínezhető, a válasz: legalább négy és legfeljebb hat. Sokan mindent megpróbáltak, hogy ezt a felső becslést kettővel lejjebb szorítsák. Egy mate matikus láncai. Sejtésből tétel Az előrelépés, úgy tűnt, 1879-ben történt meg. Alfred Kempe angol matematikus előállt a négyszín- tétel bizonyításával. Úgy látszott, nem a matematikai apparátus hiányzott eddig a probléma megoldásához, hanem egy ötlet. Egy ötlet, melyet azóta is Kempeláncoknak hívnak, és különféle gráfok kromatikus számának vizsgálatakor hasznos segédeszköznek bizonyult. Kempe gondolatmenetének 5 alapja szintén az indukció volt. Tudjuk, hogy elég lenne a következő állítást belátni: egy síkgráf színezhető négy színnel, ha egy csúcsát és az abból induló éleket elhagyva a maradék színezhető négy színnel. (Hasonlóan a hatszín-tételhez, de most ne a hat, hanem a négycsúcsú gráfoknál álljunk meg: ezek biztosan színezhetők négy színnel.) Kézenfekvőnek tűnik a kevés szomszéddal rendelkező, biztosan létező legfeljebb ötfokú csúcs elhagyásával próbálkozni, ahogyan ezt a hatszín- tételnél tettük. Igen ám, de most a csúcsnak a színszámhoz képest túl sok szomszédja lehet: az esetleg öt szomszéd közt nagyon könnyen előfordulhat mind a négy szóba jöhető szín, és ekkor nem tudunk a hiányzó csúcsnak jó színt adni. Az ötlet a következő: Igen, lehet, hogy ezen eggyel kisebb gráf színezése olyan, hogy az utolsó, még szín nélküli csúcs szomszédai között mind a négy használható szín előfordul, de hátha van másféle színezése is ennek az eggyel kisebb gráfnak? Nem tudnánk valahány csúcsot úgy átfesteni, hogy a színezés továbbra is jó maradjon, de megszabaduljunk az egyik színtől a szomszédok között, és a színtelen csúcs szomszédai már csak legfeljebb háromféle színűek legyenek? Pontosan ezt tette Alfred Kempe. Mindenekelőtt szögezzük le, hogy ha a kiválasztott legfeljebb 5 fokú csúcsunknak négynél kevesebb szomszédja van, akkor nem lehet baj: szomszédai legfeljebb háromféle színűek. Mindössze két problémás esettel kell foglalkoznunk: ha a csúcsunknak négy, csupa különböző színű szomszédja van, vagy ha csúcsunknak öt szomszédja van, és azok színei között mind a négy szín előfordul (ilyenkor természetesen két csúcs közülük mindig egyforma színű). Nézzük az első lehetőséget: számozzuk a színeket úgy, hogy a még színtelen csúcs körüli csúcsoknál az 1-es és a 3-as, illetve a 2-es és a 4-es szín legyen egymással szemben. Nem tudnánk mégis ezt a színtelen csúcsot 1-es színűre festeni? De igen, ha az 1-es színű 5
Kempe itt vázo lt gondolatai az alábbi weboldalon vannak is mertetve: http://www.stonehill.edu/compsci/ LC/Four-Color/Four-color.ht m (lásd internetes hivatkozások)
szomszédját átfestjük valami másra. Fessük a szemben levő színre (később látni fogjuk, ez miért lesz jó), 3-asra. Jó, de ennek az eredetileg 1-es, most 3-as színű csúcsnak lehetnek 3-as színű szomszédai! Ezeket is át kéne festeni: fessük mindegyiket 1-esre. Az ebben a lépésben átfestett csúcsokkal szomszédos minden 1-es színű csúcsot fessünk 3-asra, és így tovább. Az eljárás valahol megáll. Tulajdonképpen az történik, hogy az először átfestett 1-es színű csúcsból kiindulva megnézzük, melyek azok az 1-es vagy 3-as színű csúcsok, melyek elérhetők váltakozva 1-3 színű csúcsokat érintő útvonalon, és ezen csúcsok mindegyikén kicseréljük az 1-es és a 3-as színt. Ha az eredeti színezés jó volt, akkor ez is jó lesz. Nyertünk ezzel valamit? Ha a színcsere nem érte el az elsőnek átfestett csúccsal szembeni 3-as színű csúcsot, akkor igen: ez esetben ugyanis eltűnt az 1-es szín a még színtelen csúcs szomszédainak színei közül, így azt festhetjük 1-esre. (3. ábra)
3. ábra: Egy sikeres átszínezés – és ahogy a sikertelenből előnyt kovácsolunk Baj van azonban, ha a színcsere azt a csúcsot is elérte: ilyenkor csak annyi történt, hogy a színtelen csúcsunk 1-es színű szomszédja 3-as színűre és a 3-as pedig 1-es színűre változott, és nem tudunk mit kezdeni színtelen csúcsunkkal. De tudunk egy fontos dolgot. Miért érte el a színcsere a szembeni csúcsot? Mert létezik egy váltakozva 1-es 3-as színű csúcsokból álló lánc, úgynevezett Kempe-lánc a két szembeni csúcs között. Mire jó ez? Mindjárt meglátjuk. Próbálkozzunk meg újra az előbbi eljárással, de most a 2-es színű csúccsal kezdjük, és 2-es 4-es színcserét végezzünk. Ha ez sikerül úgy, hogy nem érjük el a szembeni 4-es színű csúcsot, nyertünk. De mi van, ha megint elérjük? Azaz ha van egy váltakozó 2-4 színű csúcsokból álló lánc ezen csúcspár tagjai között is? Nos, ilyen egészen biztosan nincs. Mit jelentene ez ugyanis? Mivel mindkét lánc szembeni csúcsok között fut, valahol keresztezik egymást. Csúcsban nem keresztezhetik egymást, mert az egyik lánc minden csúcsa 1-es vagy
3-as színű, a másiké meg 2-es vagy 4-es színű. A lánc élei sem keresztezhetik egymást, hiszen síkgráfról van szó. Az egyik színcsere tehát biztosan sikeres, ha az első nem, a második. Megszabadulunk valamelyik színtől a szomszédok között, és színtelen csúcsunkat ilyenre festjük. Ezzel a négy szomszéd esetét elintéztük. Mi van az öt szomszéd lehetőségével? Négy szín öt szomszédos csúcson, azaz van két egyforma színű, mondjuk 4-es. Ha ezek egymás mellett helyezkednek el, könnyű meggondolni, hogy az előbbi módszer megint célravezető. (A színcseréket megint “szembeni” színekkel végezzük, és mindig olyan színnel indulunk, melyből csak egy van a szomszédok között: először próbálkozunk 1-3-mal, majd ha nem sikerült, a 2-ből induló 2-4 csere biztosan jó lesz.) Egy kis gond van, ha a két 4-es színű csúcs nem egymás melletti (ekkor egyik oldalon egy csúcs, mondjuk 1-es színű, a másik oldalon kettő, 2-es és 3-as színű van közöttük). Most próbáljuk először az 1-ből indulva az 1-2 cserét. Ha sikerült, nyertünk, ha nem, van egy 1-2 váltakozó lánc. Próbáljuk most ki az 1-3 cserét szintén az 1-ből indulva. Ha sikerült, készen vagyunk, ha nem, van egy 1-3 váltakozó lánc. Kempe ötlete a következő volt: próbáljunk meg megszabadulni a két 4es színű szomszédtól (4. ábra). Az 1-3 lánccal körülvett 4-esből indítsunk egy 4-2 cserét, ez a lánc miatt nem érheti el a 2-es színű szomszédot. Az 1-2 lánccal
4. ábra: A nagy ötlet
körülvett 4-esből pedig indítsunk egy 4-3 cserét, ez a másik lánc miatt nem érheti el a 3-as szomszédot. Így sikerült az egyik 4-es szomszédot 2-esre, a másikat 3-asra festeni: az új csúcs immár kaphatja a 4-es színt! Ezzel kész! Úgy látszik, Kempe egy ügyes ötlettel megoldotta a 27 éves problémát. A négyszín-sejtés négyszín-tétellé lett.
Tételből sejtés. Az öts zín-tétel 11 évvel később megjelent egy angol matematikus, Percy John Heawood, és bebizonyította, hogy minden térkép színezhető öt színnel. Mi történt? Kempe szerint elég legfeljebb négy szín, akkor nyilván elég legfeljebb öt... Mit csinált hát Heawood? Nos, megmutatta, hogy Kempe bizonyítása rossz. A gondolatmenet, melyet annyi év után örömmel és fellélegezve üdvözöltek, hibás. A probléma a következő:6 előfordulhat, hogy a második, 4-esből induló színcserét nem lehet megcsinálni. Ennek okát igen egyszerűen szemléltethetjük: az 5. ábrán ott van az 1-2 és az 1-3 lánc, de azok korántsem olyan “szépen” helyezkednek el, mint képzeltük. Mivel az 1-es szín mindkettőben előfordul, ezért a két
5. ábra: A nagy hiba
lánc átfűződhet egymáson, és az egyiknek egy 2-es, a másiknak egy 3-as színű csúcsa között vezethet él, hisz különböző színűek. Azonban a két 4-esből induló színcsere a láncok átfűződése miatt elérheti ezeket az összekötött csúcsokat, és ennek során mindkettő 4-es színűvé válik, ami hibás színezés, hiszen élekkel összekötött csúcsok nem kaphatnak azonos színt. Ez tehát a hiba, melyről gondos vizsgálatok megállapították, hogy kijavíthatatlan. Kempe munkája mindazonáltal nem volt hiábavaló: először is Heawood megmutatta, hogy ugyanezzel a módszerrel az belátható, hogy öt szín elég: ekkor csak az az eset marad, mikor a még színtelen utolsó csúcsnak öt szomszédja van, és azok csupa különböző színűek. Ekkor ahhoz az előbb látott esethez hasonló a helyzet, mikor a két 4-es színű csúcs egymás melletti volt. Most képzeljük el, hogy közülük az egyik egy új, 5-ös színű, és a gondolatmenetet változatlanul hagyva az ötszín-tétel bizonyítása kész. (Ha úgy képzeljük, hogy az 1 és 3 színű csúcsok nem egymás mellettiek, és egyik oldalukon a 4 és 5 színű van, másik oldalukon pedig a 2-es, akkor ha van 1-3 lánc, akkor a 2-ből induló 2-4 csere sikerül.)
6
A Kempe-féle bizonyítás hibája szintén ismertetve van az említett weboldalon, hasonló ábrával magyarázva.
Másrészt Kempe gondolata a váltakozó színű láncokkal jó módszernek bizonyult. Sok további kutatás központjában ezek a láncok álltak. De a négy szín túl kevésnek tűnt. Semmivel nem lehetett leszorítani a színtelen csúcs szomszédainak lehetséges színeit négy alá. Türelemjáték. Lehetőségek sokasága Már Kempe hibájának vadászatakor érezhető volt, hogy lényeges problémát jelent a túl sok lehetőség. Eleinte senki nem gondolt az átfűződő láncok lehetőségére. A matematikus munkájához elengedhetetlen az alaposság, melyhez türelem és kitartás szükséges. És ötlet. Az eddigi próbálkozások lényege röviden a következő volt: tegyük föl, hogy létezik a négyszín-tételre ellenpélda. Vegyünk egy minimális ilyet. (Egy lehető legkevesebb csúcsszámút.) Egy megfelelő csúcs elhagyásával mutassuk meg, hogy mégsem lehet ellenpélda, mert a maradéknak létezik olyan színezése, mely az eredetire is kiterjeszthető. Mi van, ha eddig azért nem sikerült a bizonyítás, mert így nem is lehet megcsinálni? Talán több lehetőséget kéne figyelembe venni. Hátha a probléma olyan összetett, hogy nem lehet egy csúcs elhagyásával bizonyítani. Ne ezzel próbálkozzunk. A modellt hagyjuk meg, de egy csúcs helyett többet hagyjunk el. Hagyjunk el egy megfelelő részgráfot, és erre terjesszük ki a maradék megfelelő színezését. 7 De milyen részgráfokkal próbálkozhatunk? Az egyetlen csúcsból álló legegyszerűbbet már megpróbáltuk. Mik vezethetnek eredményre? Próbáljuk meg összegyűjteni az összes olyan részgráfot, melyek sikerrel kecsegtetnek. Nyilván csak olyan részgráfok érdekelnek minket, melyek egy esetleges minimális ellenpéldában előfordulhatnak. Különböző gráfelméleti módszerekkel bizonyos tulajdonságai kimutathatók egy ilyen minimális ellenpéldának. Emlékezzünk az Euler-tételben szereplő lapokra, azokra a régiókra, melyekre a gráf lerajzolásakor a síkot osztjuk. Ezeket a gráfok élei határolják, mindegyiket nyilván legalább három. Könnyű megmutatni, hogy egy minimális ellenpéldában minden lap háromszög. Ugyanis tegyük föl ennek ellenkezőjét, hogy van egy olyan lap, mely legalább négyszög. Ekkor ennek van két olyan csúcsa, melyek nincsenek éllel összekötve. Húzzuk össze ezt a két csúcsot egyetlen csúccsá, azaz helyettesítsük eggyel úgy, hogy ahhoz az egyhez csatlakozzon minden olyan él, mely eredetileg a két összehúzott csúcs közül valamelyikhez csatlakozott. Ez egy kisebb gráf, és ellenpéldánk minimális volt, tehát ez már
színezhető négy színnel. Az összehúzott csúcs is kap valamilyen színt, mondjuk az 1-est. De akkor az eredeti gráfunkat is ki tudjuk színezni: annak a két csúcsnak, amiket összehúztunk, adhatjuk ugyanazt a színt, az 1-est, hiszen nincsenek éllel összekötve. Gráfunk tehát mégsem lehet minimális ellenpélda, ellentmondás. Tehát minden minimális ellenpélda (ha van egyáltalán ilyen) minden lapja háromszög. A fenti bizonyításból az alapelv tökéletesen látszik: a négyszín- tétel bizonyítását valahogy úgy akarjuk végezni, hogy minden gráf színezését kisebb gráfokéra vezetjük vissza. Egy gráf nem lehet minimális ellenpélda, ha egy megfelelő színezése következik egy nála kisebb csúcsszámú gráf megfelelő színezéséből. Nevezzük az ilyen gráfokat redukálhatóknak. Az előző bekezdésbeli gondolatmenet tehát azt mutatja, hogy minden olyan síkgráf, melynek van nem háromszög lapja, redukálható. A négyszín-tétel bizonyítást nyer, ha megmutatjuk, hogy minden minimális ellenpélda-jelölt redukálható. A redukálhatóságot úgy szeretnénk egy-egy gráfról megmutatni, hogy bizonyos gráfokról kimutatjuk, hogy ha azok részgráfként szerepelnek egy gráfban, akkor az redukálható. Az ilyen tulajdonságú részgráfokat nevezzük redukálható konfigurációknak. A konfigurációk igazából nem csupán részgráfok: bizonyos kikötéseket is teszünk ugyanis a konfigurációk csúcsainak nagyobb gráfbeli fokszámára, tehát megmondjuk, hány szomszédja kell legyen a konfiguráció-részgráf egyes csúcsainak a nagy gráfban. Ezzel lényegében a részgráf beágyazására szeretnénk utalni. Az eddigiek alapján tehát mondhatnánk, hogy egy ötnél kisebb fokú csúcs vagy egy háromnál hosszabb kör, melynek “belseje üres”, redukálható konfiguráció, hiszen láttuk már, hogy ha egy gráf tartalmazza ezek valamelyikét, akkor redukálható, azaz színezése következik egy nála kisebb (kevesebb csúcsú) gráf színezéséből. (Itt látszik, miért szeretnénk a konfiguráció fogalmába beleérteni a csúcsok fokszámaira való megkötéseket is: a legfeljebb négyfokú csúcs mint részgráf egyetlen csúcsból áll, de kikötjük, mennyi szomszédja legyen: ötnél kevesebb.) Ennek ellenére ezeket ne tekintsük redukálható konfigurációknak: egyszerűen mondjuk azt, hogy csak olyan gráfokat vizsgálunk, melyeknek minden csúcsa legalább ötfokú és minden lapja háromszög (háromszögelt gráf), hiszen ezek a potenciális minimális ellenpélda-jelöltek. Nevezzük ezeket “jó jelölteknek”. Ilyenekről szeretnénk megmutatni, hogy redukálhatók, azaz most már csak olyan redukálható konfigurációkat keresünk, melyek az ilyen gráfokban fordulhatnak elő. Ezzel némileg egyszerűsítettük a
7
A probléma modern meg közelítéseinek megis meréséhez jó összefoglaló Craig Evans: Four Colour Problem, pp. 13 – 23., elérhető a http://myweb.tiscali.co.u k/craig land/FCT_files/FourColour.pdf címen, letöltve 2007. 10. 30.
feladatot. (Valójában még egyéb megszorításokat is tesznek, természetesen olyanokat, hogy azok nem teljesülése esetén azonnal következtethetnénk arra, hogy a szóban forgó gráf redukálható. Ezek a feltételek a gráfok összefüggőségével kapcsolatosak. 8 Az alapelv megértése szempontjából ezen további kikötések mellőzhetők.)
6. ábra: Egy konfiguráció; a
csúcsszámok alapján rekonstruált környezet, a gyűrű és az átszínezés – színkiterjesztés gondolatmenete a Kempe-láncokkal Lássunk most egy konkrét példát konfigurációra és arra, hogyan látható be róla, hogy redukálható. A 6. ábrán láthatunk egy konfigurációt (bal oldalon), mely tehát egy gráf, a csúcsokhoz rendelt számok (amiket az ábrán a csúcsokból induló végpont nélküli élekkel jeleztünk) pedig azt mondják meg, hány új szomszédja lesz az illető csúcsnak, mikor a konfigurációt a gráfba részgráfként beágyazzuk. Tegyük föl, hogy egy G gráf (mely tehát egy minimális ellenpélda-jelölt, így teljesülnek rá a mondott kikötéseink – többek között háromszögelt és minden csúcsa legalább ötfokú) tartalmazza ezt a K konfigurációt. K csúcsainak fokszámait előírtuk (ettől lett konfiguráció), ezért világos, hogy K két csúcsa két darab éllel, a másik két csúcsa pedig három darab éllel fog G-nek a K-n kívüli részéhez csatlakozni (az ábrán bal oldalon). Ebből és a G-re tett megkötésekből (köztük a nem részletezett összefüggőségi feltételekkel) kikövetkeztethető K-nak a közvetlen környezete, nevezzük ezt gyűrűnek és jelöljük R-rel (az ábrán középen). Természetesen egy konfiguráció általában többféleképpen lehet része egy nagyobb gráfnak, és így a környezete sem következtethető ki egyértelműen, így többféle lehetséges gyűrű is elképzelhető. Ilyenkor minden ilyet figyelembe kell venni, jelen esetben
8
A részletek megtalálhatók az alábbi írásban: Robin Thomas: An Update on the Four-Color Theorem, pp. 10 – 22, elérhető a http://www.ams.org/notices/199807/tho mas.pdf címen, letöltve 2007. 10. 30-án. A következőkben szereplő példa a konfigurációra és a redukálhatóság bizonyítása is teljes egészében innen származik.
azonban erre a konkrét K-ra a gyűrű nem lehet más, csak ami a 6. ábrán látható. (Ennek belátásához szükség lenne az elhallgatott összefüggőségi feltételekre.) Hagyjuk el most G-ből K-t. Megmutatjuk, hogy ennek a kisebb gráfnak tetszőleges jó színezése módosítható úgy, hogy az kiterjedjen K-ra is, azaz G-nek is legyen egy jó színezése; bármi legyen is G ismeretlen része. (Ezzel nyilván azt látjuk be, hogy egy K-t tartalmazó gráf redukálható, azaz K redukálható konfiguráció.) Ehhez Kempe- láncokat fogunk használni. Tekintsük a kisebb gráf színezését csak a gyűrűn. Ha ez a színezés kiterjeszthető Kra, tehát a gyűrű belsejére is, egy lépést tettünk a redukálhatóság bizonyítása felé. Ha nem ez a helyzet, például a színezés olyan, mint a 6. ábrán látható (jobb oldalon; vastag, nem dőlten szedett számok), azaz a bal oldali csúcsból indulva az óramutató járásával megegyezően 1, 2, 1, 3, 1, 2, akkor a bal oldali 1-es színű csúcsból indítsunk egy 1-4 színcserét. Ha ez nem éri el a fölső 1-es színű csúcsot, akkor egyszerűen ellenőrizhető, hogy a módosított színezés kiterjed a gyűrű belsejére (akkor is, ha a színcsere az alsó 1-es színű csúcsot sem érte el, azaz csak a bal oldali csúcs lett 4-es színű, és akkor is, ha az alsó csúcsot elérte, azaz az is 4-es színű lett: első esetben az 1, 3, 2, 4, a másodikban az 1, 4, 2, 3 színeket kaphatják a belső csúcsok, a bal oldalitól indulva az óramutató járásával megegyezően). Ha eléri a fölső 1-es színű csúcsot, akkor a két csúcs között van egy 1-4 Kempe lánc. Ekkor a fölső 2-es színűből indítva egy 2-3 cserét az változatlanul hagy minden más csúcsot a gyűrűn; csak a fölső 2-esből lesz 3-as, de ekkor is kiterjeszthetjük a színezést: 4, 2, 4, 3- mal, ahogyan az ábrán látható (dőlten szedett számok). Persze a gyűrű többi legális színezéséről is ellenőrizni kell, hogy vagy kiterjed a belső részre, vagy Kempe- láncokkal módosítható úgy (a nagy gráf színezése), hogy kiterjedjen. Ez a módszer alapelvét tekintve teljesen hasonló Kempe eredeti, hibás bizonyításához: a gráfból kihagyunk egy részt, és a maradékot megpróbáljuk úgy átszínezni, hogy az így kapott színezés már kiterjedjen az eredeti gráfra is. A különbség “mindössze” annyi, hogy most nem egyetlen csúcsot hagytunk ki, hanem egy egész részgráfot. Igen ám, de Kempe a bizonyításához kis fokszámú (legfeljebb ötszomszédú) csúcsot használt, és biztosan tudtuk, hogy ilyen minden síkgráfban van. Nekünk most arra lenne szükségünk, hogy minden minimális ellenpélda-jelöltben (“jó jelöltben”) előforduljon egy redukálható konfiguráció. Persze bizonyára végtelen sok redukálható konfiguráció van, nekünk viszont elég lenne egy véges lista, mely olyan szempontból teljes, hogy minden jó jelöltben előfordul valamelyik tagja.
Ilyen teljes lista összeállításához még külön kell vadásznunk a konfigurációkra. Ehhez Heinrich Heesch zseniális ötletét használjuk. Itt az elsődleges szempont nem az, hogy redukálható konfigurációkat találjunk, hanem hogy teljes konfigurációlistát állítsunk össze. Heesch egy olyan módszert javasolt, melynek segítségével különféle algoritmusok tervezhetők teljes listák összeállításához. Rendeljünk egy “jó jelölt” gráf minden csúcsához egy számértéket, “súlyt” úgy, hogy az összes súly összege pozitív legyen. Találjunk ki egy algoritmust, amely átsúlyozza a gráfunk csúcsait, de az összsúlyt változatlanul megőrzi. Az algoritmust tervezzük olyanra, hogy azon igyekezzék, hogy minden csúcs negatív súlyú legyen. Mivel az összsúly pozitív, ez természetesen lehetetlen. Az algoritmusunk valahol elakad, és marad néhány pozitív súlyú csúcs. Gyűjtsük össze azokat a részgráfokat, amik miatt az algoritmus el tud akadni. Mivel az algoritmus minden gráfra szükségképpen sikertelen lesz, minden jó jelölt gráf fog tartalmazni egy leállást okozó konfigurációt, így ez a lista teljes lesz. Természetesen nekünk az lenne a jó, ha a kapott teljes lista minden konfigurációja redukálható lenne. Ennek megfelelően ügyes átsúlyozó algoritmust kell terveznünk, olyat, amely “nagy valószínűséggel” redukálható konfigurációk miatt fog leállni. Ehhez a legkülönfélébb heurisztikus módszereket kell bevetni: a sikeresség szempontjait tapasztalati alapon kell megválasztani. Egyáltalán hogyan jellemezzünk egy redukálható konfigurációt? Hiszen a redukálhatóság ellenőrzéséhez is egy algoritmusra van szükségünk! Heesch azonban további észrevételeket is tett. Sok-sok konfigurációt teszteltek már redukálhatóság szempontjából, és a redukálhatónak bizonyult konfigurációknak voltak bizonyos gyakori közös tulajdonságaik; az egyik ilyen például, hogy sokszor tartalmaztak olyan csúcsot, mely négy éllel kapcsolódott a gyűrűhöz. Fontos, hogy ezen tulajdonságok sem szükséges, sem elégséges feltételei nem voltak a redukálhatóságnak (vagy legalábbis senki nem bizonyított ilyeneket), mindössze a tapasztalatra alapozták őket. Ezután úgy kellett megtervezni egy átsúlyozó algoritmust, hogy az olyan konfigurációk miatt álljon le, melyek rendelkeznek ezekkel a tapasztalatokon nyugvó tulajdonságokkal, azaz “valószínűleg” redukálhatók. Az algoritmussal összeállítottak egy teljes listát, melynek konfigurációit tesztelték redukálhatóság szempontjából. Amennyiben a listán szerepelt olyan konfiguráció, amely nem bizonyult redukálhatónak, megváltoztatták az átsúlyozó algoritmust, hogy ezt a konfigurációt már ne adja ki. Hatalmas munka körvonalazódik előttünk. Vajon működhet ez a módszer? Voltak erre utaló jelek. Sikerült belátni, hogy a négyszín-tétel igaz legfeljebb 25, majd 27, egy későbbi eredmény szerint pedig legfeljebb 35 régiót tartalmazó térképekre. 1970-ben ez a
határ 39-re emelkedett… de ez még mindig messze van a céltól: a tételt minden elképzelhető térképre tudni szeretnénk, bármennyi régiót tartalmazzon is az. Heurisztikus módszereink, a beléjük fektetett rengeteg munka ellenére, gyenge próbálgatásoknak tűnnek csupán. Hat évvel később a probléma mégis megadta magát: 1976-ban Kenneth Appel és Wolfgang Haken bejelentették, hogy az átsúlyozó algoritmusok segítségével találtak egy teljes listát, melynek minden konfigurációja redukálhatónak bizonyult. Minden jó ellenpéldajelöltnek tartalmaznia kell az egyik konfigurációt a listáról, de akkor színezése következik egy kisebb gráf színezéséből, azaz nem lehet minimális ellenpélda. Egyáltalán nincsen tehát ellenpélda: a négyszín-tétel minden síkgráfra igaz. Francis Guthrie 124 évvel korábbi sejtése igaz: bárki rajzolhat egy eddig soha nem látott térképet akármennyi országgal: azt is ki lehet majd színezni négy színnel. E biztos tudás ára: egy teljes lista 1936 redukálható konfigurációval, a teljesség 500 oldalnyi bizonyítása és egy akkori számítógép 1200 órányi munkája. Appel és Haken eredménye bevonult a matematika történetébe: megszületett az első bizonyítás, melyet senki emberfia nem láthatott át teljes egészében. Jó megoldás, rossz problé ma? 9 Nem csoda hát, hogy Kempe bizonyítása rossz volt: a kérdés olyan összetett, hogy csak a számítógépek korában lehetett rá felelni. De nem ismétli-e a történelem önmagát? Mi van, ha erről a bizonyításról is kiderül, hogy rossz? Egy matematikus nem végezhet megfigyelést vagy kísérletet tételei igazolására, de éppen ezért élhet abban a hitben, hogy a biztos tudás birtokosa. Vajon mennyire biztos ez a tudás? A bizonyítás egy nem túl precíz, de annál igazabb “definíció” szerint egymásra épülő állítások olyan sorozata, mely egy tétel igazságáról képes meggyőzni minden elegendően képzett racionális személyt. Egy komoly tétel bizonyítása csak az után jelenhet meg, hogy ilyen módon több szakmabeli (lehetőleg minél több, minél képzettebb és minél racionálisabb személy) meggyőződött a szóban forgó tétel igazságáról, és így tehát a bizonyítás helyességét is ellenőrizte. De legyünk bármennyire képzettek és racionálisak: kétezer részgráfot nem tudunk papíron és ceruzával redukálhatóság szempontjából ellenőrizni. Bizonyítás ez? A matematikai bizonyítás hagyományos értelmében nem. Több szempontból sem.
9
Az ebben a fejezetben található idézeteket ugyancsak a négyszín -tétellel kapcsolatban Simon Singh idézi A nagy Fermat-sejtés című könyvében. (Simon Singh: Velká Fermatova veta, Academia, Praha, 2002, pp. 172 – 178.)
Először is a szokásos módon történő ellenőrzés lehetetlenné válik. Nincs rá más mód, mint a programokat újra lefuttatni egy számítógépen. (Fontos megjegyezni, hogy ezt a lehető legalaposabb módon meg is tették: nemcsak Appel és Haken eredeti módszerével, hanem sok más módszerrel is. Azóta a négyszín- tételnek egyszerűbb bizonyításai is ismertek – például Robertson, Sanders, Seymour és Thomas munkája –, de egyik sem nélkülözi a számítógépet. Lehetnek fenntartásaink a számítógépekkel kapcsolatban, de nyugodtan elfogadhatjuk: a négyszín- tétel minden bizonnyal igaz.) Az ellenőrzésnek ilyen módját valószínűleg nem csak a matematikusok érzik aggályosnak: hozzászokhattunk, hogy a számítógépek a hibáikat is ismétlik. Legfeljebb a programkódot és az algoritmusokat nézhetjük át még egyszer helyesség szempontjából. De azt, hogy a számítógép nem téved, nem garantálja nekünk semmi. Swinnerton-Dyer mondta a következőt: “Senki sem kezeskedhet azért, hogy nincs hiba az adathordozó szalagon vagy beolvasáskor nem történt-e tévedés. És a számítógépek hajlamosak átmeneti rendellenességeket is produkálni.” Mondhatnánk: az ember is képes elkövetni tévedéseket. Kempe hibás bizonyítását is elfogadták. Itt nem csak az a baj, hogy a számítógép nem tévedhetetlen. Mi sem vagyunk azok. Többről van itt szó. Arról, hogy a matematika mélyen emberi tudomány. Évezredek óta az az igyekezet vitte előre, hogy megértsük a dolgok mögött rejlő lényeget. Emlékezzünk a törött sarkú sakktáblára és az egyszer kettes dominókra: nem azt szeretnénk látni, ahogyan egy gép megpróbálja kirakni a táblát és nem sikerül neki. Mi látni szeretnénk a színezést is. Nekünk bizonyítás kell. Nem bizonyíték. Ahogy Ronald Graham fogalmaz: “Nagyon lehangoló lenne, ha az ember megkérdezhetne egy számítógépet, igaz-e a Riemann-sejtés, és azt a választ kapná: Hogyne, igaz, de Ön nem tudná megérteni a bizonyítást.” Egy ilyen gép a z ismereteinket gyarapítaná ugyan, de tudásunkat nem: nem értenénk meg tőle jobban a világot. Philip Davis így emlékezik vissza a napra, mikor megtudta, hogy megoldották a százhúsz éves problémát: “Fantasztikus! Hogy csinálták?” - volt az első reakcióm. Egy csodálatos ötletet vártam, melynek szépsége bearanyozza a napom. “Több ezer esetre bontották, és mindet ellenőrizték számítógépen” - jött a válasz, és ez teljesen lehangolt. Azt mondtam: “Ha csak így lehet megcsinálni, akkor nem is volt jó probléma.” Talán mégis jó probléma volt. Talán üzen nekünk valami fontosat. Talán feltárta képességeink határait. A matematika fejlődése, hasonlóan más tudományokhoz, odáig jutott, hogy minden ismeret kollektív ismeret. Az ember fizikai adottságai és szerény, véges élet e lehetetlenné teszi bizonyos dolgok teljes megismerését. Tudásunk közös; meg kell bíznunk egymásban. Senki sem érthet meg, még csak nem is olvashat el minden bizonyítást.
Egymásnak eddig is elhittük, hogy egy-egy bizonyítás jó. Nehéz kérdés, hogy elhisszük-e ugyanezt egy számítógépnek. Vajon az így szerzett tudás az emberiség sajátja még? Hadd válaszoljon erre az egyik szerző, Wolfgang Haken: “Az a tény, hogy a számítógép több részletet ellenőrizhet néhány óra alatt, mint amennyire egy embernek egy egész élet alatt reménye lehet, nem változtatja meg a matematikai bizonyításról alkotott alapelképzeléseinket. A matematikának nem az elmélete változott meg, hanem a gyakorlata.” A kutatás, nemcsak a matematikai, nagyon sok összetevőből áll. Ilyenek a kíváncsiság, a képzelőerő, a zsenialitás, a tapasztalat, a kitartás és a pontos munka. A számítógépek mindebből csak ebben a legutóbbiban segíthetnek. Ha hagyjuk. És miért ne hagynánk, hiszen arról van szó, hogy egy újabb lépést tegyünk a megismerés felé.
Bibliográfia: Devlin, Keith: Matematika: a láthatatlan megjelenítése, Műszaki Kiadó, Typotex Kiadó, Budapest, 2001, pp. 26 – 27., 213 – 217., 228 – 229. Horváth Géza: Fejleszthető-e az alkotóképesség?, Katedra füzetek, Lilium Aurum, Dunaszerdahely, 1997, pp. 25 – 26. Simonyi Károly: A fizika kultúrtörténete, negyedik, átdolgozott kiadás, Akadémiai Kiadó, Budapest, 1998, p. 92. Singh, Simon: A nagy Fermat-sejtés (Velká Fermatova veta), Academia, Praha, 2002, pp. 24 – 27., 57 – 60., 172 – 178. Inte rnetes források: Bravaco, R., Simonson, S.: The Four-Color Theorem http://www.stonehill.edu/compsci/LC/Four-Color/Four-color.htm Evans, C.: Four-Colour Problem http://myweb.tiscali.co.uk/craigland/FCT_files/FourColour.pdf Robertson, N., Sanders, D. P., Seymour, P., Thomas, R.: The Four Color Theorem http://www.math.gatech.edu/~thomas/FC/fourcolor.html Thomas, R.: An Update on the Four-Color Theorem http://www.ams.org/notices/199807/thomas.pdf Letöltve 2007. október 30-án.
