波斯特問題

波蘭一美國數理邏輯學家波斯特(Post, E. L.)提出了如下著名問題:是否存在非遞歸併且非完備的re集?即是否存在:。度a，使OGTaGTO'?此問題即波斯特問題。

內容介紹

1944年，波斯特本人為解決此問題做了許多工作.他計畫構造一個re集A，使得A具有某種可定義的(與A非遞歸相容的)性質，並且這種性質能保證A非T完備.稱此計畫為波斯特規劃.波斯特試圖構造一個re集A，使得A是足夠“稀疏”的，並且這種“稀疏’，性最終能保證A非T完備.他首先定義了單純集，並證明了它的存在性，還證明了單純集不是m完備的.但事實上，單純集仍可能是tt完備的(從而也是T完備的).於是，他又定義了補集比單純集更稀疏的超單純集和超超單純集，它們不再是tt完備的.他構造了一個超單純集，但未能證明超超單純集的存在性，也沒有證明超單純集或超超單純集不是T完備的.到1954年，德克爾(Dekker,J.)證明了超單純集不一定不是T完備的.後來，曼希爾(Myhill , J.)又引進了極大集的概念，這是可能做到的使re集的補集最稀疏的情況.弗里德((Friedberg,R. M.)證明了極大集與超超單純集的存在性，而耶茨(Yates ,C. E. M.)則構造了一個T完備的極大集，從而使得用構一個稀疏的補集的方法，來解決波斯特問題的希望最終破滅.首先解決波斯特問題的是弗里特貝格和穆切尼克(Mucnik,A. A. ). 1956年至1957年，他們分別獨立地創造了有窮損傷方法，並用此方法證明了存在兩個不可比的r。度(因而它們也都是非遞歸且非T完備的)，從而成功地解決了波斯特問題.

波斯特規劃

雖然按照波斯特原來建議的方法無法實現波斯特規劃，但實現這個規劃的努力一直沒有停止.1973年，刁格太夫(Degtev,A. N.)證明了，存在某個正等價關係專及re集A，使得A為非遞歸、半遞歸及專極大的.1976年，馬琴科夫(Marchenkov, S. S.)證明了:專超超單純集不是Q完備的，並且re半遞歸集如果不是Q完備的，也一定不是T完備的.因此刁格太夫構造的非遞歸、半遞歸及專極大的re集，即為非遞歸且非T完備的r。集.但這個結果並未完全實現波斯特規劃，因為專超超單純集的概念不是一階可定義的.直到1990年，哈林頓(Harrington ,L.)和索爾((Snare , R. I.)找到了一個一階可定義性質Q(A)，使得滿足該性質的re集都是非遞歸且非T完備的，並且他們證明了存在滿足Q(A)條件的r。集，從而成功地實現了波斯特規劃.他們給出的性質Q(A)為