[理工] 離散 - 費氏數可數

[jerry900287 (滷蛋)]

如標題

有一題是這樣的

以下何者為可數無限集?

(a){Fn}


而(a)選項是可屬無限集

有人有想過為什麼 費氏數列可以數嗎?

有兩種解法



第一種是因為 Fn 包含於 Z

這個我倒是可以接受 因為Fn = {0,1,1,2,...} 因為集合的關係可視為 {0,1,2,....}



第二種是因為可以寫成 1-1 且 onto 的函式

可是問題就來了,如果函式用 非遞迴的費氏數列的公式

帶入F1和F2都會對應到Z中的1

那不就形成多對一的函式??

有人對第二種有不同看法嗎?

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 114.32.75.152
※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1479296530.A.9E6.html
※ 編輯: jerry900287 (114.32.75.152), 11/16/2016 19:42:38
推 yorunohoshi: Fabonacci數列有closed form 可以跟正整數一一對應
你所說的closed form 是 Fn = 1/根號5 x ( ((1+根號五)/2)^n - ((1-根號五)/2)^n )嗎?
※ 編輯: jerry900287 (114.32.75.152), 11/16/2016 19:50:37
※ 編輯: jerry900287 (114.32.75.152), 11/16/2016 19:51:01
推 leoone: 是^n喔
啊..抱歉打錯 那如果是這公式 可是發現 如果你n分別帶1和2進入
那會有F1 = F2 = 1 這種多對一的狀況出現 就不是one to one 的函數了
這樣怎麼辦?
※ 編輯: jerry900287 (114.32.75.152), 11/16/2016 20:35:47
※ 編輯: jerry900287 (114.32.75.152), 11/16/2016 20:47:39
推 gary19941208: 或許是你沒找到正確的函式吧，但是第一種就證明了他
→ gary19941208: 可數，第二種你提出的只是一個不正確的函式，不代
→ gary19941208: 表他不存在
因為聽2016林緯老師說 可以用非遞迴的公式去做one to one 且 onto 的對應
讓我產生困惑QQ
※ 編輯: jerry900287 (114.32.75.152), 11/16/2016 20:58:56
推 windwaker112: 取f_0=0,f_1=0.5,函數取f_i=「f_i-1+f_i-2「,i>=2
→ windwaker112: 時「為ceiling,1-1且onto
→ windwaker112: 感覺怪怪的，分向定義也不太對
0.5 感覺怪怪的 , 不是根據定義要~N嗎QQ
※ 編輯: jerry900287 (114.32.75.152), 11/16/2016 21:30:15
推 windwaker112: 等等= =你搞錯了，是Fn->N要1-1&onto,{0,1,1,2,3,
→ windwaker112: 5,...}={0,1,2,3,5,8....}本身就可1-1&onto到N你
→ windwaker112: 是把函數的方向想反了XDDD
這樣也不對 如果你Input:1 那又怎麼知道他要對到1還是2 哈哈
→ ken52011219: Fibonacci 是sequence吧 ??
→ ken52011219: Function 跟 1-1 or onto並沒有直接的關係
→ ken52011219: 我去年也沒甚麼印象林緯有說過@@~
對~我去年也沒聽他說 可是我在期中複習聽他2016/07的影片有新加這段讓我困惑超久
推 gary19941208: 還有集合的觀點來看F1F2都是1，在集合裡算是一個元
→ gary19941208: 素，所以沒有問題
現在的問題變成是說能不能找到一個"公式" 讓這Fibonacci帶任何值都可以對應
→ a15151616: 我覺得題目有集合符號了 所以1-1 onto 不要把他當成費
→ a15151616: 氏數列來看 你的想法跟我一樣我也自己看很久
看來只好用包含於Z去解了~~

哈哈 感謝各位這麼熱心替我解答!!
※ 編輯: jerry900287 (114.32.75.152), 11/16/2016 23:39:07
推 yorunohoshi: 把n=2抓出來額外用個式子定義可能可以XD
推 yorunohoshi: http://i.imgur.com/BowzuSJ.jpg  這樣不知行不行..
→ yorunohoshi: .