[分析] 構造/非構造式證明

看板Math作者 (QQ)時間3年前 (2022/08/04 23:16), 3年前編輯推噓41(41推 0噓 165→)
留言206則, 9人參與, 3年前最新討論串1/2 (看更多)
想用下面這個例子詢問一下如標題的問題: 令r = 2^0.5 令a_n := n/(floor(n/r)) 則我們知道a_n→r 那這樣a_n算是2^0.5的構造性證明嗎? (或許要先定義採用的公設? 比如除法反元素與floor函數的存在性) ----------------------------------------------------------- 其實最初我想問的不知道怎麼下標題... 就是找"2^0.5的逼近方法", 一堆資料教你造遞迴/數列...的有理數逼近方式(假設叫b_n) 但是我問題就在於 a_n := n/(floor(n/r)) 也是一種逼近方式, 而且也是有理數列 那b_n跟a_n就差在"電腦能不能算"這個沒定義的名詞? 而a_n最大的不同是, 他把要逼近的r拿來用了 可是這步在邏輯上並沒有錯, 因為r本身存在了, 我只是要逼近他 我目前卡在沒有定義去區分a_n跟b_n有哪裡不同 只能用一些口述語言(電腦能不能算/把r拿來用...)來描述 有關於這區別的專有名詞嗎 謝謝~ -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 59.102.225.191 (臺灣) ※ 文章網址: https://www.ptt.cc/bbs/Math/M.1659626215.A.35B.html
推
08/04 23:42, 3年前 , 1F
不過你可以把n^2/2拿去看看介於哪兩個完全平方數之
08/04 23:42, 1F
→
08/04 23:42, 3年前 , 2F
間啊。
08/04 23:42, 2F
V大你是說其中一種b_n的造法吧? 還是說a_n可以改寫成這樣? 又或是說我的問題變成 "實務上如何實作a_n" ?
推
08/04 23:47, 3年前 , 3F
這是造a_n分母的方法啊。
08/04 23:47, 3F
→
08/04 23:49, 3年前 , 4F
例如25/2介於9和16之間，分母就是3。
08/04 23:49, 4F
→
08/04 23:50, 3年前 , 5F
a_5的分母是3。
08/04 23:50, 5F
對耶...這樣造a_n分母的方法跟其中一種b_n根本一模一樣XD 所以a_n算是...對的但是多此一舉的造法XD?
推
08/04 23:55, 3年前 , 6F
V 大的做法和你的做法的差別在於他把 r 的定義寫進
08/04 23:55, 6F
→
08/04 23:56, 3年前 , 7F
做法了, 但你的就只有「令 r 是這個無理數
08/04 23:56, 7F
→
08/04 23:56, 3年前 , 8F
然後求此式」, 實際上要怎麼計算你得依照定義去求
08/04 23:56, 8F
→
08/04 23:57, 3年前 , 9F
現在你的 r 只有開根號所以還好辦
08/04 23:57, 9F
→
08/04 23:57, 3年前 , 10F
如果是其他定義的話你要怎麼實際去算出來?
08/04 23:57, 10F
推
08/04 23:59, 3年前 , 11F
至於有點題外, 你提的「電腦能算」數學上有個定義叫
08/04 23:59, 11F
→
08/04 23:59, 3年前 , 12F
「可計算性」, 表示存在演算法能求出任意逼近
08/04 23:59, 12F
→
08/05 00:00, 3年前 , 13F
這跟你的問題稍微離了遠一點就是
08/05 00:00, 13F
以根號2的例子來說, V大的做法(或是說是其中一種b_n)是"可計算性" 又可以說是給我這個a_n一種可計算性的算法 如果今天r是zeta(5)的話, 我這種a_n造法目前是不可計算? 但是絕對是合邏輯的構造性證明? 應該說我想確定的名詞是: 構造性證明又分可計算性跟不可計算性? 而迄今有演算法發表的都分類在"可計算性", 但不排除那些"不可計算性"的在未來會變"可計算"? ※ 編輯: znmkhxrw (59.102.225.191 臺灣), 08/05/2022 00:06:17
推
08/05 00:47, 3年前 , 14F
ζ(5)就用傳統的級數定義嘍。其實要湊出你的a_n也
08/05 00:47, 14F
→
08/05 00:47, 3年前 , 15F
沒有那麼難。對每個n，先找一個離ζ(5)夠近的有理
08/05 00:47, 15F
→
08/05 00:47, 3年前 , 16F
數，然後去算n/那個有理數，再拿其整數部分作為分
08/05 00:47, 16F
→
08/05 00:47, 3年前 , 17F
母。
08/05 00:47, 17F
→
08/05 00:47, 3年前 , 18F
只不過很多餘而已……
08/05 00:47, 18F
聽你這麼說, 對於任何實數r, 如果已經有"可計算性"的構造有理數解q_n→r 則令 a_n := n/floor(n/q_n), 都可以得到a_n→r, 而且a_n也是可計算的 所以才說多此一舉? 如果是這個意思我完全可以接受 只是我這篇想要的區別是:(以下正確嗎?) 對於任何正實數r>0, a_n := n/floor(n/r) 都是構造解 -- (正確) 對於任何正實數r>0, a_n := n/floor(n/r) 都是可計算性 -- (未知) 而這個"未知"要變"正確"的話, 如果已經有"任何正實數都有可計算性解"這個定理 那就是正確的 我想要區分的就是以上這件事而已, 所以才說是名詞定義問題(?
推
08/05 01:16, 3年前 , 19F
你的「實數」是什麼呢？是柯西數列或遞增有界數列
08/05 01:16, 19F
→
08/05 01:16, 3年前 , 20F
的等價類就直接抓一條數列來用，是區間套等價類就
08/05 01:16, 20F
→
08/05 01:16, 3年前 , 21F
抓區間套的上下界來用，是戴德金切斷也可以用區間
08/05 01:16, 21F
→
08/05 01:16, 3年前 , 22F
找交集裡的有理數做數列。不管你的實數是哪種都可
08/05 01:16, 22F
→
08/05 01:16, 3年前 , 23F
以做出數列來啊。
08/05 01:16, 23F
問到這邊好像有點混亂... 還是說我最初的問題本來就沒定義, 所以才導致我無法明確地講出怪的點@@? 最初單純就是: 我想要讓電腦逼近任何實數r, 可是如果用a_n:= n/floor(n/r) 的話, 我根本還沒拿到r(雖然已經存在), 所以a_n行不通 但是邏輯上a_n這樣的造法卻是正確的 而之後你V大你上面的回答好像是在說任何實數r, floor(n/r)都可以算出來
推
08/05 01:33, 3年前 , 24F
你想要證明什麼命題啊?
08/05 01:33, 24F
目前應該是定義"問題"耶...就是我無法用既有定義去描述為什麼我覺得怪 舉個極端的例子, 今天如果有個問題是: 請寫出演算法造出有理數列逼近ζ(exp(π)), ζ是zeta fucntion 我如果寫: 令a_n := n/floor(n/ζ(exp(π))) 在數學上是100分, 但是在實作上是0分, 因為拿不到floor(n/ζ(exp(π))) 除非我又去補充floor(n/ζ(exp(π)))的演算法
推
08/05 04:56, 3年前 , 25F
從你寫的問題看起來，是數值分析問題？
08/05 04:56, 25F
→
08/05 04:57, 3年前 , 26F
也就是「求 zeta(exp(π))的有理數估計值以及誤差
08/05 04:57, 26F
→
08/05 04:57, 3年前 , 27F
範圍」？
08/05 04:57, 27F
→
08/05 04:58, 3年前 , 28F
然後是要能實現在計算機上的演算法？
08/05 04:58, 28F
確實如果能 " 證明所有實數都有計算機上的演算法逼近 "--(●) 那我原文造的a_n也就很容易寫出演算法實現(由上述定理演算法先逼近r, 之後trivial) 如果(●)這個敘述是有定義而且正確的, 那就能緩解我所謂的 " a_n邏輯是對的但實作(for any real number)很怪 "的感覺 ※ 編輯: znmkhxrw (59.102.225.191 臺灣), 08/05/2022 05:12:22
→
08/05 15:44, 3年前 , 29F
Computable reals 可以嚴謹定義啊
08/05 15:44, 29F
→
08/05 15:46, 3年前 , 30F
程式只有可數無窮多 當然會有不可計算的實數
08/05 15:46, 30F
理解~
→
08/05 16:43, 3年前 , 31F
有沒有可能是這樣寫比精簡?反正floor(n/r)如V大所說
08/05 16:43, 31F
還有 137 則推文
還有 6 段內文
→
08/09 13:34, 3年前 , 169F
啊，抱歉，我原本說的「上面的推文」並不是針對
08/09 13:34, 169F
→
08/09 13:35, 3年前 , 170F
hwanger 而是整體推文看下來的，想說為什麼這麼激烈
08/09 13:35, 170F
→
08/09 13:36, 3年前 , 171F
才想到我是接在 hwanger 下回的，有這層意思
08/09 13:36, 171F
推
08/09 14:50, 3年前 , 172F
呃...上面的爭論也就只是對 constructive proof的定
08/09 14:50, 172F
→
08/09 14:52, 3年前 , 173F
義有不同的觀點...畢竟不論哪個 floor function都是
08/09 14:52, 173F
→
08/09 14:53, 3年前 , 174F
可以用的
08/09 14:53, 174F
推
08/09 15:46, 3年前 , 175F
x大別在意XD 他也不是第一次腦補錯誤假設和態度激烈
08/09 15:46, 175F
→
08/09 15:46, 3年前 , 176F
了......過來人路過（菸）
08/09 15:46, 176F
→
08/09 16:37, 3年前 , 177F
08/09 16:37, 177F
→
08/09 17:38, 3年前 , 178F
www.ptt.cc/bbs/Math/M.1599859449.A.B4F.html
08/09 17:38, 178F
→
08/09 20:05, 3年前 , 179F
感覺8/6前的推文大家似乎都避開討論這篇的標題XD
08/09 20:05, 179F
→
08/09 20:07, 3年前 , 180F
^不
08/09 20:07, 180F
→
08/10 13:01, 3年前 , 181F
因為不知道原Po到底想問什麼(其實我到現在還是不知
08/10 13:01, 181F
→
08/10 13:01, 3年前 , 182F
道
08/10 13:01, 182F
推
08/10 18:41, 3年前 , 183F
我覺得甚至原 PO 自己也不是真的很清楚他的問題
08/10 18:41, 183F
→
08/10 18:41, 3年前 , 184F
到底在哪裡...「可計算性」這個名詞我很前面有推過
08/10 18:41, 184F
→
08/10 18:41, 3年前 , 185F
但當時我以為那和他的問題所在有一點遠
08/10 18:41, 185F
→
08/10 18:42, 3年前 , 186F
是在這之後來回討論了好幾次之後才發現
08/10 18:42, 186F
→
08/10 18:42, 3年前 , 187F
原來他的問題裡面可能還有這麼一層在
08/10 18:42, 187F
→
08/10 18:43, 3年前 , 188F
所以才有我在六號時的推文說一開始他有可能卡在那裡
08/10 18:43, 188F
→
08/10 18:45, 3年前 , 189F
會以為有點遠的原因其實跟他原文敘述有關:
08/10 18:45, 189F
→
08/10 18:45, 3年前 , 190F
這篇標題以及他的敘述是在講「構造式證明」
08/10 18:45, 190F
→
08/10 18:46, 3年前 , 191F
跟「可計算性」是好像有點有關但又好像不太一樣
08/10 18:46, 191F
→
08/10 18:46, 3年前 , 192F
(或者可能他口中的這種「構造」其實就是演算法?
08/10 18:46, 192F
→
08/10 18:47, 3年前 , 193F
只是個猜測就是了啦) 所以才會大家都在困惑
08/10 18:47, 193F
→
08/10 20:48, 3年前 , 194F
我感覺get到一點原PO的癥結點了 我認為是input/outp
08/10 20:48, 194F
→
08/10 20:49, 3年前 , 195F
ut的問題 如果你手上已經有(或"構造"出)r的值 那當
08/10 20:49, 195F
→
08/10 20:50, 3年前 , 196F
然可以用這個方法構造出你要的數列
08/10 20:50, 196F
→
08/10 20:55, 3年前 , 197F
沒有input的值 像h大的Re(ζ(–π+ie))一例 當然變
08/10 20:55, 197F
→
08/10 20:56, 3年前 , 198F
不出你要的序列 或許可以把原PO想要的"構造"定義成
08/10 20:56, 198F
→
08/10 20:58, 3年前 , 199F
(1)整數可"構造" (2)給一演算法且input可"構造"則
08/10 20:58, 199F
→
08/10 20:58, 3年前 , 200F
output也可"構造"
08/10 20:58, 200F
→
08/10 21:06, 3年前 , 201F
另外 你完全可以case by case證明特定floor(n/r)可
08/10 21:06, 201F
→
08/10 21:07, 3年前 , 202F
"構造" 就算floor(x) in general不可"構造" 例如你
08/10 21:07, 202F
→
08/10 21:10, 3年前 , 203F
的原例floor(n/2^0.5)可以找到不需2^0.5值的演算法
08/10 21:10, 203F
推
08/11 02:30, 3年前 , 204F
如果是這種「構造」定義的話那其實就是可計算數了
08/11 02:30, 204F
回覆以上: ------------ 沒錯就是我到目前認識的定義無法嚴格描述我的問題, 才導致總總猜測跟模稜兩可 這裡簡短整理綜合以上的資訊 <定義1> 構造性證明(constructive proof)有其嚴格定義 而非構造性證明稱作存在性證明 <定義2> 可計算性有其嚴格定義, 又稱做可構造性, 描述的對象是實數 <問題1> 以下關於《任何實數都存在有理數列逼近》的證明是構造性還是存在性證明 pf: 對任何實數r, 令a_n:=floor(nr)/n, 則a_n→r <答案1> 構造性證明(具體原因涉及<定義1>) <問題2> 對任何實數r, floor(nr)都可計算(採用<定義2>) <答案2> 否! 只有可數個實數r其floor(nr)才可計算(具體原因涉及<定義2>) 而我目前是看成"有演算法 = 可計算性" 如果不是的話, 還要再定義何謂"有演算法", 問題又會有分支 就先不引入"演算法"這個詞彙了 ※ 編輯: znmkhxrw (59.102.225.191 臺灣), 08/12/2022 02:16:41
推
08/12 17:58, 3年前 , 205F
「有演算法=可計算性」這玩意叫做 Church-Turing
08/12 17:58, 205F
→
08/12 17:59, 3年前 , 206F
thesis, 目前大家都認為這個等號是對的
08/12 17:59, 206F
原來有這個名詞, 謝謝L大~ ※ 編輯: znmkhxrw (59.102.225.191 臺灣), 08/18/2022 21:22:45
‣ 更多 znmkhxrw 的文章
文章代碼(AID): #1Yw-BdDR (Math)
‣ 更多 znmkhxrw 的文章
文章代碼(AID): #1Yw-BdDR (Math)