مجموعه بازگشتی

مجموعه S از اعداد طبیعی بازگشتی گفته می‌شود اگر تابع شمارش پذیر تام ${\displaystyle f\,}$ وجود داشته باشد به طوری که ${\displaystyle f(x)=1\,}$ if ${\displaystyle x\in S}$ and ${\displaystyle f(x)=0\,}$ if ${\displaystyle x\notin S}$. به بیان دیگر S بازگشتی است اگر و تنها اگر تابع مشخصه ${\displaystyle 1_{S}\,}$ شمارش پذیر باشد.

• مجموعه تهی شمارش پذیر است.
• کل مجموعه اعداد طبیعی شمارش پذیر است.
• هر زیر مجموعه متناهی از اعداد طبیعی شمارش پذیر است.
• اعداد اول شمارش پذیر است.

اگر A یک مجموعه بازگشتی باشد آنگاه مکملش نیز بازگشتی است.

اگر A و B دو مجموعه بازگشتی باشند آنگاه اجتماع و اشتراکشان نیز بازگشتی است.

اگر A و B دو مجموعه بازگشتی باشند آنگاه A*B نیز تحت ضرب جفتی کانتور بازگشتی است.

یک مجموعه بازگشتی است اگر و تنها اگر در سطح ${\displaystyle \Delta _{1}^{0}}$ از سلسله مراتب حسابی باشد.

یک مجموعه بازگشتی است اگر و تنها اگر در دامنه غیر نزولی تابع شمارش کل باشد یا مجموعه تهی باشد.