-
創造集
鎖定
- 中文名
- 創造集
- 外文名
- creative set
- 所屬學科
- 數學
- 別 名
- 能行非遞歸集
- 所屬問題
- 數理邏輯(遞歸論)
- 定 義
- 餘集為產生集的re集
創造集定義
定義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是創造集。