1. Relation (Mathmatics)Permalink

Wikipedia 写得挺好，这里总结一下。

1.1 DefinitionPermalink

Given a set $X$, a relation $R$ over $X$ is a set of ordered pairs of elements from $X$, formally: $R\subseteq \{(x,y)\mid x,y\in X\}$.

• 你也可以扩展成 $R\subseteq \{(x,y)\mid (x,y)\in X\times Y\}$，但这么定义就排除了 $(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⟺x\cancel{R}y\wedge y\cancel{R}x$

1.2 Representation of RelationsPermalink

如果 $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=\{(x,y)\mid x^2+y^2=1\}$

1.3 Properties of RelationsPermalink

1.3.1 ReflexivityPermalink

Reflexive: $\mathrm{\forall }x\in X,xRx$

Irreflexive: $\mathrm{\forall }x\in X,x\cancel{R}x$

我们可以完全不用它的英文名字，也不用管中文翻译 (因为后面对称性的命名简直灾难！)，结合 boolean matrix representation 来记忆：

• reflexive 就是主对角线全是 1，比如 $M_1$
• irreflexive 就是主对角线全是 0，比如 $M_2$

我们说这组 properties 是 non-exhausitive 的，意思是 $\mathrm{\exists }R$ 既不是 reflexive 也不是 irreflexive 的，结合 boolean matrix representation 很容易举出一个反例。

1.3.2 SymmetryPermalink

Symmetric: $\mathrm{\forall }x,y\in X$, $xRy⟹yRx$

Asymmetric: $\mathrm{\forall }x,y\in X$, $xRy⟹y\cancel{R}x$

Antisymmetric: $\mathrm{\forall }x,y\in X$, $xRy\wedge yRx⟹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}\ne M_{j,i}$，主对角线上全是 0，比如 $M_2$
3. antisymmetric 就是 $M_{i,j}\ne M_{j,i}$，但主对角线上随意，比如 $M_3$

定义上有：asymmetric $\equiv$ antisymmetric $\wedge$ irreflexive

同样，这组 properities 也不是 exhausitive 的，结合 boolean matrix representation 也很容易举出反例。

1.3.3 Transitivity & ConnectednessPermalink

Transitive: $\mathrm{\forall }x,y,z\in X$, $xRy\wedge yRz⟹xRz$

Connected: $\mathrm{\forall }x,y\in X$, $x\ne y⟹$ $xRy$ or $yRx$. Or equivalently $\mathrm{\forall }x,y\in X$, $xRy$ or $yRx$ or $x=y$

Strongly Connected: $\mathrm{\forall }x,y\in X$, $xRy$ or $yRx$

考虑 transitive 的特殊情况：

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

Proof: (1) 假定 $R$ 是 transitive $\wedge$ irreflexive. 假定 $\mathrm{\exists }x,y\in X$ 同时满足 $xRy$ 和 $yRx$ (从而不满足 asymmetric)

根据 transitive 定义，$xRy\wedge yRx⟹xRx$，不满足 irreflexive，矛盾。所以 R 一定满足 asymmetric

(2) 假定 $R$ 是 transitive $\wedge$ asymmetric. 因为 asymmetric implies irreflexive，所以 $R$ 一定是 irreflexive. $◼$

结合 2D plot representation 考虑 connected 和 strongly connected:

1. connected 就是指 $\mathrm{\forall }$ 任意两个 node $x,y$，至少有一条 edge 连接它们。可以是 $x\to y$，可以是 $y\to x$，或者 both
2. connected 并不要求有 self loop
3. strongly connected 就是 connected 并要求 $\mathrm{\forall }x\in X$，都要有一个 $x\to x$ 的 self loop

定义上有：connected $\wedge$ reflexive $\equiv$ strongly connected

1.3.4 UniquenessPermalink

Injective: (a.k.a. left-unique) $\mathrm{\forall }x,y,z\in X$, $xRz\wedge yRz⟹x=y$

Functional: (a.k.a. right-unique) $\mathrm{\forall }x,y,z\in X$, $xRy\wedge xRz⟹y=z$

• Such a relation is also called a partial function

1.3.5 TotalityPermalink

Serial: (a.k.a. left-total, or simply total) $\mathrm{\forall }x\in X$, 一定 $\mathrm{\exists }y\in X$ such that $xRy$

• 注意它并没有限定 $y$ 的个数，可以有多个 $y_i$ 都满足 $xR{y}_i$，至少有一个
• Such a relation is also called a multivalued function
• 我觉得 serial 的意思是：从一个起始 $x_0$ 出发，不断找 $x_{i}R{x}_{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) $\mathrm{\forall }y\in Y$, 一定 $\mathrm{\exists }x\in X$ such that $xRy$ (扩展定义 $R\subseteq X\times Y$)

1.3.6 Special Relations / Combinations of PropertiesPermalink

Orderings:

• 我个人认为 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(\mathrm{mod}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 $\le$
• Strict Total Order: less than $<$

注意 strict subset $\subset$ 不是 strict weak order，原因：

• ${\oslash }_{\subset }$ 不是 transitive 的，所以不是 equivalence relation
• 假设 $\mathrm{\exists }$ 集合 $X,Y,Z$
  • $X{\oslash }_{\subset }Y⟺X\not\subset Y\wedge Y\not\subset X$
  • $Y{\oslash }_{\subset }Z⟺Y\not\subset Z\wedge Z\not\subset Y$
  • 但可能有 $X\subset Z$ 或者 $Z\subset X$
  • e.g. $X=\{1\},Y=\{3\},Z=\{1,2\}$

Lemma: An $R$ which is symmetric, transitive, and serial is an equivalence relation.

Proof: 由 serial 可知 $\mathrm{\forall }x\in X,\mathrm{\exists }y$ such that $xRy$.

再加上 symmetric，可知 $\mathrm{\forall }x\in X,\mathrm{\exists }y$ such that $xRy$ and $yRx$.

再加上 transitive，可知 $\mathrm{\forall }x\in X,xRx$, 得到 reflexive. $◼$

Uniqueness 性质的组合：

Uniqueness + Totality 性质的组合：

where $F$ is a $\mathbf{\text{Function}}$.

1.3.7 题外话：Congruence RelationPermalink

Definition: Let $(S,\circ )$ be an algebraic structure. Suppose $\circ$ is a $n$-ary operation. Let $R$ be an equivalence relation on $S$. If $\mathrm{\forall }{x}_1,\dots ,x_n,y_1,\dots ,y_n\in S$:

we call $R$ compatible with $\circ$ and $R$ is a congruence relation on $S$.

同理也有 “congruence class”, “$x,y$ are congruent” 这些说法

2. Asymptotic NotationsPermalink

2.1 DefinitionsPermalink

假定有 functions $f,g:{\mathbb{Z}}^{+}\to {\mathbb{R}}^{+}\cup \{0\}$

Big-Oh Notation: $f=O(g)$ if $\mathrm{\exists }$ constant $c>0$ and $\mathrm{\exists }{n}_0$ such that $\mathrm{\forall }n\ge n_0$, $f(n)\le c\cdot g(n)$

• 这个 $n_0$ 是一个 threshold，表示 “$f(n)\le c\cdot g(n)$” 这个关系是 “当 $n$ 充分大、足够大以后” 才出现的

Big-Omega Notation: $f=\mathrm{\Omega }(g)$ if $\mathrm{\exists }$ constant $c>0$ and $\mathrm{\exists }{n}_0$ such that $\mathrm{\forall }n\ge n_0$, $f(n)\ge c\cdot g(n)$

Big-Theta Notation: $f=\mathrm{\Theta }(g)$ if $f=O(g)\wedge f=\mathrm{\Omega }(g)$

• 换言之，$f=\mathrm{\Theta }(g)$ if $\mathrm{\exists }$ constants $c_1,c_2>0$ and $\mathrm{\exists }{n}_0$ such that $\mathrm{\forall }n\ge n_0$, $c_1\cdot g(n)\le f(n)\le c_2\cdot g(n)$

Little-oh Notation: $f=o(g)$ if $\mathrm{\forall }$ constant $c>0$, $\mathrm{\exists }{n}_0$ such that $\mathrm{\forall }n\ge n_0$, $f(n)<c\cdot g(n)$

Little-omega Notation: $f=\omega (g)$ if $\mathrm{\forall }$ constant $c>0$, $\mathrm{\exists }{n}_0$ such that $\mathrm{\forall }n\ge n_0$, $f(n)>c\cdot g(n)$

2.2 Problem with those NotationsPermalink

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 RelationsPermalink

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. $\mathrm{\exists }f,g$ such that $f\cancel{O}g$ and $g\cancel{O}f$.

E.g.

E.g.

$◼$

Lemma: Big-Omega is a Partial Order.

Lemma: Big-Theta is an Equivalence Relation.

Proof: (1) $\mathrm{\Theta }$ is reflexive, obviously.

(2) $\mathrm{\Theta }$ is symmetric.

If $f\mathrm{\Theta }g$, then $\mathrm{\exists }$ constants $c_1,c_2>0$ and $\mathrm{\exists }{n}_0$ such that $\mathrm{\forall }n\ge n_0$, $c_1\cdot g(n)\le f(n)\le c_2\cdot g(n)$.

At the same time, we have $\frac{1}{c_2}\cdot f(n)\le g(n)\le \frac{1}{c_1}\cdot f(n)$, so $g\mathrm{\Theta }f$.

(3) $\mathrm{\Theta }$ is transitive.

If $f\mathrm{\Theta }g$, then $\mathrm{\exists }$ constants $c_1,c_2>0$ and $\mathrm{\exists }{n}_0$ such that $\mathrm{\forall }n\ge n_0$, $c_1\cdot g(n)\le f(n)\le c_2\cdot g(n)$.

If $g\mathrm{\Theta }h$, then $\mathrm{\exists }$ constants $c_3,c_4>0$ and $\mathrm{\exists }{n}_1$ such that $\mathrm{\forall }n\ge n_1$, $c_3\cdot h(n)\le g(n)\le c_4\cdot h(n)$.

Therefore $\mathrm{\exists }{n}_{\ast }=max(n_0,n_1)$ such that $\mathrm{\forall }n\ge n_{\ast }$, $c_1\cdot c_3\cdot h(n)\le f(n)\le c_2\cdot c_4\cdot h(n)$. I.e. $f\mathrm{\Theta }h$. $◼$

Lemma: Little-oh is a Strict Partial Order.

Lemma: Little-omega is a Strict Partial Order.