Re: [理工] 清大離散對角化證明
※ 引述《jacksoncsie (Nov)》之銘言：
: 想問一下這題，
: 雖然明天可能會公布解答
: 但想知道我的想法是正確的嗎?
: https://i.imgur.com/65LRlwN.jpg
: 我認為的確證明有理數是要透過其digital一對一至x
: 但題目對映的方式應該是檢查所有對映點1~j
: 應該是這部分有問題 我的想法不知道有沒有錯?
這題目挺有趣的，想把我學到的觀念分享給大家，有錯還請幫忙指出XD
----------Prerequisite---------------------------------
看這題目前要先知道甚麼是 countable 以及 Cantor's diagonal argument
#Countable(可數):
我們說一個集合A是countable是指說A裡面的elements
要麼是finite有限個
要麼是infinite，並且存在一種對應M: A -> N, M是1-1和onto，N是所有自然數
(更簡單的說，A裡面每個數字都可以一個一個枚舉出來)
#Cantor's diagonal argument:
Cantor利用一種叫diagonalization的技巧(不是線代裡的diagonalization)
來證明實數R是uncountably infinite
這邊我們只要了解他證明裡的精神即可，我舉個簡單的例子，
EX: Prove that the set of real numbers in (0, 1) is uncountable
<pf> 方便起見，令 A = the set of real numbers in (0, 1)
用反證法，假設A是countable，我們就可以把A裡每個數
都一一列出來(這邊順序隨意)，譬如說
x1 = 0.123456789...
x2 = 0.234567890...
x3 = 0.345678901...
x4 = 0.456789012...
x5 = 0.567890123...
...
Claim: 我們可以在這個set裡找到一個x，不是任何xi
(這邊打個比方，我們把A的數字全部倒出來，然後一個一個寫在清單上，
當我們再把全部數字倒回A後，再取一個數字x出來，
發現他居然不在這個清單上，進而得到矛盾。)
這個數字x是誰呢？
我們令x小數點後的第一個digit不同於x1, 第二個digit不同於x2，以此類推。
以我們上面的例子來講：
x1 = 0.123456789...
x2 = 0.234567890...
x3 = 0.345678901...
x4 = 0.456789012...
x5 = 0.5678901234
...
取 x = 0.21456...
或是 x = 0.38697... 都可以
(x不是唯一的，只要x與任何一個xi都不同於至少1個digit都ok)
因為 x != xi, for any i, and x is in A
-> 矛盾產生
-> 所以A是uncountable
(可以看到上面黃色數字形成對角線，所以叫diagonal argument)
--------------Prerequisite Done-----------------------
回到題目，題意是
X = (0, 1)之間的所有有理數的子集合
Peter想用 Cantor's diagonal argument 來證明 X 是uncountable，
但其實 X 是countable (因為所有有理數的集合 Q 都是countable)，
我們找出這個case裡哪裡不適用這個方法
問題出在，Peter造出來的x其實不在X裡，因此無法證得矛盾
要了解這個我們先知道有理數的一個性質:
任何有理數寫成小數後，小數點後經過一些finite period後的數字
都會是repeating sequence。
譬如說:
1/2 = 0.5000000000... 重複0
1/3 = 0.33333333... 重複3
1/100 = 0.010000.... 重複0
比較有趣的例子是1/7
1/7 = 0.142857 142857 142857... 重複 142857
因此如果造出來的x是有理數，那麼
x在小數點後，經過一些finite period後，他也應該要是repeating sequence
可是根據Peter的造法，因為xi有無限多個(每個xi都對應到一個不同的自然數i，而自然數
有無限多個)，
所以x在小數點後會有無限多個digits要differ，我們無法造出一個在finite period後，
會是repeating sequence的x。
應該要的x: 0.<-> | <------------------------------------>
finite repeating sequence (infinite)
period
事實上得到的x: 0.<------------------------------------------>
infinite period
所以造出來的x不會是有理數
因此x不會在X裡，即使他跟每個xi都不同
以上分享給大家
如果有錯誤還請幫我指出來感恩~ XD
ref:
上課講義
https://en.wikipedia.org/wiki/Cantor%27s_diagonal_argument
https://www.mathpages.com/home/kmath371/kmath371.htm
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 118.166.212.2 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1638271698.A.863.html
推
11/30 20:51,
2年前
, 1F
11/30 20:51, 1F
推
11/30 21:11,
2年前
, 2F
11/30 21:11, 2F
推
11/30 22:09,
2年前
, 3F
11/30 22:09, 3F
討論串 (同標題文章)
