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

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.8万字5个月前
无名之誓 连载中
无名之誓
路过的魈厨
0.2万字2个月前
以是思尽莫招桃 连载中
以是思尽莫招桃
茶少馆
殷義·君泽哈尔的身世迷离,在这身世的背后又隐藏了何等残酷的真相呢?此本小说主要是以殷義·君泽哈尔的角度来写,所以一些伏笔会在后面,所以各位小......
0.3万字1个月前
暗欲之爱 连载中
暗欲之爱
千絮任奈
暗雨之下,他对她爱而不得,她若即若离,无路可逃得不到?那就一起下地狱吧,宝贝…..~
2.0万字3天前
星缘栀子 连载中
星缘栀子
是洛小允吖
初恩映月栀黎凝香
1.6万字3天前
总有Alpha想泡我家老大 连载中
总有Alpha想泡我家老大
带上Nancy
Omega老大的甜蜜爱情故事,顶着最温柔的名头,打最狠的架
1.7万字7小时前