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 可以表示成：

1. directed graph: 每一组 $xRy$ 都用一条 $x \to y$ 的 edge 表示
2. 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$

\[M_1 = \begin{bmatrix} 1 & - & -\\ - & 1 & -\\ - & - & 1 \end{bmatrix} \,\,\,\, M_2 = \begin{bmatrix} 0 & - & -\\ - & 0 & -\\ - & - & 0 \end{bmatrix}\]

我们说这组 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$

这个混乱的命名，我觉得背后的逻辑是：

1. 从定义的形式上来看，symmetric 的定义直接加个否定就变成了 asymmetric，非常的漂亮
2. 但这么定义下的 asymmetric 暗含了 irreflexive (因为你不可能同时有 $xRx$ 和 $x \cancel{R} x$)，有点过于 strong
3. relax 一下，不要求 irreflexive 的非对称，就变成了 antisymmetric

还是结合 boolean matrix representation 记忆：

1. symmetric 就是 $M_{i,j} = M_{j,i}$，主对角线上随意，比如 $M_1$
2. asymmetric 就是 $M_{i,j} \neq M_{j,i}$，主对角线上全是 0，比如 $M_2$
3. antisymmetric 就是 $M_{i,j} \neq M_{j,i}$，但主对角线上随意，比如 $M_3$

\[M_1 = \begin{bmatrix} - & \alpha & \beta\\ \alpha & - & \gamma\\ \beta & \gamma & - \end{bmatrix} \,\,\,\, M_2 = \begin{bmatrix} 0 & \overline\alpha & \overline\beta\\ \alpha & 0 & \overline\gamma\\ \beta & \gamma & 0 \end{bmatrix} \,\,\,\, M_3 = \begin{bmatrix} - & \overline\alpha & \overline\beta\\ \alpha & - & \overline\gamma\\ \beta & \gamma & - \end{bmatrix} \,\,\,\,\]

定义上有：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 的特殊情况：

1. if $x = y = z$，obvious implication
2. if $x = y \neq z$，obvious implication
3. if $x = z \neq y$，transitive 等价于：如果有 $x \to y \to x$ 这样一个 loop，那么就会有 $x \to x$ 的 self loop
4. 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:

1. connected 就是指 $\forall$ 任意两个 node $x,y$，至少有一条 edge 连接它们。可以是 $x \to y$，可以是 $y \to x$，或者 both
2. connected 并不要求有 self loop
3. 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.