又稱部分遞迴集。在能行性理論中，基本概念是遞迴函數，它可刻畫為：任給x，隻要它在x處有定義必可在有限步驟內求出其值。因此遞迴全函數（即處處有定義的）必可在有限步驟內求出它的任一值，至於遞迴部分函數（未必處處有定義的）則隻要求有定義處可求出其值，但不要求能夠在有限步驟內判定它的定義域的元素，即對任給的x判定x是否屬於函數的定義義域。
設有一集合A與一函數α(x)，如果α(x)=0當且僅當x∈A，則α(x)叫做A的特征部分函數，如果還有α(x)=1，當且僅當x∉A，則α（x）叫做A的特征全函數，簡稱特征函數。如果一集合A的特征部分函數（也是特征函數）是遞歸全函數，則A叫做遞歸集；如果一集A的特征部分函數是遞歸部分函數，則A叫做部分遞歸集；部分遞歸集又可定義為某個遞歸部分函數的定義域。顯然，A為遞歸集當且僅當：任給x，x屬於A與否，恒可在有限步內判定；A為部分遞歸集當且僅當：任給x，如果x∈A，則必可在有限步內判定，但如果x∉A，可能永遠不知道這件事（除非從別的途徑）。因此有下列結果：
①如果A為遞歸集，則A為部分遞歸集；
②A為遞歸集當且僅當A的補集亦為遞歸集；
③A為遞歸集當且僅當A與它的補集都是部分遞歸集。
最後一點可看出：如果x∈A，因A為部分遞歸集必可在有限步內看出；如果x∉A，因A的補集為部分遞歸集亦可在有限步內看出，從而A必為遞歸集。
遞歸可枚舉集是指它是某個一般遞歸函數（即遞歸全函數）f(x)的值域。因為遞歸全函數f(x)的每一個值都可在有限步內算出，可以逐步地計算f（0），f（1），f(2)，…，從而得出遞歸可枚舉集的所有元素。這便是遞歸可枚舉集名稱的來源。f（x）叫做該集的枚舉函數，可能有兩值f(α)與f(b)是相等的，即容許重復枚舉。如果f(x)是不減函數或(嚴格)遞增函數，便叫做不減枚舉或（嚴格）遞增枚舉。
顯然，如果x在一個遞歸可枚舉集A內，必可在有限步內判定（隻須依次計算f(0)，f(1)，…，便可）；但如果x不在A內，而A又不是嚴格遞增枚舉，則很可能人們永遠也不知道這事。根據上述部分遞歸集的特性，可知遞歸可枚舉集都是部分遞歸集。反之，如果A為部分遞歸集，命其特征部分函數為α(x)，當A為空集時，它當然不是任何遞歸全函數的值域，當A非空集時，則在第一階段對α(0)，α(1)各計算1步，第二階段對α(0)，α(1)，α(2)各計算2步，…，第n階段對α(0)，α(1)，α(2)，…，α(n)各計算n步，…，並把首先出現的α(x)=0的根取為f(0)，以後在每一階段之末均把在該階段時所已知的α(x)=0的根取為f在新主目處的值，f必為遞歸全函數，而且A的元素恰巧便是f(0)，f(1)，…的值。可見非空的部分遞歸集必是遞歸可枚舉集。一般還把空集也算作遞歸可枚舉集，這樣兩種集便一致起來瞭。
可以證明，A為遞歸可枚舉集當且僅當它是某個原始遞歸函數的值域，又當且僅當它是某個初等函數的值域。另一方面，A為遞歸可枚舉當且僅當它是某個遞歸部分函數的值域，隻須仿照上法，在第n階段計算f(0)，f(1)，…，f(n)各n步，便可把遞歸部分函數的值全部都枚舉出來瞭。
已有辦法把全體遞歸部分函數全部枚舉起來，因此也可以把它們的定義域或值域全部枚舉起來。設把第x個遞歸部分函數的定義域（值域）記為Wx，則Wx便是全體部分遞歸集（遞歸可枚舉集）的枚舉（註意其中是有重復的）。如命K={x：x∈Wx}（即如果x恰巧在第x個部分遞歸集之內，便把x作為K的元素），則K是一個遞歸可枚舉集但不是遞歸集，從而K的補集既不是遞歸集又不是遞歸可枚舉集。這是人們作出的第一個不是遞歸可枚舉集的例子，它也是一個很重要的集，對它已有充分的研究。
此外，如果f為遞歸部分函數，A為遞歸可枚舉，則f-1(A)也是遞歸可枚舉集。
著名的希爾伯特第10問題是：有沒有一個能行方法，可決定任給的一個不定方程
是否有整數解?這裡
P、
Q是兩個具有整系數的多項式。這個問題到1970年已經被否定地解決瞭，即如果把“能行方法”理解為“用計算遞歸全函數的方法”，那末可以證明：這個能行方法是沒有的。因為任何一個部分遞歸集（遞歸可枚舉集）
A，都有兩個帶整系數的多項式
P、
Q，使得
特別是當
A即集合
K時，也可找出相應的兩個多項式
P、
Q。既然
K不是遞歸的，
x屬於
K與否是不能遞歸地判定的，那末對於“什麼樣的
x能夠使
有解”的問題，也就不能遞歸地判定瞭。
上面關於集合的討論可以推廣到n元關系去。就n元關系R(x1，x2，…，xn)而言，如果R(x1，x2，…，xn)成立當且僅當
，則
f(
x
1，
x
2，…，
x
n)叫做
R(
x
1，
x
2，…，
x
n) 的特征部分函數，如果還要求：
R(
x
1，
x
2，…，
x
n)不成立當且僅當
，則
f叫做
R的特征全函數，簡稱特征函數。如果關系
R(
x
1，
x
2，…，
x
n)的特征部分函數(也是特征函數)是一個遞歸全函數，則
R叫做遞歸關系；如果
R(
x
1，
x
2，…，
x
n)的特征部分函數是遞歸部分函數，則
R叫做部分遞歸關系。有瞭這些定義以後，以上的討論完全可以推廣到遞歸關系與部分遞歸關系方面來。當然，由於函數的值是一個數而不是
n元向量，所以“遞歸可枚舉關系”不能定義為某個遞歸全函數的值域而隻能定義為部分遞歸關系。
但是對遞歸關系而論，有下列的結果，這是討論遞歸時所沒有的。
①R(x1，x2，…，xn)為部分遞歸關系當且僅當有一個n+1元遞歸關系或部分遞歸關系W使得
。
②R(x1，x2，…，xn)為部分遞歸關系當且僅當有一個n+m元遞歸或部分遞歸關系W使得
。
③A為部分遞歸集當且僅當有一個二元遞歸或部分遞歸關系W使得
。