帰納的可算集合
任意の帰納的可算集合 A , B {\displaystyle A,B} に対して、互いに素な帰納的可算集合 A ~ , B ~ {\displaystyle {\tilde {A}},{\tilde {B}}} で A ~ ⊆ A {\displaystyle {\tilde {A}}\subseteq A} , B ~ ⊆ B {\displaystyle {\tilde {B}}\subseteq B} , A ~ ∪ B ~ = A ∪ B {\displaystyle {\tilde {A}}\cup {\tilde {B}}=A\cup B} なるものが存在する。 A , B {\displaystyle A,B} の元を a 0 , b 0 , a 1 , b 1 , ... {\displaystyle a_{0},b_{0},a_{1},b_{1},\ldots } と交互に枚挙していく。 a i {\displaystyle a_{i}} がそれより前に現れないなら A ~ {\displaystyle {\tilde {A}}} に置く。また b i {\displaystyle b_{i}} がそれより前に現れないなら B ~ {\displaystyle {\tilde {B}}} に置く。このとき A ~ , B ~ {\displaystyle {\tilde {A}},{\tilde {B}}} は所望の性質を満たす。
任意の帰納的でない帰納的可算集合は2つの互いに素な帰納的でない帰納的可算集合に直和分解できる。