[科普中國(guó)]-極大集

極大集是余集為內(nèi)聚集的c.e.集。若A為c.e.集，而A的補(bǔ)集是內(nèi)聚集，則A稱為極大集。

定義極大集是其補(bǔ)集為內(nèi)聚集的遞歸可枚舉集（c.e. 集）。1

發(fā)展弗里德貝格(Friedberg,R. M.)于1958年證明了極大集的存在性，并證明了極大集都是hh單純集。因而，極大集概念是hh單純集的進(jìn)一步加強(qiáng)。

耶茨(Yates , C. E. M.)于1965年證明存在一個(gè)T完全的極大集。

極大集的存在不足以肯定回答波斯特問(wèn)題。注意到從單純集、h單純集、hh單純集到極大集，它們補(bǔ)集的元素越來(lái)越“稀疏”。而極大集之補(bǔ)的元素已是最稀疏的了，但這仍不足以保證其非T完全性，即用限制其補(bǔ)集元素之“稀疏性”的辦法是無(wú)法解決波斯特問(wèn)題的。

實(shí)際上，波斯特問(wèn)題的解決是由弗里德貝格和穆切尼克(Mucnik,A. A.)用有窮損傷優(yōu)先方法解決的。

內(nèi)聚集內(nèi)聚集是一種特殊的禁集。如果自然數(shù) A 是無(wú)窮的，且不能被任何遞歸可枚舉集分成兩個(gè)無(wú)窮部分，即對(duì)任何遞歸可枚舉集和中至少有一個(gè)是有窮的，則稱 A 是內(nèi)聚集。

本詞條內(nèi)容貢獻(xiàn)者為:

尚華娟 - 副教授 - 上海財(cái)經(jīng)大學(xué)