Re: [代數] 哥德爾定理在數論真實的例子？

看板Math作者 (煦)時間4年前 (2020/06/07 14:00), 編輯推噓11(11推 0噓 30→)
留言41則, 2人參與, 4年前最新討論串2/2 (看更多)
（代PO）朋友沒有PTT帳號，委託我代PO。原信如下： 雖然我沒有去查 Erdos 究竟指的為何，但我認為他說的可能是 Paris-Harrington 定理 或 Goodstein 定理。Paris-Harrignton 定理跟拉姆齊理論有關，而 Erdos 本身就是這 領域的人，所以可能知道。Erdos 也可能會知道 Goodstein 定理，因為定理與圖論有關 連，兩位證明者將問題轉化成圖論問題，將 Goodstein 序列比喻成九頭蛇，蛇頭被斬下 還會再長出新的蛇頭來，比原先多。此問題便在問海克利斯每次只能斬一個蛇頭，那麼他 能否有朝一日砍完所有蛇頭。(沒很熟兩個定理，所以有勞人進一步去查) 兩個定理都已經被證明單憑 Peano 算術系統證不出來，非得靠更強的證明系統如 ZFC 系 統才可證出。既然 ZFC 系統能證出來，假若 ZFC 系統沒有問題，不會不一致，那麼這兩 個定理所言為真（一階邏輯的健全性 soundness 所致）。這兩個命題為真，但是 Peano 算術系統證不出來，這便是哥德爾不完備的實例。 接下來我想討論 chemmachine 的說法，因為對我有些地方我不是很明白，所以可能有勞 chemmachine 說得詳細一點。另外我對某些說法不是很滿意，想要點出來討論一下。 自身不可證偽的資料有：連續統假設。哥德爾定理，羅素悖論。 我覺得說「自身不可證偽」不是很妥當。因為就我解讀，「偽」與「真假」有關，但證明 系統與真假無關，系統只是一堆符號的組合而已。我們所謂的證明就只是依照特定規則排 列符號而已，我們能排出或是排出，就僅此而已。證明無須牽扯真假，命題能否被證出與 命題是否真假需分別看待。命題有可能無法被證明或證明為否（取決於該證明系統形式如 何），但命題要不真要不就假。所謂的真假是後來所賦予，依一些共識賦予其意思。所以 我覺得說「自身不可證偽」不是很妥當。 以連續統假設 CH 為例。哥德爾便構造了一個滿足 ZF 公設的數學結構，而那數學結構滿 足連續統假設，所以根據一階邏輯的健全性（如果系統能證出語句 φ，那麼 φ 會在每 個滿足公設要求的結構都正確），ZF 無法證出 ~CH 。而哥德爾的學生柯亨便接手哥德爾 的工作，造出一個不滿足連續統假設的數學結構，證明 ZF 無法證出 CH（同樣跟健全性 有關）。連續統假設在每個數學結構要不真要不就假，ZF 系統的問題只是無法好好分開 這些結構，分成滿足、不滿足兩類，讓系統本身得以捕捉其中一類的特性就好。證明系統 也就因此無法證明 CH 或證明 ~CH 。 附註：其實到目前為止，我們還不知道 ZFC 的數學結構長的如何。雖然有些書會用 V 馮 紐曼宇宙指稱這個結構，但是事實上這個結構太大不是個集合，不滿足邏輯學家對 ZFC 數學結構的要求。如果我們真找到 ZFC 的數學結構，其實我們就證明了 ZFC 一致（可憑 一階邏輯的健全性得出這結論）。所以這個問題仍舊擱置著。至於哥德爾與柯亨所作只是 給出集合論宇宙的部份結構，而這結構便能滿足 ZFC 要求，並不是真的找到。現今這門 學問稱作 inner model theory。 此外，「自身不可證偽」對我而言有點不太清楚。然後您舉了連續統假設。哥德爾定理（ 是指不完備定理嘛？），羅素悖論作為例子。我不太理解三者與前述間的關係。可能有勞 您再解釋一下。 連續統描述基數N^(j)<2^N 中間沒有其他基數，N^j和 2^j基本是遞迴數字系統。指數是由乘積遞迴定義而來 乘積由加法遞迴定義而來。 我不確定是否有其它書這樣寫，但我所讀的書(Enderton，Elements of Set Theory)並非 如定義： https://imgur.com/kNpIRiq
老實說，我有點好奇怎麼用遞迴定義基數，因為「能夠遞迴」本身也要證明。以加法或乘 法的遞迴定義為例，Enderton 便是先證明有如是遞迴函數存在，再去定義其： https://imgur.com/MYgRABw
https://imgur.com/ArbfeZV
https://imgur.com/6doOKzC
Enderton 便在書上（138頁，Cardinal Arithmetic 一節）寫道：「The approach（用遞 迴定理定義運算） is unsuitable here.」 就我解讀，用遞迴定義基數運算會有些問題 ，因為這樣需證明有如是遞迴函數存在。而這函數不單只是自然數上的遞迴函數而已，它 還得是超限遞迴函數（transfinite recursion function）。但除非能排序，否則沒有道 理談遞迴。然而就我所知，超限遞迴本身僅會用在序數上，不會用於基數。 我有三個問題有待解惑：「自身不可證偽」的明確意思為何；連續統假設、哥德爾定理、 羅素悖論與「自身不可證偽」的關係為何；能否用遞迴定義基數。有勞您能回答這些問題 了。 -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 42.77.74.35 (臺灣) ※ 文章網址: https://www.ptt.cc/bbs/Math/M.1591509611.A.160.html
推
06/07 18:02, 4年前 , 1F
beth number 可以遞迴上去 但 aleph number 比較難
06/07 18:02, 1F
→
06/07 18:04, 4年前 , 2F
Aleph_1 = the cardinality of set of all sets
06/07 18:04, 2F
→
06/07 18:04, 4年前 , 3F
with cardinality Aleph_0
06/07 18:04, 3F
推
06/07 23:44, 4年前 , 4F
問題一自身不可證偽改為自身存在定理
06/07 23:44, 4F
→
06/07 23:44, 4年前 , 5F
不可證偽。這是哥德爾的敘述
06/07 23:44, 5F
→
06/07 23:44, 4年前 , 6F
我漏打了
06/07 23:44, 6F
推
06/07 23:47, 4年前 , 7F
然後哥德爾定理，本質是把羅素悖論改的複雜。因為
06/07 23:47, 7F
→
06/07 23:47, 4年前 , 8F
羅素悖論看起來很像狡辯。你說的圖論例子是模仿的。
06/07 23:47, 8F
→
06/07 23:47, 4年前 , 9F
最原始
06/07 23:47, 9F
→
06/07 23:47, 4年前 , 10F
的就是羅素悖論。故事很多，比如說誰幫理髮師剃頭，
06/07 23:47, 10F
→
06/07 23:47, 4年前 , 11F
我說的是謊話這類
06/07 23:47, 11F
推
06/07 23:51, 4年前 , 12F
連續統我本來也不知道為啥和羅素悖論有關，是做到超
06/07 23:51, 12F
→
06/07 23:51, 4年前 , 13F
冪函數時，用遞迴做加法和乘法和指數定義。加法發現
06/07 23:51, 13F
→
06/07 23:51, 4年前 , 14F
加法當作一階，乘法當做二階，指數當做三階，那二點
06/07 23:51, 14F
→
06/07 23:51, 4年前 , 15F
五階呢？遞迴不好推導。
06/07 23:51, 15F
推
06/07 23:55, 4年前 , 16F
然後康托的基數用一對一，N=N^2
06/07 23:55, 16F
→
06/07 23:55, 4年前 , 17F
=N^3=……,2^N是N的冪集。
06/07 23:55, 17F
推
06/07 23:57, 4年前 , 18F
N*N寫成N +_2 N 2^N寫成2+_3 N
06/07 23:57, 18F
→
06/07 23:58, 4年前 , 19F
康托問在+2和+3間是否有其他基數。
06/07 23:58, 19F
→
06/07 23:59, 4年前 , 20F
當然你可以猜2.5但2.5次階加法不好定義
06/07 23:59, 20F
推
06/08 00:01, 4年前 , 21F
這本身和哥德爾數論本質都是遞迴，解決之道是延拓，
06/08 00:01, 21F
→
06/08 00:01, 4年前 , 22F
延拓能不能承認2.5階會有兩種結果。我想你說的zfc
06/08 00:01, 22F
→
06/08 00:01, 4年前 , 23F
應該想法如此，詳細過程我不是很熟。
06/08 00:01, 23F
推
06/08 00:07, 4年前 , 24F
不完那個N^j是N=N^2=N^3=……的意思，我只是照抄連
06/08 00:07, 24F
→
06/08 00:07, 4年前 , 25F
續統假設而已。
06/08 00:07, 25F
推
06/08 00:21, 4年前 , 26F
更正：然後那個
06/08 00:21, 26F
推
06/08 00:40, 4年前 , 27F
第三個問題，基數序數不同，但可以當做猜定理的思
06/08 00:40, 27F
→
06/08 00:40, 4年前 , 28F
路，就是先射箭再畫靶
06/08 00:40, 28F
推
06/08 01:50, 4年前 , 29F
你的第二個問題，哥德爾定理的想法是修改羅素悖論
06/08 01:50, 29F
→
06/08 01:51, 4年前 , 30F
成數論的形式。連續統假設在zfc下不可證明為真或偽
06/08 01:51, 30F
→
06/08 01:51, 4年前 , 31F
。所以希爾伯特問題說部分解決。而且用
06/08 01:51, 31F
→
06/08 01:51, 4年前 , 32F
超冪函數的觀點也是和遞迴有關。和哥德爾定理類似。
06/08 01:51, 32F
→
06/08 01:51, 4年前 , 33F
程式也是因為遞迴結構而產生存在不可證明的問題。
06/08 01:51, 33F
→
06/08 02:31, 4年前 , 34F
您可看維基條目哥德爾定理，電腦科學，連續統假設，
06/08 02:31, 34F
→
06/08 02:31, 4年前 , 35F
羅素悖論是不是都有關就知道我所言非虛。我的閱讀
06/08 02:31, 35F
→
06/08 02:31, 4年前 , 36F
資料有
06/08 02:31, 36F
→
06/08 02:31, 4年前 , 37F
““天才之旅“的“康托與他的超限王國”，
06/08 02:31, 37F
→
06/08 02:31, 4年前 , 38F
set theory and related topics,的基數序數章節“
06/08 02:31, 38F
→
06/08 02:31, 4年前 , 39F
”微積分的推廣，加減乘除的推廣與統計擬合“的代
06/08 02:31, 39F
→
06/08 02:31, 4年前 , 40F
數部分還有網路上的羅素悖論條目，哥德爾定理條目，
06/08 02:31, 40F
→
06/08 02:31, 4年前 , 41F
連續統條目，以及個人思考整理。
06/08 02:31, 41F
‣ 更多 s1290961 的文章
文章代碼(AID): #1Ut89h5W (Math)
‣ 更多 s1290961 的文章
文章代碼(AID): #1Ut89h5W (Math)