oplijstbaar

Oplijstbaar is een term uit de wiskunde en informatica die wordt gebruikt voor verzamelingen waarvan de elementen in een opeenvolgende lijst kunnen worden gezet. In het algemeen betekent oplijstbaarheid dat er een manier is om alle elementen van de verzameling op te sommen in een lijst, eventueel met herhalingen.

Formeel kan een verzameling S oplijstbaar genoemd worden als er een surjectie f: N -> S bestaat. Dat betekent dat elk element van S in de lijst voorkomt, hoewel sommige elementen mogelijk meerdere keren worden genoemd. Een eindige verzameling is altijd oplijstbaar. Een oneindige verzameling is oplijstbaar als ze telbaar is, wat inhoudt dat er een bijectie bestaat tussen S en een deelverzameling van de natuurlijke getallen.

In de praktijk wordt soms onderscheid gemaakt tussen oplijstbaar met herhaling (alle elementen komen voor in een oneindige lijst) en oplijstbaar zonder herhaling (elk element precies één keer wordt genoemd, wat een bijectie met een subset van N impliceert). Verzamelingen die niet oplijstbaar zijn, noemen we in de meeste wiskundige context niet-telbaar. Een beroemde voorbeeld is de verzameling van de reële getallen, die niet oplijstbaar is zodat er geen lijst bestaat waarin elk reëel getal precies één keer voorkomt.

In informatica en logica speelt oplijstbaarheid een rol bij lijsten, enumeraties en generering door algoritmen. Een oplijstbare verzameling kan in principe stap voor stap worden gegenereerd, wat relevant is voor programmatologie, automatische verificatie en learnbare modellen.

Zie ook: tellelk, telbare verzamelingen, enumeratie, Cantor-diagonaliteit.