創造的集合と生産的集合
↑ Soare (1987); Rogers (1987).
1 2 Enderton (2010), pp. 79, 80, 120.
後で述べるように創造的集合は帰納的可算な補集合を持たない。すなわち創造的集合は帰納的でない。
典型的な創造的集合に K = { i ∣ i ∈ W i } {\displaystyle K=\{i\mid i\in W_{i}\}} がある。この集合は停止性問題の対角線を表している。この補集合 K ̄ = { i ∣ i ∉ W i } {\displaystyle {\bar {K}}=\{i\mid i\notin W_{i}\}} は生産的関数 f ( i ) = i {\displaystyle f(i)=i} を持つ生産的集合である: W i ⊆ K ̄ {\displaystyle W_{i}\subseteq {\bar {K}}} と仮定する。このとき i ∈ W i {\displaystyle i\in W_{i}} ならば i ∈ K {\displaystyle i\in K} かつ i ∈ K ̄ {\displaystyle i\in {\bar {K}}} となって不合理。すなわち i ∉ W i {\displaystyle i\notin W_{i}} 。それゆえ i ∈ K ̄ {\displaystyle i\in {\bar {K}}} 。