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

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.6万字5个月前
每个世界都在发生不同的事情 连载中
每个世界都在发生不同的事情
风中凌乱的
宝宝们,欢迎观看,希望宝子们喜欢,大家一起交流,可以告诉我,你想看的类型,我来写。
5.5万字5个月前
陌上月寒 连载中
陌上月寒
乔忆娇
神族战神转世为花界一个古灵精怪的小花精结识了温文尔雅的芍药花精又遇到了被抛弃的魔族殿下,她与他们之间会发生怎样的故事。
1.4万字4个月前
寻秘之秋 连载中
寻秘之秋
轻吟吟吟
流光溢彩的少年不疾不徐撞入她的眼眸,无数问题在她的心中生根发芽。“你好知秋,我是旬阳笙。”“这是我们第23次的重逢。”而她不知道的是,少年的......
0.2万字2个月前
嗜血暗夜 连载中
嗜血暗夜
亦依然
卡米拉一直认为自己是一个没有感情的怪物,可是最后他还是心软了,收养了个半人半吸血鬼的小可怜作为吸血鬼,卡米拉惊奇的发现自己新收养的小可怜竟然......
0.7万字1个月前
噬月羁绊 连载中
噬月羁绊
青秋_094204047
一个背负着沉重过去的吸血鬼,他孤傲、冷漠,却在遇见纯真善良的少女芈祝后,逐渐敞开了心扉。芈祝,一个对未知世界充满好奇的普通人类,她的勇敢和坚......
1.4万字1个月前