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

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

相关小说

情神……西玫溅妍 连载中
情神……西玫溅妍
慕羽儿mye
在第四维度的灵界上,玫瑰之王西玖溅妍与鹰国之王鹰.维洛依斯之间的超虐言情救赎,最终双双成神的故事!
1.1万字5个月前
星际迷途:时光之匙 连载中
星际迷途:时光之匙
176***090_0306349480
新人作者,多多关照
1.4万字5个月前
幸运心月 连载中
幸运心月
回礼信
裴胥熙,俢真界的一股清流,年纪轻轻便已成高就
1.0万字5个月前
时光代理人:我是反派他妹 连载中
时光代理人:我是反派他妹
辞人顾江
随着命运的航线行驶,缓缓前行,留下的印记深浅不一,这就是我们的故事。未来有无数种可能,每一次的选择都会改变未来的走向,在这期间,我并不是唯一......
2.5万字3个月前
首席演员今天也在作死 连载中
首席演员今天也在作死
一条仁
「亲爱的观众,接下来——是即兴演出时间!」)伦敦的金蔷薇剧院里,罗纳德·坎贝尔是万人追捧的金蔷薇剧院掌门人兼首席演员,优雅、自恋,连谢幕时扬......
5.2万字4周前
弑神浮云录 连载中
弑神浮云录
看到结局泪目
浮云公会会长能不能给我当几天?
5.8万字1周前