Kleene-Brouwer序的一个定理

Kleene-Brouwer序（下面简称＜ᴋʙ ）是定义在 A＜ω 上的一个序， ＜ᴀ 是 A 上的良序。 ＜ᴋʙ 定义如下： s＜ᴋʙt 当且仅当 s⊃t∨s(δ(s，t))＜ᴀt (δ(s，t)) ，其中δ(s，t)＝min{n：s(n)≠t(n)}。

我们称T ⊆ A＜ω 是well-founded当且仅当 [T]＝∅，换言之 T 没有无穷枝(infinity branch)，否则我们称 T 是ill-founded。

定理：＜ᴀ 是 A 的良序，那么 (T，＜ᴛ) 是well-founded当且仅当 (T，＜ᴋʙ) 是良序。

证明：假设(T，＜ᴛ) 是well-founded，那么 T 没有无穷枝，即每个枝都有terminal： ∀s∈T∃t∈T(s＜ᴛ t∧¬∃t'∈T(t＜ᴛ t'))。下面证明 (T，＜ᴋʙ) 是良序：任选 S ⊆ T ，定义 S' 是 S 的全体terminal，定义 ф⁰＝{s∈S'：∀t∈S'，(s(0)≤ᴀ t(0))} ，规定 фⁿ⁺¹＝{s∈фⁿ：∀t∈фⁿ，(s(n＋1)≤ᴀ t(n＋1))} ，不难看出 фⁿ⊇фⁿ⁺¹ 。如果 ∀n(фⁿ≠∅) ，可证 (T，＜ᴛ) 有无穷枝，矛盾，反证 ∃n(фⁿ＝∅) ，令 n₀ 为最小的 фⁿ＝∅ 的自然数。由于 фⁿ⁰⁻¹≠∅ ，只需从中选出 s∈фⁿ⁰⁻¹ 满足 ∀t∈фⁿ⁰⁻¹ ，(s(n₀)≤ᴀ t(n₀))，这个 s 即为S 在 ＜ᴋʙ 下的最小元。

假设(T，＜ᴛ) 是ill-founded，那么 t₀＜ᴛ t₁＜ᴛ· · · 是一个无穷枝，此时有 t₀＞ᴋʙ t₁＞ᴋʙ · · · ，那么 ＜ᴋʙ 有无穷递减链，显然不是良序，定理成立。