回歸集

回歸集(regressive set) re集的一種推廣。

基本介紹

• 中文名：回歸集
• 外文名：regressive set

.設A為自然數集合，A=}ao}a,}az,"..}為A的一種無重複枚舉.若存在部分遞歸函式獷，使得抓ao) -ao乙t/nEm抓an+a=a,.)，則稱A為關於這種枚舉的由筍回歸的集合，並稱筍為A的回歸函式.若存在A的一種無重複枚舉和一個部分遞歸函式獷，使得A為關於該枚舉由滬回歸的，則稱A為回歸集.德克爾( Dekker , J.)和邁希爾(Myhill, J.)證明了:若A為r。集，則A一定是回歸集.反之，若A是回歸集，則A必定是re集或禁集.另外，阿佩爾(Appel , K. I. )馬克勞林(Mclaughlin,T. G.)證明了:若A,A都是回歸集，則A和A中至少有一個是re集.

注意到若A是r。集，則一定存在一種(能行的)無重複枚舉A- {ao,aa2,... }，並且總存在部分遞歸函式獷，使t/ n任。(抓an) = an+i).集合的回歸性是由遞歸可枚舉性導出的一個概念.