Dedekind finite set的一些简单性质

称集合S 是Dedekind finite，当且仅当，不存在 S 的真子集 T 与 S 有双射。称 S 是Dedekind infinite，当且仅当 S 不是Dedekind finite。

不难看出，如果假设可数选择公理，那么S是Dedekind finite当且仅当 S 是finite，后者的定义是 S 与某个自然数等势。但如果仅仅有ZF的话，我们无法证明两者是等价的。

下面我们证明一些Dedekind finite set的简单性质，这些性质都只需要ZF就可以证明。

定理1 ：如果 α 是Dedekind finite set，那么 b⊂α 是Dedekind finite set。

证明：假设α⊃b⊃c 并且 f：b→ c 是双射，那么 f 可以延拓为 f'：(α−b)∪c → α 的双射，这与 α 是Dedekind finite set矛盾，因此 f 不存在。现在证明 f 可以延拓为 f' ：令 f'＝f∪{〈x，x〉：x∈α−b}即可。 ⊣

定理2 ： α 是Dedekind finite set，当且仅当不存在单射 f：ω → α 。

证明：假设存在单射f：ω → α ，显然 α 是Dedekind infinite set；假设 α 是Dedekind infinite set，那么存在 α'⊂α 满足 x∈α−α' 且存在双射 f：α → α' 。由于 x∉α' ，因此 f(x)≠x ，进一步有 fⁿ(x)≠fᵐ(x)，n≠m：否则由于 f 是双射，因此 f◦fⁿ⁻¹(x)＝f◦fᵐ⁻¹(x)，那么有 fⁿ⁻¹(x)＝fᵐ⁻¹(x) ，根据最小数原理可知矛盾，反证 fⁿ(x)≠fᵐ(x)，n≠m。那么 {fⁿ(x)：n∈ω} 是无限集，进而可得 α 有可数无穷子集。⊣

根据定理2 可知Dedekind infinite set蕴含infinite，但反过来不成立。这也可以看出有穷和无穷的界限需要选择公理才能辨别。

定理3 ：如果 α，b 是Dedekind finite set，那么 α∪b，α × b 也是。

证明：根据定理2 可知 α，b 不含有可数子集。如果 α∪b 有可数子集 c ，那么 α 或 b 中至少要有一个含有可数子集，矛盾，反证 α∪b 也是Dedekind finite set。如果存在 f：ω → α × b 是单射，令 c＝{f(n)：n∈ω} ，则 α'＝{x∈α：∃y∈b，〈x，y〉∈c} 和 b'{y∈b：∃x∈α，〈x，y〉∈c} 中必然有一个是可数集：假设 b' 不是可数集，由于 c 可数，因此 b' 是有限集，设 b＝{y₁，· · ·，yₙ} ，那么必然存在 yᵢ，i≤n 满足 {x∈α：〈x，yᵢ〉∈c} 是可数集，因此 α' 是可数集，这与 α 是Dedekind finite set矛盾，反证定理 3 成立。 ⊣

定理4 ：假设 𝐼 是Dedekind finite set， Aᵢ，i∈𝐼 都是Dedekind finite set且 i≠j → Aᵢ∩Aj＝∅ ，那么 ∪Aᵢ 也是Dedekind finite set。

ᵢ

证明：∪Aᵢ 的基数小于等于

ᵢ

A＝{〈i，x〉：i∈𝐼∧x∈Aᵢ} 的基数，下面只需证明 A 是Dedekind finite。证明与定理 3 的 α × b 类似：如果存在 f：ω → A 是单射且 B＝f[ω] ，那么要么 dom(B) 是可数集，要么对存在 i∈dom(B) 满足 {x∈Aᵢ：〈i，x〉∈B} 是可数集，因此定理成立。⊣

定理5 ：假设 α 是Dedekind finite set，那么 ν＝{r：∃n∈ω(r：n → α∧r )} 是Dedekind finite set。

证明：反证法，假设f：ω → ν 是单射，定义 f[ω]＝ρ⊆ν 且 fₙ＝{r∈ρ：dom(r)＝n} 。假设存在某个 n 满足 fₙ 是无限集，设 fₙ＝{r₁，· · ·，rₖ，· · · } ，由于有穷个元素的排列是有穷的，因此 ∀kl＞k∃u≤n，rₗ(u)∉∪rαn(rᵢ)成立； i≤k

又因为 rₖ 已经确定了 rαn(rₖ) 上的良序，因此 {rᵢ(j)：i，j＜ω} 上有一个由 fₙ 诱导出的良序，这样， {rᵢ(j)：i，j＜ω} 就是 α 的可数子集，这与 α 是Dedekind finite set矛盾。

假设对于任意n 都满足 fₙ 是有限集，由于 f 定义了 ρ 上面的良序，那么我们可以从每个 fₙ 中选择一个 sₙ ，显然 ∪rαn(sₙ) 是 α 的

ₙ

可数子集，这与 α 是Dedekind finite set矛盾，因此这样的 f 不存在， ν 是Dedekind finite set。⊣

以上内容来自Jech的set theory第三章课后题。

定理6 ：假设 α 是无穷集，那么 𝕻𝕻(α) 是Dedekind infinite。

证明：{{b⊆α：|b|＝n}：n＜ω} 是可数集即可。⊣

贴一张jech的原文，里面是Dedekind finite set的一些不能在ZF中被证明的性质。读者根据我上面的证明过程应该能理解为什么下面这些性质在ZF中推不出来。

On the other hand，one cannot prove without the Axiom of Choice that a pro- jection，power set，or the set of all finite subsets of a D-finite set is D-finite，or that the union of a D-finite family of D-finite sets is D-finite.

（中文翻译）：另一方面，如果没有选择公理，就不能证明D-有限集的投影、幂集或所有有限子集的集合是D-有限的，或者D-有限集族的并集是D-有限。

数学联邦政治世界观提示您：看后求收藏（笔尖小说网http://www.bjxsw.cc），接着再看更方便。