Ch9 Relations

• 利用定义。
• 利用数学归纳法。

Is a relation $R$ is reflexive if it is symmetric and transitive?

Incorrect. Because it cannot be guaranteed that for all $a \in S$, there exists a $b$ such that $(a,b)\in R$. Therefore, there might exist such an $a\in R$ for which there is no relation concerning $a$.”

The relation $R$ on a set $A$ is transitive if and only if $R^n \subseteq R,\, n=1,2,3,\ldots$.

设 $R,S$ 是从集合 $A$ 到集合 $B$ 上的关系，$T$ 是从集合 $B$ 到集合 $C$ 的关系，$P$ 是从集合 $C$ 到集合 $D$ 的关系。

• $(R \cup S)^{-1} = R^{-1} \cup S^{-1}$
• $(R\cap S)^{-1} = R^{-1} \cap S^{-1}$
• $(\overline R)^{-1} = \overline{R^{-1}}$
• $(R-S)^{-1} = R^{-1} - S^{-1}$
• $(A\times B)^{-1} = B \times A$：
• $\overline R= A \times B - R$
• $(S \circ T)^{-1} = T^{-1} \circ S^{-1}$
• $(R \circ T) \circ P = R \circ (T \circ P)$
• $(R \cup S) \circ T = R \circ T \cup S \circ T$

The 闭包(closure) of a relation $R$ with respect to property $P$ is the relation $S$ with property if and only if

(1) $S$ contains $R$;

(2) $S$ is a subset of every relation with property $P$.

(3) $S$ is the smallest relation satisfying (1) and (2).

关系 $R$ 的自反闭包用 $r(R)$ 表示，且满足 $r(R) = R \cup I_A$。

• 这里 $I_A$ 表示集合 $A$ 上的对角线关系，即 $I_A = \{(x,x) \mid x \in A\}$。

Proof

$R = R \cup I_A$ 当且仅当 $R$ 是自反关系。

Proof

关系 $R$ 的对称闭包用 $s(R)$ 表示，且满足 $s(R) = R \cup R^{-1}$。

Proof

$R = R \cup R^{-1}$ 当且仅当 $R$ 是对称关系。

设 $R$ 是定义在 $A$ 上的关系，则有一条从 $a$ 到 $b$ 的长度为 $n$ 的路径当且仅当 $(a,b) \in R^n$。

一些来自下一章的概念：

• A 路径(path) of length $n$ in a digraph $G$: A sequence of edges $(x_0,x_1),(x_1,x_2),\ldots,(x_{n-1},x_n)$.

• 环(cycle): A path of length $n$ with $x_0=x_n (n\ge 1)$.

Proof (by induction)

The 传递闭包(transitive closure) of a relation $R$ is $t(R) = R^\ast$.

可以通过 Floyd-Warshall 算法求解关系的传递闭包。（这就是最经典的 $O(n^3)$ 的 Floyd 算法。）

A relation $R$ on a set $A$ is an 等价关系(equivalence relation) if $R$ is (1) reflexive; (2) symmetric; (3) transitive.

We call $a$ and $b$ is 等价的(equivalent) if $(a,b) \in R$, denoted as $a\sim b$.

The 等价类(equivalence class) of $x$: the set of all elements that is equivalent to $x$, denoted as $[x]_R$ or $[x]$.

如果 $R$ 是集合 $A$ 上的等价关系，则以下三个命题等价：

(1) $aRb$

(2) $[a]=[b]$

(3) $[a]\cap[b] \neq \emptyset$

Proof

设 $R_1,R_2$ 是集合 $A$ 上的等价关系，则 $R_1 \cap R_2$ 也是集合 $A$ 上的等价关系。

设 $R_1,R_2$ 是集合 $A$ 上的等价关系，则 $R_1 \cup R_2$ 具有自反性和对称性。进一步的，$(R_1\cup R_2)^\ast$ 是集合 $A$ 上的等价关系。

A 划分(partition) of set $A$ is a collection of disjoint nonempty subsets of $A$ that have $A$ as their union, denoted as $pr(A) = \{A_1,A_2,\cdots A_n\}$.（两两不交，并为全集）

Let $R$ be an equivalence relation on a set $A$. Then the equivalence classes of $R$ form a partition of $A$.

Conversely, given a partition $\{A_i\mid i \in I\}$ of the set $A$, there is an equivalence relation $R$ that has the sets $A_i,i\in I$, as its equivalence classes.

A relation $R$ on a set $A$ is an 偏序关系(partial ordering) if $R$ is (1) reflexive; (2) antisymmetric; (3) transitive.

Notation:

• $(S,R)$: partially ordered set or 偏序集(poset).
• $a\preccurlyeq b$: $(S,R)$ is a poset and $(a,b) \in R$.

Given two posets $(A_1,\preccurlyeq_1)$ and $(A_2,\preccurlyeq_2)$, the lexicographic ordering on $A_1\times A_2$ is defined by specifying that $(a_1,a_2)$ is less than $(b_1,b_2)$, that is, $(a_1, a_2)\prec (b_1,b_2)$, either if $a_1 \prec_1 b_1$ or if $a_1 =_1 b_1$ and $a_2 \prec_2 b_2$.

由多个偏序集的笛卡尔积得到的字典序是一个偏序关系。

设 $(A,\preccurlyeq)$ 是一个偏序集，称 $a$ 是一个最大元素(maximal element) 当且仅当 $A$ 中不存在元素 $b$ 满足 $a \prec b$。称 $a$ 是一个最小元素(minimal element) 当且仅当 $A$ 中不存在元素 $b$ 满足 $b\prec a$。

设 $(A,\preccurlyeq)$ 是一个偏序集，称 $a$ 是其最大值(greatest element) 当且仅当对于每个 $A$ 中的元素 $b$ 都有 $b \preccurlyeq a$；称 $a$ 是其最小值(least element) 当且仅当对于每个 $A$ 中的元素 $b$ 都有 $a \preccurlyeq b$。

设 $(S,\preccurlyeq)$ 是一个偏序集，$A \subset S$。若存在一个 $S$ 中的元素 $a$ 满足对于 $A$ 中的所有元素 $b$ 都有 $b\preccurlyeq a$，则称 $a$ 是 $A$ 的一个上界(upper bound)。若存在一个 $S$ 中的元素 $a$ 满足对于所有 $A$ 中的元素 $b$ 都有 $a\preccurlyeq b$，则称 $a$ 是 $A$ 的一个下界(lower bound)。

如果 $a$ 是子集 $A$ 的上界中最小的，则称其是 $A$ 的最小上界(least upper bound)，记为 $\text{lub}(A)$。如果 $a$ 是子集 $A$ 的下界中最大的，则称其是 $A$ 的最大下界(greatest lower bound)。

The elements $a$ and $b$ of a poset $(S,\preccurlyeq)$ are 可比较的(comparable) if either $a\preccurlyeq b$ or $b\preccurlyeq a$. When $a$ and $b$ are elements of $S$ so that neither $a\preccurlyeq b$ nor $b\preccurlyeq a$, then $a$ and $b$ are called 不可比较的(incomparable).

$(A,\preccurlyeq)$ 是一个偏序集，$B\subseteq A$。如果 $(B,\preccurlyeq)$ 是全序的，则称 $B$ 是 $A$ 的一条链(chain)。

$(A,\preccurlyeq)$ 是一个偏序集，$B\subseteq A$。如果 $\forall a, b ,\in B(a \neq b),\space (a, b)\not\in R, (b, a)\not\in R$，则称 $B$ 是 $A$ 的一条反链(antichain)。

一个偏序集 $(A,R)$ 是良序集(well-ordered set) 当且仅当其每一个非空子集都有一个最小值。

一个偏序集被称为格(lattice) 当且仅当其每一对元素都有一个最小上界和最大下界。