数学联邦政治世界观
超小超大

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₁>ᴋʙ · · · ,那么 <ᴋʙ 有无穷递减链,显然不是良序,定理成立。

数学联邦政治世界观提示您:看后求收藏(笔尖小说网http://www.bjxsw.cc),接着再看更方便。

相关小说

涧春 连载中
涧春
五香瓜子仁
[已签约]一场让所有人匪夷所思的穿书,沐季珠以为的穿书,其实是夜渊一千两百年来的等待。
15.5万字6个月前
云与夜 连载中
云与夜
琪琪拉
哎嘿!甜甜甜!轻微ABO
2.3万字6个月前
无限流——这个NPC是如此的独特 连载中
无限流——这个NPC是如此的独特
彼岸之舟*
作为无限流游戏中的固定NPC,白景欢在同一个故事里轮回过许多次,也遇见过许多人,可那些都不是他所期盼的。直到有一天,他觉醒了意识,也再次见到......
30.7万字5个月前
异世界图书馆 连载中
异世界图书馆
镜蝶
〈别名:世界图书馆与少女梦谈〉一个偏远地区流传着一个传说,满月当空时,在荡漾着月辉的河中放下一只纸船,借着月光让纸船载着你一部分的灵魂,为你......
40.9万字4个月前
暗欲之爱 连载中
暗欲之爱
千絮任奈
暗雨之下,他对她爱而不得,她若即若离,无路可逃得不到?那就一起下地狱吧,宝贝…..~
2.0万字4周前
笙声入谁心 连载中
笙声入谁心
祁祁子阮
修仙太难,你养我吧
1.6万字4周前