帰納的集合

指示関数が帰納的関数となるような集合を帰納的集合（きのうてきしゅうごう）という。

端的に言えば、決定可能な集合であり、チャーチのテーゼを認めるならば、計算可能な集合である。

たとえば、素数の集合は、帰納的集合である。一方で停止性問題（実行すると停止するプログラムと入力の組の集合）は帰納的でない。

 関連項目 
 帰納的関数
 計算可能関数
 帰納的可算集合

Category:集合論
Category:計算可能性理論
Category:数学に関する記事