Re: [問題] 無限多的自然數跟質數誰比較多？

※ 引述《E7lijah (InsfirE喚焰)》之銘言： : ※ 引述《zax8419 (小火馬)》之銘言： : : 直接說結論: 一樣多 : : 姑且身為一個有靠數學招搖撞騙的小廢廢 應該可以提供個簡單的解答 : : 但我知道西洽存在112數學系拿卷畢業 然後現在應該在國外讀博的版友 : : 偶而也有112數學系畢業 然後讀電機碩的版友 : : 相比之下我就只是個廢物Q_Q : : 關於自然數與質數誰比較多 這個驗證方式應該分為兩個步驟 : : 1.質數是否為無限多個? : : 2.若質數為無限多個 那質數與自然數如何比較? : : 首先1. : : 質數有無限多個。 : : 其證明方式非常簡單 用最基本的反證法即可 : : 因"質數有無限多個"與"質數為有限多個"為相反的命題 : : 故先假設"質數為有限多個" : : 則我們可以從小到大 將所有質數編號 p_1,p_2,p_3......p_n p_n為最大的質數 : : 而若我們寫出一個大數N為所有質數的乘積 : : 則會發現N+1不能被以上所有的質數給整除(餘數皆為1) : : 那麼就可以得出N+1亦為一個質數 且比p_n還要大 與最初的命題矛盾 : : 所以可以得知"質數有無限多個" Q.E.D : : 再來2. : : 無限多個的自然數 與 無限多個的質數 其數量一樣多 : : 非常簡單 : : 我們可以說 : : "第一個"自然數為1 "第一個"質數為2 : : "第二個"自然數為2 "第二個"質數為3 : : "第三個"自然數為3 "第三個"質數為5 : : ...... : : 以此類推 其實這個想法要寫的嚴謹一點還有點意思 你已經做出 "排序"這件事了 當然這裡很明顯的用大小來做排序了 其實已經用到 最小上界存在 且 最小上界存在 自然數與質數的集合中 排序這件事之後在有理數跟自然數的比較中 也可以用到 當然那時候排序就不會用大小這件事 這樣還是不夠證明二個個數是一樣的 : : 所有"第N個"自然數都可以對應到一個數 同時"第N個"質數亦可對應到一個數 : : 那麼儘管有點違反直覺 但實際上論"個數" 則自然數的個數與質數的個數是一樣多的 : : 或者說 只要能找到任何一個無法同時存在有"第M個"自然數 但沒有"第M個"質數的狀況 這樣講的話 可以用強數學歸納法? N=1的時候 自然數集合 |N 跟質數集合 |P 各自的最小下界inf 1 跟2 對應 將1跟2各自放進 一個集合 A_1 跟B_1 架構 N=2 的二個集合 是{a in |N but a not in A_1} 跟{n in |P but n not in B_1} 一樣各自取inf 做對應 N=M 時 N=M+1 一樣可以做 所以一樣? 其實沒有特別記得 這樣做行不行 : : 就能說自然數的個數 與 質數的個數不相同 : : 這種概念在所有的"可數集合"均成立 : : 進階一點就像"有理數的的個數"也與"正整數的個數"是一樣多的 : : 但是當命題拉到不是可數集合的時候 就不會那麼簡單了 : : 就像無理數的個數有無限多個 正整數的個數也有無限多個 : : 但無理數的個數卻是遠大於正整數的個數 : : 不過要去說明就懶了 大概也沒人在乎 : : 數學嘛 就是這麼反直覺 唉 歡迎成為 數學教徒(?) : 其實你第一個證明有點瑕疵 : 令 N = 1 + p_1*p_2*...*p_k的作法 : 我能舉個反例： : 1 + 2*3*5*7*11*13 = 30031 = 59*509 : 此時N可以表達成兩個不為{1,N}元素的自然數之乘積 : 不符合質數的定義，新造出的N不是質數 : 你當然可以說那我不管N了，此時59與509反而是你新發現的質數 : 但原本的證明敘述仍有瑕疵就是了 你看看別人的假設 要所有的質數 那59 509 這二個數對你來說是不是質數? 要說瑕疵也先把前提看清楚 : 有一個概念相似但比較嚴謹的證明： : 同樣假設存在有限個質數p_1, p_2,..., p_i,..., p_k : i屬於{1, 2,..., k} : 則對於任何自然數n≧2 : 有p_i|n (p_i能整除n) : 這邊需要一個引理： : 若a|b，且a|c : 則a|(b-c) 你的條件很明顯的不夠 b c 都是a的時候會成立嗎? b c有額外條件吧? b c 一樣的時候會成立嗎? : 這個證明很簡單 : 令b = x*a : c = y*a : b-c = (x-y)*a，其中x,y皆為整數 : 得a|(b-c) : 回到質數無限多個的證明 : 令n = 1 + p_1*...*p_i*...*p_k : 可推得p_i|(n-1) : 再結合前述的p_i|n 這條哪來的? 後面先不看 : 我們有p_i|[n-(n-1)]=1，即p_i|1 : 但p_i必定≧2，不可能整除1，明顯矛盾 : 得證質數的數量不可能有限，即質數有無限個 : 再回到質數跟自然數是否一樣多的問題 : 數學上比較兩個集合的個數大小，可以用一一對應原則 : 概念上就是班上有40個人，老師不需要從1數到40 : 只要視線快速掃過每個座位都有人，就能確認座位數=人數 : 令R跟S為某兩個集合 : 若你能找到一個一一對應關係使每個R的元素對應到S : 則|R|≦|S| (|R|代表R集合的大小) : 而當|R|≦|S|與|R|≧|S|同時成立時， : 則|R|=|S| : 也就是說你若能R→S和S→R兩個方向上都找到一一對應關係的話， : 那麼R跟S這兩個集合的大小相同 : 以上敘述對有限集合與無限集合皆適用 : 現在我們令N為自然數集合，P為質數集合 : 明顯地，|P|≦|N|，每個質數都能對應到一個自然數 : 所以我們只需要證明每個自然數也能對應到一個質數， : 就能說明質數的數量跟自然數一樣多 : 這可以用費馬數做證明： : 第n個費馬數可以表達成 : F_n = 2^(2^n) + 1 : 已知任兩個費馬數皆互質，即任兩個費馬數的最大公因數是1， : 也就是說任兩個費馬數必不會有共享的質因數 : 那麼對於每個費馬數F_n，我找出他最小的質因數P_n， : 這個P_n必不等於其他費馬數F_m的最小質因數P_m : 於是，對每個自然數n，我能對應到一個費馬數F_n，又再對應到一個質數P_n : 我找到了將每個自然數都對應到一個質數的方法 : 所以|N|≦|P| : 再結合|P|≦|N| : 得證|P|=|N|，即質數的個數與自然數一樣多 : btw我也不是數學系，有誤煩請糾正 -- 克蘇魯? https://imgur.com/eAa4UOI https://www.ptt.cc/bbs/C_Chat/M.1658237873.A.160.html -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 101.12.53.201 (臺灣) ※ 文章網址: https://www.ptt.cc/bbs/C_Chat/M.1684289543.A.6F4.html