創造的集合と生産的集合
K ̄ {\displaystyle {\bar {K}}} は P {\displaystyle P} にm-還元可能。
定理. いま C {\displaystyle C} を自然数の集合とする。次は同値:
C {\displaystyle C} は創造的。
C {\displaystyle C} は1-完全。
C {\displaystyle C} は K {\displaystyle K} に再帰同型である。すなわち、全域計算可能な全単射 f {\displaystyle f} が存在して f ( C ) = K {\displaystyle f(C)=K} が成り立つ。
生産的集合は帰納的可算な無限集合を含むことが分かる。 P {\displaystyle P} を生産的集合、 f {\displaystyle f} を P {\displaystyle P} の全域的な生産的関数とする。まず帰納的可算集合の指標 e n {\displaystyle e_{n}} を帰納的に
W e 0 = ∅ {\displaystyle W_{e_{0}}=\varnothing }
W e n + 1 = W e n ∪ { f ( e n ) } {\displaystyle W_{e_{n+1}}=W_{e_{n}}\cup \{f(e_{n})\}}