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

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

相关小说

默祈 连载中
默祈
古灵精怪爱丽丝
父母被怪物害死的小默羽拼了命逃到教堂保住了性命,成为了看守神明法宝的一位小咯咯。但有一天,宝物意外失踪了,而所有的一切罪责和嫌疑都纷纷指向了......
2.8万字5个月前
CH:假 连载中
CH:假
我推法法
世界真真假假假假真真,真亦是假假亦是真,真假如何可要看君是如何看待
2.4万字5个月前
旁观者有罪 连载中
旁观者有罪
悲楚南落笔兰
往往查的越多…死的就越快,警告的终端便是死亡,查不到的往往是最危险的,科学的终端是玄学…而玄学的终端则是无尽的幻想……
0.6万字4个月前
童话怪谈:暗影中匍匐 连载中
童话怪谈:暗影中匍匐
千秋月yue
【无限流+怪谈+规则+中世纪童话+无cp+微群像+微恐】月亮泛着阴霾,噼啪作响散发热气的炉火旁吟诵着古老的童话故事的声音戛然而止。规则怪谈降......
1.1万字2个月前
魔域情 连载中
魔域情
山下小野花
“紫魅,以后的路,妈妈不能陪你了,你要自己走。”“妈妈,不要!”紫魅是仙女和妖人的后裔,妈妈违反天规被处罚,她在天界的地位也低,被欺凌。可是......
2.1万字3周前
我给皇叔追皇姐 连载中
我给皇叔追皇姐
紫玉甜
凌犀“世人皆知我爱孟婆,却无人知晓我爱得是你,再见之时我已是月老玄七”钰华“世人皆知我心系天下苍生,却无人知晓我为护你,方为三界之主,再见之......
8.4万字2周前