西安电子科技大学：《离散数学》课程教学课件（题解）第四章 函数与无限集合 4-4 基数的比较

西安电子科技大学离散数学软件学院第二篇集合论第4章函数与无限集合第21课时4.1函数的概念一第22课时4.2复合函数和逆函数第23课时4.3可数与不可数集合第24课时4.4集合基数的比较

西安电子科技大学 离散数学 软件学院 第二篇 集合论 第21课时 4.1 函数的概念 第4章 函数与无限集合 4.3 可数与不可数集合 4.2复合函数和逆函数 4.4 集合基数的比较 第22课时 第23课时 第24课时

西安电子科技大学S4.4.1集合基数的大小软件学院家设A、B是任意集合。（a）如果存在一个从A到B的双射函数，那么A、B等势（基数相同），记为|A|=B|：(b）如果存在一个从A到B的单射函数，那么|A≤|B|;（c）如果存在一个从A到B的单射函数，但不存在双射函数，那么|A||B|。『定理』（Cantor-Schroder-Bernstein定理）设A和B是集合，如果|A|<|B|且|B|<IA|，那么|A|=|B」

西安电子科技大学 §4.4.1 集合基数的大小 软件学院 『定理』 （Cantor-Schroder-Bernstein定理）设A和B 是集合，如果|A|≤|B|且|B|≤|A|，那么|A|=|B|。 设A、B是任意集合。 （a）如果存在一个从A到B的双射函数，那么A、B等势（基 数相同），记为|A|=|B|； （b）如果存在一个从A到B的单射函数，那么|A|≤|B|； （c）如果存在一个从A到B的单射函数，但不存在双射函数， 那么|A||B|

西安电子科技大学集合基数的大小$4.4.1软件学院【例题】证明[0,1]与(0,1)等势。证明：分别构造单射函数和g如下：I (0,1) / ≤/[0,1]f(x)=xf:(0,1)→[0,1]I[0,1] / ≤/ (0,1) 1G:[0,1]-→(0,1)g(x)=x/2+1 / 4 I故[0,1]与(0,1)等势

西安电子科技大学 软件学院 【例题】证明[0,1]与(0,1)等势。 证明：分别构造单射函数f和g如下： f:(0,1)→[0,1] f(x)=x G:[0,1]→(0,1) g(x)=x/2+1/4 |(0,1)|≤|[0,1]| |[0,1]|≤|(0,1)| 故[0,1]与(0,1)等势。 §4.4.1 集合基数的大小

西安电子科技大学S4.4.1集合基数的大小软件学院家家家『定理』设A是有限集合，则|A|<<证明：（1）设A任意有限集合，IA/=n。则A~{0,1,2,...,n-1) 。构造函数f:{0,1,2,...,n-1)→N，f(x)=X。显然,f是个单射而非满射函数，所以n<N|=Xo°2）前面用Cantor对角线法已证N与(O,1)之间不可能出现满射函数。构作单射函数g:N→(O,1)如下：g(x)=1 / (x+ 1)故有

西安电子科技大学 §4.4.1 集合基数的大小 软件学院 『定理』设A是有限集合，则|A|< א 0< א 证明：（ 1 ） 设 A任意有限集合，|A|=n。则 A~{0,1,2,.,n-1} 。 构造函数f:{0,1,2,.,n-1} → N ，f(x)=x。显然， f是个单射而非满射函数，所以n<|N|= א 0 。 （2）前面用Cantor对角线法已证N与(0,1)之间不可 能出现满射函数。构作单射函数g:N→(0,1)如下： g(x)=1/(x+1) 故有 א 0< א

西安电子科技大学集合基数的大小$4.4.1 软件学院家教务『思考题1』有限集合基数|A|与之间是否存在其它基数等级？『思考题2』与之间是否存在其它基数等级？『思考题3』之后是否存在大于x的其它基数等级？

西安电子科技大学 §4.4.1 集合基数的大小 软件学院 『思考题1』有限集合基数|A|与א0之间是否存在其 它基数等级？ 『思考题2』 א0与א之间是否存在其它基数等级？ 『思考题3』 א之后是否存在大于א的其它基数等级？

西安电子科技大学S4.4.1集合基数的大小软件学院教家『定理』任一无限集合必存在可数无限子集。证明：设A是一个无限集合，可以用以下方式构造一个A的可数无限子集B。首先设B=の。从A中任取一个元素a1，令B=BUa，因为A是无限的，因此A-B仍然是一个无限集；从A-B中任取一个元素a2，令B=BUa2j，此时A-B仍然是一个无限集，。如此下去，所得集合B即为A的一个无限可数子集

西安电子科技大学 软件学院 『定理』任一无限集合必存在可数无限子集。 证明：设A是一个无限集合，可以用以下方式构造 一个A的可数无限子集B。 首先设B=∅ 。从A中任取一个元素a1，令B=B⋃ {a1}，因为A是无限的，因此A-B仍然是一个无限 集；从A-B中任取一个元素a2，令B=B⋃{a2}，此时 A-B仍然是一个无限集，.。如此下去，所得集合 B即为A的一个无限可数子集。 §4.4.1 集合基数的大小

西安电子科技大学s4.4.1集合基数的大小软件学院家『定理』o是最小的无限集基数。证明：设A是任一无限集合，A必包含一个可数无限子集B。构作函数f：B→A，使得f(区)=X，f是单射的，所以IB|<IAI。因为「B=o，所以Ko≤「A|。由A是任意的，得<是最小的无限集基数

西安电子科技大学 §4.4.1 集合基数的大小 软件学院 『定理』 א 0是最小的无限集基数。 证明：设A是任一无限集合，A必包含一个可数无 限子集B。构作函数f: B→A，使得f (x)=x，f是单 射的，所以|B|≤|A|。 因为|B|= א 0，所以 א 0≤|A|。由A是任意的， 得 א 0是最小的无限集基数

安电子科技大学S4.4.2基数无限性和连续统假设软件学院家家家『连续统假设』1878年，康托尔提出连续统假设，断言在与x之间不存在其它基数。1940年哥德尔和科恩部分的回答了这个问题，但连续统假设作为数学界的十大难题之一至今仍然没有得到解决

西安电子科技大学 §4.4.2 基数无限性和连续统假设 软件学院 『连续统假设』1878年，康托尔提出连续统假 设，断言在 0 א 与 。之间不存在其它基数א 1940年哥德尔和科恩部分的回答了这个问题，但 连续统假设作为数学界的十大难题之一至今仍然 没有得到解决

西安电子科技大学集合基数的大小$4.4.1软件学院『定理』（Cantor定理）设M是任一集合，则有[M|<Ip(M) I证明：（a）首先证明IM|<|p(M)|构造函数f:M→p(M)，令f(a)=(a)，则f是单射，故[M /≤ Ip(M)/。任一集合的基数小于其幕集的基数

西安电子科技大学 §4.4.1 集合基数的大小 软件学院 『定理』（Cantor定理）设M是任一集合，则有 |M|<|ρ(M)| 任一集合的基数小于其幂集的基数。 证明：（a）首先证明|M|≤|ρ(M)|。 构造函数f: M→ρ(M)，令f (a)={a}，则f是单射，故 |M|≤|ρ(M)|

西安电子科技大学S4.4.1 集合基数的大小软件学院教家家证明：（b）证明|M|≠|p(M)lc设g：M→p(M)是任意函数，证明g不是满射的。函数g将M中每个元素x映射到M的一个子集g(x)，元素x可能在g(x)中，也可能不在g(x)中。若x Eg (),则称x为内部元素；否则，称x为外部元素，显然任一元素x必恰为内部元素或外部元素之一。定义S=区1x g (x)，XEM)，即S是由M中的所有外部元素构成的集合

西安电子科技大学 §4.4.1 集合基数的大小 软件学院 证明：（b）证明|M|≠|ρ(M)|。 设g: M→ρ(M)是任意函数，证明g不是满射的。 函数g将M中每个元素x映射到M的一个子集g(x)，元 素x可能在g(x)中，也可能不在g(x)中。若x∈g (x)， 则称x为内部元素；否则，称x为外部元素，显然任一 元素x必恰为内部元素或外部元素之一。定义S={x | x ∉ g (x)，x∈M}，即S是由M中的所有外部元素构成 的集合