首先讨论映射,书中使用的是函数(function),我在这里为了和其他书本相一致,采取映射这个术语.首先需要了解前面遗漏的两个符号或者术语:关系$R$的定义域和值域.
\[\text{dom}{R}=\{x: \exists y (xRy)\};\quad \text{ran}{R}=\{y: \exists x(xRy)\}.\]
集合$X$到$Y$的映射是一种特殊的关系$f$:$\text{dom}{f}=X$,对每一个$x \in X$,存在唯一的$y \in Y$,使$(x,y) \in f$,此时,满足$(x,y) \in f$的$y$记作$f(x)$.$X$到$Y$的所有映射组成的集合是$P(X \times Y)$的子集,记为$Y^X$.
书中讨论了一些术语相关的知识,这里不叙述了.有时$\{(a,b)|(a,b) \in f\}$,称为$f$的图像(graph).
如果$\text{ran}{f}=Y$,则称$f$是映上(onto)的($X$映到$Y$上的).
设$A \subset X$,记号$f(A)$的含义如下:
\[f(A)=\{y : y=f(x), \exists x \in A\},\]
这里存在一个问题,我们考虑的集合中,可能出现$A \in X$这个情形,此时$f(A)$的含义具有歧义.这个问题以前从没想过,因为以前很少遇到,或者说几乎不会遇到.
函数的限制与延拓.
设$f$是$Y$到$Z$的函数,$X \subset Y$,对于如下方式构造的$X$到$Z$的函数$g$:
\[g(x)=f(x),x \in X,\]
称$g$为$f$在$X$上的限制,$f$为$g$在$Y$上的延拓.记$g=f|X$,$\text{ran}{(f|X)}=f(X)$.
下面是几个映射的例子:
(1)$X \times Y$到$X$的映射:$f(x,y)=x$;$X \times Y$到$Y$的映射:$f(x,y)=y$.
(2)$R$是$X$上的等价关系,$X$到$X/R$的映射:$f(x)=x/R$,称为canonical map.
对于映射$f$,可以定义$X$上的等价关系如下:
\[x/R=\{y:f(y)=f(x)\},\]
也就是说$aRb\Leftrightarrow f(a)=f(b)$.令$y \in Y$,$g(y)=\{x \in X:f(x)=y\}$,此时,$g(y)=x/R$.
(3)$A \subset X$,$A$的特征函数:$\chi(x)=1$,$x \in A$,$\chi(x)=0$,$x \notin A$,对于$A \subset X$,或者$A \in P(X)$,则$A \to \chi_A$也是一个一一映射.
习题:(i)$Y^{\emptyset}$恰好有一个元素,$\emptyset$,无论$Y$是否为空集;(ii)如果$X$不是$\emptyset$,则$\emptyset^X$为空.
这里涉及到了空集,证明方法通常是反证.
$Y^{\emptyset}$表示的是所有$\emptyset$到$Y$的映射,需要证明$\emptyset$是映射,而映射又是特殊的关系$R$,需要证明$\emptyset$是关系,或者说$\emptyset$是有序对的集合,反证,如果$\emptyset$不是关系,那么应该存在元素$\alpha$不是有序对,而这是不可能的.接下来,$\emptyset$是一个映射,也就是对每一个$x \in \emptyset$,存在唯一的$y \in Y$,使$x\emptyset{}y$,这是成立的,也就是如果$\emptyset$不是一个映射,也就是存在$x \in \emptyset$,或者不存在$y \in Y$,使得$x \emptyset y$,或者有两个以上的$y_1$,$y_2$,使得$x \emptyset y_1$,$x \emptyset y_2$,这都不可能.对于任何其他映射或者关系,都要求有元素$x \in \emptyset$,这是不可能的,因此,$\emptyset$是$Y^{\emptyset}$的唯一元素.
假设存在$f \in \emptyset^X$,则对于$x \in X$,$\exists y \in \emptyset$使$f(x)=y$,这是不可能的.
簇:从指标集$I$到$X$的映射.把并集和交集运算推广到集合簇,
\[\begin{gather*}
\bigcup_{i \in I}{A_i} \text{或} \bigcup_{i}{A_i}\\
\bigcap_{i \in I}{A_i} \text{或} \bigcap_{i}{A_i}
\end{gather*}\]
$\{I_j\}$是$J$上的集合簇,$K=\bigcup_{j}{I_j}$,$\{A_k\}$为$K$上的集合簇,结合律就是
\[\bigcup_{k \in K}{A_k} = \bigcup_{j \in J}{(\bigcup_{i \in I_j}{A_i})}.\]
交换律的推广:
\[(\bigcup_{i \in I}{A_i}) \cup (\bigcup_{j \in J}{A_j}) = (\bigcup_{j \in J}{A_j}) \cup (\bigcup_{i \in I}{A_i}).\]
设$\{A_i\}$是$X$的子集簇,$B \subset X$,则
\[\begin{gather*}
B \cap \bigcup_{i}{A_i} = \bigcup_{i}{(B \cap A_i)} \\
B \cup \bigcap_{i}{A_i} = \bigcap_{i}{(B \cup A_i)}
\end{gather*}\]
这是分配律.
如果$\{A_i\}$和$\{B_j\}$均为集合簇,则
\[\begin{gather*}
(\bigcup_{i}{A_i}) \cap (\bigcup_{j}{B_j}) = \bigcup_{ij}{(A_i \cap B_j)} \\
(\bigcap_{i}{A_i}) \cup (\bigcap_{j}{B_j}) = \bigcap_{ij}{(A_i \cup B_j)}
\end{gather*}\]
这里$\bigcup_{ij}$是指$\bigcup_{(i,j) \in I \times J}$.
设$x \in (\bigcup_{i}{A_i}) \cap (\bigcup_{j}{B_j})$$\Leftrightarrow$$x \in \bigcup_{i}{A_i}$且$x \in \bigcup_{j}{B_j}$,$\exists i_0$,$j_0$,$x \in A_{i_0}$,$x \in B_{j_0}$$\Leftrightarrow$$x \in A_{i_0} \cap B_{j_0}$$\Leftrightarrow$$x \in \bigcup_{ij}{(A_i \cap B_j)}$.
另一等式的证明方法类似.
笛卡尔积的推广,笛卡尔积是集合
\[X \times Y = \{(x,y)|x \in X, y \in Y\},\]
考虑集合$\{a,b\}$,$a \neq b$;$Z$为$\{a,b\}$上的集合簇
\[Z = \{\{z_a,z_b\}|z_a \in X, z_b \in Y\},\]
于是$Z$到$X \times Y$有一个映射:$f(z)=(z_a,z_b)$.推广到一般情形,
\[\times_{i \in I}{X_i} = \{\{x_i\}_{i \in I}|x_i \in X_i\},\]
若$X_i=X$,则记号$\times_i{X_i}$变为$X^I$.
设$\{X_i\}_{i \in I}$为集合簇,$X = \times_i{X_i}$,$J \subset I$,此时存在一个自然的映射,所谓的投影映射.$X \to \times_{i \in J}{X_i}$.
$x \in X$,$f(x)=y \in \times_{i \in J}{X_i}$,其中$y_i=x_i$,$i \in J$.
习题:证明$(\bigcup_{i}{A_i}) \times (\bigcup_{j}{B_j}) = \bigcup_{ij}{(A_i \times B_j)}$,对交也是成立的,另外,$\bigcap_{i}{X_i} \subset X_j \subset \bigcup_{i}{X_i}$,有这个结论,可以把交集和并集定义为包含关系的极大极小值.
(1)设$(a,b) \in (\bigcup_{i}{A_i}) \times (\bigcup_{j}{B_j})$$\Leftrightarrow$$a \in \bigcup_{i}{A_i}$,$b \in \bigcup_{j}{B_j}$$\Leftrightarrow$$a \in A_{i_0}$,$b \in B_{j_0}$$\Leftrightarrow$$(a,b)\in A_{i_0} \times B_{j_0}$$\Leftrightarrow$$(a,b)\in \bigcup_{ij}{(A_i \times B_j)}$.
(2)$\forall x \in \bigcap_{i}{X_i}$$\Rightarrow$$x \in X_j$$\Rightarrow$$\bigcap_{i}{X_i}\subset X_j$;$\forall x \in X_j$$\Rightarrow$$x \in \bigcup_{i}{X_i}$$\Rightarrow$$X_j \subset \bigcup_{i}{X_i}$.
设$X_j \subset Y$,对任意$j$成立,则$\bigcup_{i}{X_i} \subset Y$成立;这意味着$\bigcup_{i}{X_i}$是满足对所有的$j$,$X_j \subset Y$的$Y$中的最小的.
若对每一个$j$,$Y \subset X_j$,则$Y \subset \bigcap_{i}{X_i}$,这意味着$\bigcap_{i}{X_i}$是满足对所有的$j$,$Y \subset X_j$中的最大的集合.