## 2007年8月31日 星期五

### 可數性（countability）

1←→0、2←→1、3←→ -1、4←→2、5←→ -2、6←→3、7←→ -3、……

0、1、-1、2、-2、3、-3、……

(1) 0 和 1 之間的所有實數（不包括 0 和 1）是可數的

0.1, 0.2, 0.3, ..., 0.9, 0.01, 0.02, ..., 0.99, 0.001, 0.002, ..., 0.999, 0.0001, ...

(2) 所有以整數為系數的多項式是不可數的

1 ←→ a10 + a11x + a12x2 + a13x3 + ...
2 ←→ a20 + a21x + a22x2 + a23x3 + ...
3 ←→ a30 + a31x + a32x2 + a33x3 + ...
4 ←→ a40 + a41x + a42x2 + a43x3 + ...
......

#### 2 則留言:

Marco_Dick 提到...

Prove that the power set of N is countable.

Reason:

For each subset of N, the sum of the elements is an integer k. For any k, the number of subsets that sum to k is finite (simple combinatorial argument). Let the collection of the subsets that sum to k be called P_k. Then the power set of N is just union of P_k for k from 1 to infinity, which is a countable union of finite sets, so is countable.

Kahoo 提到...

haha... I like this "proof"... it took me more time to figure out what's wrong than in my two "proofs", although the trick is essentially the same.