スマートフォン用の表示で見る

対角線論法

サイエンス

対角線論法

たいかくせんろんぽう

カントールの対角線論法

カントール対角線論法カントールのたいかくせんろんぽう)は、数学における証明テクニックの一つで、1891年にゲオルグ・カントールによって非可算濃度を持つ集合の存在を示した論文[1]の中で用いられたのが最初だとされている。 対角線論法はその後、数学基礎論や計算機科学の定理を証明するのに使われる代表的な手法の一つとなり、例えばゲーデル不完全性定理、停止性問題の決定不能性、時間階層定理といった重要な定理の証明で使われている。

http://ja.wikipedia.org/w/index.php?title=%E3%82%AB%E3%83%B3%E3%83%88%E3%83%BC%E3%83%AB%E3%81%AE%E5%AF%BE%E8%A7%92%E7%B7%9A%E8%AB%96%E6%B3%95&oldid=19555076:title