函数

定义

  • XX到YY的函数f(f：X→Y)f(f：X→Y)是XX到YY的二元关系，且具有下列性质：

    • dom(f)=Xdom(f)=X
    • ∀x∈X，y1,y2∈Y，(x,y1)∈f∧(x,y2)∈f→y1=y2∀x∈X，y_1,y_2∈Y，(x,y_1)∈f ∧ (x,y_2)∈f → y_1=y_2成立。(即对于任意的x∈Xx\in X，有且仅有唯一的后件与其对应)。
    • 将xx的唯一后件记为f(x)f(x)，则f(x)f(x)为xx的像，xx为f(x)f(x)的原像。

  • 满射(到上的/映上的)：ran(f)=Yran(f) = Y，

  • 单射(一对一的 )：∀x1,x2∈X,x1≠x2\forall x_1,x_2\in X,x_1\not = x_2，有f(x1)≠f(x2)f(x_1)\not = f(x_2)

  • 双射(一一对应的)：既是到上的又是一对一的，同时满足前两条性质

  • 3种函数的关系图和关系矩阵的特性

    • 考察Y中的元素
      • 一对一：∀y∈Y∀y∈Y，至多有一个指向它的箭头
      • 映上： ∀y∈Y∀y∈Y，至少有一个指向它的箭头
      • 一一对应： ∀y∈Y∀y∈Y，有且仅一个指向它的箭头
    • 考察矩阵的列
      • 一对一：每列至多有一个1
      • 映上： 每列至少有一个1
      • 一一对应：每列有且仅一个1

  • 函数作为关系可以进行关系运算，结果关系不一定是函数

  • 函数的复合是函数

  • f：X→Y，g：Y→Zf：X→Y，g：Y→Z

    • f和g到上 ⇒ f∘gf∘g到上
    • f和g一对一 ⇒ f∘gf∘g一对一
    • f和g一一对应 ⇒ f∘gf∘g一一对应

  • 函数的逆不一定是函数，只有当函数一一对应的时候，函数的逆才是函数(反函数)。

    • f−1f^{-1}是YY到XX的函数 当且仅当 ff是一一对应
    • ff是一一对应 ⇒ f−1f^{-1}也是一一对应
    • ff是一一对应 ⇒ f∘f−1=IXf∘f^{-1}=I_X，f−1∘f=IYf^{-1}∘f=I_Y

集合的基数

定义

  • 互相等势的集合归于一类，赋予每一类一个记号，即该类集合的基数(势)，记为∣A∣|A|。基数是广义的“计数”。
  • 有限集的基数用它的计数表示，自然数集的基数记为aa(或ℵ0ℵ_0)，实数集的基数记为cc(或ℵ1ℵ_1)
  • 可数无限集的基数都是aa，即ℵ0\aleph_0
  • 2a=c2^a = c，2ℵ0=ℵ12^{\aleph_0} = \aleph_1

集合等势

  • 集合AA与BB等势(A BA~B)：存在AA到BB的一一对应
  • 有限集合等势与所含元素个数相同的概念相符
  • 有限集不可能与无限集等势

等势的性质

  • 自反性：对任意集合AA，A∼AA \sim A
  • 对称性：对任意两个集合AA和BB，A∼B⇒B∼AA\sim B ⇒ B\sim A
  • 传递性：对任意三个集合AA、BB和CC，A∼B∧B∼C⇒A∼CA\sim B \wedge B\sim C ⇒ A\sim C

可数集

  • 可数集：集合，有限集或与N\mathbb N等势
  • 集合A可数 ⇔\Leftrightarrow 存在A的元素的序列含A的所有元素，且无重复元素
  • 可数个可数集的并是可数集
  • 不可数的集合存在，如开区间(0,1)(0,1)不是可数集

基数的比较

  • ∣A∣≤∣B∣|A|≤|B|：∃B1⊆B∃B_1⊆B，使A∼B1A\sim B_1

  • ∣A∣<∣B∣|A|<|B|：∣A∣≤∣B∣|A|≤|B|且∣A∣≠∣B∣|A|≠|B|

  • 任意无限集都含可数的无限子集

  • 可数无限集是“最小”的无限集，aa是最小的无限基数

  • 对于任意集合AA，∣A∣<∣P(A)∣|A|< |P(A)|，P(A)P(A)的基数表示为∣P(A)∣|P(A)|

  • 集合AA和BB，∣A∣≤∣B∣|A|≤|B|且∣B∣≤∣A∣|B|≤|A| ⇒∣A∣=∣B∣⇒ |A|=|B|

  • 可数集的子集必定也是可数集

  • 任意无限集都有与其等势的真子集

不可解问题的存在性

  • 不可解的问题：不存在求解它的C程序
  • C程序的集合可数，而问题的集合不可数，问题集的基数大于C程序集的基数，问题多于程序

停机问题

  • 停机问题是有实际意义的、经典的不可解问题

  • 停机问题：

    • 输入：一个程序和这个程序要处理的一个输入
    • 输出：若该程序在该输入下能终止，则输出Yes，否则输出No

  • 采用反证法，假定存在解决停机问题的C函数，然后以它为基础构造另一个C函数，最后引出矛盾

  • 假定如下的halt函数解决停机问题，它有两个输入：prog是一个C函数的源代码字符串，input是表示输入的字符串，如果函数prog在给定的输入input下能终止，则halt返回1，否则返回0。int Halt(char *prog, char *input);

  • 构造函数contrary

1
2
3
4
5
void contrary(char *prog)
{
    if (halt(prog，prog))
        while (1);
}
  • 将contrary源程序作为输入调用contrary，考察其执行过程：
    • 其中对halt的调用返回1
      • 关于Halt的假定说明：contrary在对自身运行时将会停机
      • contrary的源代码说明：contrary将进入无限循环，从而不会停机
    • 其中对halt的调用返回0
      • 关于halt的假定说明：contrary在对自身运行时将不会停机
      • contrary的源代码说明：contrary不会进入无限循环，从而将停机
  • 两种情况都引发矛盾。