定义和例子
集合 的一个编号是由 到 的,满的偏函数[2]:477。编号 在数字 的取值(若有定义)一般以 表示(而不是常见的函数表示 )。
编号的例子有:
- 所有有限子集构成的集合上,可定义编号 ,其中 ,而且对任意有限非空集合 , ,其中 [2]:477。该编号是一个(偏的)双射。
- 在偏可计算函数集上,给定一哥德尔编号 ,可以定义递归可枚举集合的编号 ,其中 是 的定义域。该编号是满射(所有编号都是)但不是单射:不同的数可能经 映射到同一个递归可枚举集合上。
编号的种类
如果一个编号是全函数,则它是全的[3]:98。如果偏编号的定义域是递归可枚举的话,则必存在等价的全编号,等价性的定义将在下节给出。
若集合 可判定,则编号 可判定。
如果 当且仅当 ,则编号 是单值的[3]:98;换言之, 是一个单射函数。偏可计算函数构成的集合上的单值编号又称费德伯格编号。
编号的大小比较
所有编号构成的集合上可以定义预序。令 和 是两编号,则 可归约到 ,记为 ,当且仅当存在一元偏可计算函数 ,使得
- 。[3]:100
若 而且 ,则 等价于 ,记为 。[3]:100
可计算编号
如果被编号的对象 足够“可构”,人们常常会考虑能高效解码的编号[2]:486。例如,若集合 递归可枚举,则编号 是可计算的当且仅当满足 的二元组 构成的集合递归可枚举。类似地,偏函数的编号 是可计算的当且仅当关系 “ ”是偏递归的[2]:487。
若某集合上任意可计算编号都可归约到特定编号,则称该特定编号为主的。所有 的递归可枚举子集以及所有偏可计算函数都有主编号[2]:487。偏递归函数上的主编号又称为可接受编号。
参见
参考文献