4.2 Megszámlálható halmazok

Halmazokkal kapcsolatban további fontos kérdés a halmazok elemszáma. A részletes tárgyalás előtt tekintsünk át néhány alapfogalmat.

Véges halmaz: Azt mondjuk, hogy egy A halmaz véges (azaz a halmaz elemeinek száma véges), ha valamely természetes számra létezik bijektív leképezés - beleértve az üres halmazt is n=0 esetén -, azaz az A halmaz elemeinek száma pontosan n. Az A véges halmaz elemszámát |A|-val jelöljük.

Egyenlő számosságú halmazok: Az A és B halmaz számossága egyenlő, ha létezik bijektív leképezés.

A természetes számok halmaza végtelen sok elemet tartalmaz. Ezt a számosságot megszámlálhatóan végtelen számosságnak nevezzük, és a véges halmazoknál használt jelölést használjuk, azaz a természetes számok halmazának számosságát jelöli.

Megjegyzés.

A megszámlálhatóan végtelen halmazok számosságának jelölésére szokás az - ejtsd: alef null - szimbólumot használni.

Ezek után már definiálható a megszámlálhatóan végtelen (számosságú) halmaz: Azt mondjuk, hogy az A halmaz (számossága) megszámlálhatóan végtelen, ha létezik bijektív leképezés, ahol a természetes számok halmaza.

Megszámlálható halmazok: A véges és a megszámlálhatóan végtelen számosságú halmazokat szokás együtt megszámlálható halmazoknak nevezni.

Megjegyzés.

Ha az A halmaz megszámlálhatóan végtelen, akkor létezik kölcsönösen egyértelmű megfeleltetés az A halmaz és a természetes számok között, azaz A elemei sorbarendezhetők.

Könnyen bebizonyítható, hogy ha véges sok elemet elhagyunk egy végtelen számosságú halmazból, akkor az így kapott halmaz még mindig végtelen számosságú marad.

Ezért a pozitív természetes számok halmaza is megszámlálhatóan végtelen, mert ekkor csak egy elemet veszünk ki a halmazból, a nullát.

Következmény.

Ha létezik bijekció, akkor A megszámlálhatóan végtelen számosságú halmaz, és elemei sorbarendezhetők.

Tétel 4.1: Megszámlálható és véges halmaz egyesítésével nyert halmaz is megszámlálható.

Bizonyítás:

Azt kell belátni, hogy az elemek sorba rendezhetők.

Legyen és , ahol , ekkor .

Ennél az elrendezésnél jól látszik, hogy a sorbarendezés megoldható.

Tétel 4.2: Egy megszámlálható halmaz bármely végtelen részhalmaza szintén megszámlálható.

Felmerülhet a kérdés, hogy az előző fejezetben tárgyalt számhalmazoknak mi a számossága, valamint vizsgálhatjuk további halmazok számosságát.

Tekintsük például a páros természetes számok halmazát. Ha azt akarjuk bizonyítani, hogy a halmaz megszámlálható számoságú, akkor egy bijektív leképezést kell találni a halmaz és a természetes számok halmaza között, ami könnyen konstruálható:

Ebből az következik, hogy a természetes számok és a páros természetes számok halmaza megszámlálhatóan végtelen számosságú.

Megjegyzés.

Azt kaptuk, hogy egy A halmaz valódi részhalmazának számossága megegyezik az A halmaz számosságával, ami elsőre egy kicsit furcsa lehet. Következésképp végtelen halmazok számosságánál a több, kevesebb vagy az ugyanannyi kifejezésnek nincs értelme.

Megjegyzés.

Az egész számok halmaza is megszámlálható, azaz bijektív leképezés. Definiáljuk φ-t a következő képen:

, azaz a nemnegatív egész számokhoz hozzárendeljük a páros természetes számokat, a negatív egész számokhoz pedig a páratlan természetes számokat.

Következmény.

, azaz az egész számok és a természetes számok számossága azonos.

Az eddigi eredmények általánosíthatók, mely általánosítások tételek formájában a következők:

Tétel 4.3: Két megszámlálható halmaz egyesítésével kapott halmaz szintén megszámlálható.

Tétel 4.4: Megszámlálhatóan végtelen sok megszámlálható halmaz egyesítésével kapott halmaz is megszámlálható.

Következmény.

A racionális számok halmaza megszámlálható, azaz . Ez azt jelenti, hogy a racionális számok számossága megegyezik a természetes számok számosságával.

Megjegyzés.

Az előző következmény alapján a racionális számok sorbarendezhetők.

Megjegyzés.

Az előzőekben csak megszámlálhatóan végtelen halmazokat definiáltunk, illetve néhány példát néztünk megszámlálhatóan végtelen halmazra. Definiálható azonban általánosan is a végtelen számosságú halmazok fogalma.

Végtelen számosságú halmaznak nevezünk egy A halmazt, ha halmaz, amelyre és létezik bijektív leképezés, azaz az A halmaznak létezik önmagával egyenlő számosságú valódi részhalmaza.