0. 预备知识

集合与映射

集合 联系性质与对象 $S=\lbrace x|p(x)\rbrace ,\ s \in S$

有限集中元素个数称为集合的长度；集合的势

交 并 差 补 直积($X \times Y := \lbrace(x,\ y)|x \in X,\ y \in Y\rbrace$)

映射 集合之间的关系 $f:X \rightarrow Y;\quad f:x \mapsto y$

定义域($Domain$)$D_f$ 到达域($Codomain$)$C_f$ 值域($Range$)$R_f = \lbrace y|y=f(x),\ \forall x\in D_f\rbrace \subset C_f$

存在恒等映射 $\mathrm{id}_X:X \rightarrow X,\ \forall x \in X,\ \mathrm{id}_X(x)=x$

映射的复合($f \circ g$):

$f\in \lbrace f|f:B \rightarrow C \rbrace ,\ g\in \lbrace f|f:A \rightarrow B \rbrace,\ \exists! f \circ g \in \lbrace f|f:A \rightarrow C \rbrace,\ s.t.\ \forall x \in A ,\ f(g(x))=(f \circ g)(x)$

映射的结合律:

$(f \circ g)(x)=f(g(x))$

$(f \circ g) \circ h = f \circ (g \circ h) \equiv f \circ g \circ h$

单射($\forall y \in R_f ,\ \exists! x \in D_f ,\ s.t. \ f(x)=y\ ; \quad$$f(x)=f(y)\Rightarrow x=y$) 满射($C_f=R_f$) 双射(既单又满)

单：若$f \circ h = f \circ g \Rightarrow g = h$(左可约)，称$f$为单射

满：$f:A\rightarrow B,\$ $\forall g,\ h\in \lbrace f|f:B\rightarrow C \rbrace ,\ g \circ f = h \circ f \Rightarrow g = h$(右可约)称$f$为满射

映射的逆:

$f:X\rightarrow Y$，$\mathrm{id}_X,\ \mathrm{id}_Y$分别是集合$X,\ Y$上的恒等映射，那么如果存在一个映射$g:Y\rightarrow X$，使$g \circ f = \mathrm{id}_X,\$$f \circ g = \mathrm{id}_Y$，称$g$为$f$的逆映射，记作$f^{-1}$

另有观点：$f^{-1}:P(C_f)\rightarrow P(D_f)$，其中$P(X)$表示$X$的幂集

集合的同构：存在可逆映射；双射与映射可逆互为充分必要条件

函数是定义域与到达域都是数集的映射