※ 引述《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://webptt.com/m.aspx?n=bbs/Grad-ProbAsk/M.1638271698.A.863.html