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

 
== 特性 ==
''A'' と ''B'' が共に帰納的可算集合なら、''A'' ∩ ''B'' 、 ''A'' ∪ ''B'' 、 ''A'' × ''B'' も帰納的可算集合である(''A'' × ''B'' は、[[対関数|カントールの対関数]]を使って順序対を1つの自然数にすることを意味する)。部分再帰関数における帰納的可算集合の逆像は帰納的可算集合である。
 
ある集合が帰納的可算である必要十分条件は、それが[[算術的階層]]のレベル <math>\Sigma^0_1</math> にあることである。
集合 <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'' の補集合が共に帰納的可算集合であることである。これは帰納的可算集合の束に於いて帰納的関数のクラスが定義可能であることを示す。(すなわち補元を持つ元が帰納的可算集合である。)ある集合が帰納的である必要十分条件は、その集合が何らかの単調増加な再帰関数の昇順の値域になっているか、または有限なことである。
 
互いに素な帰納的可算集合同士の対を取ると、あるものは[[帰納的分離不能対|帰納的分離可能]]であり、あるものは帰納的分離不可能である。対照的に、任意の互いに素な 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> なるものが存在する。<math>A,B</math> の元を <math>a_0, b_0, a_1, b_1, \ldots </math> と交互に枚挙していく。<math>a_i</math> がそれより前に現れないなら <math>\tilde{A}</math> に置く。また <math>b_i</math> がそれより前に現れないなら <math>\tilde{B}</math> に置く。このとき <math>\tilde{A},\tilde{B}</math> は所望の性質を満たす
 
任意の帰納的でない帰納的可算集合は2つの互いに素な帰納的でない帰納的可算集合に直和分解できる。<ref>Richard M. Friedberg (1958), ''Three Theorems on Recursive Enumeration. I. Decomposition. II. Maximal Set. III. Enumeration Without Duplication'', ''Journal of Symbolic Logic'' 23:3, pp.&nbsp;309–316.</ref>
 
== 注意 ==