コンテンツにスキップ

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

m
m (ボット: 言語間リンク 11 件をウィキデータ上の d:q676835 に転記)
[[自然数]]の集合 ''S'' について、定義域が ''S'' と正確に一致するような何らかの部分再帰関数([[計算可能関数|部分計算可能関数]])''f'' が存在するとき、''S'' は'''帰納的可算'''であると言う。つまり ''f'' が定義される必要十分条件は、''f'' への入力が ''S'' の元であることである。
 
この定義は任意の可算集合 A に拡張できる。そのためには、A の元を[[ゲーデル数]]で表し、もし対応するゲーデル数の集合が帰納的算ならば A の何らかの部分集合が帰納的可算になることを言えば良い。
 
== 等価な定式化 ==