首先回忆一下有限集是怎么比较的。两个**,A={0,1},B={2,3},哪个大(或者说哪个多)?答案自然是一样多。因为它们都有两个元素,或者说它们之间是一一对应的(0和2,1和3对应)。以此为出发点,我们可以定义两个**的大小比较-**的势(cardinality)。 海鲜蒸柜定义:称两个**等势如果这两个**之间有双射(即是单射又是满射)。 钢丝线
记号:用|A|表示**A的势。A,B等势记作|A|=|B|。 引理1:等势是一个等价关系(即满足 1.|A|=|A|,2.|A|=|B|推出|B|=|A|,3.若|A|=|B|,|B|=|C|,则|A|=|C|)。
证明:以3为例,|A|=|B|,则有一个双射f: A->B。|B|=|C|,则有一个双射g: B->C,则g,f 的复合g?f (x)=g(f(x))是从A到C的双射。
中间道路
定义了什么是两个**一样大,再回过头来看看什么是一个**比另一个**大。考虑A={0,1}, B={2,3,4},则B大,因为A有2个元素B有3个,或者说把它们一个一个的拿出来,A拿完了,B还有剩下。但是,这种看法在有限时是合理的,当A,B是无限集时就不合理了。比如自然数集N和整数集Z,有两种拿法:1. N中拿n的时候Z中拿n,这样N中拿完了Z还有剩下,所以Z大。2. N中拿3n的
时候Z中拿n,N中拿3n+1的时候Z中拿-n,这样Z中拿完了N还有剩下,所以N大。也就是说,对无限集来说,这种方法不是一个合理的比较大小的方法。
定义:称**A的势小于**B的势如果有从A到B的单射,但是没有从B到A的单射。记作|A|<|B|。
三维打印也就是说,有一种拿法,A拿完了,B还有剩下,但是没有一种拿法使得,B拿完了,A还有剩下。
记号:f是从X到Y的映射,W是X的子集,则f’’W={f(x)|x∈W},即f在W上的象集。引理2:如果有从A到B的单射f,和从B到A的单射g,则存在从A到B的双射,即|A|=|B|。证明:令A0=A,B0=B-f’’A0,A(n+1)=A-g’’Bn,B(n+1)=B-f’’A(n+1),归纳的定义了一列递降的子集An和一列递增的子集Bn,令A’=limAn=∩An,则h:A->B,当x∈A’时h(x)=f(x),当x?A’时h(x)=g^(-1)(x)(g^(-1)表示g的逆函数)。h的定义是合理的并且是A到B的双射,验证比较繁琐,此处略。
引理3: **之间的势比较<是一个线性序(即满足对任意**A,B,C,1. |A|≮|A|,2. 若|A|<|B|且|B|<|C|,则|A|<|C|,3. |A|,|B|之间可比较,即或者|A|<|B|,或者|A|=|B|,或者|A|>|B|)。证明:1是平凡的。2. 由定义易知A到C之间有单射,若C到A之间有单射,则C到B之间有单射,与|B|<|C|矛盾,所以C到A之间没有单射,即|A|<|C|。3. 由选择公理知(证明比较繁琐,此处略),或者A到B之间
有单射,或者B到A之间有单射。以A到B之间有单射为例,如果B到A之间有单射,则|A|=|B|,满足,如果B到A之间没有单射,则|A|<|B|,满足。
到此,我们就把**的大小比较从有限集扩展到了无限集,并且,任何两个**都可以比较大小。下面考虑比较大小的方法,一个方法就是,给定两个**A,B后,分别看A到B和B到A之间是否有单射。但是这样比较麻烦,比如A到A*B={(x,y)|x∈A,y∈B}之间有单射,但是A*B到A之间是否有单射呢?如果有,是哪个,如果没有,怎么证?
回忆有限集的比较,A={0,1}少于B={2,3,4}是因为A有2个B有3个。我们了一个东西作为过渡,把A等势于一个小于2的自然数集(当然A本身就是小于2的自然数集),把B等势于一个小于3的自然数集,然后比较这两个自然数集的大小。同样的,在无限集的时候,我
们也可以一个东西作为过渡。经过前人研究发现把良序集作为过渡是目前为止最好的手段,所以,现在用一个和A等势的最小良序集来表示A的势。
定义:称(A,<)是一个良序集如果<是一个线性序且A的任意子集都有一个最小元。
记号:良序集(A,<)的前段是指({x∈A|x<a},<),其中a是A中的一个元素。
引理4:任意两个良序集(A,<),(B,<’)均可比较(即要么(A,<),(B,<’)同构,要么其中一个同构于另一个的前段)。
证明:定义f: A->B,f(a)=B-{f(x)|x<a}的最小元(注意,若取a为A的最小元,则B-{f(x)|x<a}=B,即f(a)=B的最小元)。由超限归纳法,最后,要么在某个a∈A的时候B={f(x)|x<a},从而f(a)没有定义,要么f在A上有定义。第一种情况,B同构于A的前段({x∈A|x<a},<),第二种情况,若f的象集是B,则A,B同构,若f的象集是B的前段,则A同构于B的前段。
所以在同构意义下,良序集长度决定一切,长度一样的两个良序集是一样的。然后我们用序数表示一个良序集的长度,也即表示一个良序集。以下涉及到的东西比较复杂且过于繁琐,所以用描述代替定义且省略一些严格论证部分。 描述:称一个**为序数如果它是由所有属于(此处等价于小于)自己的序数组成。规定最小的序数为0
举例:0是最小的序数,所以没有序数∈0,即0=?,1={0}={?},2={0,1}={?,{?}},……,ω={0,1,2,…,n,n+1,…}也就是自然数集,是第一个无穷序数,ω+1= ω∪{ω},……
易知,ω和ω+1是等势的,所以,有了以下概念。
定义:称一个序数κ为基数(cardinal)如果任何比κ小的序数和κ之间没有双射(即势小于κ)。(注意,我们常用κ表示基数,就好像用n表示自然数,而ω是特指最小的那个无穷序数,就好像0表示最小的自然数,同时,ω也是基数)。 举例:ω是基数,ω+1不是基数。任意有限的序数是基数。
记号:如果κ是基数,我们用κ本身表示κ的势|κ|。如无特殊说明,n表示有限的基数,κ,λ等表示无穷基数(无穷基数即不是有限的基数)。
引理5:任何一个**A,都存在唯一一个基数κ,使得|A|=κ。
证明:略。
定义:A+B={(x,0)|x∈A}∪{(y,1)|y∈B},A*B={(x,y)|x∈A,y∈B}。
定义:基数的加法和乘法:κ,λ是基数,则κ+λ表示和用上面定义加法得到的**等势的基数,κ*λ表示和用上面定义乘法得到的**等势的基数。即,基数只考虑势。
举例:作为基数来说,ω+1=ω(注意,作为序数来说ω+1≠ω),ω+ω=ω(也即,两个可数集的并还是可数集)。
引理6:若|A|=κ,|B|=λ,则|A+B|=κ+λ,|A*B|=κ*λ。
网篮法证明:平凡的。
引理7:若κ是无穷基数,则κ+κ=κ。
证明:反证。若κ+κ>κ,则存在最小的无穷基数(注意,基数是良序集)λ满足λ+ λ>λ。λ+ λ={(x,0)|x∈λ}∪{(y,1)|y∈λ}上的字典序(即第一位较大的大,若第一位相等,则第二位较大的大)为良序且势大于λ,由引理4,λ同构于λ+λ上字典序的一个前段,推出λ等势于λ+λ的一个前段,即有一个x∈λ,λ等势于x+x(即λ=|x+x|),又由基数的定义,知|x|<λ,再由λ的最小性,|x|+|x|<λ,再由引理6,|x+x|<λ。矛盾。
引理8:若κ是无穷基数,则κ*κ=κ。
证明:方法同上,只是考虑λ*λ上的Godel序(即先比较两位中最大的数,若最大的相等再比较第一位,若最大的和第一位都相等,再比较第二位)而不是字典序。
引理9:若κ<=λ,且λ是无穷基数,则κ+λ=κ*λ=λ。
证明:λ<=κ+λ<=λ+λ=λ,λ<=κ*λ<=λ*λ=λ。
冰雕模具推论10:若A,B中至少有一个无限集,则|A+B|=|A*B|=max{|A|,|B|}。特别的,令N=自然数集,Z=整数集,R=实数集,C=复数集,则|Z|=|N+N|=|N|,|N|<=|Q|<=|N*N|=|N|, |C|=|R*R|=|R|,|2^N|<=|N^N|<=|(2^N)^N|=|2^(N*N)|=|2^N|,|2^N|=|N^N|=|Q^N|=|R|, |R^N|=|(2^N)^N|=|2^(N*N)|=|2^N|=|R|(即可数无穷维实数空间和1维实数空间等势,也可以推出R上的连续函数全体和R等势)。
豫公网安备41160202000603
站长QQ:729038198
关于我们
投诉建议