非構造性證明

非構造性證明是表述存在性的命題或定理的一種證明方式。

基本介紹

• 中文名：非構造性證明
• 外文名：Non-constructive proof
• 證明方式：表述存在性的命題或定理
• 證明的過程：不舉例而只證明語句是否正確
• 超越數：超越數是存在
• 學科：數理科學

簡介

非構造性證明是“表述存在性的命題或定理”的一種證明方式：

證明的過程中，不舉例而只證明語句是否正確。

非構造性證明很多時候依賴於排中律。數學結構主義數學不允許非構造性證明。

例一

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

超越數是存在。

證明

可以如下證明：

因為全體實數是不可數，而全體代數數是可數，所以超越數作為全體代數數的補集肯定是非空。由此得證。

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

非構造性證明很多時候依賴於排中律，數學結構主義數學是不允許非構造性證明的。

例二

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有必勝策略。