有窮集下標

有窮集下標(index for a finite set)遞歸論的基本概念之一指有窮集的編碼.有窮集作為遞歸集,自然可以有它的re下標和特徵下標(參見“遞歸集下標”).但互補下標用來刻畫有窮集則不大合適,因為有窮集之補並不是有窮集.不過,有窮集還可有另一種重要的下標,即典則下標.設有窮集A= {xo, } , xn }。令e=2'9+2}1+…十2=n,則稱e為A的典則下標.並記A為De.例如D一{0,2,3,6}.美國數學家羅傑斯(Rogers , H.)證明了:由有窮集A之典則下標可以能行地找到其特徵下標,由特徵下標又可能行地找到其re下標.但它們之逆均不成立.由此可見,有窮集的典則下標反映其集合的信息最多,特徵下標次之,而r。下標最小.

相關詞條

熱門詞條

聯絡我們