递归集合

自然数的子集 S 被称为递归的，如果存在一个全可计算函数

${\displaystyle f:S\to \mathbb {N} }$ 

使得

${\displaystyle f(x)=\left\{{\begin{matrix}0&{\mbox{if}}\ x\in S\\\neq 0&{\mbox{if}}\ x\notin S\end{matrix}}\right.}$ 

换句话说，集合 S 是递归的，当且仅当指示函数 ${\displaystyle 1_{S}}$  是可计算的。

• 空集
• 自然数
• 自然数的所有有限子集（有限子集并非可数子集，后者可能有无限多的元素）
• 素数的集合
• 递归语言是在形式语言字母表之上所有可能词的集合中的递归集合。

如果${\displaystyle A}$ 是递归集合，则${\displaystyle A}$ 的补集是递归集合。 如果${\displaystyle A}$ 和${\displaystyle B}$ 是递归集合，则${\displaystyle A\cap B}$ 、${\displaystyle A\cup B}$ 和${\displaystyle A\times B}$  是递归集合。集合${\displaystyle A}$ 是递归集合，当且仅当${\displaystyle A}$ 和${\displaystyle A}$ 的补集是递归可枚举集合。一个递归集合在全可计算函数下的原像（preimage）是递归集合。

• 递归可枚举集合
• 递归函数