等价、偏序和全序

等价、偏序和全序

引用

CSDN

1.

https://blog.csdn.net/lanchunhui/article/details/52220983

在数学和计算机科学中，等价关系、偏序关系和全序关系是三个重要的概念。它们不仅在理论研究中占据重要地位，而且在实际应用中也发挥着关键作用。本文将详细解释这些概念的定义、性质和具体例子，帮助读者建立清晰的理解。

1. 等价关系

设R是某个集合A上的一个二元关系。若R满足以下条件：

• 自反性：对于所有a∈A，有aRa
• 对称性：对于所有a,b∈A，如果aRb，则bRa
• 传递性：对于所有a,b,c∈A，如果aRb且bRc，则aRc

称R是一个定义在A上的等价关系。习惯上会把等价关系的符号由R改写为∼。

例如，设A={0,1,2,3,4,5}，定义A上的关系R如下：
xRy当且仅当x与y模3同余，即x除以3的余数与y除以3的余数相等。例子有0R3，1R4，2R5（R在形式上不包含3，但在实际含义上，却有对3取模的意思）。不难验证R为A上的等价关系（三个性质的验证）。

不是所有的二元关系也是等价关系。一个简单的反例子是比较两个数中哪个较大：

• 没有自反性：任何一个数不能比自身为较大（a≤a）
• 没有对称性：如果a≤b，就肯定不能有b≤a

2. 偏序关系

设A是一个非空集，P是A上的一个关系，若关系P是自反的、反对称的、和传递的，则称P是集合A上的偏序关系。即P适合下列条件：

• （1）对任意的a∈A，(a,a)∈P;
• （2）若（a,b)∈P且（b,a)∈P，则a=b;
• （3）若（a,b)∈P，(b,c)∈P，则（a,c)∈P,
  则称P是A上的一个偏序关系。

带偏序关系的集合A称为偏序集或半序集。若P是A上的一个偏序关系，我们用a≤b来表示（a,b)∈P。

举如下例子说明偏序关系：

• 1、实数集上的小于等于关系是一个偏序关系。
• 2、设S是集合，P（S）是S的所有子集构成的集合，定义P（S）中两个元素A≤B当且仅当A是B的子集，即A包含于B，则P（S）在这个关系下成为偏序集。
• 3、设N是正整数集，定义m≤n当且仅当m能整除n，不难验证这是一个偏序关系。注意它不同于N上的自然序关系。

偏序是在集合P上的二元关系（≤），它是自反的、反对称的、和传递的，就是说，对于所有P中的a, b和c，有着:

• a≤a（自反性）；
• 如果a≤b且b≤a则a=b（反对称性）；
• 如果a≤b且b≤c则a≤c（传递性）。

3. 全序关系

在集合中，如果对于任意a,b∈A，有a≤b或b≤a，即A中的每对元素（任意两个元素之间都存在关系，而偏序要求的仅是存在关系的两者之间需要满足的性质）都满足关系，则集合A上的偏序R是全序的或线性序的。

全序集是任意两个元素都可以比较的偏序集。序的存在可对应一些特殊的物理意义，比如时间上的先后关系。

4. 良序集

良序集（well order）是任意非空子集都有最小元的全序集。

5. 举例

下图两幅有向图：

边表示（从x指向y），

• 左图表示偏序，a和b不存在关系；
• 右图正是加上了一条指向的边，才成为正序；