可歸約性

如果存在一個一對一的遞迴函式 ，使得對於每個 ，一個整數集合 被稱為一對一可歸約到集合 () ，則稱集合A一對一可歸約到集合B。

(1)

並且

(2)

類似地，如果存在一個遞迴函式 ，使得對於每個 ，一個整數集合 被稱為多對一可歸約到集合 () ，則稱集合A多對一可歸約到集合B。

(3)

並且

(4)

這裡，這兩個可歸約關係都具有自反性和傳遞性。

一對一可歸約性蘊含多對一可歸約性。任何可歸約到遞迴集合的集合本身也是遞迴的。任何可歸約到遞迴可列舉集合的集合本身也是遞迴可列舉的。上述事實常用於透過歸約到非遞迴集合來完成遞迴不可判定性證明。

如果兩個集合彼此一對一/多對一可歸約，則稱它們是一對一/多對一等價的。一對一等價、多對一等價和遞迴同構都是等價關係。

如果集合 和 是遞迴同構的，那麼它們是一對一等價的，反之亦然。

如果一個等價集合的類（也稱為度）包含一個遞迴集合，那麼該等價類中的所有集合都是遞迴的。如果一個類（度）包含一個遞迴可列舉集合，那麼該等價類中的所有集合都是遞迴可列舉的。

存在一個最大度，所有其他遞迴可列舉集合的度都可以一對一地歸約到該最大度。多對一可歸約性也是如此。來自這兩個最大度中的每一個的集合都稱為完備集。例如，所有使得 收斂的 的集合屬於一對一和多對一可歸約性的最大度，其中 表示一個遞迴函式，其哥德爾數為 。

如果集合 是多對一完備的，那麼它也是一對一完備的，反之亦然。

儘管如此，一對一和多對一可歸約性本身在非遞迴的遞迴可列舉集合上並不重合。存在非遞迴的遞迴可列舉集合，它們不是完備的。

請注意，在遞迴函數理論中還定義和研究了其他一些可歸約性的概念。