Relations

我們有比函數還要更有彈性、更一般化的概念，稱為 關係（relations） 。

我們會定義數學上的關係，並且談到在數學上大量使用的兩個關係：等價關係及次序關係。次序關係將會貫穿整個拓樸學領域。

關係（relations） 的定義如下：

Def.

$$
A \enspace relation \enspace on \enspace set \enspace A \enspace is
$$

$$
a \enspace subset \enspace C \subseteq A \times A
$$

這時候我們會把 relation $C$ 表示成 $xCy$ ，來代表 $(x, y) \in C$。

這時我們會理解成，$x$ 跟 $y$ 有 $C$ 的關係。

一個函數 $f: A \rightarrow A$ 是 $A \times A$ 的子集，所以函數也是一種關係。

任何是 $A \times A$ 的子集，都可以被視為一種關係。

ex.

$P$ 代表世界上全人類的集合，我們定義 $D \subseteq P \times P$ 為一種關係：

$$
D = \{ (x, y) \mid x \enspace is \enspace a \enspace descendant \enspace of \enspace y \}
$$

$D$ 代表的是子孫關係，$xDy$ 代表 $x$ 是 $y$ 的子孫。

我們也可以定義血緣關係 $B$：

$$
B= \{ (x, y) \mid x \enspace has \enspace an \enspace ancestor \enspace who \enspace is \enspace also \enspace an \enspace ancestor \enspace of \enspace y \}
$$

也就是，$x$ 跟 $y$ 有共同的祖先的話，那代表 $x$ 跟 $y$ 有血緣關係。如此一來，血緣關係就會是對稱的，子孫關係則不是。

Equivalence relations

在 set $A$ 上的等價關係，是在 set $A$ 上的一種關係 $C$，並且滿足以下條件：

1. Reflexivity（自身性）： $\forall x \in A, xCx$
2. Symmetry（對稱性）： If $xCy$, then $yCx$
3. Transitivity（遞移性）： If $xCy$ and $yCz$, then $xCz$

關係並沒有強制規定說要用大寫字母表示，所以我們後面改成用大家比較常用的 $\sim$ （tilde）。

1. $\forall x \in A, x \sim x$
2. If $x \sim y$, then $y \sim x$
3. If $x \sim y$ and $y \sim z$, then $x \sim z$

ex.

我們可以檢驗看看 $\leq$ 在正整數（$\mathbb{N}$）上是不是一種等價關係？

1. Reflexivity（自身性）： $\forall x \in \mathbb{N}, x \leq x$ 成立
   • $1 \leq 1, 2 \leq 2, 3 \leq 3, …$
2. Symmetry（對稱性）： If $x \leq y$, then $y \leq x$ 不成立
   • $1 \leq 2, but \enspace not \enspace 2 \leq 1$
3. Transitivity（遞移性）： If $x \leq y$ and $y \leq z$, then $x \leq z$ 成立
   • $1 \leq 2, 2 \leq 4, then \enspace 1 \leq 4$

故 $\leq$ 不是等價關係。

ex.

假設一種等價關係是 $x \sim y$ ，定義為 $x \enspace (mod \enspace 3) = y \enspace (mod \enspace 3)$ ，那麼在 $\mathbb{N}$ 上，我們有 $5 \enspace (mod \enspace 3) = 2 = 8 \enspace (mod \enspace 3)$ 。那這有滿足等價關係嗎？

1. Reflexivity（自身性）： $\forall x \in \mathbb{N}, x \sim x$ 成立
   • $1 \enspace (mod \enspace 3) = 1 \enspace (mod \enspace 3), …$
2. Symmetry（對稱性）： If $x \sim y$, then $y \sim x$ 成立
   • $1 \enspace (mod \enspace 3) = 4 \enspace (mod \enspace 3)$
   • $4 \enspace (mod \enspace 3) = 1 \enspace (mod \enspace 3)$
3. Transitivity（遞移性）： If $x \sim y$ and $y \sim z$, then $x \sim z$ 成立
   • $1 \enspace (mod \enspace 3) = 4 \enspace (mod \enspace 3), 4 \enspace (mod \enspace 3) = 7 \enspace (mod \enspace 3),$
   • $then \enspace 1 \enspace (mod \enspace 3) = 7 \enspace (mod \enspace 3)$

故 $\leq$ 是等價關係。（以上非嚴謹證明）

所以可以把 $5 \sim 8$ 這兩者視為等價。

如果存在一種等價關係，那麼 set $A$ 裡的元素可以歸類成不同的 等價類（equivalent class），假設 $x \in A, E \subseteq A$ ，我們有：

Def.

$$
E = \{ y \mid y \sim x \}
$$

ex.

延續上面一個例子，$x \sim y$ 是等價關係，那麼我們就可以把 $\mathbb{N}$ 拆成不同的等價類：

$$
1 \sim 4, 4 \sim 7, 7 \sim 10, …
$$

$$
E_1 = \{1, 4, 7, 10, …\}
$$

$$
2 \sim 5, 5 \sim 8, 8 \sim 11, …
$$

$$
E_2 = \{2, 5, 8, 11, …\}
$$

$$
3 \sim 6, 6 \sim 9, 9 \sim 12, …
$$

$$
E_3 = \{3, 6, 9, 12, …\}
$$

等價類有以下的特性：

Lemma

$$
Two \enspace equivalent \enspace classes \enspace E \enspace and \enspace E’ \enspace are \enspace either \enspace disjoint \enspace or \enspace equal.
$$

白話文就是兩個等價類不是一樣就是互斥的。

有這樣的等價類，我們可以用 $\mathscr{E}$ 來表示所有等價類的集合（collection）。藉由以上的 Lemma，我們知道每個等價類都是互斥的。這樣我們可以把他看成是對 set $A$ 的分割（partition）。

Def.

$$
A \enspace partition \enspace of \enspace a \enspace set \enspace A \enspace is \enspace a \enspace collection \enspace of \enspace disjoint \enspace nonempty \enspace subsets \enspace of \enspace A
$$

$$
whose \enspace union \enspace is \enspace all \enspace of \enspace A.
$$

研究 set $A$ 上的等價關係等同於是研究 set $A$ 的分割。

Order relations

在 set $A$ 上的 次序關係（order relations, simple order or linear order），是在 set $A$ 上的一種關係 $\lt$，並且滿足以下條件：

1. Comparability（可比性）： $\forall x, y \in A, x \neq y, either \enspace x \lt y \enspace or \enspace y \lt x$
2. Nonreflexivity（非自身性）： $\nexists x \in A, x \lt x$
3. Transitivity（遞移性）： If $x \lt y$ and $y \lt z$, then $x \lt z$

Def.

$$
\lt \enspace is \enspace an \enspace order \enspace relation \enspace on \enspace set \enspace X, a \lt b
$$

$$
(a, b) = \{ x \mid a \lt x \lt b \} \enspace is \enspace an \enspace open \enspace interval \enspace on \enspace X
$$

我們可以像這樣去定義 開區間（open interval）。如果 $(a, b) = \emptyset$，那稱 $a$ 是 $b$ 的 緊鄰前元（immediate predecessor），而 $b$ 是 $a$ 的 緊鄰後元（immediate successor）。

假定有 $A$ 跟 $B$ 兩個集合，有兩個相對應的次序關係 $\lt_A$ 跟 $\lt_B$。我們說這兩個集合有相同的 次序類型（order type）：

Def.

$$
\exists f: A \rightarrow B, f \enspace is \enspace bijective
$$

$$
s.t. \enspace a_1 \lt_A a_2, then \enspace f(a_1) \lt_B f(a_2)
$$

這樣的雙射函數有保留次序關係。

ex.

在實數區間 $(1, -1)$ 有跟 $\mathbb{R}$ 相同的次序類型。

考慮函數 $f: (1, -1) \rightarrow \mathbb{R}$：

$$
f(x) = \frac{x}{1 - x^2}
$$

他是一個嚴格遞增函數（保留次序關係）且為雙射。

接下來我們談談 字典序關係（dictionary order relation），他是定義在 $A \times B$ 上的次序關係，假定 $A$ 跟 $B$ 集合上有次序關係 $\lt_A$ 跟 $\lt_B$。

Def.

$$
\lt \enspace on \enspace A \times B \enspace is \enspace a_1 \times b_1 \lt a_2 \times b_2
$$

$$
if \enspace a_1 \lt_A a_2, or \enspace a_1 = a_2 \enspace and \enspace b_1 \lt_B b_2
$$

ex.

所謂的字典序就是先比較第一個字元，如果一樣再比較第二的字元的次序，如此繼續下去。

$$
aaa < aab < abb
$$

如此一來，就可以為 $A \times B \times \dots$ 這樣子的集合定義次序了。

在實數中，你或許以前看過最小上界的特性。你可以為任意的有序集合定義這樣的特性。

假設 set $A$ 有次序關係 $\lt$，$A_0 \subseteq A$，

Def.

$$
b \in A_0, \forall x \in A_0, x \le b
$$

$$
b \enspace is \enspace the \enspace largest \enspace element \enspace of \enspace A_0
$$

如果相反的話，

Def.

$$
a \in A_0, \forall x \in A_0, x \ge a
$$

$$
a \enspace is \enspace the \enspace smallest \enspace element \enspace of \enspace A_0
$$

我們很簡單可以知道，一個集合會有最多一個最大的元素，以及最多一個最小的元素。

那如果我們要說，$A_0$ 有上界（bounded above）：

Def.

$$
b \in A, \forall x \in A_0, x \le b
$$

$$
b \enspace is \enspace an \enspace upper \enspace bound \enspace for \enspace A_0
$$

而上界的元素中，最小的稱為最小上界（least upper bound），或是 supremum，記為 $sup \enspace A_0$：

Def.

$$
X = \{ x \mid \forall x \enspace is \enspace upper \enspace bound \enspace for \enspace A_0 \}
$$

$$
The \enspace smallest \enspace element \enspace of \enspace X \enspace is \enspace least \enspace upper \enspace bound
$$

他有可能屬於 $A_0$，如果 $sup \enspace A_0 \in A_0$，他同時也是 $A_0$ 最大的元素。

相反，$A_0$ 有下界（bounded below）：

Def.

$$
a \in A, \forall x \in A_0, x \ge a
$$

$$
a \enspace is \enspace an \enspace lower \enspace bound \enspace for \enspace A_0
$$

而下界的元素中，最大的稱為最大下界（greatest lower bound），或是 infimum，記為 $inf \enspace A_0$：

Def.

$$
Y = \{ y \mid \forall y \enspace is \enspace lower \enspace bound \enspace for \enspace A_0 \}
$$

$$
The \enspace greatest \enspace element \enspace of \enspace Y \enspace is \enspace greatest \enspace lower \enspace bound
$$

他有可能屬於 $A_0$，如果 $inf \enspace A_0 \in A_0$，他同時也是 $A_0$ 最小的元素。

這些跟所謂的 最大值（maximum） 或是 最小值（minimum） 不太一樣：

Def.

$$
b \in A_0, \forall x \in A_0, x \le b
$$

$$
b \enspace is \enspace the \enspace maximum \enspace of \enspace A_0
$$

Def.

$$
a \in A_0, \forall x \in A_0, x \ge a
$$

$$
a \enspace is \enspace the \enspace minimum \enspace of \enspace A_0
$$

主要差別會是值是否在 $A_0$ 裏面。

這時候就可以來定義 最小上界性（least upper bound property）：

Def.

$$
\forall A_0 \subseteq A, A_0 \enspace has \enspace a \enspace least \enspace upper \enspace bound
$$

$$
A \enspace has \enspace least \enspace upper \enspace bound \enspace property.
$$

相反則是，最大下界性（greatest lower bound property）。