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

集合的基数 v基数-集合中元素的个数. v本章主要借助于函数讨论集合的所谓“大小” 问题。 一.自然数 v定义: 对任意集合A, 定义 vA+=AA v称A+为A的后继, A为A+的前驱. v例: 若A=, 则 v+= v(+)+=. v(+)+)+= 一.自然数 v定义: 集合0=是一个自然数, 若集合n是一个 自然数, 则集合n+1=n+也是一个自然数. v0= v1=0+=00=0 v2=1+=11=0, 1 v3=2+=22=0, 1, 2 v vn+1=n+=0, 1, 2, 3, , n. v定义: 设F是一个函数, Adom F, 对xA, 有 F(x) A, 则称A在函数F下是封闭的. vPeano系统是满足以下公理的有序三元组, 其中M为一个集合, F为函数, e为首元素. 5条 公理为 v(1) eM. v(2) M在F是封闭的. v(3) eranF. v(4) F是单射. v(5) 若M的子集A满足 v eA v A在F下是封闭的, 则A=M v定理. 设N为自然数集合, : NN, 且(n)=n+, 则 是Peano系统. 一.自然数 v定义: 对任意的自然数m和n. vmm vmnmnnm v定理. 对任意的自然数m和n, 下列三式有且仅有一 式成立： v mn（三歧性）。 v注1：任何自然数都不是自己的元素。 v注2：任何自然数都是它自己的子集。 v注3: mAm(n) 记Am(n)=m+n. v其中Am(0)=m, Am(n+)= (Am(n)+, 则称 +为N上的加法运算. v例: 由加法定义计算3+2. v定理. 设m, nN, 则 v0+m=m+0=m (加法规则1) vm+n+=(m+n)+ (加法规则2) v证明: m+0=Am(0)=m. (定义) v0+m=A0(m)=A0(m-1)+)= vm+n+=Am (n+)=(Am(n)+=(m+n)+ v例: 利用加法规则计算3+2 乘法 v定义: 令 : NNN, 且对m, nN, v Mm(n), 记作Mm(n)=mn. v其中Mm(0)=0, Mm(n+)=Mm(n)+m, 则称 为N上的乘法运算. v例: 利用定义计算32. v定理. 设m, nN, 则 vm0=0 (乘法规则1) vmn+=mn+m (乘法规则2) v例: 利用乘法规则1和2重新计算32. 指数运算 v定义: 设: NNN, 且对m, nN, Em(n), 记作:mn.称为N上 的指数运算.其中Em(0)=1, Em(n+)=Em(n) m. v例: 用定义计算32. v定理. 对m, nN, 有 vm0=1 vmn+=mnm. 性质 v定理. 设m, n, kN, 则 v(1) m+(n+k)=(m+n)+k v(2) m+n=n+m v(3) m(n+k)=mn+mk v(4) m(nk)=(mn) k v(5) mn=nm 整数集合Z v定义: 对自然数集合N, 令 vZ+=N-0. vZ=n Z+. vZ= Z+0Z. v则称Z+的元素为正整数, Z的元素为负整数, Z的元素为整数. 集合的等势 v定义: 设A, B为两个集合, 如果存在A到B的双 射函数, 则称A和B等势, 记AB. 否则称A和B 不等势, 记(AB)或AB. v例: N偶=nnNn为偶数. vN奇=nnNn为奇数. vN2n=xx=2n nN. v则N N偶, N N奇, NN2n v例: NZ. v解: 取f: NZ, 且nN, v v或, 取g: ZN, 对nZ v 例: NQ. 因为每个有理数都可以写成一个分数形式如下： 可以从0/1开始按照箭头指定次序排列Q中元素 所以NQ 。 另外 ZZN 如右图所示。 0/11/12/13/1-1/1-2/1-3/1 -1/2-2/2-3/20/21/22/23/2 0/31/32/33/3-1/3-2/3-3/3 -1/4-2/4-3/40/41/42/43/4 . . . . . . . . . . . . . . . 01 1 2 2 3-1 -1 -2 -2 -3 v例: (0, 1)R. v解: x(0, 1), f(x)=tg . v例: 0, 1(0, 1) 定理. (康托尔定理) (1) (NR) (2) 对任意的集合A, (AP(A). 3 有限集合与无限集合 v定义: 集合A是有限集合, 当且仅当存在nN, 使nA. 否则, 称A为无限集. v定理1. 不存在与自己的真子集等势的自然数. v推论1. 不存在与自己的真子集等势的有限集合 . v推论2. 任何与自己的真子集等势的集合是无限 集合. v推论3. 任何有限集合只与唯一的自然数等势. 4 集合的基数 v定义: 设A为任意一个集合, 用card(A)表示A中的元素 个数, 并称card(A)为集合A的基数. 作以下5条规定: v(1) 对集合A, B, 规定 vcard(A)=card(B) AB v(2) 对有限集合A, 规定与A等势的自然数n为A的基 数. 记作: card(A)=n. v(3) 对自然数集合N, 规定 vcard(N)=0 v(4) 对于实数集合R, 规定 vcard(R)=1 v(5) 将0, 1, 2, , 0, 1都称作基数. 其中自然数0, 1, 2, 称为有限基数, 0, 1称为无限基数. v例: A=a, b, c, B=a, b, c. vN偶=n | nNn为偶数, vN奇=n | nNn为奇数 可数集合 v定义1: 对集合K, 如果card K0, 则称K是可 数集合. v定义2: 如果集合K是有限的或与N等势, 则称 K是可数集合. v定理. 集合A是无限可数集合A可写成如下 的式a1, a2, , an, . v定理 (1) 可数集合的任何子集是可数集. v证: 设A可数, BA, 则BA,即 v card B card A 0. v(2) 两个可数集的并集和笛卡尔积是可数集. v证: A=a11, a12, , a1n, , vB=a21, a22, , a