半序集解析

本文概述

  • POSET的要素
  • 可比元素
  • 不可比元素
  • 线性有序集
考虑满足以下属性的集合S上的关系R:
  1. R是自反的, 即每x∈S有xRx。
  2. R是反对称的, 即如果xRy和yRx, 则x = y。
  3. R是可传递的, 即xRy和yRz, 然后是xRz。
然后, R被称为偏序关系, 集合S与偏序一起被称为偏序集或POSET, 并由(S, ≤)表示。
例:
  1. 自然数的集合N在关系“ ≤” 下形成一个球状体, 因为首先x≤x, 其次, 如果x≤y和y≤x, 则我们有x = y, 最后如果x≤y和y≤z, 则对所有x, y, z∈N暗示x≤z。
  2. 在除数下的自然数集N(即“ x除以y” )形成了一个位姿, 因为每个x∈N都有x / x。同样如果x / y和y / x, 则x = y。同样, 如果x / y, y / z为每个x, y, z∈N, 则我们有x / z。
  3. 考虑集合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的要素
  1. 最大元素:如果a中c中没有元素使得a≤c, 则元素∈A称为A的最大元素。
  2. 最小元素:如果在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 +的集合是线性有序集合。

    推荐阅读