介绍如题的内容。

Relations

Relations : A relation from a set to a set is a subset .

Ex : Symbol: A relation on is a subset . Ex: Set together with is a directed graph , with .

Properties

A relation on is: reflexive : if for all symmetric : if for all antisymmetric: if transitive: if

例子 (Ex)	自反 (Refl)	对称 (Sym)	反对称 (Anti-Sym)	传递 (Transitive)
	Y	Y	N	Y
(整除)	Y	N	Y	Y
(包含)	Y	N	Y	Y

Equivalence relation

An equivalence relation is reflective, symmetric and transitive.

Ex : equality(=) itself, .

The equivalence class of is the set of all elements in that related to by , denoted .

Ex : , .

A partition of is a collection of disjoint non-empty sets , whose union is .

Ex :

Theorem

The equivalence class of an equivalence relation on a set form a partition of .

[!Proof] 1.。 Since is reflexive, every element a is contained in its own equivalence class . Thus, the union of all equivalence classes covers . At the same time, every equivalence class shall be the subset of . Thus, 。 From above, 。

2.>Since is reflexive, has at least one element .

3.Disjointness If , let .By definition,.By symmetry,. By transitivity and ,. So . This way,. Thus, . By symmetry, we also have [b] ⊆ [a], hence [a] = [b].

A relation is a (weak) partial order if it is (reflexive), antisymmetric and transitive. It is denoted by

is called a partially order set or poset.

A poset is a directed graph with vertex set and edge set .

Hasse Diagram

A Hasse Diagram for a poset is a directed graph with vertex set and the edge set excluding

• all self-loops
• all the edges implied by transitivity

Theorem

A poset has no directed cycles other than self-loops.

[!Proof] By contradiction. Suppose . By transitivity and obvious induction, we have . Thus by antisymmetry . That is a contradiction. So the original statement is right.

So after deleting self-loops from a poset, we get a DAG(directed acyclic graph).

In poset, there could be that are incomparable when .

A total order is a partial order in which every pair of elements are comparable. It could give a straight line.

A total order consistent with a partial order is called a topological sort. A topological sort of a poset is formally defined as a total order such that .

Theorem

Every finite poset has a topological sort.

def:

[!Lemma] Every finite poset has a minimal element.

def: chain is a sequence of distinct elements such that ,where is the length of the chain.

proof:

Let be a max length chain. Then should be the minimal. Suppose : case 1: if the chain, then let be the first one we create a longer chain. That’s a contradiction. case 2: the chain. Then we could create a cycle, which could not exist according to the theorem we just proved. So that’s a contradiction. Thus, the original proposition holds.

[!Proof] By strong induction. Let  be a finite poset with . Let be the proposition itself for all integers less than .

Base Case: , is already a topological sort.

Inductive step: Assume >By lemma, with elements has minimal . Consider ${m}=A’≼ A’\times A’≼’=≼ \cap A’\times A’ P(k)(A’,≼’) a_2,…a_{k-1} m,a_2,…,a_{k-1} A (x,y)\in A x≼y \not \exists k \in A\text{ , s.t. , } k ≼ m x=m y m x\neq m \wedge y\neq m P(k) m,a_2,…,a_{k-1} A $.

Finally we find a topological sort for . So the proposition holds. In practice, we just select with zero indegree as the minimal and do it recursively.

---

手动翻译：

关系

关系 ： 一个从集合 到集合 的关系是指 笛卡尔积的一个子集 。

例如 : 符号: 一个 上的关系则是 的子集 。这可以用有向图来表示。 , with .

性质

自反性 ： 如果 对每个 都成立。 对称性 ： 如果 对所有 都成立 反对称性: 如果 对所有 都成立 传递性: 如果 对所有 都成立

例子 (Ex)	自反 (Refl)	对称 (Sym)	反对称 (Anti-Sym)	传递 (Transitive)
	Y	Y	N	Y
(整除)	Y	N	Y	Y
(包含)	Y	N	Y	Y

等价关系

一个等价关系是自反的，对称的，传递的。例如等号、同余。

一个 的等价类是指所有与 有等价关系的元素组成的集合，记作 。

Ex : , .

一个 的划分是指一些非空非交的集合 ，他们的并是 。

Ex :

定理

等价类构成 的划分。

[!证明] 1.。等价类并是 ： 由自反性, 对 有 . 所以每个元素都有他们自己的等价类，因此 >同时每个等价类都是 的子集，所以 。 由上 。

2.>因为 自反, 至少有元素 .

3.不交 如果 , 设 .由定义,.由对称性,. 由传递性和 , . 所以 . 从而 . 那么 . 同理 .综上有 .

一个关系是偏序关系如果他是自反、反对称、传递的。用 表示。 叫做 偏序集.

一个偏序集是有着顶点集 和边集 的有向图 .

哈斯图

哈斯图 是偏序集 是顶点集 和边集 去掉

• 所有自环
• 所有传递性推出来的边

定理

偏序集对应的有向图除了自环无环。

[!证明] 用反证法。 设 . 利用传递性和简单的归纳, 有 . 从而由传递性 . 矛盾，故原命题成立。

故去掉自环后，他就成了有向无环图(DAG)。

偏序集中可能有不可比较的 ，就是说 .

全序 是所有元素都可以比较的偏序，对应一条直线。

和偏序相一致的全序叫做 拓扑排序. 偏序集的拓扑排序的正式定义由全序给出： such that .

定理

任意有限偏序集都有拓扑排序。

定义:

[!引理] 任意有限偏序集都有最小值。

定义: 链 是不同元素的序列使得 ,其中 是链的长度。

证明:

设 是最长的链. 那么 将是最小值. 设 : case 1: 如果 链, 让 是第一个顶点那么就构造了更长的链. 矛盾. case 2: 链. 那么会出现环，这与前面证明的定理矛盾。 综合可知引理成立。

[!证明] 使用加强的归纳法。 设  是满足 的有限偏序集. 设 是命题对所有 以下的正整数都成立.

奠基步: , 已经是一个拓扑排序。

归纳步: 设 成立。 利用引理, 有最小值 . 考虑 ${m}=A’≼ A’\times A’≼’=≼ \cap A’\times A’ P(k)(A’,≼’) a_2,…a_{k-1} m,a_2,…,a_{k-1} A (x,y)\in A x≼y \not \exists k \in A\text{ , s.t. , } k ≼ m x=m y m x\neq m \wedge y\neq m P(k) m,a_2,…,a_{k-1} A $ 的拓扑排序.

我们找到了 的拓扑排序. 所以命题成立. 实际操作上，我们选择入度为 的 即为最小值了，然后删去 重复该过程即可。