A szeptember 14.-i gyakorlat témája

Az előző gyakorlat egyik feladatának megoldásában (8. feladat) fontos szerepet játszott az az észrevétel, hogy ha két (véges) halmaz elemei között kölcsönösen egyértelmű megfeleltetés létesíthető, akkor ez a két halmaz azonos számosságú. Felmerül a kérdés, hogy igaz-e ez az állítás végtelen halmazok esetében is. Megjegyeztem, hogy valójában ennek a tulajdonságnak a segítségével definiáljuk két (általános, tehát akár véges akár végtelen) halmaz számosságának az egyenlőségét. Érdemes felidézni az alapvető eredményeket végtelen halmazok számosságáról. Sok a végtelen halmazok számosságáról szóló eredmény hasonló a véges halmazok számosságának viselkedéséről szóló eredményekhez, de vannak lényeges és meglepő különbségek is. Érdemes ezeket az eredményeket megismerni, mert segítenek néhány e problémakörrel látszólag semmilyen kapcsolatban nem levő fogalom és eredmény jobb megértésében. Először felidézem annak a definicióját, hogy mikor nevezünk két halmazt egyenlő számosságúnak, illetve mikor mondjuk, hogy az egyik halmaz számossága nagyobb, mint a másiké.

Két halmaz számosságának az összehasonlítása. Legyen adva két általános (véges vagy végtelen) A és B halmaz. Azt mondjuk, hogy az A halmaz számossága nagyobb vagy egyenlő, mint a B halmaz számossága (jelölésben |A| ⪰ |B|), ha létezik a B halmaznak egy olyan leképezése az A halmazra, amelyben a B halmaz különböző elemeinek a képe különböző. Azt mondjuk, hogy az A halmaz és a B halmaz számossága megegyezik, (jelölésben |A| = |B|), ha az A halmaz és B halmaz elemei között létezik kölcsönösen egyértelmű megfeleltetés. Azt mondjuk, hogy az A halmaz számossága (szigorúan) nagyobb, mint a B halmaz számossága, (jelölésben A ≻ B), ha az A halmaz számossága nagyobb vagy egyenlő, mint a B halmaz számossága, de a két halmaz számossága nem egyenlő.

Ha halmazok számosságait összehasonlítjuk, akkor az így bevezetett nagyobb és egyenlő fogalmak is teljesítik azokat az alapvető tulajdonságokat, amelyeket elvárunk. Ezt a tényt fogalmazza meg az alábbi eredmény. Megjegyzem, hogy a Tétel bizonyítása, amelyet nem tárgyalunk, nehéz.

Tétel. Tetszőleges két A és B halmaz számossága összehasonlítható, azaz teljesül vagy az |A| ⪰ |B| vagy a |B| ⪰ |A| reláció. Ha egyidejűleg teljesülnek az |A| ⪰ |B| és |B| ⪰ |A| relációk, akkor |A| = |B|. Ha |A| ⪰ |B| és |B| ⪰ |C| valamely A, B és C halmazokra, akkor |A| ⪰ |C|. Igaz továbbá, hogy |A| = |A|, |A| ⪰ |B|, ha B ⊂ A, és ha |A| = |B| és |B| = |C|, akkor |A| = |C|.

Az előző Tétel eredménye halmazok nagyságának összehasonlításáról nem meglepő. Viszont végtelen halmazok számosságának van néhány meglepő, váratlan tulajdonsága is. Erre mutat példát a következő feladat, amelynek itt csak az eredményét írom le, de a gyakorlaton vázolom az eredmény bizonyítását is. Továbbá e feladat ismertetése után megfogalmazok néhány további váratlan eredményt végtelen halmazok viselkedéséről.

Feladat: Hasonlítsuk össze a természetes számok, az egész számok, a racionális számok, a valós számok és a sík pontjainak a számosságát.

Megoldás: Világos, hogy az egész számok és a racionális számok számossága nagyobb vagy egyenlő, mint a természetes számok számossága. Kevésbé nyílvánvaló, sőt meglepő, hogy valójában az egész és racionális számok számossága megegyezik a természetes számok számosságával. Ezt meg lehet mutatni az egész, illetve a racionális számok alkalmas felsorolásának a segítségével. A valós számok számossága viszont szigorúan nagyobb, mint a természetes számok számossága. Ezt egy ravasz, átlós eljárásnak nevezett módszer segítségével lehet bebizonyítani. Ha a valós számokat felírjuk tizedestört alakban, akkor láthatjuk, hogy a valós számok és egy egyenes pontjainak a számossága megegyezik. Innen látható, hogy a valós számok számossága kisebb vagy egyenlő, mint a sík pontjainak a számossága. Be lehet látni, hogy valójában a sík pontjainak a számossága megegyezik az egyenes pontjainak a számosságával. Ugyanígy, a tér pontjainak a számossága is megegyezik a valós számok számosságával. Viszont van olyan halmaz, amelynek a számossága még a valós számok számosságánál is nagyobb. Ilyen halmaz például az összes (valós számokon definiált, valós szám értékű) függvényből álló halmaz.

Az előző feladat kapcsán felidézek egy a matematikában gyakran használt fogalmat.

A megszámlálható számosság fogalma. Azt mondjuk, hogy egy végtelen halmaz megszámlálható számosságú, ha számossága megegyezik a természetes számok számosságával, azaz létezik kölcsönösen egyértelmű megfeleltetés e halmaz elemei és a természetes számok között.

Megjegyzés: A fenti elnevezés természetes, hiszen az, hogy egy halmaz megszámlálható számosságú azt jelenti, hogy a halmaz elemeit fel lehet sorolni, meg lehet számolni. Valójában, a felsorolást kezdve az 1 számnak megfelelő elemmel egy az ebben a halmazban és a természetes számok halmazában előforduló elemek közötti kölcsönösen egyértelmű megfeleltetésben, folytatva a 2, 3 számnak megfelelő elemmel, és így tovább, előbb-utóbb minden elemet felsorolunk. Azokat a halmazokat, amelyeknek a számossága megegyezik a valós számok számosságával kontinuum számosságúaknak nevezzük.

Néhány további meglepő eredmény:

Tétel. Legyen A végtelen halmaz, A_{1} és A_{2} két e halmazzal azonos számosságú halmaz. Akkor A_{1} ∪ A_{2} számossága megegyezik az A halmaz számosságával. Sőt, ha A_{1}, A_{2}, …

megszámlálható sok az A halmazzal azonos számosságú halmaz, akkor az ⋃_{k=1}^{∞} A_{k} halmaz

számossága is megegyezik az A halmaz számosságával. Ha A végtelen halmaz, akkor létezik az A halmaznak olyan valódi részhalmaza, amelynek számossága megegyezik az A halmaz számosságával.

Történelmi megjegyzés: Halmazok számosságának fogalmát Georg Cantor német matematikus vezette be a XIX. század második felében. Érdemes megemlíteni, hogy ezt a fogalmat, illetve a hozzákapcsolódó elméletet még a matematikai közvélemény is csak nehezen tudta elfogadni abban a korban, amikor Cantor élt.

1. Egy tóban 10000 hal van. Véletlenül kihalásznak belőle 1000 darabot, ezekre piros pöttyöt festenek és visszaengedik őket a tóba. Ezután ismét kifognak véletlenül 1000 halat. Mi annak a valószínűsége, hogy a kifogott halak között 100 megfestett van?

Megoldás: \binom{1000}{100}\binom{9000}{900} \binom{10000}{1000}. Ugyanis a második fogásban összesen \binom{10000}{1000} féle fogásered-

mény lehetséges, és minden fogáseredmény egyformán valószínű. (A halakat megkülönböztetjük.) Az olyan fogáseredmények száma, amelyekben az 1000 pirossal megjelölt halból 100-t a 9000 meg nem jelölt halból pedig 900-t fogtak ki \binom{1000}{100}\binom{9000}{900}. Megjegyzés: A gyakorlatban előforduló kérdés ennek fordítottja. Elvégezzük a fenti kisérletet, összeszámláljuk a megfestett halakat, és ebből próbálunk következtetni a tóban levő halak számára. Hogyan érdemes ezt csinálni? Ez későbbi vizsgálatok témája lesz.

2. Egy házibulira 50 embert hívnak meg. Mindenki egymástól függetlenül 0.5 valószínűséggel megy el. Mi annak a valószínűsége, hogy lesznek vendégek a házibulin? Megoldás: Mint sok egyéb esetben, most is érdemes az esemény be nem következésének a valószínűségét kiszámolni. Ez (\frac{1}{2})^{50}. Így annak valószínűsége, hogy valaki eljön 1 − (\frac{1}{2})^{50}.

3. Egy házibulira 50 embert hívnak meg. Mindenki egymástól függetlenül 0.5 valószínűséggel megy el.

a) Mi annak a valószínűsége, hogy pontosan 3 ember jön el?

b) Mi annak a valószínűsége, hogy Annak, hogy legalább három ember jön el?

Megoldás: a) \binom{50}{3} (\frac{1}{2})^{50}, b) 1 − (1 + \binom{50}{1} + \binom{50}{2}) (\frac{1}{2})^{50}.

4. Valaki játékra hív fel. Egy állítólag szabályos pénzdarabot dob fel egymás után 10 000-szer. Fejdobás esetén ő nyer egy forintot írás dobás estén mi. A dobások eredményeként 5500 fejdobás történt. Mi annak a valószínűsége, hogy egy szabályos pénz feldobása esetén a fejdobások száma legalább 5500?

Megoldás: Ez a valószínűség ∑_{k=5500}^{10000} \binom{10000}{k}2^{−10000}.

Valójában, ezzel a feladat megoldásával nem vagyunk kész. Arra is kiváncsiak vagyunk, hogy ez a szám körülbelül mekkora. Ki tudjuk-e ezt számolni kevés számolással viszonylag rövid idő alatt? Az igazi, minket érdeklő kérdés az, hogy pechünk volt-e, vagy a játékot javasló személy csalt, a pénzdarab nem volt szabályos. Ehhez a kérdéshez később még visszatérünk. Megbeszéltük, hogy az a kérdés, hogy az adott dobássorozat esetén elhisszük-e azt, hogy a pénzdarab szabályos-e a matematikai statisztika egy fontos kérdésének a hipotézésvizsgálatnak speciális esete. Az általános kérdés az, hogy egy elvégzett, a véletlentől is függő kisérletsorozat alapján elfogadjuk-e, hogy egy adott feltételezés (hipotézis) helyes. Ha a hipotézis érvényes és mi mégis elvetjük azt nevezzük első fajú hibának. Ha a hipotézis nem teljesül és mi mégis igaznak fogadjuk el, azt másodfajú hibának nevezzük. Azt a feladatot szokták vizsgálni, hogy megengedve előirt elsőfajú hibát (ezt általában 0.05 vagy 0.01-nek szokás választani) hogyan tudjuk a másodfajú hibát minimalizálni. Megjegyeztük azt is, hogy a valószínűségszámítás egyik alapvető eredménye a centrális határeloszlástétel segítségével meg lehet határozni egyszerűen az ebben a feladatban tekintett valószínűség jó közelítő értékét. Ennek alapján a fenti, a negyedik feladatban szereplő esemény bekövetkezése szabályos pénzdarab esetében rendkivül valószínűtlen.

5. Egy gyakorlatra véletlenszerűen 24 hallgató jön el. Mi annak a valószínűsége, hogy van közöttük két ember, akiknek ugyanazon a napon van a születésnapjuk? Megoldás: Számítsuk ki annak a valószínűségét, hogy nincs két ilyen ember. Képzeljük el, hogy egymásután megjelennek a hallgatók, valaki felírja a születésnapjukat, és minden egyes lépésben más dátumot ír fel. Az első hallgató megjelenésekor biztos, hogy új számot ír fel, a második hallgató megjelenésekor (1 − \frac{1}{365}), a harmadik hallgató megjelenésekor, (feltéve, hogy az első két hallgató esetében különböző számokat írt fel (1 − \frac{2}{365}), a negyedik hallgató esetében (1 − \frac{3}{365}) valószínűséggel írt fel különböző számokat, és így tovább. Annak a valószínűsége, hogy

mind a 24 esetben különböző számokat írt fel ∏_{k=1}^{23} (1 − \frac{k}{365}), a keresett valószínűség

pedig 1 − ∏_{k=1}^{23} (1 − \frac{k}{365}).

Kiváncsiak lehetünk, hogy ez a szám mekkora. Nagyon kicsi vagy nagyon nagy, azaz majdnem 1. Meg tudjuk-e ezt határozni viszonylag kevés számolással? A következő számolás tanulságos lehet. A vizsgálandó szorzatot felírhatjuk mint

1 − ∏_{k=1}^{23} (1 − \frac{k}{365}) = 1 − exp \{ ∑_{k=1}^{23} log (1 − \frac{k}{365})\} .

Használjuk fel a log(1 + x) ∼ x kis x számokra való közelítést. Ez azt sugallja, hogy log (1 − \frac{k}{365}) ∼ −\frac{k}{365}, és a vizsgált valószínűség közelítőleg

1 − exp \{− ∑_{k=1}^{23} \frac{k}{365}\} = 1 − exp \{−\frac{12 · 23}{365}\} = 1 − e^{−276/365}.

6. Egy szabályos dobókockát sokszor feldobunk egymás után. Mi annak a valószínűsége, hogy a 17. dobásban jelenik meg a 3. hatos? Megoldás: Ez azt jelenti, hogy az első 16 dobásban pontosan két hatos jelenik meg, a 17. dobás eredménye pedig szintén hatos. Ennek valószínűsége \binom{16}{2} (\frac{5}{6})^{14} (\frac{1}{6})^{3}.

Házi feladat: Egy szabályos dobókockát feldobunk egymás után többször. Mi annak a valószínűsége, hogy a 20. dobásban jelenik meg az ötödik hárommal osztható szám?