Megszámlálható halmazok

Egy halmaz megszámlálhatósága a halmaz méretének valamiféle megfelelője, mert végtelen halmazoknál nem lehet az elemek számával számolni, hiszen az elemek száma váratlanul … végtelen. A halmaz méretét számosságnak is nevezzük.

A végtelen halmaz mérete

Egy véges halmaz méretét egyszerű meghatározni: megszámoljuk az elemeit. Tehát az M = {a, b, c, d, e} halmaz mérete 5, felírva |M| = 5.

A végtelen halmazoknál a helyzet jóval bonyolultabb. Hogyan hasonlíthatnánk össze a végtelen halmazok méretét? Egyáltalán lehetséges, vagy minden végtelen halmaz „egyforma nagy”?

Példaként vegyük a pozitív egész számok halmazát (a magyar iskolai szóhasználatban a természetes számok közé a 0 is beletartozik, ezért a 0 nélküli halmaz jelölése ℕ⁺) és a páros pozitív egész számok halmazát. Legyen tehát ℕ⁺ = {1, 2, 3, 4, 5, 6, …} és S = {2, 4, 6, …}. Azt mondanánk, hogy a pozitív egész számok halmaza nagyobb, mint a páros számoké, mert a pozitív egész számok az összes páros számot tartalmazzák, és még néhány további elemet – a páratlan számokat.

Felírhatnánk tehát, hogy S ⊂ ℕ⁺, az S halmaz valódi részhalmaza az ℕ⁺ halmaznak. És mondhatnánk, hogy ha S ⊂ ℕ⁺, akkor az ℕ⁺ halmaz nagyobb – hiszen több elemet tartalmaz, mint az S.

Az egyik ok, amiért a halmazokat nem mérhetjük a részhalmaz-reláció alapján, hogy a halmazok különböző méretűek lehetnek akkor is, ha egyik sem részhalmaza a másiknak. Ezt véges halmazokon is megmutathatjuk: A = {1, 3, 4, 9} és B = {b, u, r, z, m}. Igaz, hogy |A| = 4 és |B| = 5. A B halmaz nagyobb, mint az A, mégsem igaz, hogy A ⊂ B. Végtelen halmazok esetén ezt a páros és a páratlan számokon láthatjuk. Egyik halmaz sem részhalmaza a másiknak.

A részhalmaz-reláció tehát nem ideális jelölt annak eldöntésére, hogy az egyik halmaz nagyobb-e a másiknál.

Bijekció

Próbáljunk ki egy másik megközelítést. Van két halmazunk, A és B. Azt mondhatjuk, hogy ugyanakkora a méretük, ha létezik köztük bijektív leképezés. Mit jelent ez? Azt, hogy veszünk egy elemet az A halmazból, egy elemet a B halmazból, és párt képezünk belőlük: (a; b). Ezeket az elemeket kivesszük a halmazokból, és folytatjuk. Ha mindkét halmazt „ki tudjuk üríteni”, találtunk bijektív leképezést.

Példa véges halmazokon: A = {a, b, c} és B = {1, 2, 3}. Az első pár lehetne (a; 1), a következő (b; 2), végül (c; 3). Mindkét halmaz összes elemét kimerítettük, találtunk bijektív leképezést. Fontos, hogy ez nem az egyetlen bijektív leképezés. Ez is érvényes megoldás: (a; 3), (b; 1), (c; 2).

A végtelen halmazoknál ez már kicsit érdekesebb. Próbáljuk ki a páratlan és a páros pozitív egész számokkal. Ösztönösen érezzük, hogy ugyanannyinak kellene lenniük. Próbáljuk ki. Vesszük az első páratlan számot, és leképezzük az első páros számra: (1; 2). Aztán a második páratlan számot és a második páros számot: (3; 4). És így tovább. Így a következő párokat kapjuk: (1; 2), (3; 4), (5; 6), (7; 8), … Felírhatnánk, hogy minden l páratlan szám az l + 1 páros számra képeződik le, és minden s páros szám az s − 1 páratlan szám képe. Minden páratlan és minden páros számhoz tehát van olyan pár, amely tartalmazza azt a számot. A páratlan és a páros számok halmaza így ugyanakkora.

Páros számok és pozitív egész számok

Most ugyanezzel az eljárással hasonlítsuk össze a pozitív egész számok és a páros számok halmazát. Legyen tehát ℕ⁺ = {1, 2, 3, 4, 5, 6, …} és S = {2, 4, 6, …}. Ösztönösen azt várjuk, hogy a pozitív egész számok halmaza lesz a nagyobb.

Most azonban próbáljuk meg megtalálni a bijektív leképezést. Mondhatjuk, hogy minden n pozitív egész szám a kétszeresére, a 2n-re képeződik le. Így a következő párokat kapjuk: (1; 2), (2; 4), (3; 6), (4; 8), (5; 10), … Minden n pozitív egész számhoz tehát van egy (n; 2n) pár, és minden s páros számhoz van egy (s/2; s) pár. Találtunk bijektív leképezést, a páros számok halmaza és a pozitív egész számok halmaza tehát ugyanakkora, ugyanaz a számosságuk.

Ez zavarosnak tűnhet, mert a pozitív egész számok mégiscsak több elemet tartalmaznak, mint a páros számok. A pozitív egész számok az összes páros számot tartalmazzák, és még az összes páratlan számot is. Mégis meg tudjuk találni a bijekciót, tehát a két halmaz ugyanakkora.

Összehasonlítás a pozitív egész számokkal

A pozitív egész számok valójában a végtelen halmaz legkisebb méretét adják meg. Hogy egy másik halmaz ugyanakkora-e, mint a pozitív egész számok halmaza, gyakran meglehetősen könnyen kideríthető – elég találni egy bijekciót a pozitív egész számokra, ami a gyakorlatban azt jelenti, hogy elég, ha az M halmazunk elemeit meg tudjuk számozni, sorba tudjuk rendezni.

Vagyis ha az elemeket úgy tudjuk sorba állítani, hogy el tudjuk dönteni, melyik az első, melyik a második, a harmadik, a negyedik, a tizedik és így tovább, akkor a halmaz ugyanakkora, mint az ℕ⁺. Az ilyen halmazt megszámlálhatónak nevezzük.

Könnyen látjuk, hogy a páros és a páratlan pozitív egész számok megszámlálhatók, mert meg tudjuk határozni az első, második, harmadik stb. páros/páratlan számot. Mi a helyzet a páros egész számokkal? Vagyis az S = {…, −4, −2, 0, 2, 4, …} halmazzal. Sorba tudjuk őket rendezni? Igen, elég az előző sorrendet venni, és a pozitív páros szám után rögtön felírni a negatív párját is: S = {0, 2, −2, 4, −4, 6, −6, …}. Hasonlóan például az egész számokra.

A racionális számok mérete

Érdekesebb példát jelentenek a racionális számok, a törtek. Sorba tudjuk őket rendezni? Igen, de ez már egy kicsit bonyolultabb. Szerkesztünk egy táblázatot, amelynek végtelen sok sora és oszlopa van. Minden cellában egy tört lesz. Az n-edik oszlopban és az m-edik sorban az n/m tört áll. Tehát az 1. oszlopban és a 2. sorban $\frac{1}{2}$ van, a harmadik oszlopban és a negyedik sorban pedig 3/4.

$$\begin{array}{ccccc}1/1& 2/1& 3/1& 4/1& \dots \\ 1/2& 2/2& 3/2& 4/2& \dots \\ 1/3& 2/3& 3/3& 4/3& \dots \\ 1/4& 2/4& 3/4& 4/4& \dots \\ \dots & \dots & \dots & \dots & \dots \end{array}$$

Hogyan rendezzük sorba, hogyan számozzuk meg ezeket a számokat? Nem számozhatjuk sorokon vagy oszlopokon végig, mert rögtön belefulladnánk az adott sorba vagy oszlopba. Ehelyett az átlók mentén haladunk: (első átló:) 1/1, (második átló:) 2/1, 1/2, (harmadik átló:) 3/1, 2/2, 1/3, (negyedik átló:) 4/1, 3/2, 2/3, 1/4, … Még rengeteg ismétlődő tört van benne, de az nem baj. Ami jobban zavar, hogy nincsenek benne negatív számok. Ezt egyszerűen megoldhatjuk: valahányszor felírunk egy törtet, rögtön utána beszúrjuk a negatív párját. Ekkor már csak a nulla hiányzik az elejéről. És ennyi, az összes racionális számot sorozatba rendeztük.

Összességében tehát ezt a sorozatot kapjuk: 0, 1/1, −1/1, 2/1, −2/1, 1/2, −1/2, 3/1, −3/1, 2/2, −2/2, 1/3, −1/3, …

A valós számok mérete

Ugyanakkorák-e a valós számok, mint a pozitív egész számok? A döntés még bonyolultabb lesz, mint a racionális számoknál. Indirekt bizonyítást végzünk. Tegyük fel, hogy a valós számok megszámlálhatók, és létezik bijektív leképezés a pozitív egész számokra. Tegyük fel tehát, hogy sorba rendezhetők. És tegyük fel, hogy a következő leképezés éppen ez a sorrend:

$$\begin{array}{ccccccccc}0,& 3& 5& 2& 2& 4& 6& 0& \dots \\ 0,& 2& 9& 2& 4& 3& 7& 5& \dots \\ 0,& 7& 2& 3& 0& 8& 4& 5& \dots \\ 0,& 1& 4& 3& 7& 9& 0& 6& \dots \\ 0,& 0& 8& 6& 5& 7& 5& 8& \dots \\ 0,& 7& 5& 4& 6& 3& 6& 3& \dots \\ 0,& 3& 4& 1& 9& 7& 0& 0& \dots \\ \dots \end{array}$$

A táblázatban a sorrendünkben szereplő első hét valós szám látható. Ez a sorrend természetesen tetszőleges lehet, nem kell a számok nagysága szerint rendezettnek lennie.

A feltevés szerint ebben a végtelen táblázatban az összes valós szám sorba van rendezve. (A táblázat itt is végtelen, csak az első hét bejegyzés látható.) Most megpróbálunk találni/szerkeszteni egy olyan számot, amely valós, de nem szerepel ebben a táblázatban. Ha találunk ilyen számot, az ellentmond annak, hogy a táblázatban az összes valós szám benne van, amiből arra következtethetünk, hogy a valós számok halmaza nem megszámlálható.

Azt a számot, amely nincs a táblázatban, így szerkesztjük meg:

$$\begin{array}{ccccccccc}0,& \boxed{\text{3}}& 5& 2& 2& 4& 6& 0& \dots \\ 0,& 2& \boxed{\text{9}}& 2& 4& 3& 7& 5& \dots \\ 0,& 7& 2& \boxed{\text{3}}& 0& 8& 4& 5& \dots \\ 0,& 1& 4& 3& \boxed{\text{7}}& 9& 0& 6& \dots \\ 0,& 0& 8& 6& 5& \boxed{\text{7}}& 5& 8& \dots \\ 0,& 7& 5& 4& 6& 3& \boxed{\text{6}}& 3& \dots \\ 0,& 3& 4& 1& 9& 7& 0& \boxed{\text{0}}& \dots \\ \dots \end{array}$$

Azzal kezdjük, hogy felírjuk: 0,… Az új valós számunk az elején így fog kinézni. Az első tizedesjegyen ezután olyan számjegy áll, amely különbözik a sorrendünk első valós számának első számjegyétől (a táblázatban keretezéssel ki van emelve). Ott a 3 számjegy áll, tehát választhatjuk például az 1-et, és megkapjuk a 0,1… számot.

Folytatjuk. A második helyen olyan számjegy lesz, amely különbözik a második valós szám második számjegyétől. Ott a 9 áll, tehát például a 2. Megkapjuk a 0,12… számot. A harmadik helyen olyan számjegy lesz, amely különbözik a harmadik valós szám harmadik számjegyétől. Ott a 3 áll, tehát választjuk mondjuk a 7-et. Megkapjuk a 0,127… számot.

És így tovább, és így tovább. Az új szám n-edik helyén mindig olyan számjegy áll majd, amely különbözik a sorrendünk n-edik számának n-edik helyén álló számjegyétől.

Mit érünk el ezzel? Olyan számot kapunk, amely a sorrendünk minden számától legalább egy számjegyben különbözik. Vegyük az utolsó ideiglenes eredményt: 0,127… Ez a szám biztosan különbözik a sorrendünk első számától legalább az első számjegyben – mert úgy állítottuk össze. A második számtól legalább a második számjegyben különbözik. A harmadiktól a harmadik számjegyben. Általában ez az új szám a sorrend n-edik helyén álló számtól legalább az n-edik helyen álló számjegyben különbözik.

Az újonnan szerkesztett számot tehát nem találjuk meg a táblázatban, amely a pozitív egész számok és a valós számok közötti bijekciót volt hivatott szimbolizálni. A valós számok tehát többen vannak, mint a pozitív egész számok. A valós számok halmaza nem megszámlálható.

További források

• Are there more odd or even numbers?