集合論/排序

排序

定義

具有某些屬性的、在集合上強加順序概念的關係被稱為**排序關係**或簡稱為**排序**。對於以下定義，令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\}$ .