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

集合的基数v基数----集合中元素的个数. v本章主要借助于函数讨论集合的所谓“大小” 问题一.自然数v定义: 对任意集合A, 定义vA+=A∪Av称A+为A的后继, A为A+的前驱.v例: 若A=Ф, 则vФ+=v(Ф+)+=.v((Ф+)+)+=一.自然数v定义: 集合0=Ф是一个自然数, 若集合n是一个 自然数, 则集合n+1=n+也是一个自然数.v0=Φv1=0+=0∪0=0v2=1+=1∪1=0, 1v3=2+=2∪2=0, 1, 2v…vn+1=n+=0, 1, 2, 3, … , n.v定义: 设F是一个函数, Adom F, 对xA, 有 F(x) A, 则称A在函数F下是封闭的.vPeano系统是满足以下公理的有序三元组, 其中M为一个集合, F为函数, e为首元素. 5条 公理为v(1) eM.v(2) M在F是封闭的.v(3) eranF.v(4) F是单射.v(5) 若M的子集A满足v ① eAv ② A在F下是封闭的, 则A=Mv定理. 设N为自然数集合, σ: N→N, 且σ(n)=n+, 则 是Peano系统.一.自然数v定义: 对任意的自然数m和n.vmmvmnmnn≥mv定理. 对任意的自然数m和n, 下列三式有且仅有一 式成立：v mn（三歧性）。

v注1：任何自然数都不是自己的元素v注2：任何自然数都是它自己的子集v注3: mAm(n) 记Am(n)=m+n.v其中Am(0)=m, Am(n+)= (Am(n))+, 则称 +为N上的加法运算.v例: 由加法定义计算3+2.v定理. 设m, nN, 则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定义: 令  : NNN, 且对m, nN, v Mm(n), 记作Mm(n)=mn.v其中Mm(0)=0, Mm(n+)=Mm(n)+m, 则称  为N上的乘法运算.v例: 利用定义计算32.v定理. 设m, nN, 则 vm0=0 (乘法规则1)vmn+=mn+m (乘法规则2)v例: 利用乘法规则1和2重新计算32.指数运算v定义: 设⊙: NNN, 且对m, nN, Em(n), 记作:mn.称⊙为N上 的指数运算.其中Em(0)=1, Em(n+)=Em(n) m.v例: 用定义计算32.v定理. 对m, nN, 有vm0=1vmn+=mnm.性质v定理. 设m, n, kN, 则v(1) m+(n+k)=(m+n)+kv(2) m+n=n+mv(3) m(n+k)=mn+mkv(4) m(nk)=(mn) kv(5) mn=nm整数集合Zv定义: 对自然数集合N, 令vZ+=N-0.vZ=n Z+.vZ= Z+∪0∪Z.v则称Z+的元素为正整数, Z的元素为负整数, Z的元素为整数.集合的等势v定义: 设A, B为两个集合, 如果存在A到B的双 射函数, 则称A和B等势, 记A≈B. 否则称A和B 不等势, 记(A≈B)或A≈B.v例: N偶=nnNn为偶数.vN奇=nnNn为奇数.vN2n=xx=2n nN.v则N≈ N偶, N≈ N奇, N≈N2nv例: N≈Z.v解: 取f: NZ, 且nN, v v或, 取g: ZN, 对nZv 例: N≈Q. 因为每个有理数都可以写成一个分数形式如下：可以从0/1开始按照箭头指定次序排列Q中元素 所以N≈Q 。

另外 Z×Z≈N 如右图所示0/11/12/13/1-1/1-2/1-3/1-1/2-2/2-3/20/21/22/23/20/31/32/33/3-1/3-2/3-3/3-1/4-2/4-3/40/41/42/43/4...............011223-1 -1-2-2-3v例: (0, 1)≈R.v解: x(0, 1), f(x)=tgπ .v例: [0, 1]≈(0, 1)定理. (康托尔定理) (1) (N≈R) (2) 对任意的集合A, (A≈P(A)).§3 有限集合与无限集合v定义: 集合A是有限集合, 当且仅当存在nN, 使nA. 否则, 称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)  ABv(2) 对有限集合A, 规定与A等势的自然数n为A的基 数. 记作: card(A)=n.v(3) 对自然数集合N, 规定vcard(N)=0v(4) 对于实数集合R, 规定vcard(R)=1v(5) 将0, 1, 2, … , 0, 1都称作基数. 其中自然数0, 1, 2, … 称为有限基数, 0, 1称为无限基数.v例: A={a, b, c}, B={{a}, {b}, {c}}.vN偶={n | nN∧n为偶数}, vN奇={n | nN∧n为奇数}可数集合v定义1: 对集合K, 如果card K0, 则称K是可 数集合.v定义2: 如果集合K是有限的或与N等势, 则称 K是可数集合.v定理. 集合A是无限可数集合A可写成如下 的式{a1, a2, …, an, …}. v定理 (1) 可数集合的任何子集是可数集.v证: 设A可数, BA, 则BA,即 v card B  card A  0.v(2) 两个可数集的并集和笛卡尔积是可数集.v证: A={a11, a12, …, a1n, …}, vB={a21, a22, …, a2n, …}, vA∪B={a11, a12, a21, a13, a22,…}v(3) 若K是无限集合, 则P(K)是不可数的.v已知的基数按从小到大的次序排列就是v0, 1, …, n, …, 0, 1 (=20), 21, … 连续统假设:不存在基数k, 使得0