递归可枚举集

对于自然数集SN，下面五种说法是彼此等价的，都可以用作递归可枚举集的定义：

(1)S是某个(一元)部分递归函数的定义域；

(2)函数

是部分递归函数；

(3)S是某个部分递归函数f的值域。

(4)S= 或S是某个递归全函数f的值域。

(5)S= 或S是某个原始递归函数的值域。

(4)、(5)表明，对于非空的递归可枚举集S，我们可以用一个递归全函数(甚至是原始递归函数)将S的元素逐一枚举出来：

S=｛f(0)，f(1)，f(2)，…｝．

f称为S的枚举函数。一个非空的递归可枚举集有无穷多个枚举函数。这种枚举S的方法常常会有重复(例如，当S是有穷集时必定会重复)。如果S是无穷的递归可枚举集，则存在一种无重复的枚举方法：有1－1的递归全函数f使

S=｛f(0)，f(1)，f(2)，…｝．

对于自然数的n元组集合AN，也可以定义递归可枚举集的概念(当然，只能使用(1)、(2)两种形式的说法)。不过由于配对函数J(x，…，x)是原始递归函数，从而AN是递归可枚举集当且仅当J［A］=｛J(x，…，x)｜(x，…，x)∈A｝是递归可枚举集(J［A］N)。所以多数文献并不另行定义多元组的递归可枚举集，而是将A与．J［A］等同看待。

递归集都是递归可枚举集，但反之不然。例如

K=｛x｜φ(x)有定义｝

就是一个递归可枚举而非递归的集合。

递归可枚举集与递归集之间还有如下四条联系：

1．S是递归集当且仅当S和都是递归可枚举集；

2．如果无穷的递归可枚举集S有一个严格单调(上升)的枚举函数，则S是递归集；

3．每个无穷的递归可枚举集有无穷的递归子集；

4．递归可枚举集的投影仍是递归可枚举集。事实上，每个(一维的)递归可枚举集都是某个二维的递归集的投影：设S是递归可枚举集，则存在二维的递归集R，使

递归可枚举集的并、交仍是递归可枚举集，但余集未必是递归可枚举集。上面提到的

K=｛x｜φ(x)有定义｝

的余集就不是递归可枚举集。实际上，非递归的递归可枚举集的余集都不是递归可枚举集。

设φ(x)，φ(x)，φ(x)，… (*)

是一元递归函数的一个哥德尔枚举(每个一元递归函数都在序列(*)中出现无穷多次)(参见通用函数)，则全体(一维)递归可枚举集可以记为

　　　　　 W，W，W… (* *)

(其中W是φ(x)的定义域)。同样，每个递归可枚举集在序列(* *)中都出现无穷多次。在讨论递归可枚举集时常常使用这个序列。