笔记与习题：《集合论：对无穷概念的探索》（2）

第二章 关系与函数

逻辑主义：将所有数学至于纯逻辑基础之上

两个信念：

（1）任何数学理论都在某种意义上是关于集合的理论

（2）任何数学命题是真的都意味着它在ZFC中得到证明

本章与下一章是以上信念的体现——用集合论的语言刻画经典数学的一些基本概念

但是很多数学问题，包括集合论的核心问题：连续统假设，在通常的ZFC中不可证明，这一点需要指出。

2.1 关系

最简单的关系：二元关系——一种对应或者映射——有序对$(a,b)$

定义：设$a$，$b$为集合，$a$，$b$组成的有序对定义为：

$$(a,b)=\{\{a\},\{a,b\}\}$$

证明这一定义是合理的：

首先，证明$\{\{a\},\{a,b\}\}$是集合

练习：证明对任何集合$a$,$b$,$\{\{a\},\{a,b\}\}$是集合

由对集公理：$\forall a \forall b \exists c \forall x(x\in c \leftrightarrow x=a \vee x=b)$

$\forall a \forall a \exists a^{\ast} \forall x(x\in a^{\ast} \leftrightarrow x=a \vee x=a)$

即$a^*=\{a\}$是集合

$\forall a \forall b \exists b^{\ast} \forall x(x\in b^{\ast} \leftrightarrow x=a \vee x=b)$

即$b^*=\{a,b\}$是集合

$\forall a^{\ast} \forall b^{\ast} \exists c \forall x(x\in c \leftrightarrow x=a^{\ast} \vee x=b^{\ast})$

即$c=\{a^{\ast},b^{\ast}\}=\{\{a\},\{a,b\}\}$是集合

其次，证明以下命题：

命题：任何两个有序对$(a,b)$，$(a^{\ast},b^{\ast})$，$(a,b)=(a^{\ast},b^{\ast})$当且仅当$a=a^{\ast}$且$b=b^{\ast}$

从右边向左边使用外延公理直接证明

从左边向右边使用上述定义分①$a=b$，②$a\ne b$两种情况讨论，证明的详细过程略去

定义：令$X$和$Y$为集合，则$X$和$Y$的卡氏积定义为：

$$X\times Y=\{(x,y)|x\in X\wedge y\in Y\}$$

练习：证明对任意$A$和$B$，它们的卡氏积是集合

考虑任意一对有序对$(a,b)$，使$a\in A,b\in B$

根据有序对定义：$(a,b)=\{\{a\},\{a,b\}\}$

现在我们有：$\{a\}\subseteq A$

所以$\{a\}\subseteq A \cup B$

因此$\{a\}\in \mathcal{P}(A \cup B)$

同样地，$\{a,b\}\subseteq A \cup B$

所以$\{a,b\}\in \mathcal{P}(A \cup B)$

由此可见：$\{\{a\},\{a,b\}\}\subseteq \mathcal{P}(A \cup B)$

所以$\{\{a\},\{a,b\}\}\in \mathcal{P}({\mathcal{P}(A \cup B)})$

（以上构造的所有集合可由并集公理和幂集公理证明存在，这里为了保证证明过程的可读性，不再使用严格的形式化语言进行证明）

由分离公理：$\forall X \exists Y \forall u(u\in Y \leftrightarrow u\in X \wedge \varphi(u))$

可以知道存在一个集合$E=\{t∈\mathcal{P}({\mathcal{P}(A \cup B)} | \exists a\exists b(a\in A\wedge b∈B\wedge t=(a,b)\}$

由外延公理可知，该集合是唯一的，它是所有$a\in A,b\in B$的有序对$(a,b)$的集合。

也就是$A$与$B$的卡氏积，所以卡氏积是集合

定义：一集合$R$称为二元关系，如果存在集合$X$，$Y$，$R\subseteq X\times Y$。

用$R(x,y)$表示$(x,y)\in R$，称$x$和$y$有关系$R$。习惯写作$xRy$

定义：令$R$为二元关系，

（1）$R$的定义域定义为：$dom(R)=\{x|\exists yR(x,y)\}$

（2）$R$的值域定义为：$ran(R)=\{y|\exists xR(x,y)\}$

练习：证明$dom(R)$和$ran(R)$都是集合

因为$R$是集合

且$dom(R)=\{x|\exists yR(x,y)\}=\{x|\exists y(\{\{x\},\{x,y\}\}\in R)\}$

$ran(R)=\{y|\exists xR(x,y)\}=\{y|\exists x(\{\{x\},\{x,y\}\}\in R)\}$

由并集公理，$\cup \cup R$是集合，且$\cup R=\{u|\exists z(z\in R\wedge u\in z)\}$

$\cup\cup R=\{v|\exists a(a\in \{u|\exists z(z\in R\wedge u\in z)\}\wedge v\in a)\}$

可见$dom(R),ran(R)\subset \cup\cup R$

因为$\cup \cup R$是集合

所以，由分离公理可知，$dom(R)$和$ran(R)$都是集合

定义：

（1）集合$X$在关系$R$下的像：$R[X]=\{y\in ranR|\exists x\in X(R(x,y))\}$

（2）集合$X$在关系$R$下的逆像：$R^{-1}[Y]=\{x\in domR|\exists y\in Y(R(x,y))\}$

（3）二元关系$R$的逆：$R^{-1}=\{(x,y)|(y,x)\in R\}$

（4）二元关系$R$和$S$的复合：$S\circ R=\{(x,z)|\exists y((x,y)\in R\wedge(y,z)\in S)\}$

练习：证明集合$Y$在关系$R$下的逆像与$Y$在$R^{-1}$下的像相等

根据定义，$Y$在$R$下的逆像由以下集合给出

$R^{-1}[Y]=\{x\in domR|\exists y\in Y(R(x,y))\}=\{x\in \{x|\exists yR(x,y)\}|\exists y\in Y(R(x,y))\}$

另一方面，$Y$在$R^{-1}$下的像由以下集合给出

$R^{-1}[Y]=\{y\in ranR|\exists x\in Y(R(x,y))\}=\{y\in \{y|\exists xR(x,y)\}|\exists x\in Y(R(x,y))\}$

所以需要证明$\{x\in \{x|\exists yR(x,y)\}|\exists y\in Y(R(x,y))\}=\{y\in \{y|\exists xR(x,y)\}|\exists x\in Y(R(x,y))\}$

这是显然的

推广：对三元序组、四元序组……n元序组的定义；对n个集合的卡氏积的定义；n元关系。（递归定义\归纳定义）

$$三元序组:(x_1,x_2,x_3)=((x_1,x_2),x_3)$$ $$四元序组:(x_1,x_2,x_3,x_4)=((x_1,x_2,x_3),x_4)$$ $$n元序组:(x_1,x_2,\dots,x_n)=((x_1,\dots,x_{n-1}),x_n)$$

以上这种定义方式叫递归定义\归纳定义

$$n个集合的卡氏积:X_1\times \dots\times X_n=\{(x1,\dots,x_n)|x_1\in X_1\wedge \dots \wedge x_n \in X_n\}$$ $$n元关系:R\subseteq X_1\times \dots \times X_n,\\通常将(x_1,\dots,x_n)\in R写作R(x_1,\dots,x_n)$$

2.2 函数

定义：一个二元关系$f$如果满足：

$$(x,y)\in f\wedge (x,z)\in f \rightarrow y=z$$

就称$f$是一个函数。记法：$f(x)=y$，$f:x\mapsto y$，$f_x=y$

如果$dom(f)=X,ran(f)\subseteq Y$，就称$f$是$X$到$Y$的函数，记为$f:X\rightarrow Y$

练习：令$f$和$g$为函数。$f=g$当且仅当$dom(f)=dom(g)$，而且对所有$x\in dom(f)$，都有$f(x)=g(x)$

根据定义：$(x,y)\in h\wedge (x,z)\in h \rightarrow y=z$

由题，$dom(f)=dom(g)$

且对所有$x\in dom(f)$，都有$f(x)=g(x)$

即$(a,b)\in f\wedge (a,b^{\ast})\in f \rightarrow b=b^{\ast}$

$(a,c)\in g\wedge (a,c^{\ast})\in g \rightarrow c=c^{\ast}$

且$b=c$

由外延公理可得

$f=g$

---

以下的内容都是构造新函数的方法

练习：如果$f$和$g$为函数，证明它们的复合$h=g\circ f$也是函数，并且$h$的定义域为$dom(h)=dom(f)\cap f^{-1}[dom(g)]$

$h=g\circ f=\{(x,z)|\exists y((x,y)\in f\wedge(y,z)\in g)\}$

如果$h$不是函数，则$(a,b^{\ast})\in h\wedge (a,c^{\ast})\in h \rightarrow b^{\ast}\ne c^{\ast}$

又由定义：$\{(a,b^{\ast})|\exists y((a,b)\in f\wedge(b,b^{\ast})\in g)\}$

$\{(a,c^{\ast})|\exists y((a,c)\in f\wedge(b,c^{\ast})\in g)\}$

因为$f$和$g$都为函数，所以$b=c,b^{\ast}= c^{\ast}$

与假设矛盾，所以$h$是函数

$dom(h)=\{x|\exists zh(x,z)\}=\{x|\exists y((x,y)\in f\wedge(y,z)\in g)\}$

由于$\{x|\exists y((x,y)\in f)\}=dom(f)$

$\{x|f(x)((f(x),z)\in g)\}=f^{-1}[dom(g)]$

所以$dom(h)=dom(f)\cap f^{-1}[dom(g)]$

定义：假设$f:X\rightarrow Y$为函数，而且对所有的$x_1,x_2\in X$ ，如果$x_1\ne x_2$，则$f(x_1)=f(x_2)$，这时就$f$为一一函数或单射。如果$ran(f)=Y$，就称$f$为满射，即使单射又是满射的函数称为双射

定义：如果一个函数的逆也是函数，就称其为可逆的

可逆$\leftrightarrow$是单射

定义：对任意函数$f$和集合$A$，$f\upharpoonright A=\{(x,y)\in f|x\in A\}$是一个函数，称为$f$到$A$上的限制。如果$g=f\upharpoonright A$，则称$f$是$g$的扩张

定义：

（1）函数$f$和$g$是相容的，如果对所有$x\in dom(f)\cap dom(g)$，都有$f(x)=g(x)$

（2）函数的集合$\mathcal {F}$称为相容的系统，如果$\mathcal {F}$中的任意两个函数都是相容的

推论：如果$\mathcal {F}$是相容的函数系统，则$\bigcup\mathcal {F}$是函数，它的定义域$dom(\bigcup\mathcal {F})=\bigcup \{dom(f)|f\in\mathcal {F}\}$。函数$\bigcup\mathcal {F}$是所有$f\in\mathcal {F}$的扩张

定义：令$X$和$Y$是集合，$X$到$Y$的所有函数组成的集合定义为：$Y^X=\{f|f:X\rightarrow Y\}$

注：空集到任何集合$Y$上都有一个空函数$\emptyset_{Y}$，所以对任何集合$Y$，$Y^{\emptyset}=\{\emptyset_{Y}\}$，但没有$X$到空集的函数，所以对任何集合$X$，$\emptyset^{X}=\emptyset$

定义：函数$i\mapsto X_i,i\in I$，每一$X_i$都是集合。这种函数称为集合的指标系统，$I$称为指标集，指标系统写作$X=\{X_i|i\in I\}$或$\{X_i\}_{i\in I}$

指标系统的一些性质：

（1）假设$\mathcal {F}=\{F_i\}_{i\in I}$是指标系统，则

$$\bigcup_{i=I}F_i=\bigcup\mathcal {F},\bigcap_{i=I}F_i=\bigcap\mathcal {F};$$

（2）指标集有时可以是二维的，即$I\times J$。这时规定

$$\bigcap_{i=I,j\in J}F_{ij}=\bigcap_{(i,j)\in I\times J}F_{ij},\bigcup_{i=I,j\in J}F_{ij}=\bigcap_{(i,j)\in I\times J}F_{ij};$$

（3）对任意公式

$$\bigcup_{i=I}\{x\in X|\psi(i,x)\}=\{x\in X|\exists i\in I(\psi(i,x))\},\\\bigcap_{i=I}\{x\in X|\psi(i,x)\}=\{x\in X|\forall i\in I(\psi(i,x))\}$$

定义：$X$是指标系统，则$X$的一般卡氏积为：

$$\prod_{i\in I} X_i=\{f|f是I上的函数并对任意i\in I,f(i)\in X_i\}$$

（可以用来”表达一个函数的坐标系统“不只一种…）

对任意$i\in I$，由$p_i(f)=f(i)$定义的函数$p_i:\prod_{i\in I}X_i\rightarrow X_i$称为投射函数

选择公理（第二形式）：对任意不含空集的非空集合族$\mathcal {F}$上都存在选择函数，即存在函数$f：\mathcal {F}\rightarrow \cup \mathcal {F}$满足：对任意$F\in\mathcal {F},f(F)\in F$

2.3 等价与划分

定义： 令$R\subseteq X^2$为二元关系，则

（1）$R$是自反的当且仅当对所有的$x\in X$，$R(x,x)$

（2）$R$是对称的当且仅当对所有的$x,y\in X$，如果$R(x,y)$，则$R(y,x)$

（3）$R$的传递的当且仅当对所有的$x,y,z\in X$，如果$R(x,y)$，且$R(y,z)$，则$R(x,z)$

（4）$R$是等价的当且仅当$R$是自反、对称、传递的，用$\sim$表示

练习：对任意集合$X$，如果$\mathcal {I}\subseteq \mathcal {P}(X)$并满足：（1）$\emptyset \in \mathcal {I}$（2）$A\subseteq B , B\in \mathcal {I}\rightarrow A\in \mathcal{I}$（3）$A,B\in \mathcal {I}\rightarrow A\cap B\in \mathcal{I}$，就称$\mathcal {I}$是$X$上的理想，则其上的二元关系：

$$R=\{(A,B)\in \mathcal{P}(\mathcal{I})\times \mathcal{P}(\mathcal{I})|(A\Delta B)\in \mathcal{I}\}$$

是等价关系，请证明之

1.证明自反性

即对所有的$A\in \mathcal{P}(\mathcal{I}),R(A,A)$

$A\subseteq A , A\in \mathcal {I}\rightarrow A\in \mathcal{I}$成立

$A\in \mathcal {I}\rightarrow A\cap A\in \mathcal{I}$成立

自反性成立

2.证明对称性

假如对$A,B\in \mathcal{P}(\mathcal{I}),R(A,B)$

有$A\subseteq B , B\in \mathcal {I}\rightarrow A\in \mathcal{I}$，

$A,B\in \mathcal {I}\rightarrow A\cap B\in \mathcal{I}$

那么也有$B\subseteq A ， A\in \mathcal {I}\rightarrow B\in \mathcal{I}$

$B,A\in \mathcal {I}\rightarrow B\cap A\in \mathcal{I}$

对称性成立

3.证明传递性

假如对$A,B,C\in\mathcal{P}(\mathcal{I}),R(A,B),P(B,C)$

有$A\subseteq B , B\in \mathcal {I}\rightarrow A\in \mathcal{I}$，$A,B\in \mathcal {I}\rightarrow A\cap B\in \mathcal{I}$；

$B\subseteq C , C\in \mathcal {I}\rightarrow B\in \mathcal{I}$，$B,C\in \mathcal {I}\rightarrow B\cap C\in \mathcal{I}$

由于包含关系的性质：$A\subseteq B,B\subseteq C\rightarrow A\subseteq C$，且$A,C\in \mathcal {I}$

所以有$A\subseteq C , C\in \mathcal {I}\rightarrow A\in \mathcal{I}$

又因为$A,C\in \mathcal{I}$

所以$A\cap C\in\mathcal{I}$，

所以有$A,C\in \mathcal {I}\rightarrow A\cap C\in \mathcal{I}$

传递性成立

定义：$\sim$是$X$上的等价关系，$x\in X$，$x$关于$\sim$的等价类指的是集合

$$[x]_{\sim}=\{t\in X|t\sim x\}$$

注：其实等价类都是集合，不是真类

练习：令$\sim$为$X$上的等价关系，则对任意$x,y\in X,[x]_{\sim}=[y]_{\sim}$或者$[x]_{\sim}\cap[y]_{\sim}=\emptyset$

定义：令$X$为一集合，$S\subseteq \mathcal{P}(X)$。如果$S$满足

（1）对所有的$a,b\in S$，如果$a\ne b$，则$a\cap b=\emptyset$

（2）$\bigcup S=X$

则称$S$是$X$的划分

定义：令$\sim$为$X$上的等价关系，则$X/\sim=\{[x]_{\sim}|x\in X\}$称为$X$的商集

定理：$X$的商集是$X$的划分

2.4 序

定义：令$\leq$为$X$上的二元关系，如果$\leq$满足：

（1）$\leq$是自反的

（2）$\leq$是反对称的，即$x,y\in X$，如果$x\leq y且y\leq x$，则$x=y$

（3）$\leq$是传递的

就称$\leq$是$X$上的偏序或序

（4）$\leq$是连接的，即对所有的$x,y\in X$，如果$x\leq y$或$y\leq x$

就称$\leq$是$X$上的线序或全序

记法：$(X,\leq)$ $\leq$是$X$上的偏序，$X$是偏序集

定义：令$\leq$是$X$上的偏序

极小元：如果$a\in X$，且对任意$x\in X$，有$\forall x\in X(\neg (a> x))$，则$a$为$X$的极小元

极大元：如果$a\in X$，且对任意$x\in X$，有$\forall x\in X(\neg (a< x))$，则$a$为$X$的极大元

---

最小元：如果$a\in X$，且对任意$x\in X$，有$\forall x\in X(\neg (a\geq x))$，则$a$为$X$的最小元

最大元：如果$a\in X$，且对任意$x\in X$，有$\forall x\in X(\neg (a\leq x))$，则$a$为$X$的最大元

---

上界：如果$X_0\subseteq X$，且存在$a\in X$使得对任意$x\in X_0$，都有$a\geq x$，则称$a$为$X_0$在$X$中的上界

上确界：如果$X_0$在$X$中所有上界的集合有最小元$a_0$，$a_0$是$X_0$的上确界$(sup(X_0))$

---

下界：如果$X_0\subseteq X$，且存在$a\in X$使得对任意$x\in X_0$，都有$a\leq x$，则称$a$为$X_0$在$X$中的下界

下确界：如果$X_0$在$X$中所有下界的集合有最小元$a_0$，$a_0$是$X_0$的下确界$(inf(X_0))$

注：对于线序集而言，极小元与最小元、极大元与最大元是等价的

偏序集的最大最小元是唯一的（如果有的话）

上（下）确界不一定属于$X_0$，若属于，就是它的最大（小）元

习题

1、证明：令$R$为二元关系，$A=\cup(\cup R)$。证明如果$(x,y)\in R$则$x\in A$且$y\in A$

$(x,y)\in R$，$\{\{x\},\{x,y\}\}\in R$

因为$A=\cup(\cup R)$

$\{\{x\},\{x,y\}\}\subseteq\cup R$

$\{x,y\}\subseteq\cup(\cup R)$

所以$x,y$是$A$中的元素

所以$x\in A$且$y\in A$

2、证明如果函数$f$是可逆的，则$f^{-1}\circ f=id_{dom(f)}$，$f\circ f^{-1}=id_{ran(f)}$。$(id_{A}=集合A上的恒等映射，对任意集合A，如果映射f:A→A定义为f(a)=a，\\即规定A中每个元素a与自身对应，则称f为A上的恒等映射)$

函数的逆的定义：$f^{-1}=\{(x,y)|(y,x)\in f\}$

$g=f^{-1}\circ f=\{(x,z)|\exists y((x,y)\in f\wedge(y,z)\in f^{-1})\}=\{(x,z)|\exists y((y,x)\in f^{-1}\wedge(y,z)\in f^{-1})\}$

由函数定义，$x=z$

所以$g(x)=x$，又因为$g$的定义域为$dom(f)$（好像证过了）

所以$f^{-1}\circ f=id_{dom(f)}$

$h=f\circ f^{-1}=\{(x,z)|\exists y((x,y)\in f^{-1}\wedge(y,z)\in f)\}=\{(x,z)|\exists y((x,y)\in f^{-1}\wedge(z,y)\in f^{-1})\}$

由函数定义，$x=z$

所以$h(x)=x$，又因为$h$的定义域为$ran(f)$（也证过了）

所以$f\circ f^{-1}=id_{ran(f)}$

3、证明：令S为非空集合的非空族，$\{X_a\}_{a\in\cup S}$为以$\cup S$为指标集的指标系统，则

$$\bigcup_{a\in \cup S} X_a=\bigcup_{C\in S}(\bigcup_{a\in C}X_a),\bigcap_{a\in \cup S} X_a=\bigcap_{C\in S}(\bigcap_{a\in C}X_a)$$

由指标系统的性质：$\bigcup_{a\in \cup S}X_a=\bigcup\{X_a\}_{a\in\cup S},\bigcap_{a\in \cup S}X_a=\bigcap\{X_a\}_{a\in\cup S};$

即证$\bigcup\{X_a\}_{a\in\cup S}=\bigcup_{C\in S}(\bigcup_{a\in C}X_a),\bigcap\{X_a\}_{a\in\cup S}=\bigcap_{C\in S}(\bigcap_{a\in C}X_a)$

由并集公理，前者等价

由任意交的定义，后者等价

4、证明对于线序集而言，它的极小（大）元就是最小（大）元

线序集与偏序集相比，多了一个连接性，即它的任何两个元素都是可比的，这意味着“不大于”就是“小于或等于”，“不小于”就是“大于或等于”，因此对于线序集而言，它的极小（大）元就是最小（大）元。

5、令$\mathcal{F}=\{X\in \mathbb{N}|X是有穷的\}$，找出$(\mathcal{F},\subseteq)$的最小、最大、极小、极大元

极小元：所有的单元素集合与空集

没有极大元

最小元：空集

没有最大元