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).
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é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.