良基關係

在數學中，類 X 上的一個二元關係 R 被稱為是良基的，若且唯若所有 X 的非空子集都有一個 R-極小元；就是說，對 X 的每一個非空子集 S，存在一個 S 中的元素 m 使得對於所有 S 中的 s，二元組 (s,m) 都不在 R 中。

等價的說，假定某種選擇公理，一個二元關係稱為是良基的，若且唯若它不包含可數的無窮降鏈，也就是說不存在 X 的元素的無窮序列 x₀, x₁, x₂, ...使得對所有的自然數 n 有着 x_n+1 R x_n。

在序理論中，一個偏序關係稱為是良基的，若且唯若它對應的嚴格偏序是良基的。如果這個序還是全序，那麼此時稱這個序為良序。

在集合論中，一個集合 x 稱為是一個良基集合，如果集成員關係在 x 的傳遞閉包上是良基的。策梅洛-弗蘭克爾集合論中的正則公理，就是斷言所有的集合都是良基的。

歸納和遞歸

良基關係之所以引人關注的一個重要原因是因為超限歸納法的一個版本可以應用到它上面。(X, R) 是良基關係，並且 P(x) 是 X 的元素的某種屬性，你期望 P(x) 對 X 的所有元素都成立，那麼良基關係有能力做到這一點：

如果 x 是 X 的一個元素並且對所有的滿足 y R x 的 y 都有 P(y) 為真，那麼 P(x) 也一定為真。

和歸納法類似，良基關係可以支持通過超限遞歸來構造對象。令 (X, R) 是一個良基的二元關係，F 為一個函數，且對所有的 x ∈ X 和 X 上的每一個偏函數 g 有 F 賦值於一個對象 F(x, g)，那麼存在唯一的一個函數 G 滿足對任意的 x ∈ X，

G(x)=F(x,G\vert _{\{y:y\,R\,x\}})

。

這就是說，如果我們想構造一個 X 上的函數 G，我們可以通過滿足 y R x 的 G(y) 的值來定義 G(x)。

最為一個例子，考慮一個良基關係 (N, S)，此處 N 為自然數集合，且 S 是後繼函數 x → x+1 的圖像。S 上的歸納就是通常的數學歸納法，而 S 上的遞歸給出了原始遞歸。如果我們考慮序關係 (N, <)，我們就得到一個完全歸納法和一個（course-of-values recursion）。命題 (N, <) 是良基的也被稱為良序原理。

還有其他一些令人感興趣的良基歸納的例子。當良基關係是通常的序數上的序關係，那麼對應的歸納法是超限歸納法；當良基集合是遞歸定義的數據結構，那麼對應的歸納法稱為結構歸納法；當良基關係是全類上的集合成員關係，對應的歸納法稱為∈歸納法。請參閱相關主題的論文來獲得更多的細節。

例子

下面給出一些是良基關係但不是全序關係的例子：

正整數 {1, 2, 3, ...}，及其這樣定義的一個序關係：a < b 若且唯若 a 整除 b且a ≠ b。
一個固定詞表上的所有的有限長字符串，及其這樣定義的一個序關係：s < t若且唯若 s 是 t 的一個真子串。
自然數的有序對的集合 N × N，及其這樣定義的一個序關係：(n₁, n₂) < (m₁, m₂) 若且唯若n₁ < m₁且n₂ < m₂。
一個固定詞表上的所有正則表達式，及其這樣定義的一個序關係：s < t 若且唯若 s 是 t 的真子表達式。
任何以集合為元素的類，及其這樣定義的一個關係：a R b 若且唯若 a 是 b 的一個元素（假定正則公理成立）。
任何一個有限的有向無環圖，及其這樣定義的一個關係：a R b 若且唯若存在一個有向邊 a→b。

其他性質

如果 (X, <) 是良基關係並且 x 是 X 中的一個元素，那麼以 x 為始的降鏈都是有限長的，但是這不意味着它們的長度必定是有界的。請考慮下面的例子：

令 X 為全體正整數和一個新元素 ω 的並，ω 比任何整數都要大。這樣 X 是一個良基集合，但是存在以 ω 為始的降鏈其長度可以任意（有限的）大：對任意的 n，鏈 ω, n-1, n-2, ..., 2, 1 的長度為 n。

莫斯托夫斯基塌陷引理蘊涵集合成員關係是一個普遍(universal)的良基關係：對任何類 X 上的類集的（set-like）良基關係 R，存在一個類 C 滿足 (X,R) 同構於 (C,∈)。

參考資料

Just, Winfried and Weese, Martin, Discovering Modern Set theory. I, American Mathematical Society (1998) ISBN 0821802666.