半序集解析半序集|离散数学

本文概述

POSET的要素
可比元素
不可比元素
线性有序集

考虑满足以下属性的集合S上的关系R：

R是自反的, 即每x∈S有xRx。
R是反对称的, 即如果xRy和yRx, 则x = y。
R是可传递的, 即xRy和yRz, 然后是xRz。

然后, R被称为偏序关系, 集合S与偏序一起被称为偏序集或POSET, 并由（S, ≤）表示。
例：

自然数的集合N在关系“ ≤” 下形成一个球状体, 因为首先x≤x, 其次, 如果x≤y和y≤x, 则我们有x = y, 最后如果x≤y和y≤z, 则对所有x, y, z∈N暗示x≤z。
在除数下的自然数集N（即“ x除以y” ）形成了一个位姿, 因为每个x∈N都有x / x。同样如果x / y和y / x, 则x = y。同样, 如果x / y, y / z为每个x, y, z∈N, 则我们有x / z。
考虑集合S = {1, 2}, S的幂集为P（S）。集合包含inclusion的关系是偏序。因为对于（P）中的任何集合A, B, C, 首先我们有A?A, 其次, 如果A?B和B?A, 则我们有A =B。最后, 如果A?B和B? C, 然后A?C。因此, （P（S）, ?）是一个姿态。

POSET的要素

最大元素：如果a中c中没有元素使得a≤c, 则元素∈A称为A的最大元素。
最小元素：如果在c中没有元素使得c≤b, 则元素b∈A称为A的最小元素。

注意：可以有一个以上的最大元素或一个以上的最小元素。示例：确定其Hasse图如图所示的位姿的所有最大和最小元素：

【半序集解析】解决方案：最大元素是b和f。
最小元素是d和e。
可比元素考虑一个有序集合A。如果满足以下条件, 则将集合A的两个元素a和b称为可比较元素
a≤b或b≤a R R
不可比元素考虑一个有序的集合A。如果a≤b或b≤a都不叫集合A的两个元素a和b。
示例：考虑A = {1、2、3、5、6、10、15、30}按除数排序。确定A的所有可比较和不可比较的元素对。
解决方案：A的可比较元素对是：{1、2}, {1、3}, {1、5}, {1、6}, {1、10}, {1、15}, {1, 30} {2, 6}, {2, 10}, {2, 30} {3, 6}, {3, 15}, {3, 30} {5, 10}, {5, 15}, {5 , 30} {6, 30}, {10, 30}, {15, 30}
A的不可比较元素对是：{2, 3}, {2, 5}, {2, 15} {3, 5}, {3, 10}, {5, 6}, {6, 10 }, {6、15}, {10、15}
线性有序集考虑一个有序集合A。如果A中的每对元素都是可比较的, 则集合A称为线性有序集合或全有序集合。
示例：通常整数≤的正整数I +的集合是线性有序集合。