數學歸納法

數學歸納法（proof by induction）是集合論裡的定理（theorem）。這個定理用在語句邏輯上大概是這個樣子：

想證明某一類型的合法語句都具有某個性質P，就得先為該類型的語句們用自然數排序（例如句子裡面沒有連接詞的語句們的排序是0，有一個連接詞的語句們的排序是1之類的），然後就可以用數學歸納法了。

先證明排序中最小的語句們（例如，如果是用語句的連接詞數量來排序，那麼最小的排序是0；如果是用推論的長度來排序，那麼最小的排序是1）有性質P（base case），然後假設排序n的語句們有性質P（inductive hypothesis），再利用假設證明排序為n+1的語句們也有性質P（inductive case）。這樣就能得到我們想要的結論：任何排序的語句都有性質P。

有三種使用數學歸納法的方式，弱歸納法（weak induction）、強歸納法（strong induction）和良序歸納法（well-ordering induction）。但是我不清楚良序歸納法是什麼就不寫了。

弱歸納法

• Base Case：證明最小的排序有性質P。
• Inductive Hypothesis：假設排序為n的語句有性質P。
• Inductive Case：用IH證明排序為n+1的語句有性質P。
  得證任何排序的語句都有性質P。

強歸納法

• Base Case：證明最小的排序有性質P。
• Inductive Hypothesis：假設排序小於n的語句都有性質P。
• Inductive Case：用IH證明排序為n的語句有性質P。
  得證任何排序的語句都有性質P。（強歸納法的範例可以在這篇文章裡找到）

數學歸納法的部分我沒有讀得很清楚，所以這篇不是寫得很好。Kiki有在講義附上參考書目（Causey R. (2001), Logic, Sets, and Recursion.），有興趣的人可以找來看看。

參考資料：中正哲學所九十九學年度第一學期進階邏輯Kiki的講義。