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