Felsorolható

Felsorolható egy halmaz. Ezzel a kifejezéssel azt a tulajdonságot szokás leírni, hogy az elemei egy sorrendbe rendezhetők úgy, hogy minden elem szerepel a listában. Formálisan egy A halmazra vonatkozóan ez több equivalens megfogalmazást jelent: létezik injekció f: A → N, vagy ekvivalensen, létezik surjektív f: N → A; ezek a megközelítések ugyanazt a tulajdonságot írják le. Gyakran mondják, hogy A felsorolható vagy számlálható.

A felsorolhatóság több szinonimával is rendelkezik: általában finite vagy countably infinite (számlálható végtelen) halmazokra vonatkozik. Ezenfelül A felsorolható, ha létezik bijekció A és egy részhalmaza a természetes számoknak; vagyis A rendezhető úgy, hogy a termék listában minden eleme egyszer szerepel. Bármely részhalmaza is felsorolható, ha a kiinduló halmaz felsorolható.

Példák és nempélda. A természetes számok N, a zárt egész számok Z, a racionális számok Q minden eleme felsorolható. A véges szavak halmaza egy adottAlphabetumban szintén felsorolható. Az algebrai számok halmaza és a számítható valós számok halmaza is felsorolható. Kevésbé intuitív példaként említhető, hogy a valós számok halmaza nem felsorolható, azaz nem ekvivalens a N tömbjével.

Kapcsolódó fogalmak. A halmazok felsorolhatóságát gyakran a számosság kategóriájaként használják, összevetve a véges és a végtelen, de konkrétan uncountable és countable körébe sorolva. A számítástudományban a rekurzíven felsorolható (rekurzíve r.e.) halmazok egy speciális, hatékonyan felismerhető cenrumot képeznek, ahol az enumeráció computable módon végrehajtható.