最大元、最小元(序理论)

来自GSXAB的知识库
最大元
术语名称 最大元
英语名称 greatest element
最小元
术语名称 最小元
英语名称 least element

最大/最小元(greatest/least element)指预序集或有向集的子集中,先(后)序于其中所有元素的某个元素。 最大元与最小元互为对偶。

区别于极大元、极小元(序理论)

定义

对预序集 [math]\displaystyle{ (P, \preceq) }[/math] 及其任意子集 [math]\displaystyle{ S\subseteq P }[/math]

  • 若对某元素 [math]\displaystyle{ m \in S }[/math] ,有 [math]\displaystyle{ (\forall s \in S) (s \preceq m) }[/math] ,则称元素 [math]\displaystyle{ s }[/math] 是其中的一个最大元(greatest element);若是(上)有向集,则称元素 [math]\displaystyle{ s }[/math] 是有向集中的最大元(greatest element)
  • 若对某元素 [math]\displaystyle{ m \in S }[/math] ,有 [math]\displaystyle{ (\forall s \in S) (m \preceq s) }[/math] ,则称元素 [math]\displaystyle{ s }[/math] 是其中的一个最小元(least element);若是下有向集,则称元素 [math]\displaystyle{ s }[/math] 是有向集中的最小元(least element)。

注:

  • 一个子集中不一定存在最大元或最小元。
  • 如果集合不是偏序集,由于预序不要求反对称,最大元和最小元不是唯一的。最大元和最小元的存在时唯一的条件,等价于这个预序集是一个有向集。
  • 上述 [math]\displaystyle{ S }[/math] 可以是预序集本身。


二元关系复合类型
名称 自反反自反 对称反对称 传递 其他
预序 自反 - 传递 -
等价关系 自反 对称 传递 -
方向 自反 - 传递 有上/下界
偏序 自反 反对称 传递 -
弱序/全序划分 自反 - 传递 完全
全序 自反 反对称 传递 完全
良序 自反 反对称 传递 完全、良基
不对称 反自反 反对称 - -
拟序/严格偏序 反自反 反对称 传递 -
严格弱序/严格全序划分 反自反 反对称 传递 不可比关系传递
严格全序 反自反 反对称 传递 完全