南京大学：《离散数学 Discrete Mathmatics》课程教学资源（课件讲稿，2018）集合论——第7章 集合的基数

集合的基数 离散数学：第八讲

集合的基数 离散数学：第八讲

急雪扇 提要 U 。集合的大小 ·无限集合 ·等势与优势关系 集合计数 ·容斥原理

提要  集合的大小  无限集合  等势与优势关系  集合计数  容斥原理

&嘉 自然数与无穷集合 GOD God made the integers;all else is the the work of man. INTEGERS -Leopold Kronecker HAWKING

自然数与无穷集合

款雪扇 我们怎么比较集合的大小 。“数得清”的我们就数元素个数。 ●“无数”的怎么办？ ●“常识”不一定经得起追问。 。集合的大小称为集合的“势”(cardinality) ●集合S的势记为|S到

我们怎么比较集合的大小  “数得清”的我们就数元素个数。  “无数”的怎么办？  “常识”不一定经得起追问。  集合的大小称为集合的“势” (cardinality)  集合S的势记为|S|

有限与无限：“宇宙旅馆” 啊？客满啦？ 没关系，我让现 在住在k号房间 的客人移到+1 号。你就住进第 1号房间吧！ 满

急售扇 集合的等势关系 ●等势关系的定义： ●如果存在从集合A到集合B的双射，则称集合A与 B等势。 ●集合A与B等势记为：AB,否则A*B 。A≈B意味着：A,B中的元素可以“一一对应”。 要证明A≈B,找出任意一个从A到B的双射即可。 “等势”的集合就被认为是“一样大

集合的等势关系  等势关系的定义：  如果存在从集合A到集合B的双射，则称集合A与 B等势。  集合A与B等势记为：AB, 否则A≉B  AB意味着：A，B中的元素可以“一一对应” 。  要证明AB，找出任意一个从A到B的双射即可。  “等势”的集合就被认为是“一样大

自然数集是无限集 ■证明：自然数集W是无穷集 反设N有穷，从而存在n以及双射函数f:n→N,令 m=f(0)+f(1)+…+f(n-1)+1,从而有Hx∈ n,f(x)≠m,故f非满射，矛盾！故N为无穷集.口

自然数集是无限集

般线扇 可列集 ■上述定义中，可列集的直观概念可以看作集合 的元素可以按确定的顺序线性排列，所谓“确 定的”顺序是指对序列中任一元素，可以说出 它“前一个”、“后一个”元素是什么 ·例如：整数集与自然数集等势，“故Z为可列集 0，-1,1,-2,2,-3,3,-4,…

可列集

效 可列集 证明：构造如下f:Z→N,易见f为双射： 将Z中元素以下列顺序排列并与N中元素对应： Z:0-11-22-33. ↓↓↓↓↓↓ N:0123456. 则这种对应所表示的函数是： 2x ≥0 fZ→N,f(x)= -2x-1 x<0

可列集

般雪扇 有限集与无限集 102 ●S是有限集合，iff.存在自然数n,使得S与n等势 ·S不是有限集合（即：无限集），ff.存在S的真子集S',使得S 与S等势 →S一定包含一个与自然数集合等势的子集M={a1,a2,a3,…} (这实际 上意味着：自然数集是“最小的”无限集) 令S'=S-{a1},可以定义f:S→S如下： 对于任意xeM,fa)Fa+1;对于任意x∈S-M,f(xx 显然这是双射，即S与其真子集S等势 =假设S是有限集，令lS=n,则给S任意的真子集S,若S=m,必有m<n, 因此从S到S的任一单射不可能是满射

有限集与无限集  S是有限集合，iff. 存在自然数n，使得S与n等势  S不是有限集合(即：无限集)，iff. 存在S的真子集S’，使得S 与S’等势  S一定包含一个与自然数集合等势的子集M = {a1 ,a2 ,a3 ,…} (这实际 上意味着：自然数集是“最小的”无限集) 令S’=S-{a1 }，可以定义ƒ:SS’如下： 对于任意xM, ƒ(ai )= ai+1； 对于任意xS-M, ƒ(x)= x 显然这是双射，即S与其真子集S’等势  假设S是有限集，令|S|=n, 则给S任意的真子集S’ , 若|S’|=m，必有m<n, 因此从S ’到S的任一单射不可能是满射