帰納的分離不能対

ウィキペディア

帰納的分離不能対

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2015/02/22 17:06 UTC 版)

計算可能性理論において帰納的分離不能対（きのうてきぶんりふのうつい、英: recursively inseparable pair)とは自然数の集合の対で帰納的集合によって分離できないものをいう(Monk 1976, p. 100)。この概念は計算理論におけるΠ₁集合と関係が深い。帰納的分離不能対はゲーデルの不完全性定理とも関係する。