單純集((simple set)一種r集，它是由波蘭-美國數理邏輯學家波斯特((Post, E.工才.)為解決波特問題引進的。
設A為r。集，若A的補集A是禁集，則稱A為單純集.於是，單純集必定是非遞歸的.波斯特最早證明了單純集的存在性，並且證明了單純集一定不是m完全的.因此，如令A為單純集，便有RG }AG }必‘(其中R為非平凡遞歸集).此即肯定地回答了關於m化歸的波斯特問題.但是德克爾(Dekker , J.)證明了，任何非遞歸reT度中都含有單純集，因此，上述方法尚不足以解決關於T化歸的波斯特問題.俄國數學家柯爾莫哥洛夫(}omooropoB, A. H.)曾給出一個“自然的”單純集例.令K(x)=}e(}pe(0)一二)(此函式K稱為柯爾菲郭洛夫複雜性)，如果二}K(x)，則稱x為隨機數.那么全體非隨機數之集A= {x } K (x)<二}便是一個單純集.
