西安电子科技大学离散数学软件学院第二篇集合论第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中的所有外部元素构成 的集合