最大元、最小元(序理论)
(重定向自最大元)
最大元 | |
---|---|
术语名称 | 最大元 |
英语名称 | 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] 可以是预序集本身。
二元关系复合类型 | |||||
---|---|---|---|---|---|
名称 | 自反、反自反 | 对称、反对称 | 传递 | 其他 | |
预序 | 自反 | - | 传递 | - | |
等价关系 | 自反 | 对称 | 传递 | - | |
方向 | 自反 | - | 传递 | 有上/下界 | |
偏序 | 自反 | 反对称 | 传递 | - | |
弱序/全序划分 | 自反 | - | 传递 | 完全 | |
全序 | 自反 | 反对称 | 传递 | 完全 | |
良序 | 自反 | 反对称 | 传递 | 完全、良基 | |
不对称 | 反自反 | 反对称 | - | - | |
拟序/严格偏序 | 反自反 | 反对称 | 传递 | - | |
严格弱序/严格全序划分 | 反自反 | 反对称 | 传递 | 不可比关系传递 | |
严格全序 | 反自反 | 反对称 | 传递 | 完全 |