カントールの対角線論法(カントールのたいかくせんろんぽう、英: Cantor's diagonal argument)は、数学における証明テクニック(背理法)の一つ。1891年にゲオルク・カントールによって非可算濃度を持つ集合の存在を示した論文の中で用いられたのが最初だとされている。...
14 KB (2,297 words) - 05:56, 26 October 2023
対角線(たいかくせん、英: diagonal)とは、単純多角形や多面体において、異なる2つの頂点を結ぶ線分のうち辺を除く線分のこと。 2次元内における単純多角形が凸多角形ならば、その対角線の両端以外は、その多角形内部に含まれる。 3次元以上における凸多面体の対角線...
4 KB (526 words) - 14:41, 22 May 2024
ゲオルク・フェルディナント・ルートヴィッヒ・フィーリップ・カントール(Georg Ferdinand Ludwig Philipp Cantor [ˈkantoːɐ̯], 1845年3月3日 - 1918年1月6日)は、ドイツで活躍した数学者。 素朴集合論の確立者。自然数と実数の間に全単射が存在しないことを対角線論法によって示す一方、R...
8 KB (918 words) - 03:44, 15 August 2024
カントールの定理(カントールのていり、Cantor's theorem)は、集合論における基本的な定理の一つで、冪集合の濃度について述べたものである。最初にこれを証明したドイツ人数学者ゲオルク・カントールにちなむ。 任意の集合 A に対して、A のすべての部分集合の集合( A の冪集合)は A 自身よりも真に大きい濃度を持つ。...
14 KB (2,037 words) - 20:43, 24 November 2023
停止性問題 (redirect from チューリングマシンの停止問題)
対角線論法は、集合Sからその冪集合P(S)への全単射が存在しない(カントールの定理)事を示す為にゲオルク・カントールが使った論法である。 実は上述の証明は対角線論法も利用している。以下簡単の為、プログラムの入力は全て自然数とする。前述したようにプログラムは0と1からなる数字で書き表せるので、プログラム全体の集合は自然数全体の集合 N...
10 KB (1,421 words) - 21:20, 17 March 2023
非可算集合 (category 日本語版記事がリダイレクトの仮リンクを含む記事)
非可算集合の例として最も知られているものは実数全体の集合 R であろう。その非可算性はカントールの対角線論法により証明される。対角線論法はその他の集合(例えば、自然数からなる無限列全体の集合、自然数からなる集合全体からなる集合族)の非可算性を証明するのにも応用される。R の濃度をしばしば連続体濃度と呼び c や 2 ℵ 0 {\displaystyle...
6 KB (962 words) - 22:13, 19 February 2024
可算集合 (category すべてのスタブ記事)
2\mathbb {N} .} よって、2N は可算集合である。また、整数全体の集合 Z や有理数全体の集合 Q も可算である。しかし、実数全体の集合 R は非可算である。この事実はカントールの対角線論法によって示される。R の濃度は連続体濃度と呼ばれ、 ℵ {\displaystyle \aleph...
5 KB (752 words) - 23:04, 15 November 2023
連続体仮説 (redirect from ヒルベルトの第1問題)
の方が大きいことは、カントールの対角線論法によって証明されている。カントールは当初、連続体仮説も証明することはそれほど難しくないと考えていたが、遂に証明することはできなかった。 1900年、パリで開かれた国際数学者会議においてダフィット・ヒルベルトは彼の有名な 23 の問題の...
12 KB (1,977 words) - 12:35, 9 January 2024
自身よりも多くの元を含む(#連続濃度の非可算性節を見よ)。このことはゲオルク・カントールによって1874年に初めて示され、無限の尺度に異なる階層があることを確立した研究の嚆矢となった。後に、カントールはより簡明な対角線論法による証明も与えている。 連続体濃度を持つ集合には以下のような例がある。二つの異なる実数...
13 KB (2,118 words) - 09:18, 18 November 2022
数学、特に集合論において、濃度(のうど、英: cardinality カーディナリティ)とは、有限集合における「元の個数」を一般の集合に拡張したものである。集合の濃度は基数 (cardinal number) と呼ばれる数によって表される。歴史的には、カントールにより初めて無限集合のサイズが一つではないことが見出された。...
9 KB (1,083 words) - 08:36, 10 December 2023
の2の冪としての記法はこれの特別の場合にあたる。 冪集合の濃度は元の集合の濃度より常に大きい(カントールの定理)。有限集合のときにはこれは自明である。一般の場合は、カントールの対角線論法によって示される。 集合 族 (数学) ブール代数 連続体濃度 連続体仮説 ^ 集合論の慣例で、自然数...
8 KB (1,382 words) - 10:22, 7 November 2023
カラテオドリの定理 カラビ・ヤウ多様体 カルダノの公式 カルタン行列 カルタンの判定条件 ガロア群 カントール集合 カントールの対角線論法 カントールの定理 キリング形式 クリストッフェル記号 クラインの壺 グラスマン代数 グラスマン多様体 グラム・シュミットの正規直交化法 クラメルの公式 グラハム数...
9 KB (925 words) - 19:22, 25 June 2024
数学 (category 独自研究の除去が必要な節のある記事/2016年7月-12月)
ールドバッハの予想—双子素数—ゲーデルの不完全性定理—ポアンカレ予想—カントールの対角線論法—ピタゴラスの定理—中心極限定理—微分積分学の基本定理—代数学の基本定理—四色定理—ツォルンの補題—オイラーの等式—コラッツの問題—合同数—バーチ・スウィンナートン=ダイアー予想—ヒルベルトの23の問題—スメイルの問題—ソファ問題...
26 KB (3,221 words) - 02:53, 5 July 2024
構成主義 (数学) (category 出典を必要とする記述のある記事/2020年8月)
を同一視すると矛盾が生じる。さらに言えば、対角線論法は完全に構成的であると考えられる。 実際カントールの対角線論法は、自然数から実数への全単射を考えると、実数が関数の値域にないために矛盾が生じるという意味で、構成的に示せる。まず関数 T が自然数から実数への全射であると仮定して、関数 T...
19 KB (2,898 words) - 02:33, 11 November 2023
P≠NP予想 (category すべてのスタブ記事)
の方が確からしいと傾いた訳でもなく、新たな証明手法が必要だと考えられてきた点がまた特徴的である。以下、試みられた証明手法と、その手法では証明できない理由。 複雑性クラスを分離するために最初期から主に1970年代末まで利用された証明手法として、集合論の創始者カントールが1891年に考案した対角線論法...
20 KB (2,700 words) - 03:39, 12 July 2024
2005年。ISBN 4-535-60144-5。 直観主義 転換法 否定の導入 二重否定の除去 無矛盾律 排中律 無限降下法 対角線論法 帰謬法 (修辞学) 『背理法』 - コトバンク 『{{{2}}}』 - 高校数学の美しい物語 Weisstein, Eric W. "Reductio ad Absurdum"...
3 KB (424 words) - 07:43, 14 December 2023
は上記の行列の対角線上の値に 1 を加えた値を返す関数である。この関数は計算可能だが、如何なる原始再帰関数もこの関数を計算できないことが明らかである。何故ならどのような原始再帰関数も、この関数とは対角線部分において値が異なるからである。従って原始再帰的でない計算可能関数が存在する。 この論法...
18 KB (3,017 words) - 13:48, 16 February 2024
定義可能実数 (section ZFCのモデルにおける定義可能性)
しかしながらカントールの対角線論法で知られるように実数は不可算個あるため、ほとんどすべての実数は定義不可能な実数である。 実数を特定する手法の一つに幾何学的な方法がある。 実数 r {\displaystyle r} が作図可能数であるとは、与えられた長さ1の線分から始めてコンパスと定規を使って長さ...
10 KB (1,550 words) - 22:43, 15 September 2023
カントールは1874年の論文 において、Nの濃度より実数全体の集合の濃度のほうが真に大きいということを示すことによって、高階の基数が存在することを示した。彼の証明は、区間縮小法を用いた複雑な論法であった。しかし、1891年の論文 では、同じことを巧妙かつ簡潔な対角線論法...
21 KB (2,798 words) - 06:11, 15 August 2023
周期 (数体系) (category 出典を必要とする記述のある記事/2024年4月)
の定数 Ωがある。計算可能数であって周期とならない自然な例は今のところ知られていないが、人工的な例はカントールの対角線論法を用いて容易に作れる。ネイピア数 e, 1/π, オイラー–マスケローニ定数 γ などは周期でない数の尤もらしい候補と考えられる。 周期は、代数的数と超越数の...
8 KB (1,232 words) - 02:52, 25 April 2024
小数 (category 数の表現)
の場合には(たとえばカントールの対角線論法)、全てを循環小数として表現することが必要になる。 整数部が0である小数を純小数または真小数、それ以外を帯小数と呼ぶことがある。 与えられた実数xと2以上の自然数nに対して,xのn進無限小数表記を与える無限数列a0, a1, a2, …の各項の...
18 KB (2,780 words) - 23:06, 15 January 2024
Μ再帰関数 (category 書きかけの節のある項目)
カントールの対角線論法を使って、それ以上の再帰関数が定義可能であることを示したことである。 結論から言えば、μ再帰関数の停止判定はμ再帰関数の体系では不可能であり、チューリングマシンの停止問題と実質的に同じ問題であることが判っている。 クリーネは以下の...
12 KB (2,084 words) - 08:07, 22 October 2022
の超限的反復 比較的新しい 自己検証理論 の発見(自身を語ることができるほど強力な体系だが、ゲーデルの証明不可能性の論証の鍵となった対角線論法を適用できるほど強力でない理論体系) 構造証明論は証明論の一分野であり、解析的証明の記述が可能な証明計算を研究する分野である。解析的証明の...
9 KB (1,377 words) - 14:48, 26 December 2023
0.999... (redirect from 0.999...が1に等しいことの証明)
対角線論法を適用して単位区間 [0, 1] の非可算性の適切な証明を与えたことを考慮しなければならない。このような証明ではある2つの実数が小数表現において異なることを言明することが必要とされる。したがって、0.2 と 0.1999… のような組を避けなければならない。簡単な方法においては、すべての...
87 KB (13,216 words) - 02:19, 1 September 2024
ケーニヒの定理の不等式の左辺はちょうどκになり、 右辺はκから{0,1}への関数全体の集合の濃度である2κとなる。 これはκの冪集合の濃度であり、ケーニヒの定理はカントールの定理の別証明を与える。 (歴史的にはカントールの定理の方が先に証明されている。) 選択公理は"任意の空でない集合の直積は空でない"という命題とも言える。...
8 KB (1,335 words) - 14:37, 27 June 2023
の門人であるヒッパソスは、単位正方形の対角線は、その辺と通約不能であることを示した。換言すると、彼は、単位正方形の対角線とその辺の比を正確にあらわす(有理)数が存在しないことを証明した。これが原因となり、ギリシアの数学の...
124 KB (11,458 words) - 23:35, 23 August 2024
論理クイズ ペアノの公理 数学的帰納法 集合論 ラッセルのパラドックス ド・モルガンの法則 写像 0.999... 極限 形式的体系 論理式 公理 推論規則 証明と定理 イプシロン-デルタ論法 連続 可算集合 カントールの対角線論法 無矛盾性と完全性 第一不完全性定理 第二不完全性定理 ゲーデル数 同値関係...
42 KB (6,153 words) - 11:01, 8 December 2023
シミュレーション仮説 (category 言葉を濁した記述のある記事 (誰)/2010年以前)
のような見方を採用すれば、シミュレーション仮説は反証可能性がないため、科学的には受け入れられない、ということになる。 CantGoTu環境の概念は、ゲオルク・カントールの対角線論法、クルト・ゲーデルの不完全性定理、アラン・チューリングなどに代表される計算可能性理論の...
39 KB (5,397 words) - 05:42, 18 July 2024
数理論理学では、対角化定理 (対角線補題(diagonal lemma)、対角化補題(diagonalization lemma)、自己言及補題(self-reference lemma)または不動点定理(fixed point theorem)としても知られる)は、自然数の特定の形式理論、特にすべての...
12 KB (1,724 words) - 10:30, 4 May 2024
1874年 — ゲオルク・カントールが、すべての実数の集合は不可算無限であるが、すべての実代数的数の集合は可算無限であることを証明する。彼の証明法(英語版)は有名な対角線論法を使用しておらず、1891年に出版された。 1882年 — フェルディナント...
65 KB (9,388 words) - 21:59, 2 August 2024