集合论/排序

排序

定义

具有某些属性的、在集合上强加顺序概念的关系被称为**排序关系**或简称为**排序**。对于以下定义，令R为一个二元关系。

如果R是自反的和传递的，那么它被称为**预序**。
如果R是预序并且也是反对称的，那么它被称为**偏序**。
如果R是偏序并且也是全序的，那么它被称为**全序**或**线性序**。

一个配备了预序、偏序或全序的集合被称为**预序集**、**偏序集**（或**偏序集**）或**全序集**（或**线性序集**）。排序关系通常用符号 $\leq$ 表示，有序集用有序对 $(S,\leq )$ 表示，其中 $\leq$ 是S上的排序关系。

偏序集的全序子集被称为**链**。因此，任何全序集有时可能被称为链。

预序集（因此在偏序或全序集中）的两个元素a和b被称为**可比较的**，如果 $a\leq b$ 或 $b\leq a$ 。注意，虽然全序保证全序集中每两个元素都是可比较的，但预序或偏序集中两个元素可能不是这样。

边界

设 $(S,\leq )$ 是一个预序集，设 $T$ 是 $S$ 的一个子集。如果存在 $S$ 中的一个元素 $u$ ，使得对于所有 $x\in T$ 都有 $x\leq u$ ，那么 $u$ 称为 $T$ 的一个上界。类似地，如果存在 $S$ 中的一个元素 $l$ ，使得对于所有 $x\in T$ 都有 $l\leq x$ ，那么 $l$ 是 $T$ 的一个下界。如果一个集合存在上界，则称该集合有上界，或者类似地，如果存在下界，则称该集合有下界。

令 $(P,\leq )$ 为一个偏序集，令 $T$ 为 $P$ 的一个子集。如果元素 $u\in P$ 是 $T$ 的上界，并且如果 $u\leq z$ 当且仅当 $z$ 是 $T$ 的上界，那么 $u$ 称为 $T$ 的 **最小上界** 或 **上确界**。类似地， $T$ 的下界，大于或等于 $T$ 的所有其他下界，是 $T$ 的 **最大下界** 或 **下确界**。以下命题指出，我们有理由称这些元素为 **上确界** 或 **下确界**，而不是仅仅 **一个** 上确界或下确界。证明留给读者。

命题： 集合的上确界和下确界都是唯一的。

令 $(P,\leq )$ 为一个偏序集， $T$ 为 $P$ 的一个子集。 $T$ 的**极大元**是指任何满足以下条件的元素 $m$ ：如果 $m\leq a$ ，则对所有 $a\in T$ ，有 $m=a$ 。如果上述语句中的不等式反转，则该元素称为**极小元**。如果 $t\in T$ 大于 $T$ 中的所有其他元素，则 $t$ 是**最大元**或**最大值**，类似地，如果它小于所有其他元素，则是**最小元**或**最小值**。请注意，偏序集中的元素可以是极大元，而不能是最大值，因为偏序集中的所有元素可能无法比较。

等价关系

另一种重要的关系类型是**等价关系**。它是一种满足**自反性**、**对称性**和**传递性**的关系（或者，简单来说，是满足**对称性**的预序）。当 *R* 是一种等价关系时，我们通常用 $\sim$ 或 $\equiv$ 表示它。一个配备了等价关系的集合也被称为**类集**。

如果 $\sim$ 是集合 $S$ 上的等价关系，我们定义对于元素 $s\in S$ ，其 **等价类** 为 $\{a\in S:a\sim s\}$ 。这通常用 $[s]$ 表示。集合 $S$ 的所有等价类的集合被称为 $S$ 模 $\sim$ 的 **商集**，记为 $S/\!\sim \ =\{[x]:x\in S\}$ .