有限半序集的结构分析和Dilworth定理的新证明

The Structure Analysis of Finite Poset and Several New Proofs of the Dilworth Theorem

中文摘要:

      在本文中我们讨论了有限半序集的结构分析,并给出了Dilworth定理的两种新证明。在(一)中我们对半序集引进了独立集(最大不可比集)的概念、度数的概念和顶集的概念。得到了关于半序集结构的分层定理(定理1),并应用顶集的性质对半序集的度数用归纳法给出了Dilworth定理的一种新的证明(定理2)。在(二)中根据半序集的独立集的不同情形,将半序集分成两种类型——A型和B型,证明了任何一个半序集均可表成有限个B型半序集的併(定理3),并据此给出了Dilworth定理的另一种新证明。在(三)中我们应用顶集的性质,对Dilworth的原证明给出了一种简化证明。

英文摘要:

      In this paper, we discuss the structure of finite poset and give two new proofs of the Dilworth theorem.In part Ⅰ, we first introduce the concepts of "independent set" (greatest uncomparable set), the "degree" of a poset and "top set". Then we obtain the "layer theorem of poset". By means of the properties of top set and by applying the method of induction to the degree of poset, we derive a new proof of the Dilworth theorem (theorem 2).In part Ⅱ, according to various different cases of the indepedent set of poset, we classify posets into two types named A-type and B-type, and prove that any poset can be expressed in unions of finite B-type posets, and from this result we give another new proof of the Dilworth theorem. In part Ⅲ. we use properties of top set to give a simplified proof of the original proof of the Dilworth theorem.