カントールの対角線論法
出典: フリー百科事典『ウィキペディア(Wikipedia)』 (2023/10/26 05:56 UTC 版)
カントールの対角線論法(カントールのたいかくせんろんぽう、英: Cantor's diagonal argument)は、数学における証明テクニック(背理法)の一つ。1891年にゲオルク・カントールによって非可算濃度を持つ集合の存在を示した論文[1]の中で用いられたのが最初だとされている。 その後対角線論法は、数学基礎論や計算機科学において写像やアルゴリズム等が存在しないことを示す為の代表的な手法の一つとなり、例えばゲーデルの不完全性定理、停止性問題の決定不能性、時間階層定理といった重要な定理の証明で使われている。
注釈
出典
- ^ George Cantor (1891). Uber ein elementare Frage der Mannigfaltigkeitslehre. Deutsche Mathematiker-Vereinigung.
- 1 カントールの対角線論法とは
- 2 カントールの対角線論法の概要
- 3 カントールの定理
- 4 停止性問題の決定不能性
- 5 脚注
カントールの対角線論法と同じ種類の言葉
- カントールの対角線論法のページへのリンク