SZEGEDI TUDOMÁNYEGYETEM Természettudományi Kar Halmazelméleti és matematikai logikai tanszék
SZAKDOLGOZAT Paradoxonok a matematikában
Témavezet : Dr. Szabó László Imre Készítette: Szigeti Tamás, V. matematika
2005.
Tartalmi összefoglaló Dolgozatom célja, hogy képet adjon az évszázadok során újra és újra felbukkanó paradoxonokról, melyekt l a matematika egyetlen ága sem mentes. Szeretném továbbá ráirányítani a figyelmet az ellentmondások feloldhatóságára, melyekhez csupán kell precizitásra van szükség. Foglalkozom az analízis (második, harmadik, nyolcadik fejezet, 4.1-es, 4.3-as, 4.4es feladatok), a valószín ségszámítás (hetedik fejezet, 5.4-es, 5.5-ös feladatok), a logika (hatodik, tizenkettedik fejezet), a halmazelmélet (tizedik, tizenegyedik fejezet, 4.2., 5.1., 5.2., 5.3. feladatok) illetve a mértékelmélet (tizenharmadik fejezet) körébe tartozó korabeli ellentmondásokkal. Néhány feladatot is válogattam a klasszikus paradoxonok közé, melyek valamilyen rokonságban állnak ezekkel. Például nem tárgyalom a Galileiparadoxont (végtelen mennyiségek körében lehet egyenl a rész az egésszel), ám a 4.2-es feladatban és a tizenharmadik fejezetben kicsit más köntösben mégis megjelenik. Hasonló a helyzet a Burali-Forti-féle antinómiával, melyet azért nem vizsgáltam, mert hosszú bevezetést igényelt volna (jólrendezés, rendszámok, jólrendezési tétel), és mert lényegileg nem sokban különbözik az összes halmazok halmazának antinómiájától. Az Epimenidészparadoxon is („Minden krétai hazudik.”, „Ez az állítás hamis.”), mely megtalálható Szent Pál apostol Tituszhoz írt levelének 12. sorában is, megjelenik formában
némileg burkolt
a hatodik fejezetben.
Mivel azonban a matematikai gondolkodás kezdete óta olyan nagy mennyiség látszólagos ellentmondás bukkant fel, amennyivel terjedelmi keretek miatt nem foglalkozhattam, ez az ízelít , bár igyekszik sokszín lenni, semmiképpen sem ölelheti fel az összes létez és ma is ismert paradoxont. Így maradt ki például az ismertebbek közül a jelölési, a Bertrand-, és még sok más régebbi és újabb paradoxon vizsgálódásaimból. Ez az összeállítás egy 11-12. osztályban ajánlott matematika-szakkört színesít anyag lehet, leginkább középiskolai matematika tanároknak ad útmutatást, de igyekeztem úgy felépíteni, hogy érdekl
bb, tagozatos, illetve emelt szint
diákok számára is érthet legyen.
2
érettségire készül
Módszertani megjegyzések A közoktatási törvény 1996. évi módosítása és az 1997-ben megjelent kormányrendelet alapján 2005-t l a kétszint érettségi vizsgarendszer lép érvénybe. A kerettanterv azonban az els három középiskolai osztályban három, 12. osztályban pedig négy órában maximalizálja a nem tagozatos osztályok óraszámát matematikából. Emelt szint érettségire való felkészítés esetén ehhez 11. és 12. osztályban plusz két-két óra adható, ami az analízis elemeinek tanításához éppen elég, így a szakdolgozatomban tárgyalt problémák és feladatok csak említés szintjén kezelhet ek nem tagozatos osztály óráin, azonban tagozaton b vebben is tárgyalhatóak, szakkörön pedig szinte teljesen szabatosan. A matematika egyik didaktikai célja, hogy a valóságban el forduló leggyakoribb térbeli és mennyiségi viszonyokat, formákat megjelenítse, ám épp ez a megjelenítés vezet számos olyan problémához, mint amilyen a Banach-Tarski-paradoxon. Ezek a problémák persze meg sem jelennének a megfelel gondolkodási kultúra illetve absztrakciós szint megléte nélkül. Absztrakció következménye a végtelen fogalma is, mely szintén számtalan paradoxonhoz vezet, és a hatodik fejezet valamint a 7.1-es feladat kivételével az összes többi ellentmondásban jelen van. Ahhoz, hogy helyes kép alakuljon ki a tanulókban a matematikáról mint tudományról, feltétlenül szükséges, hogy ne kézbe kapják a letisztult fogalmakat, hanem induktív úton tapasztalják meg szükségességüket, és a definíciókat maguk mondják ki. Ehhez persze számtalan példán át vezet az út, így például az elég tömör harmadik fejezet víthet további feladatokkal, amit a határérték-fogalom bevezetésekor minden oktató meg is tesz. A paradoxonok segítségével
persze mértékletesen adagolva
elérhet ,
hogy a tanulókban kialakuljon az igény egy precízebb tárgyalás irányába. Otthon elgondolkodva és társaikkal vitatkozva akár maguk is fel tudják oldani az egyes ellentmondásokat. Tisztázni kell továbbá az absztrakt jelölések tartalmát is velük. Így persze kaphatunk meglehet sen kellemetlen kérdéseket is. Például, ha egy diák megérti, hogy a Russel-antinómia (10.2.) feloldásakor az axiomatizálással kizárjuk vizsgálódásaink köréb l a nem tartalmazkodó halmazok halmazát, illetve nem is nevezzük halmaznak, felteheti a kérdést: Tanár úr! Ez nem a probléma megkerülése?
3
Erre aztán az a válasz, hogy tulajdonképpen igen, de jobbat nem tudunk. Esetleg mesélhetünk az axiómák hasznáról, hogy ezáltal sok paradoxon együtt kezelhet , ám a lényegen ez mit sem változtat: a kérdést nem túl megnyugtatóan válaszoltuk meg. Ha pedig nem akarjuk még nagyobb bizonytalanságban hagyni a tanulókat, jobb, ha nem is említjük meg, hogy semmi nem garantálja az újabb ellentmondások soha fel nem bukkanását. Persze a bizonytalanság egy motivációs eszköz is lehet, ám ezzel az eszközzel óvatosan kell bánni, mert matematikai érdekl dés tanártól hallottam olyan véleményt, hogy a matematikában minden állítás (még a hamisak is) bebizonyítható. Túl sok paradoxonnal találkozott az egyetemi matematikaórákon, és neki ez a tanulság kristályosodott ki az évek folyamán. Azért azt sem árt tisztázni bizonyos erre érett osztályokban, hogy egyes esetekben Gödel tételeinek értelmében
bizonyítottan lehetetlen belátni egy adott rendszer
ellentmondás-mentességét. Így a matematikus is hív abban, hogy munkája
valamilyen értelemben. Bízik
és még sokaké a történelemben
nem válik egy csapásra
értelmetlenné, mert egy adott rendszerben egyszer csak felbukkan egy ellentmondás. A matematika tudománya iránti alázat is kapcsolatos a hittel. Sokszor ugyanis hajlamosak vagyunk azt hinni, hogy a matematikát mi alkottuk, ám egy-egy a távoli területek közti megdöbbent összefüggés rámutat arra, hogy a matematika
bár alkotás
, nem az ember alkotta, éppúgy ahogy az emberi gondolkodás is csak részben az ember ve. Például igen nehéz megválaszolni, mi az oka, hogy a hiperbolikus és a trigonometrikus függvények olyan hasonlóan viselkednek. Mondhatnánk persze, hogy mivel a komplex számokon értelmezett koszinuszfüggvény egy elforgatottja a hiperbolikus koszinuszfüggvényt adja vissza, nem meglep a hasonló viselkedés. De ez az érv tulajdonképpen nem egy okot ad meg, hanem ugyanarra az összefüggésre tekint magasabb szintr l, ugyanis minden válasz, s t minden kérdés is újabb kérdést szül. Így megkérdezhetjük, miért veszi fel a komplex számokra kiterjesztett koszinuszfüggvény a képzetes tengely mentén éppen azokat az értékeket éppen abban a sorrendben, mint a valós számokon értelmezett ch(x) függvény? De ennél is izgalmasabb az a kérdés, mi az összefüggés a végtelen sorok (ezek segítségével terjeszthet
ki a cos(x) függvény a
komplex síkra), a trigonometrikus függvények és a Bolyai-geometria között, ahol a trigonometrikus
függvényeket
bizonyos
értelemben
a
hiperbolikus
függvények
helyettesítik. Az ilyen kérdésekre egy lehetséges válasz, hogy mivel a matematikai objektumok az emberi problémamegoldó gondolkodás megjelenései, az emberi elme
4
következetességének eredményei ezek az összefüggések. (Az el
kérdésre persze a
differenciálgeometria is tartogat választ.) Az a kérdés, hogy az emberi elme következetességének mi az oka, hadd maradjon nyitott csakúgy, mint az, vajon t lünk függetlenül létezik-e a matematika. Szolgálja továbbá ez az összeállítás a matematikadidaktika feladatainak némelyikét is. Kreatív, problémamegoldó gondolkodásra nevelnek a feladatként kit zött kérdések, a megoldások sok helyen kiemelten kezelik a matematikai modellben kapott eredmény valóságba történ visszaültetését, boncolgatva a matematikai absztrakció és a valóság kapcsolatát. A matematikában kell en nem hangsúlyozható kételkedési, kérdezési és bizonyítási igény fejlesztésére is kiemelten alkalmasak a paradoxonok. Csupán arra kell vigyáznunk, hogy a probléma kit zése után ügyes visszakérdezéssel rávegyük a tanulókat, hogy egymással vitatkozzanak, míg ha megadnánk bizonyos válaszokat, biztosak lehetnénk benne, hogy minket támadnának közös er vel, belekötve válaszainkba. Sokszor persze a probléma kit zését érzik hibásnak, a paradoxonhoz vezet esetleg a kit
bizonyítást, vagy
személyével kapcsolatban merülnek fel kételyeik (normális-e
egyáltalán?), és az is el fordul, hogy magukban kételkednek. Ezek a problémamegoldás során felmerül mellékes mozzanatok általában zsákutcát jelentenek, ahogy azt Lénárd Ferenc „A problémamegoldó gondolkodás” cím
könyvében megjegyzi, ügyes
kérdésfeltevéssel és apró segítségekkel azonban kezelhet ek. Ezzel kapcsolatban láttam egy valószín ségszámítási példát 11. osztályban, tagozaton: A tanár az óra elején megkérdezi:
Elképzelhet -e olyan esemény, melynek
valószín sége nulla, mégis bekövetkezik? Az egyik diák, miután megértette a kérdést:
Nem úgy definiáltuk a lehetetlen
eseményt, hogy nulla a valószín sége? Tanár:
De igen.
Második diák:
A lehetetlen esemény márpedig nem következik be!
Láthatóan nem értik, mit akar ezzel a tanár, aki közben fölrajzol a táblára egy céltáblát és kijelöl rajta egy pontot. Tanár:
Emlékeztek a geometriai valószín ségre? Mekkora a valószín sége, hogy ezt
a pontot találom el, ha találomra kiválasztok egy pontot? Harmadik diák:
A pont területe per a céltábla területe!
A tanár felírja a táblára: P
Tkörlap
, és megkérdezi:
5
Mekkora a pont területe?
Második diák: Tanár:
Egy?!
Harmadik diák: Tanár:
A pont területe 1.
A pontnak nincs területe!
Azt akarod mondani, hogy nulla?
Harmadik diák bizonytalanul:
…Igen.
A tanár kiegészíti a táblai képletet P Els diák:
0 Tkörlap
-ra, ami heves tiltakozást vált ki.
Nem kéne mégiscsak valamekkora területet tulajdonítanunk a pontoknak?
Mert így bármely pont eltalálásának valószín sége nulla. Tanár: Els
És?
diák:
Ha minden pont eltalálásának valószín sége nulla, akkor a céltábla
eltalálásának valószín sége is nulla. Negyedik diák: Els diák:
Észnél vagy? Nullaszor végtelen az nem nulla!
Hát akkor mennyi? Csak nem éppen az adott körlap területe?
Második diák:
Szerintem 1.
Hatalmas vita alakul ki, melyet a tanár alig tud lecsendesíteni, választ azonban nem ad, csak levonja a következtetést: Bármely pont eltalálásának valószín sége tehát nulla. A kérdésre még visszatérünk néhány hónap múlva.
A táblát letörli és belekezdenek a házi feladat ellen rzésébe,
bár a legtöbben még gondolkodnak a problémán. Ez a kérdés is tulajdonképpen egy korabeli paradoxon, melyet a tanár ügyes irányításával újra átéltek a gyerekek. A matematika esztétikájának megismertetésében feltétlenül helyet kell kapniuk a hasonló kalandoknak, mert esztétikai élményt nyújthat, ha látunk egy szép megoldást valamelyik feladatra, de az élmény tartósabb, ha a szép megoldás a sajátunk, hát még az mekkora örömöt okoz, ha egy olyan kérdésre sikerül választ adnunk, mely a matematika történetében is jelent s volt. A legnagyobb dics ség, ha mi magunk teszünk fel történelmi kérdést, és meg is tudjuk válaszolni, de már az is nagyon szép teljesítmény, ha egy matematikai eredménnyel csak 300 évet késünk. Különbözik ez a puszta válaszadástól, mert a matematikában (és más tudományokban is) a kérdések is vannak olyan fontosak, mint a válaszok.
6
Szakdolgozatom felépítésében az analízis elemeinek tanítását követtem, melyet a szakkörön tárgyalt problémák elmélyíthetnek. Egy lehetséges felépítés öt lépésben történik. Feladataim leginkább az els három lépésben tárgyaltak színesítését szolgálják: i.)
Sorozatok, sorozatok konvergenciája, határértéke (fogalmak tisztázása
sok példával) ii.)
Végtelen halmazok számossága, a végtelen másik megjelenése
iii.)
Függvények folytonossága, határértéke
iv.)
Differenciálszámítás és alkalmazásai
v.)
Integrálszámítás és alkalmazásai
Az els lépéshez nyújtanak segítséget a második, harmadik fejezet, a 4.1-es és 4.4-es feladatok. A megoldást nem muszáj teljes egészében bemutatni, kés bb azonban vissza lehet térni rájuk. A 4.2-es feladat már a második lépés felé terel, a 4.3-at pedig csak kés bb tárgyalhatjuk precízen, de meg lehet fogalmazni a problémát, feltenni a kérdést. t ugyanez a dilemma merül fel akkor, ha egy olyan egyenes hasáb térfogatát és felszínét számoltatjuk ki, melynek alaplapjai Koch-hópelyhek, és így az integrálszámítás használatát kikerültük, nem is beszélve az improprius integrálról. A paradoxon feloldása ugyanaz marad, a Koch-hópehely azonban illeszkedik a sorozatok témájához. Második lépésben tárgyalhatjuk az ötödik fejezet feladatait, és a 4.2-t. Az 5.4-es feladat az els lépésben tanultakat is frissíti, az 5.5-ös pedig már a mértékelmélet felé visz. Ha ekkor tárgyaljuk kikapcsolódásként a hatodik, és ismétlésként a hetedik fejezet feladatait, minden el készület adott a harmadik lépésre való áttérésre. A harmadik lépéshez segítenek a nyolcadik fejezet feladatai, melyek egyben a fraktálok fogalmát is megízleltetik, és újabb fejleményeket jelentenek a végtelen számosságok témájában is így teljesítve egy fontos követelményt, a spiralitás elvét, mely azt jelenti, hogy visszatérünk ugyanazokhoz a fogalmakhoz magasabb szinten. A kilencedik fejezetben egy fontos módszerrel ismerkedhetünk meg, mely hasznossága mellett paradoxonokat is okoz (a 10.2-es és a 10.5-ös feladatok). Ezután a tizedik és tizenegyedik fejezetekben halmazelméleti és logikai fogalmakkal találkozunk. Ez a találkozás persze nem öncélú, egyrészt a paradoxonok feloldását szolgálja, másrészt egy új paradoxont készít el , melyet a tizenkettedik fejezetben tárgyalok. Nem gondolom azonban, hogy ezen fejezetek tartalmát a diákoknak ilyen formában kellene elmondani. Ez a rész inkább a tanárnak szól, aki kivonatolva és a gyerekek számára érthet en ízelít t adhat bel le. Ezt a célt szolgálja a játékos bennszülöttes példa is a természetes számok Peanó-axiómáival kapcsolatban. Az axiómák 7
eredeti alakját nem mondtam ki, viszont a fordítást házi feladatként feladva, biztosan lesz tanuló, aki helyesen meg tudja oldani a megfelel fogalmak következetes kicserélgetését. A tizenharmadik fejezet azonban
bár elég bonyolult
tárgyalható szakkörön a
maga teljességében, de részekre bontva és a részeket külön-külön alaposan megmagyarázva. Persze, mivel a szakkörök ideje is sz kös, ha nagyon alaposak akarunk lenni, és a gyerekek türelme sem végtelen, említés szintjén is elég lehet kezelni ezt a fejezetet szemezgetve bel le. A Banach-Tarski-paradoxon bizonyítása viszont hasznos lehet olyan szempontból, hogy ez a tétel tipikusan a „hiszem, ha látom” kategóriába tartozik, és az sem árt, ha a tanulók
akár egy paradoxon kapcsán
látnak egy hosszú
bizonyítást is. Ezután lehet mesélni nekik az olyan tételek bizonyításáról, melyek ellen rzéséhez nem elég egy ember élete (egyszer csoportok elmélete), illetve az olyan szelídebb tételekr l, mint például a nagy Fermat-tétel, melynek bizonyítása csak néhány száz oldal. Itt említeném meg, hogy érdemes egy máig vitákat szül antinómiát is elmondani szakkörön, ami biztosan beindítja a tanulók fantáziáját. Ilyen lehet például a váratlan röpdolgozat
problémája:
A tagozatos osztálynak
minden
hétköznap
van
egy
matematikaórája. A tanár a következ kijelentést teszi az arra a hétre esedékes dolgozatról a hétf i óra elején: Nem fogjátok el re tudni, hogy melyik napon írjuk a dolgozatot. A diákok így gondolkodnak:
Nyilván nem írhatjuk pénteken, mert akkor már a
csütörtöki óra után tudnánk, hogy másnap dolgozatot írunk. Mivel pénteken nem írhatjuk, nem írhatjuk csütörtökön sem, mert ez az utolsó lehetséges nap, de ha szerdáig nem írtuk meg, akkor tudni fogjuk, hogy már csak csütörtökön írhatjuk.
Ilyen gondolatmenettel
aztán egymás után minden napot kizárnak. Ekkor azonban, ha például csütörtökön írják meg, vagy rögtön hétf n, mindenki meg fog lep dni. Hol a hiba?1 Az ilyen problémákon edzett tanuló játékosabban és érdekl
bben fog hozzáállni
egy közönségesebb probléma megoldásához is. Márpedig a tanulás nagyon hatékony formája a játék.
1
Egy okos tanuló válasza lehet a következ : Hallgatólagosan feltételeztük, hogy a tanár kijelentése igaz, végig így gondolkodtunk, és csak akkor vetettük el feltevésünket, amikor gondolatmenetünkben a hétf i napig elértünk. Azonban nem tudjuk, igaz-e a tanár kijelentése, így a péntek után a csütörtököt nem zárhatjuk ki, mert attól függ en az utolsó lehetséges nap a csütörtök, hogy a kijelentés igaz-e vagy hamis. (Ha a kijelentés hamis, a pénteki nap nem kizárható.) Valljuk be, ennél meggy bb feloldást nehezen találnánk! Az antinómia azonban antinómia maradhat, ha nem mindenki így oldja meg a problémát, illetve nem ért egyet vele.
8
1. Antinómiák és paradoxonok „Az igazi paradoxon az az ellentmondás, ami valamilyen értelemben elvezet az igazsághoz. Vagy kevésbé fennkölten: a paradoxon olyan ellentmondás, amely megvilágít egy igazságot, ami mélyebb annál az igazságnál, amit a paradoxon felfedezése vagy felvetése el tt ismertünk.” Laczkovich Miklós
Paradox: Önmagának látszólag ellentmondó. Ellentmondásos. Antinómia: Ellentmondás. A Magyar értelmez kéziszótár a fenti meghatározásokat adja a címben felsorolt szavakra. Hasonló értelemben használom én is
ket, a paradoxon szót a látszólagos,
feloldott, az antinómia szót a valódi, feloldatlan ellentmondásokra, melyek igaznak elfogadott ítéletekb l következnek. Hasonló e megkülönböztetés ahhoz, amikor a trükköt és a varázslatot szétválasztjuk. Paradoxon adódhat akkor, ha igaznak elfogadott kiindulási ítéleteink közé becsúszik legalább egy kakukktojás (A), és akkor is, ha következtetéseink között van hibás (B). Sokszor pedig úgy is kaphatunk paradoxont, hogy igaz premisszákból hibátlan érveléssel olyan állításhoz jutunk, amely szemléletünkkel ellenkezik (C). Ilyenkor ugyanúgy meglep dünk, mint ha logikai ellentmondásba ütköznénk. Az antinómiák kellemetlenebbek, mert a matematikusok nem értenek egyet abban, hogyan oldhatók fel. Premisszáink közül melyiket vessük el, vagy a levezetésben hol követtünk el hibát? Eredetileg a legtöbb paradoxon antinómiaként született, megingatva az emberek ellentmondás-mentességbe vetett hitét a valóságról illetve a matematikáról. Történetileg az egyik els ilyen Zénon Akhilleuszról szóló aporiája volt.
2. Akhilleusz és a tekn sbéka Tekintsünk egy olyan futóversenyt, amely Akhilleusz és egy tekn sbéka között zajlik. Akhilleusz sportszer en el nyt ad a tekn snek, akit ezek után soha sem érhet utol, mert mindig el kell jutnia addig a pontig, ahonnan a tekn sbéka el keveset is
leg elindult, és
a tekn s addigra már arrébbmászott, így mindig el nyben van.
9
ha
Ez egy C típusú paradoxon. Persze attól függ en, hogy hogyan értelmezzük a „mindig” szót. Ha ugyanis Akhilleusz sebessége v A 0, a tekn sé vT 0, ahol v A
vT , a
tekn s el nye pedig s , akkor a vizsgált id alatt Akhilleusz a tekn st tényleg nem éri utol. Az viszont nem igaz, hogy soha nem hagyja le, mert a vizsgált id tartam véges:
tn v 1 T vA
s < vA
hiszen v A
s vT vA vA
s vA vT vA
2
vT vA
...
n 1
2
vT vA
s ... vA
vT vA
n
... =
s vA
n 1
1 v 1 T vA
s vA
vT
vT , és így e végtelen sok szám összege véges. Más kérdés, hogy értelme van-
e végtelen sok szám összegének? Az el meggy
vT vA
s vA
bizonyítás tehát csak egy olyan ember számára
, aki már tud végtelen összegekkel bánni. Zénon idejében ilyen ember
valószín leg nem élt, jó kétszáz év múlva Arkhimédész az els , aki hasonló gondolatokat precízen tudott kezelni, utána pedig még sokáig senki. Szerencsére egyszer en átfogalmazható a fenti bizonyítás úgy, hogy csak véges összegeket használjon:
tn
s vA
v 1 T vA
vT vA
2
...
<
s vA
vT vA
n 1
1 v 1 T vA
vT vA vT vA
s vA
n
1 1
vT 1 vA s v vA 1 T vA
n
s vA
vT
Az akkori emberek szemében meglep lehetett, hogy egy számsorozat bármennyi tagját sorban összeadva az eredmény sosem halad meg egy el re adott számot. Mai szóhasználattal úgy mondanánk, végtelen sok szám összege lehet véges. Érdekes megfigyelni azt is, hogy a két bizonyítás nagyon hasonló, csak az egyik alkalmaz végtelen sorokat, a másik pedig nem. Zénon másik, kellemetlenül zavarba ejt
paradoxonja szintén a határérték
fogalmával kapcsolatos. Azt állítja, hogy mozgás nem lehetséges, mert ha létezne mozgó tárgy, az hol mozogna? Ott-e, ahol van, vagy ott-e ahol nincs? Ahol van, ott nem mozog, mert ott van, és így szükségképpen áll. Ahol nincs, ott nyilván nem is mozoghat. Tehát mozgás nem létezik. Ennek a paradoxonnak a feloldása akkor vált lehetségessé, amikor a
10
határérték-számítás lehet vé tette a pillanatnyi sebesség precíz definícióját. Ám az addig vezet út is paradoxonokkal volt kikövezve.
3. Végtelen sorok Az el
fejezetben használt végtelen sorok fogalma is sok paradoxonhoz vezetett. .
Például 0, 3 egyenl ség,
1 9
3, 3 0, 3
ennek
mintájára
.
.
10 0, 3 0, 3 ám
ha
2 1 2 4 8 ... 2 n
.
1 9
.
3 9
azt
1 , ami egy teljesen helytálló 3 írjuk,
1 2 4 8 ... 2 n
...
1 2 4 8 ... 2 n
...
1,
már
...
akkor
viszont
ellentmondásba ütközünk. Hogy is lehetne pozitív számok összege negatív? Sokáig gondot okozott az alábbi összeg meghatározása is: 1 1 1 1 1 1 ... ( 1) n másrészt pedig S
1
(1 1) (1 1) (1 1) ... 0 ,
S , mert egyrészt S
...
1 ( 1 1) ( 1 1) ... 1
Még Leibniz is azt mondta, ha a részletösszegeket nézzük, ugyanannyiszor kapunk 1 . Leibniz kezében persze akkoriban nem 2
1-et és 0-t, így az összeg nem lehet más, mint
voltak precíz definíciók, mégis ráérzett az igazságra, ahogy arra kés bb rámutatok. Most nézzünk inkább egy „bizonyítást” arra, hogy S 1
1 x
x2
1 3 S , vagyis S
x3
1 x
x4
x6
x7
1 . 3
... , ha itt most x 1 , akkor képletünk az
1 formát ölti. 3
A didaktika az ilyet téves analógiának nevezi, ami rokonítható a B típusú paradoxonokkal. Végtelen összegekkel nem mindig lehet olyan m veleteket végezni, mint amit véges összegekkel, még ha konvergensek, akkor sem: 1 2
L 1 2 L 2 L
Az azonos nevez
1 3
1 4
1 5
1 6
...
1
n 1
1 n
2 2
2 3
2 4
2 5
2 6
2 7
2 8
2 9
2 10
2 1
2 3
1 2
2 5
1 3
2 7
1 4
2 9
1 5
2
tagokat csoportosítva kapjuk:
11
... ... ...
2 L 2 L 1
1 2
L
2 1
1 2
2 3
1 3
1 4
1 3
1 5
1 6
...
L , azaz L
1 4
1
1 2
1 3
1 4
2 5
1 5
1 6
1 5
1 6
2 7
1 7
...
0 , ami képtelenség, hiszen
1 7
1 8
... 0
Itt a probléma az, hogy az átrendezés nem alkalmazható ez esetben. Csak abszolút konvergens sorokat szabad átrendezni. Más konvergens soroknál az átrendezés mondhatni annyi paradoxonhoz vezet, mint ahány valós szám van. Ezt mondja ki Riemann tétele. 3.1. Tétel: Feltételesen konvergens sor átrendezhet úgy, hogy egy el re adott valós számhoz vagy akár végtelenbe, illetve mínusz végtelenbe tartson. „Bizonyítás”: Megtalálható [18.]-ban, illetve [5.]-ben a 37. oldal 2.11. tétele szemléletes bizonyítást ad rá egy speciális esetben, melyet könnyedén általánosíthatunk tetsz leges feltételesen konvergens sorra.
Kinek mennyire meglep , aszerint magát a Riemann-tételt is tekinthetjük C típusú paradoxonnak. Ha szeretnénk mindezen nyugtalanító fejlemények dacára végtelen sorokat használni, pontosan le kell szögeznünk definíciókkal, mit értünk a használandó fogalmakon. Erre egy hagyományos lehet ség: 3.2. Definíció: Az s n sorozat határértéke s , ha2 bármely létezik olyan
N szám, hogy valahányszor n
, mindannyiszor s n
R, s
0 számhoz
.
3.3. Definíció: Az s n sorozat konvergens, ha létezik határértéke, különben divergens. Az igazi nagy fejl dést az hozta, amikor a végtelen sorokra mint folyamatokra kezdtek tekinteni, és egy-egy végtelen sor összegét határértékként definiálták. Erre a kulcsgondolatra Cauchy jutott els nek. Elképzelése annyira egyszer volt, hogy mindenki számára azonnal világos lett, ez a megoldás az akkori matematikát 150 éve aggasztó paradoxonok kiküszöbölésére. Egyébként, amikor a párizsi akadémián Cauchy el adott err l az eredményér l, Laplace, aki szintén a hallgatóság soraiban ült, még el adás közben felugrott helyér l, hogy hazarohanjon ellen rizni, helyesen bánik-e a végtelen sorokkal a Cauchy által megfogalmazott értelemben. 2
A „ha” szó használata definíciókban „akkor és csak akkor, ha” értelemben történik.
12
N
a n sor konvergens, ha az s N
3.4. Definíció: Egy
a n részletösszeg-sorozat
n 0
n 0
konvergens. A konvergens részletösszeg-sorozat „A” határértékét a sor összegének
an
nevezzük, és ekkor azt írjuk:
A.
n 0
a n sor abszolút konvergens, ha a
3.5. Definíció: A n 0
a n és a
3.6. Tétel: Ha a n 0
an
bn és a
n 0
an
A,
n 0
bn
B , akkor
n 0
n 0
an
bn
A B.
n 0
a pn is az, ahol p n : N N
a n abszolút konvergens, akkor
3.7. Tétel: Ha
an
bn sorok konvergensek, akkor a n 0
bn sorok is azok. S t ha
n 0
a n sor konvergens. n 0
n 0
bijekció, és ez az átrendezés a sor összegét nem változtatja meg.3
4. Néhány végtelennel kapcsolatos paradoxon Nem véletlen, hogy a végtelen összegekkel kezdtem a paradoxonok tárgyalását, hiszen a legtöbb ellentmondás a végtelen kapcsán merül fel. Lássunk néhány példát! 4.1. A villanykapcsoló problémája: Van egy ideális villanykapcsolónk, mely akármennyi kapcsolást kibír, egy ideális izzó ideális áramkörébe kötve. Páros sok kapcsolás után az izzó kialszik, páratlan sok után pedig kigyullad. A következ t játsszuk: Az els másodperc végén felkapcsoljuk izzónkat, aztán várunk fél másodpercet, hogy lekapcsoljuk, majd negyed másodperc múlva újra felkapcsoljuk. Az n-edik lépésben
1 2n
1
másodpercet várunk, hogy újra változtassunk a kapcsoló állásán. A harmadik másodpercben mit fog csinálni az izzó? 4.2. A király és az udvari bolond: A király a népét l adó formájában egyszerre mindig két aranyat kap, az udvari bolond pedig egyszerre mindig egy aranyat sikkaszt el a király vagyonából. Az els hónap végén kapja a király az els két aranyát, és ekkor lophat a bolond el ször. Az n-edik adózás
1 2n
1
hónappal követi az n-1-ediket, és a bolond is
ekkor lophat a királytól. Meg tudja-e valósítani a bolond, hogy a királynak a harmadik 3
A 3.6. és a 3.7. tételek bizonyítása is [18.]-ban található, része az egyetemi alapozó tananyagnak.
13
hónapra egyetlen aranya se maradjon? (Állapodjunk meg abban, hogy az az arany, amit a bolond a második hónap végéig nem lop el, megmarad a királynak a harmadik hónapra.) 4.3. A befestett tölcsér problémája: Forgassuk meg az f x
1 , x 1 függvényt az x
x tengely körül. Az így kapott tölcsérnek számoljuk ki a térfogatát és a felszínét! Legyen mindkét tengely egysége 1 dm hosszú! Mennyi festék kell egy ilyen tölcsér telitöltéséhez? És a befestéséhez? 4.4. A csiga és a manó: A falhoz van kötve egy 10 m hosszú, tetsz legesen nyújtható ideális gumikötél. A másik végét egy manó fogja, és 10 m/s sebességgel fut vele a fallal ellenkez
irányba. Ugyanezen végér l egy csiga indul a fal felé, mely a
gumiszalagon 1 cm/s sebességgel mászik. Elér-e a falig véges id alatt? 4.5. Megoldások 4.5.1. Az els feladatra azt mondhatjuk, hogy definiáltuk az izzó állapotát páros sok és páratlan sok kapcsolás esetére, de nem határoztuk meg a végtelen sok kapcsolás utáni állapotát, így értelmetlen a kérdésünk. Sokan vélekednek hasonlóan, azt mondják, nincs jogunk megkérdezni, mi van a végtelen után. Persze azt is mondhatjuk, elég természetes elvárásunk, hogy a végtelen állapotsorozat utáni állapot az állapotsorozat határértéke legyen. Ekkor is bajban vagyunk azonban, mert visszajutunk egy el bbi problémához: mi a határértéke az a n
1 , ha n páratlan (világít az izzó), és a n
izzó) sorozatnak? Vagyis mi az összege az
sn
0 , ha n páros (lekapcsolt
1 1 1 1 1 1
...
1
n 1
részletösszeggel definiált sornak? Erre újra válaszolhatjuk, a kérdés értelmetlen, hiszen az a n
s n sorozat nem
konvergens. De miért ne lehetne valamilyen általánosabb értelemben az? Fejér Lipót mutatta meg 1900-ban, hogy van olyan „ lim* ” konvergenciafogalom, mely szerint 1 , és persze az összes hagyományos értelemben konvergens sorozatra igaz, 2
lim * a n n
hogy ha lim bn n
b , akkor lim * bn n
b.
Ötletének lényege, hogy minden an sorozatra képezhetjük az An
a1
a2
... a n n
Fejér-közép sorozatot, és an konvergenciájának vizsgálata helyett An -et tekintjük. Azonban ennél sokkal több is igaz, az amit Leibniz is megsejtett. 14
4.5.1.1. Tétel: Akárhogyan terjesszük is ki a konvergencia hagyományos fogalmát, a fenti sor összege, amennyiben létezik, mindenképpen
1 . 2
Bizonyítás: Természetes elvárásunk a konvergenciafogalom egy kiterjesztésével szemben, hogy additív legyen, és hogy a határérték ne függjön attól, honnan indul a sorozat.
an : sn
1 1 1 1 1 1
1;0;1;0;1;0;… Legyen bn
...
1
n 1
.
Ekkor
an
sn
tagjai
rendre
a n 1 . Tegyük fel, hogy valamely „lim**” értelemben
lim* * bn
lim* * a n
a.
Ily
lim* * a n
bn
2a felhasználva az additivitást. Mivel a „lim**” kiterjesztése a
n
n
módon
azonban
a
n
is
hagyományos „lim” konvergencia fogalmának, lim* * a n n
így a
teljesül.
bn
lim a n
n
Emiatt
bn
pedig
1 2a ,
1 . 2
A feladatunkra adható megoldás tehát: Az izzó értelmezheti tetszése szerint (
1 -es állapotban lesz . Ezt ki-ki 2
1 valószín séggel világít, pislákol, …), és itt újra 2
felmerülhet bennünk, nem jó egy-egy matematikai modellt olyan problémára alkalmazni, amelyre nem biztos, hogy kiterjed a hatásköre. 4.5.2. Szerencsére ennél a feladatnál nem okoz problémát az alkalmazhatóság, hiszen meghatároztuk, mit értünk a megmaradt aranyon. Kis gondolkodás után rájöhetünk, hogy a bolond akkor lophat igazán eredményesen, ha az els két alkalommal lopja el azt a két aranyat, amit a király az els alkalommal kapott, a harmadik és negyedik lépésben a király második alkalommal szerzett két aranyát, és így tovább a második hónap végéig. Ekkor a királynak semmije sem marad, hiszen nem lesz olyan arany, amit a bolond ne lopott volna el. Logikusnak látszik használni e feladatnál a halmazelméleti határérték fogalmát.4 Így is látható, hogy mivel lim n,2n
N
n
4
Definíció: lim inf An : n
, a királynak nem marad semmije sem. Ha
Am , lim sup An : n 1m n
n
Am , és ha e kett megegyezik, akkor mondjuk n 1m n
konvergensnek az An halmazsorozatot. Ekkor lim An : lim inf An n
n
15
lim sup An . n
viszont a bolond mohó, és minden alkalommal ellopja a befolyt két arany egyikét, akkor a királynak a harmadik hónapra megszámlálható végtelen sok aranya marad. A paradox helyzetet az teremti, hogy nem mindegy, melyik két aranyat lopja el a bolond, holott a hétköznapokban nyilván teljesen közömbös, melyik százasunkat adjuk a pénztárosnak, és
melyik ötforintosát adja ide visszajáróként, ha veszünk egy 95 forintos
csokoládét vagy akármennyi véges sokat. De ha a bolt olyan különleges, hogy a raktárban megszámlálhatóan végtelen sok csokoládé van, akkor ha van annyi százasom, amib l mindet megvehetem, célszer a pénztárcám tartalmát sorba rendezni (esetleg még marad benne valamennyi), és csak minden második százasommal fizetni a csokikért így megtartva magamnak még annyi pénzt, mint amennyivel a boltba bejöttem. A visszajáró ötforintosokat borravalóként ott is hagyhatom a pénztárosnak. Más kérdés, hogy ilyen esetben egyáltalán van-e értelme fizetni, hiszen attól a bolt bevétele úgysem változik semmit, ha már egyszer van annyi ötforintosa, hogy minden százasomból vissza tudjon adni.
Az
ezzel
kapcsolatos
úgynevezett
utilitáselméletet
valószín ségszámítási
paradoxonok feloldására is használják (7.4.2.). 4.5.3. Ennek a feladatnak a megoldása t nik a legegyszer bbnek, amennyiben birtokában vagyunk az integrálszámítás alkalmazási módszereinek a térfogatszámításban. R
V
lim
R
R
f
2
x dx
1
lim
R
1
R
A
A R
lim
R
1
1 dx x
lim 2
R
f x 1
'
f x
1
minoráns
lim ln x
R
kritérium R 1
1 dx x2
1 x
lim
R
R
R
lim
1
R
lim 2
1 1 x 1
1 dx x4
értelmében,
mivel
1 1 1 x x4
2
dx
R
1 1 R
1 , x
ha
x 1,
és
, a keresett felszín tehát végtelen.
Hol itt a paradoxon? A kellemetlen, de csak látszólagos ellentmondást az okozza, hogy ha
liter festéket töltünk az így kapott tölcsérbe, majd kiöntjük azt bel le,
tulajdonképpen befestettük a bels felszínét, holott az végtelen nagy, és így bármennyi véges festék egy véges darabjának befestésére lehet csak elég, ezért elfogy, miel tt az egészet befesthetnénk. Egy feloldási lehet ség megint a valóság és a matematikai absztrakció különválasztása: Egy valódi festéknek részecskéi vannak, melyek ha nagyon aprók is, mérettel rendelkeznek, és így az adott tölcsér valódi festékkel nem tölthet tele, hiszen a
16
sz kületben elakadnának a részecskék. Az ilyen valódi festék egy felszín befestésekor egyenletesen fogy szemben a matematikai festékkel, amely akármeddig osztható, nincsenek részecskéi, és így alkalmas akármekkora felület befestésére. Például a teljes síkot úgy lehet 1ml matematikai festékkel befesteni, hogy rajzolunk a síkra egy 1cm oldalú négyzetekb l álló hálót, az összes négyzetet megszámozzuk alkalmas módon a természetes számokkal5. Ezután pedig az els négyzetet
1 1 , a másodikat , az n-ediket 2 4
1 cm vastag réteggel vonjuk be. Ha ezt minden n N számra megtettük, a teljes síkot 2n
befestettük. 4.5.4. Jelölje s t a csiga távolságát a t id pillanatban a gumikötél azon végét l, melyet a manó húz, l t pedig a szalag hosszát a t id pontban. Be fogom bizonyítani, bármennyire is meglep , hogy a csiga elér a falig. Ebben az segít neki, hogy a mögötte lév
szalagdarabot is nyújtja a manó fejetlen rohanásában. A kulcsgondolat annak
vizsgálata, hányadát tette meg a csiga az útnak.
s1 l1
1 , mivel a háta mögötti darab nyúlásának köszönhet en kicsit több, mint 2000
1 cm-t tesz meg a csiga.
s2 l2
1 2000
1 3000
sn ln
1 2000
1 1 ... 3000 1000 n 1
Ha pedig sn ln
sn ln
1 1000
ln n 2
1 -gyé válik, a csiga már biztosan elért a falig. És mivel 1 2
1 1 ... n 1 3
1 1000
n 2
2
1 dx x
1 ln n 2 1000
1000 ln 2 , ez pedig teljesül, ha ln n 2
amihez elegend , hogyha n
ln 2
1001 , azaz n 2
1 , ha
e1001 ,
e1001 . Ezzel ekvivalens n 101001 lg e , ami igaz, ha n 10 435 .
Ez azt jelenti, hogy ennyi másodperc alatt, ami legfeljebb 3,17 10 427 év, biztosan elér a falig a csiga. Megjegyzem, hasonlóan alulról is becsülhet ez az id tartam:
5
Ez megtehet , hiszen Z Z megszámlálható. Például egy kitüntetett négyzett l indulva spirálszer en kell számozni.
17
s1 l1
2 , hiszen 2 cm-nél biztosan kevesebbet tesz meg a csiga minden 2000
másodpercben.6
s2 l2
2 2000
2 3000
sn ln
2 2000
2 2 ... 1000 n 1 3000
sn ln
2 1000
1 2
ln n 1
1 1 ... n 1 3
2 1000
n 1
1
1 dx x
1 ln n 1 500
ln 1
1
500 pedig fennáll, ha n 10 500 lg e 1 , ami teljesül már n 10 217 esetén,
vagyis a csigának legalább 10 217 másodperc kell, ami legalább 3,16 10 209 év. Összehasonlításképpen a világegyetem feltételezett kora, a távoli galaxisok sebességéb l és távolságából számolt Hubble-állandó alapján, 1,6 1010 év. Ha azonban a manó 10 cm/s, a csiga 1 cm/s sebességgel halad, a gumikötél 10 cm hosszú, a végkövetkeztetés ugyanolyan hihetetlen marad, de a csigának legfeljebb 7 óra is elég lesz a célbaéréshez. Ekkor a kötél 2,52 km hosszú, ami azt mutatja, hogy ez a 7 óra is elég sok.
5. A sas és a bolha si küzdelme, megszámlálható halmazok Egy különlegesen kicsinyes sasnak az a f életcélja, hogy bolhákra vadásszon minél ügyesebben. Mint azt látni fogjuk, ez egyáltalán nem egyszer
feladat. A bolhák egy
derékszög koordinátarendszer rácspontjain ugrálnak. A sas minden tizedik másodperc végén lecsaphat egy el re kijelölt rácspontra, a bolha pedig minden tizedik másodpercet megel
másodperc elején ugorgat egyet. A sas akkor fogta meg a bolhát, ha éppen arra
a rácspontra csapott le, melyen a bolha tartózkodott abban a pillanatban. Az a kérdés, megfogja-e a sas az egyes bolhákat véges id alatt? 5.1. Az els bolha az origóból indul, és minden alkalommal ugyanabba az irányba ugyanakkorát ugrik, azaz egy origón átmen egyenesen halad egyenl (akármekkora) ugrásokkal. 5.2. A második bolha már nem az origóból indul, hanem a koordinátarendszer tetsz leges pontjából, de mindig ugyanakkorákat ugorva halad. 6
2 cm-t akkor tehetne meg az els másodpercben, ha el nyt kapna a manótól, mászhatna 1cm-t, és a manó csak ezután húzná ki ugrásszer en 20 cm-esre a 10 cm hosszú kötelet. Kés bbi másodpercekben még így se sikerülne 2 cm-t megtennie.
18
5.3. A harmadik bolhának apai ágon családi öröksége egy P t ; Q t
rendezett pár,
ahol P(t) és Q(t) két egész együtthatós akárhanyadfokú polinom, és a bolha t-edik helyzetének koordinátáit ez alapján számolja ki. 5.4. A negyedik bolha az 1;1000
1;1000 négyzet egymillió rácspontján ugrál
teljesen véletlenszer en, vagyis minden lépésben akármekkorát ugorhat akármilyen irányba a kijelölt területen. 5.5. Az ötödik bolha, a negyedik unokatestvére, teljesen véletlenszer en ugrál a Z Z rácson, ami azt jelenti, hogy minden pillanatban minden rácsponton azonos valószín séggel található meg. 5.6. Megoldások: Els
látásra azt gondolnánk, olyan nagy szabadságot ad a feladat a bolháknak,
amellyel szemben a sas tehetetlen. Éppen ezért meglep dünk, ha gondosabban is megvizsgáljuk a lehet ségeket. Ha ugyanis az adott bolha minden lehetséges helyzete megszámlálható, akkor sasunknak nincs más dolga, mint valamilyen elv szerint sorba rendezni a bolha egyes id pontokban lehetséges pozícióit, majd végighaladva a sorban megtalálni a bolha tényleges helyét. Ez minden esetben véges id alatt történik, ami nem jelent többet, mint hogy a sas nem kénytelen örökké keresgélni. Azt azonban nem tudjuk garantálni, hogy egy el re adott véges id tartam elegend neki. 5.6.1. Az els bolha els ugrásának eredményeként létrejöv lehetséges helyzetei sorba rendezhet ek, hiszen Z Z elemei felf zhet ek egy origóból induló csigavonalra az els ábrán látható módon.
1. ábra 19
Azonban ez az indulást közvetlenül követ , els helyzet egyértelm en meghatározza a bolha kés bbi helyzeteit. Így elég, ha a sas a bolha els pozícióját találgatja, és minden id pontban arra a pontra csap le, amely a feltételezett els helyzethez tartozna az adott id pontban, azaz el bbi csigavonalunk helyett egy egyre szélesed másik spirál mentén kell haladnia, ahogy azt a második ábra mutatja.
2. ábra Vagyis ha x t ; y t
jelöli az els ábra csavarvonalának t-edik pontját (els pontja
az origó), akkor a második spirálunk t-edik pontja t x t ; t y t . Erre a pontra kell lecsapnia sasunknak a t-edik alkalommal, azaz a 10t-edik másodpercben. 5.6.2. A második bolha elkapásához az el
feladat eredményét is használhatjuk.
Nyilvánvaló, hogy ha minden olyan A; B rendezett párt végigpróbálunk, melyben A a bolha kiindulópontja B pedig els
ugrását (és így mindegyiket) jellemz
vektor a
koordinátarendszerben, akkor megtaláljuk az egyetlen lehetséges paraméterpárt, mely a bolha pályáját jellemzi. A-t is és B-t is találgathatjuk az el
feladat els csigavonala
mentén haladva, csak A és B próbálgatását ügyesen kell összefésülni egy próbálgatássá. Ebben hasznunkra lehet az x t számok mindegyikét akárhányszor felveszi. Az
A; B -
1 függvény, mert ez a pozitív egész xt
1; y t
1 pár pedig minden
pozitív egészekb l álló számpárt hozzárendel valamely pozitív számhoz (esetleg többhöz is). Tehát A; B -t találgathatjuk
x xt
1;y x t
20
1 ; x yt
1; y y t
1
alakban,
s ekkor valóban minden lehet séget végignézünk. Ennek megfelel en a sas t-edik helyzetének koordinátái x x t
1
t x yt
1;y x t
1
1 .
t y yt
5.6.3. A harmadik bolha már nagyobb ellenfél, megfogásához új ötlet kell! Ha valamilyen módon fel tudnánk sorolni az összes elképzelhet
P x ;Q x
egész
együtthatós, rendezett polinompárt, más dolgunk se maradna, mint ezt a módszert a sasnak elmondani, aki ezután a bolhát már elkapottnak is tekinthetné. Egy ilyen taktika lehet a következ : A természetes számokat írjuk fel kettes számrendszerben, ezután pedig nevezzük szabályosnak azokat a számokat, melyekben legalább három egyes szerepel, és utolsó jegyük is egyes. (Ily módon minden páros szám szabálytalan.) Ha a számban n+1 darab egyes van, rendeljük e számhoz els lépésben azt a szám-n-est, melynek k-adik tagja a tízes számrendszerben felírt azon szám, amennyi nulla az n+1 darab egyes által képezett n köz közül a k-adik helyen van. Második lépésben daraboljuk két részre az így kapott szám-n-esünket úgy, hogy tagjai felváltva kerüljenek az els és a második részbe. A darabolást mindig hátulról kezdjük, és a szám-n-es utolsó tagja kerüljön a második darab végére! Harmadik lépésben e két véges számsorozatot egy-egy polinom együtthatósorozataként felfogva e két polinomból álló párt feleltetjük meg eredeti számunknak. Például a t=2613-hoz, amelynek a kettes számrendszerbeli alakja az 101000110101 2 jelsorozat, a következ 101000110101 2
I.
Pt x ; Qt x párt rendeljük: 1;3;0;1;1
Ezáltal minden elképzelhet
II .
3;1 ; 1;0;1
III .
3x 1 ; x 2 1
Pt x ; Qt x
polinompárt megfeleltettünk valamely szabályos
számnak (esetleg többnek is 7). Ha tehát a sas a t-edik alkalommal lecsap a Pt t ; Qt t pontra, ha t szabályos, más esetben pedig pihen, a bolhát véges id alatt elkapja. Ez a módszer az összes korábbi bolha esetében használható, hiszen azok taktikái a harmadik bolha menetmódjának speciális esetei. 5.6.4. Eddig minden bolha lehetséges pályái megszámlálható sokan voltak, ám a negyedikéi annyian vannak, mint ahány leképezés létezik N-b l egy egymillió elem halmazba. Ez már több mint megszámlálható, hiszen N összes részhalmazai annyian vannak, mint amennyi a leképezések száma N-b l a 0;1 kételem
7
2
halmazba8. Egy
A fenti 3x 1 ; x 1 párt a 1101000110101 2 számnak is megfeleltettük. N minden eleméhez aszerint rendeljünk 1-et vagy 0-t, hogy benne van vagy nincs benne N egy adott részhalmazában! Ekkor kölcsönösen egyértelm módon felel meg N minden részhalmazának egy-egy N-b l a kételem 0;1 halmazba történ leképezés. A kés bb szerepl 8.2-es definíciónk értelmében tehát e két halmaz számossága megegyezik. 8
21
halmaz hatványhalmazának számossága pedig mindig nagyobb a halmazénál (9.2. tétel), az pedig világos, hogy legalább annyi leképezés létezik N-b l egy több elem halmazba, mint N-b l egy kételem be. Azaz a negyedik bolha pályáit nem tudjuk felsorolni, új módszert kell keresnünk. Tanulhatunk magától a bolhától, vagyis alkalmazhatjuk a véletlen hatalmát a bolha kézre kerítésében. Mivel jobbat nem tud, csapkodjon a sas véletlenszer en a 1;1000 bolhát els re eltalálja:
1;1000 rácspontjain. Ekkor annak valószín sége, hogy a
1 , 1000000
annak, hogy els re nem, de másodikra igen:
999999 1 , 1000000 1000000
999999 annak, hogy els n-1 alkalommal nem, de n-edikre igen: 1000000
n 1
1 , 1000000
annak pedig, hogy az els n alkalom valamelyikében eltalálja, ezen diszjunkt események valószín ségeinek összege: Pn
1 1000000
1
Ez pedig éppen 1 Mivel ha n
999999 1000000
999999 1000000
2
999999 1000000
n 1
1 0,999999 n 1 1000000 0,999999 1
n
0,999999 .
, e valószín ség 1-hez tart, lesz olyan id pont, amikor a sas már
0,99 valószín séggel elkapta a bolhát. Annak valószín sége pedig, hogy valaha elkapja, éppen az a bizonyos 1 határérték. Így biztos, hogy véges id n belül karmai közé kerül a bolha. 5.6.5. Az ötödik bolha nem létezik, tehát elkapni sem lehet. Ha ugyanis feltesszük, hogy p valószín séggel tartózkodik egy adott rácsponton, és p>0, akkor p akármilyen kicsi is, tudunk olyan nagy természetes n-et választani, hogy 0
1 n
p . Ekkor viszont
annak valószín sége, hogy a bolha valamely kitüntetett n rácsponton tartózkodik: n p
n
1 n
1 , ami nyilvánvalóan lehetetlen. Ha pedig p=0, akkor annak valószín sége,
0
hogy a bolha a Z Z rácson van,
0 vagyis a bolha nem létezik, legalábbis a Z Z
i 1
rácson nem. Azért érdemes elgondolkodni rajta, lehet-e a teljes Z Z-n véletlenszer en ugrálni. Ehhez mindenekel tt kell egy valószín ségi eloszlási függvény, mely a rács minden pontjához rendel egy-egy pozitív valós számot, melyeknek összege a teljes rácson 1. Ezek 22
a számok adják meg az egyes pontokon való tartózkodás valószín ségét. Ilyen függvény nagyon sok van. Azonban ha például azt tudjuk egy bolháról, hogy Z Z véges sok pontján mi persze nem tudjuk, melyeken
ugrál azonos valószín séggel, elkaphatjuk a
negyedik stratégia apró módosításával és az els
feladat x t függvénye segítségével.
Csapjon ugyanis le a sas a t-edik alkalommal azon négyzet egy pontjára a négyzeten egyenletes eloszlással, melynek egyik csúcsa
x t ; x t , középpontja pedig az origó.
Ekkor, mivel x t minden egész számot felvesz végtelen sokszor, ha t végigfut N elemein, bármely n-hez és bármely origó középpontú négyzethez létezik olyan t, hogy a t-edik id pontig a négyzetre n-szer már lecsapott a sas. Így, mivel Z Z-nek minden véges részhalmaza korlátos, egy id után a bolha élettere is benne lesz valamely négyzetben, melyet a sas már n-szer kiválasztott. Ha pedig n-et elég nagynak választjuk, annak valószín sége, hogy sasunk megfogta a bolhát, 1-hez tetsz legesen közel vihet . Így véges id alatt ezt a bolhát is megfoghatjuk 1 valószín séggel.
6. Egy logikai csemege 6.1. A sivatagi vándor útelágazáshoz ér. Az egyik út a mennyországba, a másik a pokolba vezet. Két alak áll az útkeresztez désnél, az egyik angyal, a másik ördög, de küls re mindketten egyformák. Az angyal mindig igazat mond, az ördög mindig hazudik. Egyetlen eldöntend kérdést tehetünk föl az egyiküknek, akir l persze mi nem tudjuk, melyik. Mit kérdezzünk, hogy rátaláljunk a mennyországba vezet útra? 6.2. Találjunk ki olyan kérdést is, ami akkor is m ködik, ha csak egyvalaki áll az útkeresztez désben, akir l nem tudjuk, hogy ördög, angyal vagy rabszolga. A rabszolgának van egy napi parancslistája, melyben „Hazudj!” és „Mondj igazat!” utasítások váltakoznak valamilyen rendszer szerint, és amelyet
kívülr l tud. Az aznap
feltett n-edik kérdésre aszerint mond igazat, vagy hazudik, hogy mi a lista n-edik utasítása. 6.3. Mit kérdezzünk akkor, ha az útelágazásnál angyal, ördög, rabszolga vagy furfangos szegény ember áll, és mi nem tudjuk megkülönböztetni
ket. A furfangos
szegény ember néha igazat mond, néha hazudik, de hogy mit tesz, azt csak akkor dönti el, ha már elhangzott a kérdés. 6.4. Ha az el
feladatot megoldottuk, válaszoljunk arra a kérdésre is,
alkalmazható-e a módszerünk a valóságban! Például ha egy bíró ismeri a megoldást, segít-
23
e ez neki a vádlott kérdezésében? Lehet-e úgy kérdezni a vádlottat, hogy akár igazat mondana, akár hazudna, kiderülne az igazság, még tanúk se kellenének. 6.5. Megoldások: 6.5.1. Két módon próbálkozhatunk. Mindenekel tt olyan kérdést kell feltennünk, melynek tartalma függ attól, kit l kérdezzük. Egy jó lehet ség erre a személyes névmások vagy névmás értelm szavak ügyes használata. Például odamenve egyikükhöz rámutatunk az egyik útra, és megkérdezzük t le: Ha a társadtól kérdezném, ez az út vezet-e a mennyországba, igent mondana? Ha erre a megkérdezett igennel válaszol, akkor függetlenül attól, angyal-e vagy ördög, az út, amire mutattunk, a pokolba vezet. Hasonlóan ha nemet válaszol, az út a mennyországba visz. Ezzel a kérdéssel tulajdonképpen az angyalt vesszük rá a tagadásra, hiszen híven
szintén megmondja, mit válaszolna az ördög. Az ördög pedig
szokásához
letagadja az angyal igaz válaszát. A kulcsszó szó ez esetben a „társad” volt, mely
az egyes szám harmadik személy névmás helyett állt. További jó megoldás, ha rámutatva az egyik útra azt kérdezzük egyikükt l: Igaz-e, hogy te vagy ördög vagy, vagy ez az út a pokolba vezet?9 Itt az „igen” válasz a pokolba vezet
utat mutatja meg. Ez azért alakul ilyen
szerencsésen, mert az angyal esetében az összetett állítás els része hamis, ezért csak úgy lehet igaz a teljes állítás, ha a második fele igaz. Ha pedig az ördög válaszolt igennel, akkor
mivel negálta az összetett állítás igazságértékét
az állítás hamis. Az els fele
viszont igaz, de ez csak úgy lehetséges, ha a második fele is az. Hasonló gondolatmenet adja, hogy „nem” választ akkor kapunk, ha a mennybe vezet útra mutattunk. A megfelel névmás ez esetben a második személyt megjelöl „te” volt. Újabb megoldás a következ kérdés is: Igaz-e, hogy te akkor és csak akkor vagy ördög, ha ez az út a pokolba visz? Az el
höz teljesen hasonlóképpen kapjuk, hogy itt az „igen” jelenti a
mennyországot, a nem pedig a „poklot”. És még több megoldást ad, ha az el
két kérdést úgy módosítjuk, hogy az „ördög”
szót „angyal”-ra, vagy a „pokol” szót „mennyország”-ra cseréljük. Arra kell csak figyelnünk, hogy az egyes esetekben a kapott „igen” illetve „nem” válasz mit jelent.
9
A „vagy” köt szót páros köt szóként
megállapodás szerint
24
kizáró értelemben használom.
6.5.2. A következ , általánosabb eset megoldásához is alkalmazható az el gondolat. Csak most egy kicsit változtatnunk kell rajta. Az egyik lehet ség a következ : Ha most azt kérdeztem volna t led, ez az út vezet-e a mennyországba, igent mondtál volna? Ez a nagyon ravasz kérdés a rabszolgát és az ördögöt is rákényszeríti az egyenes válaszra: ha a rabszolga eldöntötte, hogy hazudni fog, kétszeres tagadásra veszi rá. Azonban nem alkalmazható a következ feladat megoldására, mivel csak akkor hatékony, ha olyannak tesszük fel, aki el re eldönti, egy adott pillanatban feltett kérdésre igazat mond-e vagy hazudik. 6.5.3. Bár a harmadik feladat megoldásához nem használhatjuk a másodikét, de az els összetett kérdéseit módosíthatjuk úgy, hogy alkalmazható legyen ez esetben is. Így persze az el
feladatokra is további megoldásokat kapunk:
Igaz-e, hogy te vagy hazudsz most nekem, vagy ez az út a pokolba vezet? Igaz-e, hogy te akkor és csak akkor hazudsz most nekem, ha ez az út a pokolba visz? Természetesen itt is kicserélhet ek a „hazudsz most nekem” szavak „igazat mondasz most nekem”-re, vagy a „pokol” „mennyországra”, és az így kapott kérdés is m ködik. Az érvelés is ugyanaz, mint az els feladatnál, csak az angyal mellé még be kell vennünk a furfangos szegény embert és a rabszolgát, aki az adott pillanatban igazat mond, az ördög mellé pedig azt, aki az adott pillanatban hazudik. 6.5.4. Az utolsó feladatra
azt gondolhatnánk
megoldás lehet a következ
kérdés: Igaz-e, hogy te akkor és csak akkor hazudsz most nekem, ha elkövetted azt a ncselekményt, amivel gyanúsítanak? Vagy megkérdezhetnénk a következ t: Igaz-e, hogy te vagy hazudsz most nekem, vagy elkövetted a b ncselekményt, amivel gyanúsítanak? Pedig e kérdésekre a valóságban kaphatunk akár ilyen választ is: ,
!
No de az ilyen problémák egy tolmács segítségével kiküszöbölhet ek. Azonban még ekkor is el fordulhat, hogy a gyanúsított nem érti, mit jelent az „akkor és csak akkor” logikai m velet, így pedig nem is adhat kérdésünkre logikus választ. Vagy egy hamiskártyást mi akadályoz meg abban, hogy feldobjon egy érmét, és fej esetén igent, írás
25
esetén nemet válaszoljon. S t igazán okos b nöz esetén még az is elképzelhet , hogy bár a kérdést érti
direkt olyan választ ad, amelyr l tudja, levezethet
ártatlansága, ha feltételezzük,
bel le az
egyike a feladatokban szerepl típusoknak.
Most kell körültekint nek lennünk. Hallgatólagosan esetleg feltételezhettük, hogy egy valódi ember úgy viselkedik, mint a feladatbeli furfangos szegény ember, azaz néha igazat mond, néha hazudik, és hogy mit tesz, azt akkor dönti el, amikor már elhangzott a kérdés. Pedig a valóságban az emberek néha igazat mondanak, néha hazudnak, de az is el fordul elég sokszor, hogy értelmetlen választ adnak. Ez nyilvánvaló abban az esetben, ha például valaki arra a kérdésre, n s-e, azt válaszolja, hogy négyzetszám. Ám láttuk
mint azt
egy eldöntend kérdésre lehet értelmetlenül felelni igennel vagy nemmel is.
7. Néhány valószín ségszámítási paradoxon 7.1. Az ajándékozás paradoxonja: Egy osztályf nök karácsonyi ajándékozást szervez. Minden diák készít egy ajándékot otthon, amit aztán elhoz az iskolába, és beletesz egy nagy zsákba. Az osztályf nök véletlenszer en kisorsolja a zsákban lév tárgyakat a jelenlev k között, és meg van nyugodva, hogy valószín leg senki sem fogja a saját ajándékát visszakapni, mert elég nagy létszámú az osztály. Van alapja a nyugalmának? 7.2. A szentpétervári paradoxon: Egy szabályos pénzérmét addig dobálunk, amíg fejet nem kapunk. Ha ez els re sikerül, kapunk a banktól 2 forintot, ha csak másodikra, akkor 4-et, ha pedig csak n-edikre, akkor 2 n -et. Mennyit fizessünk a banknak, hogy a játék méltányos, azaz a befizetés éppen a várható értéke legyen? 7.3. Schrödinger paradoxonja: Két ember szerencsejátékot játszik. A játékvezet véletlenszer en felír az egyikük homlokára egy természetes számot, a másikéra pedig eggyel többet. (A sorrendet a játékvezet dönti el véletlenszer en, tehát a játékosok a felírás sorrendjéb l semmit sem tudnak kikövetkeztetni.) A játékos csak az ellenfele homlokát látja. Választhat, kiszáll-e vagy játszik. Ha kiszáll, nem veszít és nem nyer, ha viszont a mindketten a játék mellett döntenek, az nyer, akinek a homlokán nagyobb a szám, annyi forintot a másiktól, mint amekkora számmal nyert. Ha ellenfelem homlokán n-et látok, érdemes-e játszanom?
26
7.4. Megoldások: 7.4.1. Az ajándékozás paradoxonja: Ennél a feladatnál érdemes meggondolni, mekkora annak a valószín sége, hogy egy el re kiválasztott diák visszakapja az ajándékát. Képzelhetjük úgy, hogy a tanulók névsor szerint sorba állnak, és ezután az ajándékokat ilyen sorrendben véletlenszer en kapják meg. Ekkor annak valószín sége, hogy egy n 1! n!
kiválasztott a saját ajándékát kapja
1 , ami csakugyan n növekedésével egyre n
kisebbé válik. Ám ha annak a valószín ségét akarjuk megkapni, hogy senki sem kapja vissza az ajándékát, számolhatunk a Poincaré-formulával, mely szerint
p A1
A2
1 p A1
An
n
1 p A1 A2
p An 1 An 1
n
p A2
n 1 n n!
1 1 2! 3!
1
n
An
p An 1
p A1 A2 n n 2! 2 n!
1 n n
p A1 A3 n n 3! 3 n!
1 n!
Itt Ai jelenti azt az eseményt, hogy az i-edik tanuló a saját ajándékát kapja vissza. Ez a valószín ség pedig mindig kisebb hiszen
1 -nél10. Így az osztályf nök nyugalma alaptalan, 2
1 -nél nagyobb valószín séggel lesz olyan valaki, aki a saját ajándékát kapja 2
vissza. 7.4.2. A szentpétervári paradoxon: A paradox eredmény az, hogy a játék várható értéke végtelen, mert E
1 2 2
1 4 4
1 n 2 2n
1 1
1
A paradoxon egyszer en feloldható. A valóságban egyetlen bank sem tud akármennyi pénzt felajánlani. Ha például legfeljebb tízmilliót hajlandó fizetni, akárhányadikra is dobok fejet, a várható érték:
E
1 2 2
1 4 4
1 23 2 2 23
1 2 24
1 2 25
10 7
23
10 7 2 23
23 1,19
24,19
Tehát 25 forint befizetése esetén a bank egy kicsit jól is jár. Ez pedig már elfogadható eredmény.
10
Érdekes megnézni, ha n végtelenbe tart, mi lesz e valószín ség határértéke. Már nem is olyan meglep , hogy
éppen
1 . e
27
Egy másik feloldási lehet ség a már említett utilitáselmélet oldaláról közelít. Elfogadja, hogy a bank akármennyi pénzt ki tud fizetni, mondjuk úgy, hogy szerz dést ír alá valahány éven belüli kamatos törlesztésr l. Ám a játékosnak nem ugyanannyit ér egyegy forint, ha más-más pénzösszeggel rendelkezik. Feltételezzük, hogy minden embernek van egy utilitásfüggvénye, mely minden valós, pozitív x-re megadja, mennyire örül az adott ember x forintnak. Egy átlagos ember utilitásfüggvénye szigorúan monoton növekv , konkáv, hiszen minél nagyobb pénzösszeggel rendelkezik, annál kevésbé örül egy újabb forintnak, de azért nagyobb összegnek jobban örül. A konkávság a kockázatkerülésr l is árulkodik, mert ha valahány forint birtokában ennek az embernek felajánlják, hogy
1 valószín séggel nyerhet s forintot és ugyanekkora valószín séggel 2
veszíthet is ennyit egy játékban, akkor nem fog játszani, mert egy már meglév forint többet ér neki mint egy kés bb nyerhet .
3. ábra Az ábrán berajzolt várható „haszon” egy az utilitásfüggvényen felvett húr felez pontja, mely egy konkáv függvény esetén a függvény grafikonja alatt helyezkedik el. Vizsgáljunk egy konkrét függvényt, az u1 x konkáv, mert u1 ' ' x
1 x2
ln x legyen ez. Az u1 x nyilván
0 minden pozitív x-re. Most azzal ne tör djünk, hogy 0 és 1
között negatív értékeket vesz fel. Számoljuk ki a játék várható utilitását a várható érték helyett!
E u1 x
1 ln 2 2
1 ln 4 4
összege pedig 2 ln 2 , mert E u1 x
1 ln 2 n 2n ln 2 n 1k
ln 2 n
1 k n 2
n . Ennek a sornak az n 1 2 1
ln 2 n 1
2
n 1
ln 2 n
1 n 0 2
2 ln 2 .
Mennyit kell hát fizetnie a játékosnak? Annyi pénzt, amennyinek 2ln2 mértékben örül.
28
összeget, akkor ln x
Vagyis ha x-szel jelöljük a befizetend
2 ln 2
ln 2 2
ln 4 . E
játékos számára tehát akkor igazságos a játék, ha 4 forintot fizet játszmánként. De vizsgálhatjuk a 1
u2 ' ' x
4 x
x -et is. Ez a függvény is konkáv, mert
u2 x
0 minden pozitív x-re.
3
E u2 x n
1 n 1 2
2
1
n
2
n 0
utilitáshoz pedig éppen
2 1
2
2n
2
n n 1
1 2
n
1 2 1
2 1.
Ekkora
3 2 2 forintot kéne befizetni, tehát ha a bank 6
forintot kér, a játékos már kicsit rosszul is érezheti magát. Azt azonban nem állítom, hogy minden konkáv utilitásfüggvény megoldja a problémát, mert például a u 3 x
1 x ln x is konkáv, hiszen második deriváltja az ln x 2
második deriváltjának fele, ami minden pozitív valós számon negatív értéket vesz föl. Ráadásul u 3 x Ám
x , tehát esélyes lehetne a paradoxon feloldására.
1 2 ln 2 2 2
E u3 x
1 2n 2n
1 4 ln 4 4 2
ln 2 n 2
1 2n 2 n 1 2n
.
Tehát visszakerülnénk az eredeti problémához. Az pedig biztos, hogy: 7.4.2.1. Tétel: Egyetlen kockázatkedvel
ember utilitásfüggvénye esetén sem
oldódik fel a paradoxon, azaz nem lesz véges a várható utilitás egyetlen konvex, monoton növekv függvényre sem. Bizonyítás: Tekintsünk ugyanis egy monoton növekv , a pozitív számokon értelmezett, konvex f x -et! Tudjuk, hogy f x konvex definíció szerint pontosan akkor, ha minden az értelmezési tartományába es teljesül az f
0
x1
x1
1
x2
f x1
1
x1 -re és x 2 -re valamint minden f x2
0;1 -re
egyenl tlenség. Válasszunk ki egy
x 2 változópárt. Ekkor állítom, hogy:
7.4.2.1.1. Lemma: Minden x
x2 ; f x 2
x 2 -re az f x függvény értéke az x1 ; f x1
pontokon átmen , f x monotonitása miatt pozitív meredekség
és az
g x húr
fölött van. A lemma bizonyítása: Tegyük fel, hogy nem így van, azaz f konvex, 0 mégis létezik olyan x 2 -nél nagyobb x3 , melyre f x3
29
f x2 x2
f x1 x3 x1
x1
x1
x2 ,
f x1 .
4. ábra
f x3 x3
Ezzel ekvivalens az
(1.)-gyel! Legyen
f
f x1
x3 x3
x2 . Ekkor x1
x1
1
x3 x3
f x3
1
f x1 x1
x3
f x2 x2
x3 x3
f
x2 f x1 x1
Ez viszont azt jelenti, hogy f átrendezve kapjuk, hogy f x 2
x2 x1 x1
x2 x3 x1
x2 x3
x1 x3 x1
x3
f x1
f x1 x2 x1
f x 2 , és
f x3 x3
x1 f x3 x1
1
f x3 x3
f x1 . Jelöljük ezt az egyenl tlenséget x1
x1
f x1 x2 x1
x1
f x1 .
f x3 , mert (1.)-et
1
f x1 , ez pedig ellentmond f
konvexitásának.
Legyen g x és f x N
g x , ha x
n k
1 f 2n n 2
AN
N
AN :
mx c az említett húr egyenlete! Mint már megállapítottuk, m
N n
x 2 a most bizonyított lemma szerint. Tehát ha k 1 m 2n n k 2 N
km
c n k
1 2n
N
N
c
m n k
N
km
n k
c n k
0,
x 2 , akkor
c . 2n 1 2n
N k
és így AN is végtelenbe tart, emiatt pedig E f x n
km
1 f 2n n 1 2
c 2k
1
lim AN
N
, ha N
,
.
7.4.3. Schrödinger paradoxonja: A megoldás az, hogy érdemes játszani, hiszen ha n>0, és n-et látok az ellenfél homlokán, akkor az én homlokomon
30
1 valószín séggel van 2
n+1 és
1 valószín séggel n-1, tehát a várható érték E 2
n=0, akkor
mivel az én homlokomon biztosan 1 van
1 n 1 2
1 n 1 2
1 , ha pedig
a várható érték szintén E=1, azaz
1 forintot nyerhetek átlagosan minden játszmában, amelyben ellenfelem homlokán n forintot látok. Hol itt a paradoxon? Gondoljuk meg, hogy az n bármely természetes szám lehet, tehát mindig megéri játszanom. A játék azonban szimmetrikus, tehát mindkett nknek mindig megéri játszani, vagyis hosszú távon mindkett nk pénze gyarapodik. Így lehet tehát a semmib l pénzt csinálni, hiszen pénzt a játékosok kívülr l nem kapnak, egymásét nyerik el. Mi hát a hiba? Az igazság az, hogy érvelésünk több sebb l is vérzik. Az egyik hiba a feladat kit zésében rejt zik, erre úgy lehet rájönni, hogy az ember elgondolkodik rajta, mikor van értelme várható értéket számolni rögzített n esetén. Nyilván csak akkor, ha hosszú távon többször is kerülök abba a helyzetbe, hogy ellenfelem homlokán n-et látok. De mi biztosítja ezt, ha egyszer végtelen sok lehetséges n van? Itt értjük meg, hogy a természetes számok halmazán nincs egyenletes valószín ségi eloszlás, ahogyan azt az ötödik bolha esetének tárgyalásakor is beláttuk a sas és a bolha paradox küzdelmér l szóló fejezetben (5.6.5.). Ez a feloldás a problémát a mértékelmélet oldaláról közelíti meg, amire még visszatérek. Ugyanakkor, mint már megállapítottuk, ebben a feladatban más hiba is van, hiszen ahhoz, hogy gondolatmenetünk tényleg minden n-re m ködjön, rendelkeznünk kéne annyi pénzösszeggel, amib l ellenfelünket kifizethetjük tetsz leges n esetén, mivel pedig n akármekkora lehet, ez az összeg végtelen. Ha pedig már rendelkezünk végtelen sok forinttal, teljesen értelmetlen céljából
nyerés
várható értéket számolni.
8. „Látom, de nem hiszem!” Ebben a fejezetben arról lesz szó, hogy amint egy fogalmat definiálunk, az önálló életre kel. Amikor a definíciót megalkottuk, annak egy szemléletes tartalmára gondoltunk, ám rendszerint definíciónk olyan dolgokat is magába foglal, amikr l nem is álmodtunk korábban. Például egy függvény folytonosságát hogyan fogalmaztuk meg? 8.1. Definíció: Az f x függvény az értelmezési tartományának egy x0 pontjában folytonos, ha i.)
van x0 -nak az értelmezési tartományba es környezete,
31
ii.)
minden olyan x n sorozatra, melyre x n
x0 igaz, f x n
f x 0 is igaz.
Ezzel a precíz meghatározással azt a szemléletes tartalmat akartuk megragadni, hogy az f x grafikonja a ceruza felemelése nélkül rajzolható meg. Ám e fogalom sokmindent megenged. Ugyan ki gondolt volna a definiáláskor olyan a teljes R-en értelmezett függvényre, mely összesen egy pontban folytonos? Pedig ilyen például az f x
x 2 , ha x racionális,
f x
0 különben.
Vagy tekintsük a Riemann-függvényt, mely minden 0;1 -beli irracionális pontban folytonos, de egyetlen racionálisban sem: Legyen x
0;1 , és
r x
1 , ha x q
r x
0 különben.
p , ahol p, q N, lnko(p;q)=1 és q q
0,
(Az irracionális pontokban való folytonosság belátásához elég meggondolni, hogy ha q rögzített pozitív egész, tetsz leges s irracionális szám egy környezetében legfeljebb véges sok q-nál kisebb nevez
racionális szám van. Így van olyan kis környezete s-nek,
melyben csupa q-nál nagyobb nevez
törtek vannak.)
Az infinitezimális mennyiségek azonban a végtelennek csak az egyik arcát mutatják meg. A másik, legalább ennyire különös arcát a transzfinit számok mögé rejti. 8.2. Definíció: Az A és B halmazok ekvivalensek, ha létezik f: A B bijekció. Ilyenkor azt is mondjuk, hogy a két halmaz számossága megegyezik. Jelei: A~B vagy A
B.
8.3. Definíció: A
B , ha létezik f: A B injektív leképezés.
8.4. Definíció: Az N-nel ekvivalens és a véges halmazok megszámlálhatóak, az Rrel ekvivalensek pedig kontinuum számosságúak. 8.5. Definíció: Végtelen halmazok számosságait transzfinit számoknak nevezzük. A definíció megalkotói még nem sejtették, hogy R és R R ekvivalensnek fognak bizonyulni. Ezt bizonyítják Cantor címben idézett szavai is. Valóban ha tekintjük az
f x
x;0 ,
0;1
0;1
0, x1 y1 x 2 y 2
xn y n
, 0;1
0;1 , 0;1
és
a
g 0, x1 x 2
xn
;0, y1 y 2
yn
0;1 függvényeket, ahol g tizedes tört párt képez
32
tizedes törtbe, és az argumentumában nem engedünk meg egymást követ végtelen sok 9est, akkor
k tanúsítják a meglep ekvivalenciát11.
mindkét függvény injektív lévén
8.6. A Cantor-halmaz Aztán olyan halmazok is vannak, melyek túl kicsinek t nnek ahhoz, hogy R-rel ekvivalensek legyenek, mégis azok. Ilyen a Cantor-halmaz (jele: C) is. Harmadoljuk a
0;1
intervallumot, és hagyjuk el a középs
szakaszt végpontjai nélkül, majd a
megmaradó szakaszokkal ismételjük ezt az eljárást, és így tovább. A Cantor-halmaz azoknak a pontoknak a halmaza, amik akárhány lépés után is megmaradnak. Az rögtön látható, hogy mivel minden lépésben kétharmadára csökken a közelít
intervallumok
hossza, C hossza csak 0 lehet. El ször azt hihetnénk, C az egymás utáni lépésekben kialakuló szakaszok végpontjaiból áll, de ez nem így van. Mivel az n-edik lépésben a 0;1 pontjai közül azokat hagyjuk el, melyeknek bármely hármas számrendszerbeli alakjában, az n-edik tizedesjegye 1-es, ezért C azon pontok halmaza, melyeknek van olyan harmadostört alakja, amiben nem szerepel az 1-es. Innen pedig már látható, hogy C~R, azaz C kontinuum számosságú. Hiszen elég ha tekintjük az f 0, a1 a 2 ai
0;1 , bi
an
2
0, b1b2
bn
3
, 0;1
C injektív leképezést, ahol
2a i minden i N-re, és f argumentumában nem engedünk meg egymást
követ végtelen sok 1-est. g x
x pedig a fordított irányú injektív leképezés.
8.7. Az ördögi lépcs A Cantor-halmaz ad lehet séget egy újabb paradox függvény, az ördögi lépcs
konstrukciójakor az els
x
1 2 ; , és l x 9 9
1 2 ; . A függvényt tehát megadtuk a C 3 3
1 ha x 2
megalkotására. Legyen l x
lépésben elhagyott helyen. Legyen továbbá l x
3 , ha x 4
1 , ha 4
7 8 ; . Ezzel l-et meghatároztuk a konstrukció második 9 9
lépésében elhagyott intervallumokon. Hasonlóan definiálható l minden 0;1 -beli, C-hez nem tartozó pontban. C\ 0 pontjaiban pedig legyen l x : sup l t : t
l0
0; x , t
C ,és
0.
11
R és 0;1 ekvivalenciáját az olvasó könnyen bebizonyíthatja, elhallgattam azonban egy aprónak nem mondható technikai részletet. Én injektív függvényeket használtam, nem egy bijekciót, de ezt megtehettem a Cantor-Bernstein-Schröder-tétel miatt, ami kimondja, hogy A~B, ha létezik mindkett l injektív leképezés a
másikba, vagyis ha A
B , és A
B , akkor A
B.
33
Az így kapott függvény folytonos, mert a 0;1 \C halmazon szigorúan monoton n , és minden olyan 0;1 -beli racionális számot felvesz, melynek nevez je a kett valamely hatványa. Az ilyen alakú számok azonban s
ek a 0;1 -ben, vagyis minden 0;1 -beli
szám tetsz leges pontossággal közelíthet velük. 12 Az ördögi lépcs az a ponthalmaz, melyet az így kapott l függvény grafikonja, az x tengely és az y=1 egyenlet egyenes határol. Azért ördögi, mert balról jobbra feljuthatunk rajta úgy, hogy 0 összhosszúságú részen megyünk felfelé, és sehol sem ugrunk, hiszen l folytonos.
5. ábra Még nagyobb paradoxonba ütközünk, ha l-et út-id grafikonnak fogjuk föl. Egy test (például egy autó) 1 km utat úgy tesz meg 1 óra alatt, hogy egy órán keresztül áll, és egyszer sem teleportál, hiszen l-en nincs szakadás.
9. Az átlós módszer Cantor az átlós módszert el ször arra használta, hogy megmutassa, a valós számok többen vannak, mint a természetesek, vagyis: 9.1. Tétel: R
N.
Bizonyítás: Tegyük fel, hogy R elemeit sorba tudjuk rendezni. Jelölje xi
12
ni , ai1a i2 ai3
10
a sorozat i-edik tagját, ha i N, aij
0;1;2;3;4;5;6;7;8;9 . Legyen
Érdemes elgondolkodni rajta, mi az összefüggés a 8.6-ban definiált f(x) és az l(x) között.
34
x:
0, b1b2 b3
10
, ahol bi
5 ha ai
5 , és bi
6 , ha ai
5 minden i N-re. Az így
definiált x szám alakja különbözik mindegyik xi alakjától, és mivel nincs benne sem egymást követ végtelen sok kilences, sem egymást követ végtelen sok nulla, nem csak alaki a különbség. Akkor viszont ellentmondásra jutottunk, mert találtunk egy a sorban N.
nem szerepl valós számot. Így R elemei nem rendezhet ek sorba, tehát R
Ám e módszer többre is hivatott, segítségével lehet bebizonyítani, hogy minden számosságnál van nagyobb számosság. 9.2. Tétel: Minden X halmaz esetén P X
X , mert az f: X
Bizonyítás: Egyrészt P X
x
X :x
g x
halmazt! Ekkor A
x X-re g bijektivitása miatt. Ha x Ha viszont x
A , akkor meg x
létezik, és ezért P X
P X , f x
X , mert tegyük fel, hogy létezik egy g: X
injektív. Másrészt P X Tekintsük az A
X .
A
P X , és így A
x
leképezés
P X bijekció. g x valamely
g x , akkor A definíciója miatt x
A
g x .
A -t követelne a definíció. Ez ellentmondás, tehát g nem
X . Akkor pedig csak P X
X teljesülhet.
10. Antinómiák a halmazelméletben A matematika minden ága bizonyos tulajdonságú halmazokkal foglalkozik. Talán ezért rázta meg az egész matematikát az a néhány
felületesen szemlélve ártalmatlannak
ellentmondás, mely a 19. század végén és a 20. század elején bukkant fel. 10.1. Az összes halmaz halmaza Erre az ellentmondásra maga Cantor, a halmazelmélet megalkotója, hívta fel a figyelmet. Legyen
az összes halmaz halmaza. Ekkor, mivel
elemként tartalmaz, minden részhalmaza egyben eleme is, így P módon
-ba képezi, ebb l következ en P
minden halmazt -t az identitás injektív
. Ez pedig ellentmond annak a már
bizonyított tételnek, hogy bármely halmaz számossága kisebb, mint hatványhalmazának számossága.
35
10.2. A Russel-antinómia Russel észrevette 1903-ban, hogy a
P X
X
állítás bizonyítását X= -ra
alkalmazva még látványosabb ellentmondásra jutunk. Nevezzünk egy halmazt tartalmazkodónak, ha tartalmazza önmagát. Tekintsük az A
x:x
x halmazt, a nem
tartalmazkodó halmazok halmazát, és kérdezzük meg, tartalmazkodó-e A? Ha igen, akkor a definíció értelmében nem tartalmazhatja, ha pedig nem, akkor szintén a definíciója miatt tartalmaznia kell önmagát. Ez pedig ellentmondás. 10.2.1. A Russel-antinómia népszer változatai A falu borbélyának paradoxonja: A falu borbélya minden férfit megborotvál a faluban, aki nem maga borotválkozik, és senki olyat nem, aki maga borotválkozik. vajon borotválkozik-e? Ha borotválkozik, akkor olyat borotvál, aki maga borotválkozik, ami ellentmond a feltételeknek, ha pedig nem, akkor egy olyan embert (önmagát) nem borotvál meg, aki nem maga borotválkozik, ami újra ellentmondás. A Gonseth-paradoxon: A könyvtárigazgató megparancsolja alkalmazottjának, készítse el az összes, a könyvtárukban szerepl , önmagát nem tartalmazó bibliográfia bibliográfiáját. Az így elkészül
címtár-jegyzékbe a szerz
beleírja-e magát az új
bibliográfiát? A heterologikus melléknév problémája (Grelling-paradoxon): Nevezzünk egy magyar nyelvben használatos melléknevet autologikusnak, ha rendelkezik azzal a tulajdonsággal, amit kifejez, heterologikusnak, ha nem. Heterologikus-e a „heterologikus” melléknév? 10.3. Az összes számosságok halmazának antinómiája Legyen S az összes számosság halmaza. Ekkor S Ai
A:
számosságok.
i
Ai .
Így
minden
i
:i
i-re
, ahol I indexhalmaz, Ai
A,
ezért
pedig
i
i
Ai
A
P A
. De mivel
számosság,
S , azaz
i
valamely i-re. Ez
viszont ellentmondás. 10. 4. A gyökértelen halmazok halmazának antinómiája Nevezzünk egy X halmazt gyökeresnek, ha léteznek xi , i N halmazok úgy, hogy minden i-re xi
1
xi , és X
x0 , és gyökértelennek különben. Legyen Y a gyökértelen
halmazok halmaza. Vajon Y Y igaz? Ha Y Y, akkor minden xi -t Y-nak választva, mivel Y
Y
Y , Y gyökeresnek bizonyul. De akkor Y definíciójával kerülünk
36
ellentmondásba, mert tartalmaz egy gyökeres halmazt, nevezetesen önmagát. Ha pedig Y Y, akkor Y definíciója szerint Y gyökeres, vagyis léteznek x0 , x1 , x 2 , hogy
x2
x1
x0
halmazok úgy,
Y , ami pedig újra csak ellentmond a definíciónak, mert Y
tartalmazza az x1 gyökeres halmazt. 10.5. K nig Gyula paradoxonja Hány valós számot lehet definiálni magyar nyelv , véges hosszúságú szöveggel? Mivel jelkészletünk véges, legfeljebb megszámlálható sok magyar nyelv
mondat
létezik13. Ennek elenyész hányada definiál valós számot, tehát ilyen szám is legfeljebb megszámlálható sok van. Rendezzük hosszúságúakat xi
ni , ai1a i2 ai3
pedig 10
ket sorba például hosszúság szerint, az azonos
ábécésorrendbe
állítva.
Legyen továbbá
minden i N-re
, és erre a sorra alkalmazva az átlós módszert, ahogy azt a 9.1-es tétel
bizonyításakor tettük, kapunk egy olyan x számot, melyet éppen most definiáltunk véges hosszúságú magyar nyelv szöveggel, mégsem szerepel a listánkon. 10.6. A Berry-Richard-paradoxon A Természetes számok bármely részhalmazának van legkisebb eleme. Vannak olyan természetes számok, melyek definiálásához nem elég tizenkilenc, a Magyar Értelmez Kéziszótárban szerepl , magyar szó. Tehát kimondhatunk egy definíciót: A legkisebb természetes szám, amely nem definiálható tizenkilencnél kevesebb, a Magyar Értelmez Kéziszótárban szerepl , esetleg ragozott, magyar szóval. Ez a definíció kijelöl egy természetes számot, minden szava szerepel a Magyar Értelmez Kéziszótárban, de jaj, csak tizennyolc szóból áll! 10.7. A hiperjáték-paradoxon Anna és Béla régóta barátok, sok véges (véges sok lépésben véget ér ), diszkrét matematikai játékot játszottak már. Egy hétvégén elhatározzák, hogy minden eddiginél izgalmasabb játékot találnak ki, így születik a hiperjáték, melynek szabálya a következ : A kezd
játékos megnevez egy véges, diszkrét matematikai játékot, majd a második
játékos megteszi az els lépést a megnevezett játékban, és ezután végigjátsszák ezt a játékot. Az így kialakult játék egyesíti magában az összes eddig játszott játék szépségeit, 13
Bizonyítás: Mondjuk, hogy legfeljebb 100 jelet használunk egy magyar nyelv szövegben beleértve a bet ket és a többi írásjelet. Feleltessünk meg minden bet nek egy-egy 0 és 99 közti természetes számot. A nullát például a kérd jelnek, ami biztosan nem állhat mondat elején. Ezután pedig a szövegnek azt a természetes számot, amelyet a jeleknek megfelel számok egymás után írásával kapunk, ha a százas számrendszerben olvassuk össze. Ezáltal egy injektív leképezést kapunk a magyar nyelven írt véges szövegek halmazából a természetes számok halmazába, amib l állításunk következik.
37
hiszen bármelyik lehet a választott. A kérdés az, véges játék-e a hiperjáték? Nyilván véges, hiszen egy másik véges játéknál egyetlen lépéssel hosszabb csak. Ha azonban véges, akkor a kezd
játékos megnevezheti magát a hiperjátékot is. Akkor viszont
kialakulhat a következ végtelen játszma is: A:
Hiperjáték!
B:
Hiperjáték!
A:
Hiperjáték!
Ez pedig ellentmond a hiperjáték végességének. 10.7.1. A hiperjáték-paradoxon egy gráfelméleti átfogalmazása a véges gyökeres fák paradoxonja. Egy gráfot fának nevezünk, ha bármely két pontja között egyetlen út (egymáshoz csatlakozó különböz élek sorozata) halad. Gyökeres a fa, ha ki van jelölve egy pontja (gyökérpont). Véges a fa, ha nincs benne végtelen út. Tekintsük az összes véges gyökeres fákat, és egy további P pontot. Ezek egyesítését egészítsük ki a P-b l minden egyes gyökérhez húzott élekkel, és jelöljük ki a P pontot. Véges-e az így kapott gyökeres fa?
11. A halmazelméleti antinómiák feloldása Több mentési kísérlet is született, ezek egyike az intuícionistáké.
k a végtelen
halmazokat nem tekintik lezárt egésznek, csak potenciálisan végtelennek, mely állandóan keletkezik. Egy halmazt csak akkor mondanak létez nek, ha nemcsak neve van, hanem véges sok, vagy legfeljebb N lépésben megkonstruálható. Ezáltal, mivel R kontinuum számosságú, számukra nem létezik az összes valós szám halmaza mint lezárt egész, csak mint folyamatosan keletkez
összesség. Így sok
módszerr l és szép matematikai eredményr l lemondanak, mert azok nem konstruktívak. Egy másik lehet ség
az egyetlen, mely ma is széles körben elfogadott
axiomatizálás. Hilbert nevéhez f
az
dik ez az irányzat, eredeti nevén a formalizmus.
Lényegében itt arról van szó, hogy nem lehet vitatkozni például a medvér l akkor, ha az egyik félnek gyerekkorában viccb l valaki azt mondta, a nyúl egyik szinonimája a medve, ezt elhitte, és attól fogva, ha
medvét mondott, nyúlra gondolt.
Precízen le kell szögezni, mit értünk az egyes fogalmak alatt és mit nem.
38
Néhány alapfogalmat, melyet már nem tudunk egyszer bb fogalmakkal definiálni, kiválasztunk, majd mondunk róluk néhány olyan állítást, melyeket mindenki számára nyilvánvalóaknak gondolunk. Ezek lesznek az axiómák, melyeket igaznak fogadunk el. Ezután pedig azt mondjuk, bárki bármit gondolhat az alapfogalmakról, ami összeegyeztethet az axiómákkal. Azonban ezt az összeegyeztethet séget is kínosan precízen kell megfogalmaznunk. Véges eljárást kell adnunk arra, hogy az axiómákat igaznak elfogadva hogyan láthatjuk be további állítások igazságát. Végül akkor mondhatjuk sikeresnek az axiomatizálást, ha az általunk felállított rendszerben a meghatározott következtetési szabályok alapján soha nem juthatunk ellentmondásra, amin most azt értem, nem származtathatunk az axiómákból egyszerre egy állítást és annak tagadását is14. Úgy is mondhatjuk, ha a matematika egy területét, például a természetes számokat axiomatizáltuk, akkor minden olyan struktúrát, ami teljesíti a természetes számok axiómáit, a természetes számok modelljének15 nevezünk, és innent l kezdve teljesen mindegy, melyik modelljére gondolunk egy vita során. Az fontos csak, hogy ha rájövünk a modellben egy érdekes összefüggésre, arról csak akkor akarjunk másokat meggy zni, ha az az axiómákból az említett véges módszerekkel tényleg levezethet , és nem a modellünk egyedi sajátossága. Hiszen minden az „ideális” természetes számokra bizonyítható állítás bizonyítható a modellünkben is, de nem feltétlenül minden modellbéli állítás bizonyítható az axiomatizált természetes számokra. 16 Álljon itt egy példa! Tegyük fel, hogy egy szigeten találkozunk egy Igazmondó Zénó nev emberrel, aki a következ ket állítja: B1: Én bennszülött vagyok. B2: Minden bennszülött tanít egy bennszülöttet. B3: Engem senki sem tanít. B4: Nincs olyan bennszülött, akit ketten is tanítanának. A1: Bármely bennszülött, bármely t le nem feltétlenül különböz
bennszülött
segítségével rendszeresen közös ajándékot készít egy bennszülöttnek. Én egy tetsz leges R bennszülött segítségével magának R-nek készítek ajándékot.
14
Még azt is meg szokták követelni, hogy az axiómák függetlenek legyenek, vagyis egyiknek se lehessen még egy részét se bebizonyítani a többib l. 15 Az volna az igazi cél, hogy az axiómák az axiomatizált struktúra minden lényeges tulajdonságát megragadják, azaz a modellek csak lényegtelen tulajdonságokban különbözhessenek. Ez azonban nem mindig sikerül, példa erre a Skolem-Löwenheim-paradoxon, amelyre még visszatérek. 16 Ez a problémakör Gödel híres, a nem teljességgel kapcsolatos tételével függ össze.
39
A2: Ha X és Y két nem feltétlenül különböz bennszülött, akkor X az Y tanítványa segítségével annak a bennszülöttnek készít ajándékot, aki tanítványa annak, akit X Y segítségével ajándékoz meg. T1: Bármely bennszülött, bármely t le nem feltétlenül különböz
bennszülött
kíséretében eljár teázni egy bennszülötthöz. Én egy tetsz leges R bennszülött kíséretében éppen önmagamhoz járok teázni. T2: Ha X és Y két nem feltétlenül különböz bennszülött, akkor X az Y tanítványa kíséretében ahhoz a bennszülötthöz jár teázni, akinek ajándékot készít X segítségével az, akihez X Y kíséretében jár teázni. K:
Ha (X) egy els rend nyelven megfogalmazott formula (állítás), melyben X
szabad változó, és amely megajándékozásról, teázásról, egyes bennszülöttekr l és azok tanítványairól szól, akkor, ha (X) igaz X=Zénóra és minden X esetén X tanítványára is igaz, akkor (X) igaz minden X bennszülöttre. Ekkor mondhatjuk, hogy a sziget a természetes számok modellje. Ennek szemléltetésére álljon itt annak bizonyítása, hogy az ajándékozás asszociatív. Bizonyítás: Jelölje Zénót Z, XaY az X által Y segítségével megajándékozott bennszülöttet, t(X) pedig az X tanítványát. Ekkor minden K-ra, M-re teljesül, hogy
KaM aZ
KaM
Ka MaZ az A1 axióma miatt. Tegyük fel hogy valamely N-re igaz, A2
KaM aN
hogy
Ka MaN . Tekintsük a
KaM at N
IND
t KaM aN
A2
egyenl séget, melyet folytathatunk t Ka MaN („IND”
jelöli
K M KaM aN
az
indukciós
feltevés
t Ka MaN
A2
Kat MaN
Ka Mat N
alkalmazását.)
Mivel
leírásával! pedig
a
Ka MaN formula a K axiómában meghatározott formájú állítás az
X=N szabad változóval, teljesül a
N K M KaM aN
Ka MaN formulával leírható
asszociativitás a bennszülöttek halmazán.
Valóban, e bizonyítás arra volt jó, hogy szemléltesse, minden ugyanúgy m ködik a bennszülöttekkel, ahogy a természetes számokkal. Ugyanígy bizonyíthatjuk a természetes számok összeadásának asszociativitását, ha a megfelel
fogalmakat következetesen
kicseréljük a bizonyításban. Minden a természetes számokra megfogalmazott állítás igaz lesz a bennszülöttek halmazára, ha maguk az axiómák igaz állítássá interpretálódnak, csak össze kell állítanunk egy alkalmas szótárt: a sziget lakói
a természetes számok
40
0
Zénó
X rákövetkez je
X tanítványa
X+Y
az a bennszülött, akinek X Y segítségével készít ajándékot
XY
az a bennszülött, akihez X Y kíséretében jár teázni
Ha ezt megtettük, a természetes számok helyett nyugodtan gondolhatunk a bennszülöttekre.17 Ahhoz, hogy ez az ízelít az axiomatikus felépítésr l teljes legyen, még definiálom az els rend
formula fogalmát. Pontosan meg kell határozni, milyen nyelven fogunk
állításokat megfogalmazni. 11.1. Els rend nyelvek Tegyük fel, hogy vannak jeleink, melyek a páronként diszjunkt konstansjelek K, változójelek V, függvényjelek F és relációjelek L halmazába sorolhatóak, továbbá egy „#”: L
F
N függvényünk, mely minden relációjelr l és függvényjelr l megmondja, ; ; ;
hány változós. Még néhány logikai jellel: vessz és a zárójel
;
; ;
és segédjelekkel
mint a
is rendelkezünk.
11.1.1. Definíció: i.)
Minden változójel és konstansjel kifejezés.
ii.)
Ha f n változós függvényjel, k1 ,
, k n kifejezések, akkor f k1 ,
, kn
is
kifejezés. iii.) Minden kifejezés el áll a i.) és ii.) véges sokszori alkalmazásával. 11.1.2. Definíció: i.)
Ha k1 és k 2 kifejezések, akkor k1
ii.)
Els rend
#(r)=n), és k1 , iii.) Ha következ k is:
formula az r k1 ,
k 2 els rend formula.
, k n , ha r
L n változós relációjel (azaz
, k n mindegyike kifejezés. 1
és
2
,
1
1
els rend formulák, és x változójel, akkor els rend formulák a 2
,
1
2
,
1
2
17
,
1
2
, x
1
,
x
1
.
Igazán nyugodtak akkor lehetnénk, ha a K axiómát Zénó így mondta volna ki: A bennszülöttek bármely részhalmazára igaz, hogy ha én benne vagyok, és minden bennszülöttel együtt annak tanítványa is, akkor ez a részhalmaz az összes bennszülöttek halmaza. Ez volna az a másodrend nyelven megfogalmazott állítás, mely a többi axiómával együtt egyértelm en írná le a természetes számokat.
41
iv.) Minden formula el áll a fenti három képzési szabály véges sokszor történ alkalmazásával. A
jeleket kvantoroknak hívjuk, melyek a x
és a
1
x
és a
1
formulákban az
x változót lekötik. Ha egy változó egy formulában nincs lekötve, azt mondjuk, hogy ott szabadon fordul el . Még arról kell néhány szót szólnunk, mi az interpretálás. 11.1.3. Definíció: Legyen U egy nem üres halmaz, I (interpretáció) pedig egy K
L -en értelmezett leképezés! Az M
F
U , I rendezett pár struktúra, ha I minden
n változós relációjelnek egy U-beli n változós relációt, minden m változós függvényjelnek egy U m
U leképezést, minden konstansjelnek U egy elemét felelteti meg.
11.1.4. Definíció: Az e: V
leképezést értékelésnek nevezzük, melyet
U
kiterjeszthetünk minden k kifejezésre a következ képpen: i.)
k
V -re e k már értelmes.
ii.)
k
K -ra e k : I k
iii.) Ha k
f k1 ,
, k n , akkor e k
I f e k1 ,
, e kn .
11.1.5. Formulák igazságértékeinek definíciója: Az M
U , I struktúrában az e
értékelés mellett pontosan akkor igaz i.)
a k1
ii.)
az r k1 ,
iii.) a 2
és
igaz; a 2
k 2 , ha az e k1 és az e k 2 értékek megegyeznek.
1
, k n , ha az e k1 ,
, ha
1
2
is hamis; a
1
, ha
x
1
nem igaz; a 1
elemek az I r relációban állnak.
, e kn 1
hamis vagy
2
2
, ha
és
1
igaz; a
1
is igaz; a
2
2
, ha
1
és
1
2
2
, ha
1
vagy
is igaz, vagy
1
ha az e értékelésben megváltoztatva x értékét találunk olyan e’
értékelést, mely mellett M-ben igaz lesz ben x értékét, a kapott e’ mellett M-ben
1
1
;a
x
1
, ha akárhogyan is változtatjuk meg e-
igaz marad.
11.1.6. Definíció: Az M struktúra modellje a
els rend
formulákból álló
halmaznak, ha bármely e értékelés esetén minden -beli formula igaz lesz M-ben az e értékelés mellett. 11.2. A halmazelmélet Zermelo-Fraenkel-féle axiómái Ebben a tárgyalásban minden halmaz eleme is halmaz, nincsenek más objektumok, csak halmazok. Alapfogalmak: halmaz, „ ” kétváltozós reláció
42
H1 Az egyenl ség axiómája: Ha x-nek és y-nak ugyanazok az elemei, akkor x
y.
H2 Pár-axióma: Bármely x és y halmazhoz létezik olyan halmaz, melynek x és y eleme, és más eleme nincs. 11.2.1. Definíció: A
t els rend formulát, amiben pontosan egy darab szabadon
el forduló változó van, a t, tulajdonságnak nevezzük. H3 Részhalmaz-axióma: Bármely x halmazhoz és T az x halmaz T tulajdonságú elemeinek y halmaza: y
t
t tulajdonsághoz létezik
x:
H4 Az unió axiómája: Bármely x-hez létezik az y
t .
x halmaz, amely azokból a
halmazokból áll, melyek x valamely elemének elemei. 11.2.2. Definíció: x részhalmaza y-nak, ha x-re teljesül a következ
t t
formula:
x
t
els rend
y .
H5 A hatványhalmaz axiómája: Bármely x-hez létezik az y
Px
halmaz,
amelynek elemei pontosan az x részhalmazai. H6 Az üres halmaz axiómája: Létezik olyan halmaz, melynek nincs eleme. 11.2.3. Definíció: x induktív, ha teljesül rá az (
x)
t t
x
t
t
x
els rend formula. H7 A végtelen halmaz axiómája: Létezik induktív halmaz. 11.2.4. Definíció: A a
x y1 y 2
x, y1
x, y els rend , két szabad változós formulát, melyre teljesül x, y 2
jelöljük és megállapodás szerint F x
y1
y2
formula, függvénynek nevezzük, F -vel
y akkor és csak akkor, ha
H8 A pótlás axiómája: Ha x halmaz és F F x
F t :t
függvény, akkor létezik az
x halmaz.
H9 A regularitási axióma: Bármely x-hez létezik olyan u C
x, y igaz.
x , amelyre u
.
A kiválasztási axióma: Bármely olyan S halmazhoz, amelynek elemei nem üres
halmazok, van olyan S-en értelmezett F függvény, melyre bármely x
F x
x
S esetén
x. Ezekkel az axiómákkal pontos konstrukciós szabályokat adtunk arra, hogy már
meglév halmazokból hogyan alkothatunk újabbakat. Csak a könnyebb érthet ség miatt fogalmaztam metanyelven az axiómákat, mindegyik leírható a halmazelmélet els rend nyelvén. Ez a nyelv egyetlen kétváltozós relációjelet tartalmaz, melynek jele: „ ”, és a
43
x; y ” helyett „ x
könnyebb olvashatóság érdekében az „
y ”-t írunk. Például az els
két axióma így szól: H1
x y
t t
H2
x y z x
x
t
z
y
y
x
z
t t
y z
t
x
t
y
A harmadik és a nyolcadik axióma kivétel, úgynevezett axiómaséma, hiszen metanyelven csak egy mondat, de els rend nyelvben nem vonatkozhatnak kvantorok formulákra, így nem írhatjuk például H3-at „ x
t y t t
y
t
x
t
”-
nek, ehelyett kénytelenek vagyunk új axiómát írni minden elképzelhet , szabályos, egy szabad változós
i
t formulával, melyek szerencsére megszámlálható sokan vannak. H8-
hoz pedig fel kell sorolni az összes lehetséges
j
u, t
függvényt. Így keletkeznek a
következ formulák: H3i
x y t t
y
t
H8j
x y t t
y
u u
x
i
t
x
j
u, t
A természetes számoknak készíthet egy modellje a halmazelméletben H7 alapján a következ módon: 0 1
{ }
2
{ ;{ }}
3
{ ;{ };{ ;{ }}}
x
x rákövetkez je
x
A m veletek pedig rekurzívan definiálhatóak. A természetes számok ezen felépítésében az a különös összefüggés fedezhet fel, hogy például 3
0;1;2 és hasonlóan n 1
0;1;
;n .
A harmadik axióma biztosítja, hogy ne lehessen definiálni, így például a antinómia A
x:x
x
x
x:
x
formájú halmazokat
x formula segítségével nem juthatunk a Russel-
x halmazához. Ennek viszont az az ára, hogy egy olyan egyszer
velet, mint az unióképzés, bonyolultabb definíciót igényel, mert két már megkonstruált halmaz uniója b vebb is lehet a kiindulási halmazoknál. Legyen A1 és A2 két már megalkotott halmaz! Ekkor H2 miatt létezik az x
A1
A2 :
x halmazt.
44
A1 ; A2 . Most már definiálhatjuk az
A regularitási axióma biztosítja, hogy minden x halmaznak legyen olyan u eleme, mely az „ ” relációra nézve minimális. Ebb l az is következik, hogy nem létezik olyan Y
x0 halmaz, melyre
x3
x2
x1
x0
Y.
Bizonyítás: H7 miatt megkonstruálható a természetes számok halmaza. Tegyük fel hogy létezik a
x3
x2
x1
x0
Y
lánc. Mivel elemei megindexelhet ek a
természetes számokkal, van olyan F függvény, melynél az xi -k mindegyike képe egy természetes számnak. Ekkor az x :
x0 ; x1 ; x 2 ; x3 ;
kifolyólag pedig létezik olyan n, amelyre x n
x
halmaz H8 miatt létezik, H9-b l . De x n
1
eleme az x n
x -nek, ez
pedig ellentmondás.
Ennek speciális eseteként nem létezik olyan x, melyre x x, mert akkor
x
x
x
x egy tiltott sorozat lenne. Ez azt mutatja, hogy minden halmaz
gyökértelen, és egyetlen halmaz sem tartalmazkodó. Tehát a gyökértelen halmazok halmazának, és a nem tartalmazkodó halmazok halmazának antinómiája ekvivalens az összes halmazok halmazának antinómiájával. Ha figyelmesen végigvizsgáljuk az axiómákat, kiderül, hogy az összes halmazok halmaza nem konstruálható meg ezen elméleten belül, egyrészt azért, mert „túl nagy” halmazokat nem enged felépíteni az elmélet, másrészt a regularitási axióma kizárja az összes halmaz halmazának létezését, mert annak elemként tartalmaznia kéne önmagát. Az összes számosság halmaza is túl nagy, az axiómák által kijelölt úton nem alkotható meg. A borbély-paradoxon egy ötletes feloldása, hogy a borbély n , aki sem nem borotválkozik, sem nem borotválják, mert nem n szakálla. Ha még azt is kikötöttük volna, hogy olyan férfi, akinek n szakálla, ellentmondást kapnánk, de ez csak annyit jelentene, hogy megvalósíthatatlan az így kialakult feltételrendszer. A Gonseth-paradoxon és a melléknév-paradoxon feloldása nagyon hasonló. A könyvtárigazgató lehetetlent kért alkalmazottjától, illetve a melléknevek fenti osztályozása nem lehetséges már csak azért sem, mert vannak melléknevek, melyekr l nem dönthet el egyértelm en, hogy melyik osztályba tartozik. Egyéni ízlést l függ, ki hova sorolja például a „méltóságteljes” melléknevet. A K nig-, a Berry-Richard- és a hiperjáték-paradoxonban az ellentmondás oka nyelvi természet , a nyelv alkotó és önreflektáló képességének egymás utáni megjelenéséb l fakad. Amikor definiálunk egy fogalmat, a definíció pillanatában még
45
nem gondoljuk meg, hogy a definíció által használt kategóriákba kés bb maga az újonnan született fogalom is besorolható lesz, ezáltal pedig circulus vitiosus léphet fel. Ez történik a hiperjáték paradoxonban is, ahol hiperjátékot is megengedjük els
miután besoroltuk a véges játékok közé
magát a
lépésben választott véges játéknak. A másik két
paradoxon számdefinícióinál is az a probléma, hogy amikor a definíció által megszületik az új szám, megváltozik a definíció értelme, hiszen most már az új számra is vonatkozik. Ez a folyamat talán a f nixmadár születéséhez hasonlítható. Ahhoz hogy az új f nixmadár megszülessen a régi által tojt tojásból, a réginek el kell égnie. (E mitológiai történetben egyesek szerint a t z különös újratermel désének lehetünk tanúi.) Az el
probléma
tükrözi a nyelv kontextusfügg ségét is. Ugyanaz a mondat más szövegben mást jelenthet. t ugyanaz a mondat más id pontban is mást jelenthet. Ez történik akkor, amikor a nig-féle definíció által els olvasáskor meghatározott szám második olvasáskor már a véges sok szóval definiált számok közé tartozik, és így már egy másik számot határoz meg a definíció. (Hétköznapibb példa arra, hogy a kijelentések lehetnek id függ k, az „Esik az es .” mondat.) Els rend
nyelvekben azonban nem lehet ilyen típusú állításokat
megfogalmazni, így ezeket a paradoxonokat sikerül kikerülni H3 segítségével.
12. Egy modellelméleti paradoxon Azonban így sem kerülünk el minden meglep
eredményt, paradoxonok így is
fölmerülnek. Példa erre a Skolem-Löwenheim-paradoxonok felszálló változata, melynek tárgyalásához néhány el készületre lesz szükségünk. 12.1. Definíció: Egy els rend
formulahalmaz ellentmondásmentes, ha nem
vezethet le bel le egyszerre egy formula és annak tagadása is. 12.2.
Tétel:
Els rend
nyelvekben
egy
formulahalmaz
pontosan
akkor
ellentmondásmentes, ha van modellje. „Bizonyítás”: Mivel a bizonyítás hosszú, és olyan fogalmakat is használ, melyeket én nem definiáltam, csak utalok rá, hogy megtalálható [13.]-ban. Nem beszéltem arról sem, pontosan mit jelent a levezethet ség. Lehet definiálni, mégis inkább az olvasó intuitív levezethet ség-fogalmára építek, mert egyetlen paradoxon tárgyalásához nem akartam újabb definíciókat kimondani. A [11.] könyv 19-22. oldalán is található egy bizonyítás rögtön a következ tételre, mely nem használja a levezethet ség fogalmát, helyette ultraszorzattal dolgozik, és nála az els rend általános, mint ahogy azt mi meghatároztuk. 46
nyelvek fogalma nem olyan
12.3. Tétel (Gödel kompaktsági tétele): Ha egy
els rend formulahalmaz minden
véges részhalmazának van modellje, akkor magának -nak is van. Bizonyítás: Tegyük fel, hogy részhalmazának van. Az el
-nak nincs modellje, bár minden véges
tétel alapján
ellentmondásos, ami azt jelenti, hogy
egyszerre levezethet bel le egy formula és annak tagadása is. A levezetésben azonban csak véges sok
-béli formulát használhattunk, ezek
ellentmondásos részhalmaza. Tehát
halmaza
-nak véges,
-nak nincs modellje, ez pedig ellentmond a
feltevésünknek.
12.4. Tétel (Skolem-Löwenheim-paradoxon): Ha
-nak van egy végtelen M
modellje akkor van M-nél nagyobb számosságú modellje is. Bizonyítás: B vítsük a nyelvet a c x : x X
M .
-t b vítsük a c x
c y
X
különböz konstansjelekkel, ahol
formulák T halmazával, ahol x
y és x, y X
minden elemén végigfut. Tudjuk úgy interpretálni az új konstansjeleket M-ben, hogy minden véges részhalmaza
T-nek igaz legyen M-ben. Nevezetesen, mivel M végtelen,
van elég sok eleme ahhoz, hogy akárhány véges sok c(x)-nek különböz M-beli elemeket feleltessek meg. Tehát M modellje a a
T minden véges részhalmazának, így léteznie kell
T modelljének is, ami egyszersmind modellje -nak is, számossága pedig legalább
X .
Speciálisan az els rend Peanó-axiómáknak is van nem megszámlálható modellje. Ez egy C típusú paradoxon. Megjegyzés: Ha lecseréljük a teljes indukció axiómáját (K) a másodrend teljes indukciós axiómára (17. lábjegyzet), már bizonyítható, hogy az így kapott axiómák bármely két modellje izomorf egymással. Másodrend
nyelvekben nem is lépnek föl
Skolem-Löwenheim-paradoxonok, viszont megfogalmazhatóak lesznek olyan állítások, melyekr l nem dönthet el, igazak-e vagy hamisak.
47
13. Darabolások, mérhet ség Az axiomatizálás sem tünteti azonban el a meglep konklúziókat, vagyis a C típusú paradoxonokat, amikre legjobb példák a huszadik század darabolási tételei. 13.1. Definíció: Legyen Y
Y1
i
1,2,
Y2
X ,Y
Rd
és
X
X1
X2
X n , valamint
Yn X-nek illetve Y-nak diszjunkt felbontásai úgy, hogy X i
Yi minden
, n -re, ahol „ ” jelöli az egybevágósági relációt. Ekkor azt mondjuk, hogy X és
Y n részre bontva egymásba darabolhatóak. Jele X hangsúlyozni a részek számát, akkor X
n
Y , vagy ha nem akarjuk
Y.
13.2. Tétel (kördarabolási paradoxon): Minden körvonal átdarabolható egy vele azonos sugarú körvonalba, melynek egy pontja hiányzik. Bizonyítás: Legyen a kör középpontja O, kerületének tetsz leges pontja P0 , pedig tetsz leges irracionális szám. Jelölje Pi az O körül i ahol i
i
i
N . Az i
j
j
A:
Pi : i
történ
B
Z fennállna, azaz 360k 360k i j
viszont
sem 2
i
j
Pj csak akkor lehetne, ha
. Ez teljesül, ha i
A
kerül,
B
A
A
de
Pi : i
minden
1,2,3, pozitív
j és k
irracionalitásának.
ellentmondana
N , B pedig a körvonal maradék része. Legyen
elforgatás! Ekkor
semmi
A
Pi megfeleltetés bijektív, ugyanis Pi
360k , k esetén
fokkal elforgatott P0 pontot,
az O körüli
0.
Legyen fokkal
, hiszen a forgatáskor P0 helyébe i-re
Pi
helyébe
Pi 1 .
Ekkor
B \ P0 .
Ez a paradoxon (egy pont eltüntetése) lényegében azon alapszik, hogy N leképezhet egy valódi részhalmazára bijektív, távolságtartó módon. Van azonban egy ennél sokkal kézenfekv bb „darabolási” paradoxon, amellyel mindannyian találkoztunk már, ha át is siklottunk fölötte. Nevezetesen bármely a, valódi részhalmazába például b,
-be, ahol b
félegyenes elmozgatható egy
a , ha eltoljuk a b a vektorral. Itt
nem egy pont, hanem egy egész intervallum t nik el. Sierpinski és Mazurkiewicz találtak
48
a síkon olyan halmazt, mely megduplázható, és akár csak a félegyenesnél, itt sem kell szigorú értelemben darabolnunk, elég az egész halmazt mozgatni: 13.3. Definíció: Ha A
, és
B
A
B
B , azt mondjuk, hogy A
A
megduplázható. 13.4. Tétel: A síkban létezik megduplázható halmaz. Bizonyítás: Tekintsük a komplex számsíkot, és rögzítsünk egy z
cos
an z n
N , a0
transzcendens számot! A : B:
u: u
an z n
diszjunktak18.
an 1 z n
u: u 1
an 1z n
1
a1 z
0 , és
N . Ekkor A és B z transzcendenciája miatt
a1 z , ai
1;0 vektorral való eltolás,
legyen a
a0 , ai
i sin
A
szög elforgatás! Így már látható, hogy
B
pedig az origó körüli
A
B , felhasználva azt a tényt,
hogy egy c komplex számnak megfelel vektort úgy forgathatunk el
szöggel, hogy
c-t osztjuk z-vel.
Most érkeztünk a legmeglep bb darabolási paradoxonhoz, melyet Banach és Tarski találtak 1924-ben felhasználva Hausdorff egy tíz évvel korábbi eredményét. 13.5. Tétel: A gömb megduplázható. Bizonyítás: A bizonyítást 1.
mivel elég hosszú
hét alpontra bontva végezzük.
Az átdarabolhatóság nyilván tranzitív, hiszen ha A
A
mn
n
B , és B
m
C , akkor
C , ehhez elég meggondolni, hogy az A B-be és B C-be való darabolásakor B-b l
keletkez
darabok metszeteivel egybevágó halmazok jók lesznek az A C-be történ
darabolásához. Rögzítsünk egy gömböt az O középponttal! r1 és r2 legyenek O-n átmen
2.
különböz egyenesek. Nevezzük szónak a a1 1
a2 2
a3 1
a2 n 2
i
i
jelölje a gömb egy ri tengely forgatását, ahol i 1 vagy 2.
transzformációk összes lehetséges kompozícióit, melyek alakja
, ahol ai
Z minden i
1;2;3;
;2n -re, és a1 illetve a 2n kivételével
nem nullák. Az üres szó az identitás. (A szavak bet inek megfelel transzformációkat
megtartva a kialakult szokást
egyes
jobbról balra haladva végezzük.)
Nyilván két szó szorzata ugyancsak szó lesz. 18
an z
Ha n
ugyanis
an 1 z
n 1
nem
volnának
a1 z a 0
bn z
azok, n
bn 1 z
akkor n 1
teljesülne
a
következ
egyenl ség:
b1 z b0 , ahol az ai -k és bi -k nem minden i-
re egyenl ek, hiszen a0 nem nulla, b0 viszont az. Ezt nullára redukálva kapnánk egy nem azonosan nulla polinomot, aminek z gyöke volna, de ez azt jelentené, hogy z algebrai.
49
3.
Lemma (Hausdorff): Léteznek olyan térbeli
1
és
2
forgatások, melyekb l
alkotható egyetlen nemüres szó sem egyenl az identitással. A lemma bizonyítása: Legyenek
és
1
a háromdimenziós derékszög
2
koordinátarendszer z illetve x tengelye körüli arccos
1 szög forgatások. Ekkor az ket 3
reprezentáló mátrixok:
1 3 2 2 3 0
1 1
Szimmetriaokokból elég a 1 1
2 2 3 1 3 0
1 1
0
1
0 és 1
1 2
0 0
-gyel kezd
0 1 3 2 2 3
0 2 2 . 3 1 3
w szavakat vizsgálni (ahol a jobb szélen
áll). Megmutatjuk, hogy az ilyen szavak az 1 0 0
T
mátrixnak megfelel pontot
T
a 3k
egy
b 2 3k
c 3k
alakú pontba viszik, ahol a, b, c egészek és b nem osztható T
hárommal, tehát már az 1 0 0 -nek sem önmaga a képe, így w nem az identitás. A bizonyítást a szó hossza szerinti teljes indukcióval végezzük. (Egy szó hossza az w1 0 0
T
a1
értéke.) Ha w hossza egy, akkor w
a2n
1 1 3
2 2
3k
1
a' b' 2
a2
a3
2
a2 n
1 1 1
2
és így
T
0 . Tegyük fel most, hogy az n hosszúságú w’ szavakra az
állítást beláttuk, továbbá legyen w 1
a1 1
1 1
T
w' vagy w
1 2
w' , ahol w' 1 0 0
T
c ' , w’ hossza n és a’, b’, c’ egészek, b’ pedig nem osztható
hárommal. Ekkor tekintetbe véve, hogy
50
1 3 2 2 3 0
1 w 0 0
1
1 w 0 0
0 1 3 2 2 3
0 0
a' 3k 1 b' 2 0 3k 1 1 c' 3k 1
2 2 3 1 3 0
0
a' 3k 1 b' 2 3k 1 c' 3k 1
0 2 2 3 1 3
a ' 4b' b' 2a' 2 3c'
1 3k
3a ' 1 b' 2c' 3k c ' 4b'
a 1 b 2 3k c
a 1 b 2 3k c
alakú,
illetve
szintén a kívánt alakú,
T
már csak azt kell bizonyítanunk, hogy a w 1 0 0 -ben szerepl b egyik esetben sem osztható hárommal. Ehhez hat esetet kell megkülönböztetni aszerint, hogy w egyenl -e 1
1
1
2
v,
1
1
1
2
1
v,
2
1 1
v,
1 2
1 1
v,
1 1
1 1
v vagy
1
esetleg v az üres szó is lehet. (Nyilván nem kell vizsgálnunk a egyikével egyenl
1
2
2 1 1
v egyikével, ahol 1
1
szavakat, hiszen azok hossza nem n+1.) Az els
felhasználva az el bbieket, b
b' 2c' , ahol c’ osztható 3-mal, vagy b
1
v és a
1
2
2
v
négy esetben, b' 2a ' , ahol a’
osztható 3-mal. Így ha b’ nem volt osztható 3-mal, akkor b sem lesz az. Az ötödik és T
hatodik esethez jelölje a' ' , b' ' és c' ' a v 1 0 0 -ben szerepl , megfelel egészeket. Az ötödik esetben:
b
b' 2a' b' 2 a" 4b"
b' b" 2a" 9b" 2b' 9b" , és ugyanilyen alakot kapunk a
hatodik esetben is:
b
b' 2c ' b' 2 c" 4b"
b' b" 2c" 9b" 2b' 9b" . Tehát ha b’ nem volt osztható 3-mal
akkor b sem lesz az, így állításunk igaz minden n+1 hosszúságú szóra is. Ezzel a bizonyítást be is fejeztük.
4.
Legyenek
w1 w2
1
w2 w2
1
1
és
2
ilyen forgatások. Ha most két szóra w1
, ami csak úgy lehetséges, ha w1 w2
vagyis ha w1 és w2 alakja megegyezik. Jelölje H
x : x
H
halmazt!
Mivel
összesen
1
x
w2 , akkor
az üres szóra egyszer södik le, R3 :
megszámlálható
x
1 esetén
szó
H
képezhet ,
a és
mindegyiknek legfeljebb két fixpontja van, az egység sugarú gömbfelület azon pontjainak halmaza, mely fixpontja valamely szónak, megszámlálható. Jelöljük ezt a halmazt F-fel, a
51
gömbfelület maradék részét pedig S-sel. Értelmezzünk egy relációt S-en: Q, P Q~P (Q elérhet
P-b l), ha van olyan
P
szó, melyre
S esetén
Q . A „~” nyilván
ekvivalenciareláció, mely S pontjait ekvivalenciaosztályokra bontja. Válasszunk ki minden ekvivalenciaosztályból egy-egy reprezentáns pontot, így kapjuk az M halmazt.19 Ha
M
végigfut az összes szón, akkor a
részekre való felbontását adják, mert egyrészt
halmazok S-nek páronként diszjunkt
M
S minden -re, másrészt S minden
pontja beletartozik valamely ekvivalenciaosztályba, és ha P
P
Y , ahol X , Y
X
5.
1
M . Ez azonban ekvivalens a 1
ami M definíciója miatt csak akkor teljesülhet, ha
M X
M , akkor Y egyenl séggel,
az identitás, azaz
.
Osszuk a szavakat a következ négy diszjunkt részhalmazra:
A1 :
a
1
pozitív kitev s hatványára végz
szavak,
A2 :
a
1
negatív kitev s hatványára végz
szavak,
A3 :
a
2
pozitív kitev s hatványára végz
szavak és a
n 2
alakú szavak, ahol n
természetes szám (így az identitás is),
A4 :
a
2
negatív kitev s hatványára végz
szavak kivéve a
n 2
alakú szavakat,
ahol n természetes szám (Végz désen a szó bal szélén álló z illetve x körüli forgatást értem, melyet utoljára végzünk el.) Nyilván
1
A2
A2
A3
A4
és
2
A4
A1
A2
A4 . Legyen H i :
M Ai
minden i 1
H2
1;2;3;4 , vagyis H i jelenti M képét az Ai szavainak alkalmazásakor. Ekkor H2
H3
H 4 és
2
H4
H1
H2
H 4 , ami viszont azt mutatja, hogy
H1
H2
2
H1
H2
H3
H4
S,
H3
H4
2
H1
H2
H3
H4
S,
tehát S megduplázható. 6.
S azonban átdarabolható
S
F -be, F ugyanis megszámlálható, és így
tekinthetünk egy O-n átmen olyan e egyenest, melynek nincs közös pontja F-fel. Azon e tengely
rossz forgatások halmaza is megszámlálható, melyekre
n
F
m
F
különböz n és m esetén nem üres, mert F minden pontjához legfeljebb megszámlálható sok olyan szög létezik, mellyel t elforgatva F egy pontjába jutunk. Ezek uniója pedig 19
Itt használjuk a kiválasztási axiómát.
52
minden F-béli pontra még mindig megszámlálható. Választhatunk tehát egy jó forgatást, melyre Fn :
n
F . Mivel
n
F
m
F
különböz
jó forgatás, Fi
n és m esetén. Legyen ekkor
, ha i
Fj
j. H :
Fi . Ahogy a körvonal i N
1
darabolásakor is csináltuk, forgassuk el helyben hagyva látható, hogy S S
7.
2
S
-gyel H-t. Így
1
H
H
F . S\H pontjait
F , és ily módon felhasználva „1.”-et a teljes
F gömbfelület megduplázható.
Ha most az eddig tárgyalt pontok helyébe mindenütt a pontba húzott sugarat
tekintjük, melyb l elhagyjuk az O középpontot, azt a T testet duplázhatjuk meg, melyet a gömbb l középpontja elhagyásával kapunk. Ez azonban átdarabolható a gömbbe. Ehhez nem kell mást tennünk, mint egy olyan k kört felvenni a gömb belsejében, amely áthalad O-n. Mint azt korábban láttuk, k\ O
k , ami megadja a T megfelel darabolását is a
gömbbe, ha T\k pontjait helyben hagyjuk. Következésképpen minden egységgömb átdarabolható két diszjunkt egységgömb uniójába.
Természetesen
az
egységnyi
sugárnak
nincs
szerepe
a
bizonyításban,
kicserélhetnénk tetsz leges R sugárra. Teljes indukció segítségével pedig belátható, hogy nem csak duplázni, hanem akárhányszorozni is tudunk. Miel tt azonban azt hinnénk, most akkor megnyílt az út el ttünk, mely még a lottó nyereményénél is mérhetetlenül jobban megtömi a pénztárcánkat, nem is kell más hozzá, mint egy éles vágóeszköz meg egy akármilyen kicsi aranygömb, nem árt meggondolnunk, milyen élesnek kell lennie a f részünknek, milyen kacskaringósnak és szétes nek. Nem árt ha az elemi részecskéket is ketté tudja vágni, és szitaszer en bizonyos pontokat el tud választani más pontoktól. Az a tény, hogy ez a darabolás a valóságban nem végezhet paradox voltából, hiszen az egyszer
el, mit sem von le
síkkal két részre osztás sem végezhet
el a
valóságban. t ennek a tételnek van egy általánosítása is, miszerint ha A és B olyan térbeli halmazok, melyek tartalmaznak nem nulla sugarú gömböt (az ilyen halmazokat telt
R n telt, ha tartalmaz nem nulla sugarú n
halmazoknak nevezzük, és általában X
dimenziós gömböt), akkor egymásba darabolhatóak. Az eddigiek alapján ez szinte már meg sem lep minket. Bizonyításához fel kell használni a Cantor-Bernstein-Schröder-tétel egy formáját.
53
Akkor most már nem is érdemes matematikával foglalkozni? Ha ilyen ellentmondások merültek fel már eddig is, milyenek jönnek még? Az igazság az, hogy nincs semmilyen ellentmondás.20 Azért érezzük paradoxnak az ilyen darabolásokat, mert úgy gondoljuk, átdaraboláskor a térfogat nem változhat. Ez kétségtelenül igaz, ha csupa olyan részre bontunk, melyeknek van térfogata, ám ha becsúszik a darabok közé egy-egy nem mérhet
is, ne csodálkozzunk a meglep
végeredményen! Vajon síkban is ez történt? Ehhez gondoljuk meg, hogyan definiáltuk a területet! Minden X sokszöghöz rendeltünk egy t X valós számot a következ módon: i.)
t X
ii.)
Ha X
iii.) Ha
0 minden sokszögre. Y , akkor t X
X-et
az
tY .
X 1, X 2 ,
, Xn
diszjunkt
sokszögekre
bontjuk,
akkor
n
t X
t Xi . i 1
iv.) Ha Q egy egységnégyzet, akkor t Q
1.
Természetes módon merül fel bennünk a kérdés, lehet-e a terület fogalmát minden síkbeli halmazra általánosítani? És térben mi a helyzet a térfogattal? 1923-ban Banach látta be, hogy ilyen úgynevezett mérték, egyenes mentén hosszúság, síkban terület definiálható, de éppen a Banach-Tarski-paradoxon mutatja, hogy térben a térfogat fogalma nem terjeszthet
ki minden halmazra, ami a térbeli forgatások bonyolultabb
rendszerének következménye. A
síkbeli
Sierpinski-Mazurkiewicz-paradoxonnál
a
megduplázott
halmaz
megszámlálható, és így nulla mérték volt. Nem mond hát ellent megduplázhatósága annak, hogy síkban minden halmazt mérhet vé lehet tenni. Jól használható mérhet
halmazosztály akárhány dimenzióban a Borel-halmazok
osztálya, melyek n dimenziós téglákból kaphatóak a halmazelméleti m veletek megszámlálható lépésben történ alkalmazásával. Ráadásul a rajtuk értelmezett mérték nemcsak additív, hanem -additív is, vagyis ha m Ai jelöli az Ai Borel-halmaz mértékét, akkor feltéve, hogy Ai
A j = , ha i
j , teljesül az m
Vitali látta be 1905-ben, hogy
m An egyenl ség.
An n 1
n 1
-additív mérték már R minden részhalmazán sem
definiálható. 20
Az intuícionisták szerint van, de feloldható, ha töröljük halmazelméleti axiómáink közül C-t.
54
Síkban tehát soha nem fogunk tudni két különböz terület alakzatot egymásba darabolni (véges sok darab használatával). De vajon mi a helyzet az azonos terület ekkel? A Banach-Tarski-paradoxon ihlette meg Laczkovich Miklóst, aki bebizonyította, hogy az azonos terület négyzetlap és körlap egymásba darabolhatóak. Egy ennél gyengébb, de mindenképpen figyelemreméltó tételt bizonyítok. 13.6. Tétel: Ha x egy négyzet, y pedig egy kör, akkor léteznek x
y
y1
x1
x 2 és
y 2 diszjunkt felbontásai x-nek és y-nak úgy, hogy x1 ~ y1 , és x 2 ~ y 2 , ahol „~”
jelöli a hasonlósági relációt. Bizonyítás: Az adott x
b0 négyzetbe rajzoljunk egy minden oldalát érint a1 kört.
b1 legyen az a1 körbe írt olyan húrnégyzet, melynek oldalai párhuzamosak az x négyzet oldalaival. Ezt az eljárást n-szer megismételve a keletkezett négyzetekre, kapjuk a n -et illetve bn -et. Legyen x1 az x négyzet azon P pontjainak halmaza, melyekhez létezik olyan m természetes szám, melyre P
bm , de P
am
1
(az ábrán a fekete szín rész), a maradék
pontok alkossák az x 2 halmazt (az ábrán a szürke rész).
6. ábra Könnyen látható, hogy minden természetes n-re bn a n 1 -nek az x négyzet középpontjára vett négyzet középpontja, Ekkor a1
x1
1 2
1
bn -nek és ugyanígy a n
2
is
arányú kicsinyített képe. Legyen O az x
pedig az O középpontú
1 2
arányú középpontos hasonlóság.
x 2 . Mivel pedig bármely két kör hasonló egymáshoz, létezik olyan
hasonlóság, mely a1 -et y-ba viszi. Tehát x tétel bizonyítását be is fejeztük.
55
x1
x 2 és y
x1
x 2 , amivel a
Ha megfigyeljük az el bbi tétel bizonyítását, rájöhetünk, hogy abban a kör és a négyzet szerepe nem lényeges, mint ahogy az sem, hogy az egymásba skatulyázott alakzatok érintsék egymást. Kimondhattuk volna a tételt úgy is, hogy x és y két tetsz leges korlátos telt alakzat valamely R n metrikus térben. A bizonyításban csupán arra kell ügyelnünk, hogy az x által tartalmazott körlapon belül vegyük fel az y-hoz hasonló a1 alakzatot, és hogy ugyanaz a hasonlóság vigye bn -et bn 1 -be és a n 1 -et a n 2 -be, minden természetes n-re. Ez egyszer en megtehet , ha O-t az a1 által tartalmazott körlapon belül
d b1 d b0
arányát olyan kicsire választjuk, hogy b1
a1
vesszük föl és a
hasonlóság
teljesüljön ( d h
jelöli a h halmaz átmér jét). Ha ezután minden természetes n-re
bn
1
bn és a n
2
an
1
, akkor a bn
a n egymásba skatulyázottság automatikusan
teljesülni fog minden pozitív egész n-re. Ez alapján már nyugodtan kimondhatjuk: 13.7. Definíció: Ha x, y
R n , n pozitív egész, x és y pedig véges sok, páronként
hasonló darabra bonthatóak, akkor azt mondjuk, hogy x és y hasonlatosak. 13.8. Tétel: Ha x és y korlátos, telt alakzatok valamely n
N -re R n -ben, akkor
hasonlatosak. Ez azt mutatja, hogy darabolással
bár síkban a méretek közötti különbségek nem t nnek el
ha egy kicsit általánosítjuk az átdarabolás fogalmát a hasonlatosságra, a
formák közti különbségek paradox módon síkban és egyenes mentén is eltüntethet ek. Visszatérve a térbeli darabolásokhoz, Hilbert híres problémája volt az azonos térfogatú szabályos tetraéder és kocka egymásba darabolhatóságának kérdése, ha csak poliéder részekre bonthatunk. Nem sokkal a probléma Hilbert általi kit zése után Max Dehn bizonyította, hogy ez lehetetlen: olyan additív mozgásinvariáns f függvényt adott meg a poliéderek halmazán, mely egy kockán 0-t vesz fel, de f t
0 , ha t egy szabályos
tetraéder. A Banach-Tarski-paradoxon általánosításából viszont következik, hogy ha megengedünk nem mérhet
darabokat is, a probléma megoldhatóvá válik. Máig sem
tudjuk azonban, mi a válasz, ha csak Borel-halmazokra darabolhatunk.
56
Tartalomjegyzék (Mindazon fejezetek jegyzéke, melyek címe nem fordul el az 57. oldal után)
TARTALMI ÖSSZEFOGLALÓ .........................................................................................2 MÓDSZERTANI MEGJEGYZÉSEK.................................................................................3 1. ANTINÓMIÁK ÉS PARADOXONOK ...........................................................................9 2. AKHILLEUSZ ÉS A TEKN SBÉKA ............................................................................9 3. VÉGTELEN SOROK.....................................................................................................11 4. NÉHÁNY VÉGTELENNEL KAPCSOLATOS PARADOXON ..................................13 5. A SAS ÉS A BOLHA
SI KÜZDELME, MEGSZÁMLÁLHATÓ HALMAZOK .....18
6. EGY LOGIKAI CSEMEGE ..........................................................................................23 7. NÉHÁNY VALÓSZÍN SÉGSZÁMÍTÁSI PARADOXON .........................................26 8. „LÁTOM, DE NEM HISZEM!”....................................................................................31 9. AZ ÁTLÓS MÓDSZER .................................................................................................34 10. ANTINÓMIÁK A HALMAZELMÉLETBEN............................................................35 11. A HALMAZELMÉLETI ANTINÓMIÁK FELOLDÁSA..........................................38 11.1. ELS
REND NYELVEK .............................................................................................41
11.2. A HALMAZELMÉLET ZERMELO-FRAENKEL-FÉLE AXIÓMÁI.....................................42 12. EGY MODELLELMÉLETI PARADOXON ..............................................................46
57
13. DARABOLÁSOK, MÉRHET SÉG21 .........................................................................48
21
A szerz nem tudta eldönteni, felvegye-e ezt a fejezetet a tartalomjegyzékbe, így végül is az olvasóra bízzuk annak megítélését, jól tette-e, hogy mégis beleírta. Még egy felmerül kérdés: Vajon a tartalomjegyzéket is szerepeltetni kell a tartalomjegyzékben?
58
Nyilatkozat
Alulírott Szigeti Tamás, matematika szakos hallgató, kijelentem, hogy a diplomadolgozatban foglaltak saját munkám eredményei, és csak a hivatkozott forrásokat (szakirodalom, eszközök, stb.) használtam fel. Tudomásul veszem azt, hogy szakdolgozatomat a Szegedi Tudományegyetem könyvtárában a kölcsönözhet könyvek között helyezik el. aláírás: dátum:
59
Irodalomjegyzék 1.)
Biblia, A magyarországi református egyház Kálvin János Kiadója, Budapest, 1996.
2.)
Eugene P. Northrop: Rejtélyek a matematikában (Paradoxonok könyve), Gondolat Kiadó, Budapest, 1960.
3.)
Székely J. Gábor: Paradoxonok a véletlen matematikájában, Typotex, 2004.
4.)
Péter Rózsa: Játék a végtelennel, Typotex, 2004.
5.)
Németh József: El adások a végtelen sorokról, Polygon, Szeged, 2002.
6.)
Szabó László Imre: Ismerkedés a fraktálok matematikájával, Polygon, Szeged, 1997.
7.)
Raymond Smullyan: A hölgy vagy a tigris? Typotex, 1997.
8.)
Raymond Smullyan: Seherezádé rejtélye, Typotex, 2001.
9.)
Laczkovich Miklós. Sejtés és bizonyítás, Typotex, 1998.
10.)
Magyar Értelmez Kéziszótár, Akadémiai Kiadó, Budapest, 1989.
11.)
Csirmaz László: Nemsztenderd analízis, Typotex, 1999.
12.)
E. W. Beth: The foundations of mathematics, North-Holland Publishing Company, Amszterdam, 1959.
13.)
Peter J. Cameron: Sets, logic and categories, London; New York: Springer, 1999.
14.)
Stan Wagon: The Banach-Tarski Paradox, Cambridge University Press, 1987.
15.)
Csákány Béla: Diszkrét matematikai játékok, Polygon, Szeged, 1998.
16.)
Csákány Béla: Kis matematikai szintézis, Polygon, Szeged, 2003.
17.)
A 2000. évi Pázmány-ünnepségen elhangzott „A paradoxonokról” cím el adás, el adója: Laczkovich Miklós
18.)
Leindler László: Analízis, Polygon, Szeged, 2001.
19.)
Lénárd Ferenc: A problémamegoldó gondolkodás, Budapest, Akadémiai Kiadó, 1984.
20.)
Totik Vilmos: Halmazelméleti feladatok és tételek, Polygon, Szeged, 1997.
60
