2010年9月14日星期二

全序集的本质

上次在和同事讨论问题的时候发现,偏序集不能排序。后来我就很好奇为什么不能,可以排序的集合上应该至少定义一个满足什么条件的二元关系?
先回顾一下偏序集和全序集的定义:

给定集合S,“≤”是S上的二元关系,若“≤”满足:

   1. 自反性:∀a∈S,有a≤a;
   2. 反对称性:∀a,b∈S,a≤b且b≤a,则a=b;
   3. 传递性:∀a,b,c∈S,a≤b且b≤c,则a≤c;

则称“≤”是S上的非严格偏序或自反偏序。通常简称偏序

给定集合S,“≤”是S上的二元关系,若“≤”满足:
   1. 完全性 a ≤ b 或 b ≤ a
   2. 反对称性 如果 a ≤ b 且 b ≤ a 则 a = b
   3. 传递性如果 a ≤ b 且 b ≤ c 则 a ≤ c

则称“≤”是S上的全序

显然完全性蕴含了自反性,因此全序都是偏序。

命题1:如果“≤”集合S上的偏序,且满足4. 反向传递性:∀a,b,c∈S,a≤b不成立且b≤c不成立,则a≤c不成立”,那么“≤”集合S上的全序

证明:只需要证明“≤” 具有完全性。假设a ≤ b 或 b ≤ a 不成立,即a≤b不成立且b≤a不成立,由反向传递性,a≤a不成立,与自反性矛盾。

命题2:如果“≤”集合S上的全序,那么“≤” 满足反向传递性

证明:假设a≤b不成立且b≤c不成立由完全性,“a≤b不成立”蕴含了“b ≤ a ,“b≤c不成立”蕴含了“c≤b。再由传递性,ca。假设a≤c ,则由反对称性,得a=c。a≤b不成立,即c≤b不成立,而b≤c也不成立,与完全性矛盾。

结合上述命题,可知:一个偏序集合是全序集合,当且仅当具有反向传递性。也就是说,反向传递性在某种程度上是全序集合的本质。

经典排序算法中,如何隐含地使用了指定序的反向传递性来保证算法正确性呢?

注意到,排序算法总是要求传入一个"<",但是保证的是数组按照""排好序。其中ab定义为b<a不成立。
以快速排序算法为例,假设pivot为b,所有<b的元素放在b的左边,其他元素放在b的右边,不失一般性(递归地),只需证明"b左边的任一元素a""b右边的任一元素c"。

假设存在a和c,使得ac不成立。由a在b的左边,知a<b成立,即ba不成立。由反向传递性,bc不成立,即c<b,这与c在b的右边矛盾。























没有评论: