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.