这一节主要是各种定义:
(1)集合$X$中的关系$R$称为是反对称的(antisymmetric),如果$xRy$,$yRx$同时成立,必有$x=y$.
(2)关系$R$称为偏序(partial order),如果关系$R$满足自反的(reflexive),反对称的(antisymmetric),传递的(transitive),此时通常使用符号$\le$.$\forall x,y,z \in X$,(i)$x \le x$;(ii)若$x \le y$,$y \le x$,必有$x=y$;(iii)若$x \le y$,$y \le z$,则$x \le z$.
这里之所以使用偏序,是因为有可能在$X$中存在元素$x$,$y$,无法确定序关系,如果对于$X$中的每一个元素$x$和$y$,或者$x \le y$,或者$y \le x$,则称$\le$为全序(total order, simple order, linear order).一个全序集常称为链(chain).
偏序集是指带有偏序关系的集合,记作$(X, \le)$.类似的,全序集是指带有全序关系的集合.
(3)对于$X$中的偏序$\le$,我们称$y \ge x$,如果$x \le y$;$x < y$或者$y>x$,如果$x \le y$,且$x \neq y$,称$x$是predecessor of $y$,$y$是successor of $x$.
对于关系$<$,有(i)$x<y$和$y<x$不能同时成立;(ii)$x<y$,$y<z$,则有$x<z$,也就是$<$是传递的.
反过来,我们可以从$<$出发定义$\le$,如果关系$<$满足(i)和(ii),然后定义$x \le y$,如果$x<y$或者$x=y$,那么$\le$是一个偏序.
可以把$\le$和$<$的这种关系推广到一半的关系,对于关系$R$和$S$,满足$xSy$,如果$xRy$,且$x \neq y$,此时称$S$是strict relation corresponding $R$.$R$是weak relation corresponding $S$.
(4)对于偏序集$(X, \le)$,$a \in X$,集合$s(a)=\{x \in X: x < a\}$,称为the initial segment determined by $a$,$\bar{s}(a)=\{x \in X: x \le a\}$称为the weak initial segment determined by $a$.
(5)若$x \le y$,$y \le z$,称$y$位于$x$和$z$之间(between $x$ and $z$),若$x<y$,$y<z$,称$y$是严格位于$x$和$z$之间(strictly between $x$ and $z$).若$x<y$,并且不存在元素严格位于$x$和$y$之间,称$x$是immediate predecessor of $y$,或者说$y$是immediate successor of $x$.
(6)$X$为偏序集,若存在$a \in X$,使得$a \le x$,$\forall x \in X$,则称$a$为least (first,smallest) element of $X$,从反对称性可知这个元素是唯一的,类似,若存在元素$a \in X$,使得$x \le a$,$\forall x \in X$,称$a$为greatest (last, largest) element of $X$.对于自然数集,按照通常的次序,$0$是first element,而不存在last element,如果把次序颠倒过来,那么$0$是last element,而不存在first element.
(7)对于偏序集$X$,$a \in X$称为minimal element,如果不存在$X$中的元素严格小于$a$ (strictly smaller than $a$),也就是从$x \le a$,将得到$x=a$;类似的,如果不存在元素严格大于$a$,称$a$为maximal element,于是从$a \le x$,必有$x=a$.
必须注意least element和minimal element是有差别的,非空集合$X$的非空子集构成的集合$\mathscr{C}$,以包含关系作为偏序关系,此时每个单元素集合是minimal的,但是$\mathscr{C}$中一般情况下不存在least element,除非$X$中只有一个元素.
(8)$X$为偏序集,$a \in X$,$E \subset X$,称$a$为$E$的下界(lower bound),若$\forall x \in E$,$a \le x$;称$a$为$E$的上界$upper bound$,若$\forall x \in E$,$x \le a$.注意,$E$中可以不存在上界或下界,也可以有多个上界或下界.后一种情况可以以自然数集作例子,$n$为$E$的上界,那么所有大于$n$的自然数都是$E$的上界.引入两个记号:
\[\begin{aligned}
E_*&=\{a \in X:\forall x \in E, a \le x\} \\
E^*&=\{a \in X:\forall x \in E, x \le a\}
\end{aligned}\]
$E_*$以及$E_* \cap E$都可能是$\emptyset$,如果$E_* \cap E \neq \emptyset$,此时它必然只有一个元素.对于$E_*$来说,如果存在一个greatest element $a$,则称$a$为$E$的下确界(greatest lower bound或者infimum),记作g.l.b.或inf,类似,若$E^*$中包含一个least element $a$,则称$a$为$E$的上确界(least upper bound或supremum),记作l.u.b.或者sup.
下面给出几个例子:
(1)作为偏序的第一个例子,自然就是集合的包含关系,它是$P(X)$上的偏序,仅当$X$是单元素集的时候是全序.
(2)全序的例子可以在自然数集中得到,
(3)另一个偏序的例子是映射的扩张,给定集合$X$和$Y$,$F$为所有定义域在$X$中而值域在$Y$中的映射组成的集合.定义$F$上的关系$R$如下:$fRg$如果$\text{dom}{f} \subset \text{dom}{g}$,且$f(x)=g(x)$,$\forall x \in \text{dom}{f}$.也就是这意味着$f$是$g$的限制,而$g$是$f$的扩张.如果注意到映射是$X \times Y$的子集,那么$fRg$实际上就是$f \subset g$.
(4)对于集合$\omega \times \omega$,我们可以定义不同的偏序:(i)$(a,b)R(x,y)$,如果$(2a+1)\cdot 2^y \le (2x+1) \cdot 2^b$,(ii)$(a,b)S(x,y)$,如果$a<x$,或者$a=x$且$b \le y$;这个次序称为字典序(lexicographical order).(iii)$(a,b)T(x,y)$,如果$a \le x$且$b \le y$.
习题:使用$R$以及逆来表述关系$R$的反对称性和totality.
$RR^{-1} \subset I$,$R = E \times E$.