創造的集合と生産的集合
生産的集合 A {\displaystyle A} は帰納的可算でない。というのも A {\displaystyle A} が W i {\displaystyle W_{i}} を含むならば、 A {\displaystyle A} は W i {\displaystyle W_{i}} に属さない数を要素として持つからである。もっといえばそのような数は i {\displaystyle i} から実効的に計算できる。同様に、創造的集合は決定可能ではない。なぜならそれの補集合は生産的集合ゆえ帰納的可算でないからである。
任意の生産的集合は単射・全域的な生産的関数を持つ。
Myhill (1955)による次の定理により、ある意味で任意の創造的集合は K {\displaystyle K} に類似しており、任意の生産的集合は K ̄ {\displaystyle {\bar {K}}} に類似している。
定理. いま P {\displaystyle P} を自然数の集合とする。次は同値:
P {\displaystyle P} は生産的。
K ̄ {\displaystyle {\bar {K}}} は P {\displaystyle P} に1-還元可能。