介绍如题的内容。

Relations

Relations : A relation from a set $A$to a set$B$is a subset$R\subseteq A \times B$ .

Ex : $R={(a,b),\text{student a is taking class b}}$Symbol:$(a,b)\in R, aRb$A relation on$A$is a subset$R\subseteq A\times A$ .
Ex: $A=\mathcal{Z}: xRy \text{ iff } x\equiv y \pmod 5$Set$A$together with$R$is a directed graph$G=(V,E)$, with$V=A,E=R$ .

Properties

A relation $R$on$A$ is:
reflexive : if $xRx$for all$x\in A$symmetric : if$xRy\implies yRx$for all$x,y\in A$antisymmetric: if$xRy \wedge yRx\implies x=y$transitive: if$xRy\wedge yRz\implies xRz$

Equivalence relation

An equivalence relation is reflective, symmetric and transitive.

Ex : equality(=) itself, $x\equiv y \pmod n$ .

The equivalence class of $x\in A$is the set of all elements in$A$that related to$x$by$R$, denoted$[x]$ .

Ex : $x\equiv y \pmod 5$,$[7]=5k+2, k\in \mathbb{Z}$ .

A partition of $A$is a collection of disjoint non-empty sets$A_1,…,A_m \in A$, whose union is $A$ .

Ex : $[1],[2],[3],[4],[0]$

Theorem

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

[!Proof]
1.$\bigcup_{a \in A} [a] \subseteq A$。
Since $R$is reflexive, every element a is contained in its own equivalence class$[a]$. Thus, the union of all equivalence classes covers $A$.
At the same time, every equivalence class shall be the subset of $A$. Thus, $\bigcup_{a \in A} [a] \subseteq A$。
From above, $\bigcup_{a \in A} [a] = A$。

2.$[a] \neq \phi$>Since$R$is reflexive,$[a]$has at least one element$a$.

3.Disjointness
If $[a] \cap [b] \neq \emptyset$, let$c \in [a] \cap [b]$.By definition,$cRa \wedge cRb$.By symmetry,$aRc$. By transitivity and$aRc \wedge cRb$,$aRb$. So$\forall x \in [a], xRb$. This way,$x\in [b]$. Thus, $[a]\subseteq[b]$ . 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 $\preccurlyeq$ $\succcurlyeq$

$(A,\preccurlyeq)$ is called a partially order set or poset.

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

Hasse Diagram

A Hasse Diagram for a poset $(A,\preccurlyeq)$is a directed graph with vertex set$A$and the edge set$\preccurlyeq$ 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 $\exists n \ge 2, \text{distinct elements } a_1,…,a_n;a_1\preccurlyeq…\preccurlyeq a_n\preccurlyeq a_1$. By transitivity and obvious induction, we have$a_1 \preccurlyeq a_n$. Thus by antisymmetry $a_1=a_n$ . 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 $a,b$that are incomparable when$\neg a \preccurlyeq b \wedge \neg b \preccurlyeq a$.

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 $(A,\preccurlyeq_T)$such that$\preccurlyeq \in \preccurlyeq_T$ .

Theorem

Every finite poset has a topological sort.

def:
$x\in A \text{ is minimal if } \neg \exists \text{ }y \in A, y\neq x \text{ } s.t. \text{ }y \preccurlyeq x$
$x\in A \text{ is maximal if } \neg \exists \text{ }y \in A, y\neq x \text{ } s.t. \text{ }x \preccurlyeq y$

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

def: chain is a sequence of distinct elements such that $a_1\preccurlyeq …\preccurlyeq a_t$,where$t$ is the length of the chain.

proof:

Let $a_1\preccurlyeq … \preccurlyeq a_n$be a max length chain. Then$a_1$should be the minimal. Suppose$\exists a\preccurlyeq a_1$ :
case 1: if $a\not \in$the chain, then let$a$ be the first one we create a longer chain. That’s a contradiction.
case 2: $a\in$ 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 $(A,≼)$be a finite poset with$∣A∣=n$. Let $P(k)$be the proposition itself for all integers less than$k$ .

Base Case: $n=1$, $A={a}$ is already a topological sort.

Inductive step: Assume $P(k)$>By lemma,$A$with$n$elements has minimal$m$. Consider$A$${m}$ $=A’$. Restrict$≼$on$A’\times A’$:$≼’=≼ \cap A’\times A’$. By$P(k)$,$(A’,≼’)$has a topological sort$a_2,…a_{k-1}$ .
Now we shall prove $m,a_2,…,a_{k-1}$is a topological sort for$A$. Consider a pair $(x,y)\in A$that$x≼y$ .
Since $\not \exists k \in A\text{ , s.t. , } k ≼ m$, if$x=m$, it follows the definition of topological sort, and$y$could not be$m$. If $x\neq m \wedge y\neq m$,by$P(k)$it follows the definition of topological sort. So$m,a_2,…,a_{k-1}$is a topological sort for$A$.

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

手动翻译：

关系

关系 ： 一个从集合 $A$到集合$B$的关系是指$A,B$笛卡尔积的一个子集$R\subseteq A \times B$ 。

例如 : $R={(a,b),\text{student a is taking class b}}$符号:$(a,b)\in R, aRb$一个$A$上的关系则是$A\times A$的子集$R$。这可以用有向图来表示。 $G=(V,E)$, with$V=A,E=R$ .

性质

自反性 ： 如果 $xRx$对每个$x\in A$ 都成立。
对称性 ： 如果 $xRy\implies yRx$对所有$x,y\in A$ 都成立
反对称性: 如果 $xRy \wedge yRx\implies x=y$对所有$x,y\in A$ 都成立
传递性: 如果 $xRy\wedge yRz\implies xRz$对所有$x,y,z\in A$ 都成立

等价关系

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

一个 $x\in A$的等价类是指所有与$x$有等价关系的元素组成的集合，记作$[x]$。

Ex : $x\equiv y \pmod 5$,$[7]=5k+2, k\in \mathcal{Z}$ .

一个 $A$的划分是指一些非空非交的集合$A_1,…,A_m \in A$，他们的并是$A$ 。

Ex : $[1],[2],[3],[4],[5]$

定理

等价类构成 $A$ 的划分。

[!证明]
1.$\bigcup_{a \in A} [a] \subseteq A$。等价类并是 $A$ ：
由自反性, 对 $a\in A$有$aRa$. 所以每个元素都有他们自己的等价类，因此$A \subseteq \bigcup_{a \in A} [a]$>同时每个等价类都是$A$的子集，所以$\bigcup_{a \in A} [a] \subseteq A$。
由上 $\bigcup_{a \in A} [a] = A$。

2.$[a] \neq \phi$>因为$R$自反,$[a]$至少有元素$a$.

3.不交
如果 $[a] \cap [b] \neq \emptyset$, 设$c \in [a] \cap [b]$.由定义,$cRa \wedge cRb$.由对称性,$aRc$. 由传递性和$aRc \wedge cRb$,$aRb$ . 所以$\forall x \in [a], xRb$. 从而$x\in [b]$. 那么 $[a]\subseteq[b]$. 同理$[b]\subseteq[a]$.综上有$[a]=[b]$.

一个关系是偏序关系如果他是自反、反对称、传递的。用 $\preccurlyeq$表示。$(A,\preccurlyeq)$ 叫做 偏序集.

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

哈斯图

哈斯图 是偏序集 $(A,\preccurlyeq)$是顶点集$A$ 和边集$\preccurlyeq$ 去掉

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

定理

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

[!证明]
用反证法。
设 $\exists n \ge 2, \text{不同元素 } a_1,…,a_n;a_1\preccurlyeq…\preccurlyeq a_n\preccurlyeq a_1$. 利用传递性和简单的归纳, 有$a_1 \preccurlyeq a_n$. 从而由传递性 $a_1=a_n$ . 矛盾，故原命题成立。

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

偏序集中可能有不可比较的 $a,b$，就是说$\neg a \preccurlyeq b \wedge \neg b \preccurlyeq a$.

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

和偏序相一致的全序叫做 拓扑排序. 偏序集的拓扑排序的正式定义由全序给出： $(A,\preccurlyeq_T)$such that$\preccurlyeq \in \preccurlyeq_T$ .

定理

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

定义:
$x\in A \text{ 是最小值如果 } \neg \exists \text{ }y \in A, y\neq x \text{ } s.t. \text{ }y \preccurlyeq x$
$x\in A \text{ 是最大值如果 } \neg \exists \text{ }y \in A, y\neq x \text{ } s.t. \text{ }x \preccurlyeq y$

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

定义: 链 是不同元素的序列使得 $a_1\preccurlyeq …\preccurlyeq a_t$,其中$t$ 是链的长度。

证明:

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

[!证明]
使用加强的归纳法。
设 $(A,≼)$是满足$∣A∣=n$的有限偏序集. 设$P(k)$是命题对所有$k$ 以下的正整数都成立.

奠基步: $n=1$, $A={a}$ 已经是一个拓扑排序。

归纳步: 设 $P(k)$ 成立。
利用引理, $A$有最小值$m$. 考虑$A$${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$,由y$P(k)$他们也符合拓扑排序定义. 所以$m,a_2,…,a_{k-1}$是$A$ 的拓扑排序.

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