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

集合 <math>T</math> の[[差集合|補集合]] <math>\mathbb{N} \setminus T</math> が帰納的可算である場合、<math>T</math> は '''co-r.e.''' と呼ばれる。同様に、ある集合が co-r.e. である必要十分条件は、それが算術的階層のレベル <math>\Pi^0_1</math> にあることである。
 
集合 ''A'' が[[帰納的集合|帰納的]](計算可能)である必要十分条件は、''A'' と ''A'' の補集合が共に帰納的可算集合であることである。これは帰納的可算集合の束に於いて帰納的関数のクラスが定義可能であることを示す。ある集合が帰納的である必要十分条件は、その集合が何らかの全体再帰関数の昇順の値域になっているか、または有限なことである。
 
帰納的可算集合同士の対を取ると、あるものは{{仮リンク[[帰納的分離不能対|帰納的分離可能|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> なるものが存在する。