Relation (Math) and Asymptotic Notations
1. Relation (Mathmatics)
Wikipedia 写得挺好，这里总结一下。
1.1 Definition
Given a set $X$, a relation $R$ over $X$ is a set of ordered pairs of elements from $X$, formally: $R \subseteq \lbrace (x,y) \mid x, y \in X \rbrace$.
- 你也可以扩展成 $R \subseteq \lbrace (x,y) \mid (x,y) \in X \times Y \rbrace$，但这么定义就排除了 $(y,x)$ 形式的元素 (类型不匹配)
符号上有：
- $(x,y) \in R$ 也可以写作 infix 形式 $xRy$，意思就是 “$x,y$ 满足 $R$ 关系”
- 自创用法：我在本文用 $x \cancel{R} y$ 表示 “$x,y$ 不满足 $R$ 关系”
- 自创用法：我在本文用 $x \oslash_{R} y$ 表示 “$x,y$ 在 $R$ 下是 incomparable 的”
- i.e. $x \oslash_{R} y \iff x \cancel{R} y \land y \cancel{R} x$
1.2 Representation of Relations
如果 $X$ 是一个 discrete 的集合，$R$ 的 size 有限，那么可以 R 可以表示成：
- directed graph: 每一组 $xRy$ 都用一条 $x \to y$ 的 edge 表示
- boolean matrix: 每一组 $xRy$ 都表示 $M_{x,y} = 1$，每一组 $x \cancel{R} y$ 都表示 $M_{x,y} = 0$
- 如果 $x \oslash_{R} y$，那么 $M_{x,y}$ 就是 undefined，此时 $M$ 也不能算是 boolean matrix 了
如果 $X$ 是 $\mathbb{R}$：
- 每一组 $xRy$ 都可以看作是坐标系下的一个点，所以 $R$ 也可以表示成一个 2D plot
- 比如 $R = \lbrace (x,y) \mid x^2 + y^2 = 1 \rbrace$
1.3 Properties of Relations
1.3.1 Reflexivity
Reflexive: $\forall x \in X, xRx$
Irreflexive: $\forall x \in X, x \cancel{R} x$
我们可以完全不用它的英文名字，也不用管中文翻译 (因为后面对称性的命名简直灾难！)，结合 boolean matrix representation 来记忆：
- reflexive 就是主对角线全是 1，比如 $M_1$
- irreflexive 就是主对角线全是 0，比如 $M_2$
我们说这组 properties 是 non-exhausitive 的，意思是 $\exists R$ 既不是 reflexive 也不是 irreflexive 的，结合 boolean matrix representation 很容易举出一个反例。
1.3.2 Symmetry
Symmetric: $\forall x,y \in X$, $xRy \implies yRx$
Asymmetric: $\forall x,y \in X$, $xRy \implies y \cancel{R} x$
Antisymmetric: $\forall x,y \in X$, $xRy \land yRx \implies x = y$
这个混乱的命名，我觉得背后的逻辑是：
- 从定义的形式上来看，symmetric 的定义直接加个否定就变成了 asymmetric，非常的漂亮
- 但这么定义下的 asymmetric 暗含了 irreflexive (因为你不可能同时有 $xRx$ 和 $x \cancel{R} x$)，有点过于 strong
- relax 一下，不要求 irreflexive 的非对称，就变成了 antisymmetric
还是结合 boolean matrix representation 记忆：
- symmetric 就是 $M_{i,j} = M_{j,i}$，主对角线上随意，比如 $M_1$
- asymmetric 就是 $M_{i,j} \neq M_{j,i}$，主对角线上全是 0，比如 $M_2$
- antisymmetric 就是 $M_{i,j} \neq M_{j,i}$，但主对角线上随意，比如 $M_3$
定义上有：asymmetric $\equiv$ antisymmetric $\land$ irreflexive
同样，这组 properities 也不是 exhausitive 的，结合 boolean matrix representation 也很容易举出反例。
1.3.3 Transitivity & Connectedness
Transitive: $\forall x,y,z \in X$, $xRy \land yRz \implies xRz$
Connected: $\forall x,y \in X$, $x \neq y \implies$ $xRy$ or $yRx$. Or equivalently $\forall x,y \in X$, $xRy$ or $yRx$ or $x=y$
Strongly Connected: $\forall x,y \in X$, $xRy$ or $yRx$
考虑 transitive 的特殊情况：
- if $x = y = z$，obvious implication
- if $x = y \neq z$，obvious implication
- if $x = z \neq y$，transitive 等价于：如果有 $x \to y \to x$ 这样一个 loop，那么就会有 $x \to x$ 的 self loop
- if $x \neq y = z$, obvious implication
flowchart LR
node_1(("X"))
node_2(("Y"))
node_1 --> node_2
node_2 --> node_1
node_1 --> node_1
定义上有：transitive $\land$ irreflexive $\equiv$ transitive $\land$ asymmetric
Proof: (1) 假定 $R$ 是 transitive $\land$ irreflexive. 假定 $\exists x,y \in X$ 同时满足 $xRy$ 和 $yRx$ (从而不满足 asymmetric)
根据 transitive 定义，$xRy \land yRx \implies xRx$，不满足 irreflexive，矛盾。所以 R 一定满足 asymmetric
(2) 假定 $R$ 是 transitive $\land$ asymmetric. 因为 asymmetric implies irreflexive，所以 $R$ 一定是 irreflexive. $\blacksquare$
结合 2D plot representation 考虑 connected 和 strongly connected:
- connected 就是指 $\forall$ 任意两个 node $x,y$，至少有一条 edge 连接它们。可以是 $x \to y$，可以是 $y \to x$，或者 both
- connected 并不要求有 self loop
- strongly connected 就是 connected 并要求 $\forall x \in X$，都要有一个 $x \to x$ 的 self loop
定义上有：connected $\land$ reflexive $\equiv$ strongly connected
1.3.4 Uniqueness
Injective: (a.k.a. left-unique) $\forall x,y,z \in X$, $xRz \land yRz \implies x = y$
Functional: (a.k.a. right-unique) $\forall x,y,z \in X$, $xRy \land xRz \implies y = z$
- Such a relation is also called a partial function
1.3.5 Totality
Serial: (a.k.a. left-total, or simply total) $\forall x \in X$, 一定 $\exists y \in X$ such that $xRy$
- 注意它并没有限定 $y$ 的个数，可以有多个 $y_i$ 都满足 $xRy_i$，至少有一个
- Such a relation is also called a multivalued function
- 我觉得 serial 的意思是：从一个起始 $x_0$ 出发，不断找 $x_iRx_{i+1}$，能得到一个 $x_0 x_1 x_2 \dots$ 的 sequence
- The successor function used by Peano to define natural numbers is the prototype for a serial relation.
Surjective: (a.k.a right-total) $\forall y \in Y$, 一定 $\exists x \in X$ such that $xRy$ (扩展定义 $R \subseteq X \times Y$)
1.3.6 Special Relations / Combinations of Properties
Orderings:
\[\begin{aligned} \textbf{Similarity Relation} &\equiv R \text{ which is } \textit{ reflexive } \land \textit{ symmetric } \\ \textbf{Equivalence Relation} &\equiv R \text{ which is } \textit{ reflexive } \land \textit{ symmetric } \land \textit{ transitive } \\ \textbf{Congruence Relation} &\equiv \text{an equivalence relation } R \text{ which is "compatible" with the associated operation on $X$} \\ \textbf{Pre-order} &\equiv R \text{ which is } \textit{ reflexive } \land \textit{ transitive } \\ \textbf{Partial Order} &\equiv R \text{ which is } \textit{ reflexive } \land \textit{ antisymmetric } \land \textit{ transitive } \\ \textbf{Strict Partial Order} &\equiv R \text{ which is } \textit{ irreflexive } \land \textit{ asymmetric } \land \textit{ transitive } \\ \textbf{Strict Weak Order} &\equiv \text{a strict partial order } R \text{ whose incomparable relation } \oslash_R \textit{ is an equivalence relation } \\ \textbf{Total Order} &\equiv R \text{ which is } \textit{ reflexive } \land \textit{ antisymmetric } \land \textit{ transitive } \land \textit{ connected } \\ \textbf{Strict Total Order} &\equiv R \text{ which is } \textit{ irreflexive } \land \textit{ asymmetric } \land \textit{ transitive } \land \textit{ connected } \end{aligned}\]- 我个人认为 equivalence 可以看作是 “没有任何 order”
- pre-order 的意思是 “almost a partial order” 或者 “one more step and you’ll get a partial order”
- partial 的意思是 “允许存在两个元素没有 order (i.e. incomparable)”
- total 的意思是 “任意的两个元素间都有 order (i.e. comparable)”
举例：
- Similarity Relation: 限定误差范围内的约等于 $\approx$
- Equivalence Relation: equality $=$
-
Congruence Relation: “congruent modulo $n$”, as in $a \equiv b \pmod n$
- See 下文 1.3.7
- Partial Order: subset $\subseteq$
- Strict Partial Order: strict subset $\subset$
-
Strict Weak Order: 类似赛马、F-1 赛车、或者田径比赛的 ranking $<$：
- $x < y$ 表示 “$x$ 比 $y$ 排名靠前”
- $x = y$ 表示 “$x$ 比 $y$ 排名相同” (成绩相同，并列第 X 名)
- 但存在 “没有完赛” 的情况，所有没有完赛的选手的成绩是 incomparable 的，且是 equivalent 的
- Total Order: less than or equal to $\leq$
- Strict Total Order: less than $<$
注意 strict subset $\subset$ 不是 strict weak order，原因：
- $\oslash_{\subset}$ 不是 transitive 的，所以不是 equivalence relation
- 假设 $\exists$ 集合 $X,Y,Z$
- $X \oslash_{\subset} Y \iff X \not\subset Y \land Y \not\subset X$
- $Y \oslash_{\subset} Z \iff Y \not\subset Z \land Z \not\subset Y$
- 但可能有 $X \subset Z$ 或者 $Z \subset X$
- e.g. $X = \lbrace 1 \rbrace, Y = \lbrace 3 \rbrace, Z = \lbrace 1,2 \rbrace$
Lemma: An $R$ which is symmetric, transitive, and serial is an equivalence relation.
Proof: 由 serial 可知 $\forall x \in X, \exists y$ such that $xRy$.
再加上 symmetric，可知 $\forall x \in X, \exists y$ such that $xRy$ and $yRx$.
再加上 transitive，可知 $\forall x \in X, xRx$, 得到 reflexive. $\blacksquare$
Uniqueness 性质的组合：
\[\begin{aligned} \textbf{One-to-one} &\equiv R \text{ which is } \textit{ injective } \land \textit{ functional } \\ \textbf{One-to-many} &\equiv R \text{ which is } \textit{ injective } \land \neg \textit{ functional } \\ \textbf{Many-to-one} &\equiv R \text{ which is } \neg \textit{ injective } \land \textit{ functional } \\ \textbf{Many-to-many} &\equiv R \text{ which is } \neg \textit{ injective } \land \neg \textit{ functional } \end{aligned}\]Uniqueness + Totality 性质的组合：
\[\begin{aligned} \textbf{Function} &\equiv R \text{ which is } \textit{ right-unique (functional) } \land \textit{ left-total (serial) } \\ \textbf{Injection} &\equiv F \text{ which is } \textit{ left-unique (injective) } \\ \textbf{Surjection} &\equiv F \text{ which is } \textit{ right-total (surjective) } \\ \textbf{Bijection} &\equiv F \text{ which is } \textit{ left-unique (injective) } \land \textit{ right-total (surjective) } \end{aligned}\]where $F$ is a $\textbf{Function}$.
1.3.7 题外话：Congruence Relation
Definition: Let $(S, \circ)$ be an algebraic structure. Suppose $\circ$ is a $n$-ary operation. Let $R$ be an equivalence relation on $S$. If $\forall x_1,\dots,x_n,y_1,\dots,y_n \in S$:
\[x_1 R y_1, \, x_2 R y_2, \, \dots, \text{ and } x_n R y_n \Longrightarrow (x_1 \circ x_2 \circ \dots \circ x_n) R (y_1 \circ y_2 \circ \dots \circ y_n)\]we call $R$ compatible with $\circ$ and $R$ is a congruence relation on $S$.
同理也有 “congruence class”, “$x,y$ are congruent” 这些说法
2. Asymptotic Notations
2.1 Definitions
假定有 functions $f,g: \mathbb{Z}^{+} \to \mathbb{R}^{+} \cup \lbrace 0 \rbrace$
Big-Oh Notation: $f = O(g)$ if $\exists$ constant $c > 0$ and $\exists n_0$ such that $\forall n \geq n_0$, $f(n) \leq c \cdot g(n)$
- 这个 $n_0$ 是一个 threshold，表示 “$f(n) \leq c \cdot g(n)$” 这个关系是 “当 $n$ 充分大、足够大以后” 才出现的
Big-Omega Notation: $f = \Omega(g)$ if $\exists$ constant $c > 0$ and $\exists n_0$ such that $\forall n \geq n_0$, $f(n) \geq c \cdot g(n)$
Big-Theta Notation: $f = \Theta(g)$ if $f = O(g) \land f = \Omega(g)$
- 换言之，$f = \Theta(g)$ if $\exists$ constants $c_1, c_2 > 0$ and $\exists n_0$ such that $\forall n \geq n_0$, $c_1 \cdot g(n) \leq f(n) \leq c_2 \cdot g(n)$
Little-oh Notation: $f = o(g)$ if $\forall$ constant $c > 0$, $\exists n_0$ such that $\forall n \geq n_0$, $f(n) < c \cdot g(n)$
Little-omega Notation: $f = \omega(g)$ if $\forall$ constant $c > 0$, $\exists n_0$ such that $\forall n \geq n_0$, $f(n) > c \cdot g(n)$
2.2 Problem with those Notations
Knuth describes such notations as “one-way equalities”, since if the sides could be reversed:
“… we could deduce ridiculous things like $n = n^2$ from the identities $n = O(n^2)$ and $n^2 = O(n^2)$.”
“… the equality sign is not symmetric with respect to such notations.”
“… mathematicians customarily use the $=$ sign as they use the word is in English: Aristotle is a man, but a man isn’t necessarily Aristotle.”
所以有的教材会写成 $f \in O(g)$，也就是把 $O(g)$ 理解成一个 function 的集合 (或者 equivalence class)。但还是不如从 relation 的角度来理解 asymptotic notations (我就是为了这口醋包了前面那么多饺子)。
2.3 Asymptotic Relations
Lemma: Big-Oh is a Partial Order.
Proof: (1) $O$ is reflexive, obviously.
(2) $O$ is antisymmetric, obviously.
(3) $O$ is transitive, obviously.
(4) $O$ is not connected. I.e. $\exists f,g$ such that $f \cancel{O} g$ and $g \cancel{O} f$.
E.g.
\[\begin{aligned} f(n) &= \begin {cases} 1&n\text{ is even}\\n&n\text{ is odd} \end {cases} \newline g(n) &= \begin {cases} n&n\text{ is even}\\1&n\text{ is odd} \end {cases} \end{aligned}\]E.g.
\[\begin{aligned} f(n) &= 1 + n + n \times (-1)^n \newline g(n) &= 1 + n - n \times (-1)^n \end{aligned}\]$\blacksquare$
Lemma: Big-Omega is a Partial Order.
Lemma: Big-Theta is an Equivalence Relation.
Proof: (1) $\Theta$ is reflexive, obviously.
(2) $\Theta$ is symmetric.
If $f \Theta g$, then $\exists$ constants $c_1, c_2 > 0$ and $\exists n_0$ such that $\forall n \geq n_0$, $c_1 \cdot g(n) \leq f(n) \leq c_2 \cdot g(n)$.
At the same time, we have $\frac{1}{c_2} \cdot f(n) \leq g(n) \leq \frac{1}{c_1} \cdot f(n)$, so $g \Theta f$.
(3) $\Theta$ is transitive.
If $f \Theta g$, then $\exists$ constants $c_1, c_2 > 0$ and $\exists n_0$ such that $\forall n \geq n_0$, $c_1 \cdot g(n) \leq f(n) \leq c_2 \cdot g(n)$.
If $g \Theta h$, then $\exists$ constants $c_3, c_4 > 0$ and $\exists n_1$ such that $\forall n \geq n_1$, $c_3 \cdot h(n) \leq g(n) \leq c_4 \cdot h(n)$.
Therefore $\exists n_{\ast} = \max(n_0, n_1)$ such that $\forall n \geq n_{\ast}$, $c_1 \cdot c_3 \cdot h(n) \leq f(n) \leq c_2 \cdot c_4 \cdot h(n)$. I.e. $f \Theta h$. $\blacksquare$
Lemma: Little-oh is a Strict Partial Order.
Lemma: Little-omega is a Strict Partial Order.
Comments