8.1 自然数及数学归纳法

• 0：0是自然数，并且0等于空集 ，即0＝

• 后继集合：对于任意集合 ，其后继集合 定义为
  任何一个集合即是其后继集合的子集也是其后继集合的元素

• 自然数集合：自然数集合 N 归纳定义如下：

  1. 基础语句：。
  2. 归纳语句：若 ，则 。
  3. 极限语句：若 且满足 前两条，即 ，并且若 ，则 ，就有 。
     根据定义，自然数集合有元素 、、、 等。

• 自然数集合数字表示：将 记为 ， 记为 等，所以还可以用数字（集合的基数）来代表集合
  
  显然：对于每个 ，
  
  其中
  
  
  
  
  
  以此类推

• 后继函数：后继函数 定义为\sigma (n) = n^+ =n \cup {n}，或\sigma＝{<n, n + >|n\in N}
  显然函数: N → N满足：

  1. ，因为任何集合的后继都不是空集。
  2. 若 ，则 ，所以， 是单射

• peano自然数公理

  1. 0 是自然数，即 。
  2. 若 ，则有n 的唯一后继数 。
  3. 0 不是任何自然数的后继数。
  4. 若自然数 和 的后继数相等，即 ，则 。
  5. 若 且满足
     • 若 ，则 ，
       就有

• 小于关系<：定义自然数集合 上的小于关系 如下： 当且仅当
  对于任意 ， 。 是 上的严格偏序， 的自反闭包 是 上的良序，即

  1. （反自反）对于每个 ， 。
  2. （传递）对任意 ， 若 且 ，则 。
  3. 良基性：不存在自然数的无穷递降链 其中 。
  4. 三岐性：对于任意 ， 三者之中恰有一个成立。

• 第一数学归纳法：第一个成立 + 只要k成立，k+1就成立
  

• 第二数学归纳法：比我小的成立，我就成立
  
  

• 第二归纳法比第一归纳法更强
  

8.2 基数

• 集合的大小称为集合的基数，也称为集合的势

• 等势：两个集合A和B是等势的，当且仅当A和B的元素之间是一一对应的(即存在一个双射函数 , 记为 ，或
  证明A和N等势
  法1：找双射的函数
  法2：把A中元素排成不重复、无遗漏的无穷序列

• 等势的集合就被认为是一样大的

• 无穷集：集合 是无穷集当且仅当 与它的某些真子集等势。如 ，其中 是非负偶数集。

• 有穷集：集合 A 是有穷集当且仅当 A 与它的任何真子集都不等势。

• 等势关系是等价关系

• 鸽巢原理

  • 多于 n 只鸽子飞进 n 个鸽巢中，必有多于一只鸽子在同一鸽巢中。
  • 若 #A = m， #B = n，m > n ，则不存在从 A 到 B的单射

• 有穷集、无穷集：与某个自然数等势的集合称为有穷集，否则称为无穷集。

• 任何有穷集只与一个自然数等势。

• 若任何有穷集合 A 与唯一的一个自然数 n 等势，则称 A 的基数为 n ，记为 #A = n 。

集合的基数

集合之间的等势关系是等价关系。
可以有两种办法定义集合的基数。一种办法是将集合的基数定义为它所在的等价类。另一种办法是从每个等价类中取出一个代表集合作为与其等势集合的基数。自然数就是这样的代表集合。对于无穷集，不再明确指出这样的代表集合。
如 A = {3,4,5}, B为有3个苹果的集合，C = 3
A、B、C的等价类的基数就是代表集合C

……