|
カントールの対角線論法（カントールのたいかくせんろんぽう）は、数学における証明テクニック（背理法）の一つ。1891年にゲオルク・カントールによって非可算濃度を持つ集合の存在を示した論文の中で用いられたのが最初だとされている。 その後対角線論法は、数学基礎論や計算機科学において写像やアルゴリズム等が存在しない事を示す為の代表的な手法の一つとなり、例えばゲーデルの不完全性定理、停止性問題の決定不能性、時間階層定理といった重要な定理の証明で使われている。 == 対角線論法 == === 集合による表現 === 対角線論法とは、陰に陽に以下の補題を使って定理を証明する背理法の事である。 * Xを集合とし、2XをXのべき集合とする。さらにψをXから2Xへの写像とする。Xの部分集合Yをにより定義すると、ψ(x)=Yとなるx∈Xは存在しない。 上の補題は以下のように示せる。ψ(x)=Yとなるx∈Xが存在すると仮定したうえでxがYの元であるか否かを考える。もしxがYの元であればx∈Y=ψ(x)である。しかしYの定義より、Yはを満たすxの集合であるので、でなければならず、矛盾する。反対にもしxがYの元でなければであるが、Yの定義により、であるxはYの元でなければならず、やはり矛盾する。 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「カントールの対角線論法」の詳細全文を読む 英語版ウィキペディアに対照対訳語「 Cantor's diagonal argument 」があります。 スポンサード リンク
|