下標集((index set)由一些下標構成的遞歸函式集.設{}e } }" E。為部分遞歸函式的能行枚舉，若存在一個部分遞歸函式集了，使A= {xE叫p E=-}}}則稱A為下標集.於是，對下標集A，若它含有某個部分遞歸函式的某個下標，則它也含有該函式的所有的下標.即A為下標集，若且唯若yxy貝xEA邑}P=_}Py}.vEA>.由墊襯引理可知，每個部分函式在下標集中枚舉無窮多次.若A為下標集，則A為空集或是一個無窮集，不僅如此，非平凡的下標集必定不是遞歸的(參見“賴斯定理”).
