極小對

極小對是一對特殊的遞歸可枚舉度，極小對的存在性最早是由耶茨(Yates , C. E. M.)證明的。極小對的存在性指出，雖然R是稠密的，但休恩菲爾德猜想仍不成立。關於極小對的進一步的結果，拉克倫(Lachlan,A. H.)證明了並非每個非0的遞歸可枚舉度都有一個極小對。

基本介紹

• 中文名：極小對
• 外文名：minima pair
• 適用範圍：數理科學

定義

極小對是一對特殊的遞歸可枚舉度。

若兩個遞歸可枚舉度a > 0，b > 0，且，則稱a，b形成極小對。

可成帽度

[cappable degree]

如果一個遞歸可枚舉度是極小對的一半，那么這個度就稱為可成帽度。

非囿界度

[nonbounding degree]

對於遞歸可枚舉度a>0，如果a下面不存在極小對，那么a就稱為非囿界的。拉克倫用∅'''方法證明了非囿界度的存在性。

套用

耶茨和拉克倫於1966年獨立地證明了極小對的存在性。極小對的存在性指出，雖然R是稠密的，但休恩菲爾德猜想仍不成立。關於極小對的進一步的結果，拉克倫(Lachlan,A. H.)證明了並非每個非0的遞歸可枚舉度都有一個極小對。