查看“︁對角論證法”︁的源代码

'''对角论证法'''是[[乔治·康托尔]]於1891年提出的用于说明[[实数]][[集合 (数学)|集合]]是[[不可数集]]的证明。

对角线法并非康托尔关于实数不可数的第一个证明，而是发表在他第一个证明的三年后。他的第一个证明既未用到[[十進位制|十进制展开]]也未用到任何其它[[數系]]。自从该技巧第一次使用以来，在很大范围内的证明中都用到了类似的证明构造方法，它們一般亦稱為對角論證法。

==实数==
康托尔的证明表明[[区间]][0, 1]不是[[可数|可数无穷大]]。该证明是用[[反證法]]完成的，步骤如下：

# 假設区间[0, 1]是可數無窮大的，已知此區間中的每個數字都能以[[小數]]形式表達。
# 我們把區間中所有的數字排成數列（這些數字不需按序排列；事實上，有些可數集，例如有理數也不能按照數字的大小把它們全數排序，但單只是成數列就沒有問題的）。對於那些有兩種小數形式的數字，例如0.499 ... = 0.500 ...，我們選擇前者。
# 舉例，如果該數列小數形式表現如下：
#: ''r''<sub>1</sub> = 0 . 5 1 0 5 1 1 0 ... 
#: ''r''<sub>2</sub> = 0 . 4 1 3 2 0 4 3 ...
#: ''r''<sub>3</sub> = 0 . 8 2 4 5 0 2 6 ... 
#: ''r''<sub>4</sub> = 0 . 2 3 3 0 1 2 6 ...
#: ''r''<sub>5</sub> = 0 . 4 1 0 7 2 4 6 ... 
#: ''r''<sub>6</sub> = 0 . 9 9 3 7 8 3 8 ...
#: ''r''<sub>7</sub> = 0 . 0 1 0 5 1 3 5 ... 
#: ...
# 考慮<math>r_k</math>小數點後的第k個位，我們給這些數字加上底線與粗體。從這裡可以看出「對角論證法」名稱的由來。
#: ''r''<sub>1</sub> = 0 . <u>'''5'''</u> 1 0 5 1 1 0 ... 
#: ''r''<sub>2</sub> = 0 . 4 <u>'''1'''</u> 3 2 0 4 3 ...
#: ''r''<sub>3</sub> = 0 . 8 2 <u>'''4'''</u> 5 0 2 6 ... 
#: ''r''<sub>4</sub> = 0 . 2 3 3 <u>'''0'''</u> 1 2 6 ...
#: ''r''<sub>5</sub> = 0 . 4 1 0 7 <u>'''2'''</u> 4 6 ... 
#: ''r''<sub>6</sub> = 0 . 9 9 3 7 8 <u>'''3'''</u> 8 ...
#: ''r''<sub>7</sub> = 0 . 0 1 0 5 1 3 <u>'''5'''</u> ... 
#: ...
# 我們設一實數<math>x \in [0, 1]</math>，其中<math>x</math>的第k個小數位為1（如果<math>r_k</math>的第<math>k</math>個小數位不是1）或2（如果<math>r_k</math>的第<math>k</math>個小數位是1）
# 明顯地<math>x</math>是一個在区间[0, 1]內的實數，以之前的數列為例，則相對應的<math>x</math>應為 0 . 1 2 1 1 1 1 1 ...。
# 由於<math>x</math>的特殊定義，<math>x</math>和<math>r_n</math>會在第<math>n</math>個小數位不同。這使得序列<math>(r_1,r_2,r_3,... )</math>之中所有的實數俱不能與<math>x</math>完全相等，即<math>x</math>不在序列<math>(r_1,r_2,r_3,... )</math>中。
# 但我們假設<math>(r_1,r_2,r_3,\ldots)</math>包括了所有區間[0, 1]內的實數，即應該要存在一個<math>r_n=x</math>。這發生了矛盾。
# 所以在第一點內所提出的假設「区间[0, 1]是可數無窮大的」不成立，證畢。

== 外部連結 ==
*[https://web.archive.org/web/20060423090728/http://uk.geocities.com/frege%40btinternet.com/cantor/diagarg.htm Original German text of the 1891 proof, with English translation]
*[http://us.metamath.org/mpegif/mmcomplex.html#uncountable A variation on Cantor's diagonal proof, completely formalized from first principles] {{Wayback|url=http://us.metamath.org/mpegif/mmcomplex.html#uncountable |date=20210206111537 }}

{{数理逻辑}}
{{集合论}}

[[Category:集合论|D]]
[[Category:數學推理|D]]
[[Category:无穷|D]]