可归约性

如果存在一个一对一的递归函数 ，使得对于每个 ，一个整数集合 被称为一对一可归约到集合 () ，则称集合A一对一可归约到集合B。

(1)

并且

(2)

类似地，如果存在一个递归函数 ，使得对于每个 ，一个整数集合 被称为多对一可归约到集合 () ，则称集合A多对一可归约到集合B。

(3)

并且

(4)

这里，这两个可归约关系都具有自反性和传递性。

一对一可归约性蕴含多对一可归约性。任何可归约到递归集合的集合本身也是递归的。任何可归约到递归可枚举集合的集合本身也是递归可枚举的。上述事实常用于通过归约到非递归集合来完成递归不可判定性证明。

如果两个集合彼此一对一/多对一可归约，则称它们是一对一/多对一等价的。一对一等价、多对一等价和递归同构都是等价关系。

如果集合 和 是递归同构的，那么它们是一对一等价的，反之亦然。

如果一个等价集合的类（也称为度）包含一个递归集合，那么该等价类中的所有集合都是递归的。如果一个类（度）包含一个递归可枚举集合，那么该等价类中的所有集合都是递归可枚举的。

存在一个最大度，所有其他递归可枚举集合的度都可以一对一地归约到该最大度。多对一可归约性也是如此。来自这两个最大度中的每一个的集合都称为完备集。例如，所有使得 收敛的 的集合属于一对一和多对一可归约性的最大度，其中 表示一个递归函数，其哥德尔数为 。

如果集合 是多对一完备的，那么它也是一对一完备的，反之亦然。

尽管如此，一对一和多对一可归约性本身在非递归的递归可枚举集合上并不重合。存在非递归的递归可枚举集合，它们不是完备的。

请注意，在递归函数理论中还定义和研究了其他一些可归约性的概念。