カントールの対角線論法

ウィキペディア

カントールの対角線論法

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2023/10/26 05:56 UTC 版)

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

対角線論法

集合による表現

対角線論法とは、以下の補題を使って定理を証明する背理法のことである。

• ${\displaystyle X}$ カテゴリ