分类

α有穷集

英文

α-finite set

简介

有穷集概念在α递归论中的推广.Lα中的元素称为α有穷集.作为对普通递归论的推广,α递归论所考虑的“计算步数”及“读写的信息数量”均允许到所有β<α,因此一个自然的想法,就是认为所有β<α是(α)有穷的(就像在经典递归论中认为一切n<ω是有穷的),这样才能有效地将经典递归论中能行的概念(在有穷步内算出,计算过程中使用有穷多个存贮单元)推广到α递归论中(在<α步骤内算出,计算过程中使用<α个存贮单元).但“有穷性”作为一个集合论概念,它又必须对“等势”封闭,即与有穷集等势的集合仍然应当是有穷的.因此,仅认为一切β<α有穷是不够的.不过在α递归论中,使用集合论的等势概念是不合适的.相反,只有在两个集合之间存在“能行的”一一对应关系时,才可以认为它们是“等势的”.因此,α有穷性概念与α递归论概念是密不可分的.在α递归论中,若f为部分α递归函数,k为α有穷集,则f[k]也是α有穷的.另外,与经典递归论相似的一个性质是:所有α有穷集可以被α能行地枚举出来.对α有穷性来说,与经典递归论不同,有穷与有界不再是相同的概念.具体地,ωck1有穷的ω的子集恰为自然数的超算术集.δ12有穷的ω的子集恰为自然数的Δ12集(关于ωck2与δ12的定义,参见“可允许序数”).