蒟蒻博主缓考了离散，于是开始芝士总结与复习，进度（3/5）
函数
基本概念
- 函数是一种特殊的关系，这种关系满足单值性，即从X到Y，元素x不能劈叉
- $即二元关系f满足：若< x, y_1> \in f 且 < x, y_2> \in f 则y_1 = y_2 $
- 这样的f我们称为X到Y的部分函数
- x叫源像点，y是像点，可记为$y=f(x) $
- 函数的定义域与值域的定义完全照搬关系的
- $若x \in dom(f), 则称f在x处有定义，记为：“f(x) \downarrow” $
- $无定义记为：“f(x) \uparrow” $
- 注意我们上述说的都是部分函数。
- 我们把$dom(f) = X $的函数称为全函数，简称函数
- $dom(f) \subset X的函数称为严格部分函数 $
- $ran(f) = Y $ ，称f为X到Y上的部分函数。
- $ran(f) \subset Y $ ，称f为X到Y内的部分函数。
- 1-1部分函数：$当f(x_1)=f(x_2)时，都有x_1=x_2 $
- 函数的限制：
- $若A \subseteq X，则f\cap(A\times X)是从A到Y的函数，称为f在A上的限制，记作f|_A$
- $又称f为f|_A到X上的延拓 $
- 部分函数f的像与源像（f是X到Y的部分函数，$A \subseteq X 且 B \subseteq Y $）：
- $f[A] = \{f(x)|x \in A \wedge f(x)\downarrow \} $
- $f^{-1}[B] = \{x \in X | f(x) \in B \wedge f(x)\downarrow \} $
- $ dom( f ) = f ^ { -1 } [Y] ; ran(f) = f[ X ] $
- 实际上这里的f和我们上文中的f:X->Y已经发生了变化，变成了集合到集合的关系，但不影响理解。
- 常用定理（不太重要，但可以看看，熟悉函数的性质）：
- $A_1 \subseteq A_2 \subseteq X，则f[A_1] \subseteq f[A_2] \subseteq ran(f) (f^{-1}同理)$
- 缩放定理：
- $A \subseteq dom(f)，则A \subseteq f^{-1}[f[A] ] $
- $B \subseteq ran(f)，则B = f[f^{-1}[B]] $
- (有点不对称，原因是 $\sharp dom > \sharp ran $)
- $若A \subseteq \rho (X), B \subseteq \rho (Y) $
- $f[\cup A] = \cup \{f[\alpha] | \alpha \in A \} $
- $f[\cap A] \subseteq \cap \{f[\alpha] | \alpha \in A \}(A \neq \phi) $
- $f^{-1}[\cup B] = \cup \{f^{-1}[\beta] | \beta \in B \} $
- $f^{-1}[\cap B] = \cap \{f^{-1}[\beta] | \beta \in B \}(B \neq \phi) $(与第2条不对称)
- 限制定理：
- $dom(f|_A) = A \cap domf $
- $ran(f|_A) = f[A] $
- $若A \subseteq domf，则f|_A是A的全函数 $
- 全函数集合：
- $Y^X = \{f | f: X \rightarrow Y\} $
- $每个X中的元素都可以任意选择一个Y中的元素，所以\sharp(Y^X) = (\sharp Y)^{(\sharp X)} $
函数的复合
- 函数是一种特殊的关系，所以函数的复合与关系的复合是一样的，我们定义$f \cdot g $为X到Z的关系
- 但是由于我们常用f(x)的方式来表示函数，所以我们把$f \cdot g $的复合关系表示为复合函数的话，写法为$g(f(x)) = (g \cdot f)(x) $
- 定义域与值域讨论：f是X到Y的部分函数，g是Y到z的部分函数
- $dom(g \cdot f) = f^-1[dom g] (ran类似)$（关系怎么证这就怎么证）
- $f与g都是全函数，则g \cdot f也是全函数 $（由上得）
- 结合律照样满足（关系一样）
- $若f:X\rightarrow X, 则我们可以定义f的n次幂，f^n$(关系可以由矩阵表示，联系方阵与矩阵的n次幂定义)
函数的性质
- 三大性质：（注意前提是全函数）
- 满射：$f是满射 \iff \forall y(y \in Y \rightarrow \exists x(x \in X \wedge y = f(x) ) ) $
- 单射：$f是单射 \iff \forall x_1 \forall x_2(x_1 \in X \wedge x_2 \in X \wedge f(x_1) = f(x_2) \rightarrow x_1 = x_2) $
- 满射 + 单射 = 双射
- $若f和g都是满/单/双射时，g\cdot f也是满/单/双射 $（按定义证）
- 左满右单定理：
- $若g\cdot f是满射，则g是满射 $
- $若g\cdot f是单射，则f是单射 $（反证法）
- $若g\cdot f是双射，则\dots $
- 可以意象化的理解
逆函数
还是那句话，函数是一种特殊的关系，所以函数的复合和关系的复合内容基本一致，但是函数有他的特殊性，就是单值性。所以我们如果沿用关系的逆的定义，会很麻烦，因为这样一个函数反过来不一定满足单值性，所以我们这里函数的逆明显不同于关系的逆，而更加的相像与矩阵的逆，而且复合是矩阵乘，所以在接触函数的逆的时候我们可以时刻联系矩阵运算
我们定义了左逆右逆： $若f:X \rightarrow Y $
- $若有g:Y \rightarrow X，使得g \cdot f = I_x，则f左可逆，g为f的左逆 $（右逆同理）
- 若有g同时为左逆和右逆，则f可逆，g为f的逆
- 左逆右逆不一定存在，也不一定唯一
- 左右可逆的条件：
- $左可逆 \iff 单射 $
- $右可逆 \iff 满射 $
- $可逆 \iff 双射 $
- 可以用左满右单定理证出一边，用单射满射的性质构造出g来证另一边
- 而我有一种新的理解，上文说到，我们可以时刻联系矩阵运算，满射的话X范围会比Y大，单射的话Y的范围会比X要大，对应的正是行数大于列数及列数大于行数的长条形矩阵（或说行满秩与列满秩），我们也可以构造出左边的逆与右边的逆（这里的逆矩阵也是长条形，当然只是类似），注意函数的左右是反过来的，所以矩阵的左乘和右乘的最后要在名称上称为右逆和左逆。（我这里不再细说，感兴趣欢迎来讨论）
- $若f可逆，则f的逆唯一，且f的逆关系f^{-1}即为f的逆函数 $
- 唯一性证明：$g_1 = g_1 \cdot I_Y = g_1 \cdot (f \cdot g_2) = I_X \cdot g_2 = g_2 $
- 关于 $f^{-1} $是f的逆函数：证明不难，但是我们注意到，$f^{-1} $的矩阵表示为f的矩阵的转置，而不是矩阵的逆，这里主要是由于关系复合的乘法与真正的矩阵乘是有差别的，但是我们可以类比单位阵的意味，这里的矩阵可逆是正交的。
- 可逆与复合的交换：$f可逆，g可逆，则g \cdot f可逆，且(g \cdot f )^{-1} = f^{-1} \cdot g^{-1} $
- 证：$(g \cdot f) \cdot (f^{-1} \cdot g^{-1}) = I_X(左乘同理) $
集合的特征函数
- 特征函数全集映射到{0,1}上，原理很简单，但是可以简化很多逻辑表达式的计算问题，但是要真正派上大用场得等到下一节-基数。
- 定义：设U是全集，A是U的子集
- $定义A的特征函数\Psi_A:U\rightarrow \{0,1\} $
- 性质：
- $\forall x(\Psi_A(x) = 0) \iff A = \phi $
- $A = U \iff \dots $
- $\forall x(\Psi_A(x) \leq \Psi_B) \iff A \subseteq B $
- $A = B \iff \dots $
- $\Psi_{A \cap B} = \Psi_A \cdot \Psi_B $
- $\Psi_{A \cup B} = \Psi_A + \Psi_B - \Psi_{A \cap B} $
- $\Psi_{\sim A} = 1 - \Psi_A $
- $\Psi_{A - B} = \Psi_{A \cap \sim B} = \dots $
- 证明俩逻辑表达式相等可以转化为证明特征函数相等
