產生集(productive set)是一種非re集。若集合A不是re的，則A的任何re子集We一定是A的真子集，從而有a∈A-We 。若這種a可以由e能行地求出，即若存在遞歸函式f，使ᗄx∈ω(Wx⊆A→f(x)∈A-Wx)，則稱A為產生集。而函式f稱為A的產生函式。
基本介紹
- 中文名：產生集
- 外文名：productive set
- 領域：數學
- 學科：集合論
- 性質：一種非re集
- 函式：產生函式
概念,集合,遞歸可枚舉集,遞歸函式,
概念
產生集(productive set)是一種非re集。若集合A不是re的，則A的任何re子集We一定是A的真子集，從而有a∈A-We。若這種a可以由e能行地求出，即若存在遞歸函式f，使ᗄx∈ω(Wx⊆A→f(x)∈A-Wx)，則稱A為產生集。而函式f稱為A的產生函式。集合K-={x|φx(x)↑}是一個產生集，且其產生函式為麼函式。任何產生集A都有一個一一遞歸的產生函式。另外，若存在部分遞歸函式φ，使ᗄx∈ω(Wx⊆A→φ(x)↓& φ(x)∈A-Wx)，則A一定也是產生集。此時φ稱為A的(部分)產生函式。
產生集不僅存在，而且很多。若A為非平凡的下標集，並含有空函式的下標，則A一定是產生集。另外，若A是產生集，則滿足A≤mB的任何集合B也都是產生集。產生集有 2N。不僅如此，對產生集A來說，
及
都是產生集，這種其本身和補集都是產生集的集合稱雙產生集。產生集還有一個重要性質：任何產生集都含有無窮的re子集。因此，產生集一定不是禁集。
集合
集合是現代數學的一個重要的基本概念。當我們把一組確定的事物作為整體來考察時，這一整體就叫做集合。
例如，(1)從1到10這10個自然數的全體；(2)小於100的所有質數的全體；(3)全體自然數；(4)一個班所有學生這一整體；(5)世界上所有國家組成的一個整體；等等，它們都是集合的例子。
上述例子可以看出，它們都是分別由不同的對象組成的一個整體，它們的特點是有確定的對象和具有一定的範圍。所以集合這個概念可以用以下的語言來描述：
集合是具有一定範圍的、確定的對象的全體。集合也簡稱為集。
在數學中，集合是一個不加定義的“原始概念”。這就是說，不能用比它更原始的概念去定義它。因此，集合在數學中被作為原始的最基本的概念來定義其它數學概念。集合是數學概念的出發點。
集合概念具有以下一些屬性：
(1)集合指的是一類事物的整體，而不是指其中的個別事物。
(2)集合中的任一對象具有確定性，即對於任何事物，可以通過某種法則確定其是否屬於某集合，或不屬於某集合，二者必居其一。(應指出，不具有這條屬性的，界限不清的集合是模糊集合。我們這裡所說的集合不是模糊集合，而是普通集合。)
(3)在一般情況下，約定一個集合中的各個對象是互不相同的。凡一個集合中所有相同的對象均應合併起來成為一個對象。例如，由1，1，2，2四個數組成的集合，應變成由1，2兩個數組成的集合。
(4)在一般情況下，集合只與組成它的成員有關，而與它的成員的順序無關。如由1，2，3，4組成的集合與由2，1，4，3組成的集合是同一個集合。
(5)一個集合不必由同一類事物作為它的對象。例如，由2， 3，a，b可以組成一個集合。
集合一般用大寫字母A，B，C，…表示。
遞歸可枚舉集
一種自然數集合。設A為一個自然數集合，若存在一個能行過程把A的所有元素能行地列舉出來，則稱A為遞歸可枚舉的。等價地，A為re集，若且唯若A=∅，或存在遞歸函式f，使A=rang (f)。在後一種情形，f稱為A的枚舉函式。若A是re集，則對n∈A，總可以在有限步內能行地判定。因為只要用A的枚舉函式f能行地枚舉出f(0)，f(1)，f(2)，…，必定會有某個m，使f(m)=n.從這個意義上說，re集只具有半可判定性。
亦稱“半可計算集”、“半可判定集”。簡稱re集。能行性理論的基本概念之一。設A是自然數集的一個子集，如果存在一個遞歸函式f(x)使得A是f(x)的值域或A是空集，就稱A是遞歸可枚舉集。換言之，當A是非空的遞歸可枚舉集時，A中的元素可以通過遞歸函式f一個一個地枚舉出來，使得f(0)，f(1)，f(2)，……成為A中一切元素的一個序列，這裡需要注意的是這個序列中的對象可能有重複，另外f(x)也不一定是單調函式。遞歸可枚舉集有多種彼此等價的定義方法。設A是自然數集的一個子集，則下列條件等價：
(1) A是遞歸可枚舉集；
(2) A是某一個部分遞歸函式的值域；
(3) A是某一個部分遞歸函式的定義域；
(4) A的部分特徵函式是部分遞歸函式；
(5) A是某一個原始遞歸函式的值域；
(6) A是空集或某一個遞歸函式的值域。
對於n元自然數組集合A，即A⊆N(N是自然數集)，也可類似地定義遞歸可枚舉性。用遞歸可枚舉性可定義遞歸性：集合A是遞歸集合若且唯若A及Ᾱ(A的余集)皆為遞歸可枚舉集。遞歸集都是遞歸可枚舉的，但是反之不然，存在某些遞歸可枚舉集並不是遞歸集。
遞歸函式
函式的概念是一個很一般的概念。在定義函式時，不一定要具體給出通過自變數求函式值的方法。因此，可將函式分成兩類，一類是所謂能行可計算函式，另一類是非能行可計算的函式。這前一種函式無論在理論上或在實際上都是非常重要的，因此人們便試圖給它們以精確的數學刻畫。遞歸函式便是許多這種刻畫中的一種。
我們以下考慮的函式都是從自然數到自然數的函式。
我們先定義幾個初等函式：
(1)零函式 Z(x)=0；
(2)後繼函式 S(x)=x+1；
(3)廣義麼函式 U1n(x1,…,xn)=xi；
顯然，上面這些函式都是能行可計算的。
再介紹幾個將函式變換為函式的運算元。
(1)複合運算元 設f是n元函式，g1…gn是m元函式，複合運算元將f，g1…gn變換成為如下的m元函式h：
h(x1,…,xm)=f1g1(x1,…,xm),…,gn(x1,…,xm))
(2)遞歸運算元 設f是n元函式 (≥0)，g是n+2元函式，遞歸運算元將f，g變換成滿足下列條件的h+1元函式h：
h(x1,…,xn,0)=f(x1,…,xn)；h(x1,…xn,,y+1)=g(x1,…xn,y，h(x1,…,xn))
(3)μ一運算元，設f是n+1元函式，如果存在y，使f(x1,…xn,y)=0，我們以μyf(x1…xny)表示這樣的y中的最小者，如果使f(x1,…,xny)=0的y不存在，我們說μyf(x1,…,xny)無定義。μ-運算元將n+1元函式f變換成下面的幾元函式h
h(x1,…,xn)=μyf(x1,…,xny)
注意，μ運算元可以將一個全函式變換成一個部分函式(即在自然數的某個子集上有定義的函式)。
可以看出，上述所有運算元都是將能行可計算函式變換為能行可計算函式。
所謂遞歸函式類便是包含零函式、廣義麼函式，並在複合運算元、遞歸運算元，μ-運算元下封閒的最小函式類。
容易相信，任何遞歸函式都是能行可計算的。反過來，是否存在直觀上能行可計算的，但不是遞歸的函式呢?人們直到現在還沒有發現這樣的函式。相反，人們證明了，現已遇到的直觀上能行可計算的函式都是遞歸函式。進一步，人們還證明了，遞歸函式類與其他的一些刻畫能行可計算函式的方法產生的函式類是完全一致的，這些事實促使車爾赤(Church)提出了他的著名的論點：
遞歸函式類與直觀能行可計算函式類是重合的。
這個論點已被大多數遞歸論學者所接受。
