Recursieve verzameling
Een deelverzameling van de natuurlijke getallen wordt recursief, ook berekenbaar of beslisbaar genoemd, als er een algoritme bestaat dat in eindige tijd kan bepalen of een getal tot de verzameling behoort.

Definitie
Een deelverzameling  van de natuurlijke getallen wordt recursief genoemd, als de indicatorfunctie  van  berekenbaar is.

Voorbeelden
 De lege verzameling is recursief.
 De verzameling van de natuurlijke getallen is recursief.
 Elke eindige deelverzameling van de natuurlijke getallen is recursief.
 De verzameling van de even getallen is recursief.
 De verzameling priemgetallen is recursief.

Verzamelingenleer