14. FEJEZET: Tetszőlegesen sok és végtelen sok{mchap:k_ii_vegtelen}
Ebben a fejezetben - ha mást nem mondunk - végtelenen mindig megszámlálható végtelent értünk. De a legtöbb feladat megoldásához nem szükséges tudni, hogy mit jelent a megszámlálható végtelen fogalma.
Véges és végtelen
Feladat: 14.1. {k_ii_090711sl_vegtelen01}
A természetes számok egy sorozatáról tudjuk, hogy van benne akármilyen hosszú számtani sorozat. Következik-e ebből, hogy maga a sorozat is számtani sorozat?
Feladat: 14.2. {k_ii_090711sl_vegtelen02}
Van-e olyan végtelen nagy halmaz, amelynek minden eleme véges szám?
Feladat: 14.3. {k_ii_090724sl_vegtelen03}
Van-e olyan véges halmaz, amelynek minden eleme végtelen?
Feladat: 14.5. {k_ii_090711sl_vegtelen03}
Az
S halmazról tudjuk, hogy olyan részhalmaza a valós számoknak, amely minden egész számnál tartalmaz nagyobbat. Következik-e ebből, hogy az
S halmaz végtelen?
Nem árt összefoglalni azokat a meghatározásokat, amelyekre eddig kimondatlanul építettünk:
Definíció: Egy halmazt akkor és csak akkor nevezünk
végesnek, ha van olyan
n természetes szám, amelyre
n eleme van.
Definíció: Egy halmazt akkor és csak akkor nevezünk
végtelennek, ha nincs olyan
n természetes szám, amelyre
n eleme volna.
Minthogy ezek a véges (és végtelen) halmaz definíciói, itt nem használtuk, hogy a feladat
számhalmazról szól. A véges
számhalmazoknak azonban van egy fontos tulajdonságuk, amely segítségével a bizonyítás ugyancsak egyszerűsíthető. Az alábbi megoldás ezt mutatja.
Tegyük fel, hogy az
S számhalmaz véges. Ekkor
van egy legnagyobb eleme, legyen ez az
a szám. Nem nehéz ennél az
a számnál nagyobb egész számot találni: ilyen például az
[a]+1 szám. A feladat feltétele szerint
S-ben van egy ennél nagyobb szám, márpedig az
a-nál is nagyobb. Ez ellentmond annak, hogy
a az
S halmaz legnagyobb eleme. Az
S halmaz tehát nem lehet véges.
Megjegyzés: Ebben a megoldásban tehát a következő fontos gondolatot használtunk:
Minden véges számhalmaznak van legnagyobb eleme.
A
11.,
12. és
13 fejezetekben bemutatjuk, hogy ez a látszólag ,,ártalmatlan" gondolat milyen erős bizonyítási eszközt (sőt eszközöket) ad a kezünkbe. Sőt, erre az egyszerű tulajdonságra támaszkodva olyan fogalmakat is bevezethetünk, amelyek gráfelméleti és más kombinatorikai struktúrákba engednek mélyebb betekintést. Ilyen volt például a
fa, faváz, maximális független élhalmaz stb. fogalma.
Feladat: 14.6. {k_ii_090724sl_vegtelen01}
Ha egy számhalmaz véges, akkor van legnagyobb és legkisebb eleme. Igaz-e az állítás megfordítása is? Azaz igaz-e, hogy ha egy számhalmaznak van legnagyobb és van legkisebb eleme, akkor véges?
Tetszőlegesen sok és végtelen sok
a számelméletben
Feladat: 14.7. {k_ii_090711sl_vegtelen04}
A természetes számok egy sorozatáról tudjuk, hogy van benne akármilyen hosszú számtani sorozat. Következik-e ebből, hogy van benne végtelen hosszú számtani sorozat is?
Feladat: 14.8. {k_ii_090711sl_vegtelen05}
Felbonthatók-e a természetes számok két olyan diszjunkt (közös tag nélküli) sorozatra, amelyek mindegyikében van akármilyen hosszú számtani sorozat?
Feladat: 14.9. {k_ii_090711sl_vegtelen06}
Felbonthatók-e a természetes számok két olyan diszjunkt (közös tag nélküli) sorozatra, amelyek mindegyikében van akármilyen hosszú számtani sorozat, de egyikben sincs végtelen hosszú számtani sorozat?
Feladat: 14.10. {k_ii_090711sl_vegtelen07}
Van-e a prímszámok sorozatában végtelen hosszú (nem nulla differenciájú) számtani sorozat?
Megjegyzés: Sokkal nehezebb kérdés, hogy van-e akármilyen hosszú számtani sorozat prímekből? Csak nemrég (2004-ben) mutatta meg Ben Green és Terence Tao, hogy a válasz igenlő.
Feladat: 14.11. {k_ii_090711sl_vegtelen09}
Tekintsük a prímszámok sorozatát, s benne a szomszédos tagok különbségét. Ez nyilván nem lehet végtelen nagy, hiszen mindig egész szám. De lehet-e akármilyen nagy?
Feladat: 14.12. {k_ii_090711sl_vegtelen10}
a)* Bizonyítsuk be, hogy a szomszédos négyzetmentes számok között akármilyen nagy különbségnél előfordul nagyobb. ([
26], 89. oldal.) Vagy másképp fogalmazva: van tetszőlegesen sok egymás melletti nem-négyzetmentes szám.
b) Lehet-e tetszőlegesen sok egymás melletti négyzetmentes számot találni az egészek között?
Feladat: 14.13. {k_ii_090811sl_vegtelen01}
*
Bizonyítsuk be, hogy a szomszédos teljes hatványok között akármilyen nagy különbségnél előfordul nagyobb. ([
26], 50. oldal.)
Teljes hatványnak az olyan számokat nevezzük, amelyek egy egész számnak egynél magasabb hatványai.
Feladat: 14.14. {k_ii_090711sl_vegtelen11}
*
Tekintsük a
d(1),d(2),…,d(n),… sorozatot, ahol
d(n) az
n szám pozitív osztóinak a számát jelenti. Bizonyítsuk be, hogy ebben a sorozatban a szomszédos elemek közötti különbség tetszőleges nagy lehet. (Ez pontosan fogalmazva azt jelenti, hogy bárhogyan adunk meg egy
K számot, van olyan
n, hogy
d(n) és
d(n+1) különbsége nagyobb, mint
K.)
Feladat: 14.15. {k_ii_090726sl_vegtelen01}
*
Az előző
14.14. feladat élesítéseként bizonyítsuk be a következő tételt:
Hegy-tétel.
Tetszőlegesen megadott
K számhoz található olyan
n pozitív egész szám, hogy
d(n) legalább
K-val nagyobb mind
d(n-1)-nél, mind
d(n+1)-nél.
A tétel onnan kapta a nevét, hogy ha
d(n)-et ábrázoljuk, akkor a tétel állítása szerint
d(n-1)-ről nagyot kell lépni felfelé, hogy
d(n)-be jussunk, majd onnan nagyot kell lépni lefelé, hogy
d(n+1)-be jussunk. Azaz
d(n) grafikonján tetszőlegesen nagy (meredekségű és magasságú) ,,hegy" van.
Tetszőlegesen sok, végtelen sok a gráfoknál
Feladat: 14.16. {k_ii_090711sl_vegtelen08}
Van-e olyan (egyszerű, végtelen) gráf, amelyben van tetszőlegesen nagy véges teljes részgráf, de nincs végtelen teljes részgráf?
Feladat: 14.17. {k_ii_090811sl_vegtelen001}
Van-e végtelen sok olyan halmaz, amelyek közül bármely véges sok metszete végtelen, de bármely végtelen sok metszete véges?
Feladat: 14.18. {k_ii_090725sl_vegtelen01}
Van-e olyan (egyszerű, végtelen) gráf, amelyben van tetszőlegesen nagy véges teljes részgráf, de nincs végtelen teljes részgráfja, s ugyanez a komplementer gráfra is igaz?
Feladat: 14.19. {k_ii_090711sl_vegtelen12}
Mint ismeretes, Tigris (a Micimackóból) a fán csak felfelé tud mászni, lefelé sajnos nem. Rajzoljunk olyan végtelen fát, amelyre igaz a következő:
Ha megmondjuk, milyen magasra kell másznia Tigrisnek, akkor fel tud mászni olyan magasra, de bármerre is mászik felfelé, egy idő után (véges sok lépés után) meg kell állnia.
Más szavakkal:
Rajzoljunk olyan végtelen fát, amelyben van akármilyen hosszú út, de nincs végtelen hosszú út.
A fenti feladatok egyrészt arról szóltak, hogy ha valamiből van akármilyen sok, akkor van végtelen sok is, illetve arról, hogy valamiből van akármilyen nagy, de nincs végtelen nagy, például számsorozatokban ,,luk", függvényekben ,,kilengés", gráfokban például teljes részgráf.
A következő feladatok nagyon hasonló kérdéseket vetnek fel: azt kérdezik, hogy ha egy
tulajdonságról tudjuk, hogy igaz
akármilyen nagy véges gráfokra, következik-e ebből, hogy igaz
végtelen gráfokra is?
Feladat: 14.20. {k_ii_090711sl_vegtelen14}
Ismeretes (l. a
12.5. feladatot), hogy ha egy egyszerű véges gráfban minden pont foka legalább kettő, akkor a gráfban van kör. Igaz-e ez egyszerű végtelen gráfra is?
Feladat: 14.21. {k_ii_090711sl_vegtelen15}
Ismeretes, hogy minden egyszerű véges gráfban van két azonos fokú pont. Igaz-e ez egyszerű végtelen gráfokra is?
Feladat: 14.22. {k_ii_090711sl_vegtelen16}
Ismeretes, hogy ha egy véges egyszerű gráfban minden kör hossza páros, akkor a gráf páros gráf, pontjai két színnel jól színezhetők. Igaz-e ez végtelen gráfokra is?
Feladat: 14.23. {k_ii_090711sl_vegtelen17}
*
Egy egyszerű végtelen gráf minden véges része három színnel jól színezhető. Következik-e ebből, hogy az egész gráf is három színnel jól színezhető?
Feladat: 14.24. {k_ii_090729sl_vegtelen01}
Előbb igazoljuk az alábbi (i) állítást, majd ennek segítségével adjunk bizonyítást a
14.23. feladatra!
(i) Ha egy végtelen gráf minden véges részgráfja három színnel színezhető, de erre a tulajdonságra ,,kritikus", azaz bármely még nem szereplő él behúzásával ez a tulajdonsága megszűnik, akkor a gráf csúcsai három osztályba sorolhatók úgy, hogy az azonos osztályba tartozó pontok között nem fut él, a különböző osztályba tartozók között fut él.
Feladat: 14.25. {k_ii_090711sl_vegtelen20}
Egy egyszerű végtelen gráf minden véges része három színnel jól színezhető. Rögzítsük minden véges részgráf egy három színnel való jószínezését, a továbbiakban csak ezt a kiválasztott színezést tekintjük jólszínezésnek.
A) Bizonyítsuk be, hogy bárhogy választunk ki egy
x pontot, ahhoz hozzárendelhetjük a három szín egyikét úgy, hogy van
tetszőlegesen nagy,
x-et tartalmazó részgráf, amelynek jólszínezésében
x ezzel a színnel van színezve.
B) Rendeljünk ilymódon hozzá minden ponthoz egy-egy színt. Mutassunk példát arra, hogy a végtelen gráf ilymódon kapott színezése nem jólszínezése a gráfnak!
C) Megadható-e végtelen sok páronként különböző halmaz úgy, bárhogyan választunk ki közülük végtelen sokat, azok uniója megegyezik az eredeti végtelen sok halmaz uniójával?
D) Próbáljuk most eldönteni a
14.23. feladatban feltett kérdést!
Folytatás: a König-lemma
Feladat: 14.26. {k_ii_090711sl_vegtelen21}
Most visszatérünk a
14.19. feladatban már szerepelt Tigrishez. Most egy olyan fán kell útnak indulnia, amelynek minden szintjén csak véges sok elágazás van. Mutassuk meg, hogy most sikerülhet neki végtelen magasra felmásznia (természetesen anélkül, hogy közben lefele is kellene másznia).
Feladat: 14.27. {k_ii_090711sl_vegtelen22}
A
14.26. feladat megoldásához Tigris beszerzett egy olyan látcsövet is, amit jól beállítva akármilyen magasra ellát, de végtelen magasra nem. Tudunk-e neki tanácsot adni, milyen eljárás szerint válassza meg az utat a következő szintre, hogy soha ne kelljen megállnia? (Az eljárásnak minden lépésben véges sok ideig szabad tartania. Ahhoz, hogy Tigris a látcsővével
n emelet magasba ellásson,
n másodpercre van szüksége.)
Feladat: 14.28. {k_ii_090729sl_vegtelen02}
Bizonyítsuk be a
König-lemmát. Ha egy végtelen fa minden csúcsának foka véges, akkor van benne végtelen hosszú út.
Vagy másképp fogalmazva: ha egy gyökerezett végtelen fa minden emeletén véges sok pont van, akkor van benne végtelen hosszú út.
Feladat: 14.29. {k_ii_090711sl_vegtelen23}
Próbáljunk a König-lemma (
14.28. feladat) segítségével megoldást találni a
14.23. feladatra!
Feladat: 14.30. {k_ii_090711sl_vegtelen24}
Milyen
k természetes számokra igaz az alábbi állítás?
Ha egy egyszerű végtelen gráf minden véges részgráfja
k színnel színezhető, akkor az egész gráf is
k színnel színezhető.
Az olyan tulajdonságot, amely ,,öröklődik" a végtelenre, ha minden véges részhalmazon igaz, kompaktsági tulajdonságnak is szokás nevezni. A König-lemma segítségével a legtöbb ilyen kompaktsági tétel bizonyítható. Egy analízisbeli kompaktsági tétel König-lemmával történő bizonyítását l. az ANAL.III.1.1. feladatnál.
Feladat: 14.31. {100921SL_vegtelen01}
Kutató munka:
Tekintsük a gráf alábbi jellemzőit:
a) A független pontok maximális száma,
b) a független élek maximális száma,
c) a gráf kromatikus száma,
d) a lefedő élek minimális száma.
Fogalmazzuk meg mindegyik esetében, hogy mit jelent az, ha öröklődik a végtelen gráfra a véges részgráfjairól és állapítsuk meg, hogy melyik igaz közülük.
Feladat: 14.32. {100921SL_vegtelen02}
Kutató munka:
Döntsük el, hogy igaz-e a következő: ha egy végtelen gráf minden részgráfjának élei lefoghatók
k ponttal, akkor a gráf összes éle is lefogható
k ponttal.
Megjegyzés. A fejezet témájába tartozó feladat még a GR.II.1.34. feladat.