Re: [分析] 證明不可數的過程

[Eeon (Chaotic Good)]

※ 引述《drinks9216 (drinks)》之銘言：
: 各位前輩及同好 ~ 午安
: 前幾天老師在台上，證明不可數，過程有點不太懂
: 故PO上來請教前輩與同好
:                 ∞
: 題目 : Prove A={Σ a_i / 3^i | a_i 屬於 {0,2} , i=1,2,3,..... } is uncountable
:                 i=1
: <pf>
: If not , A={x_1 , x_2 , x_3 , .......}
:          ∞                        ∞
: ∴ x_1 = Σ a_1i / 3^i   ,   x_2 = Σ a_2i / 3^i , .......
:          i=1                       i=1
:         ∞
: Let x = Σ y_i / 3^i
:         i=1
: y_i=｛ 0    if a_ii = 2
:     ｛ 2    if a_ii = 0      ,      ∴ x 屬於 A
: ∵ x≠x_i  , i = 1,2,3.......
: ∴ x 不屬於 A     -><-
: ∴ A is uncountable
: --------------------------------------------------------------------
: 從 y_i 開始就看不太懂 ， 為何 x 屬於 A ??? x 不屬於 x_i
: 請各位前輩和同好解惑
: 感謝 <(_ _)>


某個集合可數的意思就是說，這個集合的跟正整數集之間存在一個一一對應的關係；
一一對應意思就是可以找到一個映射是onto且one to one 。
反之，則將此集合稱做不可數。
因此，要證某集合不可數就是要說明，不可能找到一個一一對應的映射。

論述上，使用反證法，假設存在一個這樣的映射，
使得A的元素和正整數集有一個一一對應的關係；
因此A的元素可以排排站，表示成：x1,x2,x3,...


我們現在的論述是反證法，所以目標就是要去抓一個A裡的東西出來，
說這東西沒有被列到。
找的這個東西，稱之為x，x要跟 x_1 不一樣，
所以就x的第一個位置就故意取跟x_1的第一個位置唱反調，
同理，x的第二個位置跟 x_2 的第二個位置唱反調，
x的第三個位置跟 x_3 的第三個位置唱反調，以此類推。

比方說，假設x1,x_2是像下面這樣：

      x1 =  0 0 0 2 0 2 0   .....
      x2 =  2 0 2 0 0 0 0   .....
      x3 =  0 2 2 0 2 0 2   .....
      x4 =  0 0 0 2 0 2 2   .....
　　　　.          .          .
        .          .          .

決定出來的
       x = 2 2 0 0...........

對排排站裡的任意元素 x_k而言，
這樣造出來的x的第k個位置，跟 x_k 的第 k 個位置不一樣，
因此 x 跟 x_k　都不相等 for all k=1,2,3,...
所以 x 的確就沒有被某個正整數編號到，排排站時，並沒有被排到，
跟我們一開假設說 A可數（A裡的元素可跟正整數有一個一一對應）　矛盾。

本質上，這做法跟證實數不可數的時候是一樣的，都是對角線法而已。

--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 111.185.73.7
※ 編輯: Eeon            來自: 111.185.73.7         (01/07 19:11)
推 znmkhxrw    :想請問一下  對角線法應該建立在"其中一個a_i"不一樣
→ znmkhxrw    :則x_i就不一樣
→ znmkhxrw    :要如何說明這件事
→ znmkhxrw    :意思是說，先不論可不可數性，我從這個集合挑出x,y
→ znmkhxrw    :x=Σa_i , y=Σb_i
→ znmkhxrw    :如果a_i=/=b_i  則x=/=y  WHY~~??  因為分母跳很大?
→ znmkhxrw    :因為這個成立的話  才確保對角線法的x_1=/=x_2=/=...
推 suhorng     :我想可以這樣理解：若A是countable,那我們所取的 x
→ suhorng     :應該要出現在 A 的排排站的某處
→ suhorng     :但是由於我們的 x 的取法, 他不可能出現在這任何某處
→ suhorng     :所以矛盾. 剩下的可能性只有：不存在這樣的對應
推 znmkhxrw    :對壓! 所以我上面一堆推文就是要防止：
→ znmkhxrw    :a_i不同 可是收斂到一樣的值
→ znmkhxrw    :如果這件事不可能發生  自然排排站法就可以
→ znmkhxrw    :如果這件事情可能發生，那就算x與x_i的排法都不一樣
→ znmkhxrw    :也可能收斂到同一個值~
直觀的說法：
這邊分子的取值差為 2，使得兩串一旦某個位置不一樣後，
後面無論再如何無窮級數式地追趕，
也無法補足第一個不同位置所造成的差距：2/3^i

在實數（更精確地：考慮[0,1]區間）的對角線法裡，
為了避免這種收斂到同值的問題（e.g:0.499999999...... 和0.500000.....），
所以造x的位數取值時候，不去取 9，
比方說：取 4，當x_i該位數不是4，
　　　　取 5，當x_i該位數不是5。

一些嚴謹的說明操作，用limit的東西，寫一寫即可。
※ 編輯: Eeon            來自: 111.185.73.7         (01/07 21:27)
→ Sfly        :把相同的數不同表法 也一起編號就可以避免
→ drinks9216  :感謝前輩回應與回文，懂了 非常感謝 <(__)>