2010-11-18

離散

請問有關於證明countable的問題

書上有提到若存在一個函數: A->正整數 為1-1函數,則A SET為COUNTABLE

但在證明(0.1)為UNCOUNTABLE
利用矛盾證法
假設(0.1)是COUNTABLE
正整數~(0.1)
存在一個函數f:正整數 -> (0.1) 為1-1且ONTO
然後之後矛盾了ONTO
但是為什麼不用去矛盾1-1呢?

2 則留言:

胖胖呆 提到...

假如你要用矛盾的話 你要把所有函數都找出來 然後證明你列的所有函數為FOR ALL
而且都不為1-1 才能正說(0.1)為UNCOUNTABLE 至於找函數的方法就得問助教了

若存在一個函數: A->正整數 為1-1函數,則A SET為COUNTABLE 為一個若P則Q的假設

線代離散助教(wynne) 提到...

在countable定義裡的定義域與對應域和這裡是相反的, 所以要看的應該是會不會 onto 而不是 1-1, 至於甚麼時候要看 1-1, 甚麼時候要看 onto, 稍微想一下你應該就會知道了

當我們在判斷可數時, 找函數的目的也只是想要知道 A 那個集合裡面的東西究竟會不會比 N 多, 至於甚麼是"一樣多", 就像老師說的, 你每掏一個銅板出來我就可以掏一個出來, 這樣我們有的錢就一樣多

這裡也是一樣, 假設對 A 裡面的每個 element 我們都可以指定一個唯一的編號給它, 那 A 的 cardinality 就不會比 N 要來得多, 所以假設今天有一個 a, 會使得你沒有辦法給它assign一個編號 (也就是不存在 onto 函數的情形), 那就表示 A 裡面的東西的個數確實要比 |N| 來得多, 其 cardinality 在無限的世界裡和 N 是不同等級的, 這樣的 A 就不為 countable