数学百科

re集标准形

2023-06-05

英文

normal form of re sets

简介

re集的一种表示方法.若A为一个re集,则存在递归关系R,使得A={x|∃yR(x,y)}.re集A的这种表示方式称为其标准形式Σ1形.由此可以推出,A为re集,当且仅当A为某个部分递归函数的值域(即∃e(A=rang (φ e))),也当且仅当A为某部分递归函数之定义域(即∃e(A=dom  (φ e))).当A=dom (φ e)时,A记为We,即We=dom (φ e),并称e为We的下标.因此,{We}e∈ω是全体re集的一种能行枚举.此外We,s=dom (φ e,s)也是一个常用的记号.We,s实际上是一个递归集,而且,{We,s}为re集We的一个递归逼近序列.