离散数学实数集合与集合的基数.pptVIP

集合的基数 基数----集合中元素的个数. 本章主要借助于函数讨论集合的所谓“大小”问题。 一.自然数 定义: 对任意集合A, 定义 A+=A∪?A? 称A+为A的后继, A为A+的前驱. 例: 若A=Ф, 则 Ф+= (Ф+)+=. ((Ф+)+)+= 一.自然数 定义: 集合0=Ф是一个自然数, 若集合n是一个自然数, 则集合n+1=n+也是一个自然数. 0=Φ 1=0+=0∪?0?=?0? 2=1+=1∪?1?=?0, 1? 3=2+=2∪?2?=?0, 1, 2? … n+1=n+=?0, 1, 2, 3, … , n?. 定义: 设F是一个函数, A?dom F, 对?x?A, 有F(x) ?A, 则称A在函数F下是封闭的. Peano系统是满足以下公理的有序三元组M, F, e, 其中M为一个集合, F为函数, e为首元素. 5条公理为 (1) e?M. (2) M在F是封闭的. (3) e?ranF. (4) F是单射. (5) 若M的子集A满足 ① e?A ② A在F下是封闭的, 则A=M 定理. 设N为自然数集合, σ: N→N, 且σ(n)=n+, 则N,σ, 0是Peano系统. 一.自然数 定义: 对任意的自然数m和n. mn?m?n?nm m?n?m?n?n≥m 定理. 对任意的自然数m和n, 下列三式有且仅有一式成立： mn?m=n?mn（三歧性）。 注1：任何自然数都不是自己的元素。 注2：任何自然数都是它自己的子集。 注3: mn?m?n. 自然数的运算 1. 加法 定义: 令+:N×N?N, 且对?m, n?N m, n?Am(n) 记Am(n)=m+n. 其中Am(0)=m, Am(n+)= (Am(n))+, 则称+为N上的加法运算. 例: 由加法定义计算3+2. 定理. 设m, n?N, 则 0+m=m+0=m (加法规则1) m+n+=(m+n)+ (加法规则2) 证明: m+0=Am(0)=m. (定义) 0+m=A0(m)=A0((m-1)+)=… m+n+=Am (n+)=(Am(n))+=(m+n)+ 例: 利用加法规则计算3+2 乘法 定义: 令 ? : N?N?N, 且对?m, n?N, m, n?Mm(n), 记作Mm(n)=m?n. 其中Mm(0)=0, Mm(n+)=Mm(n)+m, 则称 ? 为N上的乘法运算. 例: 利用定义计算3?2. 定理. 设m, n?N, 则 m?0=0 (乘法规则1) m?n+=m?n+m (乘法规则2) 例: 利用乘法规则1和2重新计算3?2. 指数运算 定义: 设⊙: N?N?N, 且对?m, n?N, m, n?Em(n), 记作:mn.称⊙为N上的指数运算.其中Em(0)=1, Em(n+)=Em(n) ?m. 例: 用定义计算32. 定理. 对?m, n?N, 有 m0=1 mn+=mn?m. 性质 定理. 设m, n, k?N, 则 (1) m+(n+k)=(m+n)+k (2) m+n=n+m (3) m?(n+k)=m?n+m?k (4) m?(n?k)=(m?n) ?k (5) m?n=n?m 整数集合Z 定义: 对自然数集合N, 令 Z+=N-?0?. Z?=?0, n?n? Z+?. Z= Z+∪?0?∪Z?. 则称Z+的元素为正整数, Z?的元素为负整数, Z的元素为整数. 集合的等势 定义: 设A, B为两个集合, 如果存在A到B的双射函数, 则称A和B等势, 记A≈B. 否则称A和B不等势, 记?(A≈B)或?A≈B. 例: N偶=?n?n?N?n为偶数.? N奇=?n?n?N?n为奇数.? N2n=?x?x=2n? n?N.? 则N≈ N偶, N≈ N奇, N≈N2n 例: N≈Z. 解: 取f: N?Z, 且?n?N, 或, 取g: Z?N, 对?n?Z 例: N≈Q. 因为每个有理数都可以写成一个分数形式如下： 可以从0/1开始按照箭头指定次序排列Q中元素 所以N≈Q 。 另外 Z×Z≈N 如右图所示。 例: (0, 1)≈R. 解: ?x?(0, 1), f(x)=tgπ . 例: [0, 1]≈(0, 1) §3 有限集合与无限集合 定义: 集合A是有限集合, 当且仅当存在n?N, 使n?A. 否则, 称A为无限集. 定理1. 不存在与自己的真子集等势的自然数. 推论1. 不存在与自己的真子集等势的有限集合. 推论2. 任何与自己的真子集等势的集合是无限集合. 推论3. 任何有限集合只与唯一的自然