习题8.5
8.5.1证明:此集合是偏序、全序和良序的. 因为空集使得所有的要求都是空真的成立的.
8.5.2证明:集合在前,关系在后.
(a).
(b).
(c)1.上的<. 2.或者. 3.或者一个由集合构成的的集合族X和关系.
8.5.3证明:1.自反性:,故.
2.反对称性:如果且,则,进而有,故.
3.传递性:如果且,则,故.
综上集合同序关系|是偏序集.
由于对2和7有均不成立,故其不是全序集.
8.5.4证明:反证,设为的最小元,即不存在使得. 现在我们令,则此时有且. 矛盾,假设不成立,命题得证.
8.5.5证明:勘误:习题8.5.5第二行“”应改为“或”.
1.自反性:对任意,由于有,故有“或”为真,进而.
2.反对称性:对任意,如果且,则有“或”且“或”,但无论何种情形总有.
3.传递性:对任意,如果且,则有“或”且“或”,但无论何种情形总有.
综上,使X成为偏序.
当使得Y为全序集时,对任意,有或. 当时有. 当时,加上f为单射则有. 此时亦有.
8.5.6证明:f显然是满射. 对任何,如果,则和不可能同时成立. 我们分三种情形讨论:
1.和均不成立,此时有而,故;
2.不成立和成立,同理此时而,故;
3.成立和不成立,此时而,故.
综上f为单射. 进而f为双射.
对于任何,如果,则有,进而有. 如果有,那么对于任意有,进而. 故,故.
综上,对于任何有“ iff ”.
8.5.7证明:设均为Y的最小元,即且不存在使得且不存在使得. 由于Y为全序,故对一切有“”,进而有“”.
类似地可得“”.
于是无论哪种情形总有. 于是最小元只有一个.
同理可证最大元只有一个.
8.5.8证明:设X为全序集. 设Y为X的非空有限子集,显然Y也为全序集.
如果,则其为单元素集,其唯一的元素即为最大元和最小元. 这就完成了归纳基始.
现在归纳假设当时命题成立.
那么当时,我们记. 此时知,进而由归纳假设知有最大元和最小元,分别记为. 于是乎有对一切有“”. 而对,我们有或. 由于,进而有“或.”. 当时,就不存在和不存在使得. 进而不存在使得. 于是为Y的最大元. 当时,对一切有. 故不存在使得. 综上Y总有最大元.
类似地论述知Y总有最小元.
这就完成了归纳,命题得证.
8.5.9证明:假设X是无限集. 由于故X有最小元. 而,进而有最小元,并且容易证明. 由于X是无限集,我们可以证明每次从中剔除掉一个元素得到的集合仍是无限集,于是上述过程可以不断重复下去,于是我们将得到X中的一个无穷增序列. 这说明X无最大元,矛盾,假设不成立,故X是有限集.(此论证不必用到选择公理,因为虽然要重复可数无穷次,但是是可递归定义的,或者说每次的选择是明确的.)
8.5.10证明:归纳原理的集合版本.
一个错误的证明:
容易证明当X为有限集时命题成立. 于是我们现在假设X为无限集.
我们递归定义一个集合序列.
基始定义.
归纳假设已定义好.
我们定义,其中定义为:
若为空集则;若非空则令.
这就完成了归纳定义.
注意,这里没有像习题8.1.1中用到依序选择公理DC,因为在每一步中都是唯一确定的.
上述定义其实就是对X取最小元后去掉此最小元形成新集合,
再对新集合重复同样的操作而得到一个集合的序列.
我们定义,定义集合.
于是我们将看到一个递增的序列,其中.
对自然数0,有.
易知此时成立.
归纳假设对某自然数n有对一切有成立.
那么对一切有:对某自然数有.
当时由归纳假设知有成立;
当时有,
易证对一切且有
(这是因为把X中元素x分为以及其他两个集合,由于以及
递增的序列我们知道满足的X的元素只能在
序列.
即我们容易证明,
进而证明),
故由归纳假设知成立,进而命题8.5.10的蕴涵关系知成立.
故对一切自然数n有中的一切元素都使得性质P成立.
而对一切,存在自然数m使得(或存在自然数m使得),
故为真.
命题得证.
这个错误证明错在论断“对一切,存在自然数m使得(或存在自然数m使得)”,一个反例是以及标准大小序. 由是良序的且集合中定义我们容易证明其是良序的. 此时对论断“存在自然数m使得(或存在自然数m使得)”是错误的,因为是有限集而是无限集(因为1是X的最大元,而由定义我们知道若存在自然数m使得则为空集,由于X是无限集知这是不可能的.)这个例子说明良序集中非最小元的元素不一定有前驱(如果有前驱,容易证明前驱是唯一的),但是良序集中除了最大元的元素均有唯一的后继.
故(可数)良序集并不意味着你可以集合的最小元开始按序关系在有限步内取到任意你要的元素(这样的良序集可以证明必定是至多可数的,比如自然数集,自然数除了0均有唯一的前驱和后继.),其在选择公理成立的前提下只能说明由良序集中元素构成的严格递减序列必定是有限序列.
(命题8.5.10的直观是:只要我们假设存在使得为假,于是根据已知的蕴含式命题可以找到使得且为假. 这个步骤要进行多少次都可以,于是我们可以得到X的严格递减的序列(此处必须假定依序选择公理成立才能取到此序列),这与X为良序相矛盾. 但下面的两个严格证明都没有依赖任何形式的选择公理.)
我们考虑集合. 我们假设集合非空. 由于和X是良序集,我们知道是良序,由于假设其非空,故其有最小元,我们记为. 这说明对一切,对一切有为真. 但从命题的蕴涵关系我们知为真,这与为的最小元相矛盾,这个矛盾说明我们的假设不成立,进而为空集,于是对一切有为真. 这就完成了证明.
我们也可以按照习题的提示(这其实也是弱归纳原理证明强归纳原理的思路)来进行证明:考虑集合. 同理我们知道Y是良序的. 假设Y非空,于是Y存在最小元,我们记为. 即存在,存在使得且P(m)为假的. 而又由于为Y的最小元,这说明对一切,如果有:对,如果则为真. 也即说明:对一切,如果有为真,再由归纳假设知为真. 于是我们得到“对一切,如果有为真”. 这明显与相矛盾,这个矛盾说明我们的假设不成立,于是Y是空集,进而说明对一切有:对一切,如果有P(y)为真. 这蕴涵对一切有P(x)为真.
一旦构建了自然数集,我们就可以证明“强归纳原理”和“良序原理(命题8.1.4)”是等价的. 虽然不同的逻辑构建道路上是有先后顺序之分的.
这道习题告诉我们,虽然数学归纳法来源于自然数的抽象,但其也可以用于良序集,无须局限于自然数集.
8.5.11证明:如果是良序的,由定义8.5.8知是全序的.
如果是全序的,对任意的非空子集,S也是全序集.
我们定义集合. 对任意元素,即有且,进而有且,进而. 于是我们看到. 故M也为良序集.
而我们有也为良序集. 而有恒等式.
当M或中有一个为空集时,显然S是良序的,即有最小元.
当M和均非空,由于上面论证了它们皆为良序,记. 由于S是全序的,则有“或者”.
如果为,那么对任意元素,我们假设有,如果就会与a是M的最小元相矛盾,于是在假设前提下有,进而有,即,这又与b为的最小元相矛盾,综上我们的假设不成立. 故不存在使得,于是此时a为S的最小元.
同理当我们可以证明b为S的最小元.
综上为良序的.
命题得证.
8.5.12证明:勘误:习题8.5.12中第三行“如果”应为“如果”.
自反性:对任意,有且,于是有.
反对称性:对任意,如果且,则只能是“(且)且(且)”,于是有. 故.
传递性:对任意,如果且,我们有四种情形:“(且)或(且(且))或((且)且)或((且)且(且))”. 但无论何种情形总有.
综上,序关系使得为偏序集.
我们设X, Y均为全序. 对任意,由于X为全序,则我们有或者. 不失一般性,我们只考虑. 如果,则有,进而;如果,由于Y为全序集,则我们有或者,同不失一般性只考虑,于是我们可以看到且,此时.
综上,此时为全序集.
我们设X, Y均为良序,进而X, Y均为全序,由上论证我们知为全序.
对任意的非空子集. 我们有非空集合,由于X为良序进而其子集良序,我们记其最小元,进而有非空集合,进而我们有非空集合,同理我们可以记其最小元. 于是我们找到了一个元素. 现在就来证明其为A的最小元.
我们假设存在某使得,即且,进一步地有(或(x=a且)且(或),化简此逻辑表达式后我们将得到“或(且)或(且)”.
而和(且)明显与a定义相矛盾,故为假. 于是只剩下(且)为真,这又与b定义相矛盾,于是假设不成立,故元素为A的最小元.
综上此时为良序集.
8.5.13证明:(引用文段是为了帮助理解正式的证明,可以跳过不看)
引理8.5.14的证明开头的直观描述非常符合我们的常规操作,这里遇到的困难是我们不能保证在有限步骤内完成证明,甚至是在可数无限步骤内 (当的严格上界是至多可数时我们容易证明引理8.5.14的直观操作是行得通的. 不过当的严格上界是可数时论证稍微麻烦一点,关键是在可以找到,f是严格增的.]时论证对的每个严格上界都能找到可数步骤内第n步添加的严格上界使得. 这需要一点简单的技巧——先排列好为,然后构造f时就要使得对一切自然数n有). 而严格证明通过一个技巧性非常强的构造来得到一个好像“用尽”一切严格上界的集合来导出矛盾.
我们考虑集合,其显然以为最小元且为良序且是好集合. 如果是常规操作思路,我们只需要选取一个严格上界(只要有严格上界)添加进即可. 而按严格证明思路,我们已为指定了一个严格上界,于是我们就得到好集合,其与常规操作思路得到的集合不同的地方是:常规操作思路给了你选择严格上界的自由,进而带来了不确定性,或者说有无穷种选择道路;而选择公理排除了这种不确定性,给你指定了唯一的道路.
于是我们看到了严格证明是如何使用选择公理绕过了可能无穷重复的步骤:我们在使用选择公理的时候就已经为常规操作思路的可能无穷步中每个步骤指定了应该选择的严格上界,并且每个这样的步骤都可以在原来的好集合基础上添加进选择公理指定的严格上界而形成一个新的好集合. 反过来说好集合如果是有限的意味着此集合也可以看成按常规操作思路在有限步骤内得到(这确实可以证明. 但不是所有好集合都是有限集,我们可以根据习题8.5.10中提到的集合来构造一个无限的有严格上界好集合). 然后严格证明就转向证明好的集合的并确实是好集合,于是把由选择公理指定的好集合的并的严格上界加进好集合的并中还是好集合,进而导出矛盾完成证明.
总结上面的讨论就是:其实我们还是在按照书上直观描述的常规操作思路来进行证明,只不过认为是可以从好集合开始可以添加无穷多的严格上界进集合而形成一系列好集合(由于原来的好集合基础上添加进选择公理指定的严格上界可以形成一个新的好集合). 使用选择公理是为了让我们确定每次添加的严格上界是哪个. 由于所有好集合的由选择公理指定的严格上界都包含在另一个好集合中,故通过好集合的并一次性完成好集合所有严格上界的添加,进而绕过了常规操作只能进行有限步骤的限制. 并且我们知道了: 反过来,我们有好集合如果是有限的意味着此集合也可以看成按常规操作思路在有限步骤内得到(这确实可以证明).
有了上面的讨论,我们应该可以断定(拥有相同最小元的)两个好集合A和B应该有一个是由另一个反复添加严格上界得到的,否则就有使用选择公理的时候为A和B的交集指定两个不同的严格上界,这是不可能的. 我们以此为突破口,用反证法证明此事.
设是好集合.
我们大假设均非空(这说明和均不成立). 由于均为良序,于是我们看到也均为良序. 由于均非空,我们可以取的最小元和的最小元. 于是我们看到.
由于均为好集合,进而有和. 我们已知,进而有
而我们有;.
因为的最小元是和的最小元是,故同时有;.
进而我们得到
这说明了不可能同时为的(严格)上界,否则我们有.
由于,即陈述“且”不成立,这说明:存在使得且,或存在使得且.
已知和和Y’为良序(进而Y’为全序),故如果则. 同理可知如果则.
故原来的结论“存在使得且,或存在使得且”可改为:存在使得且,或存在使得且.
这说明我们有或,即或. 这说明是可比较的.
不失一般性,我们假设有. 这说明,进而由前面讨论知有.
现在考虑,容易证明其为良序且以为最小元.于是在使用选择公理的时候为其指定了一个严格上界.
而(因为).
进而我们看到.
我们前面说过,严格证明中选择公理的使用使得我们可以从思维方式上不严谨地认为:所有好集合是从好集合开始不断添加选择公理指定的严格上界进去而形成的,添加的严格上界的数量可以是无穷的. 这当然是有悖常规操作的,因为实际上我们只能添加有限个严格上界.
而如果A是好集合,也确实是可以由对一切有我们可以证明也是好集合. 因为我们容易从A是好集合知道是以为最小元且良序. 而对一切有,只要我们注意到.
于是上面这一段很好地验证说明直观“严格证明中选择公理的使用使得我们可以从思维方式上不严谨地认为:所有好集合是从好集合开始不断添加选择公理指定的严格上界进去而形成的,添加的严格上界的数量可以是无穷的.”还是很可靠的.
于是对于好集合,也即集合,由于,根据上面不严格思维方式的说明我们有足够的理由相信:是由不断地添加进选择公理指定的严格上界(可以有无穷个)而得到的. 这就说明了我们应该有,而. 下面我们就严格做此事.
考虑集合. 由于,于是非空. 由于Y是良序的,故也是良序的. 于是我们可以取到的最小元.
现在考虑和. 由于知,进而. 我们小假设存在使得且,即. 进而我们看到且,这与是的最小元相矛盾,故小假设不成立,进而对一切如果那么. 这就证明了.
综上,我们证明了.
由于Y为好集合且,于是我们看到. 而同时,于是应该有. 而已知故,也即,这明显与相矛盾,这个矛盾说明我们的大假设不成立,故有两者至少有一个为空集.
综上,我们知道中一个为另一个的子集.
于是我们可以马上看到是好的集合.
现在我们来证明“Y\Y’的每个元素都是Y’的上界,且Y’\Y的每个元素都是Y的上界.”. 我们将使用在良序集上的强归纳法.
不失一般性,我们假设.
于是“Y’\Y的每个元素都是Y的上界.”是空真成立的.
而当为空集时同理“Y\Y’的每个元素都是Y’的上界.”是空真成立的.
于是我们只需要考虑非空.
我们容易知为良序集,由于知非空,我们可以取其最小元.
由于是以元素为最小元的良序集,于是强归纳原理适用于集合.
归纳基始:由,而,于是我们看到. 而同时为好集合Y的最小元,简单的推理可知应有. 这就完成了归纳基始.
设. 归纳假设:对任意,如果那么(我们考虑是合理的,因为它们都属于好集合Y).
我们现在要证明也有. 反证:
假定有. 由于而,于是不可能. 于是从得到.
而从归纳假设已知:对任意,如果那么,于是我们看到为集合的严格上界. 这进一步说明有.
而, 由为的最小元我们知道,进而. 再由我们得到.
综上,我们看到. 进而有. 由于均为好集合,于是有和,进而再由我们得到. 这是一个矛盾,因为我们有且. 这个矛盾说明我们的假定不成立,进而有.
至此,我们补全了使用强归纳原理所需要的所有步骤,于是乎我们可以陈述:对一切我们都有. 而为的最小元. 我们终于可以陈述:中的每个元素均为的严格上界.
我们完成了习题的证明.
当然,我们也可以按照书上习题hint来进行解答.
设.
由于都是好的集合,则有,进而. 而为的最小元,进而我们有. 这就完成了归纳基始.
归纳假设:对一切,如果就有.
进而有;
.
我们先证明集合是空集,因为下面的等式变换要用到.
反证,假设不是空集,于是存在. 进而我们看到.
我们容易知是良序,于是我们看到其最小元,即.
由于是好集合,于是(当时显然是空集,故只需考虑). 于是有.
从说明陈述“且”不成立.
由以及是的最小元,我们知道是空集,进而. 于是陈述“且”不成立可改为:陈述“且”不成立.
而并且中元素不可能属于,故由简单讨论可知有;并且. 进而陈述“且”不成立可改为:陈述“且”不成立.
但是由于,我们看到是成立的,于是”不成立.
由于”不成立,这说明存在使得,这明显与我们在归纳假设得到的相矛盾,故假设不成立,进而是空集.
那么对a,有:
同理可证.
这就完成了归纳. (其中所做的变换是为了后面步骤用上归纳假设)
故由强归纳原理知对一切有.
现在来证是好的集合.
由于,我们假设存在使得,即存在使得. 这与是Y的最小元相矛盾(因为Y为好的集合),故假设不成立,即不存在使得,故为的最小元.
由于而Y是良序的,故也是良序的.
而对一切,我们有集合为集合X的子集合,以为最小元,为良序的,进而考虑是合理的,并且. 进而也是好集合.
而对任意,对任意,如果,由上论证我们知有,故有. 进而对一切,对一切有,进而有,即集合中元素均为的上界. 同理可证集合中元素均为的上界.
我们假设非空,则由为良序的知可取其最小元. 已知为好的集合,那么对,有(第二个等式把Y分解成和后根据是的最小元得到;最后一个等式是由前一段结论得到). 假设非空前提下同理可证. 于是我们发现,即有,这是个矛盾. 故说明两个假设不能同时成立,即和中一个为空集,进而我们知道或. 不失一般性,我们假设,那么陈述“的每个元素都是Y的上界”是空真地成立的;而对每个元素,有x是的上界.
这就完成了证明.
8.5.14证明:我们假设X没有最大元,即对任意元素都存在使得. 设Y是X的有上界的子集,即对任意元素有(即是Y的一个上界). 进而由X没有最大元知存在使得,进而. 故Y有严格上界.
如果X的每个全序子集Y都有上界,我们假设X无最大元,由上论证知Y有严格上界. 这明显与引理8.5.14相矛盾,故假设不成立,故X有最大元.
设A为偏序集,B为A子集. 若B有上界但无严格上界的话(这说明B非空,因为空集有严格上界),那么B的所有上界都属于B,那么B必有最大元(简单论证即知上界即为唯一的最大元). 再结合上面的第一段论证我们知道A也有最大元(不一定唯一). 即我们证明了:设A为偏序集,B为A子集. 若B有上界但无严格上界的话A和B均有最大元,B的唯一最大元即为其上界,若A为全序的话其唯一最大元是其上界.
也就是说:一个偏序集的上界如果其属于此偏序集那么此上界就是其唯一最大元;但此偏序集的最大元(不一定唯一)却不一定是其上界,除非其为全序(偏序集为全序时其最大元也是唯一的).
8.5.15证明:我们沿着提示来尝试证明.
一个容易观察到的事实是:
考虑集合. 由于空函数是单射,于是我们看到.
对任意,如果有,进而,即存在使得. 我们大假设不存在到A的单射. 于是我们看到存在S到A的单射f且不存在到A的单射. 我们小假设S到A的单射f不是满射,即存在使得对一切有. 于是我们定义函数,如果则;如果则. 我们容易验证函数f’的定义是成功的,并且容易证明函数是单射,这与我们的大假设相矛盾. 于是在大假设成立的前提下小假设不成立,即S到A的单射f是满射,进而我们得到:S到A的函数f是双射. 进一步知道存在A到S的单射,由于,于是我们可以把函数的值域扩大到B而保持其单射性,也即我们找到了A到B的单射,这与我们的题设“不存在A到B的单射”相矛盾. 于是大假设不成立,即存在到A的单射.
综上,我们证明了:对任意,如果,那么对任意我们有存在到A的单射. 进而如果集合有以为序关系的最大元那么最大元只能是集合B.(注意到证明这个事实的过程中已经使用到了条件“不存在A到B的单射”,于是凡是使用到此事实的论证都间接使用到了“不存在A到B的单射”.)
对每个B的子集,由幂集公理(公理3.10)我们可以考虑所有定义域为X以及值域为A的函数组成的集合.
再由替换公理(公理3.6)以及分类公理我们可以考虑集合. 也即:只要X为B子集,那么X到A的单射函数就属于;并且中元素均为B的某一子集到A的单射函数.
我们定义一个上的一个关系:对任意,当且仅当
对的定义域以及的定义域我们有,且对一切有.
定义此关系的动机是:1.由前面已经说明的事实知——如果我们知道了存在B的子集X到A的单射f,如果X不等于B,那么我们可以在X到A这个单射f的基础上往X增加一个不同于X中元素的元素x而构建出到A的单射g. 而这样的构建过程必定使得“g的定义域包含f的定义域,且对一切有”. 于是对X到A的单射我们不断重复此操作就使得其越来越“接近”B到A的单射;
2.更为关键的是,我们将有:只要有或者,那么存在到A的单射. 后面我们将看到这条性质推广到满足某种性质的无穷个函数的“并”是单射后,对证明起到关键性作用.
我们接下来证明上述定义的关系确实使得为偏序.
- 自反性:由于对一切有,于是有;
- 反对称性:设,. 仔细讨论我们将发现总有;
- 传递性:设,. 仔细讨论我们将发现总有.
于是确实是一个偏序集.(实际上对于只由函数构成的集合W,均为偏序集)
接下来我们来证明“是B到A的单射”的一个等价命题.
必要条件:
假设有是B到A的单射. 对一切,如果,那么对的定义域以及的定义域我们有,而已经说明“是B到A的单射”以及“并且中元素均为B的某一子集到A的单射函数.”,我们看到,即,再由要求“对一切有”我们知道有. 综上,我们证明了在假设有是B到A的单射的前提下:对一切,如果那么. 也即在假设有是B到A的单射的前提下不存在使得.
综上,我们证明了:是B到A的单射是的最大元.
充分条件:
假设是的最大元. 如果f的定义域不是B,由前面已经证明的“对任意,如果,那么对任意我们有存在到A的单射.”(即对定义关系说明的第1点)我们可以构建出一个函数使得,这与假设是的最大元相矛盾. 故在假设是的最大元前提下我们有f的定义域是B,即是B到A的单射.
综上,我们证明了:是的最大元是B到A的单射.
于是我们找到了“是B到A的单射”的一个等价命题:是的最大元.(还可以考虑引理8.5.14给出的无严格上界良序集的最大元与存在B到A的单射的关系,这里的证明由于不涉及到就不展开了.)
于是我们只需要证明集合有最大元即可. 我们将借助佐恩引理(引理8.5.15)来证明.
由于空函数是单射,故非空. 设是全序集. 我们只需要证明有上界即可完成证明. 下面就做此事.
对任意函数,记其定义域为. 我们考虑集合:对任意,我们知有对某使得,即集合非空. 于是根据选择公理我们可以为每一个选择一个中的元素并且记此元素为.
我们现在来定义一个函数:对一切,我们已经为选择了一个,于是我们定义.
现在我们来证明函数是单射. 设且. 于是我们知有且,其中对有且. 进而有,由于P为全序,于是我们知道有或者. 不失一般性,我们只考虑,进而由定义知道有,于是我们看到. 再由于以及我们知道是单射,进而有. 再由定义知道有. 综上我们看到,也即.
综上我们证明了:对任意,如果则. 故函数是单射. 于是.
而对一切,1.我们对的定义域容易知道有. 2.而对一切:我们有,其中. 于是我们看到,由于集合是全序的,于是我们看到有或者. 当时由定义知道有; 当时,结合定义知对一切有. 而我们从定义容易观察到一个事实是“如果那么就有”,进而对,有,进一步有,即有. 综合2.的论述,我们即证明了:对一切有.
结合1.和2.的论述,我们知道:对一切有,进而是P的上界.
由佐恩引理我们知道有最大元,由“有最大元”等价命题知存在B到A的单射. 这就完成了证明.
以下为对习题8.5.15证明的补充说明,可不看.
回顾上面的证明,我们发现即使没有条件“不存在A到B的单射”,也是有最大元,只是最大元不必要是B到A的单射. 换句话说,我们不依赖于条件“不存在A到B的单射”就能用Zorn引理证明是有最大元. 一个自然而然的问题就是:为何有最大元?取到最大元的时候到底意味着什么?
而对于任意的,我们在偏序关系定义的基础上容易证明:当且仅当
对的定义域以及的定义域我们有,且对一切有.
对任意的,我们希望找一个使得. 于是由上面的讨论知必须满足两点:1.,且2.对一切有.
其中寻找的策略是:
由第1点我们看到,即. 于是当(即f为B到A的单射)时我们是不能找到这样的g的. 这就是上面已证“是B到A的单射是的最大元.”的内容. 于是为了满足第1点,要求函数f的定义域不是B.
于是我们假定的定义域不是B.
我们发现要满足两点“1.,且2.对一切有”是很容易的. 在函数的基础上,往其定义域添加进一些同样映射到A的新元素(即新元素属于)后形成的新函数都是满足以上两点的. 并且只要h是单射就有,进而有(因为我们的序关系是只定义在集合上的).
综上,我们也即证明了引理0:设,().
函数的定义域不是B,且函数可看成以为基础按上述策略中方式构造而来,且是单射.
现在,我们可以终于探究一下取到的最大元时到底发生了什么?
对的最大元的定义域有:或.
当时,是的最大元的原因是简单明了的:因为B中元素全部用到了. 故我们只需考虑的情形.
由于函数的定义域不是B,于是对于任何以为基础按上述策略中方式构造而来的函数(即往定义域添加进一些同样映射到A的新元素(即新元素属于)后形成的新函数),其不可能是单射. 因为如果是单射,从前面证明的引理0我们容易发现,这与是的最大元相矛盾.
综上,使用反证法,考虑往定义域只添加进一个同样映射到A的新元素后形成的新函数,我们容易证明函数是满射. 也即函数用尽了A中的元素而导致是的最大元.
综上,我们终于知道的最大元时到底发生了什么:的定义域是B或者的值域是A,也即函数用尽中的至少一个.
我很难想象到我在思考的命题“对任意集合:存在到的单射,或者存在到的单射”是以这样的方式出现(这个思考曾出现在下面的一个不完整证明1.中),它居然等价于考虑是否存在最大元.
由于我们已经证明了是一定存在最大元的,于是我们知道存在A到B的单射或者存在B到A的单射. 现在我们终于看清“不存在A到B的单射”作用在哪了.
于是我们终于可以回答“为何有最大元?取到最大元的时候到底意味着什么?”. ——取到最大元时说明“存在A到B的单射或者存在B到A的单射.”;而为何有最大元,只能说只要你承认选择公理其就有最大元. 换句话说,只要你承认选择公理,两个集合之间必定有一个集合的基数小于另一个集合的基数. 这也是本习题的题干已经告诉我们的.
于是我们也看到了习题的另一个证明思路(代替原证明中证明““是B到A的单射”的一个等价命题是:是的最大元.”):1.同原解答定义;2.进而同样的论述说明有最大元;3.类似的论述证明引理0,进而依据引理0通过类似的论述说明取到最大元的意义是“存在A到B的单射或者存在B到A的单射.”;4.简单的论述完成证明.
以下为习题8.5.15的不完全证明或错误证明(思路),可跳过不看.
不完整证明1.:
我们玩一个思维游戏“寻找A和B之间的单射”,只要你能找到A和B之间的任意单射,你就取得胜利.
你首先尽一切努力构造A到B的单射,你为A中的一个元素a匹配一个B中的元素b后,将a从A中标记为已用元素并且将b从B中标记为已用元素(已用元素不可再用),然后对其它未用元素重复上述步骤,只要你“用尽”A中元素时B中还剩未用元素或也恰好用完就成功构造了A到B的单射.(这个构造单射的一般思路是如此符合我们的直觉,以至于很难想到更一般的构造方法) 于是“不存在从A到B的单射函数”说明你总是还未“用尽”A中元素B就已经空了,你按上述思路构造A到B的单射总是失败的!
但是你很聪明,你发现这个游戏结束时A和B中已用元素都是1对1匹配的,于是再一次玩这个游戏时你尝试寻找B到A的单射,你有了上一次游戏寻找A到B的单射失败的经验,你记住了上一次游戏从开始到失败的全部步骤,你就“假装”按原来思路先选B中元素再选A中元素(其实你的头脑思考步骤总是依照上一次游戏过程先选A中元素再选B中元素),最终你取得了和上一次一样游戏结果:B中元素用完了但A中元素未用完,于是你找到了B到A的单射,游戏胜利!
也就是说:在“寻找A和B之间的单射”这个游戏中,当你自己陈述了“不存在从A到B的单射函数”为真时,你也即陈述了“存在从B到A的单射函数”为真. 当然这样说不是很准确,因为这要求这个游戏可以结束,更具体来说是我们总可以按照上述单射构造思路来穷尽A或B中的至少一个. 而当A且B为无限时,我们不能保证这一点,我们需要更强的关于无穷的公理.
当然一个接着一个地穷尽某个集合的所有元素这个思想实施起来是有非常大的困难的【如果将此思想中的“一个接着一个地穷尽”严格化为我们人类的本能数数(更规范的说即认为可以找到一个序(数数的规则):除了起始元素每个元素都有唯一的前驱和后继,且起始元素有唯一后继),那么这个思想表达的就是“所有集合都是至多可数的”. 这当然在ZF内是不允许的,但或许某个人可以给“一个接着一个地穷尽”另一个严格化定义. 我这里“另一个严格化定义”想表达的是,是否可能将不可数上的无穷处理的如同人类对待有限集.】. 一个具体的例子是自然数集,因为自然数集是按标准序为良序的且每个非零自然数都有唯一前驱(即每个非零自然数都有唯一的前驱和后继,零也有唯一的后继),进而我们根据习题8.5.10“错误证明”中取“递增的序列”的思路用归纳法小心论证就可以证明我们确实可以“一个接着一个地”穷尽(即证明,需要先证明)自然数集(或者直接使用命题8.1.5证明过程). 当然仅仅是良序集是不够的,一个反例就是“以及标准大小序”. 标准序不能够使集合可以“一个接着一个地”穷尽.
于是我们需要转变思路:我们尽可能多(最多可数个)地从集合A和集合B开始隔离出一对一匹配的元素对. 然后从集合A和集合B中剔除已经匹配的元素得到新的集合,我们将发现集合保留了集合A和集合B的一些共性进而可以使得这个过程可以不断进行下去,最后我们希望集合B确实是被穷尽了的(事实证明这并不可行,原因在对此不完整证明1.的分析中讲. 如果数学直觉好的话可以看出这是显然的.). 于是接下来的工作就变得简单了. 现在就来做此事.
(这个思路与前面的思路(即一个接一个地穷尽)区别在于我们将借助选择公理帮助我们每次一对一匹配多个元素,进而希望可以绕过前面思路的局限.)
我们将递归定义一集合对序列,即.
首先基始定义:. 于是我们看到不存在从到的单射.
接下来我们将定义. 任取到的函数,我们知不是单射.
定义. 即我们将函数的值域中未被映射到的元素筛选出来.(这里的动机是:如果存在A到B的满射那么习题将是容易证明的. 于是我们必须尝试找到这样一个A到B的满射,虽然直觉告诉我们应该是存在这样的满射的,但在我们真正找到它之前都还只是直觉.)
于是我们看到集合中的每个元素均存在一个使得. 于是由选择公理我们可以为每个元素选择一个使得,即存在选择函数使得对每个元素有. 由于已经定义,故我们可以把函数的值域限定为而不构成循环论证,即存在函数使得对每个元素有. 显然函数是满射. 我们假设函数不是单射,即存在使得且. 由于我们已经知道“对每个元素有”于是我们看到,进而由知道,即,这与相矛盾,故我们的假设不成立,于是函数是单射. 综上函数是双射,至此我们终于在集合对隔离出一批一对一匹配的元素对.
接下来就是构建. 我们已经将函数的值域中未被映射到的元素筛选出来形成集合,现在我们目的是要尽力找到一个A到B的满射,于是我们应该将中已经在双射使用到的元素剔除掉,进而使得我们能继续使用相同的技巧(继续使用此技巧当然是有前提的)成批隔离出A和B之间的一对一匹配的元素对. 于是我们定义.
于是我们转向考虑是否可以使用相同的技巧,具体来说就是考虑是否存在到的单射,我们希望是不存在此单射. 反证法:假设存在到的单射. 我们考虑由和拼凑起来的函数:对任意,如果我们定义(由于已证是双射,使用其逆函数没有问题);如果,我们定义. 由于且我们容易知函数是定义成功了的. 现在我们来证明是单射:对任意,由“且”我们可以分四种情况讨论——1.,那么是由是双射保证的;2.,那么是由是单射保证的;3.且,我们从函数值域可以看到,进而我们看到只能有;4.且的情形类情形3. 至此我们终于证明了是单射,这与我们题设“不存在从到的单射.”相矛盾,故我们看到我们的假设不成立,进而不存在到的单射.
综上,我们看到:对自然数0,我们根据对使用选择公理定义出了并且知不存在到的单射.
归纳假设已经按上述同样的方式一步一步(这是确实可行的,因为我们前面已经讨论了如何一步一步地穷尽自然数集)定义好,于是我们也能看到不存在到()的单射.
接下来我们将定义. 任取到的函数,由归纳假设我们知不是单射.
定义. 即我们将函数的值域中未被映射到的元素筛选出来.
于是我们看到集合中的每个元素均存在一个使得. 于是由选择公理我们可以为每个元素选择一个使得,即存在选择函数使得对每个元素有. 由于已经定义,故我们可以把函数的值域限定为而不构成循环论证,即存在函数使得对每个元素有. 显然函数是满射. 我们假设函数不是单射,即存在使得且. 由于我们已经知道“对每个元素有”于是我们看到,进而由知道,即,这与相矛盾,故我们的假设不成立,于是函数是单射. 综上函数是双射,至此我们终于在集合对隔离出一批一对一匹配的元素对.
接下来就是构建. 我们已经将函数的值域中未被映射到的元素筛选出来形成集合,现在我们要尽力找到一个A到B的满射,于是我们应该将中已经在双射使用到的元素剔除掉,进而使得我们能继续使用相同的技巧(继续使用此技巧当然是有前提的)成批隔离出A和B之间的一对一匹配的元素对. 于是我们定义.
于是我们转向考虑是否可以使用相同的技巧,具体来说就是考虑是否存在到的单射,我们希望是不存在此单射. 反证法:假设存在到的单射. 我们考虑由(其是形成的过程中定义的双射)和类似拼凑起来的函数,类似的论述(论述是繁琐但思路是简单的,这里不再展开,留给读者自验,参见下图《递归定义中各集合以及函数之间的关系》)我们将证明是单射,这与我们题设“不存在从到的单射.”相矛盾,故我们看到我们的假设不成立,进而不存在到的单射.
( 此图是为理清图片上面一段是单射的证明.
- 第一列从上到下是.
- 第二列从上到下是,中间的表示的是,括号内的表示的是与选取有关(其余类推).
- 第三列从上到下是双射函数.
- 第四列的表示的是的象(即),依此类推. )
至此,我们看到:对自然数N,我们根据使用选择公理定义出了并且知不存在到的单射.
由强归纳原理,我们确实是完成了归纳定义集合对序列,并且知不存在到的单射.
由上面的归纳定义过程我们将看到两个链:
以及
对于上面两链任何一个链,容易多重归纳证明其链上元素组成的集合都是全序集. 我们假设两链均有最大元,记的最大元为以及记的最大元为().
我们逐个分析当链取到最大元的时候发生了什么.
- 首先分析取到最大元发生了什么. 我们已经说明“容易多重归纳证明其链上元素组成的集合都是全序集”,于是当自然数时我们总有. 由上图《递归定义中各集合以及函数之间的关系》我们很快就可以得到(不嫌繁琐亦可逐个递归层级分析得到):对一切自然数有,即. 再由《递归定义中各集合以及函数之间的关系》观察到均在中,进而说明对一切自然数有均为空集,而由表示的是的象我们进一步看到均为空函数,再由递归定义过程中定义我们知其定义域均为空集,再由链我们知道有. 由于是对一切自然数有,我们就发现就是的最大元,即. 综上,这说明了在序列中,当取到其最大元的时候也已取到了最大元.
- 再来分析取到最大元发生了什么. 类似的分析我们将得到:当自然数时我们总有. 由递归定义中对的定义我们和“当自然数时我们总有.”进一步知:对自然数时我们有,即对一切我们总有陈述“对一切有”成立. 而由前面归纳定义我们知道函数为从到的非单射函数,故不可能为空集(因为空函数是单射). 于是我们可以取一个元素,进而由函数定义我们知道:“存在使得有”成立.”,故我们知道“对一切我们总有陈述“对一切有”成立.”只能是空真的成立的,即论域是空集【到这一步我们终于从上面递归构造中看清:“不存在A到B的单射”是如何蕴涵着“A中元素还未用尽时B中元素就已经用尽”这样的思想.】. 综上,在序列中,当取到其最大元的时候.
进一步的分析我们容易发现当取到最大元的时候也恰好取到最大元,于是其实我们只需假设:链有最大元.
(至此证明不下去了)
对不完整证明1.的分析:我们发现链不一定能取到最大元(于是根本不可能使用Zorn引理),也即B中元素不一定可以按照上述思路取完. 一个例子是当上述递归定义中的的象均为单元素集时,B中元素是被一个接着一个取的,这意味着B为无限集时B中元素是取不完的.
而这个证明思路的适用范围也是小的可怜,其只对B为有限集的情形有效. 究其原因是:此证明思路极度依赖的选取,我们希望的象越大越好,但我们至多也只能是依据依序选择公理说明的象可以是可数集, 故B为不可数集的情形上述思路行不通. 而即使的象可以是可数集,对B为可数集时此证明思路也行不通. 一个具体的反例就是设,设,此时每个相邻整数之间(如0和1)都有B中可数个元素介于此相邻整数(比如),于是我们可以巧妙选取而使得永远都取不完B中元素.
错误证明思路2.:
我们沿着提示来尝试证明. 当A或者B为有限集时命题是容易证明的,故下面只考虑A和B均为无限集的情形.
我们假设0:不存在B到A的单射.
考虑集合(如果其有最大元,我们可以证明最大元为B. 但简单分析我们知道无法使用Zorn引理证明其有最大元,因为全序的上界构造不出来.). 由于空函数是单射,于是我们看到.
对任意,由假设0有,进而,即存在使得. 我们大假设不存在到A的单射. 于是我们看到存在S到A的单射f且不存在到A的单射. 我们小假设S到A的单射f不是满射,即存在使得对一切有. 于是我们定义函数,如果则;如果则. 我们容易验证函数f’的定义是成功的,并且容易证明函数是单射,这与我们的大假设相矛盾. 于是在大假设成立的前提下小假设不成立,即S到A的单射f是满射,进而我们得到:S到A的函数f是双射. 进一步知道存在A到S的单射,由于,于是我们可以把函数的值域扩大到B而保持其单射性,也即我们找到了A到B的单射,这与我们的题设“不存在A到B的单射”相矛盾. 于是大假设不成立,即存在到A的单射.
综上,我们证明了:对任意,如果,那么对任意我们有存在到A的单射.
我们考虑集合和组成的偏序集是否有最大元. 我们假设其有最大元. 由于我们已经假设0“不存在B到A的单射”于是我们有. 由前面证明了“对任意,如果,那么对任意我们有存在到A的单射.”易知我们有,这与是集合的最大元相矛盾,故假设不成立,即集合和组成的偏序集没有最大元.
我们再考虑集合和组成的偏序集是否有最大元.
我们假设:集合和组成的偏序集有最大元. 由于空函数为单射,于是有,进而,即存在. 于是由于是集合和组成的偏序集组成的最大元,于是我们看到存在到A的单射. 至此我们看到:存在到A的单射且不存在到A的单射. 而前面我们已经证明了“对任意,如果,那么对任意我们有存在到A的单射.”,结合“存在到A的单射”、“”以及“”我们容易证明存在到A的单射. 这明显与“是集合和组成的偏序集组成的最大元”相矛盾,故我们有假设不成立,即集合和组成的偏序集没有最大元.
我们容易知道.
(至此证明不下去了)
对错误证明思路2.的分析:我原本的思路是设,且设存在到A的单射和不存在到A的单射. 由前面“不完整证明1.”的经验,我们知道和之间“元素个数”相差不可数个. 观察到存在到A的单射且不存在B到A的单射且;往空集添加某个元素b以及从B中删去元素b,我们发现仍有存在到A的单射且不存在到A的单射且,由此“有限的”对称性于是我大胆假设——“可以把集合B分成两个不相交的等势子集使得存在到A的单射和不存在到A的单射,进而导出矛盾.” 这里有两个难点——1.如何将任意无限集合分为两个不相交的等势子集,我不知道这是否是一个开放问题;2.如何证明存在到A的单射和不存在到A的单射.
但是我们容易举出此思路的一个可能反例:不存在到的单射,而是将分为不交两部分的等势的集合,而易知不存在到的单射且不存在到的单射. 之所以其是一个“可能的”反例,是将分为两不交等势的两部分不止上述一种方式,这里仅抛砖引玉说明此思路的证明难度(引理8.5.14对此思路无帮助).
错误证明思路3.:
由幂集公理(公理3.10)我们可以考虑所有定义域为B以及值域为A的函数组成的集合.
我们定义一个上的一个关系:对任意,当且仅当
或(,且对一切我们有).
定义此关系的动机是:假设从B到A的函数f不是单射,即存在使得且. 我们将为元素保留一个映射到它的定义域中元素(比如),也即上述关系定义中出现“”的意义. 然后对于其它同样映射到元素的定义域中元素,我们将其映射到A中未映射到的元素(这是可行的,因为不存在A到B的单射,从习题3.6.8我们知道不存在B到A的满射,进而任何B到A的函数都不能用完A中元素.),这个操作过程必然使得函数的象变大(即关系定义中“”含义)以及一定满足条件“对一切有”.
于是我们不断重复此操作就使得函数越来越“接近”单射.
而关系定义中“”纯粹是为了满足偏序定义.
我们接下来证明上述定义的关系确实使得为偏序.
- 自反性:由于对一切有,于是有;
- 反对称性:设,. 于是有陈述“(或(,且对一切我们有)且(或(,且对一切我们有)))”,将其展开仔细讨论我们将发现总有;
- 传递性:设,. 类似于2.反对称性将复合命题陈述展开讨论我们将发现总有.
于是确实是一个偏序集.
接下来我们来证明“是单射”的一个等价命题.
设是单射. 我们假设存在使得. 由和上述关系的定义我们知有“,且对一切我们有”. 由知,即存在,即存在使得. 同时由于是单射我们知是单元素集,进而由上述关系的定义知也是单元素集,进而有. 至此我们看到,但是一个矛盾,因为而. 这个矛盾说明我们的假设“存在使得.”不成立. 于是我们证明了:是单射不存在使得. 进而中单射也是的最大元.
在来假设不是单射. 即存在使得且. 由于不存在A到B的单射,由习题3.6.8我们知道不存在B到A的满射,进而函数f不能用完A中元素,即,即存在. 我们定义新函数如下:如果则;否则. 我们容易验证有. 这就证明了:不是单射存在使得. 进而如果不是单射则其不是的最大元.
综上,我们证明了:是单射是的最大元.(还可以考虑引理8.5.14给出的无严格上界良序集的最大元与存在B到A的单射的关系,这里的证明由于不涉及到就不展开了.)
我们还是用Zorn引理来进行证明.
由前面论证我们已经知道确实是一个非空偏序集. 设F是的一个全序(或考虑为良序)子集.
当F是空集或单元素集时F显然有上界,故我们只需考虑F含有两个或两个以上的元素.
现在我们来定义另一个函数如下.
我们考虑集合,也即F中所有函数的象的并. 任取F中一个元素记作:
- 如果是F的最大元,那么我们知道此时集合F仍有上界(也即定义,此时就是F的上界.).
- 故我们只需考虑不是F的最大元的情形,也即存在使得,进而由定义知有. 故有. 而对一切,即有存在某使得,我们容易知. 如果不为空集,于是我们可以选取一个来定义. 于是我们使中每个元素都被映射到了. 而对于B中未在上面操作中使用到的元素可以任意映射到同一个A中未映射到的元素(即不属于,由不存在A到B的单射知这确实是可行的)而完成的定义,进而验证是定义成功的且确实是F的上界,进而由Zorn引理完成证明.
(至此证明不下去了)
对错误证明思路3.的分析:关键就是“不为空集”不一定成立. 比如我们考虑一个集族P:={{0, 1, 2, 3, 4, 5, …}、{1, 2, 3, 4, 5, …}、{2, 3, 4, 5, …}、{3, 4, 5, …}、{4, 5, …}、{5, …}、…},其是从自然数集起不断剔除其最小元过程中形成的一系列集合. 显然对任意都有非空且有“或”,但是.
但是我们容易证明这样的命题:设P是非空有限集且P中元素均为非空集合,而对一切有“或”. 那么我们有.(证明:用归纳法对P的基数进行归纳)
习题8.5.15的引申:习题8.5.15和引理8.5.14其实有很多相似之处. 比如习题8.5.15要求可以按不完整证明1.中游戏穷尽集合A或集合B,而引理8.5.14要求穷尽严格上界;两者都涉及到无穷步等等. 我们应该可以将习题8.5.15的证明改成类似引理8.5.14的形式,但应该不如使用Zorn引理简便和容易理解,故这里就不展开了.
By the way, 使用Zorn引理的难点在于——1.把某个涉及到无穷步骤的问题转化为关于某个偏序集的最大元的存在问题,并且这个偏序有这样的特点:对于偏序集中满足不是最大元的元素i我们总是容易找到偏序集中另一个元素j使得i<j;2.通常在找全序Y的上界过程中使用到“并公理”.
8.5.16证明:(提示:此题借助哈斯图有助于我们的理解)
首先第一个问题就是集合X的一切偏序是否可以构成一个集合?
回顾集X的偏序的定义,我们知道其是集合X上满足定义8.5.1三条性质的某个二元关系.
而对于X上的二元关系,我们可以把所有使得关系成立的替代成有序对而形成一个集合(此集合严格形式是,容易证明两集合形式表示的是同一个集合,故我们用更容易理解的具有概括形式的前者.). 进而我们容易证明对一切有当且仅当. 于是对一切我们考虑成不成立只需等价的考虑是否成立,即R(虽然R的构建用到了二元关系,但我们认为一旦构建完R那么R的表示形式是不太重要的)完全描述了二元关系. 这就说明集合X上的所有二元关系可以看作幂集的一个元素(这也是集合论中一个集合X上二元关系的定义. 关于两个集合X和Y之间的二元关系也有类似定义.).
进而X的一个偏序可以看作满足定义8.5.1要求的三条性质(自反、反对称和传递性)的的一个元素. 故X的一切偏序所构成的集合P确实是明确定义了的.
值得注意的是,由上我们将集合X上的二元关系看作一个集合R,于是二元关系的相等即考虑的是集合的相等. 设均为集合X上的二元关系,进而由“二元关系的相等即考虑的是集合的相等”此观念可以证明:对一切有当且仅当. 也即我们找到了判断两二元关系是否相等的等价命题(故可以合理的把此等价命题当作集合X上二元关系相等的定义). 这是二元关系相等的集合论解释,如果我们把二元关系从性质(或说命题)角度解释,两个二元关系相等其实说的就是两命题等价.
现在来证明把P当作偏序集.
- (反身性)对任意元素:由于对任何有,若则. 故我们看到有.
- (反对称性)对任意元素,若有:则对任意,有“”且“”. 进而对任意有. 由上二元关系相等的讨论我们看到有.
- (传递性)对任意元素,若有:则对任意,有“”且“”,进而我们有. 故有.
综上,序关系使得P为偏序集.
回顾偏序集的定义8.5.1,其中的反对称性表述已经默认了对X中的元素已经有一个相等关系=(其当然遵循相等要求的四条公理). 也即我们有了X上的相等关系(相等关系可以看作等价关系+代入公理)后才能定义X上的偏序.
陈述“对于任意集合X我们都可以定义其上的一个相等关系”在某种意义下是正确的. 首先要明确的是我们是在讨论数学,进而讨论的一切对象均是数学对象,即集合X中元素均为数学对象. 要进一步把其讨论清楚要费好多口舌,这里只初略讲讲我的理解(其实是关于=水很深,我把握不住:-(,不同层次的理论对其有不同解释和定义.).
1.如果X中元素为同一类型的数学对象:1.1若此类型数学对象按公理化定义理解(比如自然数的Peano公理定义、实数的公理化定义等),那么X上的相等不是定义出来的而是表示俩对象是同一个东西毫无差别的(即对任意如果则是同一的数学对象的不同记号形式. 举个例子:设,1按Peano公理定义来理解,那么我们只不过是用两个不同符号来代表1这个公理化的数学对象.),进而相等要求的四条公理是不证自明的(而实际上我们通常是这样理解的,比如在集合论的框架下我们不能区分两个具有相同元素的集合有什么不同进而规定了外延公理). 进而我们考虑集合X上的二元关系,满足等价关系的二元关系记作~,由此相等也是一个等价关系. 进而我们可以扩展“相等”的含义而使其具有外延,具体来说就是可以把满足等价关系的二元关系~看成是一个新的相等关系(依据二元关系定义的相等),代入公理(严格来说是对其等价类)仍然成立(具体的例子有模运算). 1.2若此类型数学对象按从另一些数学对象构造出来的定义理解(比如实数的柯西序列等价类定义、实数的戴德金分割定义等),那么X中元素按此类型对象理解时X上的相等需要是等价关系并且满足此类型对象公理化要求的所有性质. 举个简单的例子,我们可以公理化的定义整数集,此时相等要求的四条公理是不证自明的;而如果我们将整数集构造性的定义为(详见§4.1下注)且假定X是整数集,那么我们考虑X中元素时其不应该是自然数构成的一个个有序对,而是依整数相等定义中的等价关系形成的等价类,此时相等要求的四条公理是不证自明的.
2.如果X中元素不为同一类型的数学对象:通常来说我们不会考虑其中元素相不相等(就像我们不会考虑一个自然数和一个函数是否相等),但从“一切数学对象均是集合”这个观点来看,对同一类型的对象统一其集合形式后我们可以将其中元素相等考虑为集合间的相等. 而集合的相等显然满足相等要求的四条公理(因为两个相等的集合是同一的).
总的来说,X上的相等与对X中元素理解密切相关,但都满足相等要求的四条公理.
P恰有一个最小元,其就是相等关系=(1.确切来说是关于X中元素的相等(比如X是自然数集、整数集等等这样常见的例子);2.从万物起源于集合论观点来看,即集合间的相等(比如X中含有实数、复数、四元数、矩阵、方程、不等式等等不同种类的数学对象这样奇怪的人为构造的例子). 不管从哪种理解,只要领会到这意味着“对X中任意两个元素我们都能判断其是否相等”即可). 首先容易从相等遵循的等价关系验证. 我们假设存在元素使得,即对任何有“”且. 同时对任何,如果,进而由结合相等要求的代入公理(进一步讲是因为我们默认对任何数学对象x考察某个性质P(x)时都是无关于x的具体模型的(这有助于我们抽象的处理对象))知此时有. 综上对任意均有,由二元关系相等知有,这与前面证明的相矛盾,故假设不成立. 即P有一个最小元=.
我们再假设二:P还有一个不是=关系的最小元. 即且不存在使得. 而对任意,若有关系“”,同理容易知道有关系“”. 这说明有. 而我们知道了,故由进一步有,这又与“不存在使得”相矛盾. 这个矛盾说明假设二不成立. 故P恰有一个最小元.
现在来证明P的最大元正是X的全序.
我们已经说过集合上的偏序可以看作一个二元关系,而集合X上的二元关系可以用中的元素表示. 进而从二元关系的集合论表示我们看到.
由上解释:设. 如果,即对任何有,由二元关系的集合论解释我们知道这意味着. 于是我们看到. 同理我们可证若则. 综上我们看到. 进而有. 这就说明把集合P解释成子集时,就是集合上的包含关系.
下面的证明将采用P、的集合论解释.
先来证明一个引理如下:
Lemma 8.5.16:对任意,如果存在使得且(和都成立或都不成立)那么X不可能在序下成为全序.
证明:设,设存在使得且(和都成立或都不成立). 进而我们知道使得X为偏序集,故在由反对称性不可能和都成立,于是只能为和都不成立. 这就说明了X在序下不是全序集.
现在来证明:存在使得为全序集为的最大元.
设存在使得为全序集. 由Lemma 8.5.16知对任意如果那么和有且恰有一个成立. 我们假设不是的最大元. 进而存在使得,即存在使得且,再由偏序中自反性我们知道有,再由和为全序我们看到,由看到. 综上,对偏序我们得到且,这明显与是偏序相矛盾,这个矛盾说明我们的假设不成立,故为的最大元.
这就证明了——存在使得为全序集为的最大元.
现在来证明:为的最大元存在使得为全序集.
设不使得为全序集. 于是存在元素使得,进而知道. 定义集合, .(定义的动机是:对不是全序的偏序添加前面确定的形成的有序对后形成的新集自动满足自反性,只要不再添加元素那么反对称性也自动满足,剩下的就是将传递性确定的元素也添加进来即可. 这样最终的集合也应该是一个偏序集.)
由自身的反身性我们容易证明(其实还可以证明),于是我们看到.
现在我们来证明,即证明其也为X的偏序.
自反性:由于使得X为偏序集,进而对一切有,进而.
反对称性:设. 我们分四种情形讨论. 1.当时,由使得X为偏序集知有. 2.当且时,从定义容易知有. 结合和为偏序知有,同理进一步结合我们看到. 这个矛盾说明此情形不会出现. 3.同理2.可证情形“当且”不会出现. 4.当时,同理容易知道有,由和为偏序知有,这矛盾说明此情形不会出现. 综上,我们证明了如果那么,进而有.
传递性:设. 我们分四种情形讨论. 1.当时,有. 2.当且时,同理容易知,结合知有,于是看到,进而有,进而. 3.当且时同理2.知. 4.当时,容易知有,进而有,此矛盾说明这种情形不会出现. 综上,我们证明了如果则.
这就证明了——不使得为全序集存在使得不是的最大元.
由逆否命题即证明了——如果为的最大元存在使得为全序集.
综上,我们证明了:是的最大元当且仅当使得X成为全序.
现在我们来证明给定X的任何偏序都存在全序使得比粗糙.(沿用P、的集合论解释)
设. 由引理8.5.14我们知道存在一个良序集其以为最小元且没有严格上界.
设Y是上面集合W的全序子集. 我们考虑集合.
当Y是空集时,有为空集. 由于我们已证有一个最小元=,进而看到. 这就证明了Y为空集时其有上界=.
于是我们只需要考虑Y非空,进而非空. 接下我们证明,即是X的一个偏序. 1.(自反性)对任意,由于Y非空,即存在使得X为偏序,进而有,进而看到. 2.(反对称性)对任意,如果,说明存在使得. 再由于Y为全序我们知有或者,不失一般性我们假设为. 进而我们看到,即. 至此我们看到,由使得X为偏序集我们知道. 3.(传递性)对任意,如果,说明存在使得. 再由于Y为全序我们知有或者,不失一般性我们假设为. 进而我们看到,即. 至此我们看到,由使得X为偏序集我们知道. 综上,我们看到使得X为偏序,即. 进而也找到了非空集合Y的上界.
综上,我们知道对W的任意全序子集Y都有上界. 故由Zorn引理知道W有一个最大元.
我们假设上面说明的W的最大元不使得X为全序,由前面证明“P的最大元正是X的全序”过程我们知道存在一个使得. 而由于W无严格上界故有,这与是W的最大元相矛盾,故假设不成立,W的最大元使得X为全序.
8.5.17证明:(2023.12.10补充——这是一个伪证,原因是证明过程中使用到了“选择公理”. 也就是说我们并不是“Zorn引理习题8.4.2的结论”而是“Zorn引理+选择公理习题8.4.2的结论”. 但“选择公理”与“习题8.4.2的结论”是等价的,进而“Zorn引理+选择公理习题8.4.2的结论”可以理解成“Zorn引理+习题8.4.2的结论习题8.4.2的结论”. 至此我们可以看到这个证明没有多大意义,其相当于用结论证明结论,证了个寂寞(但对这个证明我们还有一个补救的方法:先使用Zorn引理直接证明选择公理(换句话说证明“Zorn引理选择公理”为真,而不是根据“Zorn引理选择公理”为真. 符号与符号的涵义(含义、真实意义等诸如此类的表达)是有些许差别的,我在这里费些口舌稍微讨论一下. 符号是真值函数联结词,其可以将两个命题联结起来构成一个新的(复合)命题,并且新命题的真值只由那两个命题的真值(真假)来决定. 这就是说我们在考虑(证明)“Zorn引理选择公理”真假时是从“Zorn引理”和“选择公理”的真值来入手,并不一定需要涉及到“Zorn引理”真值和“选择公理”真值之间的关系. 而符号是逻辑蕴含(蕴涵),其涵义更像是在说:可以由在符号前面的那个命题按一定推理规则推导出在符号后面的那个命题(也即我们通常意指的“数学推理”). 这就是说我们在考虑(证明)“Zorn引理选择公理”真假时是从“Zorn引理”真值和“选择公理”真值之间的关系来入手,只要我们在只假定“Zorn引理”为真前提下能推理出“选择公理”为真那么我们就可以说“Zorn引理选择公理”成立(为真)、或者就仅仅是说“Zorn引理选择公理”.),也即论证“Zorn引理选择公理”. 一旦我们论证了“Zorn引理选择公理”:其一我们可以结合书上的论证“选择公理引理8.5.14Zorn引理”看到“Zorn引理选择公理”;其二我们可以从“Zorn引理+选择公理习题8.4.2的结论”(根据“Zorn引理选择公理”,而不是根据“Zorn引理选择公理”)得到“Zorn引理习题8.4.2的结论”,也即我们论证了“Zorn引理(而不是Zorn引理+Zorn引理选择公理)Zorn引理+选择公理习题8.4.2的结论”.) 但此证明中的思考思路以及沿此思路产生的一些讨论仍有价值,故保留.)
习题8.4.2的结论——设I是集合且对每个有是不空的集合. 并且假设对所有的集合彼此不相交. 那么存在一个集合Y使得对于一切有.
我们考虑集合.
我们容易证明和对任意有,即我们知道.
我们定义集合S的动机是:虽然我们不能对集合I直接观察到习题8.4.2的结论,但是我们从有限选择容易知道对I的有限子集习题8.4.2的结论成立. 并且我们容易发现如果对有习题8.4.2的结论成立,那么我们可以往I’添加一个中的元素而证明对习题8.4.2的结论仍成立. 于是引出了下面的二元关系定义.
我们规定S上的一个二元关系:对一切,我们说当且仅当
,且对一切有
(集合使得“”,由于我们知这样的集合是存在的. 对也有同样的说明. 接下来的证明对形如的集合不再说明此事.(2023.12.10补充——注意:此处我们需要引入选择公理来对一切选取出一个(符合要求的),这导致了接下来的论述是正确的但不能达成我们的目的(Zorn引理习题8.4.2的结论),进而整个证明可以看作是伪证.))
如果读者阅读过前面习题8.5.15的解答,就会发现习题8.5.15解答中定义的二元关系和现在定义的二元关系形式是如此相像. 原因就是这样形式的二元关系容易使用“并公理”,进而可以利用Zorn引理,详见习题8.5.15解答的最末尾对Zorn引理使用的总结.
现在来证明使得集合S为偏序集.
1.(自反性)设:首先我们有. 其次,对一切有. 于是我们看到.
2.(反对称性)设且:由的定义知即有和. 于是.
3.(传递性)设且:由的定义知即有“且对一切有,和且对一切有.”,简单的谓词演算我们就有陈述“,且对一切有”为真. 于是我们看到.
综上,我们证明了使得集合S为偏序集. 于是我们知道为非空偏序集.
设A为S的任一全序子集. 我们接下来将证明为A的上界.
当时,我们容易证明且且. 于是我们找到了A的上界. 于是我们只需再考虑非空的情形.
设非空.
对任意,由于K是实实在在存在的(即论域A非空),于是我们考虑是合理的. 而我们容易证明. 而对任意:对任意,知对某有. 由于A为全序,故有或. 1.当时我们容易证明. 2.当时有——“若还有则也容易证明; 否则我们有. 观察到以及由集合S定义知道有. 而由于(即与中元素不同,进而知)故我们看到,进而由有(容易注意到这是一个矛盾,进而说明“当时不可能出现.”. 当然我们可以不理此明显的矛盾而继续推理,我们下面就是这么做的. 让我们可以忽略此矛盾而继续推理的理由是:相对于整个推理过程,在其中某一步骤得到矛盾并不能否定我们整个推理过程的严谨、正确性;出现矛盾只能说明在得到矛盾之前的某一推理链中的步骤讨论的某数学对象是“不存在”的(在上面的证明中那个不存在的数学对象即为),这使得涉及到此数学对象的论述论证是空洞无效的进而可以省略(类似于从“空真的”蕴含命题不会得到我们需要的信息). 简单来说:在证明中(不管是有意还是无意)被忽略的“矛盾”不会影响整个证明的正确性,只会影响所证命题的效用性. 比如这里对“引理1”的证明是正确无误的,进而“引理1”是正确的. 但对“,,”的情形不能根据“引理1”得到(故也不能根据进一步地得到),原因正是前面已经说过的: 在“,”前提下为空集,进而不可能有. 换句话说,“引理1”在情形“,,”是无效的、失效的等等,因为此情形根本不会出现(故证明中对此情形的论述论证是空洞无效的进而可以省略). 这就是逻辑的力量:“逻辑”能帮助你在解决问题(证明命题)的过程中考虑到所有可能情形,虽然某些情形也许根本不会出现. 进而它能让你的解决办法(证明)是周全的(并且它在某种程度上能帮助你发现错误进而尽量保证你的解决办法(证明)是正确的). 但凡事都有两面性,通过上面的简单例子我们可以类比联想意识到“知识可能是正确但无效用的”,比如不符合我们所处的这个宇宙物理规律的某些数学知识是正确的但没有实际用处(现实不满足这些数学知识的使用条件,也即这些数学知识构造的模型不符合现实). 换句话说,⌈知识是无价的⌋可以有两种理解:1.知识对现实世界有实际效用,产生了巨大的价值效益,此时“无价”意指知识给我们带来了不可估量的价值效益;2.知识对现实世界没有太多实际效用,只是知识分子的圈地自萌自娱自乐,此时“无价”意指知识不能给我们带来什么价值效益. 既然“知识可能是正确但无效用的”,对于知识的效用性我们又不能保证没有上帝之手掌控改变宇宙物理规律(使得知识的效用性发生变化),也不能保证知识在发现的当时就找到用处等等 ,所以我们对待知识的态度最好是:知识属于全人类共有,知识产权不再存有. 至此我们可以看到知识对个人、小团体等等确实是⌈无价⌋的了,知识再也不能直接对个人带来(狭义上的)价值效益,但这并没有否定依据知识而展开的劳动之中产生的价值. ⌈实践是检验真理的唯一标准⌋,在劳动实践中产生、检验知识,有效用的知识又反哺于劳动实践. 开放的知识获取体系与劳动实践是相辅相成正向反馈的,封闭的知识获取体系最终只能导致劳动实践是各立山头各自为敌. 这就像你初入社会经过一段时间的摸爬滚打能胜任某岗位后,对后来的新人(可能的竞争者)你不愿意教,怕饿死师傅. 但也许有一天你会厌烦你这重复无聊的工作想跳槽换新的岗位,此时你需要面对的情景就是原来你不愿帮的新人面对过的(我们本质上过着同一种生活,我们自己的所有经历在别人身上都已发生过类似的(比如出生、死亡、上学、逃课、出轨、背叛等等),太阳底下并无新鲜事. 人与人之间的信任就如同一根根线,牵引着我们跳出生活的舞步.). 当然上面的讨论过于理想化,只是属于我自己的幻想时间意淫自嗨. 但我想《圣经》中的“智慧树”故事也许想表达的大概是这么个差不多的意思吧(我没看过《圣经》,对“智慧树”的故事也只是道听途说式的了解.).),此时有”. 结合1.和2.我们知道总有. 故我们看到. 综上我们证明了.
综上,我们证明了引理1:对任意,对任意都有.
现在来证明. 1.容易证明. 2.考虑集合. 对一切,知对某使得,进而由集合S定义知存在使得对一切有,特别地我们看到. 由引理1(等式的第二个等号到第三个等号间变换用到)我们看到. 3.显然有. 综合1.和2.和3.我们看到. 于是我们可以考虑是否为A的上界.
现在来考虑是否为A的上界. 对任意:显然有. 2.而对一切由引理1知有. 这就看到.
综上,我们看到为A的上界.
至此,我们看到S的任一全序子集A均有上界.
由Zorn引理我们知道S存在一个最大元. 结合解答最初的讨论知我们下一步需要证明.
反证. 假设. 由于于是我们可以取到一个元素. 1.于是我们看到. 2.我们可以从(因为)中取出一个元素定义. 由于对一切有如果则:故对一切有;对有(其中证明过程使用到了事实). 结合起来就有对一切有. 3.容易证明. 综上这就证明了.
现在来证明. 1.显然有. 2.对一切有. 结合1.与2.看到.
由于,我们看到. 这说明不是S的最大元,这个矛盾说明假设不成立,故.
于是我们使用Zorn引理证明了习题8.4.2的结论.
于是我们看到:选择公理引理8.5.14Zorn引理习题8.4.2的结论选择公理.
这就说明了Zorn引理选择公理.(或许还有其他方法使得用习题8.4.2的结论直接证明Zorn引理而绕开选择公理,这里就不展开了.)
我们当然也可以按照书上的提示进行证明. 根据提示我们考虑集合.
我们容易知道,并且上的包含关系使得其为偏序集.
设A是的任一全序子集. 现在我们来证明是其上界.
首先我们要证明. 1.容易证明. 2.我们假设存在使得不成立,这说明中至少含有两个不同元素,进而我们知道对某有. 由于A为全序,于是我们看到或者,进而看到或者,而由以及定义可以知道,这说明无论如何都有. 这是一个矛盾,说明假设不成立,于是对于一切都有. 综上我们看到.
进而我们看到且对一切有. 这就证明了是A的上界.
由Zorn引理知道有一个最大元.
由于,于是对于一切都有. 假设存在使得,我们从中取出一个元素. 我们将证明而导出矛盾. 1.容易证明. 2.而对一切,有. 这就证明了,但是此时有,这与是最大元相矛盾,故假设不成立,即:对于一切都有.
类似的说明知道Zorn引理选择公理.
一个错误思路分析:考虑,定义S上的二元关系对一切我们说 当且仅当 对一切有.
此证明思路将遇到和习题8.5.15错误证明思路3.类似的困难,故说明我们要利用上Zorn引理就需要二元关系可以做“加法”(使用并公理)而不是做“减法”(使用集合的交).
习题8.5.16解答以及习题8.5.17第二个解答好像暗示了只要我们考虑的集合X选取的合理,那么对X使用Zorn引理时要考虑的偏序关系就是包含关系(且这样的路径论述是最简洁明了的). 这里就不做过多讨论了.
8.5.18证明:由于有限集具有可一个接一个取完其中元素的可穷性质,故Hausdorff最大性原理对有限集是显然成立的(我们可以写下一个证明操作步骤,但太简单了故省略.). 但这没有完全证明习题.
现在进行正式证明.
设X是一个关于关系的偏序集,记X的全体全序子集组成的集族为A,于是是非空偏序集. 对A的每个关于关系的全序子集Y:1.容易证明对任意有;2.再由Y为关于关系的全序子集,我们容易证明也为关于关系的全序子集,进而看到. 结合1.和2.看到为Y的上界,于是由Zorn引理知道A存在最大元. 这就证明了:Zorn引理Hausdorff最大性原理.
现在假定Hausdorff最大性原理成立,设X是非空偏序集,并且X的每个全序子集都有上界. 前面这句话也就是在说存在X的全序子集Y依关系是最大的且Y有一个上界,于是我们看到(否则将有为全序且),于是看到Y有最大元. 再由反证法和Hausdorff最大性原理知也为X的最大元. 这就证明了:Hausdorff最大性原理Zorn引理.
于是根据习题8.5.17,这两个命题都是逻辑上与选择公理等价的.
8.5.19证明:是的偏序.
1.自反性:由可知.
2.反对称性:设且. 当时显然有;当和互为前段时易知有和(这是一个矛盾而说明不会出现此情形,但我们可以不理会此矛盾继续推理下去),进而知. 再由前段定义中“对任意有当且仅当”知,此时也有.
综上,有.
3.传递性:仿照验证反对称性的简单讨论知传递性成立(需要仔细验证的只有的情形,只要注意到和两者由于为良序故可小值进而.
恰有一个最小元.
因为陈述“存在使得”恒假,故找不到的前段,进而是的最小元.(或者因为是任意非空Y的前段;或者因为对于非空Y有不成立.)
的最大元都是X的良序.
设且,说明存在一个元素使得. 下面我们将说明此时不是的最大元.
现在来考虑集合,我们希望在其上定义一个良序关系使得. 一个很简单的思路就是强行规定元素x为集合的最大元,严格表述即定义上的一个二元关系(二元关系按集合角度解释).
现在来证明是一个偏序集.
1.自反性. 对任意:若则;若则. 综上是自反的.
2.反对称性. 对任意,若有:当时讨论易知只能,进而由为良序知有;当时知;当时说明且,进而发现,这个矛盾说明在说明“”的前提下不会出现此情形.
3.传递性. 对任意,若有:即有. 同时注意到(a, b)的第二个分量和(b, c)的第一个分量均为元素b,说明——
- 3.1:当时必有,进而有,进而容易知;
- 3.2:当时有. 再由知即,进一步知道. 综上,故有;
- 3.3:当时显然有,同理易知,于是. 此时.
综上是一个偏序集.
同理简单讨论容易证明是一个全序集.
同理简单讨论容易证明是一个良序集.
综上,若则,即不是的最大元. 反过来说的最大元均为X的良序.(一个显而易见的事实是:X的良序是的最大元. 于是我们看到“是的最大元”和“是X的良序”是等价的.)
现在来证明:Zorn引理良序原理.
由于故非空. 设A是的任一全序子集,现在我们来证明是A的上界.(是从集合角度理解的二元关系,详见习题8.5.16的解答.) 为了书写方便,我定义,并在必要的时候才将还原为其最初含义.
首先要证明:.
容易证明. 容易证明是偏序. 进而容易证明是全序.
接下来要证明是良序.
以下引用文段为不完整证明,可跳过不看.
设S为的任一非空子集. 我们假设:不存在一个使得,换句话说即对任意均存在使得.
由于S非空则存在,于是我们看到存在使得. 根据上一段的假设我们知:对存在使得,于是我们看到存在使得. 根据我们的假设此操作可以无终结地进行下去(即此操作步骤可以是可数无穷的),于是我们看到
[8.5.19.1]
(. 是根据我们的假设说明存在的. 这里有一个易被忽略但在证明逻辑上很重要的细节:我们至少需要依序选择公理来选出(的选择则只需要在每一步骤中使用引理3.1.6单个选取),但在习题8.5.17已经证明选择公理(其蕴涵依序选择公理)等价于Zorn引理(证明等价过程并未用到良序原理),所以这里不构成循环论证.)
由于且A为全序,于是从公式[8.5.19.1]我们容易发现前段于前段于前段于…(前段于意为:是的前段,其余类同. )
也即 [8.5.19.2]
从链[8.5.19.2](即)我们可以看到链是不会有终结的. 这就说明:当集合S或集合A为有限集时我们的假设是不成立的(因为我们容易从公式[8.5.19.1]和公式[8.5.19.2]知道中对不同自然数有和. 或者直接因为当集合S或集合A为有限集时我们可以通过普通的归纳法证明S中的元素均在A中某个良序集中.). 但是这是不完整的证明,我可以举出一个简单的反例:考虑X是自然数集以及其上的标准序(于是X的任何子集均是良序的),集合A定义为. 于是我们容易发现,于是我们选取集合S就是即定义. 此时我们只要选取以及就会发现公式[8.5.19.1]和公式[8.5.19.2]确实是无矛盾成立的,进而不能推出矛盾来说明假设不成立. 究其原因,是因为我们的假设蕴涵“不存在X上的良序”(因为X上的良序使得假设恒为假. 更进一步地,只要我们考虑集合,比如正在举出的反例,就能看到“不存在X上的良序”蕴涵假设.
由于知道了:假设蕴涵“不存在X上的良序”,于是我们就不可能从假设成立来帮助我们来证明“存在X上的良序”,这是因为我们的逻辑演绎保证了我们从真命题只能得到真命题.
于是这个假设不能帮助我们完成证明,我们需要新的证明路径. 虽然我们确信我们的假设确实是假的(在承认选择公理后确实如此,这也是此题的目的.),但逻辑上我们不能借助我们的假设来来证明我们的假设为假.
回顾习题8.5.11,如果我们能将其推广到“无穷并”的话,那么我们想要的结论“是良序”是显而易见的了. 可惜的是习题8.5.11不能被推广到“无穷并”. 一个显而易见的反例是:考虑实数序列,此序列单调递减收敛到0但永远取值不到0,进而无最小元. 由此,集合中元素均为单元素集故均为良序集,此时不是良序集但是全序集.
幸运的是,我们还有其它办法. 设S为的任一非空子集. 我们大假设S不是序下的良序集,即存在一个S的非空子集无最小元. 由于非空,于是我们可以取一个元素. 从依序选择公理可以得到一个由中元素构成严格递减的可数无穷序列.(选择公理(其蕴涵依序选择公理)等价于Zorn引理(证明等价过程并未用到良序原理),所以这里不构成循环论证.)
观察到,即,故存在使得.
现在分类讨论. 如果为A的最大元(依关系):由于A为全序,进而容易证明对一切均有,进而. 进而我们看到. 并且此时容易证明,进而从可以得到. 于是良序集含有一个严格递减的可数无穷序列,这个矛盾说明不可能为A的最大元. 也就是说存在使得,即是的前段,即存在使得且对一切有当且仅当.
接下来要做的就是证明我们有且.
设且. 设元素. 于是我们看到(由我们可以看到.). 也就是说:对一切,如果那么对一切有,也即有. 而由于对一切有,也即对一切有. 于是乎有:对一切,如果那么对一切有. 进而对一切:由于,说明存在使得. 当时由已证明的“对一切,如果那么对一切有”易知. 当时显然有. 综上,这就证明了.
我们朝我们的目标迈进了一步,现在就是要证明从可得到. 显而易见的是根据定义可以从可得到,现在我们要证明其反方向. 两种论证方式. 第一种反证法:假设不成立,即其不是严格递减序列,于是存在使得且(由于且为良序),进而由定义知道有:存在使得且,这明显与我们已知到的相矛盾,故假设不成立,于是成立. 第二种直接证法:设且. 由是严格单调递减可知有,再由定义知道有存在某个使得. 但是由于有且A为全序,由序定义(即对于可以判断关系的两偶其中的是保持序结构的. 也许这个观察可以早点提出来使得证明更简略一点.)知道恒有. 这就完成了证明.
至此我们看到且,这与是良序相矛盾,于是我们的大假设“S不是序下的良序集”不成立,于是S是良序故其有最小元.
至此的任一非空子集均有最小元.
至此我们可以说是良序. 这就证明了.
现在我们终于可以考虑是否是A的上界了.
设. 为了讨论方便,我们先证明是保持序结构的.
对任意:若则由定义容易证明;若同由定义知存在使得,再由A为全序的和可证得.
于是我们看到是在集合上是相等的,故不妨直接使用来代表,具体代表哪个要根据上下文具体讨论的集合是还是来判断(由于在集合A中的任意性,故对任意我们将不再区分,下面的等式推导8.5.19.3将不再说明此事.).
由上我们可以考虑是否有一个上界.
分类讨论. 若为空集:则说明. 同时我们易知,于是看到. 于是我们看到,也即.
若非空:由为良序知为良序,故可取其最小元记为. 于是我们得到一阶命题:对一切有,也即对一切有若则. 于是我们容易看到对一切有. 这就证明了. 现在我们来证明. 显然的是我们只需要证明:对一切均有即可. 现在开始论证:因为从知存在某个使得,且. 由于A是全序的,故可以看到有“或者”. 但是当时可以看到,进而看到,这个矛盾说明这是不可能的,故只能有. 同时我们看到.[8.5.19.3,推理过程中要注意到每个是存在且是唯一的(这个很容易证明)] 而对一切如果我们已经知有,进而对一切对一切如果那么有,进而可以看到,也即. 综上于是看到. 于是在“非空”的前提下我们也有,也即.
于是我们终于看到是A的上界了.
其实在证明“”的情形下反证法论证更容易简便. 只不过我想尝试一下直接证明到底有多繁琐,嘻嘻. 反证法如下:假设存在使得. 类似直接证明前半部分的论证我们知道,于是我们看到,即有. 同时由于我们看到,结合假设“”我们看到. 综上我们看到和,这个矛盾说明我们的假设不成立,于是对一切均有,进而看到.
综上,由Zorn引理知有最大元,其最大元就是X的良序.
现在来证明:良序原理选择公理.
已知I为集合且对任意有.
若容易知. 也即空函数.
若,容易知非空. 由良序原理知道存在一个良序. 由且非空可知为非空良序集(以为序),故可取其最小元. 于是我们找到了的选择函数(即取每个集合的最小元),故选择公理成立.
至此,我们知道选择公理、Zorn引理和良序原理彼此都是等价的.
2023.12.7补充: 一点题外话. 正如§8.4中所说的那样,我们是否应该接受“选择公理”这件事受到数学、逻辑学、哲学等领域的关注. 如果我们选择接受“选择公理”,那么这就相当于我们接受了“良序原理”. 现在考虑实数集上的良序,我们知道“存在”上的良序,但是我们却不能找到上的一个明显的良序(这里“明显的”意指:对任意非空集合,我们可以由集合的具体表示形式(比如就是同一个集合的不同表示形式)所蕴含的信息根据此良序得到的具体的、有确定数值的、可计算的、可构造的、按某种步骤可知晓的等等类似表述的最小元(当然是在此良序意义下).). 本质上这是因为实数集是不可数集. 回顾习题8.5.16的解答,我们说“实数集是不可数集”是在通常的相等关系=视角下,也即只有在实直线上的每个点都是两两互异的观念下才有“实数集是不可数集”. 但正如习题8.5.16的解答中我对相等关系的讨论,我们可以扩展“相等”的含义而使其具有外延,也即把等价关系~看成是一个新的相等关系. 我们可以证明一个集合上的等价关系可以由集合的一个互不相交分类P()来刻画,比如通常的相等关系=(其也是一个等价关系)可以由集族来刻画. 于是在这样的视角下,对考虑集族,这就是说我们认为实数集中的元素都是(依等价关系外延上)相等的,换句话说实直线上的每个点就只是点而已(本质上没有什么区别或不同). 也即我们对考虑二元关系:当且仅当(或者更简单的),容易验证是上的一个等价关系. 既然我们现在拥有了上的一个新的等价关系(区别于通常的相等关系=),进一步地我们可以定义新实数:形如“”的对象叫作新实数,其中. 我们说两个新实数看作是相等的当且仅当(新实数的集合论解释是). 记全体新实数组成的集合为(使用这个符号的灵感来源于符号). 由于容易看到对任意的两个新实数都有,于是从相等关系要求的“代入公理”的角度看集合是个单元素集,其只包含唯一的一个元素,我们不妨记此元素为,进而可以看到. 当然现在我们的还没有多大的意思,比如我们还没有对其中的新实数考虑任何运算. 我们可以采用偷懒的做法,先不对新实数定义新的运算,而是考虑对实数成立的那些运算律是否对新实数还成立. 答案是依然成立,因为本质上只不过是将实数换成了新实数,也即实数集可以同构地嵌入到新实数集中;但同时答案从“应用”角度说是无意义的,因为任何从“代入公理”的角度看实数的那些运算律对新实数应用后得到的结果只有. 于是对实数集的直观“实直线”,我们有两种极端的理解:实直线上的每个点两两之间都是互异的VS实直线上的每个点就只是点而已(本质上没有什么区别或不同). 从前一种理解我们需要用自然数去“度量”实数,只有这样我们才能完整地认识实数,于是我们不断地做着计算来捕获越来越多的实数:自然数、整数、有理数、代数数、超越数…等等. 可是算的到头吗?通过计算真的能完整认识实数吗?从后一种理解我们本质上说无法认识实数. 我们可以对一个点“”说什么呢?点是什么、什么是点?点存在在现实中吗?本质上说,想要表达的意思是一样的——不存在,我们只不过是使用等等信息来内涵、表达、传递. 就像我们在玩一个思维游戏:想象你是线段上的一点. 我刚开始可能是一个接一个地标记点想抓到你;到后来我借助自然数集来一次操作就标记可数个点想抓到你;最后我想到了一个绝妙的点子,直接在线段上覆盖一条更长的线段来抓到你. 但是我真的抓到你了吗?你都是线段上的一个点了,那么你也就是线段上的一个点,这也就是说你可以从线段上“漏走”. 换句话说我们真的能抓到一个点吗?我们所处的三维空间哪里不可以看作一个点呢?哪里对点来说不是空空如也畅通无阻呢?更何况区区的线段. 看空了、看破了,就明白“点”是抓不住的、不可度量的,就像人心是不可测的.
8.5.20证明:勘误:对集族还应该假设其不含空集.
当为有限集时我们容易用普通的归纳法证明结论成立. 于是我们只需要考虑为无限集的情形.
此结论的直观是这样的:我们不断取出中元素如果满足“与中元素都不相交”就添加进中形成新的(的起始为),直到我们遍历了中的元素. 这样得到的最终集合也是其中元素彼此不相交的,并且中每个不在中的元素至少与的一个元素相交(假设不然,说明存在使得S与中元素均不相交,但是我们已经遍历了中的元素,故绝不会出现此情况,假设不成立.).
这样的直观操作在是无穷集时是0.涉及到无穷步骤的,因为我们要遍历完. 于是我们希望借助Zorn引理来跨越这样的无穷步骤.
同时我们容易观察到这样的一个1.事实:只要我们还未遍历完中元素,我们就能在原的基础上找到新的. 这个事实对应习题8.5.15解答的最末尾对Zorn引理使用的总结“对于偏序集中满足不是最大元的元素i我们总是容易找到偏序集中另一个元素j使得i<j”,至此我们知道我们要考虑的偏序集中元素是什么了,其就是在此直观操作中形成的一系列集合. 具体来说我们应该考虑的集合是.
我们现在就是要为集合找到一个偏序. 根据上面的1.事实,我们知道新是包含旧的,进而我们知道我们应该定义的关系是:对一切,我们说当且仅当. 换句话说我们考虑的是[根据习题8.5.17最后引用部分的说明,关系恰好为时使用Zorn引理是最方便的. 但也如习题8.5.17的第一个解答,这不是使用Zorn引理所必需的.].
为了判断我们是否走在正确的道路上,我们需要验证几点:2.是一个偏序;若其为偏序则3.其最大元就是我们要证明的结论. 对第2点我们知道这是显然的(例8.5.2也有提及). 对第3点,反证法. 假设对此偏序集的最大元S存在使得对一切有. 进而我们看到且(由于不含空集(但自身可以是空集),故C不是空集且中元素不含空集(但中元素可以是空集),进而的最大元S不含空集,即S中的元素不是空集.),这个矛盾帮助我们完成证明.
于是我们确信我们走在正确的方向上,接下来就是借助Zorn引理证明偏序有最大元.
有一个平凡的情形是,此时是符合要求的. 也即我们发现,于是非空.
设D为的全序子集. 接下来我们将证明为D的上界. 1.显然的是对一切集合有; 2.对任意有:存在使得. 而,于是我们看到,即,进而. 综上我们看到,即. 3.而对任意,如果:由知存在使得,由于D为全序故知之间有一个包含另一个,不妨假定,进而看到,再由结合我们看到. 综合2.和3.可知. 再结合1.我们知道为D的上界.
由Zorn引理可知集合确实有最大元. 其最大元满足题目要求.
现在来证明题目的结论蕴含习题8.4.2的结论.
题目结论:设X是集合,并设是X的一个不含空集的子集族(即),那么存在一个子族使得中的元素是两两不相交的且中的每个元素至少与中的一个元素相交.
从选择公理思考习题8.4.2的结论是十分自然的,前面我们已经说明题目结论的直观是怎样的,如果考虑集合而显然我们只能得到一个不满足习题8.4.2结论要求的集族(除去某些平凡的例子,如,或者对一切有为单元素集等.).
观察习题8.4.2结论要求的形式,我们自然而然想到可以考虑集合而,此时容易知. 问题出在对每个我们取出中的一个元素后不能阻止继续取出中的元素. 继续观察题目结论的直观,其能排除掉具有共同元素的集合出现在中,于是我们可以耍一些小花招:对每个,考虑,我们可以为中的所有添加同一个标记而利用上题目结论直观帮助我们对每个只取出中的一个元素. 具体来说,我们可以考虑:(为使得,由于对不同的有于是我们知道是唯一的,不会出现不良定义.),对于X具体是什么我们可以暂时不考虑因为我们总可以根据我们的拼凑出来. 于是我们可以知道题目的提示是怎样思考得来的了,虽然题目提示在的具体形式上和我提出的略有不同,但思考的解决方式是一致的. 如果按照我所构造的集合,在最后从的每个元素提取出我们需要的进而组成习题8.4.2要求的集合Y时,我们遇到了一个困难就是我们无法区分中到底哪个是而哪个是,于是为了区分中元素我们将其改造成形式.
我啰啰嗦嗦写下具体的思考过程,主要是因为考虑到严格的证明可能会隐藏真正的points. 而其实严格的证明只是思考数学的最后一个步骤,其主要作用是从逻辑上排除掉(所有)可能的错误或者发现未考虑到的情形而确保你的解决方法是正确周全的. 更甚者,严格证明可以写的非常形式化,让读的人可以跟随其证明步骤验证证明是正确无误的但可能永远get不到其思考切入点. 好一点的作者会提及思考切入点、具体思路或者直观理解. 学会思考远比写下一个证明重要,证明只不过是你思考的严格表述,至于证明的细枝末节你自己应该可以胸有成竹地写下来. 也就是说写证明这件事与学骑自行车、学游泳没有本质区别,在经过大量的训练后总是可以学好的;至于你的思考正不正确就要通过写下一个证明或者参考别人的证明思路来判断.
现在我们来写下严格的证明.
依提示我们考虑(当然的严格表示是,前者是由万有分类公理得来的概括形式,至于这里为什么可以使用万有分类公理公理3.8详见《陶哲轩实分析》(中文第一版)——§3.4解答中对习题3.4.6的评论. 当然我们可以证明和前面的讨论我给出的是相等的,严格证明就不妨采用提示中的形式了.)
由题目8.5.20的结论我们知:存在使得中元素彼此均不相交且中每个元素都至少与的一个元素相交. 进而用反证法容易证明“对任意存在使得”,进而容易证明“对任意恰存在一个使得”.
我们定义集合,接下来就是证明集合Y就是习题8.4.2要求的集合.
对任意,我们已经知“对任意恰存在一个使得”,于是恰存在一个使得. 进而我们看到,于是. 反证法简单论证我们将看到. 这就完成了证明.
文内补充
1.全序集的任何子集都是全序的.
显然.
2.良序集的每个子集还是良序的.
显然.
3.注8.5.11的“为什么?”.
因为对于真蕴涵关系来说,前件为真(不管是实质真还是空真,此处的情况为空真)时后件必为真.
4.定义8.5.12中“为什么这是等价的?”.
显然.
5.X的子集显然是好的.
显然.
6.也以为其最小元.
反证法容易证明,或者直接证明也可以.
7.此事对于每个使得非空的好集合都成立.(详见勘误,修改表述原因是对非空集合才会考虑其最小元. 此修改不会影响接下来证明,即书中接下来的论证无需修改就是有效的.)
显然. 因为:当时. 当时.
8.为的最小元.
显然.
9.选择公理紧密联系于序集理论.
10.定义8.5.1(偏序集)中的反对称性已经默认在X上有一个相等“=”关系. 从反对称性可以看到不能同时成立. 同时从偏序集定义可以看到“如果有则.”.
11.最大元和最小元都是相对的. 某个元素在某个序下是某个集合的最大元,那么在此集合的另一个序下可以变成最小元,比如和.
12.偏序集可以有多个最大元和多个最小元.
13.命题8.5.10应该看作“归纳原理的集合版本”. 良序集自动服从强归纳原理.
14.从定义8.5.12容易得到:有上界但无严格上界的集合必有最大元,其一个(同时容易证明是唯一的)最大元就是前面提到的上界. 详见习题8.5.14的讨论.
15.引理8.5.14中“它没有严格上界”应该说明:严格上界应严格限定于X中.
16.引理8.5.14直观中步骤“从开始不断添加严格上界进Y中”重复有限次后得到的Y仍是以为最小元的良序的理由——由习题8.5.11保证.
17.给定任何两个好集合Y和Y’,Y’\Y和Y\Y’中至少有一个为空(原文为“不空”,此处应该勘误.).
反证. 假设Y’\Y和Y\Y’均非空,于是存在,根据习题8.5.13的结论我们看到,这是一个矛盾.
18.引理8.5.15(Zorn引理)也应该说明:a.上界严格限定于X中.
b.实际上引理8.5.15的陈述“不空的”可以省略进而Zorn引理变成“设X是一个偏序集. 如果X的每个全序子集Y都有上界那么X至少含有一个最大元.”,只要注意到X为空集时蕴含式命题“如果X的每个全序子集Y都有上界那么X至少含有一个最大元.”是空真的成立的. 但是在实践中我们总是需要X非空来保证我们可以使用原引理8.5.15来得到一个最大元;在X为空集时修改后的Zorn引理变成一个空真的蕴含命题,即此时修改后的Zorn引理为真但我们却得不到X的一个最大元(因为我们可以从对全序集空集有上界知道X非空).
19.设为偏序集.
当X为有限集时对可以使用哈斯图完全刻画.
当X为无穷集时,我们不能画出其哈斯图,但形如哈斯图的想象仍是行得通的. 也即——
19.1.为偏序集时:X中元素可以依序排成一条条链(每条链是最大的全序,其中“最大”的含义详见习题8.5.18的Hausdorff最大原理),全体的链就完全刻画了;
19.2.进而为全序集时:表明我们只有一条链. 于是习题8.5.16的最后一问其实说的就是“我们总可以将多条链“(保持序结构)接”成一条链”;
19.3.进而为良序序集时:表明我们唯一的链有唯一端点(起始)使得从此端点依序增长,并且所有由此链中元素组成的保持序结构的子链也有唯一端点使得从此端点依序增长.
20.第19.点对偏序集补充的直观可以用于以下命题——引理8.5.14、引理8.5.15、习题8.5.16结论(见19.2.).
您必须登录才能发表评论。