非構造性證明

非構造性證明是「表述存在性的命題定理」的一種證明方式:證明的過程中,不舉例而只證明語句是否正確。非構造性證明很多時候依賴於排中律數學構成主義數學不允許非構造性證明。

例一

編輯

A、B兩人進行這樣一個數學遊戲:在黑板上輪流寫下1到2000中的任意一個整數(含邊界,A先寫),但不能寫下任何黑板上已存在的數的因子。當一方不能寫出數字時該方則輸。問:誰有必勝策略?

證明

編輯
考慮一種新的遊戲:A'、B'在黑板上輪流寫下2到2000中的任意一個整數(含邊界,A'先寫),但不能寫下任何黑板上已存在的數的因子。當一方不能寫出數字時該方則輸。在這個遊戲中誰有必勝策略?
如果A'有必勝策略,那麼A在原遊戲中也採用這個策略。注意,1在以後的過程中再也不能寫上了(因為它是任何數的因子)。由於在新遊戲中A'有必勝策略,所以在原遊戲中,A有必勝策略。
如果B'有必勝策略,那麼A在原遊戲中先寫上1。這就相當於構建了上述新遊戲,B是新遊戲中的A',A是新遊戲中的B'。由於在新遊戲中B'有必勝策略,所以在原遊戲中,A有必勝策略。
綜上所述,A有必勝策略。

上述證明過程中並沒有找出具體的必勝策略,但是仍然證明了A有必勝策略。

例二

編輯

比如要證明一個簡單的命題:

超越數存在。

證明

編輯
因為全體實數不可數,而全體代數數可數,所以超越數作為全體代數數的補集肯定非空。證畢。

證明過程並沒有找出任何一個超越數,但是依然證明了上述命題的正確性。

相關條目

編輯