A szöveg csak Firefox böngészőben jelenik meg helyesen. Használja a fenti PDF file-ra mutató link-et a letöltésre. A középiskolai anyagban két nevezetes számsorozat vizsgálata szerepel. Az elsőnél valamely kezdőelemből kiindulva az -edik tagot, -et az -edik tag, ismeretében úgy kapjuk meg, hogy az -edik taghoz egy állandó számat adunk hozzá. Képletben Itt persze és nem szükségképp pozitív egészek. Mint tanultuk, e sorozat -edik tagja és ismeretében rögtön előállítható anélkül is, hogy az összes közbülső tagokat kiszámítanánk, az formula szerint. Ebből a sorozat szerkezete világosan látható. A másik számsorozat azon számsorozat. melynél adott elemből kiindulva az -edik és -edik tagok közötti összefüggés az (1) formula helyett alakú, vagyis az -edik tagot az -edikből úgy kapjuk, hogy az -edik tagot egy előre adott, -től független számmal szorozzuk: A és persze itt sem szükségképp pozitív egészek. Itt is kiderül, hogy az -edik tag meghatározására nem kell az összes közbülső tagokat kiszámítani, hanem fennáll az, hogy Ezáltal tehát a sorozat szerkezete is világosan meg van határozva. Előfordult azonban a középiskolában más számsorozat is, mely csupa egész számból állott, ha erre a figyelmet külön nem is hívtuk fel. E sorozat a prímszámok sorozata; így nevezzük mindazon számokat, melyek csak -gyel és önmagukkal oszthatók. E sorozat az előzőktől abban is különbözik, hogy értelmezése nem úgy történt, mint (1) és (3)-ban, vagyis ú. n. rekurzív módon, hanem direkt módon, tehát egy egész számról közvetlenül eldönthetem, hogy a sorozat tagja-e, vagy sem. E sorozat szerkezetének feltárása azonban az előbbieknél lényegesen nehezebb és (2), ill. (4)-hez hasonló képletek, melyekkel az -edik prímszám rögtön felírható volna, mint függvénye, nem ismeretesek. Ilyen esetekben tehát igényeinket mérsékelnünk kell; meg kell általában elégednünk azzal, hogy a sorozatnak egy intervallumba eső elemeinek számára lehetőleg jó közelítő értékeket tudjunk megadni. A következőkben kétfajta sorozattal fogunk foglalkozni; ezek mindjárt azt is mutatni fogják, mennyire nem kell messze menni ahhoz, hogy nehéz és eddig megoldatlan matematikai problémákhoz jussunk. Ezek elsője a prímszámok azon tulajdonságát veszi alapul, hogy azok egyike sem osztható a másikával; a pozitív egészeknek oly véges vagy végtelen sorozatát fogjuk vizsgálni (melyben tehát a sorozat -edik tagját fogja jelölni), melyben valamelyik -elem csakis akkor lehet egy sorozatbeli -nek osztója, ha , vagy másképp, a sorozat két különböző eleme sohasem lehet olyan, hogy egyik osztható a másikkal. Ilyen tulajdonságú sorozat nagyon sok írható fel. Pl. | | egy-egy ilyen sorozat. E sorozatokat a következőkben közös névvel nevezzük -sorozatoknak. Foglalkozzunk először a véges -sorozatok esetével. Intuitíve érezhető, hogy, ha egy határ alatt túl sok egész szám van adva, ezek között már lesz legalább két olyan, melyek egyike osztható a másikával. Pontosabban kifejezve, tehát azt kérdezzük, hogy egy olyan -sorozatnak, melynek minden tagjai ,. legfeljebb hány tagja ]ehet; e maximális tagszámot jelöljük -nel. Legyen először páros, azaz Hogy az onnan világos, hogy meg lehet adni egy olyan -sorozatot igen könnyen, melynek számú, -et meg nem haladó tagja van. Egy ilyent alkotnak nyilván az számok, hiszen ezek közül vett bármely kettőnek a kisebbike is legalább a nagyobbika viszont legfeljebb , tehát nem érheti el a kisebbiknek a hétszeresét sem, nem lehet tehát meg benne egész számszor. Azt állítjuk azonban, hagy ennél több tagú -sorozat, melynek tagjai nem haladják meg a -et, nincs is, azaz Ezen állítás úgy is megfogalmazható. hogy bárhogy is adunk meg számú különböző egész számot, ezek között már van legalább két olyan szám, melyek kisebbike osztója a nagyobbiknak. A tétel Erdős Páltól származik; erre két bizonyítást fogunk elmondani. Az első egy direkt bizonyítás. mely az ú. n. skatulya-elven alapszik. Ez azt mondja ki, hogy ha darab skatulyába darab tárgyat kell elhelyeznünk, akkor legalább egy olyan skatulya lesz, melybe legalább két tárgy esik. Ennek segítségével a bizonyítás a következőképp végezhető el. Állítsuk elő a (6) alatti számokat alakban, ahol páratlan és egész, mely természetesen lehet is. Ezen és nyilván egyértelműen meg vannak határozva. Mivel páratlan, tehát értéke csak az számok közül való lehet. Tehát a -k lehetséges értékeinek száma legfeljebb , míg a száma feltevés értelmében . De ekkor az előbbi skatulya-elv alapján a -ket véve tárgyakul őket lehetséges értékeik szerint skatulyába téve (t. i. közös skatulyába téve, az egyforma értékű -ket) adódik. hogy legalább két esik ugyanazon skatulyába, azaz a -k között van legalább kettő, amelyik egyenlő, pl. De ekkor már azt állítjuk, hogy a (6) alatti -számok közül ezen és indexekkel képezett és már a kívánt tulajdonsággal bírnak, azaz valamelyikük osztható a másikkal. Ha u. i. akkor máris kapjuk, hogy | | amivel az állítás máris be van bizonyítva.
A második bizonyítás e tételt teljes indukcióval bizonyítja be. és -re a tétel kipróbálással könnyen belátható. Tegyük fel tehát, hogy a tétel igazolva van -re, ahol tehát feltételezhetjük, hogy Vagyis bizonyítottnak feltételezzük. hogy | | (10) | és nézzük a tételt -re. Tegyük fel tehát állításunkkal ellentétben, hogy volna egy -tagú számsorozat, mely egy -sorozatot alkotna és megmutatjuk, hogy ez lehetetlen. Nézzük először meg, hogy ezen -k közül hányra lehet igaz, hogy A (10) alatti feltevést -gyel alkalmazva, nyerjük, hogy ezek száma legfeljebb . Mivel a (11) alatti teljes száma , ez csak úgy lehetséges, ha és persze | | (13) | Azt állítjuk, hogy a (13) alatti -k értéke nem lehet. Ez egyszerűen azért igaz, mert ellenkező esetben a (11) sorozatban máris volna két oly elem, melyek egyike osztója másiknak; nyilván és ilyen elemek volnának. De ugyanezen okból -nek bármely osztója sem léphet fel a (13) alatti -k között, azaz Tehát minden esetre betoldható a (13) számok közé; ha a azon index, melyre akkor tekintsük (13) helyett az -tagból álló | | (15) | sorozatot. Erre az indukciós feltevést -gyel alkalmazva nyerjük, hogy elemei közt van legalább két olyan, hogy egyik osztója a másiknak. Állítás, hogy ezek közül egyik sem lehet. Ha u. i. az egyik ily elem volna, akkor a másik elem osztója vagy többese volna; az első eshetőség (14) által van kizárva, a másik pedig azáltal, hogy legkisebb többszöröse volna és ez nem tartozhat a (15) alatti sorozathoz, hiszen ennek tagjai nem nagyobbak, mint . Tehát a (15) sorozat -től különböző tagjai között kell lennie kettőnek, melyek egyike a másiknak osztója. De előbbiek szerint ezek már az eredeti (13) sorozatnak is elemei, s így annak kiválasztása szerint egyik sem lehet osztható a másikkal. Ezzel tehát az állítást -re is igazoltuk. Mi lesz a helyzet -gyel, azaz legfeljebb hány oly egész szám van, melyek értéke legfeljebb és melyek egyike sem osztható a másikkal? Mint az sorozat példája mutatja. Ha viszont volna oly -sorozat, melynek oly tagja volna, melyek nem nagyobbak, mint , akkor egyben is volna, ami azonban (10)-nek ellentmond. Tehát Összefoglalhatjuk (10) és (16) eseteit, ha bevezetjük a jelzést azon legnagyobb egész szám jelzésére, mely még nem nagyobb, mint (tehát pl. . Azt állítjuk, hogy (10) és (16)-ból minden -re Ha u. i. , akkor ebből tényleg és, ha akkor Ezzel tehát minden véges -re sikerült meghatározni azt, hogy azon -sorozatok között, melyek elemei nem nagyobbak, mint , mi az elérhető maximális tagszám. Mi a helyzet végtelen sorozatokra vonatkozólag? Van-e ilyen egyáltalán? A prímszámok sorozata erre rögtön ad példát. Tehát ilyen sorozatokra a maximális tagszám kérdésének nincs értelme. Hogy lehet azonban végtelen számsorozatokat sűrűség szempontjából mégis összehasonlítani? Ha pl. az
sorozatokat összehasonlítjuk, intuitíve azt érezzük, hogy az előbbi sorozat sűrűbb, mint a másik. Erre nyilván az ad okot, hogy bármely pozítív szám alá a (18) első sorozatából több esik, mint a másodikból. Ez azt a gondolatot ébreszti, hogy egy végtelen sorozat sűrűségét értelmezhetjük a nem-negatív számok segítségével, ahol az adott sorozatunk azon elemeinek számát jelenti, melyek nem haladják meg -et. Ezen számok segítségével többféleképp lehet egy végtelen számsorozat sűrűségét értelmezni, melyek mindegyikének megvan a maga alkalmazása. Itt e finom fogalmakat persze nem értelmezhetjük pontosan, de néhányat intuitíve megvilágíthatunk. Ha a számsorozatunk pozitív, növekvő számokból áll, akkor a hányados fix mellett azt fejezi ki, hogy az alatti egészek hány százaléka esik a mi sorozatunkba. Ha mármost van oly pozitív tört, hogy minden elég nagy -re, akkor azt mondjuk, hogy sorozatunk felső sűrűsége . Nézzük meg, mit lehet az eddigiek alapján egy végtelen -sorozat felső sűrűségére kimondani. (17) alapján, felhasználva azt, hegy általában nyerjük, hogy | | azaz helyett -t véve, ha tetszőleges kis szám is, (19) fennáll. Vagyis egy tetszőleges végtelen -sorozat felső sűrűsége tetszőleges kis pozitív esetén . Biztos-e azonban itt is, hogy ezt nem lehet javítani? Az előbb felhozott alakú sorozatok különféle -ekre nem foghatók fel egy ugyanazon végtelen sorozat részeiként. Mégis ki lehet mutatni, hogy a felső sűrűségre vonatkozó tétel sem javítható, amit egy kissé pongyola formában úgy lehet kimondani, hogy megadható oly végtelen -sorozat, melyhez végtelen sok oly található, mely alatt sorozatunk az összes egész számoknak majdnem -át tartalmazza. E mélyebb eredmény bizonyításával azonban itt nem fogunk foglalkozni. Térjünk rá most második típusú sorozataink vizsgálatára, melyeket rövidség kedvéért nevezzünk -sorozatoknak. Ezektől követeljük meg azt, hogy ne legyen bennük egyetlen számtani sornak három egymásutáni tagja sem. Más alakban e követelmény azt mondja ki, hogy az egyenletnek ne legyen oly megoldása, melyre az , , számok mindegyike az adott -sorozatba esik. Lehet-e találni egyáltalán végtelen -sorozatot? Itt már nem olyan magától értetődő, mint az előbb, hogy ilyen sorozat létezik. Könnyű azonban kimutatni, hogy pl. a sorozat -sorozat. Ez azt jelenti, hogy nem állhat fenn alakú egyenlet, ahol , , nem-negatív egészek. Mert tegyük fel, hogy (22) teljesülne és ebből egy ellentmondást fogunk levezetni. Mindenesetre leoszthatunk -nak annyiadik hatványával, amekkora az , , számok közül a legkisebb; ami által egyenletünk vagy alakok egyikét veszi fel, ahol az első esetben és a második esetben A (24)‐(26) egyenlet nyilván nem oldható meg, mert csak esetben lehetséges. A (23) egyenletre vonatkozólag miatt a baloldal nagyobb -nél, tehát ; de akkor a (23) egyenlet azért lehetetlen, mert a jobboldal osztható -mal, a baloldal pedig nem. Végtelen -sorozatok esetén a (21) alattinál jóval sűrűbb -sorozatok is képezhetők. Egy ilyen sorozatot nyerünk már akkor is, ha azokat az egész számokat vesszük, melyek előállíthatók alakban, úgy, hogy az számjegyek értéke vagy . Itt nem fogunk foglalkozni sem annak bebizonyításával, hogy e számok egy -sorozatot alkotnak, sem azzal, hogy e sorozat sűrűségét megvizsgáljuk; csupán azt jegyezzük meg, hogy e sorozat jóval ritkább, mint az előző problémában bizonyítás nélkül meg, említett végtelen -sorozat. Milyen felső becslést lehet kimondani egy véges -sorozat tagszámára? Jelöljük -nel azon -sorozatok maximális tagszámát. melyek minden egyes tagja legfeljebb . Párhuzamban az elúzö vizsgálatokkal, kérdezzük, igaz-e itt is, hogy Mint látni fogjuk, ez igaz lesz, hacsak A tételt indukcióval fogjuk bizonyítani, éspedig az indukció egy szokatlan fajtájával, melyet -ről -re való következtetés-nek nevezhetünk; a bizonyítás arra is jó lesz, hogy belássuk, hogy az indukció elejénél nem szabad elhamarkodottan eljárnunk. A bizonyításhoz két egyszerű megjegyzésre lesz szükség. Legyen egy -sorozat; állítás, hogy az | | (30) | ill. | | (31) | sorozatok maguk is -sorozatok. Ha ez nem volna igaz, akkor volna a (30), ill. (31) sorozatnak három olyan tagja, , , melyekre | | ill. De mindkettőből következne, ami máris ellentmond annak, hogy a (29) sorozat -sorozat. Mivel elemből -öt -féleképp választhatunk ki, kipróbálással igazolható, hogy Mivel az sorozat -sorozat, tehát Azt állítjuk, hogy Mindenesetre az sorozat nyilván -sorozat, azaz Ha volna, akkor tehát volna oly tagú -sorozat, melynek tagja, -nél nem nagyobbak. Ha ezek között a és mindketten nem szerepelnének akkor a sorozatnak öt oly tagja volna, mely -nál nem nagyobb; ez azonban ellentmond annak, hogy . További állítás, hogy és is szerepelne e hattagú sorozatban. Ha u. i. nem szerepelnének, akkor (30)-at alkalmazva, oly hattagú sorozathoz jutnánk, melyben és és közül legalább az egyik hiányzik; azt azonban az előbb már láttuk, hogy ez nem lehetséges. Tehát a feltételezett hattagú -sorozatban az szerepelnének. De ekkor máris nem szerepelhet a sorozatban a (az miatt) továbbá az (, , miatt), azután a (, , miatt) és végül (, , miatt); így, mint egyetlen lehetőség, marad az sorozat, ami nyilván nem -sorozat, az , , számok miatt és így tényleg Tekintsük -t .Ha volna, akkor az előbbi gondolatmenet megismétlésével adódik, hogy szükségkép a sorozat tagjai volnának. De ekkor már sorozatunkban nem szerepelhetne a (, , miatt), a (, , miatt), a (, , miatt) és a , miatt). Viszont ha a nem lépne fel a sorozatban, akkor a sorozat csupán az sorozat lehetne, ami azonban , , miatt nem -sorozat. Hasonlóképpen a -nek a sorozatban fel kell lépnie, mert különben sorozatunk csupán az sorozat lehetne, ami megint nem -sorozat , , miatt. De ekkor a sorozat tartalmazza tehát az számokat és, mint kipróbálással rögtön látható, ezekhez nem lehet alatt oly hetediket találni, hogy ezek egy -sorozatot alkossanak. Azaz ; mivel -sorozat, tehát és így Az volna várható, hogy . De az sorozat nyilván -sorozat; azaz . Ha viszont volna, akkor mivel az ezt realizáló sorozatban legfeljebb két elem lehetne nagyobb -nél, így volna, ami előbbiek szerint nem igaz. Tehát azaz -re a (27) alatti egyenlőtlenség nem áll! Viszont a további esetek vizsgálata könnyebben lesz eszközölhető egy további egyszerű észrevétellel. Tekintsük -et és legyen egy ilyen -sorozat. Vegyük külön azokat a tagokat, melyeknek értéke legfeljebb és azokat, melyek -nél nagyobbak, de -nél nem nagyobbak. Az elsőbe tartozó elemek száma legfeljebb , mert különben már alatt volna a sorozatban a (20) egyenletnek egy megoldása. A második kategóriába tartozó elemek mindegyikéből -et levonva, adódik egy olyan -sorozat, melynek elemei nem nagyobbak, mint , tehát az e részbe eső elemek száma (30) alapján legfeljebb , azaz Ez a kívánt egyszerű észrevétel. Ebből
és most térhetünk csak rá az indukcióra. Tegyük fel, hogy oly egész, melynek értéke legalább és tegyük fel, hogy a tétel igazolva van, ha és legyen . Ekkor (36)-ból | | (39) | De miatt azaz az indukciós feltevés alkalmazható -ra, és így Tehát (39)-ből azaz a (27) alatti egyenlőtlenség -re is igazolva van. Az értékei egy darabig explicit megadhatók. Így
Ezek segítségével előbbihez hasonló módon kimutatható, hogy tetszőleges kis pozitív mellett, hacsak -tól függően elég nagy, akkor Ennek bizonyítását itt nem részletezzük. Igen valószínű ‐ ellentétben az előbbi feladattal ‐ hogy minden végtelen -sorozat felső sűrűsége kisebb bármily kis pozitív számnál, de e sejtés mindmáig bebizonyítatlan. Az előbbiekben láttuk egész számok sorozatainak két típusát. Mindkettő tárgyalásában felhasznált módszerek különbözők voltak és az eredmények is. Már ezek is sejtetik, hogy ilyen számelméleti tulajdonságokkal értelmezett sorozatok vizsgálatára egységes módszer nem igen remélhető, ezek vizsgálata mindig új nehézséggel járó, érdekes feladat. Ha ezt sikerült ezen előadással valamelyest is érzékeltetnem, akkor célomat elértem. E bizonyítás Vázsonyi Endrétől és Wachsberger Mártától származik.E bizonyításra tőlem függetlenül Lázár Dezső barátom is rájött, aki 1943-bon a fasizmus áldozata lett.A/B jelentése A osztója B-nek.E sejtést újabban bebizonyította C. Roth angol matematikus. |