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

編集の要約なし
* 全ての[[帰納的集合]]は帰納的可算だが、全ての帰納的可算集合が帰納的(集合)とは言えない。
* [[帰納的可算言語]]は[[形式言語]]の帰納的可算な部分集合である。
* 妥当帰納的可算な公理系から導かれる全ての文の集合は帰納的可算集合である。
* マチャセビッチの定理によれば、全ての帰納的可算集合はディオファントス集合である(逆も明らかに真)。
* [[単純集合]]は帰納的可算だが帰納的でない。
* creative set [[創造的集合]]は帰納的可算だが帰納的でない。
* productive set [[生産的集合]]は帰納的可算ではない。
* ある計算可能関数にゲーデル数 <math>\phi</math> が与えられたとき、集合 <math>\{\langle i,x \rangle \mid \phi_i(x) \downarrow \}</math> は帰納的可算である(ここで、<math>\langle i,x \rangle</math> は[[対関数]]であり、<math>\phi_i(x)\downarrow</math> は <math>\phi_i(x)</math> が定義されていることを示す)。この集合は、[[チューリングマシン]]が停止する入力パラメータ群を表すことで、[[チューリングマシンの停止問題]]の符号化となる。
* ある計算可能関数にゲーデル数 <math>\phi</math> が与えられたとき、集合 <math>\lbrace \left \langle x, y, z \right \rangle \mid \phi_x(y)=z \rbrace</math> は帰納的可算である。この集合は関数値を決定する問題の符号化である。