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

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),接着再看更方便。

相关小说

神域天下 连载中
神域天下
青柠溪乐
第一次写修仙小说,人生一大尝试,不求表扬,但求指点,批评也行
1.1万字6个月前
不相离,不相弃 连载中
不相离,不相弃
栢竹
稚子被预言为灾星降世即便是肆意的妖,也被预言束缚不得归家她一直很疑惑为什么自己的友人眼底总是带着苦涩直到那日她踏上了家乡的土地一切也都水落石......
0.6万字6个月前
谢绝凌 连载中
谢绝凌
白芷沂
在这个宇宙中,女主角就如同那破晓前的孤星,身披一袭神秘的面纱,让人难以捉摸。似乎命运之神特意为她安排了一场跌宕起伏的剧本,她的故事像是一首待......
1.7万字6个月前
清风拂过叶林间 连载中
清风拂过叶林间
怜怜忧郁
四个人一起进入副本,探寻案件。案件一:拼凑娃娃案件二:泥墙母亲案件三:火锅男孩案件四:疯子父亲每一个案件都惊心动魄……“是真实发生的,还是我......
1.8万字5个月前
我可是女士 连载中
我可是女士
酸奶不加屎
世界线是架空的,不剧透,自己看。
1.6万字1个月前
星之誓 连载中
星之誓
清恒梦锦
光明与黑暗,两个极端的势力从相识到相爱
0.5万字3周前