Hatena Blog Tags

対角線論法

(サイエンス)
たいかくせんろんぽう

カントールの対角線論法

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

カントールの対角線論法 - Wikipedia
このタグの解説についてこの解説文は、すでに終了したサービス「はてなキーワード」内で有志のユーザーが作成・編集した内容に基づいています。その正確性や網羅性をはてなが保証するものではありません。問題のある記述を発見した場合には、お問い合わせフォームよりご連絡ください。

関連ブログ