集合的等势 基数的定义 基数的运算 基数的比较

Slides:



Advertisements
Similar presentations
2 和 5 的倍数的特征 运动热身 怎样找一个数的倍数? 从小到大写出 2 的倍数( 10 个): 写出 5 的倍数( 6 个) 2 , 4 , 6 , 8 , 10 , 12 , 14 , 16 , 18 , 20 5 , 10 , 15 , 20 , 25 , 30.
Advertisements

排列 组合 概率 会考复习. 排列、组合是不同的两个事件,区别的 标志是有无顺序,而区分有无顺序的办法是: 把问题的一个选择结果解出来,然后交换这 个结果中任意两个元素的位置,看是否会产 生新的变化,若有新变化,即说明有顺序, 是排列问题;若无新变化,即说明无顺序, 为组合问题 知识要点.
2 、 5 的倍数的特征 玉田百姓. 1 、在 2 、 3 、 5 、 8 、 10 、 12 、 25 、 40 这几个数中, 40 的因数有几个? 5 的倍数有几个? 复习: 2 、在 6 、 10 、 12 、 15 、 18 、 20 这几个数中,哪些数 是 2 的倍数?哪些数是 5 的倍数?
因数与倍数 2 、 5 、 3 的倍数的特 征 新人教版五年级数学下册 执教者:佛山市高明区明城镇明城小学 谭道芬.
练一练: 在数轴上画出表示下列各数的点, 并指出这些点相互间的关系: -6 , 6 , -3 , 3 , -1.5, 1.5.
說 劍 《莊子‧雜篇》─ 第 一 組 賴泊錞 謝孟儒 張維真 羅苡芸
复习: :对任意的x∈A,都有x∈B。 集合A与集合B间的关系 A(B) A B :存在x0∈A,但x0∈B。 A B A B.
第二节 时间和位移.
第四章 组合逻辑电路 第 四 章 组 合 逻 辑 电 路.
第五章 二次型. 第五章 二次型 知识点1---二次型及其矩阵表示 二次型的基本概念 1. 线性变换与合同矩阵 2.
不会宽容人的人, 是不配受到别人的宽容的。 贝尔奈.
复习回顾 a a×a a×a×a a a×a×a= a×a= 1.如图,边长为a厘米的正方形的面积 为 平方厘米。
数列(一) 自强不息和谐发展 授课教师:喻永明.
第四章 有限集和无限集 有限集合 元素的个数称为该集合的基数; 满足包含排斥原理。 集合元素无限多,如:自然数集合N、整数集I、实数集R等。
第八章 南极洲.
请同学们思考下列问题:.
第四章 时间序列的分析 本章教学目的:①了解从数量方面研究社会经济现象发展变化过程和发展趋势是统计分析的一种重要方法;②掌握时间数列编制的基本要求;③理解和掌握水平速度两方面指标的计算及运用④理解和掌握长期趋势分析和预测的方法。 本章教学重点:现象发展的水平指标和速度指标。 本章教学难点:现象变动的趋势分析。
一、原函数与不定积分 二、不定积分的几何意义 三、基本积分公式及积分法则 四、牛顿—莱布尼兹公式 五、小结
第四章 函数的积分学 第六节 微积分的基本公式 一、变上限定积分 二、微积分的基本公式.
第5章 定积分及其应用 基本要求 5.1 定积分的概念与性质 5.2 微积分基本公式 5.3 定积分的换元积分法与分部积分法
第1节 光的干涉 (第2课时).
第三节 格林公式及其应用(2) 一、曲线积分与路径无关的定义 二、曲线积分与路径无关的条件 三、二元函数的全微分的求积 四、小结.
第4章 种群和群落 第3节 群落的结构 自主学习案   合作探究案 课后练习案. 第4章 种群和群落 第3节 群落的结构 自主学习案   合作探究案 课后练习案.
第5章 §5.3 定积分的积分法 换元积分法 不定积分 分部积分法 换元积分法 定积分 分部积分法.
如何寫工程計畫書 臺北市童軍會考驗委員會 高級考驗營 版.
第七章 线性变换 7.1 线性映射 7.2线性变换的运算 7.3 线性变换和矩阵 7.4 不变子空间 7.5 特征值和特征向量
计算机数学基础 主讲老师: 邓辉文.
§2 求导法则 2.1 求导数的四则运算法则 下面分三部分加以证明, 并同时给出相应的推论和例题 .
走下神坛的 抽象代数 李尚志 北京航空航天大学.
计算机问题求解 – 论题 函数 2018年11月20日.
第六章 集合的基数 在前面我们的基数简单的看作集合元素的个数,这对于有限集来说没有问题,但对于无限集而言,“元素的个数”这个概念是没有意义的,那么两个集合的“大小”,“相同”的确切含义是什么呢?形式的描述元素“多少”的概念数学工具是函数。 先讨论自然数集合,有限集,无限集。
ZFC及选择公理 姜勇刚 李凯旭.
第八章 函数 主要内容 函数的定义与性质 函数定义 函数性质 函数运算 函数的逆 函数的合成 双射函数与集合的基数.
四、投影运算 在数据库中, 用关系来描述数据时常用投影运算进行数据操作。
数列.
实数与向量的积.
苏 教 版 五 年 级 数 学(上) 用字母表示数 青阳体仁小学 胡春雅.
线性代数 第二章 矩阵 §1 矩阵的定义 定义:m×n个数排成的数表 3) 零矩阵: 4) n阶方阵:An=[aij]n×n
概 率 统 计 主讲教师 叶宏 山东大学数学院.
复习.
第十章 双线性型 Bilinear Form 厦门大学数学科学学院 网址: gdjpkc.xmu.edu.cn
1.2 有理数 第1课时 有理数 伏家营中学 付宝华.
4.偏序集合中的几个特殊元素 定义:设(A,≤)是一个偏序集合, BA,若存在一个元素bB,对所有b‘B都有b’≤b, 则称b是B的最大元;若都有b≤b‘, 则称b是B的最小元。特别B=A时,称b为A的最大元或最小元。 例:A1={1,2,3,4,5,6},(A1,) 1为A1的最小元,6为A1的最大元.
离散数学-集合论 南京大学计算机科学与技术系
定理21.9(可满足性定理)设A是P(Y)的协调子集,则存在P(Y)的解释域U和项解释,使得赋值函数v(A){1}。
第16讲 相似矩阵与方阵的对角化 主要内容: 1.相似矩阵 2. 方阵的对角化.
§6.7 子空间的直和 一、直和的定义 二、直和的判定 三、多个子空间的直和.
1.2 子集、补集、全集习题课.
1.设A和B是集合,证明:A=B当且仅当A∩B=A∪B
例:循环群的每个子群一定是循环群。 证明:设H是循环群G的子群,a是G的生成元。 1.aH
4) 若A可逆,则 也可逆, 证明: 所以.
第4课时 绝对值.
上杭二中 曾庆华 上杭二中 曾庆华 上杭二中 曾庆华.
第八章 函数 主要内容 函数的定义与性质 函数定义 函数性质 函数运算 函数的逆 函数的合成 双射函数与集合的基数.
1.集合 , S1={a},S2={{a}},S3={a,{a}} aS3, S1  S3 {a}S3,S2  S3,
第15讲 特征值与特征向量的性质 主要内容:特征值与特征向量的性质.
A经有限次初等变换化为B,称A与B等价,记作A→B.
第五章 函数 函数也叫映射,交换,是数学中的一个基本概念,在高数中,函数的概念是从变量的角度提出来的,这种函数一般是连续或间断连续的函数,这里将连续函数的概念推广到离散量的讨论,即将函数看作一种特殊的二元关系。
第八章 函数 主讲:李春英 办公地点:软件大楼202
正弦、余弦函数的性质 华容一中 伍立华 2017年2月24日.
§2 方阵的特征值与特征向量.
主讲教师 欧阳丹彤 吉林大学计算机科学与技术学院
定义21.17:设P1=P(Y1)和P2=P(Y2),其个体变元与个体常元分别为X1,C1和 X2,C2,并且或者C1=或者C2。一个半同态映射(,):(P1,X1∪C1)→(P2,X2∪C2)是一对映射: P1→P2; : X1∪C1→X2∪C2,它们联合实现了映射p(x,c)→(p)((x),
第四章 函数的 积分学 第七节 定积分的换元积分法     与分部积分法 一、定积分的换元积分法 二、定积分的分部积分法.
陪集 例:三次对称群S3={e,1, 2, 3, 4, 5}的所有非平凡子群是:
集合的等势 基数的定义 基数的运算 基数的比较
集合的基数 (Cardinal Number)
数列求和 Taojizhi 2019/10/13.
离散数学─归纳与递归 南京大学计算机科学与技术系
§2 自由代数 定义19.7:设X是集合,G是一个T-代数,为X到G的函数,若对每个T-代数A和X到A的函数,都存在唯一的G到A的同态映射,使得=,则称G(更严格的说是(G,))是生成集X上的自由T-代数。X中的元素称为生成元。 A变, 变 变, 也变 对给定的 和A,是唯一的.
Presentation transcript:

集合的等势 基数的定义 基数的运算 基数的比较 第12章集合的基数 集合的等势 基数的定义 基数的运算 基数的比较

12.2 集合的等势 定义12.2.1 对集合A和B,如果存在从A到B的双射函数,就称A和B等势,记作A≈B 注意:证明等势即构造双射 􀂆等势是等价关系,可以用来分类 􀂄自反性:A≈A IA:A→A双射 􀂄对称性:若A≈B,则B≈A f:A→B双射⇒f-1:B→A双射 􀂄传递性:若A≈B且B≈C,则A≈C f:A→B, g:B→C双射⇒gof:A→C双射

集合的等势 例1 N ≈N偶,N ≈N奇 f: N→ N偶, f(n)=2n;g: N→ N奇, g(n)=2n+1 例2 Z≈N. f: Z→N, 0, n=0 f(n) = 2n, n>0 2|n|-1, n<0 例3 N≈N×N. (课本中图11.1.1) f:N×N→N, f(<i,j>)=(i+j)(i+j+1)/2 + i

例4 N≈Q 证明:因为任何有理数都可以表示成分数,即∀m ∈Z, ∀n ∈ N-{0}, m/n,从而找出全体既约分数,它们表示出了全体有理数,并编号。f:N→Q, f(n)=编号[n]的既约分数. (课本中图12.2.1)

集合的等势 例5 R≈R+. f: R→R+,f(x)=ex 例6 (0, 1)≈R f: (0,1)→R, ∀xε(0,1) f(x)=tan(x-1/2)π 例7 [0, 1]≈(0, 1) f: [0,1]→(0,1), 1/2, x=0 f(x) = 1/(n+2), x=1/n, n∈N-{0} x, 其他 注:无限集合可以和它的真子集等势,但有限集合不能

结论 无限集合可以和它的真子集等势,但有限集合不能 N ≈Z ≈Q ≈N×N (0,1) ≈[0,1] ≈R

P(A)≈A2 证明: 令f:P(A)→A2, f(B)=χB, 其中χB是B∈P(A)的特征函数, χB :A→{0,1}, χB(x)=1 ⇔ x∈B. (1) f是单射, 设B1,B2⊆A且B1≠B2, 则 f(B1)= χB1(x)≠ χB2(x)=f(B2), 故χB1 ≠ χB2. (2) f是满射. 任给χB :A→{0,1}, 令 B={x|x∈A且χB(x)=1}⊆A, 则f(B)= χB

集合的等势 定理12.2.3(Cantor康托尔定理) (1) ¬N≈R (2) 对任意的集合A, ¬ A≈P(A) 证明: (1) (反证) 假设N≈R≈[0,1], 则存在f:N→[0,1]双射, 对∀n∈N, 令f(n)=xn+1, 于是 ran(f)=[0,1]= {x1,x2,x3,…,xn,…} 将xi表示成如下小数:

¬N≈R x1=0.a11 a21 a31…… x2=0.a12 a22 a32…… x3=0.a13 a23 a33…… ┇ xn=0.a1n a2n a3n…… 其中0≤aji≤9, i,j=1,2,…

¬N≈R 选一个[0,1]中的小数 x=0.b1b2b3……使得 (1) 0≤bj≤9, i=1,2,… (2) bn ≠ ann 由x的构造可知, x∈[0,1], x∉{x1,x2,x3,…,xn,…} (x与xn在第n位上不同). 这与[0,1]={x1,x2,x3,…,xn,…}矛盾!

¬N≈R 对角化方法 x1=0.a11 a21 a31…… x2=0.a12 a22 a32…… x3=0.a13 a23 a33…… ┇ xn=0.a1n a2n a3n……ann…

(2) 对任意的集合A, ¬ A≈P(A) 证明: (反证) 假设存在双射f:A→P(A), 令 B = { x| x∈A∧x∉f(x) } 则B∈P(A). 由f是双射, 设f(b)=B, 则 b∈B⇔b∉f(b) ⇔b∉B, 矛盾!

12.3 有限集合与无限集合 自然数定义 对任意的集合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} …

有限集合与无限集合 定义12.3.1 集合A是有限集合,当且仅当存在n∈N, 使n≈A. 集合A是无限集合,当且仅当A不是有限集合,即不存在n∈N, 使n≈A. 结论 􀂄不存在与自己真子集等势的自然数(鸽巢原理) 􀂄不存在与自己真子集等势的有限集合 􀂄任何与自己真子集等势的集合是无限集合.例N, R 􀂄任何有限集合只与唯一的自然数等势

12.4 集合的基数 集合的基数就是集合中元素的个数 定义9.6.1 如果存在n∈N,使集合A与集合{x|x∈N∧x<n}={0,1,2,…,n-1}的元素个数相同,就说集合A的基数是n,记作#(A)=n或|A|=n或card(A)=n 空集Φ的基数是0 定义9.6.2 如果存在n∈N,使n是集合A的基数.就说A是有限集合.如果不存在这样的n,就说A是无限集合

集合的基数 对任意的集合A和B,它们的基数分别用 card(A)和card(B)表示,并且card(A)=card(B)⇔A≈B 对有限集合A和n∈N, 若A≈n, 则card(A)=n (有限基数) N的基数:card(N)=ℵ0 (无限基数) R的基数:card(R)=ℵ1 (无限基数)

基数的运算 对任意的基数k和l, 若存在集合K和L, card(K)=k, card(L)=l, 则 (1)若K⋂L=∅, k+l=card(K⋃L) (2)k·l=card(K×L) (3)kl=card(LK), 其中LK是从L到K的函数的集合 􀂆对集合K, L, P, M, 如果K≈P且L≈M, 则K×L≈P×M且LK ≈MP. 如果同时成立K⋂L=∅且P⋂M=∅, 则K⋃L≈P⋃M

基数的运算 例7 k0=card(∅K)=card({∅})=1 0k=card(K∅)=card(∅)=0 00=card(∅∅)=card({∅})=1 例8 对任意集合A, 有card(P(A))=2card(A)

基数的运算 例9 对任意的n∈N, 有 (1)n+ℵ0=ℵ0 (2)n·ℵ0=ℵ0 (3)ℵ0+ℵ0=ℵ0 (4)ℵ0·ℵ0=ℵ0 证明: (1)令L=N, K={a1, …, an}, 且对于i=1, 2, …, n有ai∉N. 则card(L)=ℵ0, card(K)=n, K⋂L=∅. 于是K⋃L={a1, …, an, 0, 1, 2, …}. 构造双射函数f: K⋃L→N. 则K⋃L≈N, 且 n+ℵ0 =card(K)+card(L)=card(K⋃L)=card(N)=ℵ0

基数的运算 定理12.5.1 对任意的基数k、l和m,有 (1) k+l= l+k, k·l=l·k (2) k+(l+m)=(k+l)+m, k· (l·m)=(k·l) ·m (3) k· (l+m)=k·l+k·m (4) k(l+m) =K l ·km (5) (k·l)m = km ·lm (6) (K l)m= k(l·m) 另外,对任意的基数k,有 k+0 =k, k·0=0, k·1=k, k·2=k+k 注意:对任意基数的运算的性质,与自然数的运算性质一致

基数的比较 定义12.6.1 对集合K和L,card(K)=k, card(L)=l, 如果存在从K到L的单射函数,则称集合L优势于K,记作K≤L,且称基数k不大于基数l,记作k≤l 定义12.6.2 对基数k和l,如果k≤l且k≠l,则称k小于l,记作k<l 例: 对任意的自然数n,n≤ℵ0

基数的比较 例10 对任意的基数k,有k<2k 证明:对基数k,存在集合K,使得card(K)=k. 则有card(P(K))=2k. 构造函数f: A→P(A), f(x)={x}, 则f是单射的,进而k≤2k. 又¬K≈P(K),k≠2k 因此k<2k 注意:不存在最大的基数

基数的比较 定理12.6.1 对任意的基数k,l和m,有 (1)k≤k (2)若k≤l且l≤m,则k≤m (3)若k≤l且l≤k,则k=l(Schroder-Bernstein施罗德-伯恩斯坦定理) (4)k≤l或l≤k

基数的比较 例11 R≈N2 证明:先证R≤N2. 因(0,1)≈R, 即证(0, 1)≤N2 H: (0,1)→(N→2) 单射, ∀z∈(0,1)的二进制小数, H(z):N→{0,1}, H(z)(n)=z的二进制表示的第n+1位小数. 再证N2≤R.因[0,1]≈R, 即证N2≤[0, 1] (2) G: (N→2)→[0,1] 单射, ∀f:N→2, G(f)=0.f(0)f(1)f(2) …(第n+1位小数是f(n)). 􀂆由此例可得 ℵ1=card(R)=card(N2)=card(P(A))=2ℵ0 注意:对任意集合A,有P(A)≈A2

举例 (1) z=0.101110011..时 H(z)(0)=1; H(z)(1)=0; H(z)(2)=1; H(z)(3)=1; H(z)(4)=1; … (2) 特征函数f(0)=1, f(1)=0, f(2)=1, f(3)=0,… 可以得到十进制小数f=0.1010…∈[0, 1]

基数的比较 定理12.6.2 对任意的基数k,l和m,如果k≤l,则 (1) k+m≤l+m (2) k·m≤l·m (3) km ≤lm (4) 若k≠0或m≠0,mk ≤ml 例2ℵ0=1·2ℵ0≤ℵ0·2ℵ0≤2ℵ0· 2ℵ0=2ℵ0+ℵ0=2ℵ0 所以ℵ0·2ℵ0=2ℵ0

基数的比较 结论 对基数k和l,如果k≤l、k≠0,l是无限基数,则 k+l=k·l=l=max(k, l) 对任意的无限基数k,kk =2k 对任意的无限集合K,N≤K 对任意的无限基数k,ℵ0≤k (ℵ0是最小的无限基数) 对任意的基数k,k < ℵ0当且仅当k是有限基数 有限集合的子集一定是有限的

12.7 可数集合与连续统假设 定义12.7.1 对集合K,如果card(K)≤ℵ0,则称K是可数集合 亦可描述为:如果集合K是有限的或与N等势,就称K为可数集合 例 对n∈N,n是有限可数集合 􀂄N,Z,Q是无限可数集合 􀂄R是不可数集合

可数集合 性质 􀂄可数集的任何子集是可数集 􀂄两个可数集的并集和笛卡儿积是可数集 􀂄若K是无限集合,则P(K)是不可数的 􀂄可数个可数集的并集是可数集 (或者,若A是可数集,A的元素都是可数集,则⋃A是可数集)

连续统假设 已知的基数按从小到大的次序排列为: 0,1,…,n,…,ℵ0,ℵ1,2ℵ1 ,… 连续统假设断言:不存在基数k,使得 ℵ0<k<ℵ1=2ℵ0 该假设至今未得到证明. 但是,据证,根据现有的公理系统,既不能证明它是对的,也不能证明它是错的