集合论与函数

拉丁文（functio），含义为the action of performance。函数最重要的性质是决定性：同一输入只对应同一输出。

函数的现代定义（19世纪末，Dirichlet）：在集合论基础上，将函数视为关系的特例，特别之处就是决定性。设F为二元关系，F为函数是指

$(\forall x,y,z)(xFy\wedge xFz\to y=z)$

F为函数等价于

$x \in dom(F)\to \exists y!, \ F(x)=y$

空关系也是函数。

设F，G为函数，则

$F=G \leftrightarrow [Dom(F)=Dom(G)\wedge (\forall x \in Dom(F))(F(x)=G(x))]$

定义域、值域、陪域
设A，B为集合，F为从A到B的函数（记为$F:A\to B$），且$Dom(F)=A$，$Ran(F)\subseteq B$。则称A为函数F的定义域，$Ran(F)$为函数F的值域，B为函数F的陪域（codomain）。
函数的集合
记$B^A$为A到B的所有函数的集合，即$\{F|F:A\to B\}$，读作”B上A“。
满射、单射与双射
满射（onto）：值域等于陪域，$Ran(F)=B$

单射（1-1）：$(\forall x,y \in A)(f(x)=f(y)\to x=y)$

双射：(1-1 correspondence）：满射且单射。

函数的复合
设F和G是函数，则$F\circ G$也是函数，且满足
$(1) \ Dom(F \circ G)=\{x|x \in Dom(G) \wedge G(x)\in Dom(F)\}\\ (2)\ \forall x \in Dom(F\circ G),有F\circ G(X)=F(G(x))\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \$
复合函数的性质

函数的逆关系不一定是函数，可能只是普通的二元关系。

对于单射函数$f:A\to B$，逆关系$f^{-1}$是函数，是$Ran(f)\to A$的双射函数，但不一定是$B\to A$的双射函数；

对于满射函数$f:A\to B$，逆关系$f^{-1}$不是函数；

对于双射函数$f:A\to B$，逆关系$f^{-1}$是$B\to A$的双射函数。

对于$f$是$A\to B$的双射函数的情况，我们称逆关系$f^{-1}$是$f$的反函数。

参考

主要整理自吴楠老师《离散数学》课堂讲授