相關：
第一數學歸納法 vs 第二數學歸納法 vs 良序定理
第二數學歸納法：硬币問題和堆垛遊戲
第一數學歸納法：施塔特中心的地闆磚
良序原理：算術基本定理的證明
*任何非空的非負整數集合都有一個最小的元素。*
首先不要把良序原理（Well-ordering principle）和良序定理（Well-ordering theorem）混淆了。良序原理的關鍵點在于非空和非負整數——空的集合沒有元素; 包含負數或者正有理數的集合也可能沒有最小數。雖然看起來很簡單，但它是離散數學裡最重要的原理之一。
良序原理的使用方法一般都相似。例如，我們要證明對于所有的屬于N集合的元素n，P(n)都成立：
- 設存在集合C，C中的元素為P的反面例子，也就是說，C ::= {n belongs to N | NOT(P(n)) is true}。
- 假設C是非空的（反證）。
- 由良序原理，C中會有一個最小的元素n。
- 推出一個沖突的結果。例如P(n)事實上是正确的，或者C存在一個比n還要小的元素使得P(n)不成立等等。
- 得出結論，C一定是空集，即不存在屬于N的元素使得P(n)不成立。
算術基本定理，又稱為正整數的唯一分解定理，即：每個大于1的自然數均可寫為質數的積，而且這些素因子按大小排列之後，寫法僅有一種方式。
下面利用良序定理對其證明。
必然性：
- 設存在集合C，C中的元素為大于1的自然數，且不能寫成質數的乘積。
- 假設C是非空的。
- 由良序原理，C中存在一個最小的元素n，n不能寫成質數的乘積。
- 由C的性質，n不能是一個質數，因為質數分解因式隻能得到本身即質數的乘積，是以n可以寫成a * b。由 a > 1, b > 1，是以a < n, b < n，是以a, b不屬于集合C（n是最小的元素），即a和b都可以寫成質數的乘積。a = p1*p2...*pn, b = q1*q2...*qn, 是以n = p1*p2...*pn*q1*q2...*qn，即n可以寫成質數的乘積。沖突。
- 得出結論，C一定是空集，即大于1的自然數均可寫為質數的積。
唯一性：
- 設存在集合C，C中的元素為大于1的自然數，且可以以多于一種的方式寫成多個質數的乘積。
- 由良序原理，C中存在一個最小的元素n，n可以以多于一種的方式寫成多個質數的乘積。
- 同必要性證明，n不可能是一個質數，設n = p1*p2...*pn = q1*q2...*qn，其中p序列和q序列存在不相同的值，則p1整除q序列中的一個元素qk（可以用裴蜀定理證明），由于qk也是質數，是以qk = p1，是以存在一個比n小的元素n'，使得n' =p2...*pn = q1* ... *qn（不包含qk），是以n‘也滿足C要求的性質。沖突。
- 結合必然性的證明，得出結論。每個大于1的自然數均可寫為質數的積，而且這些素因子按大小排列之後，寫法僅有一種方式。
良序集合：如果一個實數集合的每個非空子集都有一個最小的元素，就說該集合是良序的。在計算機領域中，良序的概念經常會用來證明程式是可終止的。通常的方法是證明算法中存在一個每次成功運算後其規模都會變小的值，如果這個值屬于一個良序集合，那麼這個運算就是可終止的——因為如果不會終止，那麼這個值就會導緻良序集合存在一個沒有最小值的非空子集。我後面在複習狀态機的時候會把更具體的操作寫上來的。
下面還有幾個良序原理的一般化和推廣，就不一一證明了：
- 任何一個有下界的整數集合都是良序的，其中的下界是指對于一個實數集合S，存在下界b使得S的任何元素都大于等于b。
- 任何一個有上界的整數集合都有最大值，其中的上界是指對于一個實數集合S，存在上界b使得S的任何元素都小于等于b。
- 任何非空有限實數集合都是良序的。
參考：
- Mathematics for Computer Science
- Well-ordering principle
- 算術基本定理