第一章练习题

1．设$(X,\preceq)$是偏序集，$A\subseteq X$，证明$\preceq_{A}=(A\times A)\cap\preceq$是$A$上的一个偏序．

证明. 反身性。对任意的$x\in A$，因$(x,x)\in A\times A$，且$(x,x)\in\preceq$，所以有$(x,x)\in(A\times A)\cap\preceq$，即$\preceq_{A}$具有反身性。

传递性。任取$(x,y)\in\preceq_{A}以及(y,z)\in\preceq_{A}$，则因$(x,y),(y,z)\in\preceq$，根据$\preceq$的传递性可知$(x,z)\in\preceq$。另一方面，显然有$(x,z)\in A\times A$，所以有$(x,z)\in(A\times A)\cap\preceq$，即$\preceq_{A}$具有传递性。

反对称性。如果$(x,y),(y,x)\in\preceq_{A}$，则$(x,y),(y,x)\in\preceq$。由于$\preceq$具有反对称性，所以必须有$x=y$，因此$\preceq_{A}$具有反对称性。

2．设$\preceq$是$X$上的一个偏序，证明$\preceq^{-1}=\{(x,y)\vert(y,x)\in\preceq\}$也是一个偏序．

证明. 任取$x\in X$，则由$\preceq$的反身性可知$(x,x)\in\preceq$，再由$\preceq^{-1}$的定义可知$(x,x)\in\preceq^{-1}$。

如果$(x,y),(y,z)\in\preceq^{-1}$，则有$(z,y),(y,x)\in\preceq$。由$\preceq$的传递性可知有$(z,x)\in\preceq$。再由$\preceq^{-1}$的定义可知$(x,z)\in\preceq^{-1}$。

设$(x,y),(y,x)\in\preceq^{-1}$，则$(x,y),(y,x)\in\preceq$。由$\preceq$的反对称性可知$x=y$。

3．设$(X_{i},\preceq_{i})$，$i=1,2$是两个非空偏序集，$\preceq是X=X_{1}\times X_{2}$上的关系，定义如下:
$$(x_{1},x_{2})\preceq(y_{1},y_{2})\Leftrightarrow x_{1}\preceq_{1}y_{1},x_{2}\preceq_{2}y_{2},$$证明$\preceq$是$X$上的一个偏序关系．

证明. 任取$(x_{1},x_{2})\in X_{1}\times X_{2}$，则有$x_{1}\preceq_{1}x_{1}，x_{2}\preceq_{2}x_{2}$，于是有$(x_{1},x_{2})\preceq(x_{1},x_{2})$。

设$(x_{1},x_{2})\preceq(y_{1},y_{2})，(y_{1},y_{2})\preceq(z_{1},z_{2})$，则由$\preceq$的定义可知$x_{1}\preceq_{1}y_{1}$且$y_{1}\preceq_{1}z_{1}$，于是$x_{1}\preceq z_{1}$。同理可证$x_{2}\preceq z_{2}$。再由$\preceq$的定义可知$(x_{1},x_{2})\preceq(z_{1},z_{2})$。

如果$(x_{1},x_{2})\preceq(y_{1},y_{2})$，$(y_{1},y_{2})\preceq(x_{1},x_{2})$，则由$\preceq$的定义可知$x_{1}\preceq_{1}y_{1}$且$y_{1}\preceq_{1}x_{1}$，于是由$\preceq_{1}$的反对称性可知$x_{1}=z_{1}$。同理可证$x_{2}=z_{2}$。因此有$(x_{1},x_{2})=(z_{1},z_{2})$。

4．举例说明保序的双射不必是序同构．

证明. 设$X=\{1,2,3\}$，$R=\left\{ (1,1),(2,2),(3,3),(1,2),(2,3),(1,3)\right\}$ ，$R'=\left\{ (1,1),(2,2),(3,3),(1,2)\right\}$ ，令$f:(X,R')\to(X,R)$为恒等映射，则$f$是一一保序的，但$f^{-1}$却不是保序的．

5．对任意的映射$f:X\to Y$可诱导一个映射$f_{*}:\mathcal{P}X\to\mathcal{P}Y，A\mapsto f_{*}(A)=\left\{ f(x)|x\in A\right\}$ ．证明集合包含偏序$f_{*}$保序，保上确界，$f_{*}^{-1}:\mathcal{P}Y\to\mathcal{P}X$保上、下确界．

证明. 运用命题1.1.6。

6．偏序集$(X,\preceq)$的每个子集有上确界$\Leftrightarrow X$的每个有限子集和定向子集有上确界．

证明. 必要性显然，下证充分性。

设$X$的每个有限子集和定向子集有上确界，则空集作为$X$的有限子集有上确界．对$X$的任意非空子集$A$，我们要证明$A$有上确界。因为$X$的任何有限子集有上确界，从而$X$的任何子集都是定向集，因此$A^{\ast}=\{\sup F\vert F\subseteq A是有限子集\}$是$X$的定向子集。下面证明$\sup A^{\ast}=\sup A$．事实上，由$A\subseteq A^{\ast}$，$\sup A^{\ast}$是$A$的一个上界．显然$A$的任意上界$b$都是$A^{\ast}$的上界，因此$\sup A^{\ast}\preceq b$，$\sup A=\sup A^{\ast}$．

7．证明Bernstein定理：如果存在从集$A$到集$B$的单射和从集$B$到集$A$的单射,则存在从$A$到$B$的一一映射．

证明. 设$f$是从$A$到$B$内的一一映射，并且$g$是从$B$到$A$内的一一映射．可以假设$A$与$B$互不相交．这个定理的证明是用把$A$与$B$分解的方法完成的，而它最容易用单性生殖的术语来描述．点$x$(属于$A$或者$B$)为点$y$的祖先当且仅当$y$能够由$x$依次通过$f$与$g$(或者$g$与$f$)的作用而得到．现把$A$分成三个集：令$A_{E}$表$A$中有偶数个祖先的点组成之集，令$A_{0}$表有奇数个祖先的点组成之集，并令$A_{l}$表有无限多个祖先的点组成的集合．类似地分解$B$，同时注意：$f$映$A_{E}$到$B_{0}$上,$A_{l}$到$B_{l}$上，又$g^{-1}$映$A_{0}$到$B_{E}$上．故在$A_{E}\cup A_{l}$上与$f$相一致并在$A_{0}$上与$g^{-1}$相一致的函数就是$A$到$B$上的一一映射．