Megszámlálhatóan végtelen halmazok

Definíció: H megszámlálhatóan végtelen ha párbaállítható a természetes számok halmazával.

Jelölés: A megszámlálhatóan végtelen számosság jelölése 0-val indexelt héber ábc elsõ betûje (olvasata: alefnull).

 
 
A megszámlálhatóan végtelen halmazok tualjdonságai
 

Tétel: A természetes számok egyike sem állítható párba a természetes számok halmazával.

Megjegyzés: Azaz a természetes számok halmaza végtelen.

Definíció: Egy halmaz megszámlálható, ha véges vagy megszámlálhatóan végtelen.

Lemma: (i) Megszámlálhatóan végtelen halmaz részhalmaza megszámlálhatóan végtelen vagy véges (azaz megszámlálható).
(ii) Megszámlálható halmaz részhalmaza is megszámlálható.

Lemma: Egy H végtelen halmaznak van megszámlálhatóan végtelen részhalmaza.

Megjegyzés: (a) Azaz valamilyen (a késõbbiekben pontosan megfogalmazandó) értelmeben a megszámlálahatóan végtelen számosság a legkisebb végtelen számosság.
(b) A fenti lemma természetes megfordítható, így a végtelen halmazok egy jellemzését adja.

Lemma: H akkor és csak akkor nem üres megszámlálható halmaz, ha van a természetes sza'mokon értelmezett H-értékû ráképezés.

Megjegyzés: Azaz a megszámlálható halmazok pontosan azok a halmazok, amleyek elõállnak mint egy sorozat által felvett értékek halmaza. Azaz egy megszámlálható halmaz elemei esetleges ismétléssel sorozatba rendezhetõk.

 
 
Példák megszámlálhatóan végtelen halmazokra és további tulajdonságok
 

Példa: Az egész számok halmaza megszámlálhatóan végtelen.

Példa: A természetes számokból képzett rendezett párok halmaza megszámlálhatóan végtelen.

Példa: A természetes számokból képzett rendezett n-esek (n egy természetes szám) halmaza megszámlálhatóan végtelen.

Példa: A racionális számok halmaza megszámlálhatóan végtelen.

Lemma: (i) Megszámlálható sok megszámlálható halmaz uniója megszámlálható.
(ii) Megszámlálhatóan sok megszámlálható halmaz uniója akkor és csak akkor megszámlálhatóan végtelen, ha valamelyik megszámlálhatóan végtelen vagy végtelen sok nem üres halmaz van közöttük.

Példa: A természetes számok véges részhalmazai halmazának számossága megszámlálhatóan végtelen.

Példa: Az egész együtthatós polinomok halmaza megszámlálhatóan végtelen.

Példa: Az algebrai számok halmaza megszámlálhatóan végtelen.