OS-做一个简单的shell

蒟蒻博主缓考了离散，于是开始芝士总结与复习，进度（4/5）

自然数归纳法与基数

自然数

自然数构造

• 自然数依托于用集合论构造，各种性质用Peano公理推导，所以构造出的自然数需要满足Peano公理

• 集合的后继：$对于集合A，其后继集合定义为A^{+}=A\cup \{A\}(所以每个集合的后继是唯一的)$

  • 所以我们知道后继集合的几点性质：
    • $A\subseteq A^{+}(A的元素在A^{+}里)；A\in A^{+}(A本身也在A^{+}里)$
    • $A^{+}\ne \varphi$
  • 例：
    • ${\varphi }^{+}=\{\varphi \}$
    • $\{\varphi {\}}^{+}=\{\varphi ,\{\varphi \}\}$

• 所以由上述性质：冯·诺依曼(Von Neumann)给出了他构造自然数系统< N,+,·>的方案

  • $$\begin{array}{rl}& 0=\varphi \\ & 1=0^{+}={\varphi }^{+}=\{0\}\\ & 2=1^{+}=\{\varphi {\}}^{+}=\{0,1\}\\ & 3=2^{+}=2\cup \{2\}=\{0,1,2\}\\ & ...\\ & n+1=n^{+}=\{0,1,2,...,n\}\end{array}$$
  • 我们可以采用集合论中学到的归纳定义法来定义自然数：
    • $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^{+}\ne 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\to n^{+}\in S(1/2条)，则S=N$
• 这个极小化方法是数学归纳法的基础，下面是数学归纳法的叙述（第一归纳法）
  • $设P(n)是自然数论域上的性质(或谓词)，若能证明1与2，则对所有n\in N,P(n)为真$
    1. $P(0)为真$
    2. $对任何n\in N,P(n)\Rightarrow P(n^{+})$
  • 可表述为：$P(0)\wedge (\mathrm{\forall }n)(P(n)\to P(n+1))\Rightarrow \mathrm{\forall }nP(n)$
  • 基础项也可从非0数k开始：
    • $P(k)\wedge (\mathrm{\forall }n)(n\ge k\wedge P(n)\to P(n+1))\Rightarrow \mathrm{\forall }n(n\ge k\to P(n))$
• 我们可以从第一归纳法推出第二归纳法：
  • $\mathrm{\forall }n(\mathrm{\forall }k(k<n\to P(k))\to P(n))\Rightarrow \mathrm{\forall }nP(n)$
  • 上述归纳不需要单独列出P(0)条件，因为任取到n=0时，条件等价于P(0)

    …证明过程

• 二维归纳原理：暂略

基数

集合大小的度量与比较

• 比较两个集合的大小有两个方法：
  • 计数法：数出元素的个数，谁大谁多。
  • 愚人比宝：每次各取其一，看谁先取完。
  • 对于一个无限集，计数法失效，但我们怎么用第二个方法？可以在该集合与某个自然数之间建立一个双射。
• 等势：若在两个集合之间存在一个双射，则称集合对等（或等势），记作 $A\sim B$
  • 我们易知等势关系具有自反对称传递性，是等价关系
• 集合是有穷集 当且仅当 它与一个自然数等势，且唯一（由三岐性反证法证明），这个自然数被称为有穷集合的基数，记作 $\mathrm{♯}A$
  • 而若集合是无穷极，就不能与一个自然数等势
• 定义了有穷集合的基数，我们就可以定义出对应关系与基数大小了
  • $显然，A\sim B\Rightarrow \mathrm{♯}A=\mathrm{♯}B$
  • $若存在A到B的单射，则也就是A等势的自然数与B的自然数之间存在单射，所以\mathrm{♯}A\le \mathrm{♯}B$
  • $若\mathrm{♯}A\le \mathrm{♯}B且\mathrm{♯}A\ne \mathrm{♯}B，则记为\mathrm{♯}A<\mathrm{♯}B$
  • 由自然数的三岐性可知，任何两个基数之间可以比较大小
  • 基数相等是等价关系，小于等于是偏序关系
• 小技巧：我们可以通过tan函数建立任何一个连续的开区间与实数R的双射等势关系
  • 正是如此，我们发现无穷集合可以与它本身的真子集等势（这是无穷集合的一固有性质）

抽屉原理

• 由上述表述，我们可发现无穷集合与有限集合的一点根本差别：
  • 任何与自身真子集等势的集合都是无穷集合
  • 所以任何有限集都不能与自身的真子集对等
• 上述对于有限集的叙述叫做抽屉原理（鸽笼原理），通俗的说：
  • 你有n+1本书，但是只有个抽屉，你就建立不了一个n+1与n的双射，一定会有一个抽屉放了不止一本书。
  • 形式抽象化的表示为：
    • $把s(s\ge 1)个元素分成t组，必有一个组至少有\lceil s/t\rceil 个元素(\lceil \rceil 为向上取整的记号)$

无穷集

• 上文中提到了有穷集合的基数的概念，我们拓展它，让它不再局限在元素个数这一个概念，对于无限集，我们也定义它的基数，只是规定特殊的记号。
  • $我们令\mathrm{♯}N={\mathrm{\aleph }}_0$
  • 对于上文中关于有穷集合基数的大小的性质，都可以推广到基数上
• 基数的定义：$F是集合组，\sim 是F上的等势关系，关系\sim 在F上的等价类称为基数$
  • $对于A\in F我们本应将基数记为[A{]}_{\sim }，但我们沿用上面的记号以达到统一概念的目的，记为\mathrm{♯}A$
• 可数无穷集合：与自然数等势的集合我们称为可数无穷集合，基数为 ${\mathrm{\aleph }}_0$
  • 可数集合 = 有穷集合 + 无穷可数集合，其余均是不可数集合
• 定理：无穷集的三个等价条件
  • A是无穷集
  • A有可数无穷的子集（证明：可以从出去已选元素的A中选择元素，因为A是无穷的，所以取之不尽，这样就构造出了一个可数无穷的子集）
  • A有真子集与它等势
• 上文中我们提到了单射可以确定两个集合基数的大小，满射也同样可以
  • $存在A到B的满射⟺\mathrm{♯}B\le \mathrm{♯}A$
  • 证明：
  • $$\begin{array}{r}\Rightarrow \\ & 若从A\to B有满射f，则f右可逆\\ & 存在g:B\to A，使得f\cdot g=I_B\\ & I_B是双射，所以g是单射\\ & \therefore \mathrm{♯}B\le \mathrm{♯}A\\ \Leftarrow \\ & 若\mathrm{♯}B\le \mathrm{♯}A,则有单射g:B\to A\\ & g左可逆，存在f:A\to B使得f\cdot g=I_B\\ & I_B是双射,所以f是满射\end{array}$$
• 还有几个有趣的问题：
  • $N\times N\sim N$
  • $N\sim Q$
  • $N\sim Z$

    …

• 实数集合不可数(证明：在(0,1)上构造一个无穷序列，然后利用规则，找出一个数不属于这个序列，推出矛盾，实数集合不可数)，下面我们讨论它的基数
  • 引理：对于每个集合A，皆有 $\mathrm{♯}A<\mathrm{♯}\rho (A)$
    • $首先，我们可以定义g(a)=\{a\}使得A\to \rho (A),显然g是单射，所以\mathrm{♯}A\le \mathrm{♯}\rho (A)$
    • $然后通过反证法来证明\mathrm{♯}A\ne \mathrm{♯}\rho (A)$
  • 因为不可数，所以 $\mathrm{♯}N\ne \mathrm{♯}R$，我们定义 $\mathrm{♯}R=\mathrm{\aleph }$
  • 我们可以证明：$\mathrm{♯}\rho (N)=\mathrm{♯}R$
    • 证明非常的精彩，利用集合的特征函数，与实数的二进制编码
    • 任意给定一个实数，写出实数的二进制编码，对于编码上的每一位，为1则表示在对应的集合中
    • 这样我们就得到了一个实数到一个自然数集合的双射
  • 所以 $\mathrm{♯}R=\mathrm{♯}\rho (N)>\mathrm{♯}N$，即 $\mathrm{\aleph }>{\mathrm{\aleph }}_0$
• 有意思的问题：
  • $\mathrm{♯}(R\times R)=\mathrm{\aleph }$ (思路：找一个特定的值域为R的二元连续函数)

待完善。。。