偏序、全序和良序关系

偏序、全序和良序关系

虽然 us 都不是搞数学的,然而总是时不时地会遇到这些说法,比如今天看曾经写的一篇Go的内存模型的时候就又遇到了“偏序关系”这种说法。通常比较抽象的关系,me 们会用某种数学或是生活中的数量关系来类比说明,比如自然数的 $$ \leqslant $$ (小于等于)关系,比如一个家庭族谱中的“晚辈-长辈”关系。

“关系” (relation) R 通常说的是二元关系,就是两个元素(不管是数,还是人,或是其他东西啦) a 、b 之间的关系。在计算机科学中 (a,b)∈ R 或是 aRb 说明 a 和 b 满足关系 R,比如“张三是李四的爸爸” (这肿么可能 ? O__O"…) ;而 (a,b) ∉ R 说明 a、b 不满足关系 R,比如“张三不是王五的爸爸”。R 视作满足关系的所有这样的序偶 (a,b) 的集合,所以前面用了 ∈ 和 ∉ 这种记法。

关系 R 一般满足一定的性质,比如“城市之间的可达”关系 R,城市 A 可以到 B,城市 B 可以到 C,那么城市 A 就是可以到 C 的,这种关系叫传递性。城市 A 可以到 B,那么城市 B 就可以到 A,这种关系叫对称性。张三是李四的爸爸,那么李四就不是张三的爸爸,这种关系叫反对称性(反对称性不否定自身对自身的情况,也就是 (a,a) ∈ R 这不违反反对称性;它只是用来否定两个不同的对象不能同时有 aRb 和 bRa。)。每个三角形都和自己相似,这种关系叫自反性。说一个关系 R 满足某个性质,不是说只要有 (a,b) 满足上面的说法就可以了,而是所有的情况都必须满足。比如城市 A 可以到 B,城市 B 也是可以到 A 的;而 A 可以到 C,C 却不能到 A,那么这种“可达”关系既不满足对称性,也不满足反对称性。

偏序关系

偏序关系 $$ \preccurlyeq $$ 可以使用数学中的小于等于 $$ \leqslant $$ 作类比。

    在集合 S 上满足下面三个性质的关系 R 是偏序关系:
  1. 自反性 : aRa ;
  2. 反对称性 : 如果 aRb 且 bRa ,那么 a = b ;
  3. 传递性 : 如果 aRb 且 bRc ,那么 aRc ;

偏序关系实际上不完全等价于 $$ \leqslant $$ (小于等于)关系,因为在自然数中任意两个自然数都可以比较这种关系,而偏序关系却没有要求“任意两个元素均可以比较”,所以,偏序关系更多的像是“长辈”关系(假设自己都是自己的长辈),它们满足上面三个性质,但是并不是任意两个人都有“长辈”关系

全序关系

全序关系首先是一种偏序关系,而且可以和数学中的小于等于 $$ \leqslant $$ 作完全类比。

    在集合 S 上满足下面三个性质的关系 R 是全序关系:
  1. 反对称性 : 如果 aRb 且 bRa ,那么 a = b ;
  2. 传递性 : 如果 aRb 且 bRc ,那么 aRc ;
  3. 完全性 : aRb 或是 bRa ;

根据完全性可以推出一定有 aRa ,所以全序关系是偏序关系。而根据完全性又知,“任意两个元素均是可以比较的”,所以它是一种特殊的偏序关系。实数 R 的“小于等于”关系正好就是这种关系的一个体现。自然数可以比较大小,R 也可以比较大小,然而自然数有最小值,而 R 没有最小值。所以针对自然数这种“总是会有最小值”的特定性质再加上限制,便成了“全序”关系。

良序关系

良序关系首先是一种全序关系,当然也是一种偏序关系了;其可以和自然数的小于等于 $$ \leqslant $$ 作完全类比

    在集合 S 上满足下面性质的关系 R 是偏序关系:
  1. R 是一个全序关系;
  2. S 的任意集合均有针对 R 的最小元素;

“任意一个自然数集合都有最小值”,但是不是任意实数上的集合都有最小值,比如 R 就没有。良序关系在全序基础上强调了最小元素的存在性。

良序集

可以找到一个良序关系的集合就是良序集,于是,自然数是良序集

整数和有理数乍眼一看,不是良序集,因为整数集 Z 是没有最小元素的。但是如果思考,整数集 Z 和有理数集 Q 都是可数的,也就是可以像自然数一样“一一排列”出来,那么如果将这种排列的先后作为“大小”顺序的话,整数 Z 和 有理数 Q 也都是良序集了

实际上,可数集合都是良序集,可数集合从可数的角度来看,它们都是等价的集合。

Tags: 

Article type: