作者raincole (冷雨)
看板Math
標題[集合] 函數有多少個？
時間Fri Dec 31 18:26:30 2010
例如說這樣一個集合S={f|f:N->N}，它的基數是多少？
我想應該不可能跟自然數一樣多吧，但是它和實數一樣多嗎？
實數是0.a1a2a3...這樣的型式，上述的f也可以表示成這樣(如f(x)=2x可以表示成0.246..
)，但是實數的a是在一個有限的範圍內(如十進位表示時0<=x<=9)，f的a則有可數無限種，
感覺上S似乎比R大才對，不過我知道對集合基數大小的直覺觀感通常是錯的……
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 113.61.198.13
1F：推 mzhrqoc01 :整數可以用質因數分解成2^a*3^b*.....而a,b,c是整數 12/31 18:42
2F：→ mzhrqoc01 :而整係數多項式可以用x^n的係數表示成（a,b,c,...） 12/31 18:43
3F：→ mzhrqoc01 :所以這個多項式可以和整數一一對應--我曾經看過有書 12/31 18:44
4F：→ mzhrqoc01 :是這樣說的，僅供參考。 12/31 18:45
不太領悟耶……我不懂你要表達的意思，這跟我的問題有關嗎？
5F：推 ntnusliver :原PO說的 欠一個方向 12/31 21:54
6F：→ ntnusliver :想辦法 把S裡的東西都去1-1對到 R裡面 12/31 21:54
呃，這個我還知道，問題是我無法想出這個對應，也無法證明他不存在（汗）
（我知道怎麼證明「N的所有子集的集合」跟R一樣大這個……但是這和我的原問題又不太
一樣)
7F：→ yhliu :f:A->B, A中每一元素可以對應到B中任一元素, 因此其 12/31 21:54
8F：→ yhliu :基數同於 B^A. [0,1)中實數的小數展式相當於N->{0,1} 12/31 21:56
9F：→ yhliu :的函數, 其基數同於 2^N, 而 2^N 同於 R. 12/31 21:56
10F：→ yhliu :寫錯...二進位才是 N->{0,1}, 12/31 21:58
11F：→ yhliu :十進位是 N->{0,1,...,9}. 12/31 21:58
12F：→ yhliu :N->N 的對應 = ∪(N->{1,2,...,n}的對應). 12/31 22:00
13F：→ yhliu :所以 N^N 的基數應該是同於 R. 12/31 22:00
14F：→ yhliu :好像說不通...orz 12/31 22:02
※ 編輯: raincole 來自: 113.61.198.13 (01/01 01:14)
15F：→ mzhrqoc01 :我的意思是可不可以把（0,2,4,6,8,...）對應到 01/01 03:09
16F：→ mzhrqoc01 :(2^0)*(3^2)*(5^6)*(7^8)，這樣似乎就可以把函數f對 01/01 03:11
17F：→ mzhrqoc01 :應到整數上。 01/01 03:11
18F：→ mzhrqoc01 :上面應該是(2^0)*(3^2)*(5^6)*(7^8)*..... 01/01 03:12
19F：→ mzhrqoc01 :推完第二次文才發現我想錯了....................orz 01/01 03:27
20F：推 ppia :計自然數集合的基數為 N_0 原po你說的那個集合基數為 01/01 11:59
21F：→ ppia :N_0^N_0 ≦ (2^N_0)^N_0 = 2^(N_0 xN_0) = 2^(N_0) 01/01 12:01
22F：→ ppia :而顯然 2^(N_0) ≦ N_0^(N_0) 由Schroeder Bernstein 01/01 12:02
23F：→ ppia :知 #(|R)=2^(N_0)=N_0^(N_0) 01/01 12:03
24F：→ ppia :上面那些指數律的操作雖然都只是形式上的 但其實對 01/01 12:04
25F：→ ppia :基數都成立, 另外 N_0 x N_0 = N_0 可以直接證明 01/01 12:05
26F：→ ppia :也就是證明"a countable union of countable sets is 01/01 12:05
27F：→ ppia :again countable" 但其實對任何無限集A都有 01/01 12:06
28F：→ ppia :#(AxA)=#A 01/01 12:06