「帰納的可算集合」の版間の差分

集合 ''A'' が[[帰納的集合|帰納的]](計算可能)である必要十分条件は、''A'' と ''A'' の補集合が共に帰納的可算集合であることである。ある集合が帰納的である必要十分条件は、その集合が何らかの全体再帰関数の昇順の値域になっているか、または有限なことである。
 
帰納的可算集合同士の対を取ると、あるものは有効に{{仮リンク|帰納的分離可能([[:en:effectively separable|en]])|recursively inseparable set}}であり、あるものは有効に分離不可能である。対照的に互いに素な co-r.e. 集合が帰納的分離可能であることが次の性質から示される。
 
任意の帰納的可算集合 <math>A,B</math> に対して、互いに素な帰納的可算集合 <math>\tilde{A},\tilde{B}</math> で <math>\tilde{A} \subseteq A</math>, <math>\tilde{B} \subseteq B</math>, <math>\tilde{A} \cup \tilde{B} = A \cup B</math> なるものが存在する。
 
任意の帰納的でない帰納的可算集合は2つの互いに素な帰納的でない帰納的可算集合に直和分解できる。
 
== 注意 ==