作者 comp2468 (ilikemiku)標題 Re: [問題] 無限多的自然數跟質數誰比較多？時間 Wed May 17 10:12:20 2023
※ 引述《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 (臺灣)
※ 作者: comp2468 2023-05-17 10:12:20
※ 文章代碼(AID): #1aP3W7Rq (C_Chat)
※ 文章網址: https://www.ptt.cc/bbs/C_Chat/M.1684289543.A.6F4.html
※ 同主題文章:
Re: [問題] 無限多的自然數跟質數誰比較多？
05-17 10:12 comp2468
※ 編輯: comp2468 (101.12.53.201 臺灣), 05/17/2023 10:31:38
推 E7lijah: 嗯a|b那邊確實該加個b不等於c的條件，或不失一般性直接令b>c 這樣b-c出來是正數比較好看
在這裡
則對於任何自然數n≧2
有p_i|n (p_i能整除n)
59跟509那個我也在推文討論了一下，就算此時最大的質數是13，59是合數，那麼30031可以拆成兩個合數乘積，不也有點奇怪嗎3F 05/17 10:40
→ cmrafsts: ???你們為啥不在整數裡面做11F 05/17 10:44
→ comp2468: 3樓，所以最大的質數不是13啊，你自己就是在舉反例了12F 05/17 10:51
推 Bugquan: 你不就是要證明質數無窮多，你已經找到比原先那個還要大的質數了啊13F 05/17 10:54
推 E7lijah: 那對你來說此時比13更大的質數是什麼？15F 05/17 10:54
推 KaedeHondo: 在原命題的假設下 當你做到13時就已經結束了 可以直接Q.E.D 本來就沒有59是不是質數合數的問題
再往後討論下去就是連命題根本的定義都推翻 沒意義啊16F 05/17 10:54
→ E7lijah: 不符合此時質數定義的59？509？還是可以被拆成兩個合數乘積的30031？
喔等等你們的數線只到13嗎 13後面都沒有數字？19F 05/17 10:55
推 siro0207: 因為該原文已經假設13為最大的質數 那你拿出59 509不就23F 05/17 10:59
→ E7lijah: 我的想法中，比較好的證明是無限個自然數中只有有限個質數，自然數還是延伸至無限的，所以59 509 30031這些數依然存在，只是它們當下不是定義中的質數24F 05/17 11:00
→ siro0207: 證明了13不為最大的質數? 按照這種方法 永遠都能找到更大的兩個質數來整除27F 05/17 11:00
→ E7lijah: 回siro，對啊 所以我在原文提供了59是新的質數的選項，但此時就不是N=30031做為新的最大質數29F 05/17 11:01
--