2008/09/24

有理數可數

這是代數導論第一次作業的最後一題。我很自然地先(在 ghci 裡面)用 Haskell 做一遍再把它翻譯成比較像一般數學的語言 XD。

--
這應該可以當 Haskell 的入門練習題 XD。


程式碼就是很直觀地寫 XD。

import Data.Ratio

cluster n = [ (n - i, i) | i <- [1..n-1] ]

positive_rationals =
  map (uncurry (%)) . filter ((==1) . uncurry gcd) .
  concat . map cluster $ [2..]

bijection x | x == 0    = 0
            | odd x     = positive_rationals !! ((x-1) `div` 2)
            | otherwise = -(positive_rationals !! ((x-2) `div` 2))

--
有錯就代表我作業寫錯了 ─ 不過我在作業裡面的自然數從 1 開始算 XD。

Labels:

Blogger XOO9/24/2008 4:52 pm 說:

可以 po 出程式碼嗎?:P

 
Blogger Josh Ko9/24/2008 5:14 pm 說:

Updated. :)

 
Blogger XOO9/25/2008 6:34 pm 說:

喔喔 ...我以為是在 Haskell 證明出 function 是 bijection 的。

以前投機的作法是先弄 N x N 是可數的、可數集的子集是可數的,把 Q 塞到 N x N 裡去,搞定。(畢竟要實際造一個 bijection 不是每次都這麼直覺)

 
Blogger Josh Ko9/26/2008 1:44 am 說:

要證明的話就用 Agda 或 Coq 嘍。

看起來方法是一樣的。我真正寫的時候的確就是先把 N x N 拉成一個數列然後取這個數列的適當子數列,偷懶沒證「可數集的子集也可數」。不過我想代數導論的作業應該不用寫那麼嚴格吧 XD。

 
Blogger 單中杰9/26/2008 10:31 pm 說:

Enumerating the Rationals 還有更漂亮的方法喔。

 
Blogger Josh Ko9/27/2008 10:49 am 說:

啊,我都忘記有這篇了,之前沒仔細看 :P。

不知道用裡面的手法會不會讓這件事情在 Agda 裡面比較好證?再試試看嘍…

 

<< 回到主頁