創造集(creative set)亦稱能行非遞歸集,是余集為產生集的re集。設a為re集,若ā是產生集,則稱a為創造集。例如K={x|φx(x)↓}就是一個創造集。關於創造集的最重要的結果是邁希爾(J.Myhill)證明的:A為創造集,若且唯若A為一一完全的,又若且唯若A為m完全的。若A為創造集,則A既非遞歸集,也非單純集。但是遞歸集、創造集和單純集並沒有窮盡全部的re集,德克爾(J.Dekker)證明了存在一個非遞歸、非單純又非創造集的re集。並稱這種集合為中間集。不僅如此,還證明了任何非遞歸reT度中都有中間集。
基本介紹
- 中文名:創造集
- 外文名:creative set
- 別稱:能行非遞歸集
- 所屬學科:數學
- 所屬問題:數理邏輯(遞歸論)
定義,相關結論,
定義
定義1設
是一個遞歸可枚舉集。若存在遞歸函式
使對任何遞歸可枚舉集
,如果
,
,就說
是創造集。






與創造集緊密聯繫的有另一個概念,即生產集。
定義2給定集合
,若存在遞歸函式
,使當
時,
,就說A是一個生產集,
叫A的生產函式。





生產集當然不是遞歸可枚舉集。
定義3利用生產集的概念,可以重新定義創造集如下:
若A滿足下列條件:
(1) A 是遞歸可枚舉集;
(2)
是生產集,

就說A是創造集。
生產集的特點是從它的任何一個遞歸可枚舉子集出發,可以有效地找出一個更大的遞歸可枚舉子集。
相關結論
定理1 設
為一元遞歸函式的集合,
,如果
是遞歸枚舉集,那么F是創造集。



證明:顯然空函式
,因為不然的話F是生成集,與題設矛盾。因此
,又由定理2,
是生成集,從而F是創造集。證畢。



運用本定理可以很快地判定
等遞歸枚舉集是創造集。

定理2 設
為一元遞歸函式的集合,
,並且至少有一個
,那么
是生成集。




創造集的一個重要性質如下.
定理3 如果A是創造集,那么A的補集
含有一個無窮的遞歸枚舉子集。

定理4 設
,若A是生產集,則B是生產集。

推論 設
,設A是創造集,B是遞歸可枚舉集,則B是創造集。

定理5 若A是單純集,那么A不是創造集。