资源描述：
《计算机科学与技术专业·集合论与图论》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、计算机科学与技术专业·集合论与图论第四讲自然数集与集合的势周晓聪中山大学计算机科学系软件工程实验室2008年10月http://www.cs.sysu.edu.cn/∼zxcisszxc@mail.sysu.edu.cn周晓聪(中山大学计算机科学系)离散数学基础·集合论与图论2008年10月1/9内容提要1自然数集2集合的势周晓聪(中山大学计算机科学系)离散数学基础·集合论与图论2008年10月2/9自然数集自然数集后继与归纳集+−给定集合A，称A∪{A}为A的后继，记为A；+−若集合A满足，∅∈A，且对任意集合
2、S，S∈A蕴含S∈A，则称A为归纳集自然数与自然数集−属于任意归纳集的集合称为自然数◦0=∅◦1=0+={0}◦2=1+={0,{0}}={0,1}◦n={0,1,2,···,n−1}−所有自然数构成的集合称为自然数集(N)◦自然数集是最小的归纳集自然数与自然数集的基本性质−对任意自然数m,n，若m∈n，则m⊂n++−对任意自然数m,n，m∈n当且仅当m∈n−三岐性：∀m,n∈N，m∈n,m=n,n∈m恰有一个成立−自然数集有数学归纳法成立周晓聪(中山大学计算机科学系)离散数学基础·集合论与图论2008年10月3
3、/9自然数集自然数性质证明对任意自然数m,n，若m∈n则m⊂n思路：使用数学归纳法证明：对任意自然数n满足：对任意自然数m，m∈n蕴含m⊂n当n=0时，即n=∅，命题平凡成立（不存在属于n的m）设n=k时，考虑n=k+1，即n=k+=k∪{k}+−这时对任意的自然数m，若m∈k，即m∈k∪{k}，从而有两种情况◦m∈{k}，即m=k，那么m=k∈k+◦m∈k，根据归纳假设m⊂k，而k⊂k+，因此m⊂k+周晓聪(中山大学计算机科学系)离散数学基础·集合论与图论2008年10月4/9自然数集自然数性质证明对任意自然数
4、m,n，若m∈n则m⊂n思路：使用数学归纳法证明：对任意自然数n满足：对任意自然数m，m∈n蕴含m⊂n当n=0时，即n=∅，命题平凡成立（不存在属于n的m）设n=k时，考虑n=k+1，即n=k+=k∪{k}+−这时对任意的自然数m，若m∈k，即m∈k∪{k}，从而有两种情况◦m∈{k}，即m=k，那么m=k∈k+◦m∈k，根据归纳假设m⊂k，而k⊂k+，因此m⊂k+周晓聪(中山大学计算机科学系)离散数学基础·集合论与图论2008年10月4/9自然数集自然数性质证明对任意自然数m,n，若m∈n则m⊂n思路：使用数学
5、归纳法证明：对任意自然数n满足：对任意自然数m，m∈n蕴含m⊂n当n=0时，即n=∅，命题平凡成立（不存在属于n的m）设n=k时，考虑n=k+1，即n=k+=k∪{k}+−这时对任意的自然数m，若m∈k，即m∈k∪{k}，从而有两种情况◦m∈{k}，即m=k，那么m=k∈k+◦m∈k，根据归纳假设m⊂k，而k⊂k+，因此m⊂k+周晓聪(中山大学计算机科学系)离散数学基础·集合论与图论2008年10月4/9自然数集自然数性质证明对任意自然数m,n，若m∈n则m⊂n思路：使用数学归纳法证明：对任意自然数n满足：对任意
6、自然数m，m∈n蕴含m⊂n当n=0时，即n=∅，命题平凡成立（不存在属于n的m）设n=k时，考虑n=k+1，即n=k+=k∪{k}+−这时对任意的自然数m，若m∈k，即m∈k∪{k}，从而有两种情况◦m∈{k}，即m=k，那么m=k∈k+◦m∈k，根据归纳假设m⊂k，而k⊂k+，因此m⊂k+周晓聪(中山大学计算机科学系)离散数学基础·集合论与图论2008年10月4/9自然数集自然数性质证明对任意自然数m,n，若m∈n则m⊂n思路：使用数学归纳法证明：对任意自然数n满足：对任意自然数m，m∈n蕴含m⊂n当n=0时，
7、即n=∅，命题平凡成立（不存在属于n的m）设n=k时，考虑n=k+1，即n=k+=k∪{k}+−这时对任意的自然数m，若m∈k，即m∈k∪{k}，从而有两种情况◦m∈{k}，即m=k，那么m=k∈k+◦m∈k，根据归纳假设m⊂k，而k⊂k+，因此m⊂k+周晓聪(中山大学计算机科学系)离散数学基础·集合论与图论2008年10月4/9自然数集自然数性质证明对任意自然数m,n，若m∈n则m⊂n思路：使用数学归纳法证明：对任意自然数n满足：对任意自然数m，m∈n蕴含m⊂n当n=0时，即n=∅，命题平凡成立（不存在属于n的
8、m）设n=k时，考虑n=k+1，即n=k+=k∪{k}+−这时对任意的自然数m，若m∈k，即m∈k∪{k}，从而有两种情况◦m∈{k}，即m=k，那么m=k∈k+◦m∈k，根据归纳假设m⊂k，而k⊂k+，因此m⊂k+周晓聪(中山大学计算机科学系)离散数学基础·集合论与图论2008年10月4/9自然数集自然数性质证明对任意自然数m,n，若m∈n则m⊂n思路：使用数学归纳法证
