Re: [其他] 證明

[znmkhxrw (QQ)]

※ 引述《handsomepow (handsomepow)》之銘言：
: 證 =            =
:    N 小於不等於 R
: ("="集合的元素個數)
: 翻書有查到
: =           =
: R的個數為2^ N
: 還是不太了解該怎證


首先考慮 2^N 這個集合

原始的定義是：S is a set, then 2^S is the collection of the subset of S

so 2^N = {{n_1,n_2,..n_m....}│m€Natural number}

造一個函數f：2^N → U by f({n_1,n_2,..n_m....}) = (s1,s2,...,s_n,...)

                         , si = 1 if i =  n_j , j€natural number

                           si = 0 if i=/= n_j
U是由0,1所組成的數列集合

也就是說 U = {(s1,s2,...,s_n,...)│s_i=0,1 for all i€Natural number}

所以2^N 就可以看成 U 了

則可以證明2^N是不可數的

(pf：假設2^N可數，則2^N可以排成下列形式：2^N={a1,a2,a3....}

     where ai=(ai_1,ai_2,a_i3.....)€2^N , ai_j=0 or 1

     define a sequence t=(t1,t2,t3.....) by

     ti = 1 , if ai_i = 0

          0 , if ai_i = 1

     then we find ti+ai_i = 1 , for all i

     and t€2^N

     so        t         =         ai , for some i

     (t1,t2,....,ti,...) = (ai_1,ai_2,....,ai_i,....)

     we find ti = ai_i , →← to ti+ai_i = 1 , Q.E.D.)



會令2^N是因為這個數列從1開始，下標都是正整數，1 2 3 4 ....

然後每項都有0,1兩個選擇  所以有2^N種選擇

唉呀 反正可以互推  隨你怎麼想~~XD
--------------------------------------------------------------
現在如果題目只是要證明：R is uncountable

則考慮一個函數 f：2^N → [0,1] by f((s1,s2,...,s_n,...)) = 0.s1 s2 s3...

then f is one-to-one and f(2^N) 被[0,1]包含，所以f(2^N)是[0,1]的子集

假設R是可數的話，[0,1]也會是可數，f(2^N)也會是可數

(可數集的子集也會是可數)


但是f：2^N → f(2^N) is 1-1 and onto

if f(2^N) is countable , then 2^N is countable , →←

--------------------------------------------------------------

如果現在要證你要問的第一題：

如果card(N) = card(R)

代表存在1-1 onto的函數from N to R , 與R是不可數矛盾


如果card(N) > card(R)

代表存在1-1 的函數f： N into R

所以f：N→f(N) is 1-1 , onto , so f(N) is countable

而f(N) 被R包含 R是不可數  矛盾

---------------------------------------------------------------

再來是你問的第二題：

考慮二進位的方式

0 = 0 , 1/2 = 0.1 , 1/3 = 0.01.... , 1 = 0.111111111111111

則剛剛講的f變成1-1 and onto [0,1] (小數點擺在第一個不為零之前)

所以 card(2^N) = card([0,1])


再來我只需要證[0,1]與(0,1)間存在一個bijection就證完了

因為要造一個bijection from (0,1) to R 太簡單了


可是......................

光[0,1]與(0,1)間存在一個bijection 就花了我快兩個小時= ="



還是證出不出來^^"


不過同學google到了....

http://planetmath.org/encyclopedia/ClosedOpen.html


這是一個證(0,1) [0,1] (0,1] [0,1) 彼此間都存在bijection的證明

(可推得 R、R中任何open interval ,interval , half-open or half interval

 這五個彼此間都存在bijection)

第二個證明蠻好懂得


所以我們就有card(2^N) = card([0,1]) = card(R)


--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 1.169.140.139
※ 編輯: znmkhxrw        來自: 1.169.140.139        (09/22 02:17)
推 handsomepow :謝謝
→ handsomepow :2進位那邊不太懂 1/3=0.01... 是打錯嗎
→ znmkhxrw    :只是我懶得算而已= =,因為1/3=a*1/2+b*1/4+c*1/8...
→ znmkhxrw    :a,b,c...只能是0或是1所以a=0,b=1,之後如果c=1
→ znmkhxrw    :會超過1/3的話 則取c=0, 依序抓出d,e,...