计算机科学与技术专业集合论与图论 第四讲自然数集与集合的势周 晓 聪中山大学计算机科学系软件工程实验室2008年10月http:/www.cs.sysu.edu.cn/zxc isszxcmail.sysu.edu.cn周 晓 聪 (中山大学计算机科学系)离散数学基础集合论与图论2008年10月1 / 9内容提要1自然数集2集合的势周 晓 聪 (中山大学计算机科学系)离散数学基础集合论与图论2008年10月2 / 9自然数集 自然数集后继与归纳集 给定集合A，称A A为A的后继，记为A+； 若集合A满足，A，且对任意集合S，SA蕴含S+A，则称A为归纳集自然数与自然数集 属于任意归纳集的集合称为自然数0= 1=0+= 0 2=1+= 0,0 = 0,1 n= 0,1,2, ,n1 所有自然数构成的集合称为自然数集(N)自然数集是最小的归纳集自然数与自然数集的基本性质 对任意自然数m,n，若mn，则m n 对任意自然数m,n，m+n+当且仅当mn 三岐性：m,nN，mn,m = n,nm恰有一个成立 自然数集有数学归纳法成立周 晓 聪 (中山大学计算机科学系)离散数学基础集合论与图论2008年10月3 / 9自然数集 自然数性质证明对任意自然数m,n，若mn则m n思路：使用数学归纳法证明：对任意自然数n满足：对任意自然 数m，mn蕴含mn当n=0时，即n= ，命题平凡成立（不存在属于n的m） 设n=k时，考虑n=k+1，即n=k+=k k 这时对任意的自然数m，若mk+，即mk k，从而有两种情况mk，即m=k，那么m=kk+ mk，根据归纳假设mk，而kk+，因此mk+周 晓 聪 (中山大学计算机科学系)离散数学基础集合论与图论2008年10月4 / 9自然数集 自然数性质证明对任意自然数m,n，若mn则m n思路：使用数学归纳法证明：对任意自然数n满足：对任意自然 数m，mn蕴含mn当n=0时，即n= ，命题平凡成立（不存在属于n的m） 设n=k时，考虑n=k+1，即n=k+=k k 这时对任意的自然数m，若mk+，即mk k，从而有两种情况mk，即m=k，那么m=kk+ mk，根据归纳假设mk，而kk+，因此mk+周 晓 聪 (中山大学计算机科学系)离散数学基础集合论与图论2008年10月4 / 9自然数集 自然数性质证明对任意自然数m,n，若mn则m n思路：使用数学归纳法证明：对任意自然数n满足：对任意自然 数m，mn蕴含mn当n=0时，即n= ，命题平凡成立（不存在属于n的m） 设n=k时，考虑n=k+1，即n=k+=k k 这时对任意的自然数m，若mk+，即mk k，从而有两种情况mk，即m=k，那么m=kk+ mk，根据归纳假设mk，而kk+，因此mk+周 晓 聪 (中山大学计算机科学系)离散数学基础集合论与图论2008年10月4 / 9自然数集 自然数性质证明对任意自然数m,n，若mn则m n思路：使用数学归纳法证明：对任意自然数n满足：对任意自然 数m，mn蕴含mn当n=0时，即n= ，命题平凡成立（不存在属于n的m） 设n=k时，考虑n=k+1，即n=k+=k k 这时对任意的自然数m，若mk+，即mk k，从而有两种情况mk，即m=k，那么m=kk+ mk，根据归纳假设mk，而kk+，因此mk+周 晓 聪 (中山大学计算机科学系)离散数学基础集合论与图论2008年10月4 / 9自然数集 自然数性质证明对任意自然数m,n，若mn则m n思路：使用数学归纳法证明：对任意自然数n满足：对任意自然 数m，mn蕴含mn当n=0时，即n= ，命题平凡成立（不存在属于n的m） 设n=k时，考虑n=k+1，即n=k+=k k 这时对任意的自然数m，若mk+，即mk k，从而有两种情况mk，即m=k，那么m=kk+ mk，根据归纳假设mk，而kk+，因此mk+周 晓 聪 (中山大学计算机科学系)离散数学基础集合论与图论2008年10月4 / 9自然数集 自然数性质证明对任意自然数m,n，若mn则m n思路：使用数学归纳法证明：对任意自然数n满足：对任意自然 数m，mn蕴含mn当n=0时，即n= ，命题平凡成立（不存在属于n的m） 设n=k时，考虑n=k+1，即n=k+=k k 这时对任意的自然数m，若mk+，即mk k，从而有两种情况mk，即m=k，那么m=kk+ mk，根据归纳假设mk，而kk+，因此mk+周 晓 聪 (中山大学计算机科学系)离散数学基础集合论与图论2008年10月4 / 9自然数集 自然数性质证明对任意自然数m,n，若mn则m n思路：使用数学归纳法证明：对任意自然数n满足：对任意自然 数m，mn蕴含mn当n=0时，即n= ，命题平凡成立（不存在属于n的m） 设n=k时，考虑n=k+1，即n=k+=k k 这时对任意的自然数m，若mk+，即mk k，从而有两种情况mk，即m=k，那么m=kk+ mk，根据归纳假设mk，而kk+，因此mk+周 晓 聪 (中山大学计算机科学系)离散数学基础集合论与图论2008年10月4 / 9集合的势 集合等势若集合A与集合B之间存在双射，则称集合A与B等势，记为AB 所有奇数构成的集合与自然数集等势 Z,NN,Q都与N等势 自然数集与实数集不等势（康托尔对角线法） 对任意集合A，A不与A的幂集(A)等势 集合等势是（所有集合构成的类上的）等价关系有穷集（有限集）与无穷集 与某个自然数等势的集合称为有穷集 不与任何自然数等势的集合称为无穷集 不存在与自己的真子集等势的自然数因此有穷集都不与自己的真子集等势 任意有穷集只与惟一的自然数等势 有穷集的子集仍然是有穷集 任何与自己的真子集等势的集合是无穷集 自然数集N是无穷集周 晓 聪 (中山大学计算机科学系)离散数学基础集合论与图论2008年10月5 / 9集合的势 与集合等势有关的证明证明集合A不与(A)等势思路：反证法，设A与(A)等势，即存在双函数f:A(A)f的特点是，对任意的aA，有f(a)(A)，即f(a) A 于是对A中的元素可问a是否属于f(a)，由此定义 B = aA | a 6 f(a)(A)证明B在f下没有原像，从而与f是双函数矛盾! 即要证明不存在aA使得f(a) = B 仍然用反证法：若存在a0使得f(a0) = B 则可问这样的问题：a0B？ 这个问题让人陷入矛盾的境地（有如罗素悖论!）若a0B，则根据B的定义，a06f(a0) =B若a06B，即a06f(a0)，从而根据B的定义，a0B周 晓 聪 (中山大学计算机科学系)离散数学基础集合论与图论2008年10月6 / 9集合的势 与集合等势有关的证明证明集合A不与(A)等势思路：反证法，设A与(A)等势，即存在双函数f:A(A)f的特点是，对任意的aA，有f(a)(A)，即f(a) A 于是对A中的元素可问a是否属于f(a)，由此定义 B = aA | a 6 f(a)(A)证明B在f下没有原像，从而与f是双函数矛盾! 即要证明不存在aA使得f(a) = B 仍然用反证法：若存在a0使得f(a0) = B 则可问这样的问题：a0B？ 这个问题让人陷入矛盾的境地（有如罗素悖论!）若a0B，则根据B的定义，a06f(a0) =B若a06B，即a06f(a0)，从而根据B的定义，a0B周 晓 聪 (中山大学计算机科学系)离散数学基础集合论与图论2008年10月6 / 9集合的势 与集合等势有关的证明证明集合A不与(A)等势思路：反证法，设A与(A)等势，即存在双函数f:A(A)f的特点是，对任意的aA，有f(a)(A)，即f(a) A 于是对A中的元素可问a是否属于f(a)，由此定义 B = aA | a 6 f(a)(A)证明B在f下没有原像，从而与f是双函数矛盾! 即要证明不存在aA使得f(a) = B 仍然用反证法：若存在a0使得f(a0) = B 则可问这样的问题：a0B？ 这个问题让人陷入矛盾的境地（有如罗素悖论!）若a0B，则根据B的定义，a06f(a0) =B若a06B，即a06f(a0)，从而根据B的定义，a0B周 晓 聪 (中山大学计算机科学系)离散数学基础集合论与图论2008年10月6 / 9集合的势 与集合等势有关的证明证明集合A不与(A)等势思路：反证法，设A与(A)等势，即存在双函数f:A(A)f的特点是，对任意的aA，有f(a)(A)，即f(a) A 于是对A中的元素可问a是否属于f(a)，由此定义 B = aA | a 6 f(a)(A)证明B在f下没有原像，从而与f是双函数矛盾! 即要证明不存在aA使得f(a) = B 仍然用反证法：若存在a0使得f(a0) = B 则可问这样的问题：a0B？ 这个问题让人陷入矛盾的境地（有如罗素悖论!）若a0B，则根据B的定义，a06f(a0) =B若a06B，即a06f(a0)，从而根据B的定义，a0B周 晓 聪 (中山大学计算机科学系)离散数学基础集合论与图论2008年10月6 / 9集合的势 与集合等势有关的证明证明集合A不与(A)等势思路：反证法，设A与(A)等势，即存在双函数f:A(A)f的特点是，对任意的aA，有f(a)(A)，即f(a) A 于是对A中的元素可问a是否属于f(a)，由此定义 B = aA | a 6 f(a)(A)证明B在f下没有原像，从而与f是双函数矛盾! 即要证明不存在aA使得f(a) = B 仍然用反证法：若存在a0使得f(a0) = B 则可问这样的问题：a0B？ 这个问题让人陷入矛盾的境地（有如罗素悖论!）若a0B，则根据B的定义，a06f(a0) =B若a06B，即a06f(a0)，从而根据B的定义，a0B周 晓 聪 (中山大学计算机科学系)离散数学基础集合论与图论2008年10月6 / 9集合的势 与集合等势有关的证明证明集合A不与(A)等势思路：反证法，设A与(A)等势，即存在双函数f:A(A)f的特点是，对任意的aA，有f(a)(A)，即f(a) A 于是对A中的元素可问a是否属于f(a)，由此定义 B = aA | a 6 f(a)(A)证明B在f下没有原像，从而与f是双函数矛盾! 即要证明不存在aA使得f(a) = B 仍然用反证法：若存在a0使得f(a0) = B 则可问这样的问题：a0B？ 这个问题让人陷入矛盾的境地（有如罗素悖论!）若a0B，则根据B的定义，a06f(a0) =B若a06B，即a06f(a0)，从而根据B的定义，a0B周 晓 聪 (中山大学计算机科学系)离散数学基础集合论与图论2008年10月6 / 9集合的势 与集合等势有关的证明证明集合A不与(A)等势思路：反证法，设A与(A)等势，即存在双函数f:A(A)f的特点是，对任意的aA，有f(a)(A)，即f(a) A 于是对A中的元素可问a是否属于f(a)，由此定义 B = aA | a 6 f(a)(A)证明B在f下没有原