Chapter I Foundations

1 Fundamentals of Logic

符号逻辑研究的是能够被断定为真（True）或假（False）的命题（statement）。

任意命题$A$都有其否定$\neg A$，定义为$A$为假则$\neg A$为真，$A$为真则$\neg A$为假。

两个命题$A$和$B$，可以使用“与”（conjunction）$\land$和“或”（disjunction）$\vee$来构成新命题。命题$A \land B$为真当且仅当$A$和$B$都为真，命题$A \vee B$为假当且仅当$A$和$B$都为假。

用$E \left(x\right)$表示一个表达式（expression），当使用一类对象中的一个对象作为$x$时，$E \left(x\right)$成为一个命题，$E$则是一个性质（property），“$x$有性质$E$”即“$E \left(x\right)$为真”。若$x$属于类$X$（$x$是集合$X$的一个元素），则记作$x \in X$，反之记为$x \notin X$。

那么 $$ \set{x \in X ; E \left( x \right)} $$ 是$X$中所有具有性质$E$的元素$x$构成的类。

使用符合号$\exist$代表量词（quantifier）“存在”，使用符号$\forall$代表量词“对任意”。

例如 $$ \exist x \in X : \left( x \right) $$ 表示“$X$中至少有一个$x$有性质$E$”。也可以使用$\exist ! x \in X : E \left( x \right)$表示$X$恰有一个$x$存在。 $$ \forall x \in X : E \left( x \right) $$ 表示“$X$中的每一个$x$都有性质$E$”。

最后，使用符号$\colonequals$表示定义，例如$a \colonequals b$。

1.1 示例

记$A$和$B$是命题，$X$和$Y$是对象构成的类，$E$是性质，那么有以下命题。

(a) $\neg \neg A \colonequals \neg \left( \neg A \right) = A$

(b) $\neg \left( A \land B \right) =\left( \neg A \right) \vee \left( \neg B \right) $

(c) $\neg \left( A \vee B \right) =\left( \neg A \right) \land \left( \neg B \right) $

(d) $\neg \left( \forall x \in X : E \left( x \right) \right) = \left( \exist x \in X : \neg E \left( x \right) \right)$

(e) $\neg \left( \exist x \in X : E \left( x \right) \right) = \left( \forall x \in X : \neg E \left( x \right) \right)$

(f) $\neg \left( \forall x \in X: \left( \exist y \in Y: E\left( x, y \right) \right) \right) = \left( \exist x \in X: \left( \forall y \in Y: \neg E\left( x, y \right) \right) \right)$

(g) $\neg \left( \exist x \in X: \left( \forall y \in Y: E\left( x, y \right) \right) \right) = \left( \forall x \in X: \left( \exist y \in Y: \neg E\left( x, y \right) \right) \right)$

1.2 注记

(a) 只要不产生歧义，是否写出括号和属于号$\in$不重要，但是量词$\forall$和$\exist$的顺序非常重要。

(b) 使用量词$\forall$和$\exist$之后，否定就成了纯粹的“机械性”流程，通过改变$\forall$和$\exist$（以及$\land$和$\vee$）的符号（不改变顺序），就可以得到命题的否定。

$A$和$B$是命题，定义新的命题“$A$蕴含（Implication）$B$”为$A \Rightarrow B$，有 $$ \left( A \Rightarrow B \right) \colonequals \left( \neg A \right) \vee B \tag{1.4} $$ 那么，当且仅当$A$为真且$B$为假时$A \Rightarrow B$为假。

$A \Rightarrow B$也可以表示为“$A$是$B$的充分（sufficient）条件”，或者“$B$是$A$的必要（necessary）条件”。

等价（Equivalence）关系$A \Leftrightarrow B$定义为 $$ \left( A \Leftrightarrow B \right) \colonequals \left( A \Rightarrow B \right) \land \left( A \Leftarrow B \right) $$ 这意味着“$A$是$B$的充要（necessary and sufficient）条件”或者“$A$为真当且仅当$B$为真”

对式（1.4）稍作整理，有 $$ \left( A \Rightarrow B \right) \Leftrightarrow \left( \neg B \Rightarrow \neg A \right) \tag{1.5} $$ 其中$\neg B \Rightarrow \neg A$称作是$A \Rightarrow B$的逆否（contrapositive）命题。

在数学上，真命题通常被称作命题（proposition）、定理（theorem）、引理（lemma）、推论（corollary）。命题通常被写作$A \Rightarrow B$的形式，由于$A$为假时命题自然为真，因此我们真正关心的情况是$A$为真的情况。因此为了证明$A \Rightarrow B$为真，可以假定$A$为真，进而推导出$B$为真。

命题的证明可以向前逐步推进，也可以通过反证的方式。前者的方法是 $$ \left( A \Rightarrow C \right) \land \left( C \Rightarrow B \right) \Rightarrow \left( A \Rightarrow B \right) $$ 后者先假设$B$为假，即$\neg B$为真，并且利用假设$A$为真，去证明一个已知为假的命题$C$为真，由此知$B$不可能为假，可知$B$为真。

相较于证明$A \Rightarrow B$，通常证明其逆否命题$\neg B \Rightarrow \neg A$更加容易，由式（1.5）知两者等价。

2 Set

Elementary Facts

如果$X \subseteq Y$（$X$是$Y$的子集，subset），那么$\forall x \in X : x \in Y$。也可以反过来写$Y \supseteq X$。集合相等被定义为 $$ X=Y \colon \Leftrightarrow \left( X \subseteq Y \right) \land \left( Y \subseteq X \right) $$

命题$X \subseteq X$（反射性，reflexivity）和$\left( X \subseteq Y \right) \land \left( Y \subseteq Z \right) \Rightarrow \left( X \subseteq Z \right)$（传递性，transitivity）显然成立。

如果$X \subseteq Y$和$X \neq Y$，那么$X$称为$Y$的真子集（proper subset），对应可以写作$X \subset Y$或$Y \supset X$（$X$真包含于$Y$）。

$X$为一个集合，$E$是一个性质，那么$\set{x \in X ; E\left( x \right)}$是由$X$中所有满足$E \left( x \right)$的元素$x$构成的$X$的子集。特别的， $$ \emptyset _X \colonequals \set{x \in X ; x \neq x} $$ 是$X$的空子集。

2.1 注记

(a) $E$为一个性质，$x \in X$，那么$x \in \emptyset _X \Rightarrow E \left( x \right)$恒为真。即空集具有一切性质。

证明 $\forall x \in X$，$x \in \emptyset _X$总是假，从而$x \in \emptyset _X \Rightarrow E \left( x \right)$恒为真。

(b) 如果$X$和$Y$为集合，那么$\emptyset _X = \emptyset _Y$，即仅有一个空集，因此将空集记为$\emptyset$，空集是一切集合的子集。

证明 $x \in \emptyset _X \Rightarrow x \in \emptyset _Y$，从而$\emptyset _X \subseteq \emptyset _Y$，同理亦有$\emptyset _Y \subseteq \emptyset _X$，故$\emptyset _X = \emptyset _Y$。

The Power Set

若$X$是一个集合，那么由$X$的子集作为元素构成的集合记为$\mathcal{P} \left( X \right)$，即$X$的幂集（power set），有时也写作$2^X$。之所以这么写，是因为在$\mathcal{P} \left( X \right)$和$X$到$\set{0,1}$上的全体函数（$\set{0,1} ^X$）之间，存在一个一一对应关系（对于$\mathcal{P} \left( X \right)$的任意一个元素、$X$的子集，取一个映射使将在子集中的元素映射到1、不在子集中的元素映射到0，那么每一个子集都和唯一一个$X$对应到$\set{0,1}$上的映射相对应，详见练习题3.6。）

$\mathcal{P} \left( X \right)$永远不会是空集。

2.2 示例

(a) $\mathcal{P} \left( \emptyset \right) = \set{\emptyset}$，$\mathcal{P} \left( \set{\emptyset} \right) =\set{\emptyset, \set{\emptyset}}$

Complement, Intersection and Union

$A$和$B$是集合$X$的子集，那么 $$ A \backslash B \colonequals \set{ x \in X ; \left( x \in A \right) \land \left( x \notin B \right)} $$ 是$B$在$A$中的补集（complement）。当集合$X$可以从上文中明确时， $$ A^C \colonequals X \backslash A $$ 表示$A^C$是$A$的补集。

集合 $$ A \cap B \colonequals \set{x \in X ; \left( x \in A \right) \land \left( x \in B \right)} $$ 称作$A$和$B$的交集（intersection）。如果$A \cap B = \emptyset$，即$A$和$B$没有共同的元素，那么$A$和$B$不相交（disjoint）。显然，$A \backslash B = A \cap B^C$。

集合 $$ A \cup B \colonequals \set{x \in X ; \left( x \in A \right) \vee \left( x \in B \right)} $$ 称作$A$和$B$的并集（union）。

2.3 注记

韦恩图（Venn diagrams）不能用于证明，但是可以提供对集合关系的直观印象。

2.4 定理

记$X$、$Y$和$Z$是三个集合，有：

(i) $X \cup Y = Y \cup X$，$X \cap Y = Y \cap X$（交换律，commutativity）

(ii) $X \cup \left( Y \cup Z \right) = \left( X \cup Y \right) \cup Z$，$X \cap \left( Y \cap Z \right) = \left( X \cap Y \right) \cap Z$（结合律，associativity）

(iii) $X \cup \left( Y \cap Z \right) = \left( X \cup Y \right) \cap \left( X \cup Z \right)$，$X \cap \left( Y \cup Z \right) = \left( X \cap Y \right) \cup \left( X \cap Z \right)$（分配律，distributivity）

(iv) $X \subset Y \Leftrightarrow X \cup Y = Y \Leftrightarrow X \cap Y = X$

证明依据定义证明。

Products

两个对象可以组成一个有序对（ordered pair）$\left( a,b \right)$。有序对的等量关系定义为 $$ \left( a,b \right) = \left( a^\prime ,b^\prime \right) \colon \Leftrightarrow \left( a = a^\prime \right) \land \left( b = b^\prime \right) $$

对于$x = \left( a,b \right)$定义 $$ \mathrm{pr}_1 \left( x \right) \colonequals a, \quad \mathrm{pr}_2 \left( x \right) \colonequals b $$ 我们称$\mathrm{pr}_j \left( x \right)$是$x$第$j$个投影（projection）。

若$X$和$Y$是集合，那么$X$和$Y$的笛卡尔积（Cartesian product）$X \times Y$是全体有序对$\left( x,y \right)$的集合，其中$x \in X$且$y \in Y$。

2.6 定理

(i) $X \times Y= \emptyset \Leftrightarrow \left( X= \emptyset \right) \vee \left( Y= \emptyset \right)$

证明反证法。

(ii) 通常来说$X \times Y \neq Y \times X$

扩展到多个集合的笛卡尔积，$X_1 \times \cdots \times X_n$记作$\left( x_1, \dots x_n \right)$，$x_j$是$x$的第$j$个组成成分（component），元素$x_j$也记作$\mathrm{pr}_j \left( x \right)$，是$x$第$j$个投影。$X_1 \times \cdots \times X_n$也记作$\prod^n_{j=1} X_j$。如果乘积中的所有集合都相同，例如$X_j=X, \quad \forall j=1, \dots ,n$，乘积也记作$X^n$。

Families of Sets

对于非空集合$\mathsf{A}$，$\forall \alpha \in \mathsf{A}$，记$A_\alpha$为一集合，则$\set{A_\alpha ; \alpha \in \mathsf{A}}$称作集合的族（family of sets），$\mathsf{A}$是这个集合族的索引集（index set）。

记$X$是个集合，$\mathcal{A} \colonequals \set{ A_\alpha ; \alpha \in \mathsf{A}}$，定义集合族的交和并分别为 $$ \bigcap_\alpha A_\alpha \colonequals \set{ x \in X ; \forall \alpha \in \mathsf{A} : x \in A_\alpha} $$ $和 $$ \bigcup_\alpha A_\alpha \colonequals \set{x \in X ; \exist \alpha \in \mathsf{A} : x \in A_\alpha} $$

作为记号，$\bigcap_\alpha A_\alpha$可以记作$\bigcap_{\alpha \in \mathsf{A}}A_\alpha$，$\bigcap_\alpha \set{x \in X ; x \in A_\alpha}$，$\bigcap_{A \in \mathcal{A}}A$，或者最简单的$\bigcap \mathcal{A}$。如果$\mathcal{A}$是有限个集合的族，那么也可以记作$\bigcap_{j=0}^n A_j$和$A_0 \cap \cdots \cap A_n$。

2.7 定理

记$\set{A_\alpha ; \alpha \in \mathsf{A}}$和$\set{B_\beta ; \beta \in \mathsf{B}}$是两个集合族，这两个集合族都是$X$的子集，记号$\left( \alpha , \beta \right)$遍历索引集$\mathsf{A} \times \mathsf{B}$。那么有：

(i) $\left( \bigcap_\alpha A_\alpha \right) \cap \left( \bigcap_\beta B_\beta \right)=\bigcap_{\left( \alpha , \beta \right)} A_\alpha \cap B_\beta$，$\left( \bigcup_\alpha A_\alpha \right) \cup \left( \bigcup_\beta B_\beta \right)=\bigcup_{\left( \alpha , \beta \right)} A_\alpha \cup B_\beta$（交换率）

(ii) $\left( \bigcap_\alpha A_\alpha \right) \cup \left( \bigcap_\beta B_\beta \right)=\bigcap_{\left( \alpha , \beta \right)} A_\alpha \cup B_\beta$，$\left( \bigcup_\alpha A_\alpha \right) \cap \left( \bigcup_\beta B_\beta \right)=\bigcup_{\left( \alpha , \beta \right)} A_\alpha \cap B_\beta$（分配率）

(iii) $\left( \bigcap_\alpha A_\alpha \right)^C = \bigcup_\alpha A_\alpha^C$，$\left( \bigcup_\alpha A_\alpha \right)^C = \bigcap_\alpha A_\alpha^C$（德摩根率，de Morgan's laws）

证明依据定义证明。(iii)的证明需要使用示例1.1中的结论。

练习题

7 $X$和$A$是$U$的子集，$Y$是$B$是$V$的子集。则有：

(a) 若$A \times B \neq \emptyset$，则$A \times B \subseteq X \times Y \Leftrightarrow \left( A \subseteq X \right) \land \left( B \subseteq Y \right)$

(b) $\left( X \times Y \right) \cup \left( A \times Y \right) = \left( X \cup A \right) \times Y$

(c) $\left( X \times Y \right) \cap \left( A \times B \right) = \left( X \cap A \right) \times \left( Y \cap B \right)$

(d) $\left( X \times Y \right) \backslash \left( A \times B \right) = \left( \left( X \backslash A \right) \times Y \right) \cup \left( X \times \left( Y \backslash B \right) \right)$

证明 (a)$\Leftarrow$显然，$\Rightarrow$反证。其余各题可以通过证明左侧$\subseteq$右侧（$\forall x \in$左侧，$x \in$右侧），同时左侧$\supseteq$右侧（$\forall x \in$右侧，$x \in$左侧）来证明左侧$=$右侧。

8 记$\set{A_\alpha ; \alpha \in \mathsf{A}}$和$\set{B_\beta ; \beta \in \mathsf{B}}$是两个集合族，则有：

(a) $\left( \bigcap_\alpha A_\alpha \right) \times \left( \bigcap_\beta B_\beta \right) = \bigcap_{\left( \alpha , \beta \right)}A_\alpha \times B_\beta$

(b) $\left( \bigcup_\alpha A_\alpha \right) \times \left( \bigcup_\beta B_\beta \right) = \bigcup_{\left( \alpha , \beta \right)}A_\alpha \times B_\beta$

证明证明思路同上一题。

3 Functions

从$X$到$Y$的函数（function）或映射（map）$f$是一种规则（rule），对于$X$中的每一个元素，指定$Y$中的特定一个元素与之对应，记作$f: X \rightarrow Y$或$X \rightarrow Y, x \mapsto f\left( x \right)$，也可以记作$f: X \rightarrow Y, x \mapsto f\left( x \right)$。

$f\left( x \right) \in Y$是$f$在$x$处的值（value）。$X$称作$f$的定义域（domain），记作$\mathrm{dom} \left( f \right)$。$Y$是$f$的达域（codomain）。 $$ \mathrm{im} \left( f \right) \colonequals \set{y \in Y ; \exist x \in X : y = f \left( x \right)} $$ 称为$f$的像（image）。

给定函数$f: X \rightarrow Y$， $$ \mathrm{graph} \left( f \right) \colonequals \set{\left( x,y \right) \in X \times Y ; y=f \left( x \right)}=\set{\left( x,f\left( x \right) \right) \in X \times Y ; x \in X} $$ 称作$f$的图（graph）。显然，图是笛卡尔积$X \times Y$的子集。

3.1 注记

记$G$是$X \times Y$的子集，并且$\forall x \in X$，存在唯一的$y \in Y$，使$\left( x,y \right) \in G$，那么由此可以定义函数$f: X \rightarrow Y$满足$\forall x \in X$，$f\left( x \right) \colonequals y$，其中$y \in Y$且$\left( x,y \right) \in G$，显然$\mathrm{graph} \left( f \right) = G$。

以上这种定义方式将函数$f: X \rightarrow Y$定义为了有序三元组$\left( X,G,Y \right)$，其中$G \subseteq X \times Y$，$\forall x \in X$存在唯一的$y \in Y$使$\left( x,y \right) \in G$。有了这样定义就可以使用集合论处理函数了，而不需要所谓的“规则”，将函数认为是一种“规则”的定义是有用的但是不精确的。

Simple Examples

注意以上对函数的定义中，我们并没有排除$X = \emptyset$和$Y = \emptyset$的情况。如果$X = \emptyset$，那么从$X$到$Y$上仅有一个函数，称为空函数（empty function），定义为$\emptyset : \emptyset \rightarrow Y$。如果$Y = \emptyset$，那么从$X$到$Y$上不存在函数。

两个函数相等，需要定义域、达域和规则完全相同，即$f: X \rightarrow Y$和$g: U \rightarrow V$相等，需要$X=U$，$Y=V$，$\forall x\in X \quad f\left( x \right)=g\left( x \right)$，记作$f=g$。

3.2 示例

(a) 函数$\mathrm{id}_X:X \rightarrow X, x \mapsto x$是（$X$上的）恒等函数（identity function）。

(b) 若$X \subseteq Y$，函数$i:X \rightarrow Y, x \mapsto x$称为$X$到$Y$上的包含函数（inclusion function）或嵌入函数（embedding function）。

(c) 若$X$和$Y$非空且$b \in Y$，那么函数$X \rightarrow Y, x \mapsto b$称为常函数（constant function）。

(d) 若函数$f:X \rightarrow Y$且$A \subseteq X$，那么$f|A: A \rightarrow Y, x \mapsto f\left( x \right)$是限制在$A$上的函数$f$（restriction of $f$）。

(e) 取$A \subseteq X$且$g:A \rightarrow Y$，任意函数$f:X \rightarrow Y$且$f|A=g$被称为$g$的扩展（extension），写作$g \subseteq f$。按照注记3.1中利用集合形式定义的函数，$g \subseteq f$的含义是明确的。

(f) 函数$f:X \rightarrow Y$有$\mathrm{im} \left( f \right) \subseteq U \subseteq Y \subseteq V$，那么定义为$\forall x \in X, j \in \set{1,2}, f_j \left( x \right) \colonequals f \left( x \right)$的$f_1:X \rightarrow U$和$f_2:X \rightarrow V$，称为由$f \left( x \right)$诱导（induced）的函数。

(g) 记$X \neq \emptyset$且$A \subseteq X$，那么集合$A$的特征函数（characteristic function of set $A$）定义为 $$ \chi_A : X \rightarrow \set{0,1} , x \mapsto \left{ \begin{aligned} 1,x \in A \ 0,x \notin A \end{aligned} \right. $$

(h) 若$X_1,\dots,X_n$是非空集合，那么投影 $$ \mathrm{pr} k : \prod ^n X_j \rightarrow X_k , x= \left( x_1 , \dots , x_n \right) \mapsto x_k , k=1 , \dots n $$ 是函数。

Composition of Function

取$f:X \rightarrow Y$，$g:Y \rightarrow V$，定义新的函数$g \circ f$为$f$和$g$的复合（composition）函数，有 $$ g \circ f:X \rightarrow V,x \mapsto g \left( f \left( x \right) \right) $$

3.3 定理

（复合函数结合律）取$f:X \rightarrow Y$，$g:Y \rightarrow U$，$h:U \rightarrow V$，有 $$ \left( h \circ g \right) \circ f = h \circ \left( g \circ f \right) $$

证明依据定义证明。

Commutative Diagrams

有时会使用简图来表示函数的复合，在简图中使用$f: X \stackrel{f}{\rightarrow} Y$替代$f: X \rightarrow Y$。若图中$g \circ f = \psi \circ \varphi$则称简图（diagram）是可交换的（commutative）。

\[ \begin{CD} X @>f>> Y \\ @V\varphi VV @VgVV \\ U @>\psi >> V \end{CD} \]

Injections, Surjections and Bijections

取$f:X \rightarrow Y$，若$\mathrm{im} \left( f \right) = Y$则$f$是满射的（surjective），若$\forall x_1,x_2 \in X, f \left( x_1 \right)=f \left( x_2 \right)$意味着$x=y$则$f$是单射的（injective），若$f$既是单射的又是满射的则$f$是双射的（bijective）。

3.5 定理

取$f:X \rightarrow Y$，$f$是双射当且仅当存在函数$g:Y \rightarrow X$，使得$g \circ f = \mathrm{id}_X$且$f \circ g = \mathrm{id}_Y$，并且函数$g$被$f$唯一确定。

证明证明分三步：充分性、必要性、唯一性。

充分性：$f$是满射则$\forall y \in Y, \exist x \in X, f \left( x \right)=y$，$f$是单射则上述$x$是唯一，由此定义$g:Y \rightarrow X, g \left( y \right)=x$。

必要性：$f \circ g = \mathrm{id}_Y$则$f$是满射。取$x_1,x_2 \in X, f \left( x_1 \right) = f \left( x_2 \right)$，有$x_1=g \left( f \left( x_1 \right) \right)=g \left( f \left( x_2 \right) \right)=x_2$，从而$f$是单设。

唯一性：若另存在一满足题设条件的$h$，有$g=g \circ \mathrm{id}_Y=g \circ f \circ h=\mathrm{id}_Y \circ h=h$。

Inverse Functions

参照定理3.5，取$f:X \rightarrow Y$为一双射，$f$的反函数（inverse function）$f^{-1}:Y \rightarrow X$定义为唯一使$f^{-1} \circ f= \mathrm{id}_X$和$f \circ f^{-1}= \mathrm{id}_Y$成立的函数。

3.6 定理

取$f:X \rightarrow Y$和$g:Y \rightarrow V$为两个双射，那么$g \circ f:X \rightarrow V$是双射，并且 $$ \left( g \circ f \right)^{-1}=f^{-1} \circ g^{-1} $$

证明 $g \circ f$是双射使用定义证明，并且直接验证$g \circ f \circ f^{-1} \circ g^{-1}=\mathrm{id}_Y$和$f^{-1} \circ g^{-1} \circ g \circ f=\mathrm{id}_X$即可。

取$f:X \rightarrow Y$为一函数，且$A \subseteq X$，则 $$ f \left( A \right) \colonequals \set{f \left( a \right) \in Y ; a \in A} $$ 称为$A$在$f$下的像（image）。对于每一个$C \subseteq Y$， $$ f^{-1} \left( C \right) \colonequals \set{x \in X ; f \left( x \right) \in C} $$ 称为$C$在$f$下的原像（preimage）。

Set Valued Functions

取$f:X \rightarrow Y$为一函数，有以下两个集值函数（set valued function）： $$ f : \mathcal{P} \left( X \right) \rightarrow \mathcal{P} \left( Y \right) , A \mapsto f \left( A \right) $$ 和 $$ f^{-1} : \mathcal{P} \left( Y \right) \rightarrow \mathcal{P} \left( X \right) , B \mapsto f^{-1} \left( B \right) $$ 在这里我们依旧使用$f$和$f^{-1}$符号，但是它们指代的是集值函数，而非原函数和原函数的逆。

如果$f:X \rightarrow Y$是双射，那么$f^{-1} : Y \rightarrow X$存在并且$\forall y \in Y$有$\set{f^{-1} \left( y \right)}=f^{-1}\left( \set{y} \right)$。注意，这里的两个$f^{-1}$含义并不相同，前面的表示原函数的逆，后者表示由原函数诱导出的极值函数。如果$f:X \rightarrow Y$不是双射，那么原函数的逆不存在，只有集值函数$f^{-1}$存在。在以上两种情况中，我们均使用$f^{-1} \left( y \right)$指代$f^{-1} \left( \set{y} \right)$，并且称$f^{-1} \left( y \right)$是原函数$f$在$y$处的切片（fiber）。切片$f^{-1} \left( y \right)$是等式$f \left( x \right) = y$的解的集合$\set{x \in X; f \left(x \right) = y}$。

3.8 定理

对于由$f$诱导出的集值函数：

(i) $A \subseteq B \subseteq X \Rightarrow f \left( A \right) \subseteq f \left( B \right)$

(ii) $\forall \alpha \in \mathsf{A} \quad A_\alpha \subseteq X \Rightarrow f \left( \bigcup_\alpha A_\alpha \right) = \bigcup_\alpha f \left( A_\alpha \right)$

(iii) $\forall \alpha \in \mathsf{A} \quad A_\alpha \subseteq X \Rightarrow f \left( \bigcap_\alpha A_\alpha \right) \subseteq \bigcap_\alpha f \left( A_\alpha \right)$

(iv) $A \subseteq X \Rightarrow f \left( A^C \right) \supseteq f \left( X \right) \backslash f \left( A \right)$

(i') $A^\prime \subseteq B^\prime \subseteq Y \Rightarrow f^{-1} \left( A^\prime \right) \subseteq f^{-1} \left( B^\prime \right)$

(ii') $\forall \alpha \in \mathsf{A} \quad A^\prime_\alpha \subseteq Y \Rightarrow f^{-1} \left( \bigcup_\alpha A^\prime_\alpha \right) = \bigcup_\alpha f^{-1} \left( A^\prime_\alpha \right)$

(iii') $\forall \alpha \in \mathsf{A} \quad A^\prime_\alpha \subseteq X \Rightarrow f^{-1} \left( \bigcap_\alpha A^\prime_\alpha \right) = \bigcap_\alpha f^{-1} \left( A^\prime_\alpha \right)$

(iv') $A^\prime \subseteq Y \Rightarrow f^{-1} \left( A^{\prime C} \right) = X \backslash f^{-1} \left( A^\prime \right) = \left[f^{-1} \left( A^\prime \right)\right]^C$

如果另有一个$g: Y \rightarrow V$那么$\left( g \circ f \right)^{-1}=f^{-1} \circ g^{-1}$。

说明证明均可由定义证明，这里对部分特殊情况进行说明。

在(iii)中，因为函数$f$可能不是单射的，所以$\forall \alpha \in \mathsf{A} \quad y \in f \left( A_\alpha \right)$不能保证$\bigcap_\alpha A_\alpha$中存在可以使$f$取到$y$值的元素。例如，$f\left( x \right)=c,A_i=\set{i}$，显然$f \left( \bigcap_\alpha A_\alpha \right)=\emptyset$而$\bigcap_\alpha f \left( A_\alpha \right)=\set{c}$。但是在(iii')中，$\forall \alpha \in \mathsf{A} \quad x \in f^{-1} \left( A^\prime_\alpha \right)$可以确保$f \left( x \right) \in \bigcap_\alpha A^\prime_\alpha$并且$x \in f^{-1} \left( \bigcap_\alpha A^\prime_\alpha \right)$。

在(iv)中，因为函数$f$可能不是单射的，所以$f \left( A^C \right) \bigcap f \left( A \right)$可以不是空集。例如，若$f \left( x_1 \right)=f \left( x_2 \right)=y$，那么如果$x_1 \in A$而$x_2 \notin A$，有$y \in f \left( A^C \right)$而$y \notin f \left( X \right) \backslash f \left( A \right)$。但是在(iv')中，$f^{-1} \left( A^{\prime C} \right)$和$f^{-1} \left( A^\prime \right)$将整个$X$一分为二，$\forall x \in X$不是在$f^{-1} \left( A^{\prime C} \right)$中，就是在$f^{-1} \left( A^\prime \right)$中。

若$A=\left( g \circ f \right)^{-1} B$，那么$\left( g \circ f \right) \left( A \right)=B$，且$\forall x \notin A$有$\left( g \circ f \right) \left( x \right) \notin B$。由于$B=\left( g \circ f \right) \left( A \right)=g \left( f \left( A \right) \right)$故$A \in f^{-1} \circ g^{-1} \left( B \right)$。又若$\exist x \notin A$但$x \in f^{-1} \circ g^{-1} \left( B \right)$，有$\left( g \circ f \right) \left( x \right) = g \left( f \left( x \right) \right) \in B$，产生矛盾，故$A = f^{-1} \circ g^{-1} \left( B \right)$。

定理3.8的(i')-(iv')表明，函数$f^{-1} : \mathcal{P} \left( Y \right) \rightarrow \mathcal{P} \left( X \right)$保留了所有集合运算，同时(iii)和(iv)则表明，$f : \mathcal{P} \left( X \right) \rightarrow \mathcal{P} \left( Y \right)$并不能保留集合运算。

最后，将$X$到$Y$上的所有函数构成的集合记为$\mathrm{Funct}\left( X,Y \right)$。正如注记3.1描述的那样，$\mathrm{Funct}\left( X,Y \right)$是$\mathcal{P}\left( X \times Y \right)$的子集。

（$X \times Y$是全部的二元组，$\mathcal{P}\left( X \times Y \right)$是全部二元组的全部子集构成的集合，显然在其中某个子集、由部分二元组构成的集合中，二元组的第一个元可以不穷尽所有的$X$，但是对于函数来说所有$X$中的元素都必须有一个属于$Y$的值与之对应。另一方面，在$\mathcal{P}\left( X \times Y \right)$中的某个元素、由部分二元组构成的集合中，二元组第一个元可以取相同的值而第二个元取不同的值，显然函数并不能这样。）

我们有时也使用记号$Y^X$表示$\mathrm{Funct}\left( X,Y \right)$，即从$X$到$Y$上的所有函数。之前我们使用记号$X^n$表示集合$X$的$n$维笛卡尔积，如果将每一个$\left(x_1,\dots,x_n\right)$视作一个函数$f \left( i \right)=x_i$，那么这一符号也与从集合$\set{1,2,\dots,n}$到$X$上的全部函数的含义一致。

练习题

4 取$f:X \rightarrow Y$为一函数，以下三个命题等价：(a) $f$单射。(b)$f^{-1}\left(f\left( A \right) \right)=A , A \in X$。(c)$f\left( A \bigcap B \right)=f\left( A \right) \bigcap f\left( B \right)$。

6 对任意非空集合$X$，函数$\mathcal{P}\left( X \right) \rightarrow \set{0,1}^X,A\mapsto \chi_A$是双射。其中$\chi_A$表示在$A$上取1的特征函数。

7 取$f:X \rightarrow Y$为一函数，函数$i:A \rightarrow X$是$X$的子集$A$上的包含函数，那么有：(a)$f|A=f \circ i$。(b)$\left( f | A \right)^{-1}\left( B \right)=A \bigcap f^{-1} \left( B \right),B \subset Y$。

说明以上三题均不难使用定义证明，重要的是结论。

4 Relations and Operations

$X$上的（二元）关系（relation）是子集$R \subseteq X \times X$。二元关系通常不写作$\left( x,y \right) \in R$，而是写作$xRy$或者$x\underset{R}{\sim}y$。

对于$X$上的关系$R$：

如果$\forall x \in X , xRx$，即$R$中包含所有对角（diagonal）$\Delta_X \colonequals \set{\left( x,x \right) ; x \in X}$，那么$X$上的关系$R$是反射的（reflexive）。

如果$\left( xRy \right) \land \left( yRz \right) \Rightarrow xRz$，那么$X$上的关系$R$是传递的（transitive）。

如果$xRy \Rightarrow yRx$，那么$X$上的关系$R$是对称的（symmetric）。

取$Y$是$X$的非空子集，$R$是$X$上的关系，那么集合$R_Y \colonequals \left( Y \times Y \right) \bigcap R$是$Y$上的关系，称作$R$在$Y$上的限制（restriction）。显然$xR_Yy$当且仅当$x,y \in Y$并且$xRy$。

Equivalence Relations

对于$X$上的关系，如果它是反射的、传递的、对称的，那么它被称为是$X$上的等价关系（equivalence relation），并且通常记作$\sim$。

对于每个$x \in X$，集合 $$ \left[ x \right] \colonequals \set{y \in X;y \sim x} $$ 是$x$的等价类（equivalence class），每个$y \in \left[ x \right]$都是等价类的代表（representative）。

集合 $$ X / \sim \colonequals \set{\left[ x \right];x \in X} $$ 称为“$X$模$\sim$”，是$X$的所有等价类的集合，显然它是$\mathcal{P}\left( X \right)$的子集。

集合$X$的划分（partition）是子集$\mathcal{A} \subseteq \mathcal{P} \left( X \right) \backslash \left\{ \emptyset \right\}$，并且具有性质$\forall x \in X$有唯一的$A \in \mathcal{A}$使$x \in A$。即$\mathcal{A}$由互不相交的$X$的子集构成，并且这些子集的并集等于$X$。

4.1 定理

取$\sim$是$X$上的等价关系，那么$X/\sim$是对$X$的划分。

证明显然任意$x \in X$都在$X/\sim$的子集中，只要用反证法证明任意两个子集的交集为空即可。

定义函数 $$ p \colonequals p_X : X \rightarrow X/\sim , x \mapsto \left[ x \right] $$ 显然这一函数是满射，称作$X$到$X/\sim$的（规范）商函数（quotient function）。

4.2 示例

(c) 取$f:X \rightarrow Y$为一函数，那么 $$ x \sim y : \Leftrightarrow f \left( x \right) = f \left( y \right) $$ 是$X$上的等价关系，对于$x \in X$的等价类是$\left[ x \right]=f^{-1}\left( f\left( x \right) \right)$

此外，存在函数$\tilde{f}$使如下的概念图成为交换图。其中函数$\tilde{f}$单射，并且$\mathrm{im} ( \tilde{f} ) = \mathrm{im} \left( f \right)$，当$f$是满射时$\tilde{f}$是双射。

\[ \begin{CD} X @>f>> Y \\ @Vp VV @A\tilde{f}AA \\ X/\sim @= X/\sim \end{CD} \]

(d) 如果$\sim$是$X$上的等价关系，$Y$是$X$的非空子集，那么将$\sim$限制在$Y$上得到的是$Y$上的等价关系。

Order Relations

$X$上的关系$\leq$，如果它是反射的、传递的、反对称的（anti-symmetric），那么它是偏序（partial order）。其中反对称意味着 $$ \left( x \leq y \right) \land \left( y \leq x \right) \Rightarrow x=y $$

如果$\leq$是$X$上的偏序，那么$\left( X , \leq \right)$称作偏有序集（partial ordered set）。

如果另有 $$ \forall x,y \in X: \left( x \leq y \right) \vee \left( y \leq x \right) $$ 成立，那么$\leq$被称作$X$上的全序（total order），并且$\left( X,\leq \right)$是全序集（totally ordered set）。

4.3 注记

(a) 以下是常用记号： $$ x \geq y:\Leftrightarrow y \leq x $$

\[ x<y :\Leftrightarrow \left( x \leq y \right) \land \left( x \neq y \right) \]

\[ x>y :\Leftrightarrow y<x \]

(b) 如果$X$是全序，那么对于每一对元素$x.y \in X$，以下只有一个是真的 $$ xy $$ 但如果$X$是偏序并且不是全序的，那么至少有两个元素$x,y \in X$是不可比较的，即$x \leq y$和$y \leq x$都不是真的。

4.4 示例

(a) $\left( X, \leq \right)$是偏有序集，并且$Y$是$X$的非空子集，那么将$\leq$限制在$Y$上之后也是偏序。

(b) $\left( \mathcal{P} \left( X \right), \subseteq \right)$是偏有序集，$\subseteq$称为$\mathcal{P} \left( X \right)$上的包含顺序（inclusion order）。通常情况下$\left( \mathcal{P} \left( X \right), \subseteq \right)$不是全有序的。

(c) $X$为一集合，$\left( Y,\leq \right)$是一偏有序集，那么 $$ f \leq g:\Leftrightarrow f\left( x \right) \leq g\left( x \right),x \in X $$ 定义了$\mathrm{Funct}\left( X,Y \right)$上的偏序。集合$\mathrm{Funct}\left( X,Y \right)$通常不是全有序的。

惯例除非另有说明，$\mathcal{P} \left( X \right)$及其子集都是带有包含顺序的偏有序集。

取$\left( X, \leq \right)$为一偏有序集，$A$是$X$的非空子集，对于$s \in X$，如果$\forall a \in A$都有$a \leq s$，那么$s$是$A$的一个上界（upper bound）。类似地，如果$\forall a \in A$都有$a \geq s$，那么$s$是$A$的一个下界（lower bound）。如果子集$A$有一个上界，则称为上有界（bounded above），如果有一个下界，则成为下有界（bounded below），如果即上有界又下有界则简称为有界的（bounded）。

$A$是$X$的非空子集，对于$m \in X$，如果满足$m \in A$并且$m$是$A$的上确界，那么$m$是$A$的最大值（maximum），记作$\max \left( A \right)$。如果满足$m \in A$并且$m$是$A$的下确界，那么$m$是$A$的最小值（minimum），记作$\min \left( A \right)$。注意，集合$A$最多只有一个最大值和一个最小值。

记$A$是偏有序集$X$的有上界子集，若$A$所有上界构成的集合有最小值，那么这个元素称作$A$的最小上界（least upper bound）或者$A$的上确界（supreme），记作$\sup \left( A \right)$，即 $$ \sup \left( A \right) \colonequals \min \set{s \in X ; s 是A的一个上界} $$ 相似的，对于$X$有下界非空子集$A$，定义 $$ \inf \left( A \right) \colonequals \max \set{s \in X ; s 是A的一个下界} $$ 称作$A$的最大下界（greatest lower bound）或者$A$的下确界（infimum），记作$\inf \left( A \right)$。如果$A$中含有两个元素，即$A=\set{a,b}$，通常使用记号$a \vee b \colonequals \sup \left( A \right)$和$a \land b \colonequals \inf \left( A \right)$。

4.5 注记

(a) 有上界（下界）的集合并不一定有最小上界（最小下界），详见示例10.3。

(c) 如果$\sup \left( A \right)$存在并且$\sup \left( A \right) \in A$那么$\sup \left( A \right) = \max \left( A \right)$。类似地，如果$\inf \left( A \right)$存在并且$\inf \left( A \right) \in A$那么$\inf \left( A \right) = \min \left( A \right)$。

(d) 如果$\max \left( A \right)$存在那么$\sup \left( A \right) = \max \left( A \right)$。类似地，如果$\min \left( A \right)$存在那么$\inf \left( A \right) = \min \left( A \right)$。

4.6 示例

(a) 记$\mathcal{A}$是$\mathcal{P} \left( X \right)$的非空子集，那么 $$ \sup \left( \mathcal{A} \right) = \bigcup \mathcal{A},\inf \left( \mathcal{A} \right) = \bigcap \mathcal{A} $$

(b) 取$\chi \colonequals \mathcal{P} \left( X \right)\backslash \set{\emptyset}$，$A,B \in \chi$且$A \cap B = \emptyset$，集合$\mathcal{A} \colonequals \set{A,B}$，那么$\mathcal{A} \subseteq \chi$且$\sup \left( \mathcal{A} \right) = A \cup B$，但是$\mathcal{A}$没有最大值，也没有下界。

取$X \colonequals \left( X, \leq \right)$和$Y \colonequals \left( Y, \leq \right)$是两个偏有序集，函数$f \colon X \rightarrow Y$。如果$x \leq y$意味着$f \left( x \right) \leq f \left( y \right)$，那么函数是增的（increasing），如果$x \leq y$意味着$f \left( x \right) \geq f \left( y \right)$，那么函数是减的（decreasing）。如果$x < y$意味着$f \left( x \right) < f \left( y \right)$，那么函数是严格增的（strictly increasing），如果$x < y$意味着$f \left( x \right) > f \left( y \right)$，那么函数是严格减的（strictly decreasing）。如果函数是增的或者是减的，那么函数是单调的（monotone），如果函数是严格增的或者是严格减的，那么函数是严格单调的（strictly monotone）。

取$X$为任意集合，$Y \colonequals \left( Y, \leq \right)$是偏有序集，函数$f \colon X \rightarrow Y$，如果$\mathrm{im} \left( f \right)=f\left( X \right)$是有界的、上有界的、下有界的，那么就称函数$f$是有界的、上有界的、下有界的。

如果$X \colonequals \left( X, \leq \right)$和$Y \colonequals \left( Y, \leq \right)$是两个偏有序集，函数$f \colon X \rightarrow Y$，如果对$X$的任意有界子集$A$，限制在$A$上的函数$f|A$有界，那么$f$在有界集上有界（bounded on bounded set）。

4.7 示例

(a) $X$和$Y$是集合，$f \in Y^X$，那么诱导出的函数$f \colon \mathcal{P} \left( X \right) \rightarrow \mathcal{P} \left( Y \right)$和$f^{-1} \colon \mathcal{P} \left( Y \right) \rightarrow \mathcal{P} \left( X \right)$都是增的。

(b) $X$是至少有两个元素的集合，取$\chi \colonequals \mathcal{P} \left( X \right)\backslash \set{X}$且$\chi$有包含顺序，那么恒等函数$\chi \rightarrow \chi , A \mapsto A$在有界集上有界，但是它本身是无界的。