选择公理 The Axiom of Choice 1-8OT 主讲人:匡亚明学院 马成功.

Presentation on theme: "选择公理 The Axiom of Choice 1-8OT 主讲人:匡亚明学院 马成功."— Presentation transcript:

1 选择公理 The Axiom of Choice 1-8OT 主讲人:匡亚明学院 马成功

2 目录 01 02 03 04 选择公理及其等价形式 如何理解选择公理 选择公理的发展 选择公理的应用

3 选择公理及其等价形式 PART 1

4 选择公理： 首先,我们定义几个概念 集族：指由非空集合组成的集合。 选择函数f：它是一个集族上的函数。 它规定：对于所有在集族X中的集合A，f(A)是A的一个元素。 有了这些定义，选择公理便可以被表述为： 对于任何集族，其必定存在选择函数。 用公式来表示便是：

5 还有几种等价（换汤不换药）的表述： 给定由互不相交的非空集合组成的任何集合，存在着至少一个集合，它与每个非空集合恰好有一个公共元素。 设C为一个由非空集合所组成的集合。那么，我们可以从每一个在C中的集合中，都选择一个元素和其所在的集合配成有序对来组成一个新的集合。 集族上的任意笛卡尔积总是非空的。 对于任何集合A，A的幂集（除去空集）有一个选择函数。

6 选择公理的各种等价命题 良序定理（Zermelo 定理） 要理解良序定理，我们首先要理解以下概念： 1 偏序关系
对于给定的集合X，若它的某些元之间能建立二元关系≤满足： 自反性（Reflexivity）：x ≤ x; 对称性（Symmetry）：若 x ≤ y且y ≤ x，则 x=y; 传递性（Transitivity）：若 x ≤ y且 y ≤ z，则 x ≤ z； 则称关系“≤”为集合 X上的一个偏序关系。具有偏序关系的集合为偏序集，可记为（P,≤)。 需要注意的是，在偏序集中，并非任意两个元素之间都有关系≤. 而如果 X 中的任何两个元素都有偏序关系≤ ，也就是说：对任意在X中的元素x, y, x ≤ y和 y ≤ x中至少有一个成立，则称集合 X 为关于≤的全序集。

7 对于一个任何集合而言，它一定可以被编成良序集。
2 极大（小）元 设 X 是偏序集,≤是 X上的偏序关系， A 是 X 的子集, b ∈ A。 若对一切 x ∈ A有要么 x ≤ b ( b ≤ x) 成立，要么 x 与 b 没有偏序关系，则称 b为 A 的极大元（极小元）。 3 良序 设集合 (S ,≤) 为一全序集，≤是其全序关系。若对任意的S的非空子集都有在其序下有最小元素，则称≤为良序关系，(S ,≤) 为 良序集。 良序定理如下： 对于一个任何集合而言，它一定可以被编成良序集。

8 佐恩引理（Zorn‘s Lemma）内容如下：
同样的，要理解佐恩引理，我们首先要理解如下概念： 上下界 设 X是偏序集，≤是 X 上的偏序关系，A是X的子集，若存在 b ∈ X, 使得对一切x ∈ A, 都有 x ≤ b（ b ≤ x ）成立，则称 b为A的上界（下界）。 佐恩引理（Zorn‘s Lemma）内容如下： 在任何一非空的偏序集中，若任何链（即全序的子集）都有上界（下界），则此偏序集内必然存在（至少一枚）极大元（极小元）。

9 选择公理与良序定理与佐恩引理间的等价性证明
评价（吐槽） The axiom of choice is obviously true, the well-ordering principle obviously false, and who can tell about Zorn's lemma? — Jerry Bona 选择公理显然是对的，良序定理显然是错的，佐恩引理的对错又有谁说得清呢？ 选择公理与良序定理与佐恩引理间的等价性证明 关于它们之间的互推 我举简单的几例

10 对任意由非空集合组成的集族X，取X的并集S，由良序定理，S是可以良序的。
由良序定理可简单地推出选择公理 证明过程如下： 对任意由非空集合组成的集族X，取X的并集S，由良序定理，S是可以良序的。 X中的任意集合A都是S的非空子集，故根据这个S的良序，可以从A中选出一个最小元素a。 这种选择是满足替换公理模式（ZF系统中另一条公理）的条件的，故应用替换公理模式，即证明了选择公理。

11 由佐恩引理证明良序定理： 证明过程如下： 对任意集合S，为了证明存在S上的一个良序，考虑一个集合P，P的元素是S的子集和其上的良序关系组成的有序对。 对任意A，B∈P，定义A≤B当且仅当A是B的一个前段。 (P,≤)构成一偏序集，且对这个偏序集的任意链（即全序的子集），取其中所有良序的并，则得到这条链的一个上界。 应用佐恩引理，得到P有一个极大元M。M必然是整个S的一个偏序，否则若x是不在M中的一个S的元素，把x接到M后面得到M'，则M'∈P且M≤M'，与M的极大性矛盾。 定理得证。

12 其余选择公理的各种等价形式 中文版的几个（仅供参考）
Tukey 引理：若C是关于集合的有限特征条件，则集X中所有满足条件C的子集中，至少有一个满足条件C的极大元素。 Kuratowski 引理：设 A 是一个偏序集，那么它的每个链一定包含在某一个极大链中。 基数可比定理：任何两个基数恒可比较其大小。 反链原理：对于每一个偏序集而言，其一定存在极大反链。 端点定理：对于一个实线性赋范空间而言，它的共轭空间上的单位球一定有一端点。 对于任意一个集族而言，它一定包含互不相交的集合，这个集合构成它的极大子族。 对于每一个序数而言，它的幂集恒可实现良序化。

13 完整版在这（实在难翻译） Set theory（集合论）
Well-ordering theorem（良序定理）: Every set can be well-ordered. Consequently, every cardinal has an initial ordinal. Tarski‘s theorem about choice（塔斯基定理）: For every infinite set A, there is a bijective map between the sets A and A×A. Trichotomy: If two sets are given, then either they have the same cardinality, or one has a smaller cardinality than the other. Given two non-empty sets, one has a surjection to the other. The Cartesian product of any family of nonempty sets is nonempty. König‘s theorem（柯尼希定理）: Colloquially, the sum of a sequence of cardinals is strictly less than the product of a sequence of larger cardinals. (The reason for the term "colloquially" is that the sum or product of a "sequence" of cardinals cannot be defined without some aspect of the axiom of choice.) Every surjective function has a right inverse.

14 Order theory（序理论） Zorn‘s lemma（佐恩引理）: Every non-empty partially ordered set in which every chain (i.e., totally ordered subset) has an upper bound contains at least one maximal element. Hausdorff maximal principle（Hausdorff最大原理）: In any partially ordered set, every totally ordered subset is contained in a maximal totally ordered subset. The restricted principle "Every partially ordered set has a maximal totally ordered subset" is also equivalent to AC over ZF. Tukey‘s lemma（Tukey引理）: Every non-empty collection of finite character has a maximal element with respect to inclusion. Antichain principle（反链原理）: Every partially ordered set has a maximal antichain.

15 Abstract algebra（抽象代数）
Every vector space has a basis. Krull‘s theorem（克鲁尔定理）: Every unital ring other than the trivial ring contains a maximal ideal. For every non-empty set S there is a binary operation defined on S that gives it a group structure. (A cancellative binary operation is enough, see group structure and the axiom of choice.) Every set is a projective object in the category Set of sets. Point-set topology（点集拓扑学） Tychonoff‘s theorem（Tychonoff‘s 定理）: Every product of compact topological spaces is compact. In the product topology, the closure of a product of subsets is equal to the product of the closures.

16 Functional analysis（泛函分析）
The closed unit ball of the dual of a normed vector space over the reals has an extreme point. Mathematical logic（数理逻辑） If S is a set of sentences of first-order logic and B is a consistent subset of S, then B is included in a set that is maximal among consistent subsets of S. The special case where S is the set of all first-order sentences in a given signature is weaker, equivalent to the Boolean prime ideal theorem; see the section "Weaker forms" below. Graph theory（图论） Every connected graph has a spanning tree.

17 PART 2 怎样理解选择公理 那么，说了这么多（花里胡哨），我们到底应该怎么去理解选择公理呢？

18 举几个简单的数学例子 正整数集合{1，2，3…} 考虑一由一堆（可能无穷个）正整数集合的非空子集所组成的集族，它的选择函数是什么呢？
例：函数值为对应集合中的最小数。

19 考虑实数轴上所有有限长度的闭区间，这些（无限个）闭区间就是一个个集合，那么对于由它们所组成的集族，我们又该怎么找到选择函数呢？
也很简单，可以把函数值定为对应区间的中点。 现在我们考虑由实数的所有非空子集所组成的集族，又该怎样找到一个选择函数呢？ 很遗憾，至今为止，仍未有人找到过这样的选择函数。并且，模型论中有一些颇具说服力的论证表明：这样的选择函数是不可能被找到的。 选择公理跳出来说：尽管找不到，但这样的选择函数的确存在。

20 让我们暂时告别数学例子，进入到现实生活中
给定由互不相交的非空集合组成的任何集合，存在着至少一个集合，它与每个非空集合恰好有一个公共元素。 可这样理解：对于由互不相交的非空集合组成的任何集合X，我们可以“从集合X中的每个集合中挑出一个元素来，而后将这些被挑出来的元素放在一个新的集合中”。选择公理所定义的就是这个可以。 而挑出来的元素和它所在集合的关系，其实就是所谓选择函数。

21 可行吗？ 苹果=元素 苹果堆=集合 一堆堆苹果=集族 如果在前面放置了几堆苹果。那么，我们可以在每堆中选取一个苹果，再把它们放在新的一堆内。
苹果=元素 苹果堆=集合 一堆堆苹果=集族 如果在前面放置了几堆苹果。那么，我们可以在每堆中选取一个苹果，再把它们放在新的一堆内。 如果前面放置了无限堆每堆均有无限个的苹果。那么，我们可以在每堆中选取一个苹果，把它们放在新的一堆内。 可行吗？ 需要无穷多步；而上个世纪末已经证明：一个数学证明必须在有限步内完成

22 所以，尽管有悖于我们的直觉，上述例子中的选择方法并不是显然的，我们得求助于选择公理，才能证明出它的存在。
举另外一个例子加深大家的理解： 正如罗素所说： The Axiom of Choice is necessary to select a set from an infinite number of pairs of socks, but not an infinite number of pairs of shoes. — Bertrand Russell 我们需要选择公理去从无数双袜子中每双挑出一只构成一个集合，无数双鞋则不需要。 因为对于每双鞋来说，鞋分左右，我们只要挑选所有的左脚鞋，那么，“由全体左脚鞋组成的集合”的存在性可由并集公理和子集公理得到保证，从而避开了无穷次的“选择”。而对于无数双袜子，上述方法是行不通的，这时我们只好求助于选择公理。

23 选择公理亦是如此 看到这里，相信大家应该对选择公理有了一个模糊的概念。
接受了选择公理，就意味着我们接受选择函数（也就是现实中的选择方法）始终存在，即使我们无法给出任何具体的构造或例子。 选择公理是非构造性的，它只是断言某个集合或某个函数的存在，但不能具体地给出它。 这就比方说洛尔定理和拉格朗日定理，有时候我们对于给定的函数，不使用它们，也可以找到我们需要的那个点。 但面对一般情况，我们找不到了，构造不出来了，只能求助于它们，得到“存在”具有这样性质的点。 选择公理亦是如此

24 选择公理的起源和发展 PART 3 那么，如此有趣（的选择公理，它又是怎么被提出并发展的呢？ 它又受到过那些反对和支持呢？

25 1904年，Zermelo 提出了选择公理，并用来证明良序原理。
1905年，Vitali利用选择公理构造出[0,1]中不可测集合。 1924年，Kuratowski 提出第一极大原理。十年后，Zorn又用选择公理对这个原理进行了严格证明。这个原理用起来十分方便，很受人们欢迎。 1940年，Tukey又提出了第二极大原理。 还有一些其他的事例都说明，选择公理的提出对整个近代数学理论发展和严格论证都起了巨大的推进作用，因此得到了许多数学家的称道和支持，著名数学家Hilbert就是其中的一位。

26 然而，作为一个不可被证明的公理，选择公理也遭到了许多质疑。
1914年，Hausdorff 利用选择公理在空间转动理论和变换群的结果的基础上，证明了所谓的“分球面定理”。这个定理从直观上看似乎不大可能，但却给出了严格的数学证明。 1924年，Banach 和 Tarski 在 Hausdorff 理论的基础上进一步证明了令人难以接受的分球定理也就是人们通常所说的分球悖论。这一定理指出：在选择公理成立的情况下，可以将一个三维实心球分成有限部分，然后仅仅通过旋转和平移到其他地方重新组合，就可以组成两个半径和原来相同的完整的球。明显，这个定理有悖于我们正常的世界观。这在当时也引起了一些数学家的强烈反对并使学术争辩达到高峰。

27 你自己又是怎么想的呢？ 尽管曾一度具有极大的争议性，但现在选择公理已被大多数数学家们毫无保留的使用着。
选择公理随着时间不断被完善，不断被接受。 1938年，Gödel提出可构造集合的概念。这一创造性的工作对当时整个数学基础的理论研究产生了巨大影响和推动，使得对选择公理抱有异议的数学家大大减少。 1963年，Paul Cohen用“力迫法”证明了选择公理关于ZF系统的独立性。 尽管曾一度具有极大的争议性，但现在选择公理已被大多数数学家们毫无保留的使用着。 你自己又是怎么想的呢？

28 选择公理的应用 PART 4 所以，这个公理被提出来，它究竟有什么用处呢 仅仅是为了证明所谓选择函数的存在吗？
首先，它的一个显然的作用，其实先前已经提过了，就是证明它的各个等价命题…… 并且，通过选择公理还可以得到许多弱于它，但与它紧密相关的命题。（也许你在证明某个命题时，不经意用到了选择公理） 而这些命题可谓涉及数学各个分支，其重要性自然不必多言。

29 下面我们先来看一个接地气（能看懂的）例子：

30 弱于选择公理的各个定理（英文版） Set theory（集合论） Any union of countably many countable sets is itself countable (because it is necessary to choose a particular ordering for each of the countably many sets). If the set A is infinite, then there exists an injection from the natural numbers N to A (see Dedekind infinite). Eight definitions of a finite set are equivalent. Measure theory（测度论） The Vitali theorem（维塔利定理） on the existence of non-measurable sets which states that there is a subset of the real numbers that is not Lebesgue measurable. The Hausdorff paradox. The Banach–Tarski paradox（分球悖论）. The Lebesgue measure of a countable disjoint union of measurable sets is equal to the sum of the measures of the individual sets.

31 Functional analysis（泛函分析）
The Hahn–Banach theorem in functional analysis, allowing the extension of linear functionals The theorem that every Hilbert space has an orthonormal basis. The Banach–Alaoglu theorem about compactness of sets of functionals. The Baire category theorem about complete metric spaces, and its consequences, such as the open mapping theorem and the closed graph theorem. On every infinite-dimensional topological vector space there is a discontinuous linear map. General topology（一般拓扑学） A uniform space is compact if and only if it is complete and totally bounded. Every Tychonoff space has a Stone–Čech compactification.

32 Algebra（代数） Every field has an algebraic closure. Every field extension has a transcendence basis. Stone's representation theorem for Boolean algebras needs the Boolean prime ideal theorem. The Nielsen–Schreier theorem, that every subgroup of a free group is free. The additive groups of R and C are isomorphic. Mathematical logic（数理逻辑） Gödel‘s completeness theorem（哥德尔完整性定理） for first-order logic: every consistent set of first-order sentences has a completion. That is, every consistent set of first-order sentences can be extended to a maximal consistent set. 其实，我们不经意间，在证明许多命题时用到了选择公理，尽管自己没有察觉。

33 选择公理得到了它的名字，这并不是因为数学家们在众多公理中选择了它（双关幽默）。
Quotes （吐槽） The axiom gets its name not because mathematicians prefer it to other axioms. — A. K. Dewdney 选择公理得到了它的名字，这并不是因为数学家们在众多公理中选择了它（双关幽默）。

34 起先它似乎是明白的；但你愈多思考它，由这公理得出的推论就好像变得愈奇怪；最后你完全不明白它的意思到底是甚么了。
--罗素

35 THANKS! 致谢：感谢马传龙同学的交流讨论 参考引用：Wikipedia： Axiom of choice
Stanford Encyclopedia of Philosophy: The Axiom of choice 《选择公理在现实中的实际应用》石夫磊 高迎 董文秀 《选择公理在数学中的作用和地位》郭世铭 知乎《选择公理与Zorn引理》diet meat 《如何让一个5岁小孩听懂什么是选择公理》匡世珉 百度百科:选择公理 THANKS!