Re: [離散] 數學歸納法、強數學歸納法的n=1
: 推 LPH66 : 並沒有無關喔, 後一問題是原問題改變 base case 10/27 16:50
: → LPH66 : 後一問題能用原論證證明表示原論證本來就無誤 10/27 16:51
: → LPH66 : 問題完全只在 P(1)→P(2) 無法用原論證證明 10/27 16:51
: → LPH66 : 但就因為這一個無法證明使得結論變為荒謬 10/27 16:52
: → hwanger : 原本問題是"對於任意n匹馬 這n匹馬顏色都相同" 10/27 17:34
: → hwanger : 形式是" for all x1,x2,...xn, Q(x1,x2,...,xn)" 10/27 17:34
: → hwanger : 改過的問題是"對於任意n匹馬 若任意兩兩顏色相同 則 10/27 17:34
: → hwanger : 這n匹馬顏色相同" 10/27 17:34
: → hwanger : 形式是 "for all x1,x2,...,xn, if for all i,j A(x 10/27 17:34
: → hwanger : i,xj), then Q(x1,x2,....,xn)" 10/27 17:34
: → hwanger : 第2個問題只要固定其中一匹馬 大家都跟這匹馬相比即 10/27 17:34
: → hwanger : 可 10/27 17:34
: → hwanger : 就算硬要用數學歸納法證 兩者的induction hypothesi 10/27 17:34
: → hwanger : s也不同 10/27 17:34
: → hwanger : 第一個P(n):對於任意n匹馬 這n匹馬顏色都相同 10/27 17:34
: → hwanger : P(n)推P(n+1):若"任意n匹馬 這n匹馬顏色都相同" 則 10/27 17:34
: → hwanger : "任意n+1匹馬 這n+1匹馬顏色都相同" 10/27 17:34
: → hwanger : 第二個P(n):對於任意n匹馬 若任意兩兩顏色相同 則這 10/27 17:34
: → hwanger : n匹馬顏色相同 10/27 17:34
: → hwanger : P(n)推P(n+1):若"對於任意n匹馬 若任意兩兩顏色相同 10/27 17:34
: → hwanger : 則這n匹馬顏色相同" 則 "對於任意n+1匹馬 若任意 10/27 17:34
: → hwanger : 兩兩顏色相同 則這n+1匹馬顏色相同" 10/27 17:34
: → hwanger : 用到的假設和要證的東西已經不同了 你說用類似的想 10/27 17:34
: → hwanger : 法證ok 但直接用原論證一定是不行的 10/27 17:34
: → hwanger : 最簡單的看法就是 從n+1匹馬選出n匹馬後 在第一個 10/27 17:34
: → hwanger : 情況 這n匹馬就是同顏色的 但在第二個情況 你必須 10/27 17:34
: → hwanger : 先check任意兩兩相同顏色 才能下結論這n匹馬同顏色 10/27 17:34
: → hwanger : 兩者推到選出來的n匹馬同顏色的方式不同 10/27 17:34
: → hwanger : 荒謬的是"對於任意n匹馬 這n匹馬顏色必然相同" 10/27 17:39
: → hwanger : "對於任意n匹馬 若兩兩顏色相同 則這n匹馬顏色必然 10/27 17:39
: → hwanger : 相同"則完全沒問題 10/27 17:39
: → hwanger : 兩個問題形式已經不同 說是相關勉強可以 但並不是 10/27 17:45
: → hwanger : 誰基於誰 我認為無關 就是他們形式上已經無關 前者 10/27 17:45
: → hwanger : 有問題的證明 也沒辦法直接給後者用(實際上也不需要 10/27 17:45
: → hwanger : ) 10/27 17:45
我這樣寫好了:
P(n): 「任意 n 隻馬的顏色全都相同」
那原始命題 (命題 A) 就是「證明對所有自然數 n, P(n) 成立」
修改後的命題 (命題 B) 就是「已知 P(2) 成立, 證明對所有自然數 n, P(n) 成立」
在原始問題的歸納法推論中, 沒有問題的推論是 「對於 n≧2, P(n)→P(n+1)」
單單使用這個歸納推論以及「已知 P(2) 成立」即可證明命題 B 成立
而你使用不同的方法證明了命題 B 只不過再一次強調了命題 B 是沒問題的
那為什麼命題 A 就有問題? 正是因為中間缺的這根骨牌 P(1)→P(2)
P(1) 顯然成立沒有問題
但只有 P(1) 成立無法推出 P(2) 成立, 其理由即是最原 PO 說的「無法重疊」
所以命題 A 的這個證明就有問題了
--不過一個證明有問題並不全然表示原題是錯的
這裡命題 A 是錯的的原因我們能用別的方式說明 (eg. 舉個反例)
而命題 A 是錯的但命題 B 是對的這個事實
(這兩件事都可以用跟原數歸證明無關的的證明得到←這是重點)
正是在說明原數歸證明命題 A 的誤區恰好就是 P(1)→P(2) 的推論有問題
如此而已
--
◢ ˊ_▂▃▄▂_ˋ. ◣ ▅▅ ▅▅ ι●╮ █▄▄▄▄▄
▍./◤_▂▃▄▂_◥ \'▊ HARUHI █████ <■┘ ▄▄▄▄▄▄▄
▎⊿ ◤◤◥█◥◥█Δ ISM By-gamejye ¢|\ ▌▌▌▌▌▄▌▌
▏ζ(▏●‵◥′●▊)Ψ ▏ █ ⊿Δ ▄▄▄ ▄▄▄▄
█/|▊ 〃 、 〃▋ |\ ▎ ハルヒ主義 █▄▄▄█▄▄
◥◥|◣ ‵′ ◢/'◢◢S.O.S 世界を大いに盛り上げるための涼宮ハルヒの団
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 106.1.234.196 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Math/M.1603793252.A.4C5.html
※ 編輯: LPH66 (106.1.234.196 臺灣), 10/27/2020 18:07:38
改用「命題」稱呼, 不然都在寫問題東問題西的整個看起來很有問題 orz
※ 編輯: LPH66 (106.1.234.196 臺灣), 10/27/2020 18:11:59
→
10/27 22:17,
5年前
, 1F
10/27 22:17, 1F
→
10/27 22:17,
5年前
, 2F
10/27 22:17, 2F
→
10/27 22:17,
5年前
, 3F
10/27 22:17, 3F
→
10/27 22:18,
5年前
, 4F
10/27 22:18, 4F
→
10/27 22:18,
5年前
, 5F
10/27 22:18, 5F
→
10/27 22:19,
5年前
, 6F
10/27 22:19, 6F
→
10/27 22:19,
5年前
, 7F
10/27 22:19, 7F
→
10/27 22:20,
5年前
, 8F
10/27 22:20, 8F
→
10/27 22:20,
5年前
, 9F
10/27 22:20, 9F
→
10/27 22:20,
5年前
, 10F
10/27 22:20, 10F
→
10/27 22:21,
5年前
, 11F
10/27 22:21, 11F
→
10/27 22:21,
5年前
, 12F
10/27 22:21, 12F
→
10/27 22:22,
5年前
, 13F
10/27 22:22, 13F
→
10/27 22:22,
5年前
, 14F
10/27 22:22, 14F
→
10/27 22:23,
5年前
, 15F
10/27 22:23, 15F
→
10/27 22:23,
5年前
, 16F
10/27 22:23, 16F
→
10/27 22:24,
5年前
, 17F
10/27 22:24, 17F
→
10/27 22:24,
5年前
, 18F
10/27 22:24, 18F
→
10/27 22:25,
5年前
, 19F
10/27 22:25, 19F
→
10/27 22:25,
5年前
, 20F
10/27 22:25, 20F
→
10/27 22:26,
5年前
, 21F
10/27 22:26, 21F
→
10/27 22:26,
5年前
, 22F
10/27 22:26, 22F
→
10/27 22:26,
5年前
, 23F
10/27 22:26, 23F
→
10/27 22:27,
5年前
, 24F
10/27 22:27, 24F
→
10/27 22:27,
5年前
, 25F
10/27 22:27, 25F
→
10/27 22:27,
5年前
, 26F
10/27 22:27, 26F
→
10/27 22:33,
5年前
, 27F
10/27 22:33, 27F
→
10/27 22:35,
5年前
, 28F
10/27 22:35, 28F
我覺得你從頭到尾一直都糾結在命題 A 當中
命題 B 確實和命題 A 是不同的題目 (就是你說的不同宇集)
引我很久以前回同一件事的推文就是:
※ #1K8ckEa5 (Math)
: → LPH66 : 你可以想像一個平行世界, 那裡任兩隻馬都確實同色 09/25 01:07
: → LPH66 : 這樣根據這個推論我們就能得到那世界的所有馬都同色 09/25 01:08
命題 B 的討論範圍是一個平行世界
但是推論的理由卻除了基礎不同外和命題 A 是一字不差
那這裡會扯命題 B 出來的原因就是: 能夠證出命題 B 的這些個推論是合法的
也就是 P(2)→P(3) P(3)→P(4) 等等這些推論都是對的
而命題 A 的推論只因為多了 P(1)→P(2) 整個論證就出現矛盾了 (推出不成立的事)
因此我們能知道命題 A 這個歸納證法失敗的根本且唯一理由就是 P(1)→P(2) 不成立
====
要說這裡有什麼違反直覺的地方大概也就只有 P(2)→P(3) 了吧
在命題 A 的世界裡因為 P(2) 不成立, 所以 P(2)→P(3) 這個推論是虛空地真
但是這並不表示在 P(2) 成立的命題 B 的世界裡這個推論是否成立
而事實上它成立了: 在命題 B 的世界裡能夠證出所有馬都同色的理由
本質上的核心正是 P(2)→P(3), 不論你用什麼方式證明
所以 P(2)→P(3) 這個在命題 A 的世界裡「違反直覺」的推論其實根本沒違反什麼東西
因為同一個理由在命題 B 的世界裡是很合理也很合邏輯的推論
你因為一直糾結在命題 A 當中所以才會認為這裡有個「違反直覺」的地方
====
再換句話說: 「P(2)→P(3) 成立」跟「P(2) 成立」跟「P(3) 成立」是三碼子事
其中一些成不成立和另外一些成不成立除了由於肯定前件/否定後件導致的推論之外
我們無法對其說些什麼; 特別地, 在命題 A 中第二項不成立無法說明第一項不成立
但在命題 B 中前兩項成立, 故能由肯定前件得到第三項成立
同樣的, 「P(1)→P(2) 成立」跟「P(1) 成立」跟「P(2) 成立」同樣是三碼子事
但因為肯定前件的推論, 在命題 A 中第二項成立與第三項不成立能得到第一項不成立
如此而已
※ 編輯: LPH66 (106.1.234.196 臺灣), 10/28/2020 00:40:50
→
10/28 01:45,
5年前
, 29F
10/28 01:45, 29F
→
10/28 01:45,
5年前
, 30F
10/28 01:45, 30F
所以我就只是單純把我當時講的話引來用而已
→
10/28 01:46,
5年前
, 31F
10/28 01:46, 31F
→
10/28 01:47,
5年前
, 32F
10/28 01:47, 32F
→
10/28 01:48,
5年前
, 33F
10/28 01:48, 33F
→
10/28 01:49,
5年前
, 34F
10/28 01:49, 34F
→
10/28 01:49,
5年前
, 35F
10/28 01:49, 35F
→
10/28 01:50,
5年前
, 36F
10/28 01:50, 36F
→
10/28 01:50,
5年前
, 37F
10/28 01:50, 37F
還有 157 則推文
還有 8 段內文
→
10/29 01:45,
5年前
, 195F
10/29 01:45, 195F
→
10/29 01:46,
5年前
, 196F
10/29 01:46, 196F
→
10/29 03:42,
5年前
, 197F
10/29 03:42, 197F
→
10/29 03:42,
5年前
, 198F
10/29 03:42, 198F
→
10/29 03:42,
5年前
, 199F
10/29 03:42, 199F
→
10/29 03:42,
5年前
, 200F
10/29 03:42, 200F
→
10/29 03:42,
5年前
, 201F
10/29 03:42, 201F
→
10/29 03:42,
5年前
, 202F
10/29 03:42, 202F
→
10/29 03:45,
5年前
, 203F
10/29 03:45, 203F
→
10/29 03:45,
5年前
, 204F
10/29 03:45, 204F
→
10/29 03:45,
5年前
, 205F
10/29 03:45, 205F
好, 我們不要用馬跟正整數, 就更抽象一點好了:
給定一個可數集合 U, 以及在其上的一個等價關係 R
P'(n) 表示對任何 U 中大小為 n 的子集, 當中任兩元素都有這個等價關係
(寫成邏輯式子就是:
P'(n) := ∀W⊆U, |W|=n → ∀x,y∈W, R(x,y)
這個樣子)
然後我們提出兩個命題
命題 A': 在上述前提下, 證明對所有自然數 n, P'(n) 成立
命題 B': 在上述前提下, 若還已知 P'(2) 成立, 證明對所有自然數 n, P'(n) 成立
以及對這兩個命題使用數學歸納法的「證明」
我也可以用這個抽象寫出你的命題 S:
命題 S': 對所有自然數 n > 1, P'(n)→P'(n+1)
並且注意到命題 A' 和 B' 的數學歸納法「證明」確實都是在嘗試使用命題 S' 進行歸納
那在考慮這兩個證明的合法性時
命題 A' 因為命題 S' 只有在 n > 1 成立, 因此漏掉了中間的一個鏈子 P(1)→P(2)
所以這個數學歸納法不成立
命題 B' 則沒有問題, 從已知的 P'(2) 開始運用命題 S' 即可推論下去
因此這個數學歸納法成立
那如果我們套上實際的問題
對馬的問題, U 是所有馬的集合, 等價關係 R 是兩隻馬同色
對你的正整數問題, U 是所有正整數的集合, 等價關係 R 是相等
這就成了我們前面一直爭論的命題 A 和命題 B 了
--我猜你應該會在這裡要我等一下, 說我這個抽象不成立
那我請問: 我們就先不看命題 B'
上面的抽象以及命題 A' 和 S' 在這個抽象裡的敘述
是否和我們所討論出來的「命題 A 為何數歸不成立」是一致的?
就只有把 U 代換成所有馬的集合, 把 R 代換成兩隻馬同色而已
那何以單單多了一個「P'(2) 為真」前提的命題 B' 就無法接受了呢?
如果能接受命題 B', 對命題 B' 進行相同的代換就是命題 B 了啊!
若不是, 它又不是在什麼地方?
我這樣子的抽象和代換究竟混淆了什麼概念?
是所討論的集合 U? 是所討論的等價關係 R? 還是 P'(2) 這個敘述本身?
====
延伸一下 wohtp 提的「模型背後的代表意義」
我是否可以說, 我被指稱「混淆」的
是否就是「U := 正整數 和 R := 相等 代進命題 B' 就會因為代表意義有問題」?
數學上時常有這樣子的討論
有一個符合某些條件形成的集合, 我們不知道集合裡有沒有東西
但我們會去討論集合裡東西會有什麼額外的性質
如果實際上這個集合裡後來真的發現沒有東西
那請問先前討論這個集合裡東西的性質的討論是否也會「因為代表意義」失去價值?
※ 編輯: LPH66 (106.1.234.196 臺灣), 10/29/2020 04:20:34
推
10/29 04:22,
5年前
, 206F
10/29 04:22, 206F
→
10/29 04:27,
5年前
, 207F
10/29 04:27, 207F
→
10/29 04:27,
5年前
, 208F
10/29 04:27, 208F
→
10/29 04:27,
5年前
, 209F
10/29 04:27, 209F
推
10/29 05:14,
5年前
, 210F
10/29 05:14, 210F
→
10/29 05:14,
5年前
, 211F
10/29 05:14, 211F
推
10/29 05:16,
5年前
, 212F
10/29 05:16, 212F
※ 編輯: LPH66 (106.1.234.196 臺灣), 10/29/2020 05:52:12
→
10/29 11:34,
5年前
, 213F
10/29 11:34, 213F

→
10/29 11:35,
5年前
, 214F
10/29 11:35, 214F

→
10/29 11:35,
5年前
, 215F
10/29 11:35, 215F

→
10/29 11:35,
5年前
, 216F
10/29 11:35, 216F

好的, 那顯然這就是我從一開始就形式化不夠徹底造成的誤會了
我的命題 B 甚至命題 B' 從頭到尾形式上就只是你的 (4) 而不是 (1)
命題 B 和命題 B' 從頭到尾就沒想要證 (1)
(而且本來就證不出來啊, 理由你已經羅列出來了)
我引一下最一開始提起這個命題的 TC 的推文:
: → TimcApple : 如果題目改成「若任兩匹馬顏色一樣 10/27 13:08
: → TimcApple : 則所有馬顏色一樣」這樣用數歸證就不會錯 10/27 13:08
: → TimcApple : 畢竟起點是 2 不是 1 了 10/27 13:08
我們對於命題 B 的討論一直都是有「P(2) 是前提」這件事的
而依你的回應, 產生誤會的點是在於
: 你們寫下來的證明形式化後是 (2) 和 (3)
是啊, 要用數學歸納法證 (4) 當然寫下來是 (2) 和 (3)
只不過 (2) 的理由不是 axiom/theorem 而是 assumption (所以最後變成 (4) 的前件)
你認為我所混淆的應該就是 ↑ 這兩個 ↗ 東西 -- (2) 在證明當中的理由 -- 吧
但因為我的命題 B 從頭到尾都是 (4) 所以我才會搞不懂你在說我把什麼搞混了
====
那回到最一開始「不直觀」、「類比」的議題
我們持的「這個論證沒有不直觀」、「兩個是類似題」的理由其實就是
用在了命題 A 這證明的 (3) 也同樣用在了命題 B (4) 的那證明
而 (4) 的那證明完全沒有問題
--也就是我們在說: 「(3) 這是很普通的數學歸納法的證明」
「但命題 A 這證明在用 (3) 時因為沒注意到 (3) 在 n = 1 不成立所以失敗」
「因為你看, 同樣用 (3) 的命題 B 那證明就沒問題了」
※ 編輯: LPH66 (106.1.234.196 臺灣), 10/29/2020 23:30:56
→
10/30 01:58,
5年前
, 217F
10/30 01:58, 217F

→
10/30 01:58,
5年前
, 218F
10/30 01:58, 218F

→
10/30 01:58,
5年前
, 219F
10/30 01:58, 219F

所以現在是要來一個一個拆我的文章裡的邏輯錯誤嘛, 那就來 (躺上烤架)
先說我並沒有不高興
因為我的回文風格就如前面說過的已經是會去嘗試理解我回的人問題在哪來解決
不說別的, 整件事過了三四天我還在這裡跟你丟球也是因為這樣
但是一個人做事總不可能只有讚沒有倒讚嘛
那既然有這麼一個好機會讓我吃幾顆觸身球我當然很樂意
====
(i) 我提「平行世界」講的其實是: 命題 A' 和命題 B' 所討論的 U 是不同的集合
因為符合命題 B' 的前提 (包含 P'(2) 成立) 的 U 本來就不會是命題 A' 在討論的
上一行我加了個括號說包含 P'(2) 成立, 也就是說在我的心目中
命題 A' 的討論目標是「集合 U 有關係 R」這樣的 U
命題 B' 的討論目標是「集合 U 有關係 R 且 P'(2) 成立」這樣的 U
因此「前提上」A' 的 U 和 B' 的 U 不一樣, 所以才會說「平行世界」
這裡就先跳到你的 (iii)
--從這裡看起來, 對你來說這整件事從頭到尾都只有一個 U, 一個 model
然而我在做的論證不知從哪裡飛來一個 P'(2) 成立再去做因此是荒謬的
這也可以從你後來舉了正整數的例子出來可以見之
那所以是我對「討論的 model」這東西有什麼誤解嗎?
這裡也可以帶到 (iv), 而我覺得這裡就是我們的認知不同的關鍵點:
我是否能夠因為我的論證裡只討論符合所有前提的事
而就直接把這些「符合所有前提的事」的集合做為我的 model?
還是我必須要先提出一個在我的討論中所使用到的大範圍性質的 model
(抱歉這個「大範圍性質」我一時想不到有什麼精確一點的數學說法...)
然後對它提出「若這 model 有某某前提的話」?
這其實關係到 (iii) 中究竟論證前提是否能寫做├ P'(2)
我認為可以, 因為在我的 model 這是 model 的性質, 自然成立;
你認為不行, 因為 P'(2) 在命題 B' 中始終是 assumption
因此只能寫成 (4) 的 P'(2)├ ……
這樣一來, 你說我的命題 B' 是 (1) 這件事也是合理的了
因為它真的是 (1), 只是在討論的 model 上不一樣
--不過也或許, 以上這一大段都是我的誤解
不然這個解釋無法說明你為何一直認為我的 P'(2) 是天外飛來一筆:
因為你也同意命題 A' 和命題 B' 的 model 不同
那為何要把命題 B' 的 (1) 這個形式放在命題 A' 的 model 中
然後再說我不知哪裡飛來 P'(2)?
是我對「model」這個概念有什麼根本上的誤解嗎?
再來, (v) 這裡就是一個我認為由於我的行文風格造成的問題:
因為我簡化了很多東西造成文章裡會有讓人以為有某種 implication 但那卻是不該有的
例如最上面的
: 而命題 A 是錯的但命題 B 是對的這個事實
: 正是在說明 (以下略)
這裡就是你在說的我想用 (4)「證明」(3) 吧
但我原意只是將兩個證明方式拿出來對比, 指出共同點的 (3)
再藉 (4) 的論證有效但「命題 A」的論證無效指出其無效的原因在哪裡而已
那這裡就可以回到 (ii)
我其實很早就同意命題 B' 不需要數學歸納法就能做了, 也是在最上面同一個地方:
: (這兩件事都可以用跟原數歸證明無關的的證明得到←這是重點)
那所以我的行文重點一直都嘗試著重在「這兩個命題其使用數學歸納法的證法的對比」
只不過由於前面提到的行文簡化的關係, 會讓人以為我在說 (4)「證明」(3)
這點確實是我的寫法不當
最後, (iv) 裡有另一件事我還沒提到: 哪些論證是否直覺的論述
我會認為 (3) 並沒有違反直覺其實心裡並沒有在想著 U 是馬還是正整數還是什麼
因為沒有預設 U 是什麼東西, P'(2) 就單單只是個為真的前提而已
不會因為哪個特定的 U 使得 P'(2) 為假就認為令它為真會反直覺
--我討論的就是 P'(2) 為真的那些東西嘛, 考慮其他的做什麼...
這又接回到這次回應最開始的地方
我其實就只是為了指出在 P'(2) 為真的地方這論證形式並沒有什麼反直覺之處
這才提出了一個 model 不同且這個 model 有著 P'(2) 為真這性質的命題 B' 出來
你要說這是我改變前提然後說它不反直覺我可以承認
我的目的本來就是藉這個對比說這個證法是 OK 的而已
※ 編輯: LPH66 (106.1.234.196 臺灣), 10/30/2020 07:48:54
→
10/30 12:32,
5年前
, 220F
10/30 12:32, 220F

→
10/30 12:32,
5年前
, 221F
10/30 12:32, 221F

→
10/30 12:32,
5年前
, 222F
10/30 12:32, 222F

非勝不可的戰役...嗎; 不可否認我一開始是有想說服你的念頭
但後來 (至少上一次回應) 我的期望已經變成來說服我吧
只是看起來你已經被我反覆的立場改變給搞亂了
(我的立場在回應之間確實有變, 所以才會一下子說 (1) 一下子說 (4))
那在我釐清自己的立場之前再討論下去對事情並不會有幫助
就在這裡打住吧--我會繼續思考到底什麼立場才是對的, 我先前的問題在什麼地方
※ 編輯: LPH66 (106.1.234.196 臺灣), 10/31/2020 06:45:50
→
10/31 12:13,
5年前
, 223F
10/31 12:13, 223F

→
10/31 12:13,
5年前
, 224F
10/31 12:13, 224F

→
10/31 12:13,
5年前
, 225F
10/31 12:13, 225F

→
10/31 12:14,
5年前
, 226F
10/31 12:14, 226F

→
10/31 12:53,
5年前
, 227F
10/31 12:53, 227F
→
10/31 12:54,
5年前
, 228F
10/31 12:54, 228F
→
10/31 12:54,
5年前
, 229F
10/31 12:54, 229F
討論串 (同標題文章)
本文引述了以下文章的的內容:
完整討論串 (本文為第 2 之 2 篇):