簡要說明如何證明一個命題是不可證明的?

12-02

最好舉個例子唄

答一發～

首先糾正一下題主的表述問題，「不可證明」並不是一個嚴格的說法，我猜題主想說的是「不可證明也不可證偽」，等價的說法是獨立性；再者，單獨談論一個命題不可證明是沒有意義的，因為要證任何東西總要有公理，手裡有貨才能動手對吧。所以要說的應該是在給定的公理系統下，如果證明一個命題是既不能證明也不能證偽的。當然，如果不指明的話，一般這個公理系統指的就是ZFC了。

首先讓我們回憶一下一個命題是怎麼被證明的，假使我們想用ZFC證明命題p，一個很方便的方法是使用反證法，也就是假設ZFC+ $eg p$ ，然後如果能推出矛盾，那麼就說明p是對的。因此反過來，如果p在A中是不可被證明的，那麼必然有ZFC+ $eg p$ 無矛盾。單單這一條是不夠的，因為有可能ZFC蘊含 $eg p$ 對吧，所以還要加上ZFC+p無矛盾。兩個放在一起，就說明了p在ZFC中是不可證明也不可證偽的。如果我們把ZFC+p和ZFC+ $eg p$ 都看成是新的公理系統的話，證明某個東西是不可證明且不可證偽的，和證明某個公理系統是無矛盾的，其實是一回事。

現在我們已經把證明一個命題不可證明也不可證偽的，化歸成證明某個公理系統無矛盾了對吧。那麼怎麼叫無矛盾呢？簡單來說就是存在一個模型。這裡需要稍微想一下了，舉幾個非常非常不恰當的例子，比如實數公理為什麼是沒有矛盾的，因為有Dedekind分割模型對吧，再比如第五公設的否定與其他公設也是沒有矛盾的，因為有雙曲幾何的模型對吧。嚴格的表述和解釋應當是Godel完備性定理。

那麼現在要做的事情就是希望用ZFC造一個比如說ZFC+p的模型對吧，但這件事情是不可能的，連用ZFC造ZFC的模型都是不可能的，這是根據Godel第二不完備性定理。那麼這件事情是不是沒法做了？也未必。我們雖然無法證明ZFC+p沒有矛盾，但是我們可以證明的是，ZFC+p不會產生更多的矛盾。換句話說，我們可以證明的是，如果假定ZFC是無矛盾的，那麼ZFC+p也是無矛盾的。再換個理解方式，雖然ZFC的一致性是不可證明也不可證偽的，但是我們傾向於相信這一點，我們能夠足夠開心地使用ZFC，那麼如果能夠證明ZFC的無矛盾蘊含ZFC+p的無矛盾，那麼我們就能在不降低我們的開心程度的情況下使用ZFC+p。上面這些就是相對一致性的概念。絕對的一致性，也就是無矛盾是不可能證到的，但是相對一致性是我們可以證的。如果用模型的話來說，要證明相對一致性，簡單來說思路就是，假定我們手裡有一個ZFC的模型M，那麼可以從M出發造一個新的模型M"，使得在M"中成立ZFC+p.

這個地方的最經典的事情就是GCH在ZFC下是不可證明也不可證偽的，這裡的工作來自Cohn，大概是60年代的事情。ZFC+GCH的相對一致性是比較容易的，這個好像是Godel在早些時候解決的，而ZFC+ $eg$ GCH就困難多了，Cohn用他獨創的Forcing構造外模型來解決這個問題的。簡單來說，證明ZFC+GCH的相對一致性的時候是從M出發刪掉一些多餘的東西得到一個小模型，然而Forcing是從M出發進行擴張造一個外模型。力迫法我只是略有了解，這裡也不好多說，有興趣的讀者可以自行閱讀。

註：這裡就直接說ZFC了，也就是ZF加上選擇公理AC。但是我們知道AC也並不是那麼受歡迎的。對於那些對AC小心謹慎的人來說，我們可以告訴他們以下命題：ZFC相對ZF是一致的。這就意味著使用ZFC並不會比使用ZF引入更多的矛盾。這裡的工作應該是來自於Godel。甚至於我們可以再減，把ZF換成 $ZF^-$ ，就是ZF去掉基礎公理，這個事情也是對的。

大概就是證明 $(Gamma,alpha otvdashot)wedge(Gamma, egalpha otvdashot)$

如果把你的不可證，理解成獨立，我能想到的最簡單的例子如下
攷慮半羣公理
$forall x y z ((ab)c=a(bc))$
當然這個公理體系包含所有邏輯公理。
那麼以下的命題p在這個公理體系下就是獨立的
$forall x y (xy=yx)$
證明很簡單，找一個交換羣如（Z.+）和一個非交換羣如置換羣，讓p一真一假就可以了，這種方法是我們證明命題獨立的常見方法，有時甚至唯一方法。
連續統假設和選擇公理也是獨立的，但這兩個例子都太複雜，大部分情況好舉這兩個例子的人自己也是不太懂的。

參考哥德爾不完備定理

由於題主問的是「不可證明」，不是「獨立」，那麼答案便不複雜
1，假如你所用的公理化形式系統（「推導工具」）具有一致性
那麼，證明目標命題的否定（如果可能）是最簡單的途徑
根據定義，一致的形式系統不能在證明出其否定的同時證明原命題
完
2，假如你所用的公理化形式系統（「推導工具」）不具有一致性
這件事情是做不到的
既然形式系統不一致，那麼其中會包含某個矛盾式作為定理，然後從此定理出發能證明任何你能在該系統中表達的命題

G?del"s incompleteness theorems 說的大概就是這件事情，其證明中就是構造出了這麼一個命題。嚴格的邏輯推導需要先定義一個「形式系統」T，然後在該系統中構造出一個命題P，使得命題P在形式系統T中是不可被證明的。
可以參考康托爾、哥德爾、圖靈——永恆的金色對角線(rev#2) 中的介紹，我把關鍵的段落貼出來：

要證明哥德爾的不完備性定理，只需在假定的形式系統T內表達出一個為真但無法在T內推導出（證明）的命題。於是哥德爾構造了這樣一個命題，用自然語言表達就是：命題P說的是「P不可在系統T內證明」（這裡的系統T當然就是我們的命題P所處的形式系統了），也就是說「我不可以被證明」，跟著名的說謊者悖論非常相似，只是把「說謊」改成了「不可以被證明」。我們注意到，一旦這個命題能夠在T內表達出來，我們就可以得出「P為真但無法在T內推導出來」的結論，從而證明T的不完備性。為什麼呢？我們假設T可以證明出P，而因為P說的就是P不可在系統T內證明，於是我們又得到T無法證明出P，矛盾產生，說明我們的假設「T可以證明P」是錯誤的，根據排中律，我們得到T不可以證明P，而由於P說的正是「T不可證明P」，所以P就成了一個正確的命題，同時無法由T內證明！

如果你足夠敏銳，你會發現上面這番推理本身不就是證明嗎？其證明的結果不就是P是正確的？然而實際上這番證明是位於T系統之外的，它用到了一個關於T系統的假設「T是一致（無矛盾）的」，這個假設並非T系統裡面的內容，所以我們剛才其實是在T系統之外推導出了P是正確的，這跟P不能在T之內推導出來並不矛盾。所以別擔心，一切都正常。

如果不滿足於知道個大概，想要嚴謹，可以去找哥德爾的論文看咯。
PS：我有時候會想，數論中好多未被證明的猜想是否有可能就是不可證明的。可惜哥德爾不完備定理只是構造了這麼一個不可證明的命題出來，但給定一個命題，它卻不能告訴我們它是不是不可以被證明（這樣的功能似乎有點像停機問題了，應該是不存在的），所以還是有很多數學家把孿生素數猜想、黎曼猜想。。作為畢生目標，致敬！