定义12.3.1
集合A是有限集合,
当且仅当存在n∈N,
使n≈A。
集合A是无限集合当且仅当A不是有限集合,
即不存在n∈N使n≈A。
每个自然数n都是比n小的n个自然数的集合,
而且是有限集合。 如果能证明每个有限集合A只与唯一的自然数n等势,
就可以用这个自然数n来表示A的基数。
定理12.3.1
不存在与自己的真子集等势的自然数。
证明
只要证明如下的命题:设n为一个自然数, 且f
示单射的,则f
一定是满射的,即ran( f
)=n。用数学归纳法证明之。设
。
(1) 在( )中只有 ,而 为双射的,所以 。
(2) 设 ,下面证明 。
设 ,且f为单射的,设 , 显然是单射的。
①n在f
的作用下是封闭的,即 ,于是由归纳假设 可知,ran( )=n,由f
的单射性可知,必有f(n)=n,因而
,故 。
②n在f
的作用下不封闭,即存在 ,使得f(m)=n,而 ,令 ,且

则n在 作用下是封闭的,且 是单射的,由①可知,ran( )= ,可是
,所以,
。
由以上的讨论可知S =
N。
这个定理就是鸽巢原理。
定理说明, 对n∈N,
m∈N且┐n≈m。直观上说,把m个鸽子放入n个巢中,若n<m,则至少一个巢中有多于一个鸽子。
推论12.3.2
任何与自己真子集等势的集合是无限集合。N和R都是无限集合。
证明 反证法。若不然,必存在有穷集合A和A的真子集B,使得A≈B,因而存在 且f是双射的。由于 ,因而存在
。
另一方面,由于A是有穷集合,因而存在自然数n,使得A≈n,于是又存在 且是双射的。并且 ,而且 也是双射的。取 ,且dom(h)=n,并且h是单射的。可是,由于 ,所以 ,从而 ,但是 ,于是 ,即h是n与n的真子集间的双射函数,这就导致了自然数n与自己的真子集等势,这矛盾于定理12.3.1。
推论12.3.3
任何有限集合只与唯一的自然数等势。
证明
设A为一个有限集合,若存在自然数n,m,使得A≈n且A≈m,由定理12.2.2可知n≈m。由N上的三歧性可知,对此n和m,m∈n,m=n,n∈m三式成立且仅成立一式。若m∈n,蕴含 ,这说明n与自己的真子集m等势,这矛盾于定理12.3.1。类似地,也不可能有n∈m成立,因此只有m=n。
|