资源描述：
《第七讲：集合的势》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、离散数学DiscreteMathematics第七讲：集合的势南京大学计算机科学与技术系2012年3月12日前情提要函数的定义与外延原则像与完全原像几种特殊的函数类型满射、单射、双射特征函数与自然映射函数的复合反函数前情提要2本讲主要内容自然数与无穷公理有穷集与无穷集集合的势集合的等势关系Cantor定理集合的优势关系本讲主要内容3有穷vs.无穷有穷vs.无穷4自然数与无穷集合Godmadetheintegers;allelseistheworkofman.——LeopoldKronecker自然
2、数与无穷集合5从集合构造自然数+设?为集合，?的后继(succeed)?指?∪{?}，?令0=∅,1=0+,2=0++,⋯,?=0+⋯+，这是vonNeumann的定义设?为集合，称?为归纳集(inductiveset)指：∅∈?∧∀?∈??+∈?自然数与无穷集合6归纳集是否存在？+++⋯+若存在归纳集?，则∅∈?,∅∈?,∅∈?，从而?是无穷集Russell说：“事实上，在这个世界中是否有无穷集合，我们还不能确定。”据此，还不能确定归纳集是否存在。大多数人认为宇宙是无穷的（Hilbert则否）为了保证归纳集的存
3、在，引入无穷公理自然数与无穷集合7无穷公理无穷公理（AxiomofInfinity，无穷性原则）：∃?∅∈?∧∀?∈??+∈?以往按照vonNeumann的定义，0=∅，?+1=?+，从而可以定义出单个的自然数，但不能说明全体自然数集合ℕ的存在性，而由无穷公理可以定义ℕℕ=∩{?
4、?为归纳集}自然数与无穷集合8自然数的Peano公理化体系自然数的Peano公理化体系（自然数五公设）：⑴?∈ℕ+⑵?∈ℕ→?∈ℕ++⑶?=?→?=?+⑷?≠?+⑸?∈?∧∀?∈??∈?→(∀?∈ℕ)(?∈?)由此可由集合构造
5、出Peano算术(PA)：(ℕ,?,+)自然数与无穷集合9有关自然数的若干命题对于自然数的vonNeumann定义，可定义：?≤?=?⊆?，于是有以下命题成立：⑴?+?=?,?,?,⋯,?⑵?∈?+?⑶?≤?⑷?≤?≤?→?≤?；?≤?≤?→?=?⑸?≤?∨?≤?自然数与无穷集合10自然数的定义方式总言之，有两种方法定义自然数：I.归纳定义：∅为自然数，若?为自然数，则?+亦然；II.集合定义：?为自然数指?∈ℕ自然数与无穷集合11集合的等势关系对无穷集合的研究起源于“计数”的概念，究竟如何度量无穷集合
6、的大小呢？定义（等势）：设?，?为集合，?等势(equipotence,equipollence或equinumerosity)于?指有?−?,?????:??，记为?≈?（或?~?）有穷集与无穷集12有穷集与无穷集定义（有穷集,无穷集,可列集）：?为集合，⑴若有自然数?使得?≈?，则称?为有穷集，且记?的势（或称基数，cardinal）为?=?⑵若?非有穷集则称?为无穷集⑶若?≈ℕ，则称?为可列集（或可数集），且记?的势为?=ℵ?(读作alephnull)⑷若?≈ℝ，则记?=ℵ有穷集与无穷集13关于无穷集的
7、讨论：无穷集证明：自然数集ℕ是无穷集反设ℕ有穷，从而存在?以及双射函数?:?→ℕ，令?=??+??+⋯+??−?+?，从而有∀?∈?,??≠?，故?非满射，矛盾，故ℕ为无穷集.□有穷集与无穷集14关于无穷集的讨论：可列集上述定义中，可列集的直观概念可以看作集合的元素可以按确定的顺序线性排列，所谓“确定的”顺序是指对序列中任一元素，可以说出它“前一个”、“后一个”元素是什么例如：整数集与自然数集等势，故ℤ为可列集0，-1，1，-2，2，-3，3，-4，⋯有穷集与无穷集15关于无穷集的讨论：可列集（续）证明：构造如下?
8、:ℤ→ℕ，易见?为双射.有穷集与无穷集16关于无穷集的讨论：可列集（续）自然数集的笛卡尔积是可列集：所有的整数对构成的集合与自然数集等势有穷集与无穷集17关于无穷集的讨论：等势与集合相等等势的涵义是两个集合元素的个数“一样多”Galileo佯谬（1638）：整体一定大于部分吗？(2)2222(2)⑴令ℕ={0,1,2,3,⋯}，易见ℕ⊂ℕ；令?:ℕ→ℕ(2)如下：??=??，易见?是双射，故ℕ≈ℕ(2)∗12345∗⑵令ℕ={0,1,2,3,4,5,⋯}，易见ℕ≈ℕ有穷集与无穷集18关于无穷集的讨论：等势与集合相
9、等（续）Hilbert佯谬：?,?,?,⋯≈?,?,?,⋯有穷集与无穷集19与自然数有关的若干命题⑴自然数?的任何真子集为有穷集⑵任何自然数不等势于其真子集⑶若集合?有穷，则?不与其任何真子集等势⑷若集合?与其某个真子集等势，则?无穷其中⑵即为“鸽笼原理”，证明超出课程范围有穷集与无穷集20
