蒟蒻博主缓考了离散，于是开始芝士总结与复习，进度（4/5）
自然数归纳法与基数
自然数
自然数构造
自然数依托于用集合论构造，各种性质用Peano公理推导，所以构造出的自然数需要满足Peano公理
集合的后继：$对于集合A，其后继集合定义为A^+ = A \cup \{A\}(所以每个集合的后继是唯一的) $
- 所以我们知道后继集合的几点性质：
- $A \subseteq A^+(A的元素在A^+里)；A \in A^+ (A本身也在A^+里) $
- $A^+ \neq \phi $
- 例：
- $\phi^+ = \{\phi \} $
- $\{\phi\}^+ = \{\phi, \{ \phi \} \} $
- 所以我们知道后继集合的几点性质：
所以由上述性质：冯·诺依曼(Von Neumann)给出了他构造自然数系统< N,+,·>的方案
- 我们可以采用集合论中学到的归纳定义法来定义自然数：
- $0 \in N (基础项) $
- $若 n \in N , 则 n^+ \in N (归纳项) $
- $只有有限次应用1与2得到的元素才是自然数 $
- 我们可以采用集合论中学到的归纳定义法来定义自然数：
引理：$若n \in N, 则\cup n^+ = n $
Peano公理及运算性质
- 我们前面说构造的自然数需要满足Peano公理，Peano公理的内容如下：
- P1: $0 \in N $(归纳基础项)
- P2: $若n \in N, 则n^+ \in N $(归纳项)
- P3: $若n \in N, 则 n^+ \neq 0 $(没有以0为后继的项，0是初始项)
- P4: $若n,m \in N \wedge n^+ = m^+, 则n = m $(后继的唯一性,可由上述引理得到)
- P5: $满足P1与P2的极小化 $
由Peano公理以及后继的性质我们可以知道作为集合的自然数的几点性质：
- 传递性: $若n_1 \in n_2, n_2 \in n_3, 则 n_1 \in n_3 $
- 三岐性: $对于任意两个n_1, n_2 \in N, 满足(n_1 \in n_2) \vee (n_1 = n_2) \vee (n_2 \in n_1) $
- 良基性: $不存在一个自然数的无穷递降序列n_{1\sim}，使得n_{i+1} \in n_i $
所以我们由Peano公理的三大性质可以知道，我们可以定义出自然数元素之间的关系，以及自然数的运算，我们称之为大/小于，加法，乘法。
- 小于: $若m,n \in N 且 m \in n, 则我们称m小于n，记作m<n $(很明显，小于关系是一个逆序关系)
- 由此我们也可以类推出小于等于关系，它是一个（全）偏序关系，由于良基性，它也会是一个良序关系。
- 加法: $m+0 = 0; m + n^+ = (m + n)^+ $
- 乘法: $m \cdot 0 = 0; m \cdot n^+ = m \cdot n + m $ (自己拿两个数加一加乘一乘就能理会其中的归纳意味)
数学归纳法
- 上文中Peano公理的极小化有几种表述的方法，详细见集合论一章的描述，其中有一种极小化方法如下：
- $若S \subseteq N 满足0 \in S且n \in S \rightarrow n^+ \in S(1/2条)，则S = N $
- 这个极小化方法是数学归纳法的基础，下面是数学归纳法的叙述（第一归纳法）
- $设P(n)是自然数论域上的性质(或谓词)，若能证明1与2，则对所有n\in N,P(n)为真 $
- $P(0)为真 $
- $对任何n \in N, P(n) \Rightarrow P(n^+) $
- 可表述为：$P(0) \wedge (\forall n)(P(n) \rightarrow P(n+1)) \Rightarrow \forall n P(n) $
- 基础项也可从非0数k开始：
- $P(k) \wedge (\forall n)(n \geq k \wedge P(n) \rightarrow P(n+1)) \Rightarrow \forall n(n \geq k \rightarrow P(n)) $
- $设P(n)是自然数论域上的性质(或谓词)，若能证明1与2，则对所有n\in N,P(n)为真 $
- 我们可以从第一归纳法推出第二归纳法：
- $\forall n(\forall k(k<n \rightarrow P(k)) \rightarrow P(n)) \Rightarrow \forall nP(n) $
- 上述归纳不需要单独列出P(0)条件，因为任取到n=0时，条件等价于P(0)
…证明过程
- 二维归纳原理：暂略
基数
集合大小的度量与比较
- 比较两个集合的大小有两个方法：
- 计数法：数出元素的个数，谁大谁多。
- 愚人比宝：每次各取其一，看谁先取完。
- 对于一个无限集，计数法失效，但我们怎么用第二个方法？可以在该集合与某个自然数之间建立一个双射。
- 等势：若在两个集合之间存在一个双射，则称集合对等（或等势），记作 $A \sim B $
- 我们易知等势关系具有自反对称传递性，是等价关系
- 集合是有穷集 当且仅当 它与一个自然数等势，且唯一（由三岐性反证法证明），这个自然数被称为有穷集合的基数，记作 $\sharp A $
- 而若集合是无穷极，就不能与一个自然数等势
- 定义了有穷集合的基数，我们就可以定义出对应关系与基数大小了
- $显然，A \sim B \Rightarrow \sharp A = \sharp B $
- $若存在A到B的单射，则也就是A等势的自然数与B的自然数之间存在单射，所以\sharp A \leq \sharp B $
- $若\sharp A \leq \sharp B且\sharp A \neq \sharp B，则记为\sharp A < \sharp B $
- 由自然数的三岐性可知，任何两个基数之间可以比较大小
- 基数相等是等价关系，小于等于是偏序关系
- 小技巧：我们可以通过tan函数建立任何一个连续的开区间与实数R的双射等势关系
- 正是如此，我们发现无穷集合可以与它本身的真子集等势（这是无穷集合的一固有性质）
抽屉原理
- 由上述表述，我们可发现无穷集合与有限集合的一点根本差别：
- 任何与自身真子集等势的集合都是无穷集合
- 所以任何有限集都不能与自身的真子集对等
- 上述对于有限集的叙述叫做抽屉原理（鸽笼原理），通俗的说：
- 你有n+1本书，但是只有个抽屉，你就建立不了一个n+1与n的双射，一定会有一个抽屉放了不止一本书。
- 形式抽象化的表示为：
- $把s(s\geq 1)个元素分成t组，必有一个组至少有\lceil s/t \rceil 个元素(\lceil \rceil 为向上取整的记号) $
无穷集
- 上文中提到了有穷集合的基数的概念，我们拓展它，让它不再局限在元素个数这一个概念，对于无限集，我们也定义它的基数，只是规定特殊的记号。
- $我们令\sharp N = \aleph_0 $
- 对于上文中关于有穷集合基数的大小的性质，都可以推广到基数上
- 基数的定义：$F是集合组，\sim 是F上的等势关系，关系\sim在F上的等价类称为基数 $
- $对于A \in F 我们本应将基数记为[A]_\sim ，但我们沿用上面的记号以达到统一概念的目的，记为\sharp A$
- 可数无穷集合：与自然数等势的集合我们称为可数无穷集合，基数为 $\aleph _0 $
- 可数集合 = 有穷集合 + 无穷可数集合，其余均是不可数集合
- 定理：无穷集的三个等价条件
- A是无穷集
- A有可数无穷的子集（证明：可以从出去已选元素的A中选择元素，因为A是无穷的，所以取之不尽，这样就构造出了一个可数无穷的子集）
- A有真子集与它等势
- 上文中我们提到了单射可以确定两个集合基数的大小，满射也同样可以
- $存在A到B的满射 \iff \sharp B \leq \sharp A $
- 证明：
- 还有几个有趣的问题：
- $N\times N \sim N $
- $N \sim Q $
- $N \sim Z $
…
- 实数集合不可数(证明：在(0,1)上构造一个无穷序列，然后利用规则，找出一个数不属于这个序列，推出矛盾，实数集合不可数)，下面我们讨论它的基数
- 引理：对于每个集合A，皆有 $\sharp A < \sharp \rho(A) $
- $首先，我们可以定义g(a) = \{a\}使得A\rightarrow \rho(A),显然g是单射，所以\sharp A \leq \sharp \rho(A) $
- $然后通过反证法来证明\sharp A \neq \sharp \rho (A) $
- 因为不可数，所以 $\sharp N \neq \sharp R $，我们定义 $\sharp R = \aleph $
- 我们可以证明：$\sharp \rho(N) = \sharp R $
- 证明非常的精彩，利用集合的特征函数，与实数的二进制编码
- 任意给定一个实数，写出实数的二进制编码，对于编码上的每一位，为1则表示在对应的集合中
- 这样我们就得到了一个实数到一个自然数集合的双射
- 所以 $\sharp R = \sharp \rho(N) > \sharp N $，即 $\aleph > \aleph_0 $
- 引理：对于每个集合A，皆有 $\sharp A < \sharp \rho(A) $
- 有意思的问题：
- $\sharp (R \times R) = \aleph $ (思路：找一个特定的值域为R的二元连续函数)
待完善。。。
