偏序集的完备性.md

偏序集$(A,\le)$称为完备的，如果

$A$有最小元，常记为$\perp_A$或$\perp$
$A$中的每一个全序集$K$均有最小上界（上确界）

例如，设$B$为一个集合，那么$(\rho(B),\subseteq)$为一完备的偏序集，其中$\emptyset$为最小元，对每一个链$\{b_1,b_2,b_3,\cdots\}=K$，$\cup K\subseteq B$总存在，$\cup K$为$K$的最小上界

定理：具有最小元，且仅含有穷链（全序集）的偏序集是完备的

证明：显然，有穷链必有最小上界，于是该偏序集所有链均有最小上界，又因为该偏序集有最小元，所以该偏序集是完备的

引理：每一个非空有穷偏序集$(A,\le)$都有极小元素

证明：选择$A$的一个元素$a_0$，如果它不是极小元素，那么存在元素$a_1$满足$a_1\le a_0$，如果$a_1$不是极小元素，那么存在元素$a_2$满足$a_2\le a_1$，如此下去，使得如果$a_n$不是极小元素，那么就存在元素$a_{n+1}$满足$a_{n+1}\le a_n$，由于此偏序集是有穷的，此过程一定结束，并且具有极小元素$a_n$

有了此引理就可以构造把偏序集改造为全序集的算法

算法：设$(A,\le)$为一非空有穷偏序集，如下构造$(A,\le')$，使之为全序集，且保持对任何$a,b\in A$有

若$a\le b$，则$a\le'b$

置$B$为$A$，置$A$为$\emptyset$
取$B$中任一极小元$x$（$B\ne\emptyset$时总存在）作为$A$的一个元素，即置$B$为$B-\{x\}，置A为A\cup\{x\}$
若$B\ne\emptyset$，转到(2)；否则停止
依据$A$中元素进入先后定义偏序关系$\le'$，即$a\le'b$当且仅当$a$先于$b$进入$A$，或$a=b$

显然$(A,\le')$为一全序集（从而为一良序集），上述过程常称为拓补排序算法，利用以上算法可以把任一有穷的偏序集改造为全序集，从而成为一良序集