链与反链
定义：设<A,≤>是一个偏序集，BA，（1）若xy(x∈B∧y∈B→x≤y∨y≤x)，则称B为A上的链，B中的元素个数称为链B的长度。（2）若xy(x∈B∧y∈B→(x≤y∨y≤x))，则称B为A上的反链，B中的元素个数称为反链B的长度。规定：若B只含有一个元素，则B既是链又是反链。
第1页，共46页。
例：A={2,3,4,6,9,12,18}，A上的整除关系。
其Hasse图如下图，则{2,4,12}, {3,6,18}, {3,9}, {18}等为A上的链；{4,6,9}, {12,18} {2,3}, {18}等为A 上的反链。结论：若<A, ≤>是全序关系，则A是链，且A的任何子集是链。
第2页，共46页。
证明：先证明定义域、陪域相等。其Hasse图如下图，则显然， g f≠ fg，即复合运算不满足交换律。则R和S的复合关系记作R S 。任取 x,y∈A,设<x,y>∈R, 证出 <y,x>∈R.可见fIX、IYf 与 f 具有相同的定义域和陪域。由（1）、（2）得gf是X到Z的函数。因R对称的故<b,a>R,又已知<a,c>R 由传递 ...