2011年5月21日星期六

自反+反向传递=>完全

今天终于证明了这样一个定理:偏序是全序,当且仅当可反向传递。藉此可以理偏序和全序的本质差异。

回忆
偏序=传递+反对称+自反
全序=传递+反对称+完全

E是一个集合,≤是E上的一个二元关系,称
自反:a≤a,对于任意a∈E
完全:a≤b或b≤a,对于任意a, b∈E(显然完全蕴含自反)
反对称:若a≤b且b≤a,则a=b
反向传递:a≤b不成立且b≤c不成立,则a≤c也不成立,对于任意a, b, c∈E

求证,若≤自反和反向传递,则≤完全
证明:假设不然,即存在a, b∈E,使得a≤b不成立且b≤a不成立,则由反向传递,得a≤a不成立,与≤自反矛盾

求证:若≤完全、反对称、传递,则≤反向传递
证明:对于任意a, b∈E,若a≤b不成立且b≤c不成立,
由≤完全,有b≤a且c≤b,
由≤传递,有c≤a
假设a≤c成立,则
由≤反对称,有a=c,
代入b≤a且c≤b,得到b≤a≤b,
由≤b反对称,有a=b
代入a≤b不成立,得到a≤a不成立
与自反矛盾,故而假设不成立