基礎數學觀念-3: 與「零」有關的基本性質

接下來要整理的是「零」的性質，還有一些我們認為是理所當然的數學運算性質的推導，例如為什麼 0 乘以任何數結果都是 0 ？為何 3*(-2) = –6 等等。
要討論這些問題，必須要了解以下基礎知識：

• 向量空間（vector space）
• 皮阿諾公設（Peano axioms）

簡單的說，我們從小接觸的「數線」是歐幾里德空間（Euclidean Space，簡稱歐式空間），而歐式空間也是一種向量空間，其中每一個元素（也就是實數）就是向量空間中的一個向量（vector）。在向量空間中有以下重要的公設（等於是定義，是一組既定的規則，不需要證明）：

• 向量加法（實數加法）具有單位元素（0）：也就是說，任何數加上0等於任何數本身
  
• 向量加法（實數加法）具有反元素（加法反元素）：例如：3 的加法反元素是 -3（在前面加上一個負號），使得 3+(-3) = 0（加法單位元素）

事實上「減法」這個運算是利用加法來定義的，因為如此定義可以重複利用以上兩個基本公設，不需要另外為了減法再定義新的公設，由此可見數學的簡潔性，絕不重複發明相同的輪子！

（另一個例子是，在電腦的二進位世界中，負數也是透過正數來定義的，只要在正數最前面的bit上動個手腳就可以表達負數）

利用以上兩個公設可推導出以下結果：

• 任何實數乘以0都等於0 (e.g., 3*0=0 )
  
  
• 正實數乘以負實數結果是負實數 (e.g., 3*(-2) = –6)
  
  
• 若 ab=ac, 且 a!=0, 則 b=c
   

（第一個推導如果把0換成零向量，就是某年的研究所考題）

透過以上推導的過程，可以體會到如何以基礎理論，來逐步建構出更上層的理論，整個數學體系就是像這樣一步一步慢慢建立起來的。

以上的性質被證明出來以後，一個明顯的好處是可以加快計算速度，雖然從小的填鴨式教育讓我們認為這是理所當然的性質，但其實也是需要證明的！

備註：以上資料是我從向量空間（vector space）的講義裡面整理出來的，不太確定「一維歐式空間」跟「數系」有沒有差異，如果有錯誤的話煩請指正，謝謝 ^_^

補充資料：

• [證明] 1+1=2

同系列文章連結：

1. 數學歸納法的證明與應用
2. 集合論的性質：整數與偶數個數相同

基礎數學觀念-2: 整數和偶數的元素個數相同

繼上次整理過的數學歸納法的證明及應用之後，接下來要看跟集合論（Set Theory）這個基礎數學中的重要基礎有關的一些有趣性質。

集合論中元素個數相等


如何證明兩個集合X、Y元素個數相等？最直覺的想法是：把集合X和集合Y的元素個數算出來，若兩個集合元素個數相等，就得證。但總是會遇到天不從人願的時候，若剛好兩個集合X、Y為無限集（元素個數無限），就無法計算出集合X、Y的元素個數了。

因此數學家想出一個方法：利用消去法來證明。也就是將集合X中消去一個元素，就同時將集合Y中也消去一個元素。重複執行此動作，若可以將X與Y中的所有元素都消去的話，便可證明這兩個集合元素個數相等。（[Wikipedia] Cardinality: 1. Comparing sets）

 

這個將兩個集合中對應元素消去的動作，以函數的觀點來看稱為：一對一且映成函數。因此要證明兩個無限集的元素個數相等，就可轉換為設法在兩個無限集之間找到一個一對一且映成函數，只要能夠定義出這個函數，便可證明兩個無限集的元素個數相等。（像這樣將問題轉換為利用其他已知理論、工具來解決的能力，真的需要好好培養...)

以下的證明看完以後會有種「世界變了」的感覺：
（以下集合均為無限集）

• 證明整數和偶數具有相同的元素個數
   
  明明整數就包含單數和偶數，結果整數的個數居然還是跟偶數一樣多？那單數跑到哪裡去了？
  
  
• 證明整數與自然數具有相同的元素個數
  
  根據相同的推導方式得到的這個結論也很神奇，明明整數就包含負數和自然數，但是整數的個數還是跟自然數一樣多？那負數又跑到哪裡去了呢？
  
  
• 證明正奇數（odd number）是可數集合（正奇數與自然數具有相同的元素個數）
  
  最後這個結論也很有意思，自然數除了正奇數以外，當然包括了正偶數（even number），但最後又證明出自然數的個數和正奇數相同，那麼正偶數又跑去哪裡了呢？
  

雖然目前我還不清楚上述性質到底有什麼應用，但從探討的過程中對嚴謹度還有邏輯推理能力的建立是滿有幫助的（結論也挺有趣的）。數學是從一組公設中推導出一些定理，再由這些定理發展出相關的應用，而不是憑感覺的。

從以上性質的推導可以感受到數學的嚴謹性，一切都根據已知的定理、定義來推導，不摻雜一絲不理性的因素（e.g. 感覺、猜想），而這些人格特質對於程式的開發、除錯也是很重要的，如果不去仔細思考背後的原因，而老是將發生錯誤的原因歸咎到沒有放乖乖之類的迷信，那是很難進步的。

下一篇預計整理的是「零」的性質，還有一些我們認為是理所當然的數學運算性質的推導！

基礎數學觀念-1: 數學歸納法的證明及應用 (The proof of The Principle of Mathematical Induction)

相信高中的時候大家都學過數學歸納法（The Principle of Mathematical Induction），但我一直不知道數學歸納法這個定理本身也是需要證明的！（事實上在數學中除了公設以外，所有的定理都需要證明）

這個證明使用的是反證法（proof by contradiction），以及引理（Lemma）這個以前沒注意過的概念，推導的過程需要相當的邏輯能力，蠻精采的，因此趁機整理一下。

由於數學歸納法適用的問題是自然數命題，因此需要對自然數的基本性質有一定的了解，這部份的補充說明請參考中原大學數學系董世平教授所寫的數學歸納法一文中關於「皮阿諾公設」的說明。

在了解了自然數的基本性質以後，接下來看一下數學歸納法的證明過程（字蠻小的，可能需要另開視窗）：

(此證明在研究所考試中曾經考過：91交大資科, 93中原資工)

反證法真的很有趣，比起一般的數學推導（化繁為簡、化簡為繁），欲使用反證法需要有很強的邏輯觀念，最普遍的應用是證明存在性或無限多等無法明確描述的觀念有關的問題，例如：證明正整數中有無限多個質數。因為這個命題是「無限多」，因此無法直接將所有質數表列出來證明（根本表列不完），要驗證此命題是否正確，就必須先假設質數是有限個（故意假設錯誤），再推導出矛盾的結果，進而反證此命題為真。

（存在性問題也是類似的概念，因為沒辦法直接證明「不存在」，因此必須先假設存在，再導出矛盾的結果，進而反證確實不存在）

數學歸納法的應用除了證明一次方連加、二次方連加、三次方連加等公式以外，在 Wikipedia 上面還可以看到應用在 computer science, graph theory 中的變形（稱作 Structural induction (中文)），這部份我還沒學到，所以先略過不談 XD

數學歸納法在使用上要特別小心，若邏輯觀念不夠清楚，使用時可能會產生以下的錯誤，進而推導出奇怪的謬論--利用數學歸納法證明飯永遠吃不飽（原文請參考國立中央大學教學網）：


先想想看這個顯然是胡扯的證明到底錯在哪裡？好好思考之後再看一下解答，對於建立邏輯觀念有很大的幫助。（更多的數學歸納法使用錯誤範例請參考：大葉大學通訊與計算機工程學系的許介彥教授的數學歸納法使用上易犯的錯誤一文）

另一個更深入的應用是「如何找出劣幣」（原文請參考台大數學系蔡聰明教授的如何找出劣幣-簡介訊息與熵的概念一文），這跟最近唸資料結構/演算法時碰到的 Decision tree 也有關連，由於我沒辦法解釋的比蔡教授更清楚，所以這邊也略過不談 :p

數學歸納法的部份就先整理到這邊，下一篇預計整理的是「整數和偶數的個數相同」的相關問題。