方向（序理论）

来自GSXAB的知识库
（重定向自上有向集）
方向
术语名称 方向
英语名称 direction
有向集
术语名称 有向集
英语名称 directed set
别名 滤过集, filtered set

方向(direction)指集合上的一个预序对任意两个元素都存在在集合内的上界，或者说这个预序有一个最大元。 也可以指其对偶关系，对任意两个元素都只有一个下界，或者说一个最小元。 元素间存在方向的集合称为有向集(directed set)，以上两种分别称为上有向集和下有向集。

定义

对集合 [math]\displaystyle{ P }[/math] 上的二元关系 [math]\displaystyle{ \preceq }[/math] ，如果满足自反性、传递性，且任意两个元素都在集合内有上界，即：

  • 自反性： [math]\displaystyle{ \forall a \in P (a \preceq a) }[/math] ；
  • 传递性： [math]\displaystyle{ \forall a \forall b \forall c (a \preceq b \land b \preceq c \rightarrow a \preceq c) }[/math] ；
  • 有上界： [math]\displaystyle{ \forall a \forall b \exists c (a \preceq c \land b \preceq c) }[/math] 。

称关系 [math]\displaystyle{ \preceq }[/math] 为一个方向(direction)。 并称带有方向关系的集合 [math]\displaystyle{ (P,\preceq) }[/math] 为有向集(directed set)。

在讨论有向集时往往与上下界和最大最小值的唯一性有关。其中，有上界的也称为上有向集(upward directed set)，有下界的称为下有向集(downward directed set)。

根据使用者的习惯，方向中的关系通常和预序的关系保持类似的符号，可能使用符号 [math]\displaystyle{ \preceq,\precsim,\leq }[/math] 之一。

注：任意两个元素有上界也可以等价地表达为任意有限子集有上界。

性质

  • 基本特征
    • 方向是自反且传递的二元关系（预序），且满足任意两个元素有公共上界（或下界）；
    • 上有向集要求任意两元素有公共上界；
    • 下有向集要求任意两元素有公共下界。
  • 有向集中的特殊元素

关联

  • 构造方法
    • 有最大元的预序集，或者向预序集中添加一个最大元后，都是有向集
    • 任意有预序的有限子集与其上界构成新的有向集
    • 全序集都是有向集
    • 偏序集任意有限子集若有上界则构成有向集；偏序集由于不一定有上界，可能无法构成有序集
    • 半格是上有向集或下有向集


关系
定义属性 前域、后域、定义域 [math]\displaystyle{ \operatorname{dom} }[/math]、值域 [math]\displaystyle{ \operatorname{ran} }[/math]、域 [math]\displaystyle{ \operatorname{fld} }[/math]
特殊关系 空关系 [math]\displaystyle{ \varnothing }[/math]、恒等关系 [math]\displaystyle{ I }[/math]、全关系 [math]\displaystyle{ A\times B }[/math]
二元齐次关系类型 自反、反自反、对称、反对称、传递
运算 集合运算 交 [math]\displaystyle{ \cap }[/math]、并 [math]\displaystyle{ \cup }[/math]、补 [math]\displaystyle{ \bar{\bullet} }[/math]、差 [math]\displaystyle{ \setminus }[/math]
类映射运算 转置/逆 [math]\displaystyle{ \bullet^\mathrm{T}/\bullet^{-1} }[/math]、复合 [math]\displaystyle{ \circ }[/math]（幂 [math]\displaystyle{ \bullet^n }[/math]）、限制 [math]\displaystyle{ \bullet_{|\bullet} }[/math]
闭包运算 自反 [math]\displaystyle{ \operatorname{r}() }[/math]/[math]\displaystyle{ \bullet^= }[/math]、对称 [math]\displaystyle{ \operatorname{s}() }[/math]/[math]\displaystyle{ \bullet^\sim }[/math]、传递 [math]\displaystyle{ \operatorname{t}() }[/math]/[math]\displaystyle{ \bullet^+ }[/math]、自反传递 [math]\displaystyle{ \bullet^* }[/math]、等价 [math]\displaystyle{ \bullet^\equiv }[/math]
二元关系复合类型
名称 自反、反自反 对称、反对称 传递 其他
相容关系 自反 对称 - -
预序 自反 - 传递 -
等价关系 自反 对称 传递 -
方向 自反 - 传递 有上/下界
偏序 自反 反对称 传递 -
半格 自反 反对称 传递 有上/下确界
弱序/全序划分 自反 - 传递 完全
全序 自反 反对称 传递 完全
良序 自反 反对称 传递 完全、良基
不对称 反自反 反对称 - -
拟序/严格偏序 反自反 反对称 传递 -
严格弱序/严格全序划分 反自反 反对称 传递 不可比关系传递
严格全序 反自反 反对称 传递 完全
检索自“https://knowledge.gsxab.top/index.php?title=方向（序理论）&oldid=5740”