Sorolhatóak

Sorolhatóak, vagy angolul enumerable/listable, kifejezés a halmazelméletben és a számítástudományban arra utal, hogy egy halmaz elemei egy véges vagy végtelen sorozatként rendezhetők vagyis indexelhetők a természetes számokkal. Magyarul gyakran a halmaz “sorolható” vagy “sorolható halmaz” kifejezést használják.

Definíció szerint egy halmaz A sorolható, ha létezik olyan bijekció A és B között, ahol B egy részhalmaza a természetes számoknak (B lehet véges vagy végtelen). Ekvivalens megfogalmazás: létezik surjektív függvény s: N → A. Gyakorlatban ez azt jelenti, hogy A elemei felsorolhatók egy sorozatként, például A = {a1, a2, a3, ...}, akár véges, akár végtelen. Finomabb értelemben a véges eset egyszerű, a végtelen eset pedig a számolható halmazok fogalmát fedi le.

Példák: A véges halmazok sorolhatóak, például {1, 2, 3}. A természetes számok N, a egész számok Z, és a racionális számok Q mind sorolható halmazok. A valós számok R azonban nem sorolható (countable); Cantor-diagonalis érvelés bizonyítja, hogy nincs bijekció N és R között, ezért R uncountable.

Kapcsolódó fogalmak közé tartozik a rekurzívan sorolható (recursively enumerable) halmazok fogalma, amely a számítógépes elméletben azt írja le, miként listázhatók ki hatékonyan számítógéppel. A sorolhatóság alapvető kategória a halmazok mennyiségi leírásában, és összekapcsolódik a finiteness, a számolhatóság és az uncountability témáival.